ЛМвИИ (1086253), страница 8
Текст из файла (страница 8)
Хотя в логике слово "предикат"употребляется в более общем смысле, чем в грамматике, где оно выражает только то, чтоговорится о субъекте.Пусть задано множество V={v1, v2, …, vK , ...}, в котором v1, v2 и т.д. - какие-то объектыиз этого множества. Обозначим любой предмет из этого множества через х и назовем xпредметной переменной. Тогда высказывания об этих предметах обозначим через Р(v1), Q(v1, v2)и т.д., причем такие высказывания могут быть как истинными, так и ложными. Например, еслиV={1, 2, 3, ...}, то высказывание "4 есть четное число" является истинным, а "7 есть четноечисло" - ложным.
Если вместо конкретных чисел 4, 7 подставим предметную переменную х, тополучим предикат их есть четное число", обозначаемый Р(х). Таким образом, предикат намножестве V есть логическая функция, определенная на V, при фиксировании аргументовкоторой она превращается в высказывание со значениями {И, Л}.В приведенном примере имеемлогическую функцию Р(x), определенную на множестве V и принимающую значения: И, Л. Вобщем случае через Р(x1, x2, …, xn) обозначим n-местный предикат. Приписав значенияпеременным x1, x2, …, xn из соответствующих областей определения, получим высказывание созначениями {И, Л}.Определим синтаксис логики предикатов первого порядка.• Алфавит1. Предметные переменные x, y, z, ...
и предметные константы a, b, c, ...2. Функциональные константы или имена функций f1, f2, ...3. Предикатные константы или имена предикатов Pn, QK, Rj, ...4. Логические операторы (логические связки) ¬, ^(&), v, →, ↔, ⊃.5. Символы кванторов ∀, ∃.• Термы1. Всякая переменная или константа есть терм.2. Если t1, t2, …, tn - термы и fin - функциональная n-местная константа, тоfin(t1, t2, …, tn) - терм.
Здесь верхний индекс определяет количество аргументов.Если переменные терма t содержатся среди переменных списка x1, …, xs. То пишемt(x1, …, xS).3. Никакие другие выражения не являются термами.•••Атомы1. Если t1, …, tm - термы и Рm -m-местная предикатная константа, то Рm(t1, …, tm) - атом.При m=0 предикат Р() обращается в высказывание Р. Атомом является такжеравенство, т.е. выражение типа (s=t), где s и t - термы.2. Никаких других атомов нет.•Формулы:Формулы (или правильно построенные формулы ППФ) определяются следующимобразом:1. Если t1, …, tK - термы, {x1, …, xm} - множество всех переменных, входящих в термы;Р - предикатная переменная, то Р(t1, …, tK) - элементарная формула (атом), а{x1, …, xm} — все её свободные переменные.2. Всякий атом есть формула.3.
Если А и В - формулы, а x - свободная переменная, то ¬A, AvB, A^B, A→B, A↔B,∀xA, ∃xA - формулы.4. Никаких других формул нет.В пределах формализма логики предикатов первого порядка запрещено использованиепредикатов в качестве термов, навешивания кванторов на предикатный символ.Предикат P(t1, t2 , …, tn ) служит для выражения свойства объекта (при n=1) и отношениймежду объектами (при n≥2). Атомарная формула Р(a1, a2 , …, an ) истинна в некотором "мире"(M), если между объектами в М имеется отношение, соответствующее P.Связывание свободной переменной происходит либо квантификацией (взятиемквантора по этой переменной) либо присвоением значения.Например:n∑ 2i: n - свободная переменная, i-связанная;t =1∀xP(x, y) : х - связанная переменная, у — свободная;(х=а)Р(х) : х - связанная переменная.Если предметные переменные определены на конечной области, то операциюнавешивания кванторов можно выразить через операции конъюнкции и дизъюнкциисоответственно.Пусть x 1 ∈{a 1 , a 2 , ...
, a m }, тогда ∀x1P(x1, …, xn ) =Р(a1, x1, …, xn )^Р(a2, x1, …, xn )^...^Р(am , x1, …, xn ),∃x1P(x1, x2, …, xn ) = Р(a1, x1, …, xn )vР(a2, x1, …, xn )v...vР(am , x1, …, xn ); в частном случае∀хР(х) = P(a1)^P(a2)^...^P(am ),∃хР(х) = P(a1)vP(a2)v...vP(am).Говорят, что квантор связывает соответствующую переменную. Предикат (формула)называется замкнутым, если связаны все переменные (если нет свободных, т.е. несвязанныхпеременных).1.2.3.4.Примеры.Термами являются:a) переменные: х, фамилия, число, буква;b) константы: С, Дейкстра, 94, ъ;c) функции max(x, y, z), ∑(x, y) или более традиционное представление - (х+у).Термами не являются выражения:a) Р(х) - так как Р - символ, зарезервированный для предиката;b) (х>0) - так как это отношение ( т.е. с точки зрения логики -одноместный предикат);c) х:=а - специфическая операция в программировании.Формулами являются:a) Р(х)=(х>0), выше(x, y) или в более традиционном представлении (х выше у);b) формулы, полученные из атомарных ¬Р(х), ∀хР(х), P(x)→Q(x, y),∀x∃yQ(x, y)v¬zR(x, z), (х выше y)^(y выше z)→(х выше z).4.
Формулами не являются:a) (а+b) - поскольку это терм;b) (а+b)^(с-d) - здесь два терма, соединенные логическими символами;∀P∃xP(x) - поскольку здесь квантор ∀ навешен на символ предиката ( этовыражение могло бы служить примером формулы в языке второго порядка).Из интуитивного понимания квантификации вытекает, что имеется связь междувхождениями переменной, содержащейся в квантификации. Так, в формуле ∀x(P(x)→Q(x))переменная x связана. Связь вводится первым вхождением, которое следует за кванторомобщности.Область действия некоторой квантификации есть формула, к которой применяется этаквантификация.
Переменная x в кванторах ∀x и ∃x называется квантифицированной. Каждоевхождение переменной х в область действия этой квантификации является связанным.Вхождение переменной х свободное, если оно не является ни квантифицированным, нисвязанным.В формулах ∃хА и ∀хА область действия х есть А. Если х и y - переменные, то областидействия x и y либо не пересекаются, либо одна включает другую. Рассмотрим примеры:∀x[P(x, a)→∃xQ(x)],∀xP(x, a)→∃xQ(x),∀xP(x, a)→Q(x).В первом случае две квантификации по одной переменной перекрываются. Такой типформул исключим из рассмотрения, придерживаясь правила введения кванторов: ∃xA и ∀хA формулы только в том случае, если х - переменная и А - формула, не содержащая связанныхвхождений х.Во втором случае две связанные переменные случайно получили одинаковое имя.В третьем случае и связанная переменная и свободная получили одно имя. Следовалобы сразу переименовать, например, связанную переменную: ∀yP(y, a)→Q(x).c)Пример.2.2.
Интерпретации. Модели.Формулы исчисления предикатов (как и формулы исчисления высказываний) могутбыть интерпретированы, т.е. могут получить некоторое значение истинности.Однако составные части формул исчисления предикатов являются не толькоформулами, но и термами. Поэтому необходимо интерпретировать еще и термы.
Интуитивнотерм означает объект. Тогда интерпретация должна указывать множество объектов, называемоеобластью интерпретации.Интерпретация /есть тройка (S, Ic, Iv ), где:• S - непустое множество (область интерпретации);• Ic - функция, сопоставляющая каждой n-местной функциональной константе f функциюIc(f) из Sn в S. Она также каждой m-местной предикатной константе Р ставит всоответствие функцию Ic(P) из Sm в {И, Л}.• Iv - функция, сопоставляющая каждой переменной какой-то элемент из S.Необходимо ввести еще обозначение, которое послужит для интерпретации двух видовквантифицированных формул.
Если I - некоторая интерпретация с областью SI , x - переменная иd - элемент из SI то Ix/d означает такую интерпретацию J, что Sj=SI , Jc=Ic, Jv(x)=d, Jv(y)=Iv(y) длявсех переменных у, отличных от х. Теперь для каждой интерпретации I=(S, Ic, Iv) можно задатьтакие правила интерпретации, которые каждой формуле А сопоставляют значение истинностиI(A) и каждому терму t сопоставляют элемент I(t) из S. Эти правила интерпретации образуютсемантику языка логики предикатов первого порядка.Семантика.•••••••Если х - переменная, то I(х)=Iv(х) (по определению).Если f - n-местная функциональная константа и t1, …, tn -термы, то I(f(t1, …, tn )) =Ic(f)(I(t 1), ..., I(tn)) (по определению).Если Р - m-местная предикатная константа и t1, …, tn - термы, то I(P(t1, …, tn ) =Ic(P)(I(t 1), …, I(tn)) (no определению).Если s и t - термы, то I(s=t) есть И, если I(s)=I(t), в противном случае — Л.Если А и В - формулы, то ¬A, (А^В), (AvB), (A→B) и (А↔В) интерпретируются так же,как и в исчислении высказываний.Если А - формула и x - переменная, то I(∀xA) есть И, если Ix/d(A) есть И для всехэлементов d из S.Если А - формула и x - переменная, то I(∃хА) есть И, если Ix/d(A) есть И хотя бы дляодного d из S.Формула А исчисления предикатов первого порядка называется истинной приинтерпретации f, если I(А)=И.Говорят, что терм t свободен для переменной х в формуле Р, если ни х, ни произвольнаяпеременная из t не квантифицированы в Р.
При этом через Px/t обозначается формула,полученная из Р путем одновременной замены всех вхождений х на t. Формула называетсязамкнутой, если в ней нет несвязанных (свободных) переменных.Замкнутая формула, истинная в любой интерпретации называется общезначимой.Замкнутая формула, ложная при всех интерпретациях, называется невыполнимой, а истиннаяпри некоторых интерпретациях - выполнимой.Мы определили семантику формул логики предикатов первого порядка, основанную напонятии интерпретации. Теперь определим семантику, опираясь на понятии модели. Этипонятия отличаются лишь видами используемых словарей и обозначениями.Моделью М логики предикатов первого порядка называется пара (S,V), где S - областьинтерпретации и V - функция, совпадающая с функцией интерпретации I.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
