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

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

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

V - множество предметных переменных, V={х₁, x₂, …, x_n};

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

S-множество логических связок, S={0,1, &, Ú, ®, «, ", $}; здесь 0 и 1 - логические символы, означающие «ложь» и «истина», & - символ конъюнкции или логического умножения, Ú -дизъюнкция или логическое сложение, Ø - символ логического отрицания, ® символ импликации или логического следования, «- символ эквивалентности;

F-множество функциональных символов, F= ; - m_i -местная функция;

R-множество предикатных символов, - m_i-местный предикатный символ.

множество вспомогательных символов {, (,) }.

В языке логики предикатов определяется понятие предметной области D такой, что "сÎС: с есть наименование объекта в предметной области D; хÎV, означает, что х «пробегает» весь диапазон возможных значений из D. Установление связи между элементами языка логики предикатов и предметной областью D производится с помощью функции интерпретации I.

Функциональные символы из множества F суть операции над некоторыми операндами, определенными над предметной областью D.

Предикатные символы есть отношения, определенные также в предметной области D.

Сигнатурой языка L_S называется множество S=CÈFÈR, если

· FÇR=Æ,

· "fÎF $m (m: F®N);

· "rÎR $m (m: R®N),

т.е. отображение m ставит в соответствие каждому функциональному символу и каждому предикатному символу натуральное число, являющееся местностью этого функционального или предикатного символа. Иначе, m(f) и m(r) - есть число аргументов функционального или предикатного символа. Например, если f⁽²⁾есть«+», т.е. 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 называется несущим множеством алгебраической системы.

Пусть S₁Í S₂, тогда модель Ф₁= (D; S₁) называется обеднением модели Ф₂=(D; S₂), и, соответственно, Ф₂ есть обогащение Ф₁, если интерпретация всех символов сигнатуры S₁ совпадает с интерпретацией этих символов в сигнатуре S₂.

При необходимости в модели, может указываться конкретная функция интерпретации для каждого предикатного символа сигнатуры.

Кроме перечисленных исходных символов в логике предикатов рассматриваются еще две категории выражений: термы и формулы.

Термы и формулы

Термы являются аргументами предикатных символов. Понятие терма сигнатуры S определяется индуктивно:

всякая предметная переменная хÎ V и всякая константа сÎ С являются термом;

если t₁,t₂,...,t _{n -}термы, а fÎF, f- функциональный символ местности n сигнатуры S, то выражение вида f (t_1,t₂,...,t _n) является термом.

других термов нет.

Терм называется постоянным (основным, замкнутым), если он не содержит переменных, и параметрическим - в противном случае.

Например, переменные х, у и константы 2, е, p- термы, выражения ln(sin (х+у)), е^х - термы.

Индуктивное определение формулы:

· предикатный символ r (t₁,t₂,...,t_r)ÎR, где t₁,t₂,...,t _n -термы сигнатуры S, есть атомная формула или атом;

· если А и В - формулы, то АÚВ, А&В, А®В, А«В, ØА – формулы; в общем случае формула может быть образована любыми логическими связками, определенными в логике высказываний;

· если А(х) – формула, то выражения "хА(х) и $хА(х) - формулы. Здесь "х, $х называются кванторными приставками, х - переменная кванторной приставки, А(х) - область действия кванторной приставки; в этих случаях говорят, что переменная х входит в формулу связанно, или что имеет место связанное вхождение переменной х;

· других формул нет.

Формула А называется постоянной или предложением, если она не содержит свободных вхождений переменных. В противном случае формула называется параметрической или условием.

Одна и та же переменная может входить в формулу как связанно, так и свободно. Например,

1. А(х₁,х₂) - переменные х₁ и х₂ входят свободно;

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

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

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

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒