14. Формулы в алгебре высказываний. Таблицы истинности. Равносильность формул

Формулой в алгебре высказываний – называются конструкции:

1) Сами высказывания - формулы в алгебре высказываний (АВ)

2) Высказывательные переменные (x,y,z,t,…) – формулы в АВ

3) Если F1 и F2 – формулы в АВ, то и ,, F1F2, F1F2, F1F2, F1~F2 – по определению формулы АВ.

Т: (о фиксации переем в АВ)

Пусть F(x1, x2,…, xn) – формула в АВ, которая зависит от n переменных, тогда при любой подстановке aixi высказываний вместо переменных в формулу, получается высказывание для каждого набора ai, F(a1,a2,..,an), {ai}

Таблица истинности формулы F(x1, x2,…,xn) – называется таблица и 0 и 1, в которой перечислены все возможные значения истинности (^a1,^a2,..^an)(в строках), aiE2={0,1}, и значения истинности соответствующего высказывания ^F(a1,a2,..an)(в столбцах).

Каждая строчка из значений истинности (^a1,^a2,..^an)E2x…xE2 (n раз)

Поэтому число различных строк равно количеству элементов в декартовом произведении, а значит || = 2ⁿ

Т.е: если формула зависит от n переменных, то в таблице истинности этой формулы 2ⁿ строк.

Построение таблицы истинности (1-й столбец делится на 2 равные части и т.д.; с правой стороны записывается значение истинности для формулы ^F(a1,a2,..an))

О: Формулы F1(x1, x2,…,xn) и F2(x1, x2,…,xn) - равносильны, если совпадают их таблицы истинности (F1≡F2)

Для доказательства равносильности формул также используются 19 основных равносильностей.

15. Двойственность в ав.

Основные свойства:

0*≡1, по опр. 0*≡≡1; 1*≡0; x*≡≡x; (xy)*≡≡≡xy; (xy)≡xy

Т: (общий принцип двойственности)

Пусть F*(y1,…,yn) – двойственная к F(y1,…,yn), fi*(x1,..,xn) двойственная к fi(x1,..,xn), i=1,…,m

Тогда F*(f1*(x1,..,xn)…,fm*(x1,..,xn)) = Ф*(x1,..,xn) – двойственная к Ф(x1,..,xn)= F(f1(x1,..,xn)…,fm(x1,..,xn))

≡F*(f1*(x1,..,xn)…,fm*(x1,..,xn))

()*≡ ; 2) (xy)*≡xy; 3) (xy)*≡xy

2-й шаг. Предположим, что утверждение теоремы справедливо для формул ранга f≤n-1, докажем что оно справедливо и для формул ранга n

Любая такая формула имеет один из следующих видов: 1); 2) F1F2; 3) F1F2, где F,F1,F2 – булевы формулы ранга n-1

Тогда, используя общий принцип двойственности:

1) y=Ф(y); Ф*(y) ≡y; (или (F)*≡F*)

y=F; (Ф(F))*Ф*(F*)F*, где F ранга ≤n-1, поэтому для неё теорема справедлива

2) Ф(y1,y2)=y1y2; Ф*y1y2

Ф*(F1,F2)=F1*F2* (или (F1F2)*≡F1*F2*)

3) Аналогично.

Пр: f(x,y,z)=x(yz), тогда по определению f*(x,y,z)≡(везде = поставить) x(yz)