Краткий курс лекций по Дискретной математике (стр. 6 )

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

Но как было показано, в результате равносильных преобразований формула F(x, у, z) может быть приведена к виду:

которому соответствует РКС, изображенная на схеме 8, содержащей пять переключателей.

Задачи для самостоятельного решения.

По таблице истинности найти формулы, определяющие функции F1, F2 .

x	y	z	F1	F2
1	1	1	1	1
1	1	0	1	0
1	0	1	0	1
1	0	0	0	1
0	1	1	0	0
0	1	0	1	0
0	0	1	1	1
0	0	0	0	0

2. Составьте формулу для булевой функции F(x, y,z) = 1, если а) только одна какая-либо переменная равна нулю; б) если большинство переменных равны нулю. Упростите полученные формулы.

3. Составить РКС для формул:

4. Построить схемы, реализующие следующие булевы операции:

импликацию; эквиваленцию.

5. Построить РКС для функций, если известно, что:

F(0,1,0)=F(1,0,1)=F(1,1,1)=1; F(1,0,1)=F(1,1,0)=1;

 

6. Упростить РКС:

 

 

7. Проверить равносильность схем:

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

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

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

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

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

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

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

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

ЛЕКЦИЯ 7

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

ПЛАН:

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

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

Главная

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры.

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.  Путем равносильных преобразований получить СДНФА.

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

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

Перечислим свойства совершенства для КНФ:

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

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

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

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

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

Любая не тождественно истинная формула имеет единственную СКНФ.

Один из способов получения СКНФ состоит в использовании таблицы истинности для :

1.  Составляют СДНФ.

2.  Для получения СКНФА строят отрицание СДНФ, т. е.

Или из наборов переменных, при которых А ложна, составляют элементарные дизъюнкции, в которых переменная, вошедшая со значением истина вводится с отрицанием, а со значением ложь – без отрицания. Из полученных элементарных дизъюнкций составляют конъюнкцию.

Другой способ основан на равносильных преобразованиях

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

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

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

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

4.  Если какая-либо дизъюнкция содержит xi вместе с отрицанием, то В º 1. И В исключают из КНФ.

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

Примеры.

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

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

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

Тогда