20. Скнф, кнф, днф

Т: Для любой формулы в АВ, отличной от тождественно истинной существует ее представление в виде:

f(x1,x2,..,xn) (x1^(1)x2^(2)…xn^(n)),

_сн(1,2,..,n) | f(1,2,..,n)0 - СКНФ данной формулы.



При доказательстве используем принцип двойственности

СКНФ->СДНФ Двойной двойственностью:

f(x1,x2,..,xn)(f*( x1,x2,..,xn))*[не явл.≡0=>СДНФ](x1^(1)^.x2^(2)…^.xn^(n))*≡

(1,2,..,nE2)|f*(1,2,..,n)1

≡ [f(x1,x2,..,xn)]  x1^(1)x2^(2)…xn^(n),

(1,2,..,n)|f(1,2,..,n)0



Пр: x1→x2 ≡ (1x2) [CКНФ] ≡ 1(x22)x2(x11)≡

≡1x212x1x21x2 ≡1x212x1x2 [СДНФ]

КНФ, ДНФ

Обозначим V={x1,x1,x2,x2,..,xn,xn}

Элементарная конъюнкция - конъюнкция всех элементов множества υ  V

По опр: ДНФ –дизъюнкция элементарных конъюнкций

Пр: x1x2x3

Аналогично:

Элементарная дизъюнкция - дизъюнкция всех элементов множества υ  V

КНФ – конъюнкция элементарных дизъюнкций.

Змч.: СДНФ является ДНФ, СКНФ является КНФ

21. Основные проблемы ав

; Все формулы АВ делятся на 3 части

1) Множество всех тождественно истинных формул (тавтологии)

2) Множество всех тождественно ложных формул (противоречия)

3) Нетривиально выполнимые формулы, т.е при некоторой подстановке значений истинности в формулу мы получаем истину, при другой подстановке – ложь ;

1 проблема (проблема разрешения): Определение, является ли формула тождественно истинной, тождественно ложной или неправильно выполненной.

Эта проблема разрешается при помощи ДНФ и КНФ.

1) Критерий тождественной истинности формул (2 Т)

Т.: f(x1,x2,..,xn)≡1 [≡ (КНФ) (xi1^(di1)…xik^(dik))] когда в равносильной КНФ все элементарные дизъюнкции тождественно истинны (xi1^(di1)…xik^(dik)≡1)

Т.: ЭД является тождественно истинной (xi1^(di1)…xik^(dik)≡1)  когда в ней присутствует пара:  i, что xii

2) Критерий тождественной ложности формул (2 Т)

Т.: Для того чтобы формула алгебры высказывания была тождественно ложной f(x1,x2,..,xn)≡0 [≡ (ДНФ) (xi1^(di1) …xik^(dik))], необходимо и достаточно, чтобы в равносильной ей ДНФ все ЭК были тождественно ложны (xi1^(di1) …xik^(dik)≡0).

Т.: Для того, чтобы ЭК была тождественно ложной (xi1^(di1) …xik^(dik)≡0), необходимо и достаточно, чтобы в ней существовала хотя бы для одной переменной пара-переменная и ее отрицание (i, что xii).

Из этих теорем следует решение сформулированной проблемы:

1) Формулу представляем в виде КНФ, проверяем по теоремам на тождественную истинность. Если она выполняется, то процедура заканчивается.

2) Если тождественная истинность не выполняется, строим ДНФ, проверяем на тождественную ложность. Если она выполняется, то процедура заканчивается.

3) Если не выполняется => формула нетривиально выполнимая.

2 проблема (равносильности): Известны 2 формулы в АВ f1(x1,..,xn) и f2(x1,..,xn).

Требуется определить равносильны ли эти формулы.

Эта проблема разрешается при помощи СНФ.

1) Известно, что для любой формулы, отличной от тождественно ложной с точностью до перестановки слагаемых однозначно строится СДНФ (для f1 и f2)

Если формулы равносильны, то у них д.б. одинаковая СДНФ.

2) Если нельзя построить СДНФ (fi ≡0 ), тогда можно построить СКНФ (для f1 и f2)

3 проблема представления: Можно ли двузначную (0,1) функцию n двузначных переменных f(x1,x2,..,xn) реализовать формулой в АВ ^F(x1,x2,..,xn), так что f(x1,x2,..,xn)= ^F(x1,x2,..,xn)