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

Задача 1. При составлении расписания на понедельник преподаватели просили, чтобы уроки проходили в следующем порядке:

  • а) математика — первым или третьим уроком;
  • б) история — первым или вторым;
  • в) литература — вторым или третьим.

Можно ли удовлетворить просьбы всех трех преподавателей и каким образом, если это возможно?

Введем следующие элементарные высказывания:

  • А — математика — I урок;
  • В — математика — III урок;
  • С — история — II урок;
  • D — история — I урок;
  • Е — литература — II урок;
  • F — литература — III урок.

Просьбы всех преподавателей выражены высказываниями:

Высказывание, удовлетворяющее просьбы всех трех преподавателей, есть конъюнкция St, S2, S3, т.е. S = Sj & S2 & S3, и оно должно быть истинным, т.е. 5=1. Применим дистрибутивный закон в преобразованиях 5:

В данном случае конъюнкция Л & D = 0, так как первым уроком математика и история одновременно быть не могут.

Очевидно, А & С & Е = 0, так как С & Е = 0 — второй урок не может быть одновременно уроком истории и литературы. Аналогично В & С & Е = 0; В & С & F = 0; В & D & F = 0, т.е.

Дизъюнкция истинна, если одно из слагаемых истинно:

Конъюнкция высказываний истинна, если истинны все входящие в нее сомножители. В результате получаем два возможных варианта ответа:

а) В & D & Е = 1, т.е. история — I урок;

литература — II урок;

математика — III урок;

б) Л & С & F = 1, т.е. математика — I урок;

история — II урок;

литература — III урок.

Задача 2. Мама, прибежавшая на звон разбившейся вазы, застала всех трех своих сыновей в совершенно невинных позах: Саша, Ваня и Коля делали вид, что происшедшее к ним не относится. Однако футбольный мяч среди осколков явно говорил об обратном.

  • — Кто это сделал? — спросила мама.
  • — Коля не бил по мячу, — сказал Саша. — Это сделал Ваня.
  • — Разбил Коля, Саша не играл в футбол дома, — ответил Ваня.
  • - Так я и знала, что вы друг на дружку сваливать будете, — рассердилась мама. — Ну, а ты что скажешь? — спросила она Колю.
  • - Не сердись, мамочка! Я знаю, что Ваня не мог этого сделать. А я сегодня еще не сделал уроки, — сказал Коля.

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

Решение. Введем простые высказывания:

  • • С — вазу разбил Саша;
  • • В — вазу разбил Ваня;
  • • К — вазу разбил Коля.

Запишем с помощью этих обозначений утверждения мальчиков.

  • • Саша. 1.-К. 2. В.
  • • Ваня. 1. К. 2. -’С.
  • • Коля. 1. ^В.

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

Как записать «Саша два раза солгал»? В этом случае оба его утверждения неверны, поэтому -?К = 0 и В = 0, что равносильно К & “*В = 1.

«Саша два раза сказал правду»? В этом случае оба его утверждения неверны, поэтому ^К = 1 и В = 1, что равносильно -,К & В = 1.

Если Коля солгал, а Саша и Ваня сказали правду, то ^К & В = 1 и К & -С - 1 и В = 1.

Заменив «и» на умножение, получаем -’К & В & К & “•С & В = 1, учитывая, что К & -•К = 0, получаем в левой части равенства ноль; так как в правой части — единица, этого не может быть (равенство ложно при любых значениях К, С, В).

Если Ваня солгал, а Саша и Коля сказали правду, то -^К & В = 1 и ^К & С = 1 и ^В = 1, заменив «и» на умножение, получаем -"К & В & -'К & С & ^В = 1, учитывая, что В & ^В = 0, получаем, что это равенство ложно при любых значениях К, С, В (этого не может быть).

Остается последний возможный вариант. Если Саша оба раза солгал, а Ваня и Коля сказали правду, то К & ^В = 1

и К & -?С = 1 и “•В = 1, заменив «и» на умножение, получаем К & -’В & К & -•С & -?В = 1, упростив это выражение с учетом равенств К & К = К и -?В & ^В = -’В, получим К & -?В & = 1, т.е. при этом предположении вазу разбил Коля,

а не Ваня и не Саша. Таким образом, вазу разбил Коля.

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

  • 1) Антон был вторым, а Борис пятым;
  • 2) Виктор был вторым, а Денис третьим;
  • 3) Григорий был первым, а Борис третьим;
  • 4) Антон был третьим, а Евгений шестым;
  • 5) Виктор был третьим, а Евгений четвертым.

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

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

Решение. Обозначим высказывания зрителей символом Ху, где X — первая буква имени участника турнира, а у — номер места, которое он занял в турнире. Так как в паре высказываний каждого зрителя одно истинно, а второе ложно, то будут истинными дизъюнкции этих высказываний: А2 v Б5; В2 v ДЗ; Г1 v БЗ; АЗ v Е6; ВЗ v Е4. Но тогда будет истинной и формула

F= (А2 v Б5) & (В2 v ДЗ) & (Г1 v БЗ) & (АЗ v Е6) & (ВЗ v Е4).

Путем простых равносильных преобразований легко показать, что

F= Б5 & В2 & Г1 & АЗ & Е4 = 1,

и значит, Б5 = 1; В2 = 1; Г1 = 1; АЗ = 1; Е4 = 1, что и дает ответ на вопрос задачи. Автоматически получаем, что Денис был шестым.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >