Применение алгебры Жегалкина для решения логических задач Из книги С.В. Буфеев, И.С. Буфеев «Основы математической логики и теории множеств» Задача 1. Алёша, Илья и Добрыня нашли в земле хорошо сохранившийся стеклянный сосуд с жидкостью. Рассматривая удивительную находку, каждый высказал по два предположения: Алёша: «Это сосуд французский и имеет 5 звёздочек». Илья: «Это сосуд испанский и имеет 3 звёздочки». Добрыня: «Это сосуд не французский и имеет 4 звёздочки». Змей Горыныч объяснил ребятам, что каждый из них прав только в одном из двух предположений. Где изготовлен сосуд и во сколько звёздочек оценивается его качество? Решение. Обозначим высказывания: «Сосуд — французский» — F, «Сосуд — испанский» — S, «Сосуд имеет n звёздочек» — Zₙ. Условие задачи можно записать в виде: (F ⊕ Z₅) (S ⊕ Z₃) (F ⊕ 1 ⊕ Z₄) = 1. Упростим левую часть равенства. (F ⊕ Z₅) (S ⊕ Z₃) (F ⊕ 1 ⊕ Z₄) = = (F S ⊕ F Z₃ ⊕ Z₅ S ⊕ Z₅ Z₃) (F ⊕ Z₄ ⊕ 1) = = F Z₃ ⊕ S Z₅ = 1. Получившееся равенство возможно в двух случаях: F = 1, Z₃ = 1, S = 0, Z₅ = 0 или S = 1, Z₅ = 1, F = 0, Z₃ = 0. Однако первый случай не реализуется, ибо третий множитель исходной формулы при этом даёт решение Z₄ = 1, что невозможно при Z₃ = 1. Поэтому S = 1, Z₅ = 1. Ответ: сосуд испанский, 5 звёздочек. Задача 2. По подозрению в совершении преступления задержали Брауна, Джонса и Смита. Браун: «Я совершил это. Джонс не виноват». Джонс: «Браун не виноват. Преступление совершил Смит». Смит: «Я не виноват. Виновен Браун». В процессе следствия выяснилось, что у одного из подозреваемых оба утверждения ложны, у другого одно истинно, а другое ложно, у третьего оба истинны, а также что преступник только один. Требуется определить имя преступника и выяснить, кто говорил правду, а кто нет. Решение. Обозначим буквами B, J, S соответственно высказывания «Виноват Браун», «Виноват Джонс», «Виноват Смит». Тогда утверждения, высказанные задержанными, можно записать в виде конъюнкций B ¬J, ¬B S, B ¬S, из которых по условию задачи две ложны, а одна истинна. Истинной будет формула F = B ¬J ∨ ¬B S ∨ B ¬S = 1. Упростим её: F = B (J⊕1) ∨ (B⊕1) S ∨ B (S⊕1) = = B ∨ S ∨ B = B ∨ S = 1. Значит, преступление совершил Браун или Смит. Предположим, преступник Браун. Тогда из трёх конъюнкций, составляющих функцию F, истинными будут две. А это противоречит условию задачи. Поэтому B = 0, и очевидно, S = 1 удовлетворяет условию задачи. Ответ: преступник — Смит, оба его высказывания ложны, у Брауна одно высказывание ложно, другое нет, Джонс сказал правду. Задача 3. Один из пяти братьев разбил окно. — Это мог сделать только или Виктор, или Сергей, — сказал Андрей. — Я окно не разбивал, — возразил Виктор, — и Егор тоже. — Вы оба говорите неправду, — заявил Сергей. — Нет, Сергей, один из них сказал правду, а другой сказал неправду, — возразил Дмитрий. — Ты, Дмитрий, неправ, — вмешался Егор. Их отец, которому, конечно, можно доверять, уверен, что трое братьев сказали правду. Кто разбил окно? Решение. Введём логические переменные A, B, C, D, E, определяющие, кто из братьев разбил окно, — соответственно Андрей, Виктор, Сергей, Дмитрий, Егор. Запишем алгебраически высказывания братьев: Андрей: a = B ⊕ C, Виктор: b = ¬B ¬E = (B⊕1)(E⊕1) = B⊕E⊕1 = A⊕C⊕D. (Мы воспользовались тем, что B E = 0, поскольку по условию задачи окно разбил только один из братьев.) Сергей: c = ¬a ¬b = ¬(B⊕C) ¬(¬B ¬E) = = ¬B ¬C (B⊕E) = ¬B ¬C E = E. Дмитрий: d = a ¬b ⊕ ¬a b = = (B⊕C) ¬(¬B ¬E) ⊕ ¬(B⊕C) (¬B ¬E) = = (B⊕C) (B⊕E) ⊕ ¬B ¬C ¬B ¬E = = B ⊕ (B E) ⊕ (B C) ⊕ (C E) ⊕ ¬B ¬C ¬E = = B ⊕ (B⊕1)(C⊕1)(E⊕1) = = B ⊕ (B ⊕ C ⊕ E ⊕ 1) = B ⊕ C ⊕ E ⊕ 1 = A ⊕ D. Егор: e = ¬d = ¬(A ⊕ D) = B ⊕ C ⊕ E. По условию задачи, трое братьев сказали правду. Образуем из формул a, b, c, d, e конъюнкции, беря в каждую по три формулы: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde. Поскольку a и c, b и c, c и d в конъюнкции дают противоречия, то из десяти сочетаний оставляем только три: abd, abe и bde. Легко видеть, что abd = (B⊕C) (A⊕C⊕D) (A⊕D) = 0, bde = (A⊕C⊕D) (A⊕D) (B⊕C⊕E) = 0, abe