Цинічне рішення логічних завдань



Недавно натрапив у «Вікіпедії» на статтю про так звану самої складної логічної задачі. Стаття вразила мене своєю провокаційністю, то логічної безграмотністю, особливо в частині авторських пояснень її умов та можливого ходу рішення.

Умова задачі

Є три боги: A, B і C, один з яких бог істини, інший — брехні, а третій — випадку. Бог істини завжди говорить правду, бог брехні — завжди обманює, бог випадку може говорити і правду, і неправду. Потрібно визначити богів, задавши 3 питання, на які можна відповісти «так» або «ні». Кожне питання задається тільки одному богу. Боги розуміють мову, але відповідають на своїй мові, в якому є 2 слова «da» та «ja», причому невідомо, яке слово позначає «так», а яке «ні».

Спочатку розглянемо рішення цієї задачі цинічним способом. Коротко спосіб характеризується двома тезами:
  1. Задача повинна бути зведена до системи логічних рівнянь і нерівностей (СЛУН);
  2. Обмеження на значення вхідних змінних записуються в реляційні таблиці. Рішення СЛУН здійснюється виконанням SQL-запиту. Побудована реляційна таблиця містить 0 або більше рішень логічної задачі. Кожен рядок таблиці — це одне з рішень логічної задачі.


Проілюструємо наші тези рішенням самої складної логічної задачі.

Позначимо А.СТАТУС, В.СТАТУС і С.СТАТУС змінні СЛУН, яку ми зараз складемо. Можливі значення змінних — рядкові значення «ІСТИНА», «НЕПРАВДА» І «ВИПАДОК». Для їх позначення нижче будемо використовувати ідентифікатори ІСТИНА, БРЕХНЯ І ВИПАДОК.

Вивчення умови задачі дозволяє скласти одне логічне рівняння:

(А.СТАТУС <> В.СТАТУС AND А.СТАТУС<>С.СТАТУС AND В.СТАТУС<>С.СТАТУС AND) EQV TRUE — це формальна запис першого умови завдання.

SQL-запит для рішення рівняння має вигляд:

SELECT * FROM А, В, С WHERE (А.СТАТУС<>В.СТАТУС AND А.СТАТУС <> С.СТАТУС AND В.СТАТУС <> С.СТАТУС) EQV TRUE;


Рішення рівняння (їх 6) і одна з таблиць з обмеженнями на значення вхідних змінних представлена на малюнку нижче:


Будь-який з шести рішень рівняння і є відповідь на запитання задачі. Ця відповідь отримано без бесід з богами.

Щоб підтримати «дедуктивний» діалог з метою отримання єдиного варіанта відповіді, задамо кожному з богів з одного питання, наприклад:

Богу: «Не є бог З богом випадку?». Богу: «Не є бог, А богом брехні?». Бога: «чи Не є він богом випадку?» Формально ці питання можуть бути записані у вигляді системи з 6 логічних нерівностей, рішенням якої буде єдина відповідь: А — бог істини, — бог брехні, а З — бог випадку. Зазначимо, що відповіді богів — «da» або «ja» для вирішення завдання не потрібні.

Система нерівностей має вигляд:



Доповнимо конъюнктивно пропозицію WHERE нашого SQL-запиту цією формулою і отримаємо відповідь на запитання задачі у вигляді реляційної таблиці з одним рядком.

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

Застосування тези про формалізації логічного завдання системою (або декількома системами) логічних рівнянь і нерівностей дозволяє чітко фіксувати умови завдання. В постановці самої складної логічної задачі дано лише одне рівняння. Для отримання єдиного відповіді автор задачі неявно пропонує доповнити її умову, що ми і зробили, сформулювавши 6 трійок питань. Теза про формалізації логічних завдань СЛУН змушує це розуміти без еківоків.

Перетворення СЛУН в SQL-запит неважко автоматизувати. Для деяких різновидів СЛУН і діалектів SQL це вже зроблено (ознайомитися з вирішенням інших завдань, додатковою інформацією та матеріалами можна тут). Особливий інтерес представляють системи логічних рівнянь, рішення яких здійснюється виконанням рекурсивних SQL-запитів.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.