Логика предикатов

Для определения понятия предиката рассмотрим следующие примеры.

Примеры.

1. Пусть N – множество натуральных чисел, и буквой P обозначено свойство натурального числа быть простым. Если x представляет собой произвольный элемент из N, тогда выражение «натуральное число x является простым», которое можно записать в виде P(x), уже не является высказыванием, т.к. значение истинности данного утверждения зависит от x. По существу P(x) означает переменное (неопределенное) высказывание, которое становится определенным, когда x заменено определенным элементом из N. Например, P(3) = 1, P(4) = 0. Иначе говоря, P(x) представляет собой функцию, определенную на множестве натуральных чисел и принимающую только два значения: 0 и 1.

2. Пусть Z – множество целых чисел и P – свойство пары чисел иметь одинаковый знак. Тогда P(x,y) будет означать: «целые числа x и y имеют одинаковый знак». Это неопределенное высказывание становится определенным, если x и y заменить конкретными числами. Например, P(2,3)=1, P(-1,5)=0. Неопределенное высказывание P(x,y) представляет собой функцию двух переменных.

3. Пусть A и B – множество точек, C – множество прямых на евклидовой плоскости, а P(a,b,c) обозначает: «прямая c проходит через точки a и b». В этом примере мы имеем дело с функцией трех переменных, причем a и b принимают значения из множества точек, а c принимает значения из множества прямых евклидовой плоскости.

Определение 1. Предикатом называется функция, отображающая множество произвольной природы во множество {0,1}, или (ложно, истинно).

Обратимся теперь к определению предиката в общем случае.

Определение 2. Пусть N={N₁,N₂,N₃,…,N_n} – конечный набор множеств. Всякая функция P(X₁,…,X_n), ставящая в соответствие каждому набору из n элементов {a₁,a₂,…,a_n), где a_iÎN_i, какой-либо из элементов булевой алгебры {0,1} называется n-местным предикатом на N. Множество N_i называется предметной областью для переменной x_i. Переменные x₁,…,x_n называются предметными переменными. Некоторые из множества N_i могут совпадать.

Если при отображении P образом набора (a₁,a₂,…a_n) является единица, то записывают.

P(a₁,…,a_n)=1

и говорят, что значение предиката P для набора (a₁,…,a_n) является истинным. Если же образом (a₁,…,a_n) является нуль, то записывают

P(a₁,…,a_n)=0

и говорят, что значение предиката P для набора (a₁,…,a_n) является ложным.

n – местный предикат при n = 1 называется унарным, при
n = 2 – бинарным и при n=3 тернарным. Для общности введем еще понятие 0-местного предиката, а именно, 0-местным предикатом называется любе истинное или ложное высказывание.

Поскольку предикаты принимают значения из (0,1), то над ними можно производить все логические операции, рассматриваемые нами в алгебре высказываний (-, Ù, Ú, ®, «), сохраняя за ними те же определения. Кроме операций алгебры высказываний, мы будем употреблять еще две новые операции, которые связаны с особенностями предикатов и выражают собой утверждения всеобщности и существования.