Таблицы истинности

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

Пример: Облегченный вариант задачи "Кто держит зебру?" (Einstein’s riddle)

Пусть есть:

• 3 дома: 1, 2, 3
• 3 человека: Алексей, Bалентин, София
• 3 животных: кот, собака, зебра

Условия:

• Алексей не живёт в доме 1
• Bалентин живёт в доме 2
• Владелец зебры живёт не в доме 1
• София не держит зебру
• Алексей не держит собаку
• В каждом доме ровно один человек и одно животное

По правилам логики, общее количество комбинаций в таблице рассчитывается по формуле: $2^n$ где $n$ — количество переменных. В нашем случае: $2^6=64$. Но мы будем сторить таблицы по одной переменной.

Дома. Все возможные распределения людей по домам:

• Алексей не живёт в доме 1 (Алексей ≠ дом 1) - значит 1 и 2 вариант таблицы убираем
• B живёт в доме 2 (Bалентин = дом 2) - значит 3,4 и 5 варианты таблицы убираем

Всего перестановок: 3! = 6 и Фильтруем по условиям. И получим единственное распределение людей по домам, это 6-й вариант.

Животные. Все возможные распределения животных:

• Владелец зебры живёт не в доме 1
• София не держит зебру (зебра ≠ дом 1) - значит 5 и 6 вариант таблицы убираем
• Алексей не держит собаку (собака ≠ дом 3) - значит 2 вариант таблицы убираем
• У владельца зебры есть сосед справа (зебра ≠ дом 3) - значит 1 и 3 вариант таблицы убираем

Всего перестановок: 3! = 6 и Фильтруем по условиям. И получим единственное распределение животных, это 4-й вариант.

Теперь главное: почему таблица истинности плохо масштабируется. Таблица истинности — это «тупой перебор», мы генерируем все возможные варианты, потом выкидываем лишнее.

В упрощённой задаче: люди: 3! = 6 вариантов, животные: 3! = 6 вариантов, в итоге всего 36 комбинаций.

В полной задаче: 5 категорий по 5 значений (5!)⁵ ≈ 24 883 200 000 (25 миллиардов комбинаций). Таблица истинности становится невозможной.

Constraint table — «умный перебор».

В задаче типа Einstein’s riddle, мы не генерируем комбинации, а сразу запрещаем невозможные связи.

Условия задачи "Кто держит зебру?":

• На улице стоят 5 домов.
• Англичанин живет в красном доме.
• Швед держит собаку.
• Датчанин пьет чай.
• Зеленый дом стоит слева от белого (они соседние).
• Жилец зеленого дома пьет кофе.
• Человек, который курит Pall Mall, держит птиц.
• Жилец желтого дома курит Dunhill.
• В центральном доме (№3) пьют молоко.
• Норвежец живет в первом доме.
• Курильщик Blend живет рядом с тем, кто держит кошек.
• Человек, который держит лошадей, живет рядом с тем, кто курит Dunhill.
• Курильщик Blue Master пьет пиво.
• Немец курит Prince.
• Норвежец живет рядом с синим домом.
• У курильщика Blend есть сосед, который пьет воду.

Заносим факты в таблицу (самые очевидные факты):

Продолжаем формировать "острова сязей":

• Немец + сигареты Prince
• сигареты Blend имеет соседа пьющего Воду и соседа с Кошками
• Норвежец + №1 Дома имеет соседа с Синим домом
• Жилец №2 Дома имеет Синний цвет дома
• сигареты Blue Master + Пиво
• сигареты Dunhill + Жёлтый и сосед с Лошадьми
• №3 Дом + Молоко
• сигареты Pall Mall + Птицы

Получаем:

• Зеленый дом может иметь только №4 Дома
• И в Доме №4 может жыть только Немец курящий Prince
• Тогда жилец №5 Дома имеет Белый цвет дома
• Тогда Норвежец не в зеленом доме
• Швед и датчанин в Доме №2 или №5, тогда в Доме №3 может жить только англичанин

Оставшиеся "острова сязей":

• курильщик Blend имеет соседа пьющего Воду и соседа с Кошками
• курильщик Blue Master + пьет Пиво
• курильщик Dunhill + Жёлтый дом и сосед с Лошадьми
• курильщик Pall Mall + Птицы
• жилец Дома №5 имеет Белый цвет дома
• жилец Дома №2 имеет Синий цвет дома

Получаем:

• жилец Дома №1 имеет Жёлтый цвет дома (так как остальные уже распределены)
• тогда в Доме №1 курильщик Dunhill и в доме №2 живет датчанин и любит Лошадей
• норвежец или швед курит сигареты Blue Master + пьет Пиво
• курильщик Blend
  • курильщик Blend не живет в доме №5
  • норвежец не курит Blend (так как у шведа и датчанина нет двух пустых ячеек для напитка и животного)
  • курильщик Blend англичанин только если в доме №2 швед
  • тогда курильщик Blend может быть только датчанин из дома №2, тогда воду пьет норвежец
• норвежец или англичанин с Кошками
• швед курильщик Blue Master + Пиво
• тогда остается только один курильщик Pall Mall + Птицы это дом №3
• тогда у соседа курящего Blend с кошками есть только один вариант это дом №1
• тогда зебра может быть только у немца в доме №4