Решение логических задач

При решении логических задач применяют правила и законы алгебры логики.

Методика решения состоит в следующем:

1.       Внимательное изучение условий предлагаемой задачи.
2.       На основании анализа условия формируется логическое высказывание и далее для них водится система обозначений.
3.       Составляется логическая формула.
4.       Устанавливается значение истинности этой логической формулы.
5.       Из полученных знаний деятельности делается вывод об истинности логических высказываний, введенных в соответствии с условиями задачи.

Примеры решения задач

Пример 1

Три внука Костя, Вася и Стас остались в гостях у бабушки. Кто-то из мальчиков случайно разбил хрустальную вазу. После того как бабушка спросила кто это сделал, внуки дали следующий ответ:

•       Стас ответил, что не разбивал и что Вася не разбивал.
•       Вася ответил, что Стас не разбивал вазу и ее разбил Костя.
•       Костя ответил, что не разбивал вазу, а разбил ее Стас.

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

В данной задаче мы имеем дело с тремя логическими высказываниями. Для каждого из них следует ввести обозначения:

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

Противоположные им высказывания можно выразить, используя инверсию:

•       — Костя не разбивал;
•       — Вася не развивал;
•       — Стас не разбивал.

Решение задачи

Составляем таблицу истинности, в которой запишем высказывание каждого внука.

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

Костя	Вася	Стас
0	0	1
0	1	0
1	0	0

Исходя из того, что знает о внуках бабушка, следует искать в таблице строку, содержащую в каком-либо порядке три комбинации значений:

•       00 — слова шутника,
•       11 — слова правдиво внука,
•       01 или 10 — слова хитреца.

Костя	Вася	Стас	Утверждение Стас		Утверждение Васи		Утверждение Костя
						К		С
0	0	1	0	1	0	0	1	1
0	1	0	1	0	1	0	1	0
1	0	0	1	1	1	1	0	0

Эта комбинация представлена в первой строке. Значит, вазу разбил Стас и оказался хитрецом. А шутником оказался Вася. Имя правдиво внука Костя.

Пример 2

Трое мальчиков Ваня, Артем и Слава нашли старинный сосуд. Рассматривая находку, каждый из них высказал по два предположения:

•       Ваня сказал — это греческий сосуд, он изготовлен в V веке,
•       Артем сказал — это финикийский сосуд, он изготовлен в III веке,
•       Слава сказал — это не греческий сосуд, он изготовлен в IV веке.

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

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

•       Х1 — греческий сосуд,
•       Х2 — финикийский сосуд,
•       Х3 — не греческий сосуд,
•       Y3 — сосуд изготовлен в III веке,
•       Y4 — сосуд изготовлен в IV веке,
•       Y5 — сосуд изготовлен в V веке.

Для удобства индексы у переменных Y соответствуют векам.

В задаче рассматривается только две возможности происхождения сосуда — греческий или финикийский, то есть не греческий. Поэтому можно заменить инвертированные X2 и X3 просто на X1.

Х1 = 2 = 3

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

Ваня: Х1VY5 = 1

Артем: VY3 = 1

Слава: 1VY4 = 1

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

(Х1VY5)^(VY3)^(1VY4) = 1

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

(Х1VY5)^(Х1VY3) = Х1^V Х1^Y3VY5^VY5^Y3

Конъюнкция логического высказывания и инвертированного ему всегда ложна. Этот закон называется законом исключения третьего.

Х1^ = 0,     Y5^Y3 = 0

Высказывание Y5^Y3 означает, что сосуд изготовлен одновременно в V и III веке. Но так как сосуд не мог быть изготовлен в двух веках, то конъюнкция Y5^Y3 — ложна.

Теперь наше выражение примет вид

(X1^Y3VY5^X1)^(X1VY4) = 1

Раскроем скобки

(X1^Y3VY5^)^(VY4) = X1^Y3^VX1^Y3^Y4VY5^^VY5^^Y4

Несколько высказываний будут ложными:

•       Первое на основании закона исключения третьего, который уже использовали чуть раньше

Х1^Y3^ = 0

•       второе и третье из-за того, что сосуд может быть изготовлен только в каком-то одном веке

X1^Y3^Y4 = 0

Y5^^Y4 = 0

Логическое произведение равно 1 (истине), только когда оба множителя истинны.

= 1, то есть Х1 = 0, и Y5 = 1

Ответ: Мальчики нашли финикийской сосуд V века.

Пример 3

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента.

Запрос	Найдено страниц (в тысячах)
протон & бозон	165
фотон & бозон	80
фотон & протон & бозон	125

Определите число, которое будет соответствовать следующему запросу:

(протон│фотон) & бозон

Допустим, что все запросы осуществлялись практически синхронно. Тогда набор страниц, включающий все искомые данные, за период выполнения запросов оставался неизменным.

В языке запросов для записи логической операции «или» применяется вертикальная черта, а для логической операции «и» — символ «ампесанд».

Здесь представлено три множества — количество страниц, содержащих слова протон, фотон и бозон. Для решения таких задач удобно использовать диаграммы Венна, названные так по имени английского логика и философа Джона Венна.

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

Каждое множество представляет кругом, пересечению множеств соответствует их общая часть, а объединению — суммарное занимаемое ими пространство.

Запросам, которые указаны в таблице в условии задачи соответствует области, показанные на данном рисунке.

Теперь введем обозначения и выполни вычисление.

Область B мы задействуем дважды — в запросах протон и бозон, и  фотон и бозон. Так что соответствующее этой области количество страниц, мы обязаны вычесть.

A+B+C = (A+B)+(B+C) – B = 165+80-125 = 120

В результате по запросу (протон│фотон) & бозон будет выдано 120 тыс. страниц.