Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Исходные символы языка логики предикатов




Исходные символы языка логики предикатов делятся на шесть групп:

V - множество предметных переменных, V={х1, x2, …, xn};

С - множество предметных констант, С={с12,...};

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. А(х12) - переменные х1 и х2 входят свободно;

2. А(х12)®$х1 В(х1) - первое вхождение переменной х1 свободно, второе - связано. Переменная х2 входит свободно.

3. "х2 (В (х12)®$х1А(х1)) - первое вхождение переменной х1 свободно, второе – связано, переменная x2 входит в формулу связанно.

Множество формул образует язык логики предикатов.

Поделиться:





Читайте также:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...