Исчисление предикатов первого порядка

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

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

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

К дедуктивным принципам введения кванторов относятся правила:

1.1. — введения квантора общности (обозначим символом «"_в»), выражаемое схемой:

А (x/ y, z₁, …, z_n)

^{______________________} , гдеy— абсолютное ограничение, z₁, …, z_n — ограничение.

"x A (x, z₁, …, z_n)

1.2. — введения квантора существования (обозначим символом «$_в»), выражаемое схемой:

А (x/ t)

^___________ .

$x А (x)

2.1.— исключения квантора общности (обозначим символом «"_и»), выражаемое схемой:

"x А (x)

^___________ .

А (x/ t)

2.2. — исключения квантора существования (обозначим символом «$_и»), выражаемое схемой:

$x А (x, z₁, …, z_n)

^{______________________} , гдеy— абсолютное ограничение, z₁, …, z_n — ограничение.

А (x/ y, z₁, …, zg_n)

В правилах «введения квантора существования» и «исключения квантора общности» запись A(x/t) означает результат правильного замещения термом t всех имеющихся в формуле A(x) свободных вхождений предметной переменной x.

 

v Пример

Пусть формула A(x) является записью выражения $x(P²(x,y)ÉQ²(x,z)). Допустим, что универсумом рассуждения является множество городов, вместо свободной переменной y подставляется терм — предметная постоянная, имеющая значение «Омск», вместо z — предметная постоянная, имеющая значение «Тара», и P² — предикаторная постоянная, имеющая значение «старше», а Q² — предикаторная постоянная, имеющая значение «моложе», тогда мы получаем правильную подстановку, поскольку суждение «Существуют города, такие что они старше Омска, но моложе Тары» истинно.

 

Но в силу того, что рассматриваемая формула $x(P²(x,y)ÉQ²(x,z)), являясь выполнимой, не является общезначимой формулой логики предикатов, можно осуществить и такую подстановку термов вместо свободных переменных y и z, что данная формула будет иметь всегда ложное значение.

Допустим, что универсумом рассуждения является множество людей, вместо свободной переменной y подставляется сложный функциональный терм, имеющий значение «являться отцом человека», вместо z — сложный функциональный терм, имеющий значение «являться предком человека», и P² — предикаторная постоянная, имеющая значение «младше», а Q² — предикаторная постоянная, имеющая значение «старше», тогда получаем неправильную подстановку, поскольку суждение «Существуют люди, такие что они старше отцов, но моложе потомков» является ложным всегда.

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

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

Запись А (x/ y, z₁, …, z_n) в правилах «введения квантора общности» и «исключения квантора существования» есть фиксация частного случая правильной подстановки предметной переменной y на место всех свободных вхождений предметной переменной x в выражении А (x, z₁, …, z_n).

Содержащиеся в правилах «введения квантора общности» и «исключения квантора существования» указания вида «y — абсолютное ограничение; z₁, …, z_n — ограничение» обусловлены тем, что с содержательной точки зрения свободные предметные переменные являются пробегающими по универсуму рассуждения (некоторого множества предметов), принимая в выбранном универсуме любые значения (в таком случае они используются в интерпретации всеобщности). Но будучи включёнными в состав формул логики предикатов предметные переменные иногда не выполняют данную роль, поскольку не выступают в качестве знаков, обозначающих именно любой объект универсума рассуждения (т. е. используются в интерпретации всеобщности). Таким образом, имеют место два возможных случая функционирования предметной переменной в составе формул.

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

 

v Пример

В выражении x + y = y + x, представляющем собой закон перестановочности сложения, переменные x и y употреблены в интерпретации всеобщности, так как это соотношение истинно при любых значениях x и y.

Другую ситуацию имеем в том случае, когда переменные входят в состав, например, математических уравнений. Так, в выражении x + 5 = 8 переменная x уже не используется в интерпретации всеобщности, так как не обозначает произвольный объект из универсума. Напротив, возможные значения для x строго фиксированы, т. е. ограничены условием данного утверждения. В этом случае говорят, что переменная использована в условной интерпретации.

 

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

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

Четвёртая эвристика заключается в применении первой и второй эвристик для выбора посылок после того, как применение всех шагов по первой эвристике привело к формуле вида "xA или $xA.

 

v Пример

Обоснованием утверждения о выводимости |- Ø$xØP(x,y,a)É"xP(x,y,a) будет:

 

_______ _______________________

1. Ø$xØP(x,y,a) — пос. (1 эвристика). 2. ØP(x,y,a) — пос. (4 эвристика). 3. $xØP(x,y,a) — $в, 2. 4. ØØP(x,y,a) — Øв, 1, 3. 5. P(x,y,a) — Øи, 4. 6. "xP(x,y,a) — "в, 5, x — абс. огр.; y — огр. 7. Ø$xØP(x,y,a)É"xP(x,y,a) — Éв, 6.

Контрольные вопросы

I. Каковы функции пропозициональных 1) переменных и 2) связок?

II. Что является законом классической логики высказываний?

III. В чём заключаются общие принципы построения истинностных таблиц?

VI. Каковы содержание и объём понятия формулы исчисления высказываний?

V. На какие виды подразделяются правила вывода логики высказываний?

VI. Какие эвристики и в какой последовательности применяют в выводах логики предикатов?

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

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

IX. Чем сходны и чем различаются классические исчисления логики предикатов и логики высказываний?

 

Варианты домашнего задания по разделу

«Логика высказываний и предикатов»

I. Определите табличным способом значения истинности суждений:

1. Если бы троллейбус №1 задерживался на остановках или ехал медленно, Олег непременно опоздал бы к началу семинара; но он успел, значит, троллейбус ехал быстро и не задерживался.

2. Данное число чётно, и число, большее его на единицу, чётно.

3. Эйфелева башня находится в Париже или она находится в Лондоне.

 

II. Подберите по два примера всех возможных модусов умозаключений:

1. Разделительно-категорических.

2. Условно-категорических.

3. Чисто разделительных.

 

III. Какие из следующих дилемм являются правильными?

1. Если будешь во время сплошного пожара на нижних этажах небоскрёба спускаться по лестнице, то сгоришь, если же выпрыгнешь в окно, то разобьёшься. Получается, что, не спускаясь по лестнице во время сильного пожара на нижних этажах небоскрёба или не выпрыгивая в окно, не сгоришь или не разобьёшься.

2. Если философ дуалист, то он не материалист. Если философ диалектик, то он не метафизик. Этот философ материалист или метафизик. Значит, он не дуалист или не диалектик.

 

IV. Определите тип формулы и решите методом «от противного», являются ли данные формулы тождественно-истинными:

1. (pÉ(qÉp)).

2. (p&q)Éq.

3. ((pÚq)Ép)).

4. (pÉØq)É(ØpÉq).

 

V. Осуществите доказательство формул:

1. (Ø(xÚy)É(ØxÙØy)).

2. $xA(x)ÉØ"xØA(x).

3. Ø$xA(x)º"xØA(x).

4. Ø"xA(x)º$xØA(x).

 

VI. Определите, являются ли термами следующие выражения:

1. f²(g²(a, b)).

2. P¹(f¹(a, b)).

3. f³(a, b, c).

 

VII. Определите, являются ли следующие выражения формулами, и укажите в формулах связанные и свободные вхождения переменных:

1. P(a, a).

2. $x(P(x)ÉQ(x, a)).

3. "xÉ(P¹(y)ÙQ³(x)).

 

VIII. Запишите на языке логики предикатов первого порядка выражение:

1. Существуют люди, любящие всяческие удовольствия больше, чем некоторых друзей.

2. Некоторые зайцы — белые, но этот заяц — не белый.

3. Всякий учёный знает какую-нибудь науку.

4. Он уверен в себе и непоколебим, значит, его планы осуществятся.

5. Не всякий довод является неложным и подтверждает тезис пропонента.

 

IX. Установите область интерпретации значений дескриптивных постоянных, а также значение свободных переменных, при которых приведённые ниже формулы 1) истинны, 2) ложны:

1. "y(P²(y, x)ÉQ²(y, z)).

2. $x"yR(x, y)É"y$xR(x, y).

3. $x"yP²(x, y).

4. "y$xR(x, y)É$x"y R(x, y).

5. "y(P³(y, x, z)ÉQ²(y, z)).

6. "x(P(x)ÉØQ(x))ÉØ$x(P(x)ÙQ(y)).

 

Список рекомендуемой литературы

1. Бочаров В. А., Маркин В. И. Основы логики: Учеб. — М.: ИНФРА-М, 2002. — 296 с.

2. Брюшинкин В. Н. Практический курс логики для гуманитариев. — М.: Новая школа, 1996. — 320 с.

3. Войшвилло Е. К., Дегтярев М. Г. Логика: Учеб. для вузов. — М.: Гуманит. изд. центр ВЛАДОС, 1998. — 528 с.

4. Клини С. К. Математическая логика. — М.: Мир, 1973. — 480 с.

5. Лихтарников Л. М., Сукачёва Т. Г. Математическая логика: Курс лекций. Задачник-практикум и решения. — СПб.: Изд-во «Лань», 1999. — 288 с.

6. Серебрянников О. Ф. Эвристические принципы и логические исчисления. — М.: Наука, 1970. — 283 с.

7. Такеути Г. Теория доказательств. — М.: Мир, 1978. — 412 с.

8. Формальная логика / Под ред. И.Н. Бродского и И.Я. Чупахина. — Л.: Изд-во ЛГУ, 1977. — 360 с.

ЧАСТЬ IV

ТЕОРИЯ ПРАВДОПОДОБНЫХ

РАССУЖДЕНИЙ

Введение

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

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

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

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

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

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

Глава девятая