Двойственность в алгебре высказываний. Теорема о общем принципе двойственности для булевых формул

Определение 3.17. Пусть f(x1, x2,..., хп) - формула алгебры высказываний. Двойствен¬ной к ней будем называть формулу f*(x1, x2,... ,хп) = .
Утверждение. Справедливы следующие равносильности:
1) (f*)* ≡f, 2) (0)* ≡ 1, 3) (1)* ≡0, 4) (х)* ≡ х, 5) (х)* ≡ х, 6) (х у)* ≡ х V у, 7) (x у)* ≡ x у.
Доказательство каждого из пунктов следуют непосредственно из определения. Напри¬мер,
1) (0*) ≡ ≡ 1; 7) (x у)* = = = x y.
Теорема 3.18. f1(x1, x2,... ,хп) ≡ f2(x1, x2,... ,хп) - равносильные формулы в алгебре высказываний тогда и только тогда, когда f1*(x1, x2,...,хп) ≡ f2*(x1, x2,... хп) - равно¬сильные формулы в алгебре высказываний.
Доказательство. Заметим, что столбец * в таблице истинности формулы f* может быть получен из столбца в таблице истинности формулы f с помощью инвертирования, то есть симметрии относительно середины таблицы по строкам и отрицания:
x1 x2 … xn
*

0 0 … 0 α1

0 0 … 1 α2

. . … . .
. . … . .
1 1 … 0

1 1 … 1

Отсюда сразу следует, что, если совпадают таблицы истинности формул f1 и f2, то совпа¬дают и таблицы истинности формул f1* и f2* . Теорема доказана.
Теорема 3.19. Общий принцип двойственности. Пусть G(x1, x2,... ,xn) = F(f1(x1, x2,... ,xn),f2(x1, x2,... ,xn),... ,fm(x1, x2,... ,xn)) .

Тогда G*(x1 , x2,... ,хп) = F*(f1*(x1, x2,... ,хп), f2*(x1, x2,... ,хп),,..., fm*(x1, x2,... ,хп)), где F*(у1, у2, …, yт) - формула, двойственная к формуле F(y1, y2,... ,ут).
Доказательство. Действительно,
G*(x1, x2 ,... ,xn) = (F(f1(x1,x2,... ,xn), f2(x1,x2,... ,xn),... , fm(x1, x2,...,xn)))* =
=
=
=
Теорема (двойственность для булевых функций)
f(x1,x2,…,xn) – булева функция. Тогда f*(x1,x2,…,xn) получается из f следующим образом 0→1, 1→0, → , → , а структуру и скобки оставлять.
Доказательство по индукции по количеству булевых операций в этой формуле.
Ранг f≤1, 0*≡1, 1*≡0, ( )*≡ , (x)* ≡x
(x y)* ≡x y, (x y)* ≡x y
Предположим, что теорема справедлива для формулы rang f ≤n-1. Докажем ее для формулы rang=n. Любая такая формула имеет один из следующих видов, либо F1 F2, либо , либо , где F, F1, F2 – формулы ранга ≤ 1 будем использовать общий принцип двойственности.
1). Для : =Ф(y), g=F, (Ф(F))*=Ф*(F*)≡
Формула F rang≤n-1, поэтому теорема для нее справедлива
2). Ф(y1,y2) = y1 y2, Ф*= y1 y2, Ф*(F1,F2)=F1* F2*
3). Аналогично.
Пример: Написать двойственную функцию
f(x,y,z)=x( z)
f*(x,y,z)= = =x ( z)
Нормальная форма алгебры высказывания.
Пусть σ E2={0;1} Обозначим

Уравнение х σ = 1 имеет решение х= σ, Рассмотрим уравнение: … =1
Т.к. конъюнкция равна 1 <=> , когда каждый множитель =1 , то это уравнение равносильно системе

( , … )- решение.
Рассмотрим уравнение вида
… =1, ( , … ) ,
Решением этого уравнения будет:
={( , … )}
Лемма (о разложении формулы в алгебре высказываний по переменным)
Пусть f(x1,x2,…,xn) – формула в алгебре высказываний. Тогда f(x1,x2,…,xn)≡ xif(x1,x2,…,xi-1, 1, xi+1, … xn) f(x1,x2,…,xi-1, 0, xi+1, … xn) ≡ f(x1,x2,…,xi-1, , xi+1, … xn). σi E2
Доказательство:
Чтобы доказать равносильность формул, надо доказать их равенство на любом наборе значений истинности (совпадение таблиц истинности) {α=( α1, α2, …, αn)} αk E2. Множество всех наборов значений истинности разобьем на 2 неперекрещивающихся подмножества: 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) – верно

.

Powered by Drupal - Design by artinet