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

Техники таблиц истинности достаточно для решения всех задач ЛВ. Но практическое применение таблиц затрудняется быстрым ростом числа строк в зависимости от увеличения числа атомарных формул.

этой книге методом деревьев. Этот метод отличается универсальностью, простотой и эффективностью.

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

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

Правила построения деревьев в логике высказываний

П2. Если формула имеет вид (ф &ф), тогда дерево, в которое она вхо­дит, начинается или продолжается в каждой своей ветви формулами ф и φ (коммутативность и идемпотентность формул ф и φ подразумевается):

П3.

П4. Если формула имеет видтогда дерево, в которое она вхо­

дит, начинается или продолжается ветвлением каждой ветви на формулу - ф и формулу φ:

П5. Если формула имеет вид (ф ? φ), тогда дерево, в которое она вхо­дит, начинается или продолжается ветвлением на формулу (ф &φ) и фор­мулу

П6. Если формула имеет видтогда дерево, в которое она вхо­

дит, начинается или продолжается ветвлением каждой ветви на формулу

П7. Если формула имеет вид -тогда дерево, в которое она

входит, начинается или продолжается ветвлением каждой ветви на фор-

П8. Если формула имеет видтогда дерево, в которое она

входит, начинается или продолжается в каждой своей ветви формулами

П13.

П14. Ветвь, содержащая по крайней мере одну пару противоречащих друг другу формул (не обязательно атомарных), называется замкнутой, отмечается знаком * и не подлежит дальнейшему продолжению. После своей идентификации замкнутая ветвь удаляется.

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

Каждая ветвь правильно построенного дерева эквивалентна конъюн­кции всех атомарных формул и/или их отрицаний, содержащихся в ней. Назовем такую ветвь полной. Каждое дерево эквивалентно дизъюнкции всех своих полных ветвей.

Процесс конструирования дерева формулы завершается одним из следующих возможных результатов.

• Если дерево формулы включает в себя хотя бы две ветви с нулевой вершиной (без формул), одна из которых содержит атомарную формулу, а другая ее отрицание, значит исходная формула - логическая истина.

• Если все ветви дерева формулы замкнуты, значит исходная формула - логическая ложь.

• Если по меньшей мере одна ветвь дерева формулы незамкнута и нет ни одной пары ветвей с нулевой вершиной, одна из которых содержит атомарную формулу, а другая ее отрицание, значит исходная формула - логически нейтральная

Пример 1

Дерево анализируемой формулы содержит пять ветвей с нулевой вер­шиной и с формулами В (С) и - В (- С), логически отрицающими друг друга. Значит, эта формула - логическая истина.

Пример 2

Все ветви дерева анализируемой формулы замкнуты. Значит, она - ло­гическая ложь.

Пример 3

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

6.8.