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

Можно выделить следующую последовательность шагов в решении логических задач.

1. Выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами.

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

3. Составить единое логическое выражение для требований задачи.

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

5. Выбрать решение – набор значений простых высказываний, при котором построенное логическое выражение является истинным.

6. Проверить, удовлетворяет ли полученное решение условию задачи.

Пример:

Задача 1: «Пытаясь вспомнить победителей прошлогоднего турнира, пять бывших зрителей турнира заявили, что:

1. Антон был вторым, а Борис – пятым.

2. Виктор был вторым, а Денис – третьим.

3. Григорий был первым, а Борис – третьим.

4. Антон был третьим, а Евгений – шестым.

5. Виктор был третьим, а Евгений – четвертым.

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

Решение:

1) Обозначим через первую букву в имени участника турнира, а – номер места, которое он имеет, т.е. имеем .

2) 1. ; 3. ; 5. .

2. ; 4. .

3) Единое логическое выражение для всех требований задачи: .

4) В формуле L проведем равносильные преобразования, получим: .

5) Из пункта 4 следует: , , , , .

6) Распределение мест в турнире: Антон был третьим, Борис – пятым, Виктор – вторым, Григорий – первым, а Евгений – четвертым.

Задача 2: «По обвинению в ограблении перед судом предстали Иванов, Петров, Сидоров. Следствием установлено:

1. если Иванов не виновен или Петров виновен, то Сидоров виновен;

2. если Иванов не виновен, то Сидоров не виновен.

Виновен ли Иванов?»

Решение:

1) Рассмотрим высказывания:

А: «Иванов виновен», В: «Петров виновен», С: «Сидоров виновен».

2) Факты, установленные следствием: , .

3) Единое логическое выражение: . Оно истинно.

. Составим для него таблицу истинности.

А	В	С	L

Решить задачу – значит указать, при каких значениях А полученное сложное высказывание L истинно. Если , а , то у следствия не достаточно фактов для того, чтобы обвинить Иванова в преступлении. Анализ таблицы показывает и , т.е. Иванов в ограблении виновен.

Вопросы и задания.

1. Составить РКС для формул:

а)

б)

в)

г)

д)

2. Упростить РКС:

а)

б)

в)

3. По данной переключательной схеме построить соответствующую ей логическую формулу.

а)

б)

в)

г)

4. Проверить равносильность РКС:

а)

и

б)

и

в)

и

г)

и

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

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

x	y	z	F

7. Проанализируйте схему, приведенную на рисунке, и выпишите формулу для функции F.

8. Задача: «Однажды следователю пришлось одновременно допрашивать трех свидетелей: Клода, Жака, Дика. Их показания противоречили друг другу, и каждый из них обвинял кого-нибудь во лжи.

1) Клод утверждал, что Жак лжет.

2) Жак обвинял во лжи Дика.

3) Дик уговаривал следователя не верить ни Клоду, ни Жаку.

Но следователь быстро вывел их на чистую воду, не задав им ни одного вопроса. Кто из свидетелей говорил правду?

9. Определить, кто из четырех студентов сдал экзамен, если известно, что:

1) Если первый сдал, то и второй сдал.

2) Если второй сдал, то третий сдал или первый не сдал.

3) Если четвертый не сдал, то первый сдал, а третий не сдал.

4) Если четвертый сдал, то и первый сдал.

10. На вопрос, кто из трех студентов изучал логику, был получен ответ: если изучал первый, то изучал и третий, но не верно, что если изучал второй, то изучал и третий. Кто изучил логику?

Дата добавления: 2014-01-07