Применение нормальных форм

5.18. Найдите наипростейшую формулу от трех переменных среди равносильных формул от трех переменных, последний столбец истинности которых имеет следующий вид:

а) 00001111;

б) 01010101;

в) 00100100;

г) 01011110;

д) 11000100;

Решение: а) Для нахождения формулы можно воспользоваться как СДНФ, так и СКНФ. Используем, например, СКНФ. Выделяем те наборы значений переменных, для которых формула обращается в 0.

F(0,0,0)=F(0,0,1)=F(0,1,0)=F(0,1,1)=0.

Выписываем СКНФ, удовлетворяющую этим условиям, и затем упрощаем ее с помощью равносильных преобразований:

F(X,Y,Z)º(XÚYÚZ)Ù(XÚYÚùZ)Ù(XÚùYÚZ)Ù(XÚùYÚùZ)º(XÚYÚ(ZÙùZ))Ù(XÚùYÚ(ZÙùZ))º(XÚYÚ0)Ù(XÚùYÚ0)º(XÚY)Ù(XÚùY)ºXÚ(YÙùY)ºXÚ0ºX.

5.19. Найдите наипростейшую из равносильных формул от трех переменных, которая принимает значение 1 тогда и только тогда, когда точно две ее переменные принимают значение 1.

5.20. Найдите такую формулу от трех переменных, которая всегда принимает то же значение, что и ее второй аргумент.

5.21. Найдите формулу от трех переменных, которая принимает такое же значение, как и большинство ее аргументов.

5.22. Найдите такую формулу от трех переменных, которая принимает значение 1 тогда и только тогда, когда точно две ее переменные принимают значение 0.

5.23. Найдите формулу F(X,Y) от двух переменных, такую, что бы следующая формула была тождественно истинной.

а) ((FÙY)®ùX)®((X®ùY)®F);

б) ((FÙY)®ùX)®((X®Y)®F).

Указание. Придавая всевозможные значения переменным данной формулы, выясните сначала, какие значения должна принимать искомая формула F(X,Y) на каждом из четырех возможных значений ее переменных. Затем напишите саму формулу F(X,Y), используя СДНФ или СКНФ.