Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

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

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

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

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

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

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

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

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

Примеры.

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

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

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

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

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

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

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

Р: М → {И, Л},

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

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

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

1. Алфавит А:

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

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

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

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

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

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

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

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

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

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

3. Аксиомы:

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

Р1: ;

Р2: ;

Р3: ;

кванторные:

Р4: ;

Р5: .

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

R1: modus ponens;

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

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

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

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

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

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

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

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

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

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

Предметы из множеств Х1, Х2,..., Хп — малыми буквами начала латинского алфавита а, b, с,..., a1, a2, …

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

Число переменных будем указывать как верхний индекс у предиката: Рk1, х2,..., хk) — k- местный предикат, Q2(x, у) двуместный предикат, Р(х) одноместный предикат.

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





Дата публикования: 2014-11-04; Прочитано: 667 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.01 с)...