Логические задачи очень разнообразны. Способов их решения тоже немало. Но наи-большее распространение получили следующие три способа решения логических задач:
• средствами алгебры логики;
• табличный;
• с помощью рассуждений;
 

      Обычно используется следующая схема решения:
1. Изучается условие задачи.
2. Вводится система обозначений для логических высказываний.
3. Конструируется логическая формула, описывающая логические связи между всеми высказываниями, выделенными из условия задачи.
4. Определяются значения истинности этой логической формулы.
5. Из полученных значений истинности формулы определяются значения истин-ности введённых логических высказываний, на основании которых делается заключение о решении.
Рассмотрим текстовые задачи, которые могут быть решены с привлечением аппарата алгебры логики, т. е. основных законов алгебры логики.

ЗАДАЧА 1.

     Однажды гномы, решившие отправиться за сокровищами, собрались на совет, чтобы обсудить возможные опасности, которые их ожидают. Было высказано три предложения:
1. Их либо захватят гоблины, либо нападёт дракон, либо они заблудятся в лесу, либо их ожидают какие – то две, а может быть, и все три из этих опасностей.
2. Если дракон не нападёт, то они утонут в реке.
3. И дракон нападёт, и заблудятся в лесу.
     Помогавший им волшебник успокоил их и сказал, что второе и третье предположения ложны. Каких же опасностей следует ожидать гномам?
 

Решение:

Введём логические переменные:
x – гномов захватят гоблины;
y – на гномов нападёт дракон;
z – они утонут в реке;
w – они заблудятся в лесу.
     Первому высказыванию соответствует формула x+y+w, второму – y→z и третьему– z&w.
     С учётом, что второе и третье высказывания ложны, запишем истинное составное вы-сказывание и упростим его.
(x+y+w)&(y→z)&z&w= (x+y+w)&(y+z)&(z+w)= (x+y+w)&y&z&(z+w)= (x&y&z+y&z&w)&(z+w)= x&y&z+x&y&z&w+y&z&w= x&y&z+y&z&w.
     Из полученного выражения видно, что исходное высказывание истинно, когда истин-но x, а y и z – ложны, либо когда истинно w, а y и z – ложны, либо когда x и w одновременно истинны, а y и z – ложны. Возвращаясь к исходной интерпретации, можно сказать, что гно-мам следует приготовиться и к нападению гоблинов, и к переходу через лес.

ЗАДАЧА 2.

     Один король как – то подвергся нападению вражеской армии и был осаждён в крепо-сти, в которой были северные и южные ворота. Чтобы выдержать штурм, ему необходимо было точно знать, на какие из этих ворот готовится атака.
     Рано утром перед началом штурма к нему привели пленника, захваченного у против-ника. Об этом пленнике было известно, что он либо рыцарь, который всегда говорит правду, либо лжец, который всегда лжёт, и, кроме того, на все вопросы он отвечает только «да» или «нет».
      Король быстро понял, что задавать простые вопросы бесполезно. Если бы он спросил: «Назначен ли штурм на северные ворота?» - и получил бы ответ «да», то из этого ответа нельзя было бы сделать правильного вывода. Если бы штурм действительно был назначен на северные ворота, то рыцарь ответил бы «да», а лжец «нет». А если бы на южные, то рыцарь сказал бы «нет», а лжец – «да». Поскольку король не знал, кто перед ним (рыцарь или лжец), то ответ «да» не позволял бы понять, верно ли, что штурм назначен на северные ворота.
     Король впал в отчаяние, но присутствующий при допросе логик задал вопрос, с по-мощью которого удалось установить, на какие ворота готовится штурм. Какой это вопрос?

Решение:

Необходимо рассмотреть четыре возможности.

Место штурма               Кто пленник            Ответ
северные ворота           Рыцарь                     да
северные ворота             Лжец                       да
южные ворота                Рыцарь                    нет
южные ворота                  Лжец                       нет

       Надо сформулировать вопрос, ответ на который в первых двух случаях будет «да», и «нет» в двух остальных. Пусть вопрос будет таким: «Верно ли, что штурм назначен на юж-ные ворота и ты лжец, или неправда, что штурм назначен на южные ворота и ты рыцарь?»
       В первом случае (северные ворота – рыцарь) на первую часть вопроса: «Верно ли, что штурм назначен на южные вопросы и ты лжец?» - рыцарь ответит «нет», потому что на са-мом деле штурм назначен на северные ворота. На вторую часть вопроса: «Верно ли, что не-правда, что штурм назначен на южные ворота и ты рыцарь?» - рыцарь ответит «да», потому что это действительно неправда. Поэтому ответ на весь вопрос будет «да».
       Во втором случае (северные ворота – лжец) на первую часть вопроса лжец ответит «да», потому что на самом деле штурм назначен на северные ворота, а лжец говорит неправ-ду. Поэтому независимо от ответа на вторую часть вопроса ответ на весь вопрос будет «да», это следует из определения дизъюнкции.
       В третьем случае (южные ворота – рыцарь) на первую половину вопроса рыцарь отве-тит «нет», потому что он не лжец. На вторую половину вопроса он также скажет «нет», по-тому что верно, что штурм назначен на южные ворота и он рыцарь. Значит, ответ на весь во-прос будет «нет».
      В четвёртом случае (южные ворота – лжец) на первую половину вопроса лжец отве-тит «нет», потому что это истина. На вторую половину он также скажет «нет», потому что он не рыцарь, значит, это в самом деле неправда, но лжец вместо «да» всегда говорит «нет». От-сюда ответ на весь вопрос будет «нет».
       Таким образом, независимо от того, рыцарь это или лжец, каждый из них ответит «да», если штурм назначен на северные ворота, и «нет» - если на южные.

ЗАДАЧА 3.

       Менеджер банка должен установить 4 банкомата. В течение каждого дня работы должны выполняться следующие условия:
1. Если работает первый банкомат, то третий банкомат не должен работать, а второй и четвёртый должны.
2. Если работает третий банкомат, то первый и четвёртый не должны работать, а вто-рой должен.
3. Должен работать по крайней мере один банкомат.
     Необходимо определить наибольшее число дней, которое могут работать банкоматы при выполнении этих условий, так, чтобы их назначение ни в один из дней не повторялось, а также указать допустимое расписание на каждый день.
 

Решение:

     Максимальное количество дней и соответствующее расписание можно най-ти прямым перебором. При четырёх переменных надо рассмотреть 16 логических возможно-стей. Однако более рационально построить составное высказывание, истинное для заданных условий, а затем преобразовать соответствующую ему формулу к СДНФ. Введём логические переменные:
w – работает первый банкомат;
x – работает второй банкомат;
y – работает третий банкомат;
z – работает четвёртый банкомат.
      Первому условию соответствует формула w→x&y&z, а второму- y→w&x&z. Запи-шем формулу истинного составного высказывания, определяющего ежедневную работу бан-коматов в соответствии с первыми двумя условиями: (w→x&y&z)&(y→w&x&z)=(w+x&y&z)&(y+w&x&z). Раскроем скобки и получим: w&y+w&x&z+x&y&z. Учитывая, что выражения
(x&z+x&z+x&z+x&z)=1
(y+y)=1
(w+w)=1
       перепишем исходную формулу в виде эквивалентного выражения:
w&y&(x&z+x&z+x&z+x&z)+w&x&z&(y+y)+x&y&z&(w+w)= w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z
исключив из него повторяющиеся элементарные конъюнкции, а также конъюнкцию w&x&y&z, которая противоречит третьему условию, получим выражение в форме СДНФ: w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z.
        Анализируя его, можно сказать, что максимальное число дней, при котором нет по-вторений в работе банкоматов, равно пяти, потому что в полученном выражении 5 элемен-тарных конъюнкций, а каждая элементарная конъюнкция этого выражения определяет на-значение банкоматов на один день работы. Допустимое расписание работы может быть та-ким: в первый день работает четвёртый банкомат (это следует из того, что в первую конъ-юнкцию w&x&y&z переменная z входит без отрицания), во второй день – второй банкомат, в третий день должны работать второй и четвёртый, в четвёртый день – второй и третий бан-коматы и, наконец, в пятый день – первый, второй и четвёртый банкоматы.

ЗАДАЧА 4.

        Имеется множество из 8 различных букв {A, B, C, D, E, F, G, H}. Один из играющих задумывает любую букву из этого множества. Другой играющий должен угадать эту букву. Он имеет возможность задать три вопроса, ответы на которые должны быть «да» или «нет». Вопросы должны быть заданы независимо один от другого, т. е. второй играющий узнает от-веты только после того, как он задал все три вопроса. Какие вопросы необходимо задать?
 

Решение:

       Если выбрать какую – то букву из заданного множества и спросить, являет-ся ли она задуманной, то в общем случае потребуется 7 вопросов для установления искомой буквы. Чтобы была возможность определять любую букву при помощи трёх вопросов, надо разбить множество на три подмножества. Возьмём три такие подмножества: {B, D, F, H}, {E, F, G, H}, {C, D, G, H}.
        Три вопроса будут такими:
1. Входит ли задуманная буква в первое подмножество?
2. Входит ли задуманная буква во второе подмножество?
3. Входит ли задуманная буква в третье подмножество?
        Если получено три ответа «да», то задумана буква H, поскольку только она входит во все три подмножества. Если получены «да», «да», «нет», то задумана буква F, потому что только она входит в первое и второе подмножества, но не входит в третье. Если получены ответы «да», «нет», «да», то задумана буква D, потому что только она входит в первое и третье подмножества и не входит во второе, и т. д. Наконец, если получено три ответа «нет», то это буква A, потому что она не входит ни в одно из подмножеств.
       Этот пример иллюстрирует прямую аналогию между алгеброй логики и алгеброй множеств. Если вместо операции конъюнкции рассматривать операцию пересечения мно-жеств, а вместо операции дизъюнкции – операцию объединения множеств, то эти операции над подмножествами заданного множества подчиняются тем же законам, что и операции над высказываниями. В то же время любая алгебраическая система, подчиняющаяся этим зако-нам, называется булевой алгеброй. Поэтому если подмножества обозначать переменными, то с помощью операций объединения и пересечения можно строить сложные выражения (фор-мулы), также определяющие некоторые подмножества. Используя булеву алгебру, можно преобразовывать и упрощать формулы.

ЗАДАЧА 5.

       Трое друзей, болельщиков автогонок «Формула - 1», спорили о результатах пред-стоящего этапа гонок.
- Вот увидишь, Шумахер не придёт первым, - сказал Джон. - Первым будет Хилл.
- Да нет же, победителем будет, как всегда Шумахер,- воскликнул Ник. - А об Алези и говорить нечего, ему не быть первым.
Питер, к которому обратился Ник, возмутился:
- Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.
       По завершении этапа гонок оказалось, что каждое из двух предположений двоих дру-зей подтвердилось, а оба предположения третьего оказались неверными. Кто выиграл этап гонки?
 

Решение:

Введём обозначения для логических высказываний:
Ш – победит Шумахер;
Х – победит Хилл;
А – победит Алези.
      Реплика Ника «Алези пилотирует самую мощную машину» не содержит никакого ут-верждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.
Зафиксируем высказывания каждого из друзей:
Джон: Ш&Х;
Ник: Ш&А;
Питер: Х;
       Учитывая то, что предположения двух друзей подтвердились, а предположения третьего неверны, запишем истинное высказывание:
(Ш&Х)&(Ш&А)&Х+(Ш&Х)&(Ш&А)&Х+(Ш&Х)&(Ш&А)&Х= (Ш+Х)&Ш&А&Х= Ш&А&Х.
Высказывание Ш&А&Х истинно только при Ш=1, А=0, Х=0.
Победителем этапа гонок стал Шумахер.

ЗАДАЧА 6.

       По обвинению в ограблении перед судом предстали Иванов, Петров, Сидоров. Следствием установлено следующее:
1. Если Иванов невиновен или Петров виновен, то Сидоров виновен.
2. Если Иванов невиновен, то Сидоров невиновен.
Виновен ли Иванов?
 

Решение:

Рассмотрим простые высказывания:
A = Иванов виновен,
B = Петров виновен,
C = Сидоров виновен.
Запишем на языке алгебры логики факты, установленные следствием:
(A+B)→C и A→C.
Пусть F(A,B,C) = ((A+B)→C)&(A→C).
Решить задачу – это значит указать, при каких значениях A это сложное высказыва-ние истинно. И если хотя бы в одном случае (при разных значениях B и C) F=1 при A=0 (Иванов невиновен), то у следствия недостаточно фактов для того, чтобы обвинить Иванова в преступлении.
Составим таблицу истинности: 

 

 
Из таблицы истинности видно, что сложное высказывание истинно только когда A – истинно, т. е. Иванов виновен в ограблении.

ЗАДАЧА 7.

      На вопрос, кто из трёх школьников изучал логику, был получен правильный ответ: если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и вто-рой. Кто из учащихся изучал логику?
 

Решение:

Обозначим через P1, P2, P3, высказывания, состоящие в том, что, соответ-ственно, первый, второй, третий школьник изучали логику. Из условия задачи следует ис-тинность высказывания:
(P1→P2)&(P3→P2).
Воспользуемся тем, что A→B=A+B, и упростим полученное высказывание:
(P1+P2)&P3+P2)=(P1+P2)&(P3&P2)=(P1&P3&P2)+(P2&P3&P2).
Высказывание P2&P2 ложно, а следовательно, ложно и высказывание P2&P3&P2. По-этому истинным является высказывание P1&P3&P2, а это означает, что логику изучал третий учащийся, а первый и второй не изучали.

ЗАДАЧА 8.

Алёша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая удивительную находку, каждый высказал по два предположения:
Алёша: «Это сосуд греческий и изготовлен в V веке».
Боря: «Это сосуд финикийский и изготовлен в III веке».
Гриша: «Это сосуд не греческий и изготовлен в IV веке».
Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предположений.
Где и в каком веке изготовлен сосуд?
 

Решение:

Рассмотрим простые высказывания:
A = сосуд греческий,
B = сосуд финикийский,
C = сосуд изготовлен в III веке,
D = изготовлен в IV веке,
E = сосуд изготовлен в V веке.
Запишем предположения школьников на языке алгебры логики:
A&E (слова Алёши),
B&C (слова Бори),
A&D (слова Гриши).
    Из слов учителя следует, что каждое из этих высказываний ложно, так как каждый мальчик прав только в чём-то одном. Предположим, Алёша угадал, что сосуд греческий (А=1), но ошибся во времени его изготовления (Е=0). В противном случае (верно угадано время изготовления, но неправильно – место) А=0 и Е=1. Следовательно, всегда А+Е=1.
Рассуждая аналогично, получаем ещё два истинных сложных высказывания:
В+С=1,
А+D=1.
Если все эти высказывания логически перемножить, то получится истинное сложное высказывание:
(A+E)&(B+C)&(A+D)=1
Раскроем скобки:
(A&B+A&C+E&B+E&C)&(A+D)=1 (2)
Исходя из того, что сосуд мог быть изготовлен только в одной стране и в одном веке, запишем высказывания заведомо ложные:
A&B=0, 
E&C=0.
Получим из (2): 
(0+A&C+E&B+0)&(A+D)=1
(A&C+E&B)&(A+D)=1
A&C&A+A&C&D+E&B&A+E&B&D=1 (2´)
Снова запишем высказывания заведомо ложные:
A&A=0,
C&D=0,
E&D=0.
Следовательно:
A&C&A=0,
A&C&D=0,
E&B&D=0.
Подставим в (2´)
0+0+E&B&A+0=1
Значит, Е&B&A=1.
Мы установили, что сосуд финикийский и изготовлен в V веке, что удовлетворяет ус-ловию задачи. 

ЗАДАЧА 9.

Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на поджидавшем их автомобиле. На следствии Браун показал, что преступники скрылись на синем «Бьюике», Джонс сказал, что это был чёрный «Крайслер», а Смит утверждает, что это был «Форд Мустанг», и ни в коем случае не синий. Стало извест-но, что желая запутать следствие, каждый из них указал правильно либо только марку маши-ны, либо только её цвет.
Какого цвета и какой марки был автомобиль?
 

Решение:

Рассмотрим простые высказывания:
A = машина синего цвета,
B = машина марки «Бьюик», 
C = машина чёрного цвета,
D = машина марки «Крайслер»,
E = машина марки «Форд Мустанг».
Так как либо цвет, либо марка машины каждым из соучастников названа верно, то из их слов можно заключить, что:
A+B=1 (из слов Брауна),
C+D=1 (из слов Джонса),
A+E=1 (из слов Смита).
Если все эти высказывания логически перемножить, то получится истинное высказы-вание:
(A+B)&(C+D)&(A+E) = 1&1&1 =1. (1)
По аналогии с алгеброй чисел выполним преобразование левой части этого выраже-ния:
(A&C&A)+(A&C&E)+(A&D&A)+(A&D&E)+(B&C&A)+(B&C&E)+(B&D&A)+(B&D&E)=1
Запишем заведомо ложные высказывания.
Во - первых:
A&A=0.
Так как разыскиваемый автомобиль определённой марки и цвета, то все логические произведения, содержащие высказывания о разных цветах одного автомобиля, являются ложными:
A&C=0,
D&E=0,
B&E=0,
B&D=0.
Следовательно:
A&C&A=0,
A&C&E=0,
A&D&A=0,
A&D&E=0,
B&C&E=0,
B&D&E=0,
B&D&A=0.
Подставим эти значения в (1):
0+0+0+0+(B&C&A)+0+0+0=1.
Единственное выражение, значение которого может быть истинным, это B&C&A. Действительно, чёрный «Бьюик» удовлетворяет условию задачи.
Следовательно, B&C&A=1, т. е. автомобиль был чёрного цвета марки «Бьюик».

Задача Эйнштейна.

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

Известно, что:
Англичанин живет в красном доме.
Швед держит собаку. 
Датчанин пьет чай. 
Зеленой дом стоит слева от белого. 
Жилец зеленого дома пьет кофе. 
Человек, который курит Pallmall, держит птицу. 
Жилец среднего дома пьет молоко. 
Жилец из желтого дома курит Dunhill. 
Норвежец живет в первом доме. 
Курильщик Marlboro живет около того, кто держит кошку. 
Человек, который содержит лошадь, живет около того, кто курит Dunhill.
Курильщик Winfield пьет пиво. 
Норвежец живет около голубого дома. 
Немец курит Rothmans. 
Курильщик Marlboro живет по соседству с человеком, который пьет воду. 
Вопрос: У кого живет рыба?

Решение:

ШАГ 1
По условию, норвежец живёт в первом доме (9). Из (14) следует, что второй дом синий.
Какого цвета первый дом? Он не может быть ни зелёным, ни белым, поскольку дома? этих двух цветов должны располагаться рядом (5). Красным он тоже не может быть, потому что в красном доме живёт англичанин (1). Итак, первый дом жёлтый.
Следовательно, в первом доме курят «Данхел» (7), а во втором доме держат лошадь (11).
Что пьёт норвежец (который живёт в первом, жёлтом, доме и курит «Данхел»)? Это не чай, поскольку чай пьёт датчанин (4). И не кофе, потому что кофе пьют в зелёном доме (3). И не молоко, которое пьют в третьем доме (8). И не пиво, потому что человек, который пьёт пиво, курит «Винфилд» (12). Следовательно, норвежец пьёт воду.

ШАГ 2
Из (15) следует, что человек, живущий во втором, синем, доме, курит «Мальборо».
Какой национальности человек, живущий во втором, синем, доме, предпочитающий «Мальборо» и держащий лошадь? Это не норвежец — он в первом доме (9). Не англичанин — он в красном доме (1). Не швед — у шведа собака (2). Не немец — немец курит «Ротманс» (13). Значит, во втором доме живёт датчанин и, как следует из (4), пьёт чай.

ШАГ 3
Зеленый дом не может быть третьим, поскольку в нём пьют кофе, а не молоко (3). Зеленый дом не может быть пятым, поскольку справа от него есть дом (5). Следовательно, зеленый дом — четвёртый. Значит, белый дом — пятый, а красный — третий, и в нём живёт англичанин (1). В зеленом доме пьют кофе, и для белого дома остаётся только пиво. Из (12) следует, что в белом доме курят «Винфилд».

ШАГ 4
Где живёт немец, который курит «Ротманс» (13)? Он может жить только в четвёртом, зелёном доме. А значит, человек, который курит «Пал Мал» и разводит птиц, может жить только в третьем, красном доме — это англичанин.

    Конечно, это решение предполагает, что недостающие в условиях задачи животное и есть искомая рыбка. Кроме того, предполагается, что первый дом — слева. Тем не менее, прямо в условиях это нигде не указано. Многие поэтому утверждают, что единственный правильный ответ — «в задаче не хватает данных», так как мы не можем быть уверены в том, что рыбки, например, вообще живут хотя бы в одном из этих домов. Однако, этим суждением зачастую «покрывают» свою неудачу в решении задачи.
     Если предположить, что первый дом находится справа, и в нём живёт норвежец (по условию задачи), то первым слева стоит зелёный, а рядом белый, дальше красный и синий. Разница между первым вариантом решения задачи, в расположении домов по цветам (а в условии об этом ничего не сказано). В итоге решение задачи такое же как и в первом варианте — рыбок разводит немец, пьёт — кофе, курит — Ротманс.