Контрольные вопросы

1. Какое множество называется алгеброй Буля?

2. Какие интерпретации алгебры Буля нам знакомы?

3. Определение функции алгебры логики.

4. Как представить заданную таблицей истинности функцию в виде формулы алгебры логики?

5. Что называется релейно-контактной схемой?

6. Какие виды соединений переключателей соответствуют основным логическим операциям?

7. Как нужно представить формулу, чтобы для нее можно было бы составить РКС?

Лекция 7

ТЕМА: СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ.

ПЛАН:

1. Совершенная дизъюнктивная нормальная форма.

2. Совершенная конъюнктивная нормальная форма.

Главная

1. Совершенная дизъюнктивная нормальная форма.

Формула , составленная для заданной таблицей истинности функции, по выше приведенному правилу обладает свойствами, которые называются свойствами совершенства. Перечислим их:

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

2. Все логические слагаемые различны.

3. Ни одно слагаемое не содержит одновременно переменную и ее отрицание.

4. Ни одно слагаемое не содержит одну и ту же переменную дважды.

Каждой не тождественно ложной формуле соответствует единственная формула с такими свойствами.

Для одной и той же формулы можно составить множество равносильных ей ДНФ. Но среди них существует единственная ДНФ с перечисленными свойствами совершенства.

ДНФ, для которой выполняются свойства совершенства называется совершенной ДНФ (СДНФ).

Составленная формула по таблице истинности и является СДНФ формулы.

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

Приведем соответствующий алгоритм:

1. Путем равносильных преобразований получить какую – либо ДНФ.

2. Если какая-либо элементарная конъюнкция В не содержит переменную х_i , то вводят ее, используя равносильность . И раскрывают скобки.

3. Если в ДНФ входят две одинаковые конъюнкции В, то лишнюю отбрасывают, используя свойство идемпотентности ВV B  B.

4. Если какая-либо конъюнкция содержит x_i вместе с отрицанием, то В  0. И В исключают из ДНФ.

5. Если какая-либо конъюнкция содержит переменную x_i дважды, то одну из них отбрасывают, используя свойство x_i x_i  x_i.

Примеры.

1. Составить СДНФ для формулы по таблице истинности и путем равносильных преобразований.

Составим таблицу истинности, которая содержит 4 строки.

х	у	1	2	3	4
0	0	1	1	0	0
1	0	1	1	0	1
0	1	0	0	0	0
1	1	0	1	1	1

Получим какую-либо ДНФА и преобразованиями доведем до совершенства:

2. Аналогичное задание для формулы

Составим таблицу истинности, содержащую 8 строк.

a	b	c	1	2	3	4
1	1	1	1	1	1	1
1	1	0	0	1	1	1
1	0	1	0	0	1	1
0	1	1	1	0	0	0
0	0	1	0	0	1	0
0	1	0	0	0	1	0
1	0	0	0	0	1	1
0	0	0	0	0	1	0

Преобразуем формулу:

3. Путем равносильных преобразований получить СДНФА.