Свойства конъюнкции, дизъюнкции и отрицания.

Простые свойства логических функций:

; ; ;

; ; ;

1. сочетательный закон: ; ;

2. переместительный закон: ; ;

3. распределительный закон: ;

4. закон поглощения: ;

5. закон склеивания: ;

6. закон де Моргана: ;

Данный закон распространяется на любое число переменных:

                 

7. закон Блейка: если  и  - какие-то логические функции, тогда

 

Система логических функций называется полной, если через эти функции можно выразить любую другую функцию.

 

Докажем, что любую логическую функцию можно выразить с помощью операций конъюнкции, дизъюнкции и отрицания. Логическая функция  задана с помощью таблицы истинности:

			…
…	…	…	…	…	…

- константы 0 или 1, определяющие значения аргументов x, - константы 0 или 1, определяющие значения функции для данных аргументов x.

Зададим логические функции от аргумента x:

, при

, при

Представим исходную функцию в виде:

Докажем справедливость данного равенства.

Возьмём произвольную n-ю строку таблицы, в ней , где

, при

, при

Для выбранного n и для любого i верно равенство:

Подставим в

Далее рассмотрим любую другую строку кроме n-ной. Пусть она имеет номер m. Так как все строки таблицы содержат разные наборы , то хотябы в одном столбце будет различие. Пусть различие в k-том столбце , тогда

, при

, при

Тоесть в любой строке отличной от n существует хотя бы один k-элемент, для которого  Подставим в m-ную строку:

В результате получим:

Дизъюнкти́вная норма́льная фо́рма(ДНФ) – этоформа представления, при которой логическое выражение функции строится в виде дизъюнкции ряда членов, каждый из которых является простой конъюнкцией аргументов или их инверсий.

Конъюкти́вная норма́льная фо́рма(КНФ)определяется аналогичным образом.

 Если в каждом члене ДНФ представлены все аргументы (или их инверсии) функции, то такая форма носит название совершенной дизъюнктивной нормальной формы (СДНФ).

Для любой функции алгебры логики существует своя единственная СДНФ. Рассмотрим пример получения СДНФ используя таблицу истинности логической функции.

0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

 

Отметим строки таблицы, в которых . Рассмотрим значения переменных, при которых функция принимает единичное значение. Если значение переменной равно 0, то она записываетсяв СДНФ с инверсией, если 1 – то без инверсии.

СДНФ:

Недостаток функций СНДФ или СНКФ, в их сложности.

Методы упрощения функции называются методами мимнимизаци. Минимизация означает переход от СДНФ к ДНФ с максимальным уменьшением количества логических переменных и логических операций.

Методы минимизации:

1. картами Карно

2. Квайна

3. Квайна- Мак-Клоски

 

 

Структуры данных.

 

В памяти компьютера данные представляются в двоичной системе счисления.

Напомним формулу перевода из двоичной системы счисления в десятичную:

Для удобства записи и представления двоичных чисел часто используют шестнадцатеричную систему счисления. Формула перевода из шестнадцатеричной в десятичную приведена ниже:

Указатели.

Указатель - переменная, значением которой является адрес ячейки памяти. То есть указатель ссылается на блок данных из области памяти.

Объявление указателей:

char *ch;

ch=&a;         // присваивание указателю адреса переменной a.

Массив-структура, объединяющая определённое количество данных одного типа.

char M[10].

M[0]=1;

M[1]=100;

По стандарту языка Си имя массива без индекса “M” является указателем на нулевой элемент данного массива.

Более сложными структурами данных являются стеки, очереди, связные списки.

Стек - структура данных, в которой доступ к элементам организован по принципу «последним пришёл — первым вышел».

Рис. 1 Упрощённая структура стека

 

Очередь — структура данных, в которой доступ к элементам организован по принципу «первый пришёл — первый вышел»

Связный список - структура данных, состоящая из значения и ссылок (указателей) на другие элементы списка.

Рис. 2 упрощённые структуры односвязного и двусвязного списков.

 

К нелинейным структурам данных относятся: граф, дерево, куча.

Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта. Граф состоит из узлов (вершин) и связей между ними.

Связи могут иметь направление. В этом случае они называются дугами, а граф ориентированный. Если у связей нет направления, они называются рёбрами, а граф – не ориентированный. Дугам и рёбрам могут ставится в соответствие некоторые значения (веса). Два узла графа называются смежными, если существует дуга или ребро соединяющая их. Узел называется инцидентным к ребру, если он является его вершиной, т.е. ребро направлено к этому узлу.

Степенью узла называется число ребер графа, которым принадлежит этот узел. Узел изолированный, если его степень равна 0 (то есть если он не инцидентен ни одному ребру).

Рассмотрим три способа задания графа: аналитический, геометрический и матричный.

Аналитический способ задания. Граф G = G(X, F) задаётся с помощью двух множеств: множество вершин и множество ребер, а также отношения между ними, которое указывает, какие вершины соединены с какими ребрами.   Этот способ задания мало информативен и носит академический характер.

Геометрический способ задания графа.

Рис 3. Геометрическое задание графа.

 

Матричный способ задания графа.

Матрица смежности.

	a	b	c	d	e
a	0	1	1	0	0
b	1	0	1	1	0
c	1	1	0	0	0
d	0	1	0	0	1
e	0	0	0	1	0

Матрица инциденции.

	r1	r2	r3	r4	r5
a	1	1	0	0	0
b	1	0	1	1	0
c	0	1	1	0	0
d	0	0	0	1	1
e	0	0	0	0	1

Для ориентированного графа матрица инцидентности будет содержать 1 в клетке, если вершина будет началом дуги, и -1, если вершина будет концом дуги.

	r1	r2	r3	r4	r5	r6
a	1	1	0	1	1	0
b	-1	0	1	0	0	0
c	0	-1	-1	0	0	0
d	0	0	0	-1	0	-1
e	0	0	0	0	-1	1

 

 

 

Маршрутом в графе называется последовательность вершин и ребер, в которой любые два соседних элемента инцидентны. Например (a r₁ b r₃ c).

Граф называют связным, если между любой парой вершин этого графа существует как минимум один путь.

Цепь — маршрут, все рёбра которого различны.

Цикл — замкнутая цепь. Для ориентированных графов цикл называется контуром.

Цикл, содержащий в себе все рёбра графа, называется Эйлеровым. Другими словами это маршрут, проходящий по всем рёбрам графа по одному разу и возвращающийся в исходную точку. Граф называется Эйлеровым, если в нём существует Эйлеров цикл.

 

 

Теорема Эйлера – граф без изолированных вершин является Эйлеровым тогда и только тогда, когда степени всех его вершин чётные.

Доказательство: дан связный граф G у которого степени всех вершин четные. Пусть v₀ – произвольная вершина графа. Построим цепь начинающуюся в вершине v₀ по рёбрам e_1…e_k  и вершинам v₀…v_k до момента, когда цепь нельзя будет продолжить. Докажем, что v_k=v₀ (что построенная цепь является циклом). Предположим, что v_k≠v₀. При построении цепи мы n раз входили в вершину v_k и n-1 раз выходили. В построенной цепи ровно 2n-1 ребер инциндентных v_k. Так как степень вершины v_k чётная, то существует инцендентное v_k ребро не входящее в цепь. Получили противоречие в построении цепи и v_k=v₀. Обозначим первоначальный цикл C₁. Он может быть эйлеровым, а может и не быть таковым. Если C₁ не эйлеров, то среди оставшихся рёбер найдётся инциндентное одной из вершин цикла. Из данной вершины можно построить цикл C₂ аналогично первому циклу C_1. Такого рода построения можно продолжать, пока все циклы не будут охватывать все рёбра и граф не окажется Эйлеровым.

Цикл, проходящий через каждую вершину графа ровно один раз называется Гамильтоновым. Граф называется Гамильтоновым, если в нём существует гамильтонов цикл.

Теорема Оре. Пусть G – связный граф, содержащий n-вершин, где n > 3. Если сумма степеней любых двух не смежных вершин графа больше или равна n, то G – гамильтонов граф.

Теорема Дирака. Пусть G – связный граф, содержащий n-вершин, где n > 3. Если степень любой вершины больше или равна n/2, то G – гамильтонов граф.

Теоремы Оре и Дирака являются достаточными но не необходимыми условиями существования гамильтонова графа.

Дерево.

Деревом называют граф, который не содержит циклов.

Элементы составляющие дерево называются узлами. Единственный начальный элемент называется корнем. Каждый узел дерева имеет ноль или более узлов-потомков(детей), которые располагаются ниже по дереву. Узел, имеющий потомка, называется узлом-родителем относительно своего потомка. Каждый узел имеет не больше одного предка. Узел, не имеющий потомков, называется листом. Высотой дерева называется самый длинный путь в дереве из корня к листу.

Бинарное дерево — древовидная структура данных, в которой каждый узел имеет не более двух потомков (левый и правый ребёнок).

Куча.

Куча– это разновидность дерева, в котором всегда выполняется условие: если B является узлом-потомком узла A, то А ≥ В (при построении max-кучи), либо А ≤ В при построении (min-кучи).

Бинарная куча – это бинарное дерево, удовлетворяющее трём условиям:

- значение в любой вершине не меньше, чем значения её потомков;

- глубина листьев (расстояние до корня) отличается не более чем на 1 слой;

- последний слой заполняется слева направо.

 

 

Основные понятия теории алгоритмов.

 

Алгоритм – набор некоторого числа правил, задающих последовательность выполнения операций для решения определённой задачи.

Свойства алгоритма:

1) Конечность. Алгоритм всегда должен заканчиваться после выполнения определённого числа шагов.

2) Определённость. Каждый шаг алгоритма должен быть точно определён. Действия, которые нужно выполнить, должны быть строго и недвусмысленно определены для каждого возможного случая.

3) Наличие входных данных. Любой алгоритм имеет некоторое число входных данных, задаваемых до начала его работы.

4) Наличие выходных данных. Любой алгоритм имеет некоторое количество выходных данных, которые однозначно связаны с входными.

5) Понятность. Алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.

 

Классификация алгоритмов.

Алгоритмы подразделяются на:

1) Линейные. Описывают следующие одна за другой команды, которые выполняются толко один раз.

2) Разветвляющиеся. Описывают действия, выполняющиеся в зависимости от каких-либо условий. В языках программирования эта возможность реализовани при помощи конструкций if – else.

3) Циклический. Описывает действия которые могут повторятся. В языках программирования такая возможность реализуется заданием циклических структур while, for и др. При разработке циклических алгоритмов важно продумать варианты корректного завершения.