Представление булевой функции формулой логики высказываний
Решение.
Поскольку n=2, различных булевых функций от двух переменных существует ровно 16 (табл. 19).
Таблица 19
|
№ функции |
Значение функции |
Формула, соответствующая функции |
|
1. 1 |
f=0000 |
f=0 |
|
2. 2 |
f=0001 |
f=x1Щx2 |
|
3. 3 |
f=0010 |
f= |
|
4. 4 |
f=0011 |
f=x1 |
|
5. 5 |
f=0100 |
f= |
|
6. 6 |
f=0101 |
f=x2 |
|
7. 7 |
f=0110 |
f=x1Еx2 |
|
8. 8 |
f=0111 |
f=x1Ъx2 |
|
9. 9 |
f=1000 |
f= |
|
10. 10 |
f=1001 |
f= |
|
11. 11 |
f=1010 |
f= |
|
12. 12 |
f=1011 |
f= |
|
13. 13 |
f=1100 |
f= |
|
14. 14 |
f=1101 |
f=x1®x2 |
|
15. 15 |
f=1110 |
f= |
|
16. 16 |
f=1111 |
f=1 |
Теорема. Пусть f(x1, x2, …, xk) k-местная булева функция. Если f не равна тождественно нулю, то существует такая формула F, зависящая от списка переменных x1, x2, …, xn и находящаяся в СДНФ относительно этого списка, что F выражает собой функцию f. Формула F определена однозначно с точностью до перестановки дизъюнктивных членов.
предыдущаяследующая