Теоретический материал
Теорема
1.Любую функцию
можно
представить в виде СДНФ.
Простые
конъюнкции составляются для тех наборов
(x1, …,xn),
гдеf = 1;
еслиxi = 0,
берем
,
еслиxi = 1,
беремxi.
Составляя дизъюнкцию простых конъюнкций, получаем СДНФ.
Теорема 2.Любую функцию
можно
представить в виде СКНФ. Простые
дизъюнкции составляются для тех наборов
(x1,…,xn),
гдеf = 0;
еслиxi = 1,
берем
,
еслиxi = 0,
беремxi.
Конъюнкция простых дизъюнкций дает СКНФ.
Теорема 3 (Поста). Для того чтобы некоторый набор функций был полным, необходимо и достаточно, чтобы в него входили функции, не принадлежащие каждому из классовT0,T,L,M,S:
T0 – класс функций, сохраняющих 0;
T – класс функций, сохраняющих 1;
L – класс линейных функций;
M – класс монотонных функций;
S – класс самодвойственных функций.
Классы функций
T0 :f(0,0,…,0) = 0;
T1 : f(1,1,…,1) = 1;
L : f(x1,…, xn) = a0 + a1x1 +…+ anxn;
S :
f(x1,…,
xn)
= f*(
x1,…,
xn)
=
;
M :
f(1)
f(2)
при 1 <
2
(1 = (x1,…,
xn);
2 = (x1,…,
xn);
).
Логические функции двух переменныхf(x1,x2)
|
№ |
fj(x1,x2) |
f0 |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 | |
|
x1 x2 | ||||||||||
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
2 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
3 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
Обозначения |
0 |
x1x2 |
(x1x2) |
x1 |
(x2x1) |
x2 |
(x1+x2) |
(x1x2) | ||
п/п
|
№ |
fj(x1,x2) |
f8 |
f9 |
f10 |
f11 |
f12 |
f13 |
f14 |
f15 | |
|
x1 x2 | ||||||||||
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
2 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
3 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
Обозначения |
(x1x2) |
(x1x2) |
|
(x2x1) |
|
(x1x2) |
(x1x2) |
1 | ||
п/п
|
№ п/п |
Свойства логических функций | |
|
1 |
|
x + x = 0 |
|
2 |
|
|
|
3 |
|
x + y = y + x |
|
4 |
x (y z) = (x y) z |
x + (y + z) = (x + y) + z |
|
5 |
x (y z) = (x y) z |
x (y + z) = x y + x z |
|
6 |
x y = y x; x y = y x |
x y = y x |
|
7 |
x (y z) = x y x z |
x y = y x |
|
8 |
x (y z) = (x y)(x z) |
x y = y x |
|
9 |
|
(x y) z = x (y z) |
|
10 |
x xy = x |
x x = 1 |
|
11 |
|
x x
= x
x =
|
|
12 |
|
|
|
13 |
|
|
|
|
|
|
|
|
|
|
|
№ п/п |
Полиномы Жегалкина | |
|
1 |
| |
|
2 |
| |
|
3 |
| |
|
4 |
| |
|
5 |
| |
|
6 |
| |
