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

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].