іччя? <=> Г™ (Г№ (F1 & F2 & ... & Fn) VG) - протиріччя? <=> {По з -ну Деморгана} <=> F1 & F2 & ... & Fn & Г№G - протиріччя?
Спосіб доведення твердження від протилежного: (А Г B) Г (Г№BГ Г№A).
Приклад:
Доведемо, що з формули PГ Q і Г№Q виводиться Г№P, тобто PГ Q, Г№Q | - Г№P/
По 1-й теоремі досить показати, що формула ((PГ Q) & Г№Q) Г Г№P - тавтологія.
PQ123ЛЛІІІЛІІЛЛІЛЛЛЛІІІЛЛ
тавтологія => така виводимість має місце.
Приведення формули до КНФ. Виводимість на основі протиріччя
диз'юнктів зв. диз'юнкція пропозіціональних змінних або їх заперечень, кот.наз. літералами. Для простоти диз'юнкт прийнято записувати як перелік літералів, тобто якщо C = L 1 VL 2 V ... VL n , то С = (L 1 , ..., L n ).
КНФ зв. логічне твір диз'юнктів. Прийнято вважати, що в диз'юнктів змінні і літерали не повторюються, т. к. LVL = L, LV Г№ L Вє І (тотожна істина). У КНФ немає однакових диз'юнктів, т. к. C & C = C.
Приклад:
(AV Г№ B) (AVC) ( Г№ AVB) - КНФ.
КНФ теж можна записувати як безліч диз'юнктів. Т. е. є
КНФ З 1 З 2 < span align = "justify"> ... З n => (C 1 , C 2 , ..., C < span align = "justify"> n ) - КНФ.
Наведемо формулу
F 1 & ... F n & Г№ G до КНФ => питання: КНФ - суперечлива?
Для приведення формули до КНФ використовуються тотожності булевої алгебри:
A Г B = Г№ < span align = "justify"> AVB Вє B = (A Г B) (B Г A) & І = AV І = І & (BVC) = (A & B) V (A & C) V (B & C) = (AVB) & (AVC)
Г№ (AVB) = Г№ A & Г№ B
Г№ (A & B) = Г№ AV Г№ B
з-ни іденпатентності, асоціативності, дистрибутивності.
Приклад: (A Г B) V (A & Г№ C) приведемо до КНФ.
(A Г B) V (A & Г№ C) = Г№ AVBV (A & Г№ C) = ( Г№ AVBVA) & ( Г№ AVBV Г№ C) = Г№ AVBV Г№ C.
Тепер перевіряємо на суперечливість КНФ.
резольвент 2-х диз'юнктів R (C 1 , C 2 ), де
C 1 = L 1 < span align = "justify"> V...
