27. Свойства выводимости

Пусть G - некоторое множество формул данной теории, A, В и C - произ-

вольные формулы той же теории. Рассмотрим некоторые свойства выводимо-

сти в формальных аксиоматических теориях.

1. Если G содержится в некотором множестве формул F и если G ├ A, то F ├

A.

Доказательство. Пусть A имеет вывод

А1,А2,...,Аn (1)

из гипотез G. Если некоторая формула Аi принадлежит G, то, очевидно, Аi ∈ F.

Следовательно, вывод (1) формулы А является выводом формулы А из

гипотез F. Что и требовалось доказать.

2. G ├ A тогда и только тогда, когда в G существует конечное подмноже-ство

Н такое, что Н ├ А.

Доказательство следует из определения вывода.

3. Пусть G ├ A и каждая формула В, принадлежащая G, выводима из не-

которого множества формул F, тогда F ├ A.

Доказательство. Пусть A имеет вывод

А1,А2,...,Аn (2)

из гипотез G. По определению вывода некоторые Аi из (2) могут принадлежать

G, но каждая формула из G, имеет вывод из F. Заменим в (2) все Аi,

принадле-жащие G, выводом Ai из F. В результате получим

последовательность формул:

B1,B2,...,Bm,

которая уже является выводом А из F. Что и требовалось доказать.

Как частный случай п.3 имеем:

3` . Если A ├ B и B ├ C, то А ├ C.

4. Если G,A ├ B и G ├ A, то G ├ B.

Доказательство. Пусть B имеет вывод

B1,B2,...,Bn (3)

из гипотез G и А, а формула А имеет вывод

А1,А2,...,Аm (4)

из гипотез G. В выводе (3) формулы В некоторые из Вi могут быть равны А.

Заменим такие Вi последовательностью (4). В результате получим последова-

тельность формул

C1,C2,...,Cr,

которая является выводом для В из гипотез G. Что и требовалось доказать.

42

31.(38) Логические функции

Функция P(х1,х2,..,хn), переменные которой имеют своими значениями

элементы некоторого множества D, обращаются в высказывания, для которых

n-элементов этого множества называются n-местным предикатом и n-местной

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

является значение предиката P(х1,х2,..,хn) его истинностное значение, можно

установить зависимость между предикатом и функцией. Dn-(это стрелка)

{1,0}. Функция вида Dn{1,0} называется n-местной логической функцией;

множество Dn-область определения логич. функции; {1,0}-область значений

логич. функции.

43

34. Кванторы

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

на M одноместный предикат. Тогда выражение

хР(х) читается: "для всех х Р(х)" или "для всех х выполняется ∀ Р(х)", или "для

любого х Р(х)", или "для каждого х Р(х)". Под выражением "∀хР(х)" будем

подразумевать высказывание истинное, когда Р(х) истинно для каждого х из

M и ложное - в противном случае. Символ ∀х называется квантором

всеобщности. Выражение

∃хР(х) читается "существует х такое, что Р(х)" или "хотя бы для одного х Р(х)",

или "для некоторого (некоторых) х Р(х)". Под выражением "∃хР(х)" будем

подразумевать высказывание, которое истинно, если Р(х) принимает

значение И хотя бы для одного значения переменной х∈ M, и ложно, если

Р(х) для всех значений переменной х принимает значение Л. Символ ∃х

называется квантором существования. Квантор ∃х будем называть

двойственным к квантору ∀х, и наоборот.

В литературе применяются и другие обозначения. Так, вместо ∀хР(х) пишут

ΛхР(х) или ΛхР(х), а вместо ∃хР(х) пишут VхР(х) или VхР(х), или ЕхР(х)

Введенные обозначения позволяют записывать предложения в

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

логических действий над этими предложениями. При символизации языка

требуется определенная аккуратность и правильное понимание контекста. В

естественном языке часто слово "все" опускается. Так, например,

предложение "рыбы дышат жабрами" означает, что все рыбы дышат жабрами

или что каждая рыба дышит жабрами. Поэтому при символизации

необходимо ввести квантор общности. Таким образом, если положить для

множества живых существ, что R(х) означает "х - рыба", а G(х) - "х дышит

жабрами", то имеем

∀х(R(х)⇒G(х)). Но в то же время не в каждом случае встречающиеся в

предложениях слова "все" понимаются как "каждый". Например, предложение

"все песчинки образуют кучи пуска" не означает, что каждая песчинка

образует кучи песка, следовательно, при символизации нельзя употреблять

квантор ∀х, как это сделано в предыдущем примере.В языке слово "все"

имеет два значения: "любой, каждый" и "все вместе". Квантор ∀х применяется

для первого значения.

Из изложенного следует, что "∀хР(х)" служит обозначением для следующих

высказываний:

для всех х выполняется (имеет место) Р(х);

для каждого х выполняется (имеет место) Р(х);

для любого х выполняется (имеет место) Р(х);

для произвольного х выполняется (имеет место) Р(х);

каково бы ни было х выполняется (имеет место) Р(х).

В языке слово "некоторый", так же как и "все", часто опускается. Например,

предложение "люди побывали на Луне" означает, что некоторые люди

побывали на Луне.

44

Символическая запись хР(х), как мы знаем, означает, ∃ что для некоторых х

имеет место Р(х), но не исключено, что и для всех х имеет место Р(х). В

естественном же языке слово "некоторый" иногда употребляют в смысле "не

все". Когда говорят "некоторые студенты отличники", подразумевают, что

некоторые, но не все студенты отличники. Следовательно, имеется в виду:

"неверно, что все студенты отличники, но некоторые - отличники". Тогда, если

С(х) означает "х - студент", О(х) означает "х - отличник", то получим:

(∀х(С(х) ⇒О(х))) &∃ х(С(х)&О(х)).

Итак, слово "некоторый" имеет два значения: первое - "некоторый, но может

быть и все", второе - "некоторый, но не все". Символ ∃х обозначает первое.

Следовательно, запись ∃хР(х) служит обозначением для следующих

высказываний:

для некоторых х (имеет место) Р(х);

существует х, для которого Р(х);

найдется х, для которого Р(х);

хотя бы для одного х (верно) Р(х);

имеется х, для которого Р(х).

Рассмотрим следующие часто встречающиеся предложения и справа от них

приведем их символическую запись:

(А) все S суть Р - ∀х(S(х) ⇒Р(х));

(Е) ни одно S не есть Р - ∀х(S(х) ⇒ Р(х));

(I) некоторые S суть Р - ∃х(S(х)&Р(х));

(О) некоторые S не есть Р - ∃х(S(х)& Р(х)).

Символизация приведенных предложений позволяет записывать в

символическом виде довольно сложные выводы, использующие

всевозможные комбинации предложений (А)-(О).

До сих пор мы рассматривали приписывание кванторов к одноместным

предикатам.

Далее рассмотрим приписывание кванторов к многоместным предикатам.

Пусть P(х1,х2,...,хn) -n-местный (n≥2) предикат, заданный на множестве M.

Выражение

∀хiР(х1,х2,...,хn), 1 ≤ i ≤ n, (2.1)

45