Редактирование: Семантическая таблица
Перейти к навигации
Перейти к поиску
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий ниже, чтобы убедиться, что это нужная вам правка, и запишите страницу ниже, чтобы отменить правку.
Текущая версия | Ваш текст | ||
Строка 13: | Строка 13: | ||
==Пропозициональная логика== | ==Пропозициональная логика== | ||
В этом разделе представлено исчисление таблиц для классической логики высказываний. Таблица проверяет, является ли данный набор формул выполнимым или нет. Его можно использовать для проверки правильности или следствия: формула действительна, если ее отрицание неосуществимо, а Формулы A 1 , … , A n ldots, A_{n}подразумевают | В этом разделе представлено исчисление таблиц для классической логики высказываний. Таблица проверяет, является ли данный набор формул выполнимым или нет. Его можно использовать для проверки правильности или следствия: формула действительна, если ее отрицание неосуществимо, а Формулы A 1 , … , A n ldots, A_{n}подразумевают B Б { A 1 , … , A n , ¬ B } , что она неосуществима. | ||
Основной принцип пропозициональных таблиц состоит в попытке "разбить" сложные формулы на более мелкие до тех пор, пока не будут получены комплементарные пары литералов или дальнейшее расширение невозможно. | Основной принцип пропозициональных таблиц состоит в попытке "разбить" сложные формулы на более мелкие до тех пор, пока не будут получены комплементарные пары литералов или дальнейшее расширение невозможно. | ||
Метод работает на дереве, узлы которого помечены формулами. На каждом шаге это дерево изменяется; в пропозициональном случае единственными разрешенными изменениями являются добавления узла как потомка листа. Процедура начинается с генерации дерева, состоящего из цепочки всех формул в наборе, чтобы доказать неудовлетворительность. Вариант к этому стартовому шагу должен начаться с дерева единственного узла, корень которого помечен ⊤ \верхний ; в этом втором случае процедура может всегда копировать формулу в наборе ниже листа. В качестве примера выполнения показана таблица для набора { ( a ∨ ¬ b ) ∧ b , ¬ a } | |||
Метод работает на дереве, узлы которого помечены формулами. На каждом шаге это дерево изменяется; в пропозициональном случае единственными разрешенными изменениями являются добавления узла как потомка листа. Процедура начинается с генерации дерева, состоящего из цепочки всех формул в наборе, чтобы доказать неудовлетворительность. Вариант к этому стартовому шагу должен начаться с дерева единственного узла, корень которого помечен ⊤ \верхний ; в этом втором случае процедура может всегда копировать формулу в наборе ниже листа. В качестве примера выполнения показана таблица для набора { | |||
Принцип таблицы заключается в том, что формулы в узлах одной ветви рассматриваются совместно, а различные ветви считаются дизъюнктивными. В результате таблица является древовидным представлением формулы, которая является дизъюнкцией соединений. Эта формула эквивалентна множеству, чтобы доказать неудовлетворительность. Процедура изменяет таблицу таким образом, что формула, представленная результирующей таблицей, эквивалентна исходной. Одно из этих соединений может содержать пару комплементарных литералов, и в этом случае это соединение оказывается неудовлетворительным. Если все соединения оказываются неосуществимыми, то исходный набор формул неосуществим. | Принцип таблицы заключается в том, что формулы в узлах одной ветви рассматриваются совместно, а различные ветви считаются дизъюнктивными. В результате таблица является древовидным представлением формулы, которая является дизъюнкцией соединений. Эта формула эквивалентна множеству, чтобы доказать неудовлетворительность. Процедура изменяет таблицу таким образом, что формула, представленная результирующей таблицей, эквивалентна исходной. Одно из этих соединений может содержать пару комплементарных литералов, и в этом случае это соединение оказывается неудовлетворительным. Если все соединения оказываются неосуществимыми, то исходный набор формул неосуществим. |