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

Всякая аксиоматическая теория для своего обоснования требует рассмотренных четырех проблем:

1) проблемы разрешимости,

2) проблемы непротиворечивости,

3) проблемы полноты,

4) проблемы независимости.

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

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

Теорема 1. Проблема разрешимости для исчисления высказываний разрешима.

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

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

Теорема 2. Исчисление высказываний непротиворечиво.

3. Проблема полноты исчисления высказываний. Существует два понятия полноты − в узком смысле и в широком смысле.

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

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

Теорема 3. Исчисление высказываний полно в узком смысле.

Теорема 4. Исчисление высказываний полно в широком смысле.

4. Проблема независимости аксиом исчисления высказываний. Для каждого аксиоматического исчисления возникает вопрос о независимости его аксиом; а именно: нельзя ли какую-нибудь аксиому вывести из остальных аксиом, применяя правила вывода?

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

Аксиома называется независимой от всех остальных аксиом исчисления, если она не может быть выведена из остальных аксиом.

Система аксиом исчисления высказываний называется независимой, если каждая аксиома системы независима.

Теорема 5. Система аксиом исчисления высказываний независима.

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

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

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

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

О тесной взаимосвязи ТИФ и доказуемых формул свидетельствует

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

Таким образом, прямую и обратную теоремы о полноте в широком смысле кратко можно записать так:

следует , следует

Несмотря на то, что из теоремы 4 следует, что все аксиомы исчисления высказываний являются ТИФ алгебры логики, мы, тем не менее, это проверим.

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

1) I₁: ,т.е. получаем

2) II₁: т.е.

3) II₂: т.е.

4) III₁: , т.е.

5) III₂: ,т.е.

6) IV₂: , т.е.

7) IV₃: , т.е.

8)IV₁: т.е.

9) I₂:

т.е.

10) II₃:

, т.е.

11) III .

т.е

Таким образом, все 11 аксиом являются ТИФ в алгебре логики. В качестве аксиом могут быть выбраны и другие формулы. Так, известна и другая система из 10 аксиом, которая приводится ниже. Для различения аксиом этой системы и аксиом, рассмотренных выше, будем обозначать их так:

;

;

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

Сделаем это:

т.е.

[ ] ,т.е.

Последняя формула точно совпадает с третьей формулой для последовательности равносильных формул в I₂. Ее последующие преобразования показали, что она ТИФ. Следовательно, не продолжая дальнейшие преобразования, мы можем заключить, что и тоже является ТИФ.

Видим, что все аксиомы этой системы также являются ТИФ алгебры логики.

Использованием теоремы 4 о полноте исчисления высказываний в широком смысле может значительно упроститься процесс установления доказуемости формул. Действительно, тогда вместо того, чтобы искать некоторый вывод из совокупности формул, а затем по обобщенной теореме дедукции устанавливать доказуемость анализируемой исходной формулы, достаточно установить, является она ТИФ (общезначимой) или нет. Процесс же установления общезначимости формулы более определен, чем процесс установления доказуемости формул. Действительно, если установление общезначимости формулы путем алгебраических преобразований вызывает затруднения, то всегда для любой формулы можно построить таблицу истинности и по ней определить, является она общезначимой или нет (напомним, что формула будет общезначимой, если в последнем столбце её таблицы истинности будут стоять все единицы).

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

 

Вопросы для самоконтроля

1. Какая запись является формулой в исчислении высказываний?

2. Запишите аксиомы исчисления высказываний.

3. Сформулируйте правило подстановки и правило одновременной подстановки.

4. Сформулируйте правило заключения и правило сложного заключения.

5. Что понимается под термином «доказуемость» в исчислении высказываний. Дайте определение доказуемой формулы.

6. Сформулируйте и запишите правило силлогизма.

7. Сформулируйте и запишите правило контропозиции.

8. Сформулируйте и запишите правило снятия двойного отрицания.

9. Дайте определение выводимо формулы.

10. Что называется выводом из совокупности формул H?

11. Сформулируйте и запишите теорему дедукции.

12. Запишите обобщенную теорему дедукции и приведите ее доказательство.

13. Запишите правило введения конъюнкции.

14. Запишите правило введения дизъюнкции.

15. Перечислите четыре основных проблемы исчисления высказываний и прокомментируйте их.

16. Докажите тождественную истинность аксиомы I₂.

17. Докажите тождественную истинность аксиомы II₃.

18. Докажите тождественную истинность аксиомы III₃.

19. Докажите тождественную истинность аксиомы IV₄.

 

 

Логика предикатов

Понятие предиката

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

Часто это приводит к тому, что участвующие в логических операциях высказывания по смыслу могут быть совершенно не связанными между собой, и, тем не менее, полученные из них новые сложные высказывания будут правильными с точки зрения исчисления высказываний, хотя и абсурдными с точки зрения естественного языка. Так, например, высказывание “если число 15 делится на 3, то каждый день начинается с восхода солнца” является законным с точки зрения исчисления высказываний, но абсурдным с точки зрения естественного языка, так как составляющие его простые высказывания никак не связаны по смыслу (по содержанию).

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

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

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

Логика предикатов расчленяет простое высказывание на субъект (подлежащее, дополнение) и предикат (сказуемое, определение).

Субъект – это то, о чем что-то утверждается в высказывании. Предикат – это то, что именно утверждается о субъекте. Например, в высказывании “12 – составное число” “12” – субъект, “ составное число” – предикат. Это высказывание утверждает, что “12” обладает свойством быть составным числом.

Если в приведенном примере заменить конкретное число 12 переменной из множества натуральных чисел, то получим так называемую высказывательную форму: “ –составное число”. Обратим внимание, что в данном примере при замене числа 12 на мы получим повествовательное предложение, о котором не можем определенно сказать, истинно оно или ложно. Следовательно, это предложение не подпадает под определение высказывания, поэтому и говорят, что предложение имеет высказывательную форму, а соответствующее переменное называют высказывательным переменным (пропозициональным, об этом уже говорилось в подразд.2.1).

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

Из изложенного выше вытекают следующие определения.

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

Множество , на котором определен предикат , называется областью определения предиката.

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

Так, предикат – “ – составное число” определен на множестве (всех натуральных чисел), а множество для него есть множество всех составных чисел.

Другой предикат − “диагонали параллелограмма перпендикулярны” определен на множестве всех параллелограммов, а его множеством истинности является множество всех ромбов.

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

Определение 2. Предикат , определенный на множестве , называется тождественно истинным (тождественно ложным), если .

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

Здесь множество является частным случаем декартова произведениядвух множеств и .

Определение 3. Двухместным предикатом называется функция двух переменных и , определенная на множестве и принимающая значение из множества . Примерами двухместных предикатов являются: предикат равенства ─ “ ”, определенный на множестве действительных чисел , предикат делимости нацело ” ”, определенный на множестве .

 

Таким образом, предикат – это функция или, как мы уже говорили выше, высказывательная форма. Если, например, в высказывательную форму мы подставим вместо и какие-то конкретные значения, то высказывательная форма становится высказыванием, принимающим вполне определенные значения истины или лжи (1 или 0). Так, есть предикат (высказывательная форма), но уже является истинным высказыванием, а − ложным высказыванием. В то же время является высказывательной формой (предикатом), так как его значение истинности зависит от того, каким натуральным числом будет заменена переменная (т.е. является функцией от , а значит, предикатом). В то же время является высказыванием, причем истинным, так как любое делится на единицу.

Еще несколько замечаний о терминологии. Иногда вместо термина “ -местный предикат” употребляют термин “ -арный предикат”. При этот предикат называется унарным (от лат. unio ─ единение, единый), при − бинарным (от лат. binaries − двойной) и при − тернарным (от лат. tertia – третья).

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