Булевы функции и формулы алгебры высказываний. ДНФ и КНФ.

Булевы функции – любые функции от 0 и 1. всего их 2^

Логическая функция – когда любым двум элементам ставится в соответствие элемент из этого же множества.

Логическая функция – только ^ v -> не. В добавок к ним пара булевых (не являющимися логическими) функций:

Штрих Шеффера (анти конъюнкция). Интересно отметить, что:

Стрелка Пирса (Лукашевича). В действительности:

Дизъюнктиивная нормальная форма (ДНФ)— форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ (я бы не рискнул так громко об этом заявлять ахахах). Для этого можно использовать закон двойного отрицания, закон де Моргана, закон дистрибутивности. Дизъюнктивная нормальная форма удобна для автоматического доказательства теорем.

Конъюнктивная нормальная форма (КНФ) форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов.

Алгоритм построения КНФ и ДНФ

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

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:

3) Избавиться от знаков двойного отрицания.

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

Также можно использовать следующие свойства:

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

(X v Y) v Z = X v (Y v Z)

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

X v Y = Y v Z

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

X ^ Y v X ^ Z = X ^ (Y v Z)

XY v X notY = X ^ (Y v notY) = X – минимальная дизъюнктивная нормальная форма.

Y v notY = 1

Не нашли, что искали? Воспользуйтесь поиском: