Кванторы и предикаты

ЛОГИКА ПРЕДИКАТОВ

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

Кванторы и предикаты

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

1) " -”любой”. Выражение " х Р(х) читается как: ” Для любого х справедливо Р(х) ”,

2)$ -”существует”. Выражение $ х Р(х) означает:” Сущест-вуют х , для которых справедливо Р(х) ”.

Замечание. Квантор $ можно было бы не вводить, по-скольку выражение $ х Р(х) является сокращенной записью выражения Ø (" х) Ø (Р(х)) - ” Не для любого х справед-ливо отрицание Р(х) ”.

Для того, чтобы оперировать с отдельными элемента-ми множеств вводится обобщение понятия высказывания - предикат.

Определение. Пусть задано некоторое множество объектов М. Предикатом (логической функцией ) P (`x ⁿ ) = Р(х ₁, ... , х _n) называется высказывание-функция, в кото-ром переменные в наборе (х ₁, ... , х _n ) принимают значения из М , а Р принимает на наборах ( х ₁, ... , х _n ) значения “истина” (И = 1) либо “ложь” (Л = 0).

Определение. Предикат с n переменными называется n - местным.

Определение. Областью истинности предиката Р на-зывается множество значений переменных (х ₁, ... , х _n ), на котором Р = 1.

Рассмотрим действие предикатов на конечных мно-жествах. Пусть М является конечным множеством эле-ментов: М = {a₁ , . . . , a_m }, Р(х) - предикат на М . Тогда справедлива следующая