Главная | Случайная
Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






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




 

Пример 3.

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

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

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

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

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

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

Решение.

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

Высказывания Виновен Браун Виновен Джон Виновен Смит
Браун Да Нет  
Джон Нет   Да
Смит Да   Нет
       

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

.

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

№ п/п Б Д С U

 

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

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

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

Пример 4.

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

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

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

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

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

Решение.

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

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

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

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

Ответ: В 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. Постройте комбинационную схему, реализующую логическую функцию .

 

 




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

vikidalka.ru - 2015-2019 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных