Исходные символы языка логики предикатов
Исходные символы языка логики предикатов делятся на шесть групп: V - множество предметных переменных, V={х1, x2, …, xn}; С - множество предметных констант, С={с1,с2,...}; S-множество логических связок, S={0,1, &, Ú, ®, «, ", $}; здесь 0 и 1 - логические символы, означающие «ложь» и «истина», & - символ конъюнкции или логического умножения, Ú -дизъюнкция или логическое сложение, Ø - символ логического отрицания, ® символ импликации или логического следования, «- символ эквивалентности; F-множество функциональных символов, F= ; - mi -местная функция; R-множество предикатных символов, - mi-местный предикатный символ. множество вспомогательных символов {, (,) }. В языке логики предикатов определяется понятие предметной области D такой, что "сÎС: с есть наименование объекта в предметной области D; хÎV, означает, что х «пробегает» весь диапазон возможных значений из D. Установление связи между элементами языка логики предикатов и предметной областью D производится с помощью функции интерпретации I. Функциональные символы из множества F суть операции над некоторыми операндами, определенными над предметной областью D. Предикатные символы есть отношения, определенные также в предметной области D. Сигнатурой языка LS называется множество S=CÈFÈR, если · FÇR=Æ, · "fÎF $m (m: F®N); · "rÎR $m (m: R®N), т.е. отображение m ставит в соответствие каждому функциональному символу и каждому предикатному символу натуральное число, являющееся местностью этого функционального или предикатного символа. Иначе, m(f) и m(r) - есть число аргументов функционального или предикатного символа. Например, если f(2) есть«+», т.е. f(x,y)=х+у, то m(f)=2; если f = Sin (х), то m(f)=1.
Если предикатный символ r есть < в выражении вида х<у, то m(r)=2. Мощность множества RÈF называется мощностью сигнатуры S. Алгебраической системой сигнатуры S, обозначается M=(D,S) называется упорядоченная пара, содержащая непустое множество D (предметную область) и объекты сигнатуры S, если каждому n-местному предикатному (функциональному) символу из S сопоставлен n-местный предикат (функция) той же местности на D, а каждой предметной константе из S сопоставлен некоторый элемент из D. Если сигнатура не содержит функциональных символов, то алгебраическая система называется моделью. Множество D называется несущим множеством алгебраической системы. Пусть S1 Í S2, тогда модель Ф1= (D; S1) называется обеднением модели Ф2=(D; S2), и, соответственно, Ф2 есть обогащение Ф1, если интерпретация всех символов сигнатуры S1 совпадает с интерпретацией этих символов в сигнатуре S2. При необходимости в модели, может указываться конкретная функция интерпретации для каждого предикатного символа сигнатуры. Кроме перечисленных исходных символов в логике предикатов рассматриваются еще две категории выражений: термы и формулы. Термы и формулы Термы являются аргументами предикатных символов. Понятие терма сигнатуры S определяется индуктивно: всякая предметная переменная хÎ V и всякая константа сÎ С являются термом; если t1,t 2,...,t n - термы, а fÎF, f- функциональный символ местности n сигнатуры S, то выражение вида f (t1,t 2,...,t n) является термом. других термов нет. Терм называется постоянным (основным, замкнутым), если он не содержит переменных, и параметрическим - в противном случае. Например, переменные х, у и константы 2, е, p- термы, выражения ln(sin (х+у)), ех - термы. Индуктивное определение формулы: · предикатный символ r (t1,t 2,...,tr)ÎR, где t1,t 2,...,t n -термы сигнатуры S, есть атомная формула или атом;
· если А и В - формулы, то АÚВ, А&В, А®В, А«В, ØА – формулы; в общем случае формула может быть образована любыми логическими связками, определенными в логике высказываний; · если А(х) – формула, то выражения "хА(х) и $хА(х) - формулы. Здесь "х, $х называются кванторными приставками, х - переменная кванторной приставки, А(х) - область действия кванторной приставки; в этих случаях говорят, что переменная х входит в формулу связанно, или что имеет место связанное вхождение переменной х; · других формул нет. Формула А называется постоянной или предложением, если она не содержит свободных вхождений переменных. В противном случае формула называется параметрической или условием. Одна и та же переменная может входить в формулу как связанно, так и свободно. Например, 1. А(х1,х2) - переменные х1 и х2 входят свободно; 2. А(х1,х2)®$х1 В(х1) - первое вхождение переменной х1 свободно, второе - связано. Переменная х2 входит свободно. 3. "х2 (В (х1,х2)®$х1А(х1)) - первое вхождение переменной х1 свободно, второе – связано, переменная x2 входит в формулу связанно. Множество формул образует язык логики предикатов.
Читайте также: A- выдвижение кончика языка к верхней губе Воспользуйтесь поиском по сайту: ©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|