Упражнения. Построение логической формулы по заданной таблице истинности

Построение логической формулы по заданной таблице истинности

По таблице истинности также можно составить сложное высказывание. Одна из его форм называется совершенной дизъюнктивной нормальной формой (СДНФ) или стандартной суммой произведений.

Чтобы понять, как строится стандартная сумма произведений, рассмотрим следующую таблицу.

Таблица 2.3.8

	A	B	C	F

Вторая строка таблицы, в которой функция принимает единичное значение соответствует входной комбинации, А=0, В=0 и С=1. Рассмотрим произведение входной комбинации . Подставляя в него значения 0, 0 и 1 для A, B и С, мы, очевидно, получим логическую 1. Нетрудно убедиться, что для любой из основных семи комбинаций произведение равно логическому 0. Таким образом, произведение можно использовать для описания второй строки таблицы.

Аналогичным образом определяем произведения всех остальных строк с единичным значением функции (третья строка соответствует , шестая строка - ).

Объединяя полученные результаты с помощью логической операции дизъюнкции получим следующую формулу высказывания

Выражение такого типа является совершенной дизъюнктивной нормальной формой.

В общем случае каждая строка таблицы истинности с единичным значением функции может быть описана произведением всех входных переменных. Переменные, имеющие нулевые значения в строке, входят в произведение с отрицанием, а переменные со значением единица - без отрицания. Объединение с помощью операции дизъюнкции (логического отрицания) всех произведений, построенных для строк с единичными значениями функции, дает сумму произведений для заданной таблицы истинности.

Существует и другая форма записи. По таблице истинности можно составить сложное высказывание в совершенной конъюнктивной нормальной форме (СКНФ) или стандартным произведение сумм.

Обратимся снова к таблице 2.3.9. Таблица определяет функцию f. Таблица истинности для инверсной функции, т.е. для функции , получается инверсией значений в последнем столбце. Результат показан в таблице 2.3.9. Пользуясь, рассмотренным выше способом можно записать СДНФ для функции в следующем виде:

Если теперь выполнить отрицание над обеими частями этого равенства и воспользоваться законом де Моргана, то получим

Таблица 2.3.9

	A	B	C

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

В общем случае, чтобы построить СКНФ по таблице истинности, нужно сначала вычислить таблицу истинности для инверсной функции, заменив 1 на 0, а 0 на 1 в столбце значений функций. Затем нужно записать СДНФ для этой инверсной функции. И наконец, взять отрицание полученного выражения, пользуясь законом де Моргана.

Контрольные вопросы:

1. Назовите основные логические операции и приведите их таблицы истинности.

2. Что такое логическое выражение?

3. Каков порядок выполнения операций при вычислении значения логического выражения?

4. Приведите пример сложных логических высказываний, представление их в виде логических выражений и вычисления их значений.

5. Что такое совершенная нормальная дизъюнктивная форма представления логического выражения?

6. Что такое совершенная нормальная конъюнктивная форма представления логического выражения?

7. Какие высказывания называются равносильными? Привести примеры.

8. В чем суть минимизации логического выражения?

9. Назовите основные законы алгебры высказываний.

1. Какие из следующих предложений не являются объектами алгебры высказываний:

1) Войдите!

2) Река Волга длиннее реки Оби.

3) Не курить!

4) Трижды семь больше, чем дважды двенадцать.

5) Пожалуйста, впустите!

6) Число 73 имеет четыре простых делителя.

7) Который час?

Ответ: (1, 3, 5, 7)

2. Одно высказывание “Музыку к балету “Гаянэ” написал А. Хачатурян”. Если в этом высказывании заменить фамилию автора, будет ли новое высказывание объектом алгебры высказываний?

Ответ: (Да)

3. Приведите высказывания, записанные в виде формулы и в виде фразы, которые не являются объектами алгебры высказываний.

4. Даны высказывания “Семь больше девяти” и “Баку - столица Америки”. Составьте из этих высказываний логическое произведение и определите его истинность.

Ответ: “Семь больше девяти и Баку - столица Америки” является сложным высказыванием.

5. Истинное логическое произведение состоит из трех простых высказываний: A, B и С. Известно, что А и В истинны. Может ли высказывание С быть одним из следующих:

1) Дважды три - семь.

2) Слоны живут в Африке и в Индии.

3) 5x + 3 = 11x.

Ответ: Да. Высказывание “Слоны живут в Африке и в Индии”.

6. Дано высказывание: “Сережа закончил тренировку, идет по улице и подбрасывает мяч”. Выделите простые высказывания, обозначьте их буквой и запишите составное высказывание в виде формулы.

x = ABC, где:

А - Сережа закончил тренировку,

В - Сережа идет по улице,

С - Сережа подбрасывает мяч.

7. Какие два из следующих высказываний, соединенных союзом ИЛИ образуют ложную логическую сумму:

1) Утки зимуют на юге.

2) Трижды три - семь.

3) “Горе от ума” написал А. С. Грибоедов.

4) Три делитель числа 56?

Ответ: (Высказывания 2 и 4, т.к. они оба ложны).

8. Выделите высказывания, не являющиеся логической суммой:

1) Корнем квадратного уравнения является число а или число b.

2) Перед нами портрет Матвеева или Соколова.

3) Семь - делитель числа а и числа b.

4) Председателем палаты изберут Иванова или Петрова.

Ответ: Высказывания 2 и 4, т.к. союз ИЛИ употребляется в них в разделительном смысле.

9. Даны высказывания “ 3 < 11 ” и ” 3 < 7 < 15 ”. Какое из них является логическим произведением?

Ответ: (3 < 7 < 15).

10. Даны высказывания:

А – Петр работает в институте;

В - Петр читает лекции;

С – Петр ведет практические занятия.

Составить формулы следующих сложных высказываний:

1) Неверно, что Петр работает в институте и неверно, что он читает лекции.

2) Неверно, что Петр, работая в институте, читает лекции или ведет практические занятия.

3) Петр не работает в институте, но при этом читает лекции или не ведет практических занятий.

4) Петр не работает в институте, не ведет практические занятия - он только читает лекции.

Ответ:

11. Запишите в виде формулы фразу “Если Алексей примет правильное решение, то Владимир тоже примет правильное решение; если же Алексей не примет правильного решения, то об успехе Владимира ничего определенного сказать нельзя, - он может принять правильное решение, а может не принять”.

Ответ: Фраза, формулу которой требуется составить, говорит о трех возможных событиях:

Формула имеет вид:

12. Запишите в виде формулы фразу: “Если Ваня и Алеша проголосуют “за”, то Сережа поступит так же. В случае противоположного мнения у Вани и Алеши - о мнении Сережи ничего определенного сказать нельзя”.

Ответ:

13. Среди следующих высказываний выберите тождественно ложное:

Ответ: Тождественно ложным является высказывание

14. Среди следующих высказываний выберите тождественно истинное:

)

Ответ: Тождественно истинным является высказывание

15. Данные высказывания запишите, используя только операции дизъюнкции и отрицания:

_{; ;}

Ответ: .

16. Данные высказывания запишите, используя только операции конъюнкции и отрицания:

_;

Ответ: .

17. Какие высказывания в каждом из двух наборов равносильны:

1. ; ; ;

2.

Ответ: Равносильны высказывания а) x₁ и x₂; б) x₁ и x₃.

18. Даны высказывания:

а) “Сейчас идет дождь, а гром не гремит”

б) “Сейчас не идет дождь или сейчас гремит гром”

Как изменить второе высказывание, чтобы оно оказалось равносильно первому?

Ответ: .

19. Используя законы де Моргана, преобразуйте формулы данных высказываний так, чтобы отрицание не распространялось на сложные высказывания:

а) б) в)

г) д) е)

ж) з)

Ответ: а) з)

20. Какая из следующих формул записана в СДНФ:

Ответ: x₃.

21. Какие из следующих формул не написаны в СКНФ:

; ;

Ответ: x₁ , x₃ .

22. Из простых высказываний:

А - Виктор хороший пловец;

В - Виктор хорошо ныряет;

С - Виктор хорошо поет,

составлена фраза, формула которой имеет вид:

.

Установить, равносильно ли высказывание x высказыванию D - Виктор хороший пловец, и он хорошо поет.

23. Данные высказывания записать в СДНФ:

Ответ:

24. Найти минимальные формы высказываний:

Ответ:

25. Записать в СДНФ и в СКНФ форму сложного высказывания, заданного таблично:

A B C
F

Ответ: СДНФ:

СКНФ:

Дата добавления: 2014-10-17