Язык логики предикатов

§4. Язык логики предикатов.

Пусть I, J, K – произвольные множества.

Рассмотрим алфавит V = V 1 È V 2 È V 3 È V 4 È V 5 È V 6, где

V 1 = {v0,v1,v2,…} - предметные переменные,

V 2 ={Pini}i Î I (ni Î N) - предикатные символы,

V 3 = {fjnj} j Î J (nj Î N) - функциональные символы,

V 4= {ak}kÎ K - предметные константы,

V 5 = {&, Ú , É , ù , " , $ } - логические символы,

V 6 = {,, (, )} - вспомогательные символы.

Pini – называется ni-местным предикатным символом, fjnj -- называется nj-местным функциональным символом, символ " называется квантором общности, а символ $ -- квантором существования. Названия остальных символов и сокращенные обозначения формул приведены в §1.

s = V 2 È V 3 È V 4 назовем сигнатурой. На дальнейшем зафиксируем некоторую сигнатуру s . Дадим определение терма сигнатуры s :

1. предметные переменные и предметные константы являются термами;
2. если
fn—п-местный функциональный символ из s и t1, …, tn—термы, то fn(t1, …, tn )-- терм;
3. никаких термов, кроме построенных по пп. 1), 2), нет.

1. атомная формула есть формула;
2. если Á и В – формулы, то ù Á
, (Á & B), (ÁÚB), (ÁÉB) -- подформулы;
3. если Á -- формула, а х – предметная переменная, то " хÁ
, $хÁ -- формулы (в этом случае " хÁ и $ хÁ называются областью действия квантора " х или $ х ); соответственно
4. никаких формул, кроме построенных по пп. 1)—3), нет.

Вхождение переменной х в формулу называется связанным, если оно находится в области действия квантора " х или $ х, и свободным в противном случае. Переменная х называется свободной переменной формулы Á , если в Á имеется свободное вхождение х , и связанной переменной формулы Á , если в Á имеется связанное вхождение х. Терм t называется свободным для переменной х в формуле Á , если никакое свободное вхождение х в Á не находится в области действия никакого квантора " у$ у, где у—переменная, входящая в t. Формула Á называется замкнутой формулой, или предложением , если всякое вхождение переменной в Á является связанным. или

Подслово формулы Á , которое само является формулой, называется подформулой формулы Á .

В дальнейшем используем символы x, y, z, x1, x2,… для обозначения предметных переменных, t1, t2,… для обозначения термов, Á , В - для обозначения формул. В случаях, когда речь идет о формуле Á и переменных х1,…, хп, используется также запись Á ( х1,…, хп). Если Á ( х1,…, хп) – формула, то через Á ( t1,…, tп) обозначаем результат подстановки термов t1,…, tп в Á вместо всех свободных вхождений переменных х1,…, хп.

Пусть М—непустое множество и Rn—некоторое п-местное отношение на М. п-местным предикатом на М, соответствующем отношению Rn, называется п-местная функция Рn из М в {и, л}такая, что для любых a1,… , anÎ M

Pn (a1,… , an) = u Û á a1,… , an ñ Î Rn.

Алгебраической системой Â = á М; s ñ сигнатуры s называется непустое множество М, где каждому п-местному предикатному (функциональному) символу из s сопоставлен п-местный предикат (функция) на М, а каждой предметной константе из s сопоставлен некоторый элемент из М. Предикаты (функции, элементы), сопоставленные символам из s , обозначаем теми же символами.

Алгебраическую систему Â = á М; s ñ называем моделью, если s не содержит функциональных символов.

Мощностью системы Â = á М; s ñ называется мощность множества М и обозначается через .

Пусть s 1 Í s 2. Â 1= á М; s 1ñ называется объединением Â 2= á М; s 2ñ , а Â 2 – обогащением Â 1 , если символы из s 1 интерпретируются одинаково в Â 1 и Â 2.

Пусть М1 Í М2. Система (модель) Â 1= á М1; s ñ называется подсистемой (подмоделью) Â 2= á М2; s ñ , а М2—расширением М1, если все символы из s интерпретируются одинаково в Â 1 и Â 2 на элементах из М1. Если М1¹ М2 , то подсистема (расширение, подмодель) называется собственной.

Пусть t – терм сигнатуры s , все переменные которого содержаться среди x1,…, xn , Â = á М; s ñ -- алгебраическая система. Значение терма t при значениях переменных m1,… ,mn Î M определяется по индукции:

1. если
t есть переменная xi (константа aj) , то значение t есть mi(aj);
2. если
t есть fn( t1,… , tn),а значения t1,… , tn суть b1,… , bn , то значение t есть fn( b1,… ,bn).

Формула Á (x1,…, xn) сигнатуры s , все свободные переменные которой суть x1,…, xn , называется истинной в Â = á М; s ñ при значениях переменных m1,… ,mn Î M соответственно, если предложение Á( m1,… ,mn) истинно в Â . В противном случае Á считается ложной в Â = á М; s ñ .