16. Любая формула в алгебре высказывания равносильна некоторой булевой.

Ранг формулы – кол-во операций, входящих в формулу

≡, ~≡, при этом справа стоят булевы формулы

2⁰ Предположим, что теорема верна при f≤m-1. Докажем, что теорема справедлива для  формулы ранга f=m. Будем рассматривать формулы, в которых присутствует m операций. Если среди этих операций нет , ~, то формула по определению булева, в противном случае F1  F2≡F1F2, F1~F2≡F1F2F1F2 , где F1, F2 – формулы ранга f≤m-1 и они равносильны некоторым булевым формулам

17. Теорема о подстановке формул в формулу в ав.

Т: (о подстановке формулы в формулу)

Пусть дана формула F(x1,x2,..,xn), и такие формулы: f1(y1,y2,..,ym), f2(y1,y2,..,ym)…, fn(y1,y2,..,ym) – формулы от m переменных.

Тогда F(f1(y1,y2,..,ym), f2(y1,y2,..,ym),.. fn(y1,y2,..,ym)) – тоже формула от переменных y1, y2,…, ym

Пр: xy→zx = АF(x,y,z)

f1=x~z; f2=xz ; f3= x

(x~z)(xz) →x(x~z)=F(f1,f2,f3)=F1(x,z)

Т: (о равносильной подстановке)

Пусть F(x1,x2,..,xn)  G(x1,x2,..,xn)

Пусть f1(y1,y2,..,ym)  g1(y1,y2,..,ym)

…

Пусть fn(y1,y2,..,ym)  gn(y1,y2,..,ym),

Тогда F(f1(y1,..,ym),.., fn(y1,..,ym))  G(g1(y1,..,ym),..,gn(y1,..,ym))

Пр: хотя бы закон де Моргана

18. Лемма о разложении формулы в ав по переменной.

; Пусть E2, обозначим x^ = {x, если =1; , если =0}

Уравнение x^=1 имеет решение x=

Л: (о разложении формулы в алгебре высказывания)

Пусть f(x1,x2,..xn) – формула в АВ

Тогда: f(x1,x2,..,xn)  xi f(x1,..,x(i-1),1,x(i+1),..,xn)

xi f(x1..,x(i-1),0,x(i+1),..,xn) xi^i f(x1,..,i,..,xn), (iE2).

Доказательство:

Чтобы доказать равносильность формул надо доказать их равенство на любом наборе значений истинности (тогда совпадут таблицы истинности).

Множество всех наборов значений истинности: {=(1,2,..,n)},kE2, разобьем на два не пересекающихся подмножества I={ | i=1} , II={ | i=0}

Если докажем лемму для множества I отдельно и для множества II, то она будет доказана

1. I => i = 1 => f(1,..,n)  1f(1,..,(i-1),1,(i+1),..,n)1f(1,..,n)  f(1,..,n) - верно

2. II => i = 0 => f(1,..,n)  0f(1,..,n)0f(1,..,(i-1),0,(i+1),..,n)  1f(1,..,i,..,n) - верно



19. СДНФ

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

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

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



Пусть f(x1,x2,..,xn) - формула в АВ

Разложим эту формулу по переменной x1

Тогда: f(x1,x2,..,xn)_снизу(1E2) x1^(1)(1,x2,..,xn)  (разложим по x2 и подставим в разложение)  (1E2)((2E2) x1^(1)^.x2^(2)f(1,2,x3,..,xn))…и т.д. 

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

где f(1,2,..,n) - 0 or 1

Мы можем опустить те слагаемые, для которых f(1,2,..,n)0, и получим

f(x1,x2,..,xn)_сн[(1,2,..,n) | f(1,2,..,n)1] x1^(1)^.x2^(2)…^.xn^(n)

