Решение логических задач

В ряде задач приводится несколько высказываний относительно некоторого события, и имеются некоторые сведения об их ложности или истинности. Требуется определить какое из событий имело место. Такие задачи называются логическими.

Алгоритм:

1. Вводятся обозначения для элементарных высказываний.

2. Записывают имеющиеся высказывания в виде формул логики высказываний со значениями равными 1 (при необходимости прибегаем к отрицанию).

3. Записываем конъюнкцию полученных формул и приравниваем её 1. (Характеристическое уравнение).

4. Приводим левую часть уравнения к ДНФ (СДНФ).

5. Каждый конъюнктивный член (независимо от других) приравниваем 1.

6. Решаем получившиеся уравнения. Каждое из решений характеристического уравнения является решением задачи.

Замечание. Можно строить формулы со значениями, равными 0. Тогда характеристическое уравнение получается как дизъюнкция этих формул, равная 0. Затем приводим к КНФ.

Задача:

В конкурсе участвовало 4 девушки: Оля, Нина, Марина и Тамара.

На вопрос о том, как распределились между ними места, были получено три ответа:

Оля ─ 1 , Нина ─2 ,

Оля ─ 2 , Тамара ─ 3,

Марина ─ 2, Тамара ─ 4.

Известно, что хотя бы одно высказывание в каждом ответе истинно. Как распределились места?

Решение:

Введем обозначения:

ОН; ОТ; МТ.

Тогда КНФ: (ОН) (ОТ) (МТ) 1, т.к. Каждое из элементарных сумм истинно.

Преобразуем в ДНФ, раскрывая скобки:

(ОН) (ОМОТТМТТ)

(т.к. О₂ М ₂ = 0 и Т₃Т₄ = 0) (ОН) (ОТТМ) (раскрываем скобки)

ООТОТМНОТНТМ

ОТМ.

Получили ОТМ1.

Следовательно: Оля ─ 1,Марина ─ 2, Тамара ─ 3, Нина ─ 4.