1_Algebra_logiki
.pdf
Полнота и замкнутость Теорема 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 ) система N полна.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
30 / 50 |
Полнота и замкнутость |
Теорема I о полноте |
Теорема I о полноте систем булевых функций
Пример
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
31 / 50 |
Полнота и замкнутость |
Теорема I о полноте |
Теорема I о полноте систем булевых функций
Пример
Пример
M = f_; ^; xg è N = f_; xg
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
31 / 50 |
Полнота и замкнутость |
Теорема I о полноте |
Теорема I о полноте систем булевых функций
Пример
Пример
M = f_; ^; xg è N = f_; xg
x ^ y = x _ y.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
31 / 50 |
Полнота и замкнутость |
Теорема I о полноте |
Теорема I о полноте систем булевых функций
Пример
Пример
M = f_; ^; xg è N = f_; xg
x ^ y = x _ y.
Пример
M = f_; ^; xg è N = f^; xg
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
31 / 50 |
Полнота и замкнутость |
Теорема I о полноте |
Теорема I о полноте систем булевых функций
Пример
Пример
M = f_; ^; xg è N = f_; xg
x ^ y = x _ y.
Пример
M = f_; ^; xg è N = f^; xg
x _ y = x ^ y.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
31 / 50 |
Полнота и замкнутость |
Теорема I о полноте |
Теорема I о полноте систем булевых функций
Пример
Пример |
|
|
|
|
Пример |
|
|
|
M = f_; ^; xg è |
M = f_; ^; xg è |
|||||||
N = f_; xg |
N = f"g (x " y = |
x ^ y |
) |
|||||
|
|
|
|
|
|
|
|
|
x ^ y = x _ y. |
|
|
|
|||||
Пример |
|
|
|
|
|
|
|
|
M = f_; ^; xg è |
|
|
|
|||||
N = f^; xg |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
x _ y = x ^ y. |
|
|
|
|||||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
31 / 50 |
Полнота и замкнутость |
Теорема I о полноте |
Теорема I о полноте систем булевых функций
Пример
Пример |
|
|
|
|
Пример |
|
|
|
|
|
M = f_; ^; xg è |
M = f_; ^; xg è |
|||||||||
N = f_; xg |
N = f"g (x " y = |
x ^ y |
) |
|||||||
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
x ^ y = x " y |
||||
x ^ y = x _ y. |
||||||||||
Пример |
|
|
|
|
|
|
|
|
|
|
M = f_; ^; xg è |
|
|
|
|
|
|||||
N = f^; xg |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
x _ y = x ^ y. |
|
|
|
|
|
|||||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
31 / 50 |
Полнота и замкнутость |
Теорема I о полноте |
Теорема I о полноте систем булевых функций
Пример
Пример |
|
|
|
|
Пример |
|
|
|
|
|
M = f_; ^; xg è |
M = f_; ^; xg è |
|||||||||
N = f_; xg |
N = f"g (x " y = |
x ^ y |
) |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x ^ y = x " y |
||||
x ^ y = x _ y. |
||||||||||
Пример |
|
|
|
|
|
|
|
|
|
|
M = f_; ^; xg è |
|
|
|
|
|
|||||
N = f^; xg |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
x _ y = x ^ y. |
|
|
|
|
|
|||||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
31 / 50 |
Полнота и замкнутость |
Теорема I о полноте |
Теорема I о полноте систем булевых функций
Пример
Пример |
|
|
|
|
Пример |
|
|
|
|
|
|||
M = f_; ^; xg è |
M = f_; ^; xg è |
||||||||||||
N = f_; xg |
N = f"g (x " y = |
x ^ y |
) |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x ^ y = x " y |
|||||||
x ^ y = x _ y. |
|||||||||||||
|
|
|
|
|
|
|
|
|
|||||
Пример |
|
|
|
|
x = x ^ x = x " x |
||||||||
M = f_; ^; xg è |
|
|
|
|
|
|
|
|
|||||
N = f^; xg |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x _ y = x ^ y. |
|
|
|
|
|
|
|
|
|||||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
31 / 50 |