1_Algebra_logiki
.pdf
Дискретная математика
Раздел: Алгебра логики
Николаева Екатерина Александровна
Томский государственный университет, кафедра программирования
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
1 / 50 |
Содержание
1Функции алгебры логики
Элементарные булевы функции
Формульное представление булевой функции
Существенные и фиктивные переменные
Тождества алгебры логики
2Нормальные формы
Разложение булевой функции по подмножеству переменных
Cовершенные ДНФ и КНФ
3 Полиномы
4 Двойственная функция
5Полнота и замкнутость
Теорема I о полноте
Замкнутые классы
Теорема Поста о полноте систем булевых функций
6 Функции k-значной логики
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
2 / 50 |
Функции алгебры логики
Функции алгебры логики
Булева функция
Функция f : E2n ! E2, ãäå E2 = f0; 1g, называется функцией алгебры логики или булевой функцией.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
3 / 50 |
Функции алгебры логики
Функции алгебры логики
Булева функция
Функция f : E2n ! E2, ãäå E2 = f0; 1g, называется функцией алгебры логики или булевой функцией.
|
x1 |
x2 . . . |
xn 1 |
xn |
f(x1; : : : ; xn 1; xn) |
|
0 |
0 |
0 |
. . . |
0 |
0 |
f(0; : : : ; 0; 0) |
1 |
0 |
0 |
. . . |
0 |
1 |
f(0; : : : ; 0; 1) |
|
|
|
|
|
|
|
2 |
0 |
0 |
. . . |
1 |
0 |
f(0; : : : ; 1; 0) |
. . . |
. . . . . . . . . |
. . . |
. . . |
. . . |
||
|
|
|
|
|
|
|
2n 2 |
1 |
1 |
. . . |
1 |
0 |
f(1; : : : ; 1; 0) |
2n 1 |
1 |
1 |
. . . |
1 |
1 |
f(1; : : : ; 1; 1) |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
3 / 50 |
Функции алгебры логики
Функции алгебры логики
Булева функция
Функция f : E2n ! E2, ãäå E2 = f0; 1g, называется функцией алгебры логики или булевой функцией.
|
x1 |
x2 . . . |
xn 1 |
xn |
f(x1; : : : ; xn 1; xn) |
|
0 |
0 |
0 |
. . . |
0 |
0 |
f(0; : : : ; 0; 0) |
1 |
0 |
0 |
. . . |
0 |
1 |
f(0; : : : ; 0; 1) |
|
|
|
|
|
|
|
2 |
0 |
0 |
. . . |
1 |
0 |
f(0; : : : ; 1; 0) |
. . . |
. . . . . . . . . |
. . . |
. . . |
. . . |
||
|
|
|
|
|
|
|
2n 2 |
1 |
1 |
. . . |
1 |
0 |
f(1; : : : ; 1; 0) |
2n 1 |
1 |
1 |
. . . |
1 |
1 |
f(1; : : : ; 1; 1) |
f : f0; 1g f0; 1g : : : f0; 1g ! f0; 1g
| |
|
|
{z |
|
} |
|
|
|
|
n |
|
|
|
|
|
|
|
|||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
|
3 / 50 |
|||
Функции алгебры логики
Функции алгебры логики
Булева функция
Функция f : E2n ! E2, ãäå E2 = f0; 1g, называется функцией алгебры логики или булевой функцией.
x1 x2 x3 |
f(x1; x2; x3) |
00 0 0 f0 = 0 = f(0; 0; 0)
10 0 1 f1 = 1 = f(0; 0; 1)
20 1 0 f2 = 1 = f(0; 1; 0)
30 1 1 f3 = 0 = f(0; 1; 1)
41 0 0 f4 = 1 = f(1; 1; 0)
51 0 1 f5 = 0 = f(1; 0; 1)
61 1 0 f6 = 0 = f(1; 1; 0)
71 1 1 f7 = 0 = f(1; 1; 1)
f : f0; 1g f0; 1g : : : f0; 1g ! f0; 1g
| |
|
|
{z |
|
} |
|
|
|
|
n |
|
|
|
|
|
|
|
|||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
|
3 / 50 |
|||
Функции алгебры логики
Функции алгебры логики
Булева функция
Функция f : E2n ! E2, ãäå E2 = f0; 1g, называется функцией алгебры логики или булевой функцией.
|
|
x1 x2 x3 |
|
|
f(x1; x2; x3) |
|
0 |
|
0 0 0 |
|
f0 |
= 0 = f(0; 0; 0) |
P2 Множество всех булевых |
1 |
0 0 1 |
|
f1 |
= 1 = f(0; 0; 1) |
||
|
функций, включая константы 0, 1 |
|||||
20 1 0 f2 = 1 = f(0; 1; 0)
30 1 1 f3 = 0 = f(0; 1; 1)
41 0 0 f4 = 1 = f(1; 1; 0)
51 0 1 f5 = 0 = f(1; 0; 1)
61 1 0 f6 = 0 = f(1; 1; 0)
71 1 1 f7 = 0 = f(1; 1; 1)
f : f0; 1g f0; 1g : : : f0; 1g ! f0; 1g
| |
|
|
{z |
|
} |
|
|
|
|
n |
|
|
|
|
|
|
|
|||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
|
3 / 50 |
|||
Функции алгебры логики
Функции алгебры логики
Булева функция
Функция f : E2n ! E2, ãäå E2 = f0; 1g, называется функцией алгебры логики или булевой функцией.
|
|
x1 x2 x3 |
|
|
f(x1; x2; x3) |
|
0 |
|
0 0 0 |
|
f0 |
= 0 = f(0; 0; 0) |
P2 Множество всех булевых |
1 |
0 0 1 |
|
f1 |
= 1 = f(0; 0; 1) |
||
|
функций, включая константы 0, 1 |
|||||
20 1 0 f2 = 1 = f(0; 1; 0)
3 |
0 1 1 |
f3 |
= 0 = f(0; 1; 1) |
Число p2 (n) всех функций из |
|
4 |
1 0 0 |
f4 |
= 1 = f(1; 1; 0) |
||
P2, зависящих от n переменных, |
|||||
5 |
1 0 1 |
f5 |
= 0 = f(1; 0; 1) |
равно 22n , ò.å. jP2j = 22n |
61 1 0 f6 = 0 = f(1; 1; 0)
71 1 1 f7 = 0 = f(1; 1; 1)
f : f0; 1g f0; 1g : : : f0; 1g ! f0; 1g
| |
|
|
{z |
|
} |
|
|
|
|
n |
|
|
|
|
|
|
|
|||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
|
3 / 50 |
|||
Функции алгебры логики |
Элементарные булевы функции |
Элементарные булевы функции
Элементарные булевы функции одной переменной
x |
0 |
1 |
x |
x |
|
|
|
|
|
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
|
|
|
|
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
4 / 50 |
Функции алгебры логики |
Элементарные булевы функции |
Элементарные булевы функции
Элементарные булевы функции одной переменной
f0 = 0 функция константа 0.
x |
0 |
1 |
x |
x |
|
|
|
|
|
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
|
|
|
|
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
4 / 50 |