Метод аналитических таблиц
Метод аналитических таблиц
§3. Метод аналитических таблиц
3.1. Общее описание аналитических таблиц
В предыдущем параграфе были введены понятия закона классической логики предикатов и логического следования. Таким образом, были даны ответы на важнейшие для каждой логической теории вопросы: что является законом этой теории и что представляет собой отношение логического следования в ней.
Однако с практической точки зрения не менее важно получить ответ на другие вопросы: каким образом, с помощью какой процедуры можно показать, что некоторая формула А действительно является законом данной логической теории и что из формул А1, А2. Аn в этой теории действительно следует формула В.
Так, в классической логике высказываний (в том виде, как эта теория построена в главе III) для этой цели использовалась процедура построения таблиц истинности. Если формула А принимает значение «истина» во всех строках данной таблицы, то она относится к числу логических законов этой теории. Для ответа же на вопрос, следует ли формула В из формул А1, А2. Аn в классической логике высказываний, необходимо, согласно определению логического следования, построить совместную таблицу истинности для формул А1, А2. Аn и В и установить, имеется ли в данной таблице строка, в которой А1, А2. Аn принимают значение «истина», а В – значение «ложь».
Процесс построения таблиц истинности является алгоритмическим и осуществляется в конечное число шагов. Как было показано в предыдущей главе это и означает, что классическая логика высказываний является разрешимой теорией. Иначе обстоит дело с классической логикой предикатов. Определения закона этой теорий и логического следования в ней не являются эффективными, т. е. не содержат алгоритма решения вопросов об общезначимости произвольной формулы А и о наличии отношения следования между произвольными формулами А1, А2. Аn и В.
Действительно, для того чтобы установить общезначимость формулы А, в соответствии с определением общезначимой формулы, необходимо рассмотреть все реализации и убедиться, что в каждом случае эта формула принимает значение «истина». Для того чтобы показать, что А1, А2. Аn ⊨ В, согласно определению логического следования, нужно рассмотреть все реализации и возможные распределения значений предметных переменных и удостовериться, что среди них нет таких, когда А1, А2. Аn принимали бы значение «истина», а В – значение «ложь». Однако подобный перебор всех реализаций ℑ и приписываний φ невозможен в силу того, что их число бесконечно (в отличие от числа строк любой таблицы истинности).
Более того, никакого алгоритма решения вопросов об общезначимости формул языка логики предикатов и наличия между ними отношения логического следования не существует в принципе, т. е. классическая логика предикатов неразрешима (см. главу XII). Таким образом, решения указанных вопросов представляют собой творческую задачу.
Вместе с тем в современной логике разработан ряд методов, позволяющих упростить, сделать стандартной и, насколько это возможно, эффективной процедуру обоснования общезначимости формул и наличия следования между формулами языка логики предикатов. Один из них, получивший название метода аналитических таблиц, будет рассмотрен в данном параграфе.
Идея указанного метода состоит в том, что тезис об общезначимости формулы А или тезис о следовании формулы В из A1, A2. An обосновываются посредством рассуждения от противного. Так, для обоснования тезиса «⊨ А» («формула А истинна в каждой реализации ℑ = при каждом приписывании φ») показывают, что допущение ложности формулы А с необходимостью приводит к противоречию. Для обоснования тезиса «А1, А2. Аn ⊨ В» («не существует реализации ℑ и приписывания φ, при которых А1, А2. Аn истинны, а В ложна») демонстрируют, что допущение истинности А1, А2. Аn и ложности В необходимо ведет к противоречию.
Рассуждение от противного, обосновывающее какой-либо из указанных тезисов, оформляется в виде некоторой последовательности шагов, которые и образуют аналитическую таблицу.
Как и в случае вывода, аналитическая таблица будет строится сверху вниз. Однако, во-первых, в отличие от вывода, аналитическая таблица будет состоять не из самих формул, а из так называемых отмеченных формул. Под отмеченной формулой имеют в виду формулы, к которым добавлены символы t или f. Написание tA означает, что формула А оценивается как истинная, а написание fА означает, что формула А оценивается как ложная. Во-вторых, аналитическая таблица будет не одномерной (линейно упорядоченной) последовательностью отмеченных формул, а двумерной (плоскостной) конфигурацией таких формул. Последнее обусловлено тем, что аналитическая таблица представляет собой дерево отмеченных формул (о понятии «дерево» см. главу II).
В этом упорядоченном множестве будем выделять цепи отмеченных формул (см. в главе II). Под цепью аналитической таблицы будем понимать последовательность без пропусков вхождений отмеченных формул, начинающуюся с самой верхней формулы таблицы (корня дерева) до одной из самых нижних формул. Место расщепления некоторой цепи таблицы на две самостоятельные цепи (подцепи), в силу чего и возникает двумерная древесная конфигурация аналитической таблицы, будем помечать горизонтальной и вертикальной линиями. Последняя линия как раз и будет разделять две самостоятельные цепи.
Таблица, соответствующая первому шагу рассуждения от противного, содержит одну (начальную) цепь отмеченных формул и выражает исходное допущение данного рассуждения, т. е. антитезис. Если тезисом является «⊨ А», то эта цепь начинается с отмеченной формулы – fА, выражающей допущение о ложности А. Эта формула и есть корень дерева. Если же тезисом является
«A1, A2. An ⊨ В», то начальная цепь начинается с отмеченных формул
tA1, tA2. tAn, fB, что выражает допущение об истинности A1, A2. An и ложности В. Корнем дерева в этом случае является отмеченная формула tA1.
Дальнейшие шаги по построению аналитической таблицы осуществляются с помощью точных правил, которые называются правилами редукции. Эти правила всегда применяются к отмеченным формулам, находящимся в некоторой цепи таблицы, и могут привести либо к продолжению построения данной цепи, либо к ее расщеплению на две самостоятельные цепи. В основе правил редукции лежат логические смыслы пропозициональных связок &, ∨, ⊃, ¬ и кванторов ∀, ∃. Данные правила выражают, по существу, условия истинности и ложности формул вида (А & В),
(A ∨ В), (А ⊃ В), ¬A, ∀αA, ∃αА, указывая некоторым новым способом на те следствия, которые могут быть получены из факта истинности или ложности формул приведенных типов.
Цель рассуждения от противного – показать, что исходное допущение (антитезис) с необходимостью приводит к противоречию. Поэтому задача, которая решается построением аналитической таблицы, состоит в получении такой таблицы, каждая цепь которой содержит некоторую формулу С, отмеченную как знаком t, так и знаком f, т. е. содержит одновременно утверждение, как об истинности, так и ложности С, что и означает получение противоречия. При получении этого результата тезис об общезначимости формулы А или же о следовании В из A1, A2. An считается обоснованным.
Применение метода аналитических таблиц будет ограничено замкнутыми формулами. Это условие никоим образом не ограничивает возможность обоснования логической истинности высказываний естественного языка и демонстрации правильности умозаключений. Действительно, посылками и заключениями в умозаключениях являются высказывания, а логические формы высказываний в языке логики предикатов фиксируются посредством именно замкнутых формул.
3.2. Правила редукции
Правило t&. Предположим, что в некоторой цепи содержится отмеченная формула t(A & В). Она выражает утверждение об истинности формулы А & В. Как известно, формула А & В истинна тогда и только тогда, когда истинными являются ее подформулы А и В. Поэтому в эту же цепь можно поместить (обязательно одну под другой) две отмеченные формулы – tA и tB. Сокращенная формулировка данного правила выглядит следующим образом:
Правило f&. Пусть в некоторой цепи содержится отмеченная формула вида f(A & В). Она выражает утверждение о ложности А & В. Напомним, что конъюнктивная формула ложна, если и только если А принимает значение «ложь» или В принимает значение «ложь». Иначе говоря, в случае ложности А & В имеем две возможности:
случай, когда ложно А, случай, когда ложно В.
Поэтому исходная цепь расщепляется на две самостоятельные цепи, в одну из которых помещается fА, а в другую – fB:
Отметим, что новые цепи содержат все отмеченные формулы той цепи, в которой находилась формула f(A & В), и различаются только тем, что в левую цепь теперь входит отмеченная формула fA, а в правую – отмеченная формула fB. То же самое происходит и при применении других правил редукции, которые ведут к расщеплению цепей, а потому данное свойство в дальнейшем описании оговариваться не будет.
Правило t∨. Наличие формулы t(A ∨ В) в некоторой цепи означает утверждение об истинности A ∨ В. Данная формула истинна, если и только если А принимает значение «истина» или В принимает значение «истина». Поэтому исходная цепь отмеченных формул расщепляется на две самостоятельные цепи, в одну из которых помещается tA, а в другую – tB. Иначе говоря, в случае истинности A ∨ В имеем две возможности:
1) случай, когда истинно А,
2) случай, когда истинно В.
Правило f∨. Наличие формулы f(A ∨ В) в некоторой цепи означает утверждение о ложности A ∨ В. Данная формула ложна, если и только если как А, так и В принимают значение «ложь». Поэтому в эту же цепь помещаем (обязательно одну под другой) отмеченные формулы fA и fB.
Правило t⊃. Предположим, что в некоторой цепи содержится отмеченная формулу: t(A ⊃ В). Формула A ⊃ В истинна, если и только если имеет место по крайней мере один из двух случаев:
А принимает значение «ложь», В принимает значение «истина».
Поэтому исходная цепь отмеченных формул расщепляется на две подцепи, в одну из которых помещается fA, а в другую – tB.
Правило f⊃. Пусть некоторая цепь включает отмеченную формулу f(A ⊃ В),
т. е. содержит утверждение о ложности A ⊃ В. Эта формула принимает значение «ложь», если и только если А истинно, а В – ложно. Поэтому в эту же цепь помещаем (обязательно одну под другой) отмеченные формулы tA и fB.
Правило t¬. Наличие отмеченной формулы t¬A в некоторой цепи означает утверждение об истинности ¬A. Поскольку истинность ¬A равносильна ложности A, в эту же цепь помещается отмеченная формула fА:
Правило f¬. Наличие в некоторой цепи отмеченной формулы f¬A означает утверждение о ложности ¬A. Поскольку ложность ¬A равносильна истинности A, в эту же цепь помещается отмеченная формула tA:
Правило t∀. Предположим, что в некоторой цепи имеется отмеченная формула вида t∀αA. Это означает утверждение об истинности ∀αA. В соответствии с логическим смыслом квантора общности, формула ∀αA истинна, если и только если любой индивид предметной области удовлетворяет условию А. Поэтому в случае истинности ∀αA истинной оказывается также любая формула вида A(k), которая является результатом подстановки вместо всех свободных вхождений α в А произвольного замкнутого терма k. Но так как в языке логики предикатов таких термов бесконечно много, список подставляемых термов ограничивается следующим условием – в качестве k можно брать содержащийся уже в отмеченных формулах данной цепи замкнутый терм, а если таковых нет в цепи, то любую индивидную константу.
Все правила редукции, рассмотренные до сих пор, применяются при построении аналитической таблицы локально, т. е. один раз в некотором конкретном месте. Правило же редукции t∀ является не локальным, а глобальным. Это означает, что оно может применяться неоднократно для того, чтобы повторным применением получать утверждения об истинности A(k1), A(k2),… для замкнутых термов уже содержащихся в таблице и отличных от терма k. Итак, с учетом указанных выше обстоятельств, правило t∀ формулируется следующим образом:
где A(k) – результат подстановки вместо всех свободных вхождений переменной α в формуле А замкнутого терма k.
Правило f∀. Пусть в некоторой цепи имеется отмеченная формула f∀αA. Это означает утверждение о ложности ∀αA. Ложность формулы ∀aA означает существование объекта, не удовлетворяющего условию А. Введем в качестве имени этого объекта новую, не встречающуюся в отмеченных формулах цепи, предметную константу k. Ясно, что поскольку k не удовлетворяет условию А, формула A(k) оказывается ложной. Поэтому в эту же цепь помещаем отмеченную формулу fA(k).
Смысл того ограничения, что константа k должна быть новой, состоит в следующем. Если k входит в отмеченные формулы цепи, то не исключается возможность, что эти формулы содержат информацию об истинности A(k). Тогда делать вывод, что именно объект k не удовлетворяет условию А, было бы некорректно. Итак, с учетом указанных выше обстоятельств, формулировка правила f∀ имеет следующий вид:
где A(k) – результат подстановки вместо всех свободных вхождений переменной α в формуле А предметной константы k, которая не содержится в данной цепи.
Правило t∃. Пусть в какой-то цепи содержится отмеченная формула t∃αA,
т. е. содержится утверждение об истинности ∃αA. Согласно смыслу квантора ∃, истинность ∃αA означает существование объекта, удовлетворяющего условию А. В качестве имени этого объекта вводится новая, не встречающаяся в отмеченных формулах цепи, предметная константа k. Ясно, что A(k) истинно в силу того, что k удовлетворяет условию А.
где A(k) – результат подстановки вместо всех свободных вхождений переменной α в формуле А предметной константы k, которая не содержится в данной цепи.
Правило f∃. Предположим, что в некоторой цепи содержится отмеченная формула f∃αA. Это говорит о ложности ∃αA. Ложность формулы ∃αA означает, что любой индивид предметной области не удовлетворяет условию А. Поэтому эта же цепь пополняется отмеченной формулой вида fA(k), где k удовлетворяет тем же самым условиям, которые были сформулированы для правила t∀. Таким образом, правило редукции f∃ тоже является глобальным.
где A(k) – результат подстановки вместо всех свободных вхождений переменной α в формуле А замкнутого терма k.
Понятие аналитической таблицы.
Аналитической таблицей называется конечное или бесконечное древесно упорядоченное множество отмеченных формул (дерево отмеченных формул), получаемое из начальной цепи применением правил редукции.
Понятие замкнутой цепи аналитической таблицы.
Цепь называется замкнутой, если в ее составе встречается две отмеченные формулы – tC и fС.
Понятие замкнутой аналитической таблицы.
Аналитическая таблица называется замкнутой, если каждая ее цепь является замкнутой.
Сформулируем, наконец, критерии общезначимости формул и логического следования.
Формула А общезначима (⊨ А), если и только если существует замкнутая аналитическая таблица, начальная цепь которой начинается с отмеченной формулы fA.
Из A1, A2. An логически следует формула В (A1, A2. An ⊨ В), если и только если существует замкнутая аналитическая таблица, начальная цепь которой начинается с отмеченных формул tA1, tA2. tAn и fB.
Описание аналитико-табличной процедуры завершено.
3.3. Примеры использования аналитических таблиц
Прежде чем привести примеры построения аналитических таблиц, дадим ряд советов, облегчающих процесс обоснования указанным методом общезначимости формул и наличия между формулами отношения логического следования.
1. Правила редукции можно разделить на две группы. К первой относятся так называемые пропозициональные правила – t&, f∨, f⊃, t¬, f¬, f&, t∨, t⊃. Ко второй группе относятся так называемые кванторные правила. При построении аналитической таблицы следует (при наличии соответствующей возможности) применять сначала пропозициональные правила, не ведущие к расщеплению цепей, а затем кванторные правила редукции.
2. Среди пропозициональных правил редукции к числу правил, не ведущих к расщеплению цепей, относятся правила t&, f∨, f⊃, t¬ и f¬. Правила же ведущие к расщеплению цепей – это правила f&, t∨, t⊃. Аналитическая таблица будет менее громоздкой, если пропозициональные правила второго типа применять в самую последнюю очередь после того, как применены все возможные пропозициональные правила первого типа и кванторные правила.
3. Среди кванторных правил редукции рекомендуется в первую очередь применять правила f∀ и t∃, которые требуют введения новых предметных констант, и только потом правила t∀ и f∃, не содержащие ограничений на терм k, подставляемый вместо подкванторной переменной.
И еще одно важное замечание. Правила редукции всегда применяются к тем логическим константам, содержащимся в формуле А, идущей после отметки t или f, которые являются в ней главными знаками.
Продемонстрируем сначала, каким образом применяются пропозициональные правила редукции. Обоснуем с использованием метода аналитических таблиц тезис:
Р(а) ∨ Q(b), Q(b) ⊃ R(c) ⊨ R(c) ∨ P(a).
Начальная цепь таблицы содержит тогда следующие отмеченные формулы:
Источник
