Полнота и замкнутость |
Теорема Поста о полноте систем булевых функций |
Теорема поста о полноте. Пример
Теорема
Из полной системы булевых функций M можно выделить полную подсистему, содержащую не более четырех функций.
Доказательство |
9M = f0; f1; fS; fM ; fL полна. |
fS |
= S; |
fM |
= M |
f0 |
2= T0; f1 |
2= T1 |
> |
f |
g |
|
2 |
|
|
2 |
f |
= L |
|
|
= |
|
|
f L=2T |
0 ) |
f (0; : : : ;>0) = 1 |
|
|
0 2 |
0 |
|
; |
|
) число функций системы можно сократить до |
f0(1; : : : ; 1) = 1 ) f0 2= S |
четырех: f0 = fS |
|
|
|
f0(1; : : : ; 1) = 0
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
49 / 50 |
Полнота и замкнутость |
Теорема Поста о полноте систем булевых функций |
Теорема поста о полноте. Пример
Теорема
Из полной системы булевых функций M можно выделить полную подсистему, содержащую не более четырех функций.
Доказательство |
9M = f0; f1; fS; fM ; fL полна. |
fS |
= S; |
fM |
= M |
f0 |
2= T0; f1 |
2= T1 |
> |
f |
g |
|
2 |
|
|
2 |
f |
= L |
|
|
= |
|
|
f L=2T |
0 ) |
f (0; : : : ;>0) = 1 |
|
|
0 2 |
0 |
|
; |
|
) число функций системы можно сократить до |
f0(1; : : : ; 1) = 1 ) f0 2= S |
четырех: f0 = fS |
|
|
|
f0(1; : : : ; 1) = 0 ) f0 2= T1 |
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
49 / 50 |
Полнота и замкнутость |
Теорема Поста о полноте систем булевых функций |
Теорема поста о полноте. Пример
Теорема
Из полной системы булевых функций M можно выделить полную подсистему, содержащую не более четырех функций.
Доказательство |
9M = f0; f1; fS; fM ; fL |
|
fS |
= S; |
|
fM |
= M |
полна. |
f0 |
2= T0 |
; f1 |
2= T1 |
> |
f |
g |
|
2 |
|
|
|
2 |
f |
= L |
|
|
|
= |
|
|
f L=2T |
0 ) |
f (0; : : : ;>0) = 1 |
|
|
0 2 |
0 |
|
; |
|
|
f0(1; : : : ; 1) = 1 ) f0 2= S ) число функций системы можно сократить до четырех: f0 = fS
f0(1; : : : ; 1) = 0 ) f0 2= T1 è f0 2= M
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
49 / 50 |
Полнота и замкнутость |
Теорема Поста о полноте систем булевых функций |
Теорема поста о полноте. Пример
Теорема
Из полной системы булевых функций M можно выделить полную подсистему, содержащую не более четырех функций.
Доказательство |
|
9M = f0; f1; fS; fM ; fL полна. |
fS |
= S; |
fM |
= M |
f0 |
2= T0; f1 |
2= T1 |
> |
f |
g |
|
2 |
|
|
2 |
|
f |
= L |
|
|
|
= |
|
|
f L=2T |
0 ) |
f (0; : : : ;>0) = 1 |
|
|
0 2 |
0 |
|
|
; |
|
|
f0(1; : : : ; 1) = 1 |
) f0 2= S ) число функций системы можно сократить до |
четырех: f0 = fS |
) f0 2= T1 è f0 2= M |
) число функций можно сократить |
f0(1; : : : ; 1) = 0 |
äî òðåõ: f0 = f1 è f0 = fM
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
49 / 50 |
Функции k-значной логики
Функции k-значной логики
Функция k-значной логики
Функция f : Ekn ! Ek, ãäå Ek = f0; 1; : : : ; k 1g, называется функцией k- значной логики. Множество всех функций k-значной логики обозначается Pk.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
50 / 50 |
Функции k-значной логики
Функции k-значной логики
Функция k-значной логики
Функция f : Ekn ! Ek, ãäå Ek = f0; 1; : : : ; k 1g, называется функцией k- значной логики. Множество всех функций k-значной логики обозначается Pk.
Число pk (n) всех функций k-значной
логики, зависящих от n переменных, определяется формулой pk(n) = kkn
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
50 / 50 |
Функции k-значной логики
Функции k-значной логики
Функция k-значной логики
Функция f : Ekn ! Ek, ãäå Ek = f0; 1; : : : ; k 1g, называется функцией k- значной логики. Множество всех функций k-значной логики обозначается Pk.
Число pk (n) всех функций k-значной
логики, зависящих от n переменных, определяется формулой pk(n) = kkn
kn
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
50 / 50 |
Функции k-значной логики
Функции k-значной логики
Функция k-значной логики
Функция f : Ekn ! Ek, ãäå Ek = f0; 1; : : : ; k 1g, называется функцией k- значной логики. Множество всех функций k-значной логики обозначается Pk.
Число pk (n) всех функций k-значной
логики, зависящих от n переменных, определяется формулой pk(n) = kkn
kn
x1 x2 f
0 0 0
0 1 1
0 2 2
1 0 1
1 1 1
1 2 2
2 0 0
2 1 2
2 2 0
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
50 / 50 |
