Тема 8.3.Составление формулы по заданной таблице истинности

Пример 8.4:

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

Выбираем строки, где и выписываем конъюнкции всех переменных, причём, если переменная в этом наборе равна 1, то записываем её саму, а если переменная = 0, то её отрицание.

Для данного примера:

конъюнкция этих дизъюнкций и будет искомой формулой:

Определение: Конъюнкция называетсяэлементарной, если в неё входят переменные и их отрицания. Количество различных переменных, входящих в элементарную конъюнкцию или элементарную дизъюнкцию, называетсярангом.

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

Строго доказано, что любую формулу булевой алгебры можно выразить с помощью операций , &,. Интуитивно этот факт очевиден, вспомним алгоритм составления формулы по таблице истинности. При этом мы используем только эти операции. Такая форма записи называется дизъюнктивной нормальной формой (ДНФ). Это своеобразный механизм нормализации формул алгебры логики.

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

Аналогично определяется КНФ – коньюктивная нормальная форма.

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

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

Следствие:Любую булеву формулу, не являющуюся тождественно ложной можно представить в виде суперпозиции &,,, причём отрицание относится только к переменным.

Тема 8.4. Двойственность

Определение:Функцияназываетсядвойственнойк функции, если.

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

Пример 8.5:Если рассматривать логические функции, то, очевидно, дизъюнкция двойственна конъюнкции и наоборот (непосредственно следует из законов Де Моргана). Отрицание является самодвойственной функцией. Функция-константадвойственна функции. Ещё один традиционный пример самодвойственной функции – функция.

Пользуясь определением двойственности нетрудно доказать следующее утверждение, называемое принципом двойственности.

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

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

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