Импликационное исчисление высказываний - Implicational propositional calculus

В математическая логика, то импликационное исчисление высказываний это версия классический пропозициональное исчисление который использует только один соединительный, называется подразумеваемый или условный. В формулы, это бинарная операция обозначается "подразумевает", "если ..., то ...", "→", " ${ displaystyle rightarrow}$ ", так далее..

Виртуальная полнота как оператор

Одно только следствие не функционально полный как логический оператор потому что нельзя образовать все другие двузначные функции истины от него. Однако если у кого-то есть пропозициональная формула который, как известно, ложный и использует это, как если бы это была нулевая связка для ложности, тогда можно определить все другие функции истинности. Так что импликация в качестве оператора практически завершена. Если п,Q, и F предложения и F заведомо ложно, тогда:

¬п является эквивалент к п → F
п ∧ Q эквивалентно (п → (Q → F)) → F
п ∨ Q эквивалентно (п → Q) → Q
п ↔ Q эквивалентно ((п → Q) → ((Q → п) → F)) → F

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

Стоит отметить, что F не определима из → и произвольных переменных предложения: любая формула, построенная из → и пропозициональных переменных, должна получить значение true, когда все ее переменные оценены как истинные. Отсюда следует, что {→} не является функционально полным. Например, его нельзя использовать для определения двухзначной функции истинности, которая всегда возвращает ложный.

Система аксиом

Рассмотрены следующие утверждения тавтологии (несводимый и интуитивно верный по определению).

Схема аксиомы 1 это п → (Q → п).
Схема аксиомы 2 (п → (Q → р)) → ((п → Q) → (п → р)).
Схема аксиомы 3 (Закон Пирса ) является ((п → Q) → п) → п.
Один ненулевой правило вывода (modus ponens ) из п и п → Q сделать вывод Q.

Где в каждом случае п, Q, и р может быть заменен любыми формулами, которые содержат только «→» в качестве связки. Если Γ - набор формул и А формула, тогда ${ displaystyle Gamma vdash A}$ Значит это А выводится с использованием аксиом и правил, приведенных выше, и формул из Γ в качестве дополнительных гипотез.

Лукасевич (1948) нашел систему аксиом для импликативного исчисления, которая заменяет схемы 1–3, приведенные выше, единственной схемой.

((п → Q) → р) → ((р → п) → (S → п)).

Он также утверждал, что не существует более короткой системы аксиом.

Основные свойства деривации

Поскольку все аксиомы и правила исчисления являются схемами, вывод замкнут при замена:

Если

{ displaystyle Gamma vdash A,}

тогда

{ Displaystyle sigma ( Gamma) vdash sigma (A),}

где σ - любая подстановка (формул, использующих только импликацию).

Импликационное исчисление высказываний также удовлетворяет теорема дедукции:

Если

{ displaystyle Gamma, A vdash B}

, тогда

{ displaystyle Gamma vdash A to B.}

Как объяснено в теорема дедукции В статье это справедливо для любого аксиоматического расширения системы, содержащего схемы аксиом 1 и 2, указанные выше, и modus ponens.

Полнота

Импликационное исчисление высказываний семантически полный относительно обычной двузначной семантики классической логики высказываний. То есть, если Γ - множество импликационных формул и А импликационная формула повлекло за собой по Γ, то ${ displaystyle Gamma vdash A}$ .

Доказательство

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

Доказательство похоже на полноту полной логики высказываний, но оно также использует следующую идею для преодоления функциональной неполноты импликации. Если А и F формулы, то $А \to F$ эквивалентно $(\neg А *) \lor F,$ куда А * является результатом замены в А все, некоторые или ни одно из вхождений F ложью. По аналогии, $(А \to F) \to F$ эквивалентно $А * \lor F .$ Поэтому при некоторых условиях их можно использовать вместо слов А * ложно или А * верно соответственно.

Сначала рассмотрим некоторые основные факты о выводимости:

{ Displaystyle от A до B, B до C vdash от A до C}

(1)

Действительно, мы можем вывести А → (B → C), используя аксиому 1, а затем вывести А → C по modus ponens (дважды) от Axe. 2.

{ Displaystyle А к В vdash (В к С) к (А к С)}

(2)

Это следует из (1) по теореме дедукции.

{ Displaystyle от A до C, (от A до B) до C vdash C}

(3)

Если мы далее предположим C → B, мы можем вывести

А \to B

с помощью (1), то выводим C пользователя modus ponens. Это показывает

{ Displaystyle от A до C, (от A до B) до C, C до B vdash C}

, а теорема дедукции дает

{ Displaystyle от A до C, (от A до B) до C vdash (от C до B) до C}

. Применяем Axe. 3 для получения (3).

Позволять F - произвольная фиксированная формула. Для любой формулы А, мы определяем $А 0 = (А \to F)$ и $А 1 = ((А \to F) \to F).$ Рассматривайте только формулы в пропозициональных переменных п₁, ..., п_п. Мы утверждаем, что для каждой формулы А в этих переменных и каждый назначение истины е,

{ displaystyle p_ {1} ^ {e (p_ {1})}, dots, p_ {n} ^ {e (p_ {n})} vdash A ^ {e (A)}.}

(4)

Докажем (4) индукцией по А. Базовый случай А = п_я тривиально. Позволять $А = (B \to C).$ Мы выделяем три случая:

е(C) = 1. Тогда также е(А) = 1. Имеем
${ Displaystyle (С к F) к F vdash ((B к C) к F) к F}$
применяя (2) дважды к аксиоме $C \to (B \to C).$ Поскольку мы получили $(C \to F) \to F$ по предположению индукции можно вывести $((B \to C) \to F) \to F .$
е(B) = 0. Затем снова е(А) = 1. Теорема дедукции, примененная к (3) дает
${ Displaystyle В к F vdash ((В к C) к F) к F.}$
Поскольку мы получили $B \to F$ по предположению индукции можно вывести $((B \to C) \to F) \to F .$
е(B) = 1 и е(C) = 0. Тогда е(А) = 0. Имеем
${ displaystyle { begin {align} (B to F) to F, C to F, B to C & vdash B to F && { text {by (1)}} & vdash F && { text {by modus ponens,}} end {выравнивается}}}$
таким образом ${ Displaystyle (B к F) к F, C к F vdash (B к C) к F}$ по теореме дедукции. Мы вывели $(B \to F) \to F$ и $C \to F$ по предположению индукции, поэтому мы можем вывести $(B \to C) \to F .$ Это завершает доказательство (4).

Теперь позвольте F быть тавтологией в переменных п₁, ..., п_п. Докажем обратной индукцией по k = п, ..., 0, что для каждого задания е,

{ displaystyle p_ {1} ^ {e (p_ {1})}, dots, p_ {k} ^ {e (p_ {k})} vdash F.}

(5)

Базовый случай k = п следует из частного случая (4) с помощью

{ Displaystyle F ^ {е (F)} = F ^ {1} = ((F к F) к F)}

и тот факт, что F→F является теоремой по теореме дедукции.

Предположить, что (5) выполняется для k +1, покажем для k. Применяя теорему дедукции к предположению индукции, получаем

{ displaystyle { begin {align} p_ {1} ^ {e (p_ {1})}, dots, p_ {k} ^ {e (p_ {k})} & vdash (p_ {k + 1 } to F) to F, p_ {1} ^ {e (p_ {1})}, dots, p_ {k} ^ {e (p_ {k})} & vdash ((p_ { k + 1} to F) to F) to F, end {выравнивается}}}

сначала установив е(п_k+1) = 0 и вторая установка е(п_k+1) = 1. Отсюда получаем (5) с использованием modus ponens.

За k = 0 получаем, что тавтология F доказуемо без предположений. Вот что нужно было доказать.

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

Система аксиом Бернейса – Тарского

Часто используется система аксиом Бернейса – Тарского. В частности, в статье Лукасевича аксиомы Бернейса-Тарского выводятся из единственной аксиомы Лукасевича как средство демонстрации ее полноты.
Она отличается от схем аксиом, приведенных выше, заменой схемы аксиом 2, (п→(Q→р))→((п→Q)→(п→р)), с

Схема аксиомы 2 ': (п→Q)→((Q→р)→(п→р))

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

Мы показываем это из п→(Q→р) и п→Q можно вывести п→р. Этот факт можно использовать вместо схемы аксиом 2 для получения мета-теоремы.

п→(Q→р) данный
п→Q данный
(п→Q)→((Q→р)→(п→р)) топор 2 '
(Q→р)→(п→р) т.пл. 2,3
(п→(Q→р))→(((Q→р)→(п→р))→(п→(п→р))) топор 2 '
((Q→р)→(п→р))→(п→(п→р)) тп 1,5
п→(п→р) т.пл. 4,6
(п→(п→р))→(((п→р)→р)→(п→р)) топор 2 '
((п→р)→р)→(п→р) т.пл. 7,8
(((п→р)→р)→(п→р))→(п→р) топор 3
п→р mp 9,10 qed

Проверка того, является ли формула импликативного исчисления высказываний тавтологией

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

Пример нетавтологии:

Предполагать [(А→B)→((C→А)→E)]→([F→((C→D)→E)]→[(А→F)→(D→E)]) ложно.

Потом (А→B)→((C→А)→E) правда; F→((C→D)→E) правда; А→F правда; D правда; и E ложно.

С D правда, C→D правда. Итак, правда о F→((C→D)→E) равносильно истине F→E.

Тогда, поскольку E ложно и F→E правда, мы получаем это F ложно.

С А→F правда, А ложно. Таким образом А→B верно и (C→А)→E правда.

C→А ложно, поэтому C правда.

Значение B не имеет значения, поэтому мы можем произвольно выбрать его как истинное.

Подводя итоги, оценка, которая устанавливает B, C и D быть правдой и А, E и F быть ложным сделает [(А→B)→((C→А)→E)]→([F→((C→D)→E)]→[(А→F)→(D→E)]) ложный. Так что это не тавтология.

Пример тавтологии:

Предполагать ((А→B)→C)→((C→А)→(D→А)) ложно.

Потом (А→B)→C правда; C→А правда; D правда; и А ложно.

С А ложно, А→B правда. Так C правда. Таким образом А должно быть правдой, что противоречит тому факту, что оно ложно.

Таким образом, нет оценки, которая делает ((А→B)→C)→((C→А)→(D→А)) ложный. Следовательно, это тавтология.

Добавление схемы аксиомы

Что произойдет, если к перечисленным выше схемам добавить еще одну схему аксиом? Есть два случая: (1) это тавтология; или (2) это не тавтология.

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

Если новая схема аксиом не является тавтологией, тогда каждая формула становится теоремой (что делает в данном случае бесполезным понятие теоремы). Более того, тогда существует верхняя граница минимальной длины доказательства каждой формулы, потому что существует общий метод доказательства каждой формулы. Например, предположим, что новая схема аксиом была ((B→C)→C)→B. Потом ((А→(А→А))→(А→А))→А это пример (одна из новых аксиом), а также не тавтология. Но [((А→(А→А))→(А→А))→А]→А является тавтологией и, следовательно, теоремой, основанной на старых аксиомах (с использованием приведенного выше результата о полноте). Применяя modus ponens, получаем, что А это теорема расширенной системы. Тогда все, что нужно сделать, чтобы доказать любую формулу, - это заменить А по желаемой формуле на протяжении всего доказательства А. Это доказательство будет состоять из того же количества шагов, что и доказательство А.

Альтернативная аксиоматизация

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

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

аа 1: ꞈА→А
аа 2: (А→B) → ꞈ (А→(C→B))
аа 3: А→((B→C) → ꞈ ((А→B)→C))
аа 4: А→ ꞈ (B→А)

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

Рассмотрим любую формулу Φ, которая может содержать А, B, C₁, ..., C_п и заканчивается А в качестве окончательного заключения. Затем берем

аа 5: Φ₋→ (Φ₊→ ꞈΦ)

как схему аксиом, где Φ₋ является результатом замены B к А на всем протяжении Φ и Φ₊ является результатом замены B к (А→А) на всем протяжении Φ. Это схема схем аксиом, поскольку существует два уровня подстановки: в первом подставляется Φ (с вариациями); во втором - любая из переменных (включая обе А и B) можно заменить произвольными формулами импликативного исчисления высказываний. Эта схема позволяет доказывать тавтологии с более чем одной переменной, рассматривая случай, когда B ложно Φ₋ и случай, когда B верно Φ₊.

Если переменная, которая является окончательным выводом формулы, принимает значение истина, то вся формула принимает значение истина независимо от значений других переменных. Следовательно, если А верно, то Φ, Φ₋, Φ₊ и Φ₋→ (Φ₊→ Φ) истинны. Итак, без ограничения общности, мы можем предположить, что А ложно. Заметим, что Φ является тавтологией тогда и только тогда, когда оба Φ₋ и Φ₊ тавтологии. Но пока Φ имеет п+2 различных переменных, Φ₋ и Φ₊ как есть п+1. Таким образом, вопрос о том, является ли формула тавтологией, свелся к вопросу о том, являются ли все определенные формулы с одной переменной каждой тавтологией. Также обратите внимание, что Φ₋→ (Φ₊→ Φ) является тавтологией независимо от того, является ли Φ, потому что если Φ ложно, то либо Φ₋ или Φ₊ будет ложным в зависимости от того, B ложно или верно.

Примеры:

Вывод закона Пирса

[((п→п)→п)→п]→([((п→(п→п))→п)→п]→[((п→Q)→п)→п]) аа 5
п→п аа 1
(п→п)→((п→п)→(((п→п)→п)→п)) аа 3
(п→п)→(((п→п)→п)→п) т.пл. 2,3
((п→п)→п)→п т.пл. 2,4
[((п→(п→п))→п)→п]→[((п→Q)→п)→п] mp 5,1
п→(п→п) аа 4
(п→(п→п))→((п→п)→(((п→(п→п))→п)→п)) аа 3
(п→п)→(((п→(п→п))→п)→п) т.пл. 7,8
((п→(п→п))→п)→п т.пл. 2,9
((п→Q)→п)→п mp 10,6 qed

Вывод единственной аксиомы Лукасевича

[((п→Q)→п)→((п→п)→(S→п))]→([((п→Q)→(п→п))→(((п→п)→п)→(S→п))]→[((п→Q)→р)→((р→п)→(S→п))]) аа 5
[((п→п)→п)→((п→п)→(S→п))]→([((п→(п→п))→п)→((п→п)→(S→п))]→[((п→Q)→п)→((п→п)→(S→п))]) аа 5
п→(S→п) аа 4
(п→(S→п))→(п→((п→п)→(S→п))) аа 2
п→((п→п)→(S→п)) т.п.3,4
п→п аа 1
(п→п)→((п→((п→п)→(S→п)))→[((п→п)→п)→((п→п)→(S→п))]) аа 3
(п→((п→п)→(S→п)))→[((п→п)→п)→((п→п)→(S→п))] т.пл. 6,7
((п→п)→п)→((п→п)→(S→п)) т.п.5,8
[((п→(п→п))→п)→((п→п)→(S→п))]→[((п→Q)→п)→((п→п)→(S→п))] т.пл. 9,2
п→(п→п) аа 4
(п→(п→п))→((п→((п→п)→(S→п)))→[((п→(п→п))→п)→((п→п)→(S→п))]) аа 3
(п→((п→п)→(S→п)))→[((п→(п→п))→п)→((п→п)→(S→п))] т.пл. 11,12
((п→(п→п))→п)→((п→п)→(S→п)) т.п.5,13
((п→Q)→п)→((п→п)→(S→п)) т.п.14,10
[((п→Q)→(п→п))→(((п→п)→п)→(S→п))]→[((п→Q)→р)→((р→п)→(S→п))] т.пл. 15,1
(п→п)→((п→(S→п))→[((п→п)→п)→(S→п)]) аа 3
(п→(S→п))→[((п→п)→п)→(S→п)] mp 6,17
((п→п)→п)→(S→п) т.пл. 3,18
(((п→п)→п)→(S→п))→[((п→Q)→(п→п))→(((п→п)→п)→(S→п))] аа 4
((п→Q)→(п→п))→(((п→п)→п)→(S→п)) т.пл. 19,20
((п→Q)→р)→((р→п)→(S→п)) т.п.21,16 qed

Использование таблицы истинности для проверки единственной аксиомы Лукасевича потребует рассмотрения 16 = 2⁴ случаев, поскольку он содержит 4 различных переменных. В этом выводе мы смогли ограничить рассмотрение всего 3 случаями: р ложно и Q ложно, р ложно и Q правда, и р правда. Однако, поскольку мы работаем в рамках формальной системы логики (а не вне ее, неформально), каждый случай требовал гораздо больше усилий.