Решение логических задач средствами алгебры логики

Пример 3.

Рассмотрим задачу «Кто есть кто?», вошедшую в большинство учебников по математической логике.

По подозрению в совершенном преступлении задержаны Браун, Джон и Смит. Один из – известный мошенник, другой - малоизвестный чиновник, третий – уважаемый старик. Известно, что старик всегда говорит правду, мошенник всегда лжет, а чиновник – в одном случае лжет, в другом – говорит правду. Их высказывания:

Браун: «Я совершил преступление, Джон не виновен».

Джон: «Преступник – Смит, Браун не виновен».

Смит: «Я не виновен, виновен Браун».

Определите имя старика, чиновника и мошенника, и кто из них виновен в преступлении, если известно, что преступник только один.

Решение.

Обозначим буквами Б, Д, С, соответственно, высказывания: «виновен Браун», «виновен Джон», «виновен Смит». Тогда их утверждениям соответствуют формулы , , . Запишем в виде таблицы смысловое значение этих формул

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

.

Составим для этой формулы таблицу истинности:

№ п/п	Б	Д	С							U

Из таблицы видно, что формула истинна только в пяти случаях, причем только в четырех из них, истинна только одна конъюнкция, это строки с номерами 2, 4, 6, 7. Так как преступник только один, столбцы Б, Д, С должны содержать только одну единицу и два нуля. В строках 4, 6, 7 оказывается по два истинных высказывания. Следовательно, остается только один случай, описанный строкой 2. Таким образом, нашли преступника – это Смит.

Так как преступник Смит – Джон говорил правду, а значит, старика зовут Джон. Оба высказывания Смита «Я не виновен» и «виновен Браун» ложны, так как мы уже знаем, что виновен он. Следовательно, Смит дважды лжет, и он - мошенник по условию задачи. Высказывания Брауна: «Я совершил преступление» - ложно, «Джон не виновен» - истинно. Следовательно, Браун – чиновник.

Ответ: Джон – старик, Смит – мошенник (он же преступник), Браун – чиновник.

Пример 4.

Алекс, Боб, Джек и Сэм учатся в разных группах. Вот что они говорят:

Алекс: "Я студент 3-ей группы, Сэм – 1-ой".

Боб: "Я студент 3-ей группы, Алекс – 2-ой".

Сэм: "Я студент 2-ой группы, Боб – 4-ой".

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

Решение.

Обозначим А_К, Б_К, Д_К, С_К высказывания "Алекс студент К-ой группы", "Боб студент К-ой группы", "Джек студент К-ой группы", "Сэм студент К-ой группы".

Рассмотрим высказывание Алекса, и предположим, что А₃=1, тогда С₁=0. Тогда в высказывании Боба А₂=0 (так как истина – "Алекс учится в 3-ей группе") и Б₃=1, а в высказывании Сэма Б₄=0 (так как истина – "Боб учится в 3-ей группе") и С₂=1.

Получили истинность высказываний: С₂, А₃, Б₃. Этого не может быть, по условию задачи они студенты разных групп, а мы получили, что Алекс и Боб учатся в 3-ей группе.

Пусть в высказывании Алекса А₃=0, и С₁=1. Тогда в высказывании Сэма С₂=0 и Б₄=1, а в высказывании Боба А₂=1, а Б₃=0. В этом случае истинны высказывания: С₁, А₂, Б₄.

Ответ: В 1-ой группе учится Сэм, во 2-ой – Алекс, в 3-ей – Джек, в 4-ой – Боб.

Задание 3. (для самостоятельной работы)

1) Кто из студентов А, В, С изучал информатику, если высказывание "Если изучал А, то и В изучал тоже" истинно, а "Если изучал С, то изучал и В" – ложно.

2) Определите, кто из трех студентов сдал экзамен, если известно:

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

2."Если сдал второй, то и третий сдал".

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

Указание. Решение постройте на основе таблицы истинности.

3) На экзамене пять студентов набрали 30, 35, 40, 45, 50 баллов. На вопрос: "Какой у вас балл" они ответили следующее:

Ален: "У меня - 30, у Джона – 40".

Боб: "У меня - 30, у Петра – 35".

Петр: "У меня - 30, у Джона – 45".

Джон: "У меня - 40, у Майкла – 50".

Майкл: "У меня - 50, у Алена – 45".

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

4) Четырех друзей пригласили на праздник. Известно:

1. Если пришел первый, то и второй тоже.

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

3. Если пришел четвертый, то и первый тоже.

4. Если четвертый не пришел, то первый пришел, а третий – нет.

Определите, кто из них присутствовал на празднике.

Указание. Решение постройте на основе таблицы истинности.

5) После сдачи экзамена студенты придумали игру. Каждый из них информировал о результатах экзамена так, что одно из утверждений было ложно, а другое истинно.

1. "А набрал 90 баллов, а В - 60".

2. "А набрал 80 баллов, а F - 50".

3. "C набрал 80 баллов, а F - 70".

4. "С набрал 90 баллов, а D – 80".

5. "Е набрал 100 баллов, а B - 80".

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

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

1. Постройте участки комбинационных схем, соответствующие дизъюнкции, конъюнкции, импликации и эквиваленции.

2. Какие равносильности алгебры логики позволяют упростить комбинационные схемы?

3. Оптимизируйте аналитически заданную функцию

4. Постройте комбинационную схему, реализующую логическую функцию .

Не нашли, что искали? Воспользуйтесь поиском: