Мегаобучалка Главная | О нас | Обратная связь  


Логические операции. СДНФ. СКНФ.




Коммутативность

x1 & x2 = x2 & x1.                                                                    

x1 v x2 = x2 v x1 .

 

Ассоциативность

x 1 v (x2 v x3) = (x1 v x2) v x3.

x 1 & (x2 & x3) = (x1 & x2) & x3 .

Дистрибутивность

x 1 & (x2 v x3) = (x1 & x2) v ( x 1 & x3 ).                                                                

x 1 v ( x 2 & x 3 ) = ( x 1 v x 2 ) & ( x 1 v x 3 ).

 

Отметим также важные соотношения:

 

X v X = X , X & X = X , X v 1 = 1, X & 1 = X ,

X v 0 = X , X & 0 = 0, X v Ø X = 1, X & Ø X = 0.

 

Положим x a =  { X , если a = 1; и

                             Ø X , если a = 0 } .                     

 

Утверждение. Любая функция алгебры логики кроме 0 может быть представлена в форме

   f(x 1...xn) = Ú x1 a & x2 a... & xn a                                  (1)

 

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

Формула (1) определяет СДНФ.

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



Например, выражение   не является СДНФ, а выражение   является СДНФ для списка переменных  {x y z}.


Определение. Простой дизъюнкцией называется дизъюнкция одной или нескольких переменных, при этом каждая переменная (либо сама, либо её отрицание) входит в дизъюнкцию не более одного раза.

Например, выражение является простой дизъюнкцией.

Определение. Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций.

Например, выражение   является КНФ.

Пример. Приведем к КНФ логическую формулу :

F = ( X → Y ) ∧ ( ( Y → Z ) → X ) .

Преобразуем формулу    F к формуле, не содержащей → , получим:

F = ( X ∨ Y ) ∧ ( ( Y → Z ) ∨ X ) = ( X ∨ Y ) ∧ ( ( Y ∨ Z ) ∨ X ) В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:

F = ( X ∨ Y ) ∧ ( ( Y ∧ Z ) ∨ X ) .

По закону дистрибутивности получим КНФ:

F = ( X ∨ Y ) ∧ ( X ∨ Y ) ∧ ( X ∨ Z ) . F = ( X ∨ Y ) ∧ ( X ∨ Y ) ∧ ( X ∨ Z ) . {\displaystyle F=(\neg X\vee Y)\wedge (\neg X\vee \neg Y)\wedge (\neg X\vee \neg Z).}

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

Например, выражение   

        является СКНФ.

Теорема. Всякая булева функция (кроме 0) имеет единственную СДНФ.

Следствие . Всякая булева функция может быть выражена через дизъюнкцию, конъюнкцию и отрицание.

Теорема . Всякая булева функция (кроме 1) может быть единственным образом представлена в виде СКНФ.

Рассмотрим алгоритм построения СДНФ булевой функции по заданной таблице истинности.

В таблице истинности берём только те наборы переменных (x1 , x2 ,..., xn ) , для которых f (x1 , x2 ,..., xn) = 1 и составляем простую конъюнкцию для этого набора так: если xi = 0 , то берём в этой конъюнкции xi , если xi = 1, то берём xi . Составляя дизъюнкцию этих простых конъюнкций, придём к СДНФ.

По аналогии с представлением любой функции (не равной 0) в виде СДНФ можно любую функцию (не равную 1), представить в виде СКНФ. А именно, простые дизъюнкции составляются для тех наборов переменных

(x1 , x2 ,..., xn), для которых f ( x1 , x2 ,..., xn ) = 0, причём если в наборе xi = 1, то в простую дизъюнкцию включаем xi , если же xi = 0 , то в неё включаем xi .

Пример.  Составим СДНФ и СКНФ для импликации и сложения по модулю два.

Решение.

СДНФ для этих функций имеет вид:

СКНФ для этих функций будет иметь вид:

 

 

Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Читайте также:
Как построить свою речь (словесное оформление): При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою...
Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (187)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.018 сек.)
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7