Представление булевой функции формулой логики высказываний
Теорема 2. Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно единице, то существует такая формула F, зависящая от списка переменных x1, x2, …, xk и находящаяся в СКНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки конъюнктивных членов.
Поскольку каждая булева функция представима в виде формулы логики высказываний, то принцип построения СДНФ и СКНФ сохраняется такой же как и для формул логики высказываний.
Пример 34.
Построить СКНФ и СДНФ булевой функции f(x1, x2, x3)= 00101110.
Решение.
Строим таблицу значений функции (табл. 20):
Таблица 20
|
№ |
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
СДНФ (1): № 2, 4, 5, 6
