Множества, отображения, логика (стр. 8 )

Если исходная формула содержит другие операции (импликацию, эквиваленцию), то они предварительно выражаются через конъюнкцию, дизъюнкцию и отрицание с помощью формул (см. п. 4.8):

,

.

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

Можно доказать, что любая булева функция, не являющаяся тождественным нулем, имеет одну и только одну СДНФ.

Если какой-либо слагаемое j данной ДНФ не содержит переменной х, то j заменяется на эквивалентное слагаемое j( = jj. В силу тождеств , одинаковые слагаемые, если они появляются, заменяются одним таким слагаемым.

Пример 9. Продолжая пример 8, приведем полученную функцию  к СДНФ:

=

=

.

Попутно заметим, что из полученной СДНФ получается интересная формула: , как будто член  лишний в левой части. На самом деле это действительно так, ибо как мы только что выяснили

,

при этом

.■

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

конъюнкция ® дизъюнкция,

дизъюнкция ® конъюнкция,

0 ® 1,

1 ® 0.

Пример 10. Формуле  двойственна формула .

Пример 11. Формуле  двойственна формула .

Примечание. Принцип двойственности имеется во многих науках и, в частности, в теории множеств, в которой операции пересечения и объединения являются взаимно двойственными. В геометрии принцип двойственности помогает из доказанной теоремы получать двойственную теорему, справедливость которой следует из справедливости исходной теоремы и принципа двойственности. Последний в случае (проективной) двумерной геометрии гласит: «Если верна теорема А, в которой говорится о точках и прямых, то верна двойственная теорема А*, которая получается из теоремы А взаимной заменой слов «точка» « «прямая», «точка пересечения прямых» « «прямая, проходящая через точки». Ярким примером служит:

Теорема (Дезарг). Если между вершинами двух данных треугольников установлено взаимно однозначное соответствие и три прямые, соединяющие соответственные вершины, пересекаются в одной точке, то три точки пересечения соответственных сторон треугольников лежат на одной прямой (рис. 7).

Двойственная теорема запишется так: Если между сторонами данных треугольников установлено взаимно однозначное соответствие и три точки пересечения соответственных сторон лежат на одной прямой, то три прямые, соединяющие соответственные вершины, пересекаются в одной точке.

4.26. Переключательные схемы. В качестве одной из интерпретаций булевых функций рассмотрим электрическую схему, состоящую из источника напряжения (батареи), лампочки и одного или двух ключей (х и у). Ключи управляются кнопками с двумя состояниями: кнопка нажата (1) и кнопка отпущена (0). Если в исходном состоянии ключ разомкнут, то при нажатии кнопки он замыкается. Ключ может быть сконструирован и так, что в исходном состоянии он замкнут, тогда нажатие кнопки означает его размыкание, т.е. приводит к противоположному результату. Поэтому нормально замкнутые ключи обозначим  и .

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

4.27. Задача. Булева функция f (x, y, z) задана таблицей истинности:

х	y	z	f (x, y, z)
1	1	1	0
1	1	0	1
1	0	1	0
1	0	0	0
0	1	1	1
0	1	0	1
0	0	1	0
0	0	0	1

Требуется: 1) записать функцию f формулой, 2) упростить ее (если это возможно), 3) проверить результат с помощью таблицы истинности, 4) построить граф переключательной схемы для функции f.

Решение. □ 1) Будем искать функцию f в СДНФ, представив ее в виде дизъюнкции всевозможных минитермов третьего ранга:

.

Однако если оставить f в таком виде, мы не получим правильного решения. Следовательно, некоторые минитермы нужно удалить, используя данную таблицу. Из первой строки следует, что при (x, y, z) = (1, 1, 1) функция f равна 0, в то время как минитерм xyz равен 1; следовательно, этот минитерм не может входить в дизъюнкцию f. Аналогично рассуждая, мы приходим к выводу, что минитермы , ,  не должны входить в f. Таким образом, .

2) Упростим найденную функцию:

.

3) Проверим результат с помощью таблицы истинности; при этом значения найденной функции запишем в предпоследнем столбце, а данной функции — в последнем:

х	y	z							f (x, y, z)
1	1	1	0	0	0	0	0	0	0
1	1	0	1	0	1	1	0	1	1
1	0	1	0	0	0	0	0	0	0
1	0	0	1	0	1	0	0	0	0
0	1	1	0	1	1	1	0	1	1
0	1	0	0	0	0	0	1	1	1
0	0	1	0	1	1	0	0	0	0
0	0	0	0	0	0	0	1	1	1

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