1_Algebra_logiki
.pdf
Двойственная функция
Принцип двойственности
Пример
Пример 1
f = xy _yz _ zx =
f_(f^(x; y); f^(y; z); f^(z; x)) f = (x _ y) (y _ z) (z _ x)
=(xz _ y) (z _ x)
=xy _ yz _ zx
Пример 2
f= (x ! y) (1 ! z)
f= (xy) (0 z) = xy z
Двойственные пары
(x _ y) = x y (x y) = x _ y
(x) = x
(1) = 0; (0) = 1
(a _ b) (a _ c) = a _ bc
(a ! b) = a _ b )
(a ! b) = (a _b) = a b
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
28 / 50 |
Полнота и замкнутость
Полнота систем булевых функций
Определение
Система M = ff1; : : : ; fr; : : : g называется полной, если каждую функцию F 2 P2 можно представить формулой над M.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
29 / 50 |
Полнота и замкнутость
Полнота систем булевых функций
Определение
Система M = ff1; : : : ; fr; : : : g называется полной, если каждую функцию F 2 P2 можно представить формулой над M.
Пример: M = fx1 _ x2; x1 ^ x2; x1g
Для любой (8) булевой функции f(x1; : : : ; xn) справедливо выражение:
_
f(x1; : : : ; xn) = x11 xnn
( 1;:::; n) f( 1;:::; n)=1
Следовательно ()) система M = fx1 _ x2; x1 ^ x2; x1g полна
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
29 / 50 |
Полнота и замкнутость |
Теорема I о полноте |
Теорема I о полноте систем булевых функций
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
30 / 50 |
Полнота и замкнутость Теорема I о полноте
Теорема I о полноте систем булевых функций
Теорема
Пусть система M = ff1; : : : ; fr; : : : g полна и любая ее функция может быть представлена формулой над множеством N = fg1; : : : ; gl; : : : g, тогда система N тоже является полной.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
30 / 50 |
Полнота и замкнутость Теорема I о полноте
Теорема I о полноте систем булевых функций
Теорема
Пусть система M = ff1; : : : ; fr; : : : g полна и любая ее функция может быть представлена формулой над множеством N = fg1; : : : ; gl; : : : g, тогда система N тоже является полной.
Доказательство.
Система M полна ) h = C[f1; : : : ; fr; : : : ], ãäå 8h 2 P2
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
30 / 50 |
Полнота и замкнутость Теорема I о полноте
Теорема I о полноте систем булевых функций
Теорема
Пусть система M = ff1; : : : ; fr; : : : g полна и любая ее функция может быть представлена формулой над множеством N = fg1; : : : ; gl; : : : g, тогда система N тоже является полной.
Доказательство.
Система M полна ) h = C[f1; : : : ; fr; : : : ], ãäå 8h 2 P2) f1 = C1[g1; : : : ; gl; : : : ];
: : :
fr = Cr[g1; : : : ; gl; : : : ]:
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
30 / 50 |
Полнота и замкнутость Теорема I о полноте
Теорема I о полноте систем булевых функций
Теорема
Пусть система M = ff1; : : : ; fr; : : : g полна и любая ее функция может быть представлена формулой над множеством N = fg1; : : : ; gl; : : : g, тогда система N тоже является полной.
Доказательство.
Система M полна ) h = C[f1; : : : ; fr; : : : ], ãäå 8h 2 P2) f1 = C1[g1; : : : ; gl; : : : ];
: : :
fr = Cr[g1; : : : ; gl; : : : ]:
Тогда
h = C C1[g1; : : : ; gl; : : : ]; C2[g1; : : : ; gl; : : : ]; : : : ; Cr[g1; : : : ; gl; : : : ]
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
30 / 50 |
Полнота и замкнутость Теорема I о полноте
Теорема I о полноте систем булевых функций
Теорема
Пусть система M = ff1; : : : ; fr; : : : g полна и любая ее функция может быть представлена формулой над множеством N = fg1; : : : ; gl; : : : g, тогда система N тоже является полной.
Доказательство.
Система M полна ) h = C[f1; : : : ; fr; : : : ], ãäå 8h 2 P2)
f1 = C1[g1; : : : ; gl; : : : ];
: : :
fr = Cr[g1; : : : ; gl; : : : ]:
Тогда
) h = C10[g1 |
; : : : ; gl; : : : ] |
|
|
h = C C [g1 |
; : : : ; gl; : : : ]; C2 |
[g1 |
; : : : ; gl; : : : ]; : : : ; Cr[g1; : : : ; gl; : : : ] |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
30 / 50 |
Полнота и замкнутость Теорема I о полноте
Теорема I о полноте систем булевых функций
Теорема
Пусть система M = ff1; : : : ; fr; : : : g полна и любая ее функция
может быть |
представлена формулой над множеством N = |
|
fg1; : : : ; gl; : : : g, тогда система N тоже является полной. |
|
|
Доказательство. |
|
|
Система M полна ) h = C[f1; : : : ; fr; : : : ], ãäå 8h 2 P2) |
|
|
|
f1 = C1[g1; : : : ; gl; : : : ]; |
|
|
: : : |
|
|
fr = Cr[g1; : : : ; gl; : : : ]: |
|
Тогда |
; : : : ; gl; : : : ] ) любая функция из P2 может быть |
|
) h = C10[g1 |
||
h = C C [g1 |
; : : : ; gl; : : : ]; C2[g1; : : : ; gl; : : : ]; : : : ; Cr[g1; : : : ; gl; : : : ] |
|
представлена формулой над N
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
30 / 50 |