Учебный материал
По теме
Пример. Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 00101110.
Решение.
Строим таблицу значений функции (табл.):
Таблица
|
№ |
x1 |
x2 |
x3 |
f(x1, x2, x3) |
|
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
|
2 |
0 |
1 |
0 |
1 |
|
3 |
0 |
1 |
1 |
0 |
|
4 |
1 |
0 |
0 |
1 |
|
5 |
1 |
0 |
1 |
1 |
|
6 |
1 |
1 |
0 |
1 |
|
7 |
1 |
1 |
1 |
0 |
Алгоритм построения СКНФ и СКНФ см. на странице правила построения СДНФ и СКНФ по таблице истинности
СКНФ (0): № 0, 1, 3, 7
$f(x_1,x_2,x_3)=(x_1 \vee x_2 \vee x_3) (x_1 \vee x_2 \vee\bar{x_3}) (x_1 \vee\bar{x_2} \vee\bar{x_3})(\bar{x_1} \vee\bar{x_2} \vee\bar{x_3})$
СДНФ (1): № 2, 4, 5, 6
$f(x_1,x_2,x_3)= \bar{x_1} x_2 \bar{x_3} \vee x_1 \bar{x_2} \bar{x_3} \vee x_1 \bar{x_2} x_3 \vee x_1 x_2 \bar{x_3}$
- Теорема. Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно нулю, то существует такая формула F, зависящая от списка переменных x1, x2, …, xn и находящаяся в СДНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки дизъюнктивных членов.
- Теорема . Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно единице, то существует такая формула F, зависящая от списка переменных x1, x2, …, xk и находящаяся в СКНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки конъюнктивных членов.