3.B. Правіла падстановы. Адмаўленне да прапазіцыйнай формулы, якая змяшчае , , l. Прынцып дуальнасці (без доказаў).

Сцверджанне 2 (правіла падстановы). Няхай А ёсць формула, у якую ўваходзяць толькі літары А,, А₂,...,А_П, а А* атрымліваецца з А падстановай у А прапазіцыйных форму­ла)/ А₁,А₂,...,А_Я замест А,,А₂,...,А_П адпаведна. Калі \= А, тады \= А', г.зн., падстановаў таўталогію дае таўталогію.

Сцверджанне 3. Няхай А - формула, пабудаваная з прапазіцыйных літараў A,,A,,...,A_n і іхніх адмаўленняў-А₁, A₂,..., A_n 3дапамогаютолькісымболяў логікавых аперацыяў & і v, А⁺ - формула, атрыманая з А заменам & на v, v на & і кожнай прапазіцыйнай літары А_і (без адмаўлення) на A_і і наадварот. Тады А = А⁺.

Прыклад 8. Няхай А ёсць А &(BvC), тады А = Av(B&С).

Сцверджанне 4 (прынцып дваістасці (дуальнасці)).

Няхай A і В -формулы гаго ж ныіляду, што ўсцверджанні 3, А', В' - формулы, атрыманыя з A і В замечай & на v, v на &. Гады:

1. Калі |=A , гады |=A';

2. Калі |= A , тады |=A';

3. Калі |= A <=> В, тады |=A'<=>В',

(d) Калі |=A=>B, тады |= B'=> A'.

Заўвага. Калі ў запісе формулаў А , В прануіпчаныя дужкі паводле дамоўленасці, якую мы зрабілі пасля азначоння прапазіцыйнай формулы, тады перад выкананпем анерацыяў ⁺ і' сцверджанняў 3 і 4 іх трэба аднавіць.

6.B. Прапазіцыйныя формулы і булевы функцыі. Поўныя сістэмы злучнікаў (без доказу тэарэмы). Днф і кнф. Кан'юнкцыя адмаўленняў і штрых Шэфера.

Як было адзначана вышэй, кожная прапазіцыйная форму­ла, у якую ўваходзяць п літараў, вызначае булеву функцыю ад п аргументаў. Логікава эквівалентным формулам адпавядае тая сама булева функция. Натуральна паўстае пытанне: ці ўсе бу­левы функцыі спараджаюцца такім чынам?

Сцверджанне 1. Кожная булева функцыя спараджаецца некаторай праназіцыйнай формулай, якая мае злучнікі ┐, & i v.

Вынік 1. Для кожнай з наступных трох йараў злучнікаў: & і ┐, v і ┐, => і ┐ і для ўсякай булевай функцыі f існуе прапазіцыйная формула, якая змяшчае злучнікі толькі з гэтай пары і спараджае f.

Увядзем два новыя злучнікі ↓ (кап 'юнкцыя адмаўленняў) і | (дыз'юнкцыя адмаўленняў, або штрых Шэфера)

формуламі:

А↓В = (┐А&┐В), A|B = (┐Av┐B).

Вынік 2. Для кожнага з злучнікаў ↓ і | і для ўсякай булевай функцыі f існуе прапазіцыйная формула, якая змяшчае

толькі адзін гэты злучнік і спараджае f.

3 сцверджання 1 вынікае, што кожная прапазіцыйная фор­мула А логікава эквівалентная формуле, якая з'яўляецца дыз'юнкцыяй некалькіх (магчыма, аднаго) дыз'юнкцыйных складнікаў, кожны з якіх ёсць кан'юнкцыя адной або некалькіх лі іараў ці іх адмаўленняў; такая формула называецца дыз'юнк-цыйнай нармальнай формай (ДНФ) формулы А .

Формула, якая з'яўляецца кан'юнкцыяй некалькіх (магчыма, аднаго) кан'юнкцыйных складнікаў, кожны з якіх ёсць дыз'юнкцыя адной або некалькіх літараў ці іх адмаўленняў, логікава эквівалентная прапазіцыйнай формуле А, называецца кан 'юнкцыйнай нармальнай формой (КНФ) формулы А .