Метод аналитических таблиц

Инструмент для доказательства логической формулы

Графическое представление частично построенной пропозициональной таблицы

В теории доказательств семантическая таблица ^[1] ( / t æ ˈ b l oʊ , ˈ t æ b l oʊ / ; множественное число: tableaux ), также называемая аналитической таблицей , ^[2] деревом истины , ^[1] или просто деревом , ^[2] является процедурой принятия решений для сентенциальных и связанных с ними логик и процедурой доказательства для формул логики первого порядка . ^[1] Аналитическая таблица представляет собой древовидную структуру, вычисляемую для логической формулы, имеющую в каждом узле подформулу исходной формулы, которая должна быть доказана или опровергнута. Вычисление строит это дерево и использует его для доказательства или опровержения всей формулы. ^[3] Метод таблиц также может определять выполнимость конечных множеств формул различных логик. Это самая популярная процедура доказательства для модальных логик . ^[4]

Метод деревьев истины содержит фиксированный набор правил для создания деревьев из заданной логической формулы или набора логических формул. Эти деревья будут иметь больше формул на каждой ветви, и в некоторых случаях ветвь может содержать как формулу, так и ее отрицание, то есть противоречие. В этом случае говорят, что ветвь закрывается . ^[1] Если каждая ветвь в дереве закрывается, говорят, что само дерево закрывается. В силу правил построения таблиц, закрытое дерево является доказательством того, что исходная формула или набор формул, использованных для ее построения, сами по себе были противоречивы, ^[1] и, следовательно, ложны. И наоборот, таблица также может доказать, что логическая формула тавтологична : если формула тавтологична, ее отрицание является противоречием, поэтому таблица, построенная из ее отрицания, закроется. ^[1]

История

В своей книге «Символическая логика , часть II» Чарльз Лютвидж Доджсон (также известный под своим литературным псевдонимом Льюис Кэрролл) представил метод деревьев — самое раннее современное использование дерева истины. ^[5]

Метод семантических таблиц был изобретен голландским логиком Эвертом Виллемом Бетом (Beth 1955) ^[6] и упрощен для классической логики Рэймондом Смаллианом (Smullyan 1968, 1995). ^[7] Упрощение Смаллиана, «односторонние таблицы», описано здесь. Метод Смаллиана был обобщен на произвольные многозначные пропозициональные и первопорядковые логики Уолтером Карниелли (Carnielli 1987). ^[8]

Таблицы можно интуитивно рассматривать как последовательные системы, перевернутые вверх дном. Это симметричное отношение между таблицами и последовательными системами было формально установлено в (Carnielli 1991). ^[9]

Логика высказываний

Фон

Формула в пропозициональной логике состоит из букв, которые обозначают пропозиции, и связок для конъюнкции , дизъюнкции , условных предложений , биусловных предложений и отрицания . Истинность или ложность предложения называется его истинностным значением. Формула или набор формул называется выполнимым, если существует возможность приписывания истинностных значений пропозициональным буквам таким образом, что вся формула, которая объединяет буквы со связками, сама по себе также является истинной. ^[1] Такое приписывание называется удовлетворяющим формуле. ^[2]

Таблица проверяет, является ли заданный набор формул выполнимым или нет. Она может быть использована для проверки либо действительности, либо следствия: формула действительна, если ее отрицание невыполнимо, и формулы подразумевают, если невыполнимо. ${\displaystyle A_{1},\ldots ,A_{n}}$ ${\displaystyle B}$ ${\displaystyle \{A_{1},\ldots ,A_{n},\neg B\}}$

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

Общий метод

Основной принцип пропозициональных таблиц заключается в попытке «разбить» сложные формулы на более мелкие до тех пор, пока не будут получены дополнительные пары литералов или дальнейшее расширение станет невозможным.

Начальная таблица для {(a⋁¬b)⋀b,¬a}

Метод работает на дереве, узлы которого помечены формулами. На каждом шаге это дерево модифицируется; в пропозициональном случае единственными разрешенными изменениями являются добавления узла как потомка листа. Процедура начинается с генерации дерева, состоящего из цепочки всех формул в наборе для доказательства невыполнимости. ^[12] Затем следующая процедура может быть многократно применена недетерминированно:

1. Выберите открытый конечный узел. (Конечный узел в начальной цепочке отмечен как открытый).
2. Выберите подходящий узел на ветке над выбранным узлом. ^[13]
3. Применить соответствующий узел, что соответствует расширению дерева ниже выбранного конечного узла на основе некоторого правила расширения (подробно описано ниже).
4. Для каждого вновь созданного узла, который является как литералом/отрицательным литералом, и чье дополнение появляется в предыдущем узле на той же ветви, пометить ветвь как закрытую . Пометить все остальные вновь созданные узлы как открытые .

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

Принцип таблицы заключается в том, что формулы в узлах одной ветви рассматриваются в соединении, в то время как различные ветви считаются дизъюнктированными. В результате таблица представляет собой древовидное представление формулы, которая является дизъюнкцией конъюнкций. Эта формула эквивалентна набору для доказательства невыполнимости. Процедура изменяет таблицу таким образом, что формула, представленная результирующей таблицей, эквивалентна исходной. Одна из этих конъюнкций может содержать пару дополнительных литералов, в этом случае эта конъюнкция оказывается невыполнимой. Если все конъюнкции доказаны невыполнимыми, исходный набор формул является невыполнимым.

И

(a⋁¬b)⋀b порождает a⋁¬b и b

Всякий раз, когда ветвь таблицы содержит формулу , которая является конъюнкцией двух формул, эти две формулы являются следствиями этой формулы. Этот факт можно формализовать следующим правилом для расширения таблицы: ${\displaystyle A\wedge B}$

( ) Если ветвь таблицы содержит конъюнктивную формулу , добавьте к ее листу цепочку из двух узлов, содержащих формулы и ${\displaystyle \wedge }$ ${\displaystyle A\wedge B}$ ${\displaystyle A}$ ${\displaystyle B}$

Это правило обычно записывается следующим образом:

${\displaystyle (\land ){\frac {A\wedge B}{\begin{array}{c}A\\B\end{array}}}}$

Вариант этого правила позволяет узлу содержать набор формул, а не одну. В этом случае формулы в этом наборе рассматриваются в совокупности, поэтому можно добавить в конец ветви, содержащей . Точнее, если узел на ветви помечен , можно добавить к ветви новый лист . ${\displaystyle \{A,B\}}$ ${\displaystyle A\wedge B}$ ${\displaystyle X\cup \{A\wedge B\}}$ ${\displaystyle X\cup \{A,B\}}$

Или

a⋁¬b порождает a и ¬b

Если ветвь таблицы содержит формулу, которая является дизъюнкцией двух формул, например , можно применить следующее правило: ${\displaystyle A\vee B}$

( ) Если узел на ветви содержит дизъюнктивную формулу , то создайте два дочерних узла-братья для листа ветви, содержащих формулы и , соответственно. ${\displaystyle \vee }$ ${\displaystyle A\vee B}$ ${\displaystyle A}$ ${\displaystyle B}$

Это правило разделяет ветвь на две, отличающиеся только для конечного узла. Поскольку ветви рассматриваются в дизъюнкции друг с другом, две результирующие ветви эквивалентны исходной, поскольку дизъюнкция их необщих узлов в точности равна . Правило для дизъюнкции обычно формально записывается с использованием символа для разделения формул двух отдельных узлов, которые должны быть созданы: ${\displaystyle A\vee B}$ ${\displaystyle |}$

${\displaystyle (\vee ){\frac {A\vee B}{A\mid B}}}$

Если предполагается, что узлы содержат наборы формул, это правило заменяется следующим: если узел помечен как , то к листу ветви, в которой находится этот узел, могут быть добавлены два дочерних узла того же уровня, помеченные как и , соответственно. ${\displaystyle Y\cup \{A\vee B\}}$ ${\displaystyle Y\cup \{A\}}$ ${\displaystyle Y\cup \{B\}}$

Нет

Цель таблиц — генерировать все более простые формулы до тех пор, пока не будут получены пары противоположных литералов или пока не будет невозможно применить никакое другое правило. Отрицание можно обработать, изначально приведя формулы в нормальную форму отрицания , так что отрицание будет встречаться только перед литералами. В качестве альтернативы можно использовать законы Де Моргана во время расширения таблицы, так что например рассматривается как . Правила, которые вводят или удаляют пару отрицаний (например, в ), также используются в этом случае (иначе не было бы способа расширить формулу типа : ${\displaystyle \neg (A\wedge B)}$ ${\displaystyle \neg A\vee \neg B}$ ${\displaystyle \neg \neg A}$ ${\displaystyle \neg \neg (A\wedge B))}$

${\displaystyle (\neg 1){\frac {A}{\neg \neg A}}}$

${\displaystyle (\neg 2){\frac {\neg \neg A}{A}}}$

Таблица закрыта.

Закрытие

Каждая таблица может рассматриваться как графическое представление формулы, эквивалентной набору, из которого она построена. Эта формула выглядит следующим образом: каждая ветвь таблицы представляет собой конъюнкцию ее формул; таблица представляет собой дизъюнкцию ее ветвей. Правила расширения преобразуют таблицу в таблицу, имеющую эквивалентную представленную формулу. Поскольку таблица инициализируется как одна ветвь, содержащая формулы входного набора, все последующие таблицы, полученные из нее, представляют формулы, которые эквивалентны этому набору (в варианте, где исходная таблица является единственным узлом, помеченным как true, формулы, представленные таблицами, являются следствиями исходного набора.)

Таблица для выполнимого множества {a⋀c,¬a⋁b}: все правила были применены к каждой формуле на каждой ветви, но таблица не закрыта (закрыта только левая ветвь), как и ожидалось для выполнимых множеств

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

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

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

Таблица с метками набора

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

Правила расширения таблицы теперь могут работать на листьях таблицы, игнорируя все внутренние узлы. Для конъюнкции правило основано на эквивалентности набора, содержащего конъюнкцию, с набором, содержащим и вместо него. В частности, если лист помечен как , к нему может быть добавлен узел с меткой : ${\displaystyle A\wedge B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle X\cup \{A\wedge B\}}$ ${\displaystyle X\cup \{A,B\}}$

${\displaystyle (\wedge ){\frac {X\cup \{A\wedge B\}}{X\cup \{A,B\}}}}$

Для дизъюнкции множество эквивалентно дизъюнкции двух множеств и . В результате, если первое множество помечает лист, к нему можно добавить два дочерних элемента, помеченных двумя последними формулами. ${\displaystyle X\cup \{A\vee B\}}$ ${\displaystyle X\cup \{A\}}$ ${\displaystyle X\cup \{B\}}$

${\displaystyle (\vee ){\frac {X\cup \{A\vee B\}}{X\cup \{A\}|X\cup \{B\}}}}$

Наконец, если множество содержит как литерал, так и его отрицание, эту ветвь можно закрыть:

${\displaystyle (id){\frac {X\cup \{p,\neg p\}}{closed}}}$

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

Ниже приведены две закрытые таблицы для набора

${\displaystyle X=\{r\wedge \neg r,\;p\wedge ((\neg p\vee q)\wedge \neg q)\}}$

Каждое применение правила отмечено справа. Оба достигают одинакового эффекта, первое закрывается быстрее. Единственное отличие — порядок, в котором выполняется сокращение.

${\displaystyle {\dfrac {\quad {\dfrac {\quad r\wedge \neg r,\;p\wedge ((\neg p\vee q)\wedge \neg q)\quad }{r,\;\neg r,\;p\wedge ((\neg p\vee q)\wedge \neg q)}}(\wedge )}{closed}}(\wedge )}$

и второй, более длинный, с правилами, применяемыми в другом порядке:

${\displaystyle {\dfrac {\quad {\dfrac {\quad {\dfrac {\quad r\wedge \neg r,\;p\wedge ((\neg p\vee q)\wedge \neg q)\quad }{r\wedge \neg r,\;p,\;((\neg p\vee q)\wedge \neg q)}}(\wedge )\quad }{r\wedge \neg r,\;p,\;(\neg p\vee q),\;\neg q}}(\wedge )}{\quad {\dfrac {\quad r\wedge \neg r,\;p,\;\neg p,\;\neg q\quad }{closed}}(id)\quad \quad {\dfrac {\quad r\wedge \neg r,\;p,\;q,\;\neg q\quad }{closed}}(id)}}(\vee )}$

Первая таблица закрывается после всего лишь одного применения правила, в то время как вторая не попадает в цель и закрывается гораздо дольше. Очевидно, что мы бы предпочли всегда находить самые короткие закрытые таблицы, но можно показать, что не может существовать один алгоритм, который находит самые короткие закрытые таблицы для всех входных наборов формул. ^{[ необходима цитата ]}

Приведенных выше трех правил достаточно , чтобы решить, является ли заданный набор формул в отрицательных нормальных формах совместно выполнимым: ${\displaystyle (\wedge )}$ ${\displaystyle (\vee )}$ ${\displaystyle (id)}$ ${\displaystyle X'}$

Просто применяйте все возможные правила во всех возможных порядках, пока не найдем закрытую таблицу для или пока не исчерпаем все возможности и не придем к выводу, что каждая таблица для открыта. ${\displaystyle X'}$ ${\displaystyle X'}$

В первом случае является совместно невыполнимым, а во втором случае листовой узел открытой ветви дает назначение атомарным формулам и отрицаемым атомарным формулам, что делает совместно выполнимым. Классическая логика на самом деле обладает довольно приятным свойством, которое нам нужно для полного исследования только (любой) одной таблицы: если она закрывается, то является невыполнимой, а если она открыта, то является выполнимой. Но это свойство, как правило, не используется другими логиками. ${\displaystyle X'}$ ${\displaystyle X'}$ ${\displaystyle X'}$ ${\displaystyle X'}$

Эти правила достаточны для всей классической логики, если взять начальный набор формул X и заменить каждый элемент C его логически эквивалентной отрицаемой нормальной формой C', что даст набор формул X' . Мы знаем, что X выполнимо тогда и только тогда, когда X' выполнимо, поэтому достаточно найти замкнутую таблицу для X', используя процедуру, описанную выше.

Задав, мы можем проверить, является ли формула А тавтологией классической логики: ${\displaystyle X=\{\neg A\}}$

Если таблица для замыкается, то невыполнима, и поэтому A является тавтологией, поскольку никакое присвоение значений истинности никогда не сделает A ложным. В противном случае любой открытый лист любой открытой ветви любой открытой таблицы для дает присвоение, которое фальсифицирует A. ${\displaystyle \{\neg A\}}$ ${\displaystyle \neg A}$ ${\displaystyle \{\neg A\}}$

Условный

Классическая пропозициональная логика обычно имеет связку для обозначения материальной импликации . Если мы запишем эту связку как ⇒, то формула A ⇒ B будет означать «если A, то B ». Можно дать правило таблицы для разбиения A ⇒ B на составляющие ее формулы. Аналогично, мы можем дать по одному правилу для разбиения каждой из ¬( A ∧ B ), ¬( A ∨ B ), ¬(¬ A ) и ¬( A ⇒ B ). Вместе эти правила дадут завершающую процедуру для решения вопроса, является ли заданный набор формул одновременно выполнимым в классической логике, поскольку каждое правило разбивает одну формулу на ее составляющие, но ни одно правило не строит более крупные формулы из более мелких составляющих. Таким образом, мы должны в конечном итоге достичь узла, который содержит только атомы и отрицания атомов. Если этот последний узел соответствует (id), то мы можем закрыть ветвь, в противном случае она остается открытой.

Но обратите внимание, что в классической логике справедливы следующие эквивалентности, где (...) = (...) означает, что левая формула логически эквивалентна правой формуле:

${\displaystyle {\begin{array}{lcl}\neg (A\land B)&=&\neg A\lor \neg B\\\neg (A\lor B)&=&\neg A\land \neg B\\\neg (\neg A)&=&A\\\neg (A\Rightarrow B)&=&A\land \neg B\\A\Rightarrow B&=&\neg A\lor B\\A\Leftrightarrow B&=&(A\land B)\lor (\neg A\land \neg B)\\\neg (A\Leftrightarrow B)&=&(A\land \neg B)\lor (\neg A\land B)\end{array}}}$

Если мы начнем с произвольной формулы C классической логики и применим эти эквивалентности многократно для замены левых частей на правые части в C , то мы получим формулу C' , которая логически эквивалентна C , но которая обладает тем свойством, что C' не содержит импликаций и ¬ появляется только перед атомарными формулами. Говорят, что такая формула находится в отрицательной нормальной форме , и можно формально доказать, что каждая формула C классической логики имеет логически эквивалентную формулу C' в отрицательной нормальной форме. То есть, C выполнима тогда и только тогда, когда C' выполнима.

Пропозициональная таблица с объединением

Вышеуказанные правила для пропозициональной таблицы можно упростить, используя единую нотацию. В единой нотации каждая формула имеет либо тип (альфа), либо тип (бета). Каждой формуле типа альфа назначаются два компонента , а каждой формуле типа бета назначаются два компонента . Формулы типа альфа можно рассматривать как конъюнктивные, поскольку обе и подразумеваются как истинные. Формулы типа бета можно рассматривать как дизъюнктивные, поскольку либо или подразумевается как истинные. В приведенных ниже таблицах показано, как определить тип и компоненты любой заданной пропозициональной формулы: ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \alpha _{1},\alpha _{2}}$ ${\displaystyle \beta _{1},\beta _{2}}$ ${\displaystyle \alpha _{1}}$ ${\displaystyle \alpha _{2}}$ ${\displaystyle \alpha }$ ${\displaystyle \beta _{1}}$ ${\displaystyle \beta _{2}}$ ${\displaystyle \beta }$

${\displaystyle {\begin{array}{c|c|c}\alpha &\alpha _{1}&\alpha _{2}\\\hline X\wedge Y&X&Y\\\neg (X\vee Y)&\neg X&\neg Y\\\neg (X\implies Y)&X&\neg Y\\\neg \neg X&X&X\\\end{array}}}$ ${\displaystyle {\begin{array}{c|c|c}\beta &\beta _{1}&\beta _{2}\\\hline \neg (X\wedge Y)&\neg X&\neg Y\\X\vee Y&X&Y\\X\implies Y&\neg X&Y\\\neg \neg X&X&X\\\end{array}}}$

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

${\displaystyle {\begin{array}{c|c|c}\alpha &\alpha _{1}&\alpha _{2}\\\hline T\,X\wedge Y&T\,\,X&T\,\,Y\\F\,\,X\vee Y&F\,\,X&F\,\,Y\\F\,\,X\implies Y&T\,\,X&F\,\,Y\\F\,\,\neg X&T\,\,X&T\,\,Y\\T\,\,\neg X&F\,\,X&F\,\,Y\end{array}}\qquad {\begin{array}{c|c|c}\beta &\beta _{1}&\beta _{2}\\\hline F\,\,X\wedge Y&F\,\,Y&F\,\,X\\T\,\,X\vee Y&T\,\,X&T\,\,Y\\T\,\,X\implies Y&F\,\,X&T\,\,Y\\F\,\,\neg X&T\,\,X&T\,\,X\\T\,\,\neg X&F\,\,X&F\,\,Y\end{array}}}$

При построении пропозициональной таблицы с использованием приведенной выше нотации, всякий раз, когда мы встречаем формулу типа альфа, ее два компонента добавляются к текущей ветви, которая расширяется. Всякий раз, когда мы встречаем формулу типа бета на некоторой ветви , мы можем разделить ее на две ветви, одну с набором { , } формул, а другую с набором { , } формул. ^[14] ${\displaystyle \alpha _{1},\alpha _{2}}$ ${\displaystyle \theta }$ ${\displaystyle \theta }$ ${\displaystyle \theta }$ ${\displaystyle \beta _{1}}$ ${\displaystyle \theta }$ ${\displaystyle \beta _{2}}$

Логическая таблица первого порядка

Таблицы расширены до логики предикатов первого порядка двумя правилами для работы с кванторами всеобщности и существования соответственно. Можно использовать два разных набора правил; оба используют форму скулемизации для работы с кванторами существования, но различаются в работе с кванторами всеобщности.

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

Таблица первого порядка без объединения

Формула первого порядка подразумевает все формулы, где есть основной член . Поэтому следующее правило вывода является верным: ${\displaystyle \forall x.\gamma (x)}$ ${\displaystyle \gamma (t)}$ ${\displaystyle t}$

${\displaystyle (\forall ){\frac {\forall x.\gamma (x)}{\gamma (t)}}}$где - произвольный основной термин ${\displaystyle t}$

В отличие от правил для пропозициональных связок, может потребоваться многократное применение этого правила к одной и той же формуле. Например, множество может быть доказано невыполнимым только в том случае, если оба и порождаются из . ${\displaystyle \{\neg P(a)\vee \neg P(b),\forall x.P(x)\}}$ ${\displaystyle P(a)}$ ${\displaystyle P(b)}$ ${\displaystyle \forall x.P(x)}$

Кванторы существования обрабатываются с помощью скулемизации. В частности, формула с ведущим квантором существования типа порождает свою скулемизацию , где — новый постоянный символ. ${\displaystyle \exists x.\delta (x)}$ ${\displaystyle \delta (c)}$ ${\displaystyle c}$

${\displaystyle (\exists ){\frac {\exists x.\delta (x)}{\delta (c)}}}$где новый постоянный символ ${\displaystyle c}$

Таблица без унификации для {∀xP(x), ∃x.(¬P(x)⋁¬P(f(x)))}. Для ясности формулы пронумерованы слева, а формула и правило, используемые на каждом шаге, справа

Член Сколема является константой (функцией арности 0), поскольку квантификация по не встречается в пределах действия какого-либо универсального квантификатора. Если исходная формула содержала некоторые универсальные квантификаторы, такие, что квантификация по была в пределах их действия, эти квантификаторы, очевидно, были удалены применением правила для универсальных квантификаторов. ${\displaystyle c}$ ${\displaystyle x}$ ${\displaystyle x}$

Правило для квантификаторов существования вводит новые константные символы. Эти символы могут использоваться правилом для квантификаторов всеобщности, так что может генерировать даже если не было в исходной формуле, но является константой Сколема, созданной правилом для квантификаторов существования. ${\displaystyle \forall y.\gamma (y)}$ ${\displaystyle \gamma (c)}$ ${\displaystyle c}$

Вышеуказанные два правила для кванторов всеобщности и существования верны, как и пропозициональные правила: если набор формул порождает закрытую таблицу, этот набор невыполним. Полнота также может быть доказана: если набор формул невыполним, то существует закрытая таблица, построенная из нее этими правилами. Однако, чтобы на самом деле найти такую ​​закрытую таблицу, требуется подходящая политика применения правил. В противном случае невыполнимый набор может породить бесконечно растущую таблицу. Например, набор невыполним, но закрытая таблица никогда не будет получена, если неразумно продолжать применять правило для кванторов всеобщности к , порождая, например , . Закрытую таблицу всегда можно найти, исключив эту и подобные «несправедливые» политики применения правил таблиц. ${\displaystyle \{\neg P(f(c)),\forall x.P(x)\}}$ ${\displaystyle \forall x.P(x)}$ ${\displaystyle P(c),P(f(c)),P(f(f(c))),\ldots }$

Правило для универсальных квантификаторов является единственным недетерминированным правилом, поскольку оно не указывает, с каким термином инстанцировать. Более того, в то время как другие правила должны применяться только один раз для каждой формулы и каждого пути, в котором находится формула, это правило может потребовать многократного применения. Применение этого правила, однако, можно ограничить, отложив применение правила до тех пор, пока не будет применимо никакое другое правило, и ограничив применение правила основными терминами, которые уже появляются в пути таблицы. Вариант таблиц с унификацией, показанный ниже, направлен на решение проблемы недетерминизма. ${\displaystyle (\forall )}$

Таблица первого порядка с объединением

Основная проблема таблицы без унификации заключается в том, как выбрать базовый термин для правила универсального квантификатора. Действительно, можно использовать любой возможный базовый термин, но очевидно, что большинство из них могут оказаться бесполезными для закрытия таблицы. ${\displaystyle t}$

Решение этой проблемы — «отложить» выбор термина до того момента, когда консеквент правила позволит закрыть хотя бы ветвь таблицы. Это можно сделать, используя переменную вместо термина, так что генерируется , а затем разрешить подстановки для последующей замены на термин. Правило для универсальных квантификаторов становится: ${\displaystyle \forall x.\gamma (x)}$ ${\displaystyle \gamma (x')}$ ${\displaystyle x'}$

${\displaystyle (\forall ){\frac {\forall x.\gamma (x)}{\gamma (x')}}}$где переменная, не встречающаяся больше нигде в таблице ${\displaystyle x'}$

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

Это правило использует переменную вместо основного термина. Это изменение дает то, что этим переменным можно присвоить значение, когда ветвь таблицы может быть закрыта, решая проблему генерации терминов, которые могут быть бесполезны.

Например, можно доказать невыполнимость, сначала сгенерировав ; отрицание этого литерала унифицируемо с , наиболее общим унификатором является подстановка, которая заменяет на ; применение этой подстановки приводит к замене на , что закрывает таблицу. ${\displaystyle \{\neg P(a),\forall x.P(x)\}}$ ${\displaystyle P(x_{1})}$ ${\displaystyle \neg P(a)}$ ${\displaystyle x_{1}}$ ${\displaystyle a}$ ${\displaystyle P(x_{1})}$ ${\displaystyle P(a)}$

Это правило закрывает по крайней мере ветвь таблицы — ту, которая содержит рассматриваемую пару литералов. Однако подстановка должна быть применена ко всей таблице, а не только к этим двум литералам. Это выражается в том, что свободные переменные таблицы являются жесткими : если вхождение переменной заменяется чем-то другим, все другие вхождения той же переменной должны быть заменены таким же образом. Формально свободные переменные (неявно) универсально квантифицированы, и все формулы таблицы находятся в области действия этих квантификаторов.

С кванторами существования работает скулемизация. В отличие от таблицы без унификации, термины Скулема могут не быть простыми константами. Действительно, формулы в таблице с унификацией могут содержать свободные переменные, которые неявно считаются универсально квантифицированными. В результате формула типа может находиться в области действия кванторов всеобщности; если это так, термин Скулема не является простой константой, а состоит из нового символа функции и свободных переменных формулы. ${\displaystyle \exists x.\delta (x)}$

${\displaystyle (\exists ){\frac {\exists x.\delta (x)}{\delta (f(x_{1},\ldots ,x_{n}))}}}$где — новый символ функции и свободные переменные ${\displaystyle f}$ ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle \delta }$

Таблица первого порядка с объединением для {∀xP(x), ∃x.(¬P(x)⋁¬P(f(x)))}. Для ясности формулы пронумерованы слева, а формула и правило, используемые на каждом шаге, справа

Это правило включает упрощение по сравнению с правилом, где свободные переменные ветви, а не только. Это правило может быть еще более упрощено путем повторного использования символа функции, если он уже использовался в формуле, которая идентична с точностью до переименования переменной. ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle \delta }$ ${\displaystyle \delta }$

Формула, представленная таблицей, получается способом, аналогичным пропозициональному случаю, с дополнительным предположением, что свободные переменные считаются универсально квантифицированными. Что касается пропозиционального случая, формулы в каждой ветви соединены, а результирующие формулы разъединены. Кроме того, все свободные переменные результирующей формулы универсально квантифицированы. Все эти квантификаторы имеют всю формулу в своей области действия. Другими словами, если — формула, полученная путем разъединения конъюнкции формул в каждой ветви, а — свободные переменные в ней, то — формула, представленная таблицей. Применяются следующие соображения: ${\displaystyle F}$ ${\displaystyle x_{1},\ldots ,x_{n}}$ ${\displaystyle \forall x_{1},\ldots ,x_{n}.F}$

• Предположение о том, что свободные переменные универсально квантифицированы, делает применение наиболее общего унификатора обоснованным правилом: поскольку означает, что верно для каждого возможного значения , то верно для термина , на который заменяется наиболее общий унификатор . ${\displaystyle \gamma (x')}$ ${\displaystyle \gamma }$ ${\displaystyle x'}$ ${\displaystyle \gamma (t)}$ ${\displaystyle t}$ ${\displaystyle x}$
• Свободные переменные в таблице являются жесткими: все вхождения одной и той же переменной должны быть заменены одним и тем же термином. Каждую переменную можно считать символом, представляющим термин, который еще предстоит определить. Это следствие того, что свободные переменные предполагаются универсально квантифицированными по всей формуле, представленной таблицей: если одна и та же переменная встречается свободной в двух разных узлах, оба вхождения находятся в области действия одного и того же квантификатора. Например, если формулы в двух узлах и , где является свободной в обоих, формула, представленная таблицей, имеет вид . Эта формула подразумевает, что верно для любого значения , но в общем случае не подразумевает для двух разных терминов и , поскольку эти два термина могут в общем случае принимать разные значения. Это означает, что нельзя заменить двумя разными терминами в и . ${\displaystyle A(x)}$ ${\displaystyle B(x)}$ ${\displaystyle x}$ ${\displaystyle \forall x.(...A(x)...B(x)...)}$ ${\displaystyle (...A(x)...B(x)...)}$ ${\displaystyle x}$ ${\displaystyle (...A(t)...A(t')...)}$ ${\displaystyle t}$ ${\displaystyle t'}$ ${\displaystyle x}$ ${\displaystyle A(x)}$ ${\displaystyle B(x)}$
• Свободные переменные в формуле для проверки на действительность также считаются универсально квантифицированными. Однако эти переменные нельзя оставлять свободными при построении таблицы, поскольку правила таблицы работают с обратной формулой, но по-прежнему рассматривают свободные переменные как универсально квантифицированные. Например, недействительно (это не верно в модели, где , и интерпретации, где ). Следовательно, выполнимо (оно удовлетворяется той же моделью и интерпретацией). Однако закрытая таблица может быть создана с помощью и , а замена на приведет к созданию замыкания. Правильная процедура заключается в том, чтобы сначала сделать универсальные квантификаторы явными, тем самым генерируя . ${\displaystyle P(x)\rightarrow P(c)}$ ${\displaystyle D=\{1,2\},P(1)=\bot ,P(2)=\top ,c=1}$ ${\displaystyle x=2}$ ${\displaystyle \{P(x),\neg P(c)\}}$ ${\displaystyle P(x)}$ ${\displaystyle \neg P(c)}$ ${\displaystyle x}$ ${\displaystyle c}$ ${\displaystyle \forall x.(P(x)\rightarrow P(c))}$

Следующие два варианта также верны.

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

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

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

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

Табличные исчисления и их свойства

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

Исчисление таблиц называется полным, если оно позволяет построить доказательство таблиц для любого заданного невыполнимого набора формул. Упомянутые выше исчисления таблиц могут быть доказаны как полные.

Замечательное различие между tableau с унификацией и двумя другими исчислениями заключается в том, что последние два исчисления изменяют tableau только путем добавления к нему новых узлов, тогда как первое позволяет производить замены для изменения существующей части tableau. В более общем смысле, tableau calculi классифицируются как деструктивные или недеструктивные в зависимости от того, добавляют ли они только новые узлы к tableau или нет. Tableau с унификацией, таким образом, является деструктивным, в то время как propositional tableau и tableau без унификации являются недеструктивными.

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

Процедуры проверки

Исчисление таблиц — это просто набор правил, который предписывает, как можно модифицировать таблицу. Процедура доказательства — это метод фактического нахождения доказательства (если оно существует). Другими словами, исчисление таблиц — это набор правил, в то время как процедура доказательства — это политика применения этих правил. Даже если исчисление является полным, не каждый возможный выбор применения правил приводит к доказательству невыполнимого множества. Например, является невыполнимым, но и таблицы с унификацией, и таблицы без унификации позволяют многократно применять правило для кванторов всеобщности к последней формуле, в то время как простое применение правила для дизъюнкции к третьей напрямую приведет к замыканию. ${\displaystyle \{P(f(c)),R(c),\neg P(f(c))\vee \neg R(c),\forall x.Q(x)\}}$

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

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

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

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

Поиск закрытой картины

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

Дерево поиска в пространстве таблиц для {∀xP(x), ¬P(c)⋁¬Q(c), ∃yQ(c)}. Для простоты формулы набора были опущены из всех таблиц на рисунке, и вместо них использован прямоугольник. Закрытая таблица находится в жирном поле; другие ветви все еще могут быть расширены.

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

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

Сокращение поиска

Размер дерева поиска зависит от количества (дочерних) таблиц, которые можно сгенерировать из данной (родительской). Уменьшение количества таких таблиц, таким образом, уменьшает требуемый поиск.

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

Различные методы сокращения поиска запрещают создание некоторых таблиц на том основании, что закрытая таблица все еще может быть найдена путем расширения других. Эти ограничения называются глобальными. В качестве примера глобального ограничения можно использовать правило, которое указывает, какая из открытых ветвей должна быть расширена. В результате, если таблица имеет, например, две незакрытые ветви, правило указывает, какая из них должна быть расширена, запрещая расширение второй. Это ограничение уменьшает пространство поиска, поскольку теперь запрещен один возможный выбор; однако полнота не страдает, поскольку вторая ветвь все равно будет расширена, если первая в конечном итоге будет закрыта. Например, таблица с корнем , потомком и двумя листьями и может быть закрыта двумя способами: сначала применена к , а затем к , или наоборот. Очевидно, что нет необходимости следовать обеим возможностям; можно рассмотреть только случай, в котором сначала применяется к , и проигнорировать случай, в котором он впервые применяется к . Это глобальное ограничение, поскольку пренебречь этим вторым расширением позволяет наличие другой таблицы, где расширение применяется к первому и последующим. ${\displaystyle \neg a\wedge \neg b}$ ${\displaystyle a\vee b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle (\wedge )}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle (\wedge )}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$

Пункт таблицы

При применении к наборам предложений (а не к произвольным формулам) методы таблиц позволяют добиться ряда улучшений эффективности. Предложение первого порядка — это формула , которая не содержит свободных переменных и каждая из которых является литералом. Квантификаторы всеобщности часто опускаются для ясности, так что, например, на самом деле означает . Обратите внимание, что, если воспринимать их буквально, эти две формулы не совпадают с формулой для выполнимости: скорее, выполнимость такая же, как у . То, что свободные переменные квантифицированы всеобщности, не является следствием определения выполнимости первого порядка; это скорее используется как неявное общее предположение при работе с предложениями. ${\displaystyle \forall x_{1},\ldots ,x_{n}L_{1}\vee \cdots \vee L_{m}}$ ${\displaystyle L_{i}}$ ${\displaystyle P(x,y)\vee Q(f(x))}$ ${\displaystyle \forall x,y.P(x,y)\vee Q(f(x))}$ ${\displaystyle P(x,y)\vee Q(f(x))}$ ${\displaystyle \exists x,y.P(x,y)\vee Q(f(x))}$

Единственными правилами расширения, применимыми к предложению, являются и ; эти два правила можно заменить их комбинацией без потери полноты. В частности, следующее правило соответствует последовательному применению правил и исчисления первого порядка с унификацией. ${\displaystyle (\forall )}$ ${\displaystyle (\vee )}$ ${\displaystyle (\forall )}$ ${\displaystyle (\vee )}$

${\displaystyle (C){\frac {L_{1}\vee \cdots \vee L_{n}}{L_{1}'|\cdots |L_{n}'}}}$где получается путем замены каждой переменной на новую в ${\displaystyle L_{1}'\vee \cdots \vee L_{n}'}$ ${\displaystyle L_{1}\vee \cdots \vee L_{n}}$

Когда набор, который нужно проверить на выполнимость, состоит только из предложений, этого и правил объединения достаточно, чтобы доказать невыполнимость. В других мирах tableau calculi, состоящий из и, является полным. ${\displaystyle (C)}$ ${\displaystyle (\sigma )}$

Поскольку правило расширения предложения генерирует только литералы и никогда новые предложения, предложения, к которым оно может быть применено, являются только предложениями входного набора. В результате правило расширения предложения может быть дополнительно ограничено случаем, когда предложение находится во входном наборе.

${\displaystyle (C){\frac {L_{1}\vee \cdots \vee L_{n}}{L_{1}'|\cdots |L_{n}'}}}$где получается путем замены каждой переменной на новую в , которая является предложением входного набора ${\displaystyle L_{1}'\vee \cdots \vee L_{n}'}$ ${\displaystyle L_{1}\vee \cdots \vee L_{n}}$

Поскольку это правило напрямую использует предложения во входном наборе, нет необходимости инициализировать таблицу в цепочке входных предложений. Поэтому начальная таблица может быть инициализирована с единственным узлом, помеченным ; эта метка часто опускается как неявная. В результате этого дальнейшего упрощения каждый узел таблицы (кроме корня) помечен литералом. ${\displaystyle true}$

Для clause tableau можно использовать ряд оптимизаций. Эти оптимизации направлены на сокращение числа возможных таблиц, которые необходимо исследовать при поиске закрытой таблицы, как описано в разделе «Поиск закрытой таблицы» выше.

Таблица соединений

Connection — это условие над tableau, запрещающее расширение ветви с использованием предложений, не связанных с литералами, которые уже находятся в ветви. Connection можно определить двумя способами:

сильная связанность

при расширении ветви используйте предложение ввода только в том случае, если оно содержит литерал, который можно объединить с отрицанием литерала в текущем листе

слабая связанность

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

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

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

Оба условия связности приводят к полному исчислению первого порядка: если набор предложений невыполним, он имеет замкнутую связанную (сильно или слабо) таблицу. Такая замкнутая таблица может быть найдена путем поиска в пространстве таблиц, как объяснено в разделе «Поиск замкнутой таблицы». Во время этого поиска связность исключает некоторые возможные варианты расширения, тем самым сокращая поиск. В других мирах, в то время как таблица в узле дерева может быть в общем случае расширена несколькими различными способами, связь может допускать только несколько из них, тем самым сокращая количество результирующих таблиц, которые необходимо дополнительно расширить.

Это можно увидеть на следующем (пропозициональном) примере. Таблица, состоящая из цепочки для набора предложений, может быть в общем расширена с использованием каждого из четырех входных предложений, но соединение допускает только расширение, использующее . Это означает, что дерево таблиц имеет четыре листа в общем, но только один, если наложена связность. Это означает, что связность оставляет только одну таблицу для попытки расширения вместо четырех для рассмотрения в целом. Несмотря на это сокращение выбора, теорема о полноте подразумевает, что замкнутая таблица может быть найдена, если набор невыполним. ${\displaystyle true-a}$ ${\displaystyle \{a,\neg a\vee b,\neg c\vee d,\neg b\}}$ ${\displaystyle \neg a\vee b}$

Условия связности, применяемые к пропозициональному (клаузальному) случаю, делают результирующее исчисление неконфлюэнтным. Например, является невыполнимым, но применение к порождает цепочку , которая не замкнута и к которой нельзя применить никакое другое правило расширения, не нарушив при этом ни сильную, ни слабую связность. В случае слабой связности слияние имеет место при условии, что предложение, используемое для расширения корня, имеет отношение к невыполнимости, то есть оно содержится в минимально невыполнимом подмножестве множества предложений. К сожалению, проблема проверки того, удовлетворяет ли предложение этому условию, сама по себе является сложной проблемой. Несмотря на неконфлюэнтность, закрытую таблицу можно найти с помощью поиска, как представлено в разделе «Поиск закрытой таблицы» выше. Хотя поиск необходим, связность сокращает возможные варианты расширения, тем самым делая поиск более эффективным. ${\displaystyle \{a,b,\neg b\}}$ ${\displaystyle (C)}$ ${\displaystyle a}$ ${\displaystyle true-a}$

Регулярные таблицы

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

Однако эти запрещенные шаги расширения бесполезны. Если — ветвь, содержащая литерал , и — предложение, расширение которого нарушает регулярность, то содержит . Чтобы закрыть таблицу, нужно расширить и закрыть, среди прочего, ветвь, где , где встречается дважды. Однако формулы в этой ветви точно такие же, как формулы одного. В результате те же шаги расширения, которые закрывают, также закрывают . Это означает, что расширение было ненужным; более того, если содержало другие литералы, его расширение порождало другие листья, которые нужно было закрыть. В пропозициональном случае расширение, необходимое для закрытия этих листьев, совершенно бесполезно; в случае первого порядка они могут повлиять только на остальную часть таблицы из-за некоторых унификации; однако их можно объединить с подстановками, используемыми для закрытия остальной части таблицы. ${\displaystyle B}$ ${\displaystyle L}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle L}$ ${\displaystyle B-L}$ ${\displaystyle L}$ ${\displaystyle B}$ ${\displaystyle B-L}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle C}$

Таблицы для модальной логики

В модальной логике модель включает в себя набор возможных миров , каждый из которых связан с оценкой истинности; отношение доступности определяет, когда мир доступен из другого мира. Модальная формула может определять не только условия над возможным миром, но и те, которые доступны из него. Например, истинно в мире, если истинно во всех мирах, которые доступны из него. ${\displaystyle \Box A}$ ${\displaystyle A}$

Что касается пропозициональной логики, таблицы для модальных логик основаны на рекурсивном разбиении формул на их основные компоненты. Однако расширение модальной формулы может потребовать установления условий над различными мирами. Например, если является истинным в мире, то существует мир, доступный из него, где является ложным. Однако нельзя просто добавить следующее правило к пропозициональным. ${\displaystyle \neg \Box A}$ ${\displaystyle A}$

${\displaystyle {\frac {\neg \Box A}{\neg A}}}$

В пропозициональных таблицах все формулы ссылаются на одну и ту же оценку истинности, но предварительное условие правила выше выполняется в одном мире, а следствие — в другом. Непринятие этого во внимание приведет к неверным результатам. Например, формула утверждает, что является истинным в текущем мире и ложным в мире, который доступен из нее. Простое применение и правила расширения выше даст и , но эти две формулы в общем случае не должны порождать противоречие, поскольку они выполняются в разных мирах. Модальные таблицы исчисления содержат правила типа приведенного выше, но включают механизмы, позволяющие избежать некорректного взаимодействия формул, ссылающихся на разные миры. ${\displaystyle a\wedge \neg \Box a}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle (\wedge )}$ ${\displaystyle a}$ ${\displaystyle \neg a}$

Технически, таблицы для модальной логики проверяют выполнимость набора формул: они проверяют, существует ли модель и мир, такие, что формулы в наборе истинны в этой модели и мире. В приведенном выше примере, в то время как утверждает истинность в , формула утверждает истинность в некотором мире , который доступен из и который в общем случае может отличаться от . Исчисления таблиц для модальной логики учитывают, что формулы могут ссылаться на разные миры. ${\displaystyle M}$ ${\displaystyle w}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle w}$ ${\displaystyle \neg \Box a}$ ${\displaystyle \neg a}$ ${\displaystyle w'}$ ${\displaystyle w}$ ${\displaystyle w}$

Этот факт имеет важное следствие: формулы, которые выполняются в мире, могут подразумевать условия для различных последователей этого мира. Невыполнимость затем может быть доказана из подмножества формул, ссылающихся на одного последователя. Это выполняется, если мир может иметь более одного последователя, что верно для большинства модальных логик. Если это так, то формула типа истинна, если существует последователь, где выполняется, и существует последователь, где выполняется. С другой стороны, если можно показать невыполнимость в произвольном последователе, формула доказывается невыполнимой без проверки миров, где выполняется. В то же время, если можно показать невыполнимость , нет необходимости проверять . В результате, хотя есть два возможных способа расширить , одного из этих двух способов всегда достаточно, чтобы доказать невыполнимость, если формула невыполнима. Например, можно расширить таблицу, рассмотрев произвольный мир, где выполняется. Если это расширение приводит к невыполнимости, то исходная формула невыполнима. Однако также возможно, что невыполнимость не может быть доказана таким образом, и что вместо этого следовало бы рассмотреть мир, в котором выполняется. В результате всегда можно доказать невыполнимость, расширив либо только , либо только ; однако, если сделан неправильный выбор, полученная таблица может оказаться незакрытой. Расширение любой из подформул приводит к исчислениям таблиц, которые являются полными, но не доказательство-конфлюэнтными. Поэтому может потребоваться поиск, описанный в разделе «Поиск закрытой таблицы». ${\displaystyle \neg \Box A\wedge \neg \Box B}$ ${\displaystyle \neg A}$ ${\displaystyle \neg B}$ ${\displaystyle \neg A}$ ${\displaystyle \neg B}$ ${\displaystyle \neg B}$ ${\displaystyle \neg A}$ ${\displaystyle \neg \Box A\wedge \neg \Box B}$ ${\displaystyle \neg A}$ ${\displaystyle \neg B}$ ${\displaystyle \neg \Box A}$ ${\displaystyle \neg \Box B}$

В зависимости от того, ссылаются ли предусловие и следствие правила расширения таблицы на один и тот же мир или нет, правило называется статическим или транзакционным. В то время как правила для пропозициональных связок являются статическими, не все правила для модальных связок являются транзакционными: например, в каждой модальной логике, включая аксиому T , она содержит в себе подразумеваемое в том же мире. В результате относительное (модальное) правило расширения таблицы является статическим, поскольку и его предусловие, и следствие ссылаются на один и тот же мир. ${\displaystyle \Box A}$ ${\displaystyle A}$

Формула-удаляющая таблица

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

Например, в S5 каждая формула , которая истинна в мире, также истинна во всех доступных мирах (то есть во всех доступных мирах истинны и ). Поэтому при применении , следствие которого выполняется в другом мире, удаляются все формулы из ветви, но можно сохранить все формулы , поскольку они выполняются и в новом мире. Чтобы сохранить полноту, удаленные формулы затем добавляются ко всем другим ветвям, которые все еще ссылаются на старый мир. ${\displaystyle \Box A}$ ${\displaystyle A}$ ${\displaystyle \Box A}$ ${\displaystyle {\frac {\neg \Box B}{\neg B}}}$ ${\displaystyle \Box A}$

Мировая маркировка tableau

Другой механизм обеспечения правильного взаимодействия между формулами, относящимися к разным мирам, заключается в переходе от формул к маркированным формулам: вместо того, чтобы писать , можно было бы написать , чтобы явно указать, что выполняется в мире . ${\displaystyle A}$ ${\displaystyle w:A}$ ${\displaystyle A}$ ${\displaystyle w}$

Все правила пропозиционального расширения адаптированы к этому варианту, утверждая, что все они ссылаются на формулы с одной и той же меткой мира. Например, генерирует два узла, помеченных и ; ветвь закрыта, только если она содержит два противоположных литерала одного и того же мира, как и ; замыкание не генерируется, если две метки мира различны, как в и . ${\displaystyle w:A\wedge B}$ ${\displaystyle w:A}$ ${\displaystyle w:B}$ ${\displaystyle w:a}$ ${\displaystyle w:\neg a}$ ${\displaystyle w:a}$ ${\displaystyle w':\neg a}$

Правило модального расширения может иметь следствие, которое относится к разным мирам. Например, правило для будет записано следующим образом ${\displaystyle \neg \Box A}$

${\displaystyle {\frac {w:\neg \Box A}{w':\neg A}}}$

Предпосылка и следствие этого правила относятся к мирам и , соответственно. Различные исчисления используют различные методы для отслеживания доступности миров, используемых в качестве меток. Некоторые включают псевдоформулы, например, для обозначения того, что доступен из . Некоторые другие используют последовательности целых чисел в качестве меток мира, эта нотация неявно представляет отношение доступности (например, доступен из .) ${\displaystyle w}$ ${\displaystyle w'}$ ${\displaystyle wRw'}$ ${\displaystyle w'}$ ${\displaystyle w}$ ${\displaystyle (1,4,2,3)}$ ${\displaystyle (1,4,2)}$

Таблицы маркировки набора

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

Таблицы для модальных логик используются для проверки выполнимости набора модальных формул в заданной модальной логике. При заданном наборе формул они проверяют существование модели и мира, таких что . ${\displaystyle S}$ ${\displaystyle M}$ ${\displaystyle w}$ ${\displaystyle M,w\models S}$

Правила расширения зависят от конкретной используемой модальной логики. Табличная система для базовой модальной логики K может быть получена путем добавления к пропозициональным табличным правилам следующего:

${\displaystyle (K){\frac {\Box A_{1};\ldots ;\Box A_{n};\neg \Box B}{A_{1};\ldots ;A_{n};\neg B}}}$

Интуитивно, предпосылка этого правила выражает истинность всех формул во всех доступных мирах, и истинность в некоторых доступных мирах. Следствием этого правила является формула, которая должна быть истинной в одном из тех миров, где истинно. ${\displaystyle A_{1},\ldots ,A_{n}}$ ${\displaystyle \neg B}$ ${\displaystyle \neg B}$

Более технически, методы модальных таблиц проверяют существование модели и мира , которые делают набор формул истинным. Если истинны в , должен быть мир , который доступен из и который делает истинным. Таким образом, это правило сводится к выводу набора формул, которые должны быть удовлетворены в таком . ${\displaystyle M}$ ${\displaystyle w}$ ${\displaystyle \Box A_{1};\ldots ;\Box A_{n};\neg \Box B}$ ${\displaystyle w}$ ${\displaystyle w'}$ ${\displaystyle w}$ ${\displaystyle A_{1};\ldots ;A_{n};\neg B}$ ${\displaystyle w'}$

В то время как предварительные условия предполагаются выполненными в , последствия предполагаются выполненными в : та же модель, но, возможно, разные миры. Таблицы с метками множеств явно не отслеживают мир, в котором каждая формула предполагается истинной: два узла могут ссылаться или не ссылаться на один и тот же мир. Однако формулы, помечающие любой заданный узел, предполагаются истинными в том же мире. ${\displaystyle \Box A_{1};\ldots ;\Box A_{n};\neg \Box B}$ ${\displaystyle M,w}$ ${\displaystyle A_{1};\ldots ;A_{n};\neg B}$ ${\displaystyle M,w'}$

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

Примечательно, что это не распространяется напрямую на множественные отрицательные формулы в рамке, такие как в : хотя существует доступный мир, в котором является ложным, и мир, в котором является ложным, эти два мира не обязательно являются одним и тем же. ${\displaystyle (K)}$ ${\displaystyle \Box A_{1};\ldots ;\Box A_{n};\neg \Box B_{1};\neg \Box B_{2}}$ ${\displaystyle B_{1}}$ ${\displaystyle B_{2}}$

В отличие от пропозициональных правил, устанавливает условия по всем своим предварительным условиям. Например, его нельзя применить к узлу, помеченному как ; хотя этот набор является несогласованным, и это можно легко доказать, применив , это правило нельзя применить из-за формулы , которая даже не имеет отношения к несогласованности. Удаление таких формул становится возможным благодаря правилу: ${\displaystyle (K)}$ ${\displaystyle a;\Box b;\Box (b\rightarrow c);\neg \Box c}$ ${\displaystyle (K)}$ ${\displaystyle a}$

${\displaystyle (\theta ){\frac {A_{1};\ldots ;A_{n};B_{1};\ldots ;B_{m}}{A_{1};\ldots ;A_{n}}}}$

Добавление этого правила (правила прореживания) делает результирующее исчисление неконфлюэнтным: таблицу для противоречивого набора может оказаться невозможно закрыть, даже если существует закрытая таблица для того же набора.

Правило недетерминировано: набор формул, которые нужно удалить (или сохранить), может быть выбран произвольно; это создает проблему выбора набора формул для отбрасывания, который не настолько велик, чтобы сделать результирующий набор выполнимым, и не настолько мал, чтобы сделать необходимые правила расширения неприменимыми. Наличие большого количества возможных вариантов усложняет задачу поиска закрытой таблицы. ${\displaystyle (\theta )}$

Этого недетерминизма можно избежать, ограничив использование так, чтобы оно применялось только перед правилом модального расширения и чтобы оно удаляло только формулы, которые делают это другое правило неприменимым. Это условие можно также сформулировать, объединив два правила в одно. Полученное правило дает тот же результат, что и старое, но неявно отбрасывает все формулы, которые делали старое правило неприменимым. Было доказано, что этот механизм удаления сохраняет полноту для многих модальных логик. ${\displaystyle (\theta )}$ ${\displaystyle (\theta )}$

Аксиома T выражает рефлексивность отношения доступности: каждый мир доступен из себя самого. Соответствующее правило расширения таблицы:

${\displaystyle (T){\frac {A_{1};\ldots ;A_{n};\Box B}{A_{1};\ldots ;A_{n};\Box B;B}}}$

Это правило связывает условия в одном и том же мире: если истинно в мире, то по рефлексивности также истинно в том же мире . Это правило статическое, а не транзакционное, поскольку и его предварительное условие, и его следствие относятся к одному и тому же миру. ${\displaystyle \Box B}$ ${\displaystyle B}$

Это правило копирует из предусловия в следствие, несмотря на то, что эта формула была «использована» для генерации . Это верно, поскольку рассматриваемый мир тот же самый, поэтому также выполняется там. Это «копирование» необходимо в некоторых случаях. Например, необходимо доказать несоответствие : единственные применимые правила находятся в порядке , из которого одно блокируется, если не копируется. ${\displaystyle \Box B}$ ${\displaystyle B}$ ${\displaystyle \Box B}$ ${\displaystyle \Box (a\wedge \neg \Box a)}$ ${\displaystyle (T),(\wedge ),(\theta ),(K)}$ ${\displaystyle \Box a}$

Вспомогательные таблицы

Другой метод работы с формулами, содержащимися в альтернативных мирах, заключается в том, чтобы начать отдельную таблицу для каждого нового мира, который вводится в таблицу. Например, подразумевает, что является ложным в доступном мире, поэтому начинается новая таблица, укорененная в . Эта новая таблица прикрепляется к узлу исходной таблицы, где было применено правило расширения; закрытие этой таблицы немедленно генерирует закрытие всех ветвей, где находится этот узел, независимо от того, связан ли тот же узел с другими вспомогательными таблицами. Правила расширения для вспомогательных таблиц такие же, как и для исходной; поэтому вспомогательная таблица может по очереди иметь другие (под)вспомогательные таблицы. ${\displaystyle \neg \Box A}$ ${\displaystyle A}$ ${\displaystyle \neg A}$

Глобальные предположения

Вышеуказанные модальные таблицы устанавливают согласованность набора формул и могут быть использованы для решения локальной логической проблемы следствия. Это проблема определения того, для каждой модели , если является истинным в мире , то является также истинным в том же мире. Это то же самое, что проверить, является ли истинным в мире модели, в предположении, что также является истинным в том же мире той же модели. ${\displaystyle M}$ ${\displaystyle A}$ ${\displaystyle w}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$

Связанная проблема — это проблема глобальных последствий, где предполагается, что формула (или набор формул) верна во всех возможных мирах модели. Проблема заключается в проверке того, является ли во всех моделях, где верно во всех мирах, также верным во всех мирах. ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle B}$

Локальное и глобальное предположение различаются в моделях, где предполагаемая формула истинна в некоторых мирах, но не в других. Например, влечет глобально, но не локально. Локальное следствие не выполняется в модели, состоящей из двух миров, делающих и истинными соответственно, и где второй доступен из первого; в первом мире предположения истинны, но ложны. Этот контрпример работает, потому что может быть предположен истинным в одном мире и ложным в другом. Однако, если то же самое предположение считается глобальным, не допускается ни в одном мире модели. ${\displaystyle \{P,\neg \Box (P\wedge Q)\}}$ ${\displaystyle \neg \Box Q}$ ${\displaystyle P}$ ${\displaystyle \neg P,Q}$ ${\displaystyle \neg \Box Q}$ ${\displaystyle P}$ ${\displaystyle \neg P}$

Эти две проблемы можно объединить, так что можно проверить, является ли локальным следствием при глобальном предположении . Tableaux calculi может иметь дело с глобальным предположением с помощью правила, разрешающего его добавление к каждому узлу, независимо от мира, к которому он относится. ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle G}$

Обозначения

Иногда используются следующие условные обозначения.

Единая нотация

При написании правил расширения таблиц формулы часто обозначаются с использованием соглашения, так что, например, всегда считается . В следующей таблице приведены обозначения для формул в пропозициональной, первопорядковой и модальной логике. ${\displaystyle \alpha }$ ${\displaystyle \alpha _{1}\wedge \alpha _{2}}$

Каждая метка в первом столбце считается любой из формул в других столбцах. Формула с надчеркиванием, например, указывает, что является отрицанием любой формулы, которая появляется на ее месте, так что, например, в формуле подформула является отрицанием . ${\displaystyle {\overline {\alpha _{1}}}}$ ${\displaystyle \alpha _{1}}$ ${\displaystyle \neg (a\vee b)}$ ${\displaystyle \alpha _{1}}$ ${\displaystyle a}$

Поскольку каждая метка указывает на множество эквивалентных формул, эта нотация позволяет записать одно правило для всех этих эквивалентных формул. Например, правило расширения конъюнкции формулируется как:

${\displaystyle (\alpha ){\frac {\alpha }{\begin{array}{c}\alpha _{1}\\\alpha _{2}\end{array}}}}$

Формулы с подписью

Формула в таблице предполагается истинной. Знаковые таблицы позволяют утверждать, что формула ложна. Обычно это достигается путем добавления метки к каждой формуле, где метка T указывает на формулы, предполагаемые истинными, а F — на формулы, предполагаемые ложными. Другая, но эквивалентная запись заключается в том, чтобы записывать формулы, предполагаемые истинными, слева от узла, а формулы, предполагаемые ложными, справа.

Смотрите также

• Разрешение (логика)

Примечания

1. Хаусон, Колин (1997). Логика с деревьями: введение в символическую логику . Лондон; Нью-Йорк: Routledge. стр. ix, x, 24–29, 47. ISBN 978-0-415-13342-5.
2. Restall, Greg (2006). Логика: введение. Основы философии. Лондон; Нью-Йорк: Routledge. С. 5, 42, 55. ISBN 978-0-415-40067-1. OCLC  63115330.
3. Хаусон 2005, стр. 27.
4. Гирл 2014.
5. Энциклопедия философии 2023.
6. Бет 1955.
7. Смаллиан 1995.
8. Карниелли 1987.
9. Карниелли 1991.
10. Платон, Ян фон (2013). Элементы логического рассуждения (1-е изд.). Кембридж: Cambridge University Press. стр. 9. ISBN 978-1-107-03659-8.
11. Weisstein, Eric W. "Connective". mathworld.wolfram.com . Получено 2024-03-22 .
12. Вариант этого начального шага — начать с дерева с одним узлом, корень которого помечен . В этом втором случае процедура всегда может скопировать формулу в наборе под листом. В качестве рабочего примера показана таблица для набора. ${\displaystyle \top }$ ${\displaystyle \{(a\vee \neg b)\wedge b,\neg a\}}$
13. Применимый узел — это узел, самая внешняя связность которого соответствует правилу расширения и который еще не был применен ни к одному предыдущему узлу на ветви выбранного конечного узла.
14. Смаллиан 2014, стр. 88–89.

Ссылки

• Бет, Эверт В. (1955). «Семантическая следствие и формальная выводимость». Mededelingen van de Koninklijke Nederlandse Akademie van Wetenschappen, Afdeling Letterkunde . 18 (13): 309–42.Перепечатано в Intikka, Jaakko, ed. (1969). Философия математики . Oxford University Press. ISBN 978-0-19-875011-6.
• Босток, Дэвид (1997). Промежуточный курс логики. Oxford University Press. ISBN 978-0-19-156707-0.
• Карниелли, Уолтер А. (1987). «Систематизация конечных многозначных логик с помощью метода таблиц». Журнал символической логики . 52 (2): 473–493. doi :10.2307/2274395. JSTOR  2274395. S2CID  42822367.
• Карниелли, Уолтер А. (1991). "О секвенциях и таблицах для многозначных логик" (PDF) . Журнал неклассической логики . 8 (1): 59–76. Архивировано из оригинала (PDF) 2016-03-05 . Получено 2014-10-11 .
• D'Agostino, M.; Gabbay, D .; Haehnle, R.; Posegga, J., ред. (1999). Справочник по методам Tableau. Kluwer. ISBN 978-94-017-1754-0.
• Фитинг, Мелвин (1996) [1990]. Логика первого порядка и автоматическое доказательство теорем (2-е изд.). Нью-Йорк: Springer. doi :10.1007/978-1-4612-2360-3. ISBN 978-1-4612-7515-2. S2CID  10411039.
• Girle, Rod (2014). Модальная логика и философия (2-е изд.). Taylor & Francis. ISBN 978-1-317-49217-7.
• Горе, Раджив. «Методы таблиц для модальной и временной логики». Справочник по методам таблиц . С. 297–396.
• Hähnle, Reiner (2001). "3. Таблицы и связанные с ними методы". В Robinson, Alan JA; Voronkov, Andrei (ред.). Handbook of Automated Reasoning . Elsevier. стр. 101–179. ISBN 978-0-08-053279-0.
• Howson, Colin (11 октября 2005 г.) [1997]. Логика с деревьями: введение в символическую логику. Routledge. ISBN 978-1-134-78550-6.
• Джеффри, Ричард (2006) [1967]. Формальная логика: ее область применения и пределы (4-е изд.). Hackett. ISBN 978-0-87220-813-1.
• Летц, Рейнхольд; Стенц, Гернот. «28. Процедуры исключения моделей и соединения таблиц». Справочник по автоматизированному рассуждению . С. 2015–2114.
• Смаллиан, Рэймонд (1995) [1968]. Логика первого порядка. Дувр. ISBN 978-0-486-68370-6.
• Смаллиан, Рэймонд (2014). Руководство для начинающих по математической логике . Дувр. ISBN 978-0486492377.
• Энциклопедия философии, ред. (11 декабря 2023 г.). "Современная логика: Булев период: Кэрролл". Энциклопедия философии . Получено 26 декабря 2023 г. .
• Zeman, Joseph Jay (1973). Модальная логика: Льюисовские модальные системы. Clarendon Press. ISBN 978-0-19-824374-8. OCLC  641504.

Внешние ссылки

• TABLEAUX: ежегодная международная конференция по автоматизированным рассуждениям с использованием аналитических таблиц и связанных с ними методов
• JAR: Журнал автоматизированного мышления
• Пакет таблиц: интерактивный доказатель для пропозициональной и первопорядковой логики с использованием таблиц
• Генератор доказательств на основе дерева: еще один интерактивный доказатель для пропозициональной и первопорядковой логики с использованием таблиц
• LoTREC: универсальный доказательный модуль на основе таблиц для модальной логики от IRIT/Университета Тулузы
• Введение в Truth Trees на YouTube