Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Двойственность. Принцип двойственности

Определение 3.6. Булева функция /(ац,..., хп) называется двойственной к функции f*(xi,...,rrn), если

Если в равенстве (3.4) взять отрицание над обеими его частями и подставить вместо переменных Х, ..., хп их отрицания, то получим, что f*(xi,...,.xn) двойственна f(xi,...,xn), т. е. отношение двойственности симметрично. Ясно, что для любой функции двойственная функция определяется однозначно.

Определение 3.7. Функция называется самодвойственной, если она совпадает со своей двойственной, т. е. /(ад,..., xn) = f(x 1,..., хп).

Зная таблицу истинности булевой функции, легко получить таблицу истинности двойственной ей функции. По определению 3.6 двойственные функции принимают противоположные значения на противоположных значениях переменных, значит, заменив в таблице истинности все О па 1, и наоборот, мы получим таблицу истинности двойственной функции Г{хи.. . ,хп).

П р и м е р 3.9. Составить таблицу истинности для функции, двойственной функции f(x,x2,^3), которая задана табл. 10.

Таблица 10

Х

х2

х3

f(xl,X2,X 3)

0

0

0

1

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

0

1

1

0

1

1

1

1

1

Заменим в табл. 10 все 0 на 1, и наоборот, мы получим таблицу ИСТИННОСТИ ИСКОМОЙ функции /** (гг 1, Х‘2, Жз).

Таблица 11

Xi

х2

Хз

f*{xiy х2) Хз)

1

1

1

0

1

1

0

1

1

0

1

1

1

0

0

0

0

1

1

1

0

1

0

1

0

0

1

0

0

0

0

0

В силу закона де Моргана х V у = ху и закона двойного отрицания имеем: хУ у = ху. Последнее равенство показывает, что дизъюнкция и конъюнкция - двойственные друг другу функции. Очевидно, что двойственные функции константы 1 и 0, а отрицание - самодвойственная функция.

Упражнение 5. Проверить, что двойственными являются функции а) X] =Хо и Х 0.Т-2, б) Х [х<2 и Ххо.

Сформулируем принцип двойственности: если в формуле F, представляющей функцию /, все знаки функций заменить двойственными им, то полученная формула F* будет представлять функцию /*, двойственную /.

Отсюда получаем важное утверждение, доказательство которого можно найти в [7] §1.1.4.

Теорема 3.5. Если формулы F и G равносильны (F = G), то и двойственные им формулы F* и G* равносильны (F* = G*).

В булевой алгебре принцип двойственности реализуется следующим образом: если в булевой формуле /у представляющей функцию /, все конъюнкции заменить дизъюнкциями, дизъюнкции конъюнкциями, О заменить 1, а 1 заменить 0, то получим формулу F*, которая представляет функцию /*, двойственную /. Теорема 3.5 расширяет запас равносильностей в булевой алгебре. Например, закон исключенного третьего AW^A = 1 можно рассматривать как равносильность, полученную из закона противоречия АУ^А = 0. Это замечание относится к каждой паре равносильностей 1, 2, 3, 4, 9, 10 из списка важнейших равносильностей булевой алгебры, приведенных в пункте 3.3.

Упражнение 6. Показать, что /(.т, у, z) = ху V xz V yz - самодвойственная функция.

Принцип двойственности можно использовать для представления логической функции в совершенной конъюнктивной нормальной форме (СКИФ).

Сформулируем определение СКНФ как определение, двойственное определению СДНФ (см. определение 3.5).

Определение 3.8. Формула F называется совершенной конъюнктивной нормальной форм,ой (СКНФ), если она представляет собой конъюнкцию дизъюнкций переменных од, ..., хп либо их отрицаний, причем выполняются следующие условия:

  • 1) каждый конъюнктивный сомножитель содержит все п переменных;
  • 2) все конъюнктивные сомножители различны:
  • 3) ни один конъюнктивный сомножитель не содержит переменную и отрицание этой переменной;
  • 4) ни один конъюнктивный сомножитель не содержит одну и ту же переменную дважды.

Ясно, что если формула F - СДНФ функции /(ад, ...,а?п), то двойственная формула F* - СКНФ двойственной функции /*(ац,..., хп) = — f(x 1,...,жп). Исходя из этого, можно сформулировать алгоритм построения СКНФ по таблице истинности.

В таблице истинности функции f(xi,...,xn) выбираем все нулевые наборы и каждому такому набору сопоставляем дизъюнкцию переменных. в которой переменная Xk записывается с отрицанием, если ту- = 1 и без отрицания в противном случае. Например, для функции / из примера 3.8 СКНФ имеет вид:

В силу принципа двойственности справедлива теорема, двойственная теореме 3.4.

Теорема З.б. Всякая логическая функция f(xi,...,xn), которая не равна тождественно 1, единственным образом (с точностью до перестановки конъюнктивных сомножителей) представима в виде СКНФ.

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>