Некоторые схемы доказательств

I. Простейшей схемой доказательства является цепь импликаций

из которой заключаем, что А => Н. Здесь А называется условием или посылкой, а Я — заключением, причем истинность посылки А в этой схеме не предполагается.

II. Вторая схема доказательств использует закон контрапозиции — (А=> В) = (-1 В =>—> А). С каждой теоремой А => В можно рассматривать еще три утверждения: 1) обратную теорему В => А, 2) противоположную теорему —iА => —>5, 3) теорему, обратную противоположной —? В => —А.

III. В схеме доказательства от противного используется равно сильность.

В традиционной логике такая схема доказательства называется сведе нием к абсурду.

IV. Эквивалентность А В высказываний А и В доказывается по одной из схем:

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

Существуют рассуждения традиционной логики, которые не могут быть обоснованы, формализованы в логике высказываний. Например, из двух высказываний-посылок: 1) А — всякое натуральное число есть число рациональное и 2) В — число 5 есть число натуральное, следует истинное высказывание-заключение С — число 5 есть число рациональное, таким образом А&В => С. Но в исчислении высказываний нет средств анализа таких умозаключений. Формализация умозаключений традиционной логики относительно связей между всеобщими и частными утверждениями и анализ таких умозаключений составляют предмет исследования в исчислении предикатов.

В исчислении предикатов имеется три сорта переменных. Высказывательная форма (см. и. 1.5) 5(х_|, х₂,…, х_А.) в этом исчислении называется^{-местной} предикатной переменной — предикатом. Аргументы предикатов называются предметными переменными. Множество их значений составляют имена предметов, объектов и т. п. Третий сорт переменных в исчислении высказываний составляют так называемые пропозициональные переменные, область значений которых образуют: а) высказывания, как О-месгные предикаты, и б) предикатные переменные.

Рис. 2.1.

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

Пример 2.3. Пусть двухместный предикат (иначе говоря — бинарный предикат) S (X, Y) определен условием.

[И, если X + Y >, 5(ДГ, К) = 1 Ес;

[Л, если X + Y < 1.

ли X и Y суть координаты точки М в плоскости XOY, го предикат S (M) = S (X, Y) описывает свойство точек М плоскости XOY находиться над прямой /г, заданной уравнением X + Y = 1 (S (Q) = И), или под этой прямой h (S (Р) = Л), как показано на рис. 2.1.

Замечание 2.1. Для точек М_а прямой /г, координаты х_а, у_а которых связаны равенством х_а + у_а = 1, бинарный предикат S (X, Y) не определен.

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

• а) простые предложения — все переменные, кроме предметных;
• б) сложные предложения, образуемые из простых предложений тремя следующими способами:
  • 1. Если S'(X|, x₂,…, x_i, x)-(к + 1)-местный предикат и а есть имя предметной переменнойх, тогда 5(х, х₂,…, х_А, а) есть^{-местный} предикат.
  • 2. Если S и Т суть предложения, тогда предложениями будут слова: —1S, S &Т, S v Т, S => Т, S Т, при этом в бинарных связках свободные переменные входят bSmT одновременно.
  • 3. Если S (x) есть предложение со свободной переменной х, то предложениями, но уже со связанной переменной х будут слова: Vx 5(х) и Зх S (x), значения которых определяются следующими двумя аксиомами:

Vx А (х) => A{t) и A (t) => Зх А (х).

В логике предикатов к правилам вывода исчисления высказываний добавляются два связанных с кванторами 3 и V правила вывода.

где переменная х не входит в В (а). В этих правилах в числителе стоит посылка, а в знаменателе — заключение.

Пример 2.4. (См. [15, с. 125]). Пусть S (a, b) есть бинарный предикат, определяющий отношение неравенства во множестве R действительных чисел, т. е. а <�Ь. Предикат S (a, b) удовлетворяет, в частности, двум аксиомам:

Аксиома 1. —S (a, a), т. е. а < а ложно.

Аксиома 2. S (a, b)&S (b, c)=> S (a, c), т. е. (а <�Ь и Ьа<�с.

Доказать, что -nS (b, a т. е. что b < а ложно.

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

• 1. Правило замены предметной переменной.
• 2. Правило разъединения посылок: (А & В => С) => (А=> (В => С)).
• 3. Тавтологию (А => В) о (—, В => —А).
• 4. Правило перестановки посылок: (А=>(В => С)) => (В => (А => С)).
• 5. Схему заключения (Л & (Л => В)) => В.

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

• 1-й шаг доказательства. Заменив в Аксиоме 2 с на а, получим импликацию S (a, b) & S (b, a) ^>S (a, a).

2- й шаг. Заменив в Правиле 2 А на S (a, /?), В на S (b, а) и С на S (a, а), получим следующие две импликации:

3- й шаг. Приняв в Правиле 3 S (b, а) за А и S (a, а) за В, из условия (*) получим условие:

4- й шаг. Применив Правило 4 к условию (**), получим:

5- й шаг. Подставив в Схему заключения 5 —? S (a, a) вместо А, (S (a, b) => —15(6, а)) вместо 5, и учитывая Аксиому 1, получим доказываемую формулу S (a, b) => —IS (b, a) M

Этот пример показывает, что получение даже простых заключений интерпретируемых теорий непосредственным применением правил вывода есть процедура громоздкая. Но именно с помощью таких процедур исчисления предикатов решаются в математической логике основные проблемы обоснования математики. Из других областей приложения математической логики можно назвать теорию алгоритмов, теоретическую кибернетику, теорию контактно-релейных схем и т. д. Подробности можно найти в книгах [10], [15], [19], [21], [33], [37], [39], [48], [53], [65], [76], [78, [88], [93].

Вопросы Читателю

• 1. Можно ли доказать основные законы традиционной логики? Если Ваш ответ да, тогда скажите, как это сделать?
• 2. Что общего у тавтологии и противоречия?
• 3. Какое значение должно принять высказывание В, чтобы высказывание (А => =>В) стало истинным?
• 4. Можно ли сократить количество независимых логических связок до одной? Ответ на этот очень трудный вопрос можно найти, например, в книге Э. Мендельсона [53].