Тема 2. Аксиоматические системы пропозициональной логики

Вопросы:

1. Язык пропозициональной логики.

2. Аксиоматическая система пропозициональной логики.

3. Отношение выводимости. Понятие доказуемой формулы.

4. История и проблемы систем пропозициональной логики.

1. Алфавит языка пропозициональной логики включает три рода исходных символов:

1) пропозициональные переменные: A, B, C, D, ...

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

Символ	Название	Значение в естественном языке
º («)	эквивалентность (эквиваленция)	тогда, и только тогда; если, и только если
 ( )	строгая дизъюнкция	или …, или …; либо…, либо…
É (®)	импликация	если…, то…; когда…, то…
& (Ù, )	конъюнкция	и; а; да; но
Ú	дизъюнкция простая	или
 (~, A)	отрицание	не; нет; невозможно, что; неверно, что

3) вспомогательные знаки: (, ) – левая и правая скобки.

Значимые выражения в символических языках логики называются формулами. Индуктивно-рекурсивное определение формулы состоит из трех пунктов:

1) Любая пропозициональная переменная является элементарной формулой.

2) Если A и B – элементарные формулы, то A  B, A Ú B, A É B, A & B, A Ú B, ØA являются формулами.

3) Нечто является пропозициональной формулой, если удовлетворяет пунктам 1 и 2.

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

Пропозициональные связки относятся к группе логических знаков: они представляют некоторые отношения, которые имеют место в сложных высказываниях. Например, в высказывании “Если с утра светит солнце, то погода прекрасная” имеется условно-следственная связь, для выражения которой в нашем символическом языке используется связка импликации, то есть, этому высказыванию мы можем сопоставить формулу A É B, где переменная А обозначает высказывание “С утра светит солнце”, а переменная В – “Погода прекрасная”.

Вспомогательные знаки – скобки – не имеют самостоятельного значения и служат только для того, чтобы ограничить действие одной связки от другой. В этом плане использование здесь скобок аналогично их использованию в математике, где, например, запись “2 + 4  3” может иметь две различные трактовки (поскольку будут давать различный результат): 1) 2 + (4  3) и 2) (2 + 4)  3. Если же мы примем соглашение, что операция умножения является более сильной, чем сложение, то исходная запись будет соответствовать второй трактовке. Точно также для нашего символического языка имеется соглашение о ранге связок: самой сильной связкой является эквивалентность, а самой слабой – отрицание, которое будет включать в область своего действия или только элементарную формулу, или некоторую сложную формулу, но в этом случае оно должно стоять перед скобкой. Мы будем считать, что связки  и  имеют одинаковый ранг и при их совместном использовании всегда будут применяться скобки.

Сделаем некоторые пояснения относительно определения формулы. По своему характеру оно является индуктивным; второй пункт дает примеры сложных формул, а третий, обобщающий пункт поясняет, что пропозициональной формулой является или отдельно стоящая переменная (в этом случае она называется элементарной формулой), или некоторая последовательность символов, в которой имеются элементарные формулы и связки, которые (за исключением отрицания) всегда связывают две какие части. Части сложной формулы называются подформулами; для конъюнкции их принято именовать конъюнктами, для дизъюнкции — дизъюнктами. В импликации первая часть формулы называется антецедентом, вторая – консеквентом. Так, например, выражению “Пушкин в карты не играл, а если и играл, то без всяких фокусов” (М. Булгаков) будет соответствовать формула:

А  (А  В),

где переменная А означает “Пушкин играл в карты”, а переменная В – “Играл в карты без фокусов”. Основной связкой в этой формуле является конъюнкция. Второй конъюнкт – формула импликативная, он берется в скобки, чтобы ограничить действие импликации. (При отсутствии скобок в формуле основной связкой считалась бы импликация, что давало бы совершенно другое выражение – “Если Пушкин не играл в карты и Пушкин играл в карты, то играл в карты без фокусов”, в котором антецедент импликации представляет собой противоречие.)

Рассмотрим еще один пример. Для того чтобы представить в виде формулы нашего символического языка выражение “Что горяч ты – это хорошо, а вот еслив горяч, да с дуринкой, – это плохо” (В. Шукшин) нам потребуется три переменные: А – “Ты горяч”; В – “Это хорошо”; С – “Ты – с дуринкой” (здесь “это плохо” мы обозначим как отрицание “это хорошо”). Получим формулу:

(А  В)  (А  С  В),

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

2. Дедуктивную часть системы пропозициональной логики задается путем приведения списка аксиом системы и формулировки правил вывода. Мы сделаем это, следуя П.С. Новикову (Элементы математической логики. – М., 1973. С.72-73). Список аксиом системы включает четыре группы:

I (аксиомы для импликации)

1. А  (В  А)

2. (А  (В  С))  ((А  В)  (А  С))

II (аксиомы для конъюнкции)

1. А  В  А

2. А  В  В

3. (А  В)  ((А  С)  (А  В  С))

III (аксиомы для дизъюнкции)

1. А  А  В

2. В  А  В

3. (А  С)  ((В  С)  (А  В  С))

IV (аксиомы для отрицания)

1. (А  В)  (В  А)

2. А  А

3. А  А

Аксиомами являются исходные выводимые формулы, правильные (истинные) в силу своей структуры; давать содержательную интерпретацию переменным А, В и С нельзя, так как система должна “работать” в любой области знания.

Правилами вывода системы являются:

1. Правило подстановки:

Пусть И – формула, содержащая элементарную формулу А. Тогда, если И – выводимая формула, то заменив в ней формулу А, всюду, где она входит, произвольной формулой Б, также получим выводимую формулу.

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

1. А  (В  А) акс. I,1.

2. (А  С)  (В  (А  С)) подст. А/(А  С), 1.

Это правило можно записать символически:

И (А)

И (Б) ,

где горизонтальная черта называется “чертой вывода”.

2. Правило заключения (отделения):

Если И, И  Б, – выводимые формулы, то Б также является выводимой формулой. Символически:

И, И  Б

Б

Это правило было известно еще стоику Хрисиппу (ок. 350-260 до н. э.); в средневековой логике оно получило название “modus ponens”, так что применение этого правила часто обозначается буквами МР.

3. При формулировке правил вывода мы использовали буквы И, Б; введение последних связано с необходимостью проведения различия между “объектным языком” и “метаязыком”. Под объектным языком понимается тот символический язык, на котором “работает” наша формально-логическая система. В нашем случае он включает только пропозициональные переменные, связки и скобки. Метаязыком называется язык, с помощь которого формулируются формально-логические системы и анализируются их свойства. Метаязык включает в себя часть естественного языка (в нашем случае, это русский язык), метапеременные (И, Б), за которыми скрывается множество формул объектного языка, и другие символы. В частности, символическая запись правил вывода производится в метаязыке, из чего следует, что символы объектного языка (в нашем случае – пропозициональные связки) также могут быть элементами метаязыка.

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

И ├─ Б,

читается: “Из формулы И выводима формула Б” (или “Формула Б выводима из формулы И”). Эта запись означает, что существует некоторая конечная последовательность формул объектного языка, начальная из которых представлена формулой И, каждая последующая является или аксиомой, или формулой, полученной из предыдущих применением одного из правил вывода, а последняя формула представлена формулой Б.

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

├─ А  В  В  А,

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

1. (А  В)  ((А  С)  (А  В  С)) акс.II,3.

2. (А  В  В)  ((А  В  С)  (А  В  В  С)) подст. А/А  В, 1.

3. А  В  В акс.II,2.

4. (А  В  С)  (А  В  В  С) МР 2, 3.

5. (А  В  А)  (А  В  В  А) подст.С/А, 4.

6. А  В  А акс.II,1.

7. А  В  В  А МР 5, 6.

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

1. Если есть первое, то есть второе. Первое есть. Следовательно, есть и второе.

2. Если есть первое, то есть второе. Второго нет. Следовательно, нет и первого.

3. Или первое, или второе. Есть первое. Следовательно, нет второго.

4. Или первое, или второе. Нет первого. Следовательно, есть второе.

5. Первое и второе не могут быть вместе. Есть первое. Следовательно, нет второго.

Исторически первая аксиоматически построенная система пропозициональной логики была предложена Готтлобом Фреге в 1879 году в работе “Запись понятий”. Список аксиом системы включал шесть формул:

1. А  (В  А)

2. (А  (В  С))  ((А  В)  (А  С))

3. (А  (В  С))  (В  (А  С))

4. (А  В)  (В  А)

5. А  А

6. А  А

Правилами вывода системы являлись правило подстановки и правило заключения. В список аксиом системы вошли только формулы со связками импликации, которую Фреге называл “условностью”, и отрицания; системы, в которых используются только эти связки в получили название импликативно-негативных. Фреге использовал идеографическую символику, которая исключала использование скобок. Импликация (штрих условности) обозначась как т.е. “a  b”, а отрицание (a) как

Связки конъюнкции и простой дизъюнкции определялись через комбинацию связок импликации и отрицания:

для связки конъюнкции и для дизъюнкции.

Анализируя систему Фреге, польский логик Ян Лукасевич в 1934 году в статье “Из истории логики высказываний” писал: «Эта аксиоматическая система является полной: то есть, все правильные формулы пропозициональной логики могут быть получены из них посредством двух правил вывода. Она несовершенна только в “элегантности”: система не является независимой из-за третьей аксиомы, которая может быть доказана из первых двух» [Łukasiewicz J. Selected Works. Amsterdam; London, 1970. P.216]. То есть, на системы пропозициональной логики распространялась проблема независимости аксиом, которая впервые для формальных систем была сформулирована Д. Гильбертом (1862-1943) еще в 1899 году в работе “Об основаниях геометрии”.

Лукасевич не только модернизировал систему Фреге, сведя количество аксиом к трем (путем введения (В  А)  (А  В) вместо трех последних и исключения третьей аксиомы, не обладающей статусом независимости), но предложил также свою собственную систему из трех аксиом с теми же правилами вывода:

1. (А  В)  ((В  С)  (А  С))

2. А  (А  В)

3. (А  А)  А

Лукасевич (как и Фреге) использовал бесскобочный способ образования формул языка пропозициональной логики; при этом переменные обозначались малыми буквами латинского алфавита, а связки – большими буквами. Запись Rpq соответствует p º q в принятой нами символике, Cpq – p É q, Kpq – p & q, Apq – p Ú q, Np – Ø p. Так, например, формуле

p É Ø(q & r) & s

в польской школе (Львовско-Варшавская школа логики) будет соответствовать запись

CpKNKqrs.

Используемая нами символика ведет свое происхождение от трехтомной работы Б. Рассела и А. Уайтхеда “Principia Mathematica” (1910-1913), в которой за основу была взята символика итальянского математика и логика Дж. Пеано (1858-1932). В частности, это символы для импликации и дизъюнкции, хотя конъюнкцию Рассел обозначал через “точку” (A  B), а отрицание – через “”.

Система пропозициональной логики Рассела и Уайтхеда имела следующий список аксиом:

1. A Ú A É A

2. A É B Ú A

3. A Ú B É B ÚA

4. A Ú (B Ú C) É B Ú (A Ú C)

5. (B É C) É (A Ú B É A Ú C)

При этом импликация не являлась базисной связкой и определялась через дизъюнкцию и отрицание

A É B = ØA Ú B,

также как и конъюнкцию и эквивалентность:

A & B = Ø(ØA Ú ØB),

A º B = (A & B) Ú (ØA & ØB).

Система Рассела и Уайтхеда относилась к типу дизъюнктивно-негативных..

Аксиоматическая система пропозициональной логики для всех связок (кроме строгой дизъюнкции) была предложена Д. Гильберт и П. Бернайс [Гильберт Д., Бернайс П. Основания математики. Логические исчисления и формализация арифметики. М., 1979. С.94-97]. В их системе правилами вывода являлись правило подстановки и modus ponens, а список аксиом состоял из пяти групп. Аксиомы для конъюнкции, дизъюнкции и отрицания совпадают с аксиомами описанной нами системы; группа для импликации включала три аксиомы:

1. A É (B É A)

2. (A É (A É B)) É (A É B)

3. (A É B) É ((B É C) É (A É C))

Группа аксиом для эквивалентности также имела три аксиомы:

1. (A º B) É (A É B)

2. (A º B) É (B É A)

3. (A É B) É ((B É A) É (A º B))

Многообразие систем пропозициональной логики поставило проблему минимизации как выразительных возможностей, так и списка аксиом. Попытки решения этой проблемы способствовали, в свою очередь, постановке проблемы полноты формально-логической системы, которая трактуется в двух смыслах – широком и узком. «Логическое исчисление называется полным в узком смысле, если присоединение к его аксиомам какой-нибудь не выводимой в ней формулы приводит к противоречию» [Новиков П.С. Элементы математической логики. С.111]. Под проблемой полноты в широком смысле понимается постановка вопроса о том, достаточно ли аксиом и правил вывода формально-логической системы, для того чтобы вывести любую формулу, которая в содержательном плане считалась бы безусловной истиной. Проблема полноты в широком смысле оказывается связанной с решением проблемы разрешимости, которую можно сформулировать как вопрос: “Какие из правильно построенных формул являются доказуемыми в системе, а какие – нет?” То есть, нужно иметь эффективные средства для определения того, что некоторую формулу можно доказать в системе, хотя мы еще не имеем самой процедуры доказательства. Такие средства, как будет показано в следующей теме, существуют, что позволяет говорить о положительном решении проблемы разрешимости (а тем самым и полноты в широком смысле) для систем пропозициональной логики.

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

Задачи и упражнения к теме 2.

1. Запишите следующие высказывания в виде пропозициональных формул:

а) Если бы Иван Никифорович не сказал этого слова, то они бы поспорили между собой и разошлись, как всегда, приятелями; но теперь произошло совсем другое. (Н.В. Гоголь).

б) Необходимое и достаточное условие счастья для шейха состоит в том, чтобы иметь вино, женщин и услаждать свой слух пением.

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

г) Не покупай кота в мешке, если тебе не нужен мешок.

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

е) Кто хочет что-нибудь сделать – находит средства, кто не хочет ничего делать – находит оправдания.

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

з) Если я намереваюсь поехать в деревню тогда и толь­ко тогда, когда я сдам экзамен, то если я не сдам экзамен, то я останусь в городе.

и) Не разбираясь как следует в категориях, не оценишь должным образом самого себя (Л. Витгенштейн).

2. Исходя из следующих формул, сформулируйте высказывания, если переменная А означает: “Разбираешься как следует в категориях”, а переменная B – “Оцениваешь должным образом самого себя”:

а) А  В б) (A  B) в) B  A г) A  B

3. Пусть A означает: “Число a делится на число b”, B означает: “Число a делится на число c”, C означает: “Число a делится на произведение чисел b и c”. Сформулируйте высказывания, записанные в виде пропозициональных формул:

а) ØA & B б) Ø(A & B) в) A Ú ØB

г) Ø(ØA Ú B) д) A & B É C е) C É A & B

ж) A & B º C з) C º A & B и) Ø(A Ú ØB) É ØC

4. Исключите возможно большее число скобок в следующих формулах:

а) ((A Ú ((ØB) É (A & C))) º (B É (ØA)))

б) (((A & (ØB)) & C) É ((ØB) Ú A))

5. Восстановите скобки в следующих формулах:

а) C É Ø(A Ú C) & A º B

б) B & A É A º ØA Ú B

в) A  B Ú A  A & B  C

6. Запишите пять схем вывода Хрисиппа в метаязыке, с использованием принятой нами символики.

7. Исходя из идеографической символики Г. Фреге выразите в современной символике связки конъюнкции и простой дизъюнкции через импликацию и отрицание.

8. Покажите, что в системах Г. Фреге и Я. Лукасевича формула A É A является доказуемой.