Тема 8. Элементы символической логики

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

Логика высказываний, или исчисление высказываний – раз-дел математической логики, изучающий логические операции с простыми высказываниями, которые объединяются в сложные высказывания с помощью пропозициональных связок, сходных с принятыми в обычной речи союзами: «и» (в математической логике представлен символом &), «или» (v), «если…, то…» (→), «если … и только если…», «тогда и только тогда, когда» (↔), а также с отрицанием, обозначаемым частицей «не» (~). Исчисление – такая система изучения тех или иных областей объективного мира, в которой предметам какой-либо определённой области ставятся в соответствие материальные знаки (цифры, буквы и др.), с которыми затем по принятым в системе точным правилам производятся операции, необходимые для решения поставленной цели.

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

Особенность исчисления высказываний состоит в том, что в нём не рассматривается логическая структура простых высказываний, т. е. связь между субъектом и предикатом, как это имеет место в суждении.

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

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

Каждая формула логики высказываний может быть или тождественно-истинной, или тождественно–ложной, или нейтральной. Тождественно-истинные высказывания – это высказывание, которое при любых значениях простых суждений, входящих в его состав, имеет значение «истина». Такие высказывания называют также тавтологиями, а формулы, которые им соответствуют, тождественно-истинными формулами или законами логики. Существуют также тождественно-ложные формулы или противоречия, которые принимают только значение «ложь». Тождественно-истинные и нейтральные формулы являются выполнимыми формулами. Выполнимая формула – формула логики высказываний, получающая значение «истина» хотя бы для одного набора логических значений своих переменных.

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

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

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

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

Например, формула (((pv~q)&r)v(~rvq)) имеет нормальную форму.

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

Приведение к конъюнктивной нормальной форме (КНФ) позволяет по виду формулы, приведённой к некоторой стандартной форме, судить о том, тождественно-истинная она или нет. Приведение формулы к КНФ осуществляется в два этапа: 1) сначала приводим формулу к нормальной форме; 2) затем каждую подформулу вида (Av(B&C)) согласно равносильности (6) и каждую подформулу вида ((B&C)vA) согласно равносильности (6') заменяем формулой ((AvB)&(AvC)).

Формула, имеющая КНФ, тождественно-истинна тогда и только тогда, когда тождественно-истинны все её конъюнктивные члены, т.е. когда каждая элементарная дизъюнкция содержит хотя бы одну пару дизъюнктов, из которых один есть некоторая переменная, а другой – её отрицание. Например, формула (~pvqvp)&(~pvqv~q) является тождественно-истинной.

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

Приведение к дизъюнктивной нормальной форме (ДНФ) позволяет по виду формулы, приведённой к некоторой стандартной форме, судить о том, тождественно-ложная она или нет.

Приведение формулы к ДНФ осуществляется в два этапа: 1) сначала приводим формулу к нормальной форме; 2) затем каждую подформулу вида (A&(BvC)) согласно равносильности (7) и каждую подформулу вида ((BvC)&A) согласно равносильности (7') заменить формулой ((А&B)v(A&C)).

Формула, имеющая ДНФ, тождественно-ложная тогда и только тогда, когда тождественно-ложны все её дизъюнктивные члены, т.е. когда каждая элементарная конъюнкция содержит хотя бы одну пару конъюнктов, из которых один есть некоторая переменная, а другой – её отрицание.

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

Исчисление предикатов – раздел математической логики, исследующий операции с высказываниями, расчленёнными на субъект и предикат.

Алфавит языка логики предикатов образуется присоединением к алфавиту языка логики высказываний следующих знаков: а) квантор всеобщности (читается – все, всякий, каков бы нибыл и т.д.); квантор существования (читается – некоторые, хотя бы один, существует и т.д.); б) предметные или индивидные переменные; в) символы n-местных (n= 1, 2…) предикатов, или n-местные предикатные буквы. Символы одноместных предикатов и т.д.

В предикатных буквах верхний индекс указывает число их (аргументных) мест, а нижние индексы служат для различения предикатных букв с одинаковым числом мест.

Самым простым случаем предикатной формулы или формулы логики предикатов (определение см. в учебной литературе, в частности в [12] списка литературы) являются элементарные формулы. Например, формулы: p, Gx, Rxy, Vxyz – элементарные формулы.

Элементарная формула с одноместной предикатной буквой, например, формула Gx, читается: «х обладает свойством G», или «G от х»; элементарная формула с двухместной предикатной бук-вой, например, Rxy читается: «х находится в отношении R к y», или «R от x, y»; элементарная формула с трёхместной предикат-ной буквой, например, Vxyz может быть прочитана: «x, y, z находятся в отношении V», или «V от x, y, z» и т.п.

Иногда переменные, стоящие после предикатной буквы, заключают в скобки и разделяют запятыми. Так, вместо Vxyz можно было бы написать V (x, y, z). Кроме того, элементарные формулы с двухместными предикатными буквами записываются так: первую переменную ставят перед предикатной буквой, а вторую – после неё. Например, вместо Rxy пишут xRy.

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

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

Пример. Запишем на языке логики предикатов предложение: «Ни один человек не бессмертен». Получаем формулу:

Читается: каков бы ни был х, если х человек, то неверно, что он бессмертен.

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

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

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

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

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

Вопросы для самопроверки:

6. Что такое исчисление?

7. В чём заключается смысл разрешающей процедуры?

8. В чём разница между исчислением высказываний и исчислением предикатов?

9. Для чего используется метод аналитических таблиц?

10. Какие правила содержит система естественного вывода?