Виды формул в классической логике предикатов первого порядка

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

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

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

Формула A есть невыполнимой (тождественно-фальшивой) тогда и лишь тогда, в то время, когда она принимает значение «неправда» в каждой реализации и при любом , т. е. .

Приведем схемы общезначимых формул (законов) логики предикатов первого порядка:

1. Взаимовыразимость кванторов:

;

.

2. Образование контрадикторных противоположностей (законы отрицания кванторов):

;

.

3. Закон подчинения (сообщение квантора существования и квантора общности):

– закон подчинения.

4. Законы пронесения кванторов:

;

;

;

;

, в случае, если не свободна в А;

, в случае, если не свободна в A;

;

, в случае, если не свободна в A;

, в случае, если не свободна в B;

;

, в случае, если не свободна в A;

, в случае, если не свободна в B,

.

5. Законы перестановки кванторов:

;

;

.

6. Закон удаления квантора общности:

, где A(t) – итог подстановки вместо всех свободных вхождений переменной ? в формулу A терма t.

7. Закон введения квантора существования:

, где A(t) – итог подстановки вместо всех свободных вхождений переменной ? в формулу A терма t.

8. Закон непустоты предметной области:

.

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

Вероятная реализация именуется моделью формулы A, в случае, если формула A принимает значение «истина» в данной реализации при любом приписывании ? значений индивидным переменным, т. е. .

Вероятная реализация именуется моделью множества формул Г, в случае, если есть моделью для каждой формулы .

Как и в пропозициональной логике, фундаментальными логическими отношениями в логике предикатов первого порядка являются отношения совместимости по истинности, совместимости по ложности и логического следования. Пускай Г – произвольное множество формул.

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

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

Логическое следование между множеством формул Г и формулой B (Г B) имеет место в том случае, если не существует таковой приписывания и реализации значений предметным переменным ?, при которых любая формула из Г принимает значение «истина», а формула B – «неправда».

Законов логики предикатов понятия и первого порядка логического следования слишком мало для анализа рассуждений. Фактически серьёзным есть установление процедуры, которая бы разрешала продемонстрировать, что некая формула A вправду есть законом данной логической теории и что из формул A1, A2,…, Anв данной теории вправду направляться формула B. В отличие от пропозициональной логики, дефиниции логического следования и логического закона в логике предикатов не содержат метода ответа вопросов об общезначимости произвольной формулы A и наличии отношения логического следования между формулами и B. Чтобы продемонстрировать, что имеет место отношение логического следования , необходимо разглядеть все возможные распределения и возможные реализации значений предметных переменных и удостовериться, что среди них нет таких, в то время, когда принимали бы значение «истина», а B – значение «неправда». Но это нереально, поскольку количество всех приписываний и реализаций ? нереально потому, что их число вечно. Никакого метода не существует в принципе. Следовательно, хорошая логика предикатов неразрешима.

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

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

Анализ некоей формулы A начинается с предположения, что при некоем распределении истинностных значений по ее пропозициональным переменным формула A фальшива. Предположение об истинности либо ложности формулы отмечается посредством добавления знаков T и F перед формулой (для формулы A – TA и FA соответственно). Такие формулы именуются отмеченными.Предстоящий анализ формул осуществляется правильно, каковые соответствуют ложности и семантическим условиям истинности пропозициональной логики и логики предикатов первого порядка.

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

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

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

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

Правило предполагает, что при наличии в цепи отмеченной формулы , которая в соответствии с определению конъюнкции возможно подлинной в том и лишь в том случае, если подлинными являются ее подформулы A и B, в эту же цепь возможно поместить две отмеченные формулы – TA и TB.

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

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

Правила и основаны на особенностях отрицания, т. е. они разрешают при наличии в цепи отмеченных формул либо поместить в эту же цепь соответственно формулы либо .

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

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

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

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

Ниже представлены правила редукции для формул, содержащих кванторы:

Правило используется в том случае, если в некоей цепи имеется отмеченная формула вида . Формула подлинна, в случае, если и лишь в случае, если любой индивид предметной области удовлетворяет условию A. Это указывает, что подлинной оказывается
кроме этого каждая формула вида A(k), которая является результатом подстановки вместо всех свободных вхождений ? в A произвольного замкнутого терма k. Замкнутым термом k возможно лишь уже содержащийся в отмеченных формулах данной цепи замкнутый терм, а вдруг таковых нет в цепи, то возможно забрать любую индивидную константу. Это правило редукции есть глобальным, т. е. оно может использоваться много раз чтобы повторным применением приобретать утверждения об истинности A(k1), A(k2), … для замкнутых термов, уже содержащихся в аналитической таблице и хороших от терма k.

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

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

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

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

Цепь аналитической таблицы именуется замкнутой, в случае, если в ее составе видится две противоречащие друг другу отмеченные формулы – TC и FC. В соответствии с этим в замкнутой аналитической таблице любая цепь есть замкнутой.

Следовательно, формула A общезначима, в случае, если и лишь в случае, если существует замкнутая аналитическая таблица, начальная цепь которой начинается с отмеченной формулы FA. Из множества формул A1, A2, …, Anлогически направляться формула B тогда и лишь тогда, в то время, когда существует замкнутая аналитическая таблица, начальная цепь которой начинается с отмеченных формул TA1, TA2, …, TAnи FB.

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

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

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

Расщепляющие правила направляться использовать в последнюю очередь, лишь по окончании того, как применены все нерасщепляющие пропозициональные и кванторные правила.

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

(1)
(2)
(3)		– из (2) по
(4)		– из (2) по
(5)		– из (3) по
(6)		– из (4) по
(7)			– из (1) по

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

Пример 2. Заберём пример, содержащий квантифицированные формулы. Нужно обосновать выводимость вида . Для начала введем предположение о том, что , и . Поместим эти отмеченные формулы в начало цепи. Аналитическая таблица будет иметь вид:

(1)
(2)
(3)
(4)		– из (3) по
(5)		– из (1) по
(6)		– из (2) по
(7)		– из (4) по
(8)		– из (4) по
(9)			– из (5) по
				– из (6) по

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

Логика. 2.2. Запись суждений в виде формулы

Интересные записи:

• Vi. право собственности на природные ресурсы
• Выполнение арифметических операций над числами, представленными с фиксированной запятой.
• Vi. проблема прочности права. вопрос о субъективном гражданском праве и о злоупотреблении правом
• Вишнёвый сад»: наше прошлое, настоящее или будущее? (по пьесе а.п. чехова «вишнёвый сад»).