Логіки першого порядку, Детальна інформація

Реферат на тему:

Логіки першого порядку

На рівні логік предикатів 1-го порядку функції та предикати в загальному випадку розглядаються як квазиарні, композиціями таких логік є логічні зв’язки, операції квантифікації та суперпозиції. Назва “логіка 1-го порядку” зв’язана з тим, що квантори застосовуються тiльки до імен компонентів даних (предметних iмен). Обмежимося розглядом логік з фінарними функціями та предикатами, яка по суті є класичною логікою предикатів 1-го порядку. При цьому операції суперпозиції задаваються неявно, в стилі класичної логіки. Моделями такої логіки предикатів 1-го порядку є математичні структури дуже загального вигляду \xF02D алгебраїчні системи (скорочено АС).

1. АЛГЕБРАЇЧНІ СИСТЕМИ

Алгебраїчною системою назвемо об’єкт вигляду A=(A, FnA (PrA), де A \xF02D непорожня множина, яку називають носiєм, або основою АС, FnA та PrA \xF02D множини функцiй та предикатiв, заданих на A.

Нехай \xF073 \xF02D\xF020 довільна множина така, що існує тотальне однозначне відображення I: ((FnA,(PrA. Елементи множини \xF073 трактуватимемо як імена деяких функцій та предикатів із FnA(PrA. Такі імена нази-вають функціональними символами (ФС) та предикатними символами (ПС), іменовані ними функції та предикати називають базовими. Множину \xF073 функціональних та предикатних символів називають сигнатурою. Нехай Fs – множина функціональних символів, Ps – множина предикатних символів. Тоді сигнатура \xF073=Fs(Ps.

АС iз носiєм A та сигнатурою \xF073=Fs(Ps назвемо АС з доданою сигнатурою [18]. Такі АС позначатимемо у вигляді A = (A, I, (), або A = (A, (), якщо I. мається на увазі.

Для кожного g(Fs функцію G(FnA таку, що I(g)=G, назвемо значенням ФС g при інтерпретації I на АС A=(A, FnA (PrA), та позначатимемо таку функцію gA Предикат P(PrA такий, що I(p)=P, назвемо значенням ПС p при інтерпретації I на АС A, та позначатимемо такий предикат pA . Якщо функція gA є функція-константа на A, ФС g називають константним символом.

Обмежимося розглядом алгебраїчних систем фінарних функцій та предикатів, причому базові функції та предикати п-арні. Тому вважаємо, що з кожним ФС та ПС зв’язане натуральне число \xF02D арність такого символа. При цьому для кожного h(\xF073 арність hA pівна арності символу h.

АС B=(B, I, () назвемо розширенням АС A=(A, I, (), якщо A(B і для всіх h(\xF073 та а(А маємо hA (hВ . В цьому випадку АС A називають підсистемою АС B, а B називають підсистемою АС A. Цей факт позначатимемо A (B.

Нехай A=(A, (). Множина С(А утворює підсистему C=(C, () алгебраїчної системи A = (A, (), якщо C замкнена відносно базових функцій fA , де f(\xF073.

Hе для кожної С(А можна говорити про підсистему (C, ().

Наприклад, для АС (N, (), де (={+, =}, а символи + та = інтерпретуються природним чином, множина непарних чисел Nн (N незамкнена відносно +, тому Nн не утворює підсистеми. В той же час множина парних чисел Nп (N утворює власну підсистему (Nп , () системи (N, ().

Нехай множини А1 ( А та А2 ( А замкнені відносно всіх базових функцій АС (A, (). Тоді А1(А2 теж замкнена відносно всіх базових функцій АС (A, (), якщо тільки А1(А2 ((. Отже, якщо (A1, () та (A2 , () \xF02D підсистеми системи (A , (), то (А1(А2 , () або підсистема системи (A , (), або (.

Підсистему (А1(А2 , () назвемо перетином підсистем (A1, () та (A2 , ().

Теорема 1.1. Перетин М носіїв всіх підсистем системи (A, () або утворює підсистему (М, (), або є (.

Така підсистема (М, () називається найменшою підсистемою системи (A , ().

Зрозуміло, що якщо сигнатура ( містить константні символи, АС (A , () має найменшу підсистему.

, де (={((( | В(А(}, є найменшою множиною, замкненою відносно всіх базових функцій системи A=(A, (). Така С визначає АС (С, (), яку називають підсистемою системи (A, (), породженою множиною В.

Якщо при цьому С=А, то кажуть, що АС (A, () породжується підмножиною В(А. Зрозуміло, що різні підмножини можуть породжувати одну і ту ж підсистему.

Приклад 1. Підсистема (Z+, {1, +, =}) системи (N, {1, +, =}) породжується довільною підмножиною иножини Z+, яка містить 1. Найменшою такою підмножиною є {1}.

Приклад 2. Система (N, {+, =}) породжується множиною {0, 1}.

Приклад 3. Система (N, {0, 1, +, (, =}) породжується множиною {0, 1}. Наявність константних символів 0 та 1 приводить до того, що в кожній підсистемі такої системи носій містить 0 та 1, але тоді підсистема співпаде з усією системою. Отже, вказана система власних підсистем не має.

Приклад 4. Система (Z+, {+, =}) має підсистеми (kZ+, {+, =}), де kZ+={kx | x(Z+}, для довільних k(Z+.

2. МОВИ 1-го ПОРЯДКУ

Для опису алгебраїчних систем використовуються мови логіки предикатів 1-го порядку, або просто мови 1-го порядку.

Алфавiт мови 1-го порядку складається iз таких символiв:

\xF02D предметнi імена (змiннi) x, y, z,...;

\xF02D функцiональнi символи f0, f1, f2,... заданої арностi;

\xF02D предикатнi символи p0, p1, p2,... заданої арностi;