Логика и аргументация: Учебное пособие для вузов.

Рузавин Георгий Иванович

Чаще всего кванторы общности и существования встречаются вместе. Например, чтобы выразить символически утверждение: "Для каждого действительного числа х существует такое число у, что х будет меньше у", обозначим предикат "быть меньше" символом <, известным из математики, и тогда утверждение можно представить формулой: (х) (Еу) < (х, у). Или в более привычной форме: (х) (Еу) (х < у). Это утверждение является истинным высказыванием, поскольку для любого действительного числа х всегда существует другое действительное число, которое будет больше него. Но если мы переставим в нем кванторы, т.е. запишем его в форме: (Еу) (х) (х < у), тогда высказывание станет ложным, ибо в переводе на обычный

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

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

1. Законы перестановки кванторов:

(х) (у) А ~ (у) (х) А;

(Ех) (Еу) А ~ (Еу) (Ех) А;

(Ех) (у) А ~ (у) (Ех) А;

2. Законы отрицания кванторов:

¬ (х) А ~ (Ех) ¬ А;

¬ (Ех) А ~ (х) ¬ А ;

3. Законы взаимовыразимости кванторов:

(х) А ~ ¬ (Ех) ¬ А;

(Ех) А ~ ¬ (х) ¬ А.

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

4.3. Исчисление предикатов

Построение исчисления предикатов осуществляется, с одной стороны, аналогично построению исчисления высказываний, а с другой - качественно отличается от него.

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

Прежде всего в исчислении предикатов используются кванторы. Кроме того, для определения истинности пропозициональной функции необходимо установить определенное соответствие между функцией и теми независимыми переменными (аргументами), которые составляют область ее определения (универсум рассуждения). Например, если универсум для отношения х < у составляет множество пар целых положительных чисел, то для определения значения истинности этого отношения необходимо установить соответствие (функцию) между любой парой чисел х и у из универсума и отношением х < у. Очевидно, что при х = 2 и у = 3 высказывание, полученное путем подстановки этих чисел в формулу, будет истинным, а при х=5 и у=3- ложным.

Функция, которая соотносит независимым переменным из ее универсума соответствующее значение истинности или ложности, называют логической, интерпретационной или семантической.

В общем случае, если предикат Р зависит от п индивидных (предметных) переменных, т.е. Р (x¹, х²,..., xⁿ), то каждой n-ке переменных из универсума семантическая функция будут соотносить значение "истина" или "ложь". Если n=0, мы получим отдельное, нерасчлененное высказывание (законы исчисления

таких высказываний рассматривались в предыдущей главе). Следовательно, исчисление высказываний может быть получено в качестве частного случая исчисления предикатов, а тем самым устанавливается связь между ними. При n = 1, т.е. Р(х), предикат является свойством, при n = 2, 3, 4 получаем бинарные, тернарные и тому подобные отношения.

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

(х) А и (Ех) А,

где А, как обычно, обозначает любую формулу предметного языка.

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

Опираясь на эти определения, мы можем теперь вычислить таблицу истинности для произвольной формулы, например, формулы, универсум которой состоит всего из двух объектов: 1 и 2.

Чтобы вычислить истинностные значения, например, формулы

Р(у) v (х) (Р(х) -> Q).

необходимо учесть определенное распределение, состоящее из семантической функции для Р(х), значения истинности подформулы Q и значения для свободной переменной у. В связи с этим на входах таблицы истинности для рассматриваемой формулы будут три величины. Но предварительно следует выписать список четырех (2²) распределений значений истины семантической функции одной переменной для универсума |1, 2| (табл. 12).

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

Этот пример показывает, что построение таблицы истинности для исчисления предикатов составляет несравненно более трудную задачу, чем построение таблицы для исчисления высказываний. В самом деле, если универсум рассуждения будет состоять из 10 элементов, то для этого придется построить 210 = 1024 семантические функции только для одной независимой переменной, а число строк в таблице в огромной степени возрастает по мере усложнения формул. В нашем примере речь шла только о двух объектах универсума рассуждений, а формула была крайне проста. Поэтому к таблицам истинности в исчислении предикатов обращаются главным образом для иллюстраций, используя для этого весьма простые формулы с крайне ограниченным универсумом рассуждений.

Тем не менее аналогия с исчислением высказываний оказывается весьма полезной для объяснения таких понятий, как общезначимая (или тождественно истинная) формула исчисления предикатов и логическое следование в этом исчислении. Формула А считается общезначимой в исчислении предикатов, если при всяком выборе универсума рассуждений (области ее значений) столбец ее значений в таблице будет состоять только из истин. Если универсум будет фиксирован, то формула называется общезначимой только в этом универсуме.