Деревья в логике высказываний

Таблиц истинности достаточно для решения всех задач Л В. Но практическое применение таблиц затрудняется быстрым ростом числа строк в зависимости от увеличения числа атомарных формул. Напомним, что эта зависимость описывается функцией 2^я, где п — число атомарных формул. Например, для анализа формулы, включающей семь атомарных формул, требуется таблица истинности из 2⁷ = 128 строк. Было создано множество методов, преодолевающих указанный недостаток таблиц истинности (аксиоматические, натуральные, секвенциальные исчисления). Ниже объясняется новый способ анализа и преобразования формул Л В, названный в этой книге методом деревьев. Он отличается универсальностью, простотой и эффективностью.

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

Графически изобразить структуру какой-либо формулы означает построить ее дерево по определенным правилам. Все они, за исключением правила П12, которое представляет частный случай правила П11, были приведены в предшествующем параграфе как основные законы логики.