Полнота классического исчисления высказываний

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

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

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

Покажем сначала, что система N естественного вывода семантически полна, отложив установление ее семантической корректности до следующего параграфа.

Будем говорить, что формула F составлена из пропозициональных букв E ₁, E ₂,..., E_n (эти буквы выписаны без повторений), если в перечне E ₁, E ₂,..., E_n имеются все пропорциональные буквы, входящие в F (но могут содержаться и другие, не входящие в F буквы).

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

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

~ p Ú q,

первый из них является минимальным:

1) р, q; 2) р, q, r; 3) p, q, r, p ₁, q ₂ и т. д.

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

В п начальных (входных) столбцов таблицы вписываются пропозициональные буквы E ₁, E ₂,..., E_n (по одной в каждый столбец); в заключительный столбец выписывается формула F. Промежуточные столбцы заполняются остальными подформулами формулы F (также по одной в каждом столбце). Начальные столбцы заполняются всеми различными наборами, образованными из символов логических значений (по одному символу в каждом столбце и по одному набору в каждой строке). Очевидно, что число таких n -членных наборов будет равно 2 ⁿ. Остальные столбцы заполняются символами логических значений в соответствии с истинностными таблицами для логических знаков: ~, Ù, Ú, ® до тех пор, пока полностью не будет заполнен заключительный столбец.

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

A ₁ ® (A ₂ ®... (А_n ® С)...)

мы будем иногда сокращенно записывать так:

A _1, A ₂,..., А_n ® С.

Введем одно вспомогательное понятие. Будем говорить, что

G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_k

является n -кой, отвечающей i -й (i = 1, 2,..., 2 ⁿ) строке и таблице формулы при перечне E ₁, E ₂,..., E_n пропозициональных букв, из которых составлена F [в дальнейшем сокращенно: (i -й) соответственной n -кой формулы F ], если выполняются условия:

1) Gⁱ_k есть для любого k (k = 1, 2, …, n), когда в i -й строке под E_k стоит символ логического значения «истинно»;

2) Gⁱ_k есть ~ E_k для любого k (k = 1, 2,..., n), когда в i -й строке под E_k стоит символ логического значения «ложно».

Имеют место следующие леммы:

Лемма 3. ПустьG ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n есть (i-я) соответственная п-ка формулы F. Тогда, если в i-й строке (данной таблицы формулы F) под F написан символ логического значения «истинно», то формула

G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® F (I)

доказуема в системе N, и если в i-й строке (данной таблицы формулыF) под F написан символ логического значения «ложно», то формула

G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® ~ F (II)

доказуема в системе N.

Доказательство леммы можно свести к рассмотрению следующих случаев:

Случай 0. Формула F — пропозициональная буква. Тогда, если (в i -й строке) под F написан символ логического значения «истинно», формула F совпадает с одной из формул G ₁ ⁱ, Gⁱ ₂ ,..., Gⁱ_n, a потому формула (I) пo T2^[20] доказуема в N. Сходным образом, если под F написан символ логического значения «ложно», формула (II) по T2 также доказуема в N.

Теперь в предположении, что лемма верна для собственных подформул^[21] формулы F, рассмотрим дальнейшие случаи.

Случай I. Формула F представима в виде ~ А.

Случай I.1. Под F написан в i -й строке символ логического значения «истинно». Тогда (в этой же строке) под А написан символ логического значения «ложно», а потому (согласно предположению) в N доказуема формула

G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® ~ А,

которая совпадает с требуемой формулой (I).

Случай I.2. Под F написан символ логического значения «ложно». Тогда под А написан символ логического значения «истинно» и (по предположению) формула

(1) G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® A

доказуема в N. Кроме того, в N доказуема формула

(2) А ® ~~ А по Т14.^[22]

Применяя к формулам (1) и (2) обобщенное правило силлогизма,^[23] устанавливаем, что требуемая формула (II) также доказуема в N.

Случай II. Формула F представима в виде А Ù В.

Случай II.1. Под F написан в i -й строке символ логического значения «истинно». Тогда в данной строке этот же символ написан как под А, так и под В. По предположению, каждая из формул

G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® A;

G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® B

доказуема в N. Следовательно, на основании правила ДЧ (правила доказательства по частям^[24]) в N должна быть доказуема и требуемая формула (I).

Случай II.2. Под F написан символ логического значения «ложно». Тогда а) под А или б) под В написан этот же символ.

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

По предположению формула

(1) G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® ~ A

доказуема в N. Кроме того, в N доказуема формула

(2) А ® ~ (А Ù В) по Т21.^[25]

Требуемая формула (II) следует из формул (1) и (2) по обобщенному правилу силлогизма.

Случаи III. Формула F представима в виде A Ú B.

Случай III.1. Под F написан символ логического значения «истинно». Тогда этот же символ написан а) под А или б) под В. Здесь мы ограничимся рассмотрением подслучая б).

По предположению формула

(1) G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® B

доказуема в N. Кроме того, в N доказуема и формула

(2) В ® (A Ú B) по Т11.^[26]

Из (1) и (2) по правилу обобщенного силлогизма следует требуемая формула (I).

Случай III.2. Под F написан символ логического значения «ложно». Тогда как под А, так и под В написан этот же символ.

По предположению, каждая из следующих формул:

(1) G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® ~ A;

(2) G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® ~ B

доказуема в N. Кроме того, в N доказуема формула

(3) (~ А Ù ~ В) ® ~ (А Ú В) по Т32.^[27]

Согласно правилу ДЧ, если (1) и (2) доказуемы в N, то в N доказуема и формула

(4) G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® (~ А Ù ~ B ).

Наконец, из формул (4) и (3) по правилу обобщенного силлогизма следует требуемая формула (II).

Случай IV. Формула F представима в виде А ® В.

Случай IV.1. Под F написан символ логического значения «истинно». Тогда а) под А написан символ логического значения «ложно» или б) под В написан символ логического значения «истинно».

Если имеет место а), то по предположению в N доказуема формула

(1) G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® ~ A.

Кроме того, в N доказуема формула

(2) ~ А ® (А ® В) Ср. Т34.^[28]

По правилу обобщенного силлогизма из (1) и (2) следует требуемая формула (I). Если имеет место б), то в N доказуема формула

(1) G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® B.

Очевидно также, что в N доказуема формула

(2) В ® (А ® В) по Т3.^[29]

По правилу обобщенного силлогизма из (1) и (2) следует требуемая формула (I).

Случай IV.2. Под F написан символ логического значения «ложно». Тогда под А написан символ логического значения.«истинно», а под В — символ логического значения «ложно».

По предположению, в этом случае в N доказуемы формулы

(1) G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® A;

(2) G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® ~ B.

Согласно правилу ДЧ если в N доказуемы формулы (1) и (2), то в N доказуема и формула

(3) G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® (A Ù ~ B).

Кроме того, в N доказуема формула

(4) (A Ù ~ B) ® ~(A ® B) по Т33.^[30]

По обобщенному правилу силлогизма из (3) и (4) следует требуемая формула (II).

Рассмотрением данного частного случая завершается доказательство леммы 3.

Лемма 4. Пусть 1) Е ₁, Е ₂,..., E_n — перечень пропозициональных букв, из которых составлена формула F. Тогда, если F есть тождественно-истинная формула, то в системе N доказуема формула

(Е ₁ Ú ~ Е ₁), (Е ₂ Ú ~ Е ₂),..., (E_n Ú ~ E_n) ® F. (III)

Доказательство. Применяя к формуле (III) 2^{( n —l)} + 2^{(n —2)} +... + 1 раз правило PC (правило доказательства разбором случаев^[31]), мы сводим задачу на доказательство формулы (III) к построению доказательств каждой из 2 ⁿ кратных импликаций, представимых в виде

G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n ® F, (IV)

где G ₁ ⁱ, Gⁱ ₂,..., Gⁱ_n — соответственная n -ка формулы F.

По лемме 3 для любого i (i= 1, 2,..., 2 ⁿ) формула (I V) доказуема в N.

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

Теорема 2. Если формула F тождественно-истинна, то F доказуема в N.

Доказательство. По лемме 4, если Е ₁, Е ₂,..., E_n — перечень пропозициональных букв, из которых составлена формула F, то в N доказуема формула (III).

В то же время в системе N доказуема любая формула вида

Е_i Ú ~ Е_i. ^[32]

Отсюда следует, что формула F доказуема в N.

Доказательство теоремы 2 дает эффективный общий метод (алгоритм), с помощью которого для любой тождественно-истинной формулы по ее таблице можно построить доказательство данной формулы в системе N.

Из теоремы 2 вытекает:

Следствие. Если формулыА,В равносильны, то в системе N доказуема формула А «В.

Очевидно, что с помощью логической теоремы вида А «В мы можем показать, что в системе N производны правила следования вида

А,В,

ВА,

которые можно записать в виде одной схемы

А

В.

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

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

Не нашли, что искали? Воспользуйтесь поиском: