Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Аксиоматическое представление логики высказываний




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

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

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

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

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

А1. А ® (В ® А);

А2. (А ® (В ® С)) ® ((А ® В) ® (А ® С));

A3. А ® (В ® (А Ù В));

А4. (А Ù В) ® А;

А5. (А Ù В) ® В;

А6. А ®(А Ú В);

А7. В ®(А Ú В);

A8. (А ® С) ® ((В ® С) ® ((А Ú В) ® С));

A9. (А ® В ) ® (А ® ~ В ) ® ~ А;

A10. А ®(~ А ® В);

A100.~~ А ® А,

а единственным правилом вывода служит

 

МП А А ® В.
  В

 

Доказательство в системе Н формулы F строится согласно следующему предписанию.

На любом шаге построения можно написать:

1) одну из аксиом;

2) формулу, следующую из ранее написанных формул по правилу МП.

Доказательство формулы F считается построенным, если в соответствии с пп. 1 —2 получена последовательность формул, оканчивающаяся формулой F.

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

Так же как и в системе N, в системе Н знак «вводится по определению.

Пример. Ниже приводится доказательство в системе Н формулы

q ® q.

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

1) (q ® ((p ® q) ® q)) ® ((q ® (p ® q)) ® (q ® q) аксиома А2;
2) q ® ((p ® q) ® q) аксиома A1;
3) (q ® (p ® q)) ®(q ® q) МП (2, 1);
4) q ® (p ® q) аксиома A1;
q ® q МП (4,3).

Сделаем некоторые пояснения. При получении аксиомы в строке 1 по аксиомной схеме А2, последняя применяется следующим образом. В А2 мы заменяем (замещаем) все вхождения А вхождениями q; далее все вхождения С замещаются вхождениями q; наконец, на места вхождений В вставляется формула p ® q. Аксиома в строке 2 получается из аксиомной схемы А1 заменой буквы А на q и буквы В на p ® q. В строку 3 формула вписывается по правилу МП на основании формул, написанных в строках 1, 2.

Предлагаем читателю самому шаг за шагом убедиться, что схема правила МП здесь применена корректно. Последняя строка приведенного доказательства, по-видимому, не нуждается больше в дополнительных пояснениях. Заметим также, что доказательство той же формулы в системе N тривиально и состоит всего из одной строки (см. с. 72).

Существует простая связь между доказательствами конкретных формул (логики высказываний) и схемами доказательств. Так, выше была доказана формула q ® q. Ее доказательство легко превратить в схему доказательства формулы вида А ® А. Для этого в доказательстве формулы q ® q надо всюду q заменить на А и р на В. В результате описанной процедуры мы получаем следующую схему, по которой можно построить доказательство любой формулы вида

А ® А.

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

1) (A ® ((B ® A) ® A)) ® ((A ® (B ® A)) ® (A ® A) аксиома А2;
2) A ® ((B ® A) ® A) аксиома A1;
3) (A ® (B ® A)) ®(A ® A) МП (2, 1);
4) A ® (B ® A) аксиома A1;
A ® A МП (4,3).

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

В системе H аксиомы задаются с помощью аксиомных схем, т. е. особых выражений метаязыка этой системы. Как мы знаем, конкретная аксиома может быть получена надлежащим замещением метапеременных в соответствующей аксиомной схеме произвольными формулами. Но можно поступить иначе, задав аксиомы в самом языке системы в виде списка из следующих 11 формул:

1) p ® (q ® p);

2) (p ® (q ® r)) ® ((p ® q) ® (p ® r));

3) p ® (q ® (p Ù q));

4) (p Ù q) ® p;

5) (p Ù q) ® q;

6) p ®(p Ú q);

7) q ®(p Ú q);

8) (p ® r) ® ((q ® r) ® ((p Ú q) ® r));

9) (p ® q) ® (p ® ~ q) ® ~ p;

10) p ®(~ p ® q);

11) ~~ p ® p.

В этом случае, кроме правила МП, потребуется еще одно правило — правило подстановки. Операция подстановки определяется следующим образом. Подстановкой в формулу А формулы F вместо некоторой пропозициональной буквы Е называется замещение всех вхождений Е вхождениями F. Эту операцию можно производить и одновременно вместо нескольких различных пропозициональных букв, следя за тем, чтобы одинаковые пропозициональные буквы замещались всюду одинаковыми формулами.[33] Описанная система — назовем ее H '—очевидно, равнообъемна системе Н. Действительно, легко видеть, что любая аксиома в H является результатом подстановки в соответствующую аксиому системы Н '. Например, аксиома системы Н, построенная по схеме А1, является результатом подстановки в аксиому 1 системы Н'. Аксиома системы Н, построенная по А2, является результатом подстановки в аксиому 2 системы Н ' и т. д. Поэтому любое доказательство D в системе Н перейдет в одноименное доказательство D ' в системе Н ' вставкой в D перед каждым вхождением аксиомы системы Н соответствующей аксиомы системы Н '.

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

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

Замечание. Нетрудно видеть, что любое доказательство в системе H можно рассматривать в качестве одноименного доказательства в системе N, так как каждая из аксиом системы H доказуема в N (см. выше Т3, Т5—Т11, Т13, Т34, Т39) и, кроме того, в системе N имеется правило МП. Таким образом, первая часть доказательства равнообъемности Н и N тривиальна.

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

Вывод (в системе Н) формулы С из исходных формул (допущений) A 1, А 2,..., Аn (в дальнейшем, сокращенно: вывод A 1, А 2,..., Аn / С) есть последовательность формул, строящаяся так, что на любом шаге построения можно написать:

1) одну из формул A 1, А 2,..., Аn;

2) формулу, следующую из ранее написанных формул по правилу МП;

3) аксиому или ранее доказанную формулу.

Построение вывода A 1, А 2,..., Аn / С считается законченным, если в соответствии с пп. 1 —3 получена последовательность формул, конечная формула которой совпадает с С.

Очевидно, что доказательство формулы С в системе Н есть частный случай вывода в этой же системе из допущений, а именно тот частный случай, когда число допущений п = 0; иначе говоря, когда вывод строится при пустом списке допущений.

Нетрудно видеть, что для установления производности в системе Н правила следования, представленного фигурой вида

A 1, А 2,..., Аn

С

достаточно построить в этой системе вывод

A 1, А 2,..., Аn / С,

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

Лемма 5. В системе Н производны следующие правила (системы N): МП, ВК, УК, ВД, УД.

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

Вывод: А, В / А Ù В

1) А допущ.;
2) В допущ.;
3) А ® (В ® (А Ù В)) аксиома, A3;
4) (В ® (А Ù В)) МП (1, 3);
  А Ù В МП (2, 4).

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

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

Теорема 3. Если предъявлен выводA 1, А 2,..., Аn / С в системеН, то в системе Н можно построить вывод

A 1, А 2,..., Аn —1/ Аn ® С.

Доказательство этой теоремы будет состоять в обосновании метода перестройки вывода

A 1, А 2,..., Аn / С,

называемого в дальнейшем вспомогательным, в вывод

A 1, А 2,..., Аn —1/ Аn ® С,

который называется в дальнейшем результирующим.

Пусть последовательность формул

B 1;

В 2;

.

.

.

Вk;

.

.

.

Bl

есть вспомогательный вывод.

Очевидно, что Вl как конечная формула данного вывода, совпадает с С.

Согласно определению вывода из исходных формул (допущений) для любой формулы Вk (k = 1, 2,..., п) данной последовательности имеет место хотя бы один из следующих случаев:

Случай 1. Вk является аксиомой.

Случай 2. Вk является ранее доказанной формулой.

Случай 3. Вk является одной из формул A1, А2,..., A n -1.

Случай 4. Вk является формулой A n.

Случай 5. Вk следует из ранее написанных формул Вi Вj по правилу МП. Мы можем считать, что Bj представима в виде Bi ® Вk.

Приписав слева к каждой формуле вспомогательного вывода выражение An ®, мы получим последовательность формул:

An ® B 1;

A n ® B 2;

. (I)

.

.

An ® Вk;

.

.

.

An ® Bl

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

Предположим, что перед всеми формулами, написанными ранее, чем формула An ® Вk, в упомянутой последовательности (I) уже сделаны надлежащие вставки. Рассмотрим теперь, в зависимости от того, какой из пяти случаев имеет место для формулы Вk вспомогательного вывода, что следует вставить перед формулой An ® Вk, последовательности (I).

Случай1. Так как в соответствии с аксиомной схемой A1 формула

Вk ® (An ® Вk)

является аксиомой, то требуемая вставка состоит из двух формул вида

Вk,

Вk ® (An ® Вk),

из которых формула

A n ® Вk

следует по правилу МП.

Случай 2 рассматривается аналогично.

Случай 3 также рассматривается аналогично предшествующим случаям, с той лишь разницей, что вхождение формулы во вставку мотивируется тем, что Вk является одним из допущений A 1, А 2,..., Аn —1, каждое из которых, очевидно, может быть написано в результирующем выводе.

Случай 4. Так как Вk есть Аn, то An ® Вk совпадает с формулой An ® An которую в силу замечания на с. 99 можно считать ранее доказанной.

Случай 5. Так как формула Вk, следует из ранее написанных формул Вi и Вi ® Bk по правилу МП, то в последовательности (I), превращаемой в требуемый результирующий вывод, формулам Вii ® Bk отвечают формулы

(1) An ® Вi;

(2) An ® (Вi ® Bk).

Требуемая вставка состоит из, следующих двух формул:

(3) (An (Вi ® Bk)) ® ((An ® Вi)® (An ® Вk));

(4) (An ® Вi) ® (An ® Вk).

Из входящей во вставку формулы (4) и ранее написанной в последовательности (I) формулы (1) формула An ® Вk, перед которой делается вставка, следует по правилу МП; в свою очередь по этому же правилу формула (4) из вставки следует из формулы (3), которая по A2 является одной из аксиом системы Н и ранее написанной в последовательности (I) формулы (2).

Очевидно, что, пользуясь описанным методом, мы можем шаг за шагом сделать все вставки в последовательности (I) и превратить ее по осуществлении вставки на l -м шаге в требуемый результирующий вывод.

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

В 1, В 2,..., Bk

вспомогательного вывода при любом k = 1, 2, ..., l можно рассматривать в качестве самостоятельного вывода

A 1, А 2,..., Аn / Bk ,

который мы описанным выше эффективным способом превращаем на k- м шаге процесса перестройки в вывод

A 1, А 2,..., Аn —1/ An ® Вk.

Из теоремы 3 непосредственно вытекает

Следствие. Для того чтобы в системе Н построить доказательство формулы

A 1 ® (А 2 ®...(Аn ® С)...),

достаточно построить в системе Н вывод

A 1, А 2,..., Аn / С.

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

Установленная выше дедукционная теорема верна, как это видно из ее доказательства, для любого исчисления высказываний гильбертовского типа, в котором единственным правилом вывода служит МП и доказуемы формулы A1, A2. Эта теорема существенно облегчает поиск доказательств теорем в системе Н, так как теперь мы можем воспользоваться услугами метода введения допущений, широко применяемого в системах естественного вывода.

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

С помощью дедукционной теоремы легко показать, что, выбросив А10 из списка аксиомных схем системы Н, мы получим систему, равнообъемную Н. Для этого достаточно построить вывод А, ~ А / В, не пользуясь при этом, разумеется, А10. В качестве полезного упражнения мы предлагаем читателю построить упомянутый вывод, а затем, применяя метод дедукционной теоремы, преобразовать его в доказательство формулы А ® (~ А ® В). Таким образом, в системе Н можно было бы обойтись без аксиомной схемы А10. Включение же ее в состав аксиомных схем системы Н продиктовано необходимостью проводить в этой системе различие между конструктивными и неконструктивными доказательствами аналогично тому, как это мы делали выше в системе N естественного вывода.

Чтобы завершить установление равнообъемности систем H и N, остается доказать следующее предложение.

Лемма 6. Любое доказательство в системе N можно преобразовать в одноименное доказательство в системе Н.

Доказательство этого предложения мы предоставляем провести читателю, используя дедукционную теорему и лемму 5. План доказательства состоит в следующем. Пусть D — произвольное доказательство в системе N формулы вида

A 1 ® (А 2 ®...(Аn ® С)...)

(случай п = 0 не исключается).

В предположении, что доказательства формул, вписанных в качестве ранее доказанных, уже преобразованы в одноименные доказательства в системе Н, нужно показать, как преобразовать D в одноименное доказательство в Н, рассмотрев следующие случаи: а) D — прямое доказательство и б) D — косвенное доказательство. Заметим, что случай б) потребует выявления некоторых дальнейших подслучаев.

Из замечания на с. 99 и леммы 6 непосредственно вытекает следующее утверждение.

Теорема 4. Системы Н и N равнообъемны (эквивалентны).

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

Семантическую корректность системы Н устанавливает следующая теорема.

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

Доказательство теоремы 5 сводится к проверке того, что любая аксиома системы Н есть логическое тождество и что если посылки А, А ® В правила МП суть логические тождества, то заключение В, получаемое по данному правилу, также есть логическое тождество. Предлагаем читателю убедиться в этом самостоятельно, пользуясь табличным методом.

Из теорем 4 и 5 непосредственно вытекает семантическая корректность системы N естественного вывода, рассмотренной в предыдущем параграфе.

Следствие. Любая формула, доказуемая в системе N, тождественно-истинна.

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

Непротиворечивость является непременным требованием, которое предъявляется к системе способов рассуждения, применяемых в науке. «Логической противоречивости — при условии, конечно, правильного логического мышления — не должно быть ни в экономическом, ни в политическом анализе».[34]

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

Для системы, в которой доказуема формула

А ® (~ А ® В)

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

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

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

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

Система Н — аксиоматическое представление логики высказываний, так же как и система N естественного вывода, построена в форме иерархии частичных систем (подсистем). Аксиомные схемы Al, A2 вместе с правилом МП образуют положительное импликативное исчисление. Далее, система Н без аксиомных схем А9, А10, А100 —это исчисление положительной логики. Минимальной логике отвечает фрагмент системы Н, не содержащий аксиомных схем А10, А100. Наконец, исчисление конструктивной логики получается из Н выбрасыванием аксиомной схемы А100.

Для системы Н можно доказать теорему, устанавливающую допустимость в Н правила эквивалентной замены. (Формулы А, В называются эквивалентными, если доказуема формула А «В.)

Согласно этому правилу, если формулы А, В эквивалентны, то, заменив в какой-то формуле F одно или более вхождений А вхождением В, мы получим некоторую формулу G, эквивалентную первоначальной формуле F.

На основании установленных в § 6 эквивалентностей,[35] можно посредством правила эквивалентной замены показать, что принимаемые в качестве исходных в системе Н логические знаки ~, Ù, Ú, ® не являются независимыми в системе Н в следующем смысле: для любой формулы можно найти эквивалентную формулу, не содержащую других логических знаков, кроме тех, которые принадлежат только одной из следующих групп:

1) ®, ~; 2) Ú, ~; 3) Ù, ~.

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

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

1) (p ® (q ® r)) ® ((p ® q) ® (p ® r));

2) (p ® (q ® p);

3) (p ® (q ® r)) ® (q ® (p ® r));

4) p ® ~~ p;

5) ~~ p ® p;

6) (р ® q) ® (~ q ® ~р).

Польский логик Я. Лукасевич показал, что аксиома 3 избыточна, так как ее можно вывести из первых двух аксиом. Он также показал, что в системе Фреге последние три аксиомы можно заменить формулой (~ q ® ~ р) ® (p ® q).

Иными словами, Лукасевич установил эквивалентность системы Фреге более простой системе, содержащей три аксиомы:

1) (p ® (q ® r)) ® ((p ® q) ® (p ® r));

2) (p ® (q ® p);

3) (~ q ® ~р) ® (p ® q).

Из систем классической логики, построенных и изученных Лукасевичем, упомянем еще одну, содержащую следующие аксиомы:

1) (p ® (q ® r)) ® ((p ® q) ® (p ® r));

2) (~ р ® р) ® р;

3) p ® (~ p ® q).

Известны также импликативно-негативные системы с единственной аксиомой.

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

А Ù В =df ~(А ® ~ В);

A Ú B = df ~ A ® B

или

A Ú B = df(A ® B) ® B.

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

Но, как показал Лукасевич, если к классическому исчислению высказываний добавить

(a) правило отбрасывания через подстановку: если результат подстановки в формулу А отбрасывается, то отбрасывается и А;

(b) правило отбрасывания через отделение: если формула А ® В доказуема, а формула В отбрасывается, то отбрасывается и формула А;

(c) аксиому отбрасывания: некоторая пропозициональная буква, скажем, р, отбрасывается,

то с помощью этих правил можно будет отбросить все те, и только те, формулы, которые не являются тождественно-истинными.

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

*1. p аксиома отбрасывания;

2. (~ р ® р) ® р р.д. ф.;

*3. ~ р ® р (b): 2, 1;

4. p ® q (a): 3;

5. (~ р ® р) ® q р.д ф.;

*6. ~ р (b): 7, 6;

7. ~(р Ù р) ® ~ р р. д. ф.;

*8. ~(р Ù р) (b): 7, 6;

9. ~(р Ù q) (a): 8.

Запись «(b): 2,1» в строке 3 означает, что формула в данной строке отбрасывается по правилу отбрасывания через отделение на основании того, что написано в строках 2,1. Далее, запись «(a): 3» в строке 4 указывает на то, что формула здесь отбрасывается по правилу отбрасывания результата подстановки в данную формулу и т. п.

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

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

Упражнения

I. Показать, что система Г.Фреге равнообъемна первой из приведенных выше систем Я. Лукасевича.

II. Доказать результат В. И. Гливенко: если формула (логики высказываний) А тождественно-истинна, то ~~ А доказуема в конструктивном исчислении высказываний, скажем в N c n ; при этом любая тождественно-истинная формула вида ~ В доказуема в N c n .

Указание. Сначала надо показать, что любую последовательность формул, получаемую из некоторого доказательства D в системе Н приписыванием слева к каждой формуле, входящей в D, двух смежных знаков отрицания, можно преобразовать в одноименное доказательство в конструктивной части системы Н, т. е. в системе, получаемой из Н выбрасыванием аксиомной схемы А100. При этом следует использовать то обстоятельство, что формула ~~ (А ® В) ® (~~ А ® ~~ В) является теоремой конструктивного исчисления высказываний.

III. Пользуясь результатом В. И. Гливенко, доказать следующий результат К. Геделя: любая тождественно-истинная формула, не содержащая других логических знаков, кроме Ú и ~, доказуема в конструктивном исчислении высказываний.

IV. Используя теорему о семантической полноте классического исчисления высказываний (см. теорему 2 § 7), показать, что если формула А отбрасывается согласно приведенным выше правилам (a), (b), (с), то А не есть логическое тождество.

V. Показать, что если к системе Н ' добавить в качестве новой аксиомы любую не тождественно-истинную формулу, то описанное расширение системы Н ' будет противоречивой системой.

 


[1] Ленин В.И. Полн. собр. соч. 5-е изд. Т. 29. С. 172.

[2] Маркс К., Энгельс Ф. Соч. 2-е изд. Т. 20. С. 629.

[3] В традиционной логике оно известно под названием «простая конструктивная дилемма».

[4] Modus tollens (лат.) — отрицающий способ.

[5] См.: Гильберт Д., Аккерман В. Основы теоретической логики. М., 1947. С. 47.

[6] Доказательство этой теоремы приводится в «Началах» Евклида.

[7] Вводимое ниже допущение называется допущением косвенного доказательства.

[8] На этом шаге к доказательству присоединяется частный случай теоремы, установленной в предыдущем примере.

[9] См.: Слупецкий Е., Борковский Л. Элементы математической логики и теория множеств. М., 1965.

[10] Здесь и в дальнейшем р.д.ф. — ранее доказанная формула.

[11]Формулы С ¢ не существует, если С не начинается знаком отрицания. т. е. если С нельзя представить в виде ~ В.

[12] Исчисление минимальной логики было впервые построено и исследовано советским ученым акад. А. Н. Колмогоровым (См.: Колмогоров А. Н. О принципе tertium non datur // Матем. сборник. Т. 32. Вып. 4. М., 1925).

[13] Modus tollendo ponens (лат.) — способ утверждения посредством отрицания.

[14] Шанин Н. А. Логические проблемы арифметики // Труды Матем. ин-та им. В. А. Стеклова. 1954. XLII.

[15] Они рассматриваются ниже в § 6 данной главы.

[16] Обстоятельное рассмотрение затронутого вопроса см.: Марков А. А. Конструктивное направление (в математике и логике // Философская энциклопедия. Т. 3. М. 1964.; Математическая логика // Там же.

[17] См. с. 77.

[18] Напоминаем, чтоотношение одноименности доказательств было определено на с. 74 — 75.

[19] См. выше, с. 77.

[20] См. выше, с. 80.

[21] Т. е. формул, отличных от формулы F.

[22] См. выше, с. 85.

[23] См. выше, с. 78.

[24] См. выше, с. 81.

[25] См. выше, с. 85.

[26] См. выше, с. 181.

[27] См. выше, с. 86.

[28] См. выше, с. 88.

[29] См. выше, с. 80.

[30] См. выше, с. 86.

[31] См. выше, с. 82-83.

[32] См. выше, с. 92, Т40.

[33] В то же время различные пропозициональные буквы можно замещать как различными, так и одинаковыми формулами.

[34] Ленин В. И. Полн. собр. соч. Т. 30. С. 91.

[35] См. выше, с. 92.






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

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных