Определение предиката

Пусть Х₁, Х₂, ..., Х_п произвольные переменные. Эти переменные будем называть предметными. Пусть наборы переменных выбираются из множества X, которые будем называть предметной областью. Предикатом местности n (n - местным предикатом), определенным на предметной области X, называют отображение множества X во множество высказываний. Обозначение: P( )- n - местный предикат, определенный на X:=( ).

Пример: «х простое число».

Это выражение не является высказыванием, но если в нем переменную х заменить на определенное число, то получим высказывание. Причем при замене хна число 3 получим истинное высказывание, тогда как при замене х на 8 получим ложное высказывание.

Таким образом, выражение: «х простое число» можно рассматривать как функцию Р(х), зависящую от переменной х. Область определения Р(х) — множество чисел, а область значения — высказывание.

Предикаты - отображения произвольных множеств во множество высказываний. Пусть х₁,х₂, . . . , х_n - произвольные переменные. Эти переменные будем называть предметными. Пусть наборы переменных х₁,х₂, . . . , х_n выбираются из множества X, которые будем называть предметной областью.

Предикатом местности n (n-местным предикатом), определенным на предметной области X, называют отображение множества X во множество высказываний.

Обозначение: P(х₁,х₂, . . . , х_n) - n-местный предикат, определенный на X:={х₁,х₂, . . . , х_n}.

Дадим другое определение предиката.

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

Примеры.

1) Р(х₁, х₂) "Натуральное число х₁ делится (без остатка) на натуральное число х₂" - двуместный предикат, определенный на множестве пар натуральных чисел (х₁, х₂ N ). Очевидно Р(4, 2) =1; Р(5, 3) = 0

2) Р(х) = “x² < -1, xR” - одноместный предикат, определенный на R.

Ясно, что Р(-1) = 0 и вообще предикат P(x) - тождественно ложен, т.е. Р(x) = 0

3) Р(х, y, z) = “x² + y² ≤ z, x,y,xR” - трехместный предикат, определенный на R³. Р(1, 1, -2) = 0, Р(1, 1, 2) = 1

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

С помощью формальных теорий можно описать обширный класс высказываний, называемых предикатами. Дадим определение исчисления предикатов как формальной теории, а затем подробно остановимся на интерпретации.

Определение 1 (предиката). Функция Р(х₁, ... ,х_п), определенная на некотором множестве М и принимающая одно из двух значений: И (истина) или Л (ложь):

Р: М → {И, Л},

называется п-местным предикатом.

Произвольная функция Р: Мⁿ→В, заданная на произвольном множестве М, называется n-местным предикатом Р(х₁, х₂, . . .,x_n), т.е. Р задает семантическую характеристику.

Формальная теория S = <A, F, Р, R> называется исчислением предикатов первого порядка, если заданы алфавит, формулы, аксиомы и правила вывода.

1. Алфавит А:

х, у, z... — предметные переменные, принимающие конкретные значения из некоего множества D. Тогда х₀, y₀, z₀... — значения предметных переменных, т.е. предметные постоянные (константы);

р, q, r ... — переменные высказывания, принимающие два значения: 1 (истина) и 0 (ложь). Тогда p₀, q₀, r₀... — фиксированные значения;

Р, Q, F — переменные, символизирующие само высказывание; Р₀, Q₀( ) — постоянные предикаты;

— символы логических операций; дополнительно используются символы ;

— кванторы общности и существования;

служебные символы ), ( — нужны для установления порядка выполнения связок и области действия кванторов;

можно использовать также знаки ! — единственность, : — «такой, что...» и другие символы метаязыка. Например, .

2. Формулы: F:

переменные есть формулы;

если А, В — формулы, х — переменная, то А(х), , , и — формулы.

3. Аксиомы:

исчисления высказываний:

Р₁: ;

Р₂: ;

Р₃: ;

кванторные:

Р₄: ;

Р₅: .

4. Правила вывода:

R₁ : modus ponens;

R₂: введение квантора общности;

R₃: введение квантора существования.

Построенная формальная теория S описывает весьма общие объекты, поэтому нужно ее интерпретировать в то, с чем можно работать.

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

Пример. О высказывательной форме «Он получил специальность программиста» нельзя сказать, истинна она или ложна, пока не произведена замена местоимения «он» на существительное: «М. А. Иванов стал программистом» (истинно), «Дом стал программистом» (ложно).

Далее подробно опишем все составляющие формальной теории исчисления предикатов в такой интерпретации.

Чтобы задать п-местный предикат Р(х₁, х₂, ..., х_п), следует указать множества Х₁, Х₂, ..., Х_п — области изменения переменных х₁, х₂, ..., х_п, причем чаще всего рассматривается случай, когда Х₁ = Х₂ = ...= Х_п.

С теоретико-множественной точки зрения предикат определяется заданием подмножества М в декартовом произведении X₁ x Х₂ x ... x Х_п.

Переменные х₁, х₂, ..., х_п называются предметными переменными. Элементы множеств Х₁, Х₂, ..., Х_п называются предметами. Множество М — множество кортежей длины п <х₁, х₂, ..., х_п> называется полем предиката Р(х₁, х₂, ..., х_п).

Будем обозначать предметные переменные малыми буквами конца латинского алфавита (иногда будем снабжать эти буквы индексами) x, y, z, …, х₁, х₂, ..., х_п .

Предметы из множеств Х₁, Х₂, ..., Х_п — малыми буквами начала латинского алфавита а, b, с, ..., a₁, a₂, …

Предикаты — большими буквами латинского алфавита с приписанными предметными переменными или без них А(х, х). В, F(x, y), Р(х₁, х₂, ..., х_п).

Число переменных будем указывать как верхний индекс у предиката: Р^k(х₁, х₂, ..., х_k) — k-местный предикат,Q²(x, у) — двуместный предикат, Р(х) — одноместный предикат.

Итак, k-местный предикат — Р^k(х₁, х₂, ..., х_k) есть функция, предметные переменные которой принимают значения из некоторого множества М_k, а сама она принимает только два значения: истина (1) или ложь (0), т.е.