Составление таблицы истинности кажется наиболее надежным методом проверки разных булевых формул в том смысле, что этот процесс довольно примитивен. Одно плохо: при большом количестве переменных или большом количестве операций в формуле этот процесс требует много времени. Можно ли как-нибудь ускорить это дело? Да, можно.
Речь пойдет о составлении сокращенных таблиц истинности с помощью формул поглощения. При составлении обычной таблицы мы заполняем за один шаг одну строку. Для сокращенной таблицы мы заполняем за один шаг сразу несколько строк (больше или меньше - как повезет). При составлении обычной таблицы мы начинаем вычисление каждой строки от операций наивысшего приоритета. При составлении сокращенной таблицы мы часто начинаем с той операции, которая вычисляется последней.
Составим сокращенную таблицу для формулы
B) ((A (B C)) (A ~C))
Для начала нарисуем заготовку. В ней заполним ячейки только для одной переменной,
скажем,
Зафиксируем
B) ((A (B C)) (A ~C)) = B) ((false (B C)) (false ~C)) = ((false (B C)) (false ~C)) = (B C)) (false ~C) = (false ~C) = true =
То есть, когда
Зафиксируем теперь
B) ((A (B C)) (A ~C)) = B) ((true (B C)) (true ~C)) = ((true (B C)) (true ~C)) = ((B C) (true ~C)) = ((B C) ~C)
Формула получилась по-проще, но не константа. Подготовим таблицу к рассмотрению обоих случаев
для
Фиксируем
((B C) ~C) = ((false C) ~C) =
Вписываем:
Фиксируем
((B C) ~C) = ((true C) ~C) = C) ~C = ~C =
Не константа. Готовим таблицу:
Заполняем оставшиеся ячейки таблицы, вычисляя
Замечание. Какую переменную фиксировать первой? Лучше всего ту, которая сильнее всего упростит формулу, благодаря законам поглощения. А это более вероятно для тех переменных, которые в формулах встречаются чаще других. Также это более вероятно для переменных, операции над которыми выполняются последними.