Примеры решения задач. Пример 1. По таблице истинности (табл

Пример 1. По таблице истинности (табл. 8) найдите формулы, определяющие функции и и придайте им более простой вид (табл. 8):

Таблица 8

Решение. 1. Используя правило получения формулы алгебры логики из таблицы истинности для функции , получим

Таким образом, искомой формулой, определяющей функцию , можно считать .

2. Используя правило получения формулы алгебры логики из таблицы истинности для функции , получим

Таким образом, искомой формулой, определяющей функцию , можно считать .

Пример 2. Используя СДНФ, найдите формулу, принимающую значение 1 на следующих наборах значений переменных, и только на них:

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

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

Решение. 1. Первому условию удовлетворяет лишь конъюнктивный одночлен , второму – , третьему – . Тогда формула F(x, y, z) обращается в 1, тогда и только тогда, когда обращается в 1, или обращается в 1, или обращается в 1. Следовательно, F(x, y, z) – искомая формула.

2. Первому условию удовлетворяет лишь конъюнктивный одночлен , второму – , третьему – . Тогда формула обращается в 1, тогда и только тогда, когда обращается в 1, или обращается в 1, или обращается в 1. Следовательно, F(x,y, z,s) – искомая формула.

Пример 3. Используя СКНФ, найдите формулу, принимающую значение 0 на следующих наборах значений переменных, и только на них:

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

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

Решение. 1. Первому условию удовлетворяет лишь дизъюнктивный одночлен , второму – . Тогда формула F(x, y) обращается в 0, тогда и только тогда, когда обращается в 0,или обращается в 0. Следовательно, F(x, y) – искомая формула.

2. Первому условию удовлетворяет лишь дизъюнктивный одночлен , второму – . Тогда формула F(x, y, z) обращается в 0, тогда и только тогда, когда обращается в 0, или обращается в 0. Следовательно, F(x, y, z) – искомая формула.

Пример 4. Приведите равносильными преобразованиямикаждую из следующих формул к дизъюнктивной нормальной форме.

1. .

2. .

Решение.

Пример 5. Приведите равносильными преобразованиямикаждую из формул задачи 4 к конъюнктивной нормальной форме.

Решение.

Пример 6. Применяя равносильные преобразования, найдите СДНФ для формул из задачи 4.

Решение.

Пример 7. Применяя равносильные преобразования, найдите СКНФ для формул из задачи 4.

Решение.

Пример 8. Для каждой из формул задачи4 с помощью её таблицы истинности найдите СДНФ и СКНФ.

Решение.

а) СДНФ А.

1. Составим таблицу истинности для формулы (табл. 9).

Таблица 9

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

б) СКНФ А.

Выбирая наборы значений переменных, на которых формула обращается в 0, запишем

а затем воспользуемся формулой двойственности

а) СДНФ В.

2. Составим таблицу истинности для формулы (табл. 10).

Таблица 10

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

б) СКНФ В.

Выбирая наборы значений переменных, на которых формула обращается в 0, записываем совершенную конъюнктивную нормальную форму для данной формулы, т.е.

Пример 9. Определить, к какому классу относится данная формула ?

Решение. Приведем формулу к какой-либо нормальной форме:

Полученная ДНФ не является тождественно ложной, так как каждая элементарная конъюнкция не содержит переменную и ее отрицание. Следовательно, исходная формула тождественно истинна или выполнима. Преобразуем данную формулу к КНФ.

Это произведение не является тождественно истинным, так как элементарная сумма не тождественно истина. Таким образом, исходная формула не тождественно ложна и не тождественно истинна, следовательно, она выполнима.

Проверочная работа № 3

Функции алгебры логики. Совершенные нормальные формы алгебры логики. Проблема разрешимости

Ι. По таблицам истинности найдите формулы, определяющие функции и придайте им более простой вид (табл. 11, табл.12):

Таблица 11

Таблица 12

ΙΙ. Используя СДНФ, найдите формулу, принимающую значение 1 на следующих наборах значений переменных, и только на них:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ΙΙΙ. Используя СКНФ, найдите формулу, принимающую значение 0 на следующих наборах значений переменных, и только на них:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ΙV. Приведите равносильными преобразованиямикаждую из следующих формул к дизъюнктивной нормальной форме:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

V. Приведите равносильными преобразованиямикаждую из формул задачи ΙV к конъюнктивной нормальной форме.

VΙ. Применяя равносильные преобразования, найдите СДНФ для

формул из задачи ΙV.

VΙΙ. Применяя равносильные преобразования, найдите СКНФ для

формул из задачи ΙV.

VΙΙΙ. Для каждой из формул задачиΙV с помощью её таблицы истинности

найдите СДНФ и СКНФ.