Примеры решения задач. Пример 1. По таблице истинности (табл
Пример 1. По таблице истинности (табл. 8) найдите формулы, определяющие функции и и придайте им более простой вид (табл. 8):
Решение. 1. Используя правило получения формулы алгебры логики из таблицы истинности для функции , получим
Таким образом, искомой формулой, определяющей функцию ,можно считать .
2. Используя правило получения формулы алгебры логики из таблицы истинности для функции , получим
Таким образом, искомой формулой, определяющей функцию ,можно считать .
Пример 2. Используя СДНФ, найдите формулу, принимающую значение 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(x, y) обращается в 0, тогда и только тогда, когда обращается в 0,или обращается в 0. Следовательно, F(x, y) – искомая формула.
2. Первому условию удовлетворяет лишь дизъюнктивный одночлен , второму – . Тогда формула F(x, y, z) обращается в 0, тогда и только тогда, когда обращается в 0, или обращается в 0. Следовательно, F(x, y, z) – искомая формула.
Пример 4.Приведите равносильными преобразованиямикаждую из следующих формул к дизъюнктивной нормальной форме.
Пример 5.Приведите равносильными преобразованиямикаждую из формул задачи 4 к конъюнктивной нормальной форме.
Пример 6.Применяя равносильные преобразования, найдите СДНФ для формул из задачи 4.
Пример 7.Применяя равносильные преобразования, найдите СКНФ для формул из задачи 4.
Пример 8.Для каждой из формул задачи4 с помощью её таблицы истинности найдите СДНФ и СКНФ.
1. Составим таблицу истинности для формулы (табл. 9).
Теперь, выбирая наборы значений переменных, на которых формула обращается в 1, записываем совершенную дизъюнктивную нормальную форму для данной формулы, т.е. .
Выбирая наборы значений переменных, на которых формула обращается в 0, запишем
а затем воспользуемся формулой двойственности
2. Составим таблицу истинности для формулы (табл. 10).
Теперь, выбирая наборы значений переменных, на которых формула обращается в 1, записываем совершенную дизъюнктивную нормальную форму для данной формулы, т.е.
Выбирая наборы значений переменных, на которых формула обращается в 0, записываем совершенную конъюнктивную нормальную форму для данной формулы, т.е.
Пример 9. Определить, к какому классу относится данная формула ?
Решение. Приведем формулу к какой-либо нормальной форме:
Полученная ДНФ не является тождественно ложной, так как каждая элементарная конъюнкция не содержит переменную и ее отрицание. Следовательно, исходная формула тождественно истинна или выполнима. Преобразуем данную формулу к КНФ.
Это произведение не является тождественно истинным, так как элементарная сумма не тождественно истина. Таким образом, исходная формула не тождественно ложна и не тождественно истинна, следовательно, она выполнима.
Проверочная работа № 3
Функции алгебры логики. Совершенные нормальные формы алгебры логики. Проблема разрешимости
Ι.По таблицам истинности найдите формулы, определяющие функции и придайте им более простой вид (табл. 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
ΙΙΙ.Используя СКНФ, найдите формулу, принимающую значение 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
ΙV.Приведите равносильными преобразованиямикаждую из следующих формул к дизъюнктивной нормальной форме: