Чистое исчисление предикатов

Лекция 1

Часть II. Логика предикатов и элементы теории алгоритмов

Вопросы и упражнения к Лекции 4.

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

2. Дайте другое (эквивалентное) определение понятия

непротиворечивой теории.

3. Сформулируйте теорему о полноте исчисления высказываний.

4. Почему исчисление высказываний является разрешимой теорией?

5. Если в пф входит 10 пп, то сколько строк будет в таблице

истинностности такой пф?

6. Почему система L непротиворечива?

7. Что такое полная формальная теория?

8. Опишите понятие независимой аксиомы (схемы аксиом) в данной

формальной теории.

9. Что такое многозначная логика?

10.Какая формальная теория называется подходящей для данной

многозначной логики?

1.1. Язык и формулы чистого исчисления предикатов. Вхождения переменных в формулы.

Как уже упоминалось в Части I, существуют такие виды логических рассуждений, которые не могут быть обоснованы в рамках исчисления высказываний. Внутренняя структура таких предложений другая. Необходимо также понимать такие выражения, как «все», «некоторый» и др. В пункте 1.1. Части I (далее 1.1.(ЧI)) мы уже описывали понятие «предикат» и «квантор» и выясняли смысл этих понятий. Теперь мы опишем на формальном уровне исходные понятия исчисления предикатов, которое есть расширение аксиоматической теории L. К символам, описанным в пункте 3.1.(ЧI), добавим символ ", предметные (индивидные) константы (т.к. у нас их не будет, то и никаких обозначений не вводим), предметные (индивидные) переменные (пп), предикатные буквы (прб) А_кⁱ, где к – нижний индекс - номер прб, а i – валентность (местность) прб. Функциональных букв у нас не будет и такое исчисление предикатов называется чистым. Прб с переменными и будут элементарными формулами (эф) (заметим, что прб без переменных (валентности 0) есть высказывание). Фл исчисления предикатов определяются так:

(а) всякая эф есть фл; (b) если А и В – фл, то (ØА), (А®В), ("yА) также есть фл; (с) выражение является фл только если это следует из (а) и (b).

В последней формуле из пункта (b) А называется областью действия квантора "y (А может и не содержать пп y). Квантор существования $xА(x) определяется как сокращённая запись

Ø"xØА(x). Оставляя в силе введённые ранее правила об опускании скобок, будем дополнительно считать, что кванторы "y и $y располагаются по силе между связками º,® и связками Ø, Ù, Ú. Пример: вместо (("xА(x))®В(x,y)) пишем "xА(x)®В(x,y); вместо ("x(А(x)ÚВ(x,y))) пишем "x(А(x)ÚВ(x,y)). Также, вместо нижних индексов просто употребляем разные прб, а верхние индексы опускаем, т.к. все пп, входящие в фл, пишем полностью.

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

Задача. В следующих трёх примерах А(x,y); А(x,y)®"xВ(x); "x(А(x,y)®"xВ(x)) укажите для всякого вхождения всякой пп каким это вхождение является.

Ответ: В первом примере обе переменные вхождят свободно. Во втором примере первое вхожденеи x и вхождение y – свободные, а второе вхождение x – связанное. В третьем примере все вхождения x – связанные, а y входит свободно.

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

В заключение данного раздела приведём несколько «текстовых» задач на логику предикатов.

1. Все учащиеся, пропускающие занятия, плохо сдают экзамены. Но т.к. некоторые учащиеся не пропускают занятий, то они хорошо сдают экзамены.

Ответ: Это не факт. Можно не пропускать занятий, но сдавать

экзамены плохо.

2. Верно ли, что существует такой человек, что если он пьёт, то пьют все? (принцип пьяницы!).

Ответ: К сожалению, это так. Решение см. ниже.

3. Верно ли, что существует такой человек, что если кто-нибудь пьёт,

то пьёт и он?

Ответ: И это то же верное утверждение.

Замечание Два последних вывода дают понять, что в классической

логике предикатов что-то не ладно по отношению к реальности!!

(см. конец лекции).

4. Все отличники получают стипендию. Ваня получает стипендию,

следовательно, Ваня отличник.

Ответ: Не верное заключение, см. 1.

5. Все спортсмены, играющие в хоккей, хорошо катаются на коньках.

Петя плохо катается на коньках, следовательно, Петя не играет в хоккей.

Ответ: Это так. Пора научиться кататься на коньках.

6. Все спортсмены, играющие в хоккей – смелые и отважные люди.

Коля не играет в хоккей, следовательно, Коля – трус.

Ответ: Да нет, он м.б. смелым и отважным; например, прыгать с

парашютом.

7. Некоторые студенты, которые часто болеют, пропускают много

занятий. Следовательно, любой студент, который не пропускает много занятий, болеет не часто (сами решите!)

8. Некоторые люди плохо плавают и плохо бегают. Тогда все люди, которые хорошо плавают, хорошо и бегают (сами решите!)

1.2 Интерпретации и модели.

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

Упражнения Предлагаем читателю рассмотреть на области натуральных чисел (без 0) следующие фл: (i) А(x,y); (ii) "yA(x,y); (iii) $y"xA(x,y), где А(x,y) интерпретируется как x£y и выяснить, какие отношения эти фл представляют (затем замените множество всех натуральных чисел на множество всех целых чисел и снова выясните, какие отношения эти же фл представляют).

Теперь мы определим понятия выполнимости и истинности, но не будем крайне формалистичны. Назовём оценкой любое отображение множества пп в область D. Определим значение фл А при оценке f индукцией по построению А. Если А(x₁, …,x_n) – эф и А интерпретируется как отношение А на Dⁿ, то подставим в А вместо переменных их значения при данной оценке f. Если при этом отношение А ( f(x₁),…f(x_n)) выполнено на D, то значение эф А(x₁, …,x_n) при оценке f равно 1, в противном случае значение эф А(x₁, …,x_n) при оценке f равно 0. Далее, значение фл при оценке определяется по индукции с помощью таблиц истинностности для пс. Значение фл ØА при оценке f есть Ø(значение фл А при той же оценке). Значение фл А®В при оценке f есть (значение фл А при f)®(значение фл В при f). Значение фл "xA(x,x₁,,x_n) при оценке f есть 1, если отношение А (d,f(x₁),…,f(x_n)) выполнено при любом d из D. Иначе значение фл "xA(x,x₁,,x_n) при оценке f есть 0.

Определение. Фл А истинна в данной интерпретации, если она выполнена при любой оценке f. Если формула не выполнена ни при одной оценке, то она называется ложной (в данной интерпретации). Следующие факты проверяются без труда: а) если фл А ложна в данной интерпретации, то фл ØА истинна в той же интерпретации и наоборот; в) никакая фл не может быть одновременно истинной и ложной в данной интерпретации; с) если фл А и А®В истинны в данной интерпретации, то фл В истинна в той же интерпретации; d) фл А®В ложна в данной интерпретации тогда и только тогда, когда фл А истинна, а фл В ложна в этой интерпретации; e) фл А истинна в данной интерпретации (т.е. при любой оценке!), когда фл "xА(x) истинна в той же интерпретации;

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

Задача. Проверьте пункты а) – g) самостоятельно.

Указание: вспомнить определение интерпретации.

Фл А называется общезначимой (озф), если она истинна в любой интерпретации. Фл А называется выполнимой (вф), если найдётся интерпретация, при которой она истинна. Следующие факты также доказываются без труда: а) А есть озф тогда и только тогда, когда фл ØА не является вф; в) А есть вф тогда и только тогда, когда фл ØА не является озф; с) зфл А выполнима тогда и только тогда, когда она истинна в какой-либо интерпретации.

Фл А – противоречие, если ØА – озф. Фл А влечёт фл В, если в любой интерпретации фл В истинна при всякой оценке, при которой выполнена фл А. Две фл эквивалентны, если каждая из них влечёт другую. Следующие факты докажите самостоятельно: а) фл А влечет фл В, если фл А®В озф; в) фл А и В эквивалентны, если фл АºВ озф; с) если фл А влечёт фл В и фл А истинна в данной интерпретации, то фл В истинна в той же интерпретации.

Задача. Докажите, что: а) всякий частный случай тавтологии есть озф (определение частного случая было дано выше); в) если фл А не содержит x свободно, то фл "x(A®B)®(A®"xB(x)) – озф; с) фл "xA(x)®A(y) – озф; d) фл "x$yA(x,y)®$y"xA(x,y) не является озф (рассмотрите подходящую интерпретацию для данной фл!).

Задача. Докажите, что фл ["xA(x)®"xB(x)] ®["x(A(x)®B(x))] не является озф; докажите также общезначимость таких фл:

а) "xA(x) ® $xA(x); в)"xA(x) º Ø$xØA(x);

c) "x(A(x)®B(x)) ® ("xA(x)® "xB(x));

d) ("xA(x)Ù"xB(x)) º "x(A(x)ÙB(x)) и тот же факт, но с заменой Ù на Ú;

e) $x"yA(x,y) ®"x$yA(x,y).

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

К схемам аксиом из пункта 3.1.(ЧI) А1-А3 добавим ещё две: А4. "xA(x)®A(y) и А5. "x(A®B(x)) ® (A®"xB(x)), где фл А не содержит пп x свободно. К правилам вывода из пункта 3.1.(ЧI) (МР) добавим такое правило вывода: фл "xА есть непосредственное следствие фл А (правило Gen – дженерализация или обобщение).

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

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

Тогда всякая теорема теории К истинна в той же интерпретации. Ограничения на пункты схем А4 и А5 необходимы. Пусть А(x) есть Ø"yB(x,y) и пп y не входит свободно в А(x). Рассмотрим частный случай схемы аксиом А4: "x(Ø"yB(x,y)) ® Ø"yB(y,y) и теперь в качестве интерпретации возьмём область D с не менее чем двумя элементами, а в качестве В – отношение тождества (совпадения). Тогда антецедент (посылка) нашего частного случая А4 истинен, а консеквент (сукцедент, заключение) – ложен. В схеме аксиом А5 отказ от ограничения также невозможен. Пусть А и В есть С(x) (теперь x входит в А свободно!). Рассмотрим такой пример схемы аксиом А5: "x(C(x)®C(x))®(C(x)®"xC(x)). Посылка примера общезначима, но если в нашей интерпретации С выполнено не для всех элементов области, то заключение не будет истинным.

Наряду с теорией К будем рассматривать теорию К₄, которая получается следующим образом: берем исчисление высказываний в форме L₄ (см. пункт 4.2.(ЧI) для определения (изменяется и язык!)) и добавляем в язык квантор существования $, а в качестве аксиом добавляем две схемы аксиом и два правила вывода (они известны как правила Бернайса). Схемы "xA(x)®A(y) и A(x)®$xA(x). Правила: если в К₄ выводима фл "x(B®A(x)), где пп x не входит свободно в В, то в К₄ выводима фл В®"xA(x) (правило В1); если в К₄ выводима фл "x(B(x)®A), то в К₄ выводима фл $xB(x)®A, где пп x не входит свободно в А (правило В2). В дальнейшем некоторые факты для К будут доказываться при нотации с квантором существования, однако в этих случаях этот квантор будет всегда выражен через квантор всеобщности так: $xA(x) = Ø"xØA(x).

Вопросы и упражнения к Лекции 1.

1. Какие вхождения пропозициональных переменных в формулу

называют связанными, а какие свободными?

2. Может ли одна и та же переменная входить в одну и ту же формулу

связанно и свободно? (этот вопрос задавался и ранее!).

3. О принципах пьяницы. Доказательства этих верных утверждений

связано с использованием закона исключенного третьего (зит). Зит

в ряде случаев плохо отражает реальную ситуацию. Однако (и это

очень спорный вопрос) он присутствует во всех математических

рассуждениях. Задачи про пьяниц решаются так: в силу зит либо

все пьют, либо это не верно. Если первое, тогда в качестве нужного

лица берём произвольного человека (ведь всё равно все пьют).

Если нет, то тогда найдётся непьющий человек Т.к. не верно, что

он пьёт, то отсюда следует, что если он пьёт, то пьют все. Вторая

задача решается совершенно аналогично.

4. Что такое интерпретация? Что такое оценка?

5. Что означает, что фл истинна в данной интерпретации при данной

оценке?

6. Что такое модель для чистого исчисления предикатов?

7. Что означает, что фл логики предикатов общезначима?

8. Дайте определение языка первого порядка.

9. Сформулируйте дополнительные схемы аксиом и дополнительные

правила вывода для исчисление К.

Дата добавления: 2014-01-06