Нормальные формы для формул алгебры высказываний

Пропозициональные переменные. Классификация формул.

В формулу (ХY) Z вместо переменных X, Y, Z можно подставлять конкретные высказывания, после чего вся формула будет превращаться в некоторое составное высказывание. Переменные, вместо которых можно подставлять высказывания, т.е. переменные, пробегающие множество высказываний, называют пропозициональными переменными, или высказывательными переменными, или переменными высказываниями.

Теперь дадим точное определение формулы алгебры высказываний. Определение 2.1

1. Каждая отдельно взятая пропозициональная переменная есть формула алгебры высказываний.

2. Если F₁ и F₂ — формулы алгебры высказываний, то

выражения F₁& F₂, F₁V F₂, F₁ F₂ , F₁ F₂ ,также являются формулами алгебры высказываний.

3. Никаких других формул алгебры высказываний, кроме получающихся согласно п. 1 и 2, нет.

Определения такого типа называются индуктивными.

Формулы алгебры высказываний подразделяются на следующие типы: выполнимые, тавтологии, опровержимые и тождественно ложные.

Формула алгебры высказываний называется выполнимой, если некоторая ее конкретизация является истинным высказыванием, т.е. существуют такие конкретные высказывания А₁ , А₂,..., А_n, которые, будучи подставленными в эту формулу вместо переменных Х₁, Х₂,..., Х_n соответственно, превращают ее в истинное высказывание. Таким образом, F(X₁ ,X2,..., Х_n) выполнима, если существуют такие конкретные высказывания А₁, А₂,..., А_n, что (F(A₁,А₂,..., А_n)) = 1.

Формула F(X_1,Х₂,..., Х_n) называется тавтологией, или тождественно истинной, если она превращается в истинное высказывание при всякой подстановке вместо переменных конкретных высказываний А₁ , А₂,..., А_n,т.е. если (F(A₁,А₂,..., А_n)) = 1 для любых высказываний

Формула F(X_1,Х₂,..., Х_n)называется опровержимой, если существуют такие конкретные высказывания А₁ , А₂,..., А_n, которые превращают данную формулу в ложное высказывание F(А₁ , А₂,..., А_n.),т.е. (F(A₁,А₂,..., А_n)) = 0. Другими словами, опровержимые формулы — это формулы, не являющиеся тавтологиями.

Наконец, формула F(X_1,Х₂,..., Х_n)называется тождественно ложной, или противоречием, если (F(A₁,А₂,..., А_n)) = 0 для любых конкретных высказываний A₁,А₂,..., А_n. Другими словами, тождественно ложные формулы — это такие формулы, которые

не являются выполнимыми.

. В алгебре логики важную роль играют следующие равенства:

1. Законы коммутативности (переместительности):

а) A &В В & А - коммутативность конъюнкции;

б) А V В В V А - коммутативность дизъюнкции.

2. Законы ассоциативности (сочетательности):

а) (А&В) &С А & (В& С) - ассоциативность конъюнкции

б) (А V 5) V С А V (В V С) - ассоциативность дизъюнкции

3. Законы идемпотентности:

а) А А А - идемпотентность конъюнкции;

б) AV А А - идемпотентность дизъюнкции.

4. Законы дистрибутивности (распределительности):

а) А& (В V С) (А & В) V (А & С) - дистрибутивность конъюнкции относительно дизъюнкции;

б) А V(В& С) (А V Б) & (А V С) - дистрибутивность дизъюнкции относительно конъюнкции.

5. Свойства нуля и единицы:

а) А&0 0;

б) AV0 A;

в) A&1 A;

г) АV1 1.

6. A - правило снятия двойного отрицания.

7. Законы де Моргана;

а) А& В V ;

б)

8. A 0 - закон противоречия.

9. А V = 1 - закон исключённого третьего.

10. Законы поглощения:

а) А & (А V В) А;

б) AV(A&B)A.

11. Правила склеивания-расщепления:

а) (А V ) & (А V) А;

б) (A&)V(A&B) A

12. AB V В - выражение импликации через дизъюнкцию и отрицание.

13. А В (АВ) (В А) - выражение эквивалентности через конъюнкцию и импликацию.

14. Выражение эквивалентности через конъюнкцию, дизъюнкцию и отрицание:

а) А В (А & В) V (& );.

б) AB (VB)&(AV);.

Множество всех булевых в базисе S1={¬, &, V} образуют булеву алгебру. Все формулы в этой алгебре можно записать с помощью этих трех связок.

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

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

Если x логическая переменная, а ,то выражение

называется литерой.

Литеры х и ┐х называются контрарными. Конъюнктом называется конъюнкция литер. Дизъюнктом называется дизъюнкция литер. Например, формулы x y ┐z и х у х ┐х являются конъюнктами, формулыxVyV┐z и xVyV┐x - дизъюнктами, а формула ┐z является одновременно и конъюнктом и дизъюнктом.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного числа конъюнктов.

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

Более просто: ДНФ - это сумма произведений, а КНФ - это произведение логических сумм

Литеры х и ┐х называются контрарными. Конъюнктом называется конъюнкция литер. Дизъюнктом называется дизъюнкция литер. Например, формулы x-y-z и х у х х являются конъюнктами, формулы xvyvz и xvyvx - дизъюнктами, а формула z является одновременно и конъюнктом и дизъюнктом.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного числа конъюнктов.

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

Более просто: ДНФ - это сумма произведений, а КНФ - это произведение логических сумм

Примеры.

1. X yVyzVx — это ДНФ (сумма произведений).

2. (хV ┐у V ┐z)• (хVу)• z —это КНФ (произведение сумм).

3. ┐xVyVzV┐w — это ДНФ и КНФ (одновременно).

4. ┐х • у • ┐z • w — это ДНФ и КНФ (одновременно).

5. (xVxVy)(yVzVx)-z — это КНФ.

6. x y ┐z и х у х ┐х — это ДНФ.

7. х (х V yz) x-┐y-z — это не нормальная форма (не ДНФ и не КНФ).

Пусть функция f записана в базисе S1. Данная функция приводится к нормальной форме следующим путем:

1) используем законы де Моргана, чтобы преобразовать формулу к виду, в котором знаки отрицания относятся только к отдельным переменным;

2) применяем правило снятия двойного отрицания: ┐┐x=x;

3) далее использовать законы дистрибутивности, причем необходимо использовать первый закон дистрибутивности для приведения к ДНФ

HI & (H2VH3)=(H1 &H2)V(H1 &НЗ),

и второй закон дистрибутивности для приведения к КНФ.

H1V(H2&H3)=(H1VH2)&(H1VH3).

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

Пример 1. Для приведения к ДНФ используем 1-ый закон дистрибутивности.

x ┐y x y ┐z (yVz)=x ┐y (┐xV┐yV┐┐z) (yVz)=(x┐y┐xVx┐y┐yVx┐yz)-(yVz)= -это КНФ

= (0 V х ┐у V х ┐у z) (у V z) = (х ┐у V х ┐у z) (у V z) = это другая

КНФ

= x┐yyVx┐yzyVx┐yzVx┐yzz = 0V0Vx┐yzVx┐yz =

=x┐yzVx┐yz -это ДНФ

Дата добавления: 2014-01-04