WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Логіки першого порядку - Реферат

Логіки першого порядку - Реферат


Реферат на тему:
Логіки першого порядку
На рівні логік предикатів 1-го порядку функції та предикати в загальному випадку розглядаються як квазиарні, композиціями таких логік є логічні зв'язки, операції квантифікації та суперпозиції. Назва "логіка 1-го порядку" зв'язана з тим, що квантори застосовуються тiльки до імен компонентів даних (предметних iмен). Обмежимося розглядом логік з фінарними функціями та предикатами, яка по суті є класичною логікою предикатів 1-го порядку. При цьому операції суперпозиції задаваються неявно, в стилі класичної логіки. Моделями такої логіки предикатів 1-го порядку є математичні структури дуже загального вигляду алгебраїчні системи (скорочено АС).
1. АЛГЕБРАЇЧНІ СИСТЕМИ
Алгебраїчною системою назвемо об'єкт вигляду A=(A, FnA PrA), де A непорожня множина, яку називають носiєм, або основою АС, FnA та PrA множини функцiй та предикатiв, заданих на A.
Нехай довільна множина така, що існує тотальне однозначне відображення I: FnA, PrA. Елементи множини трактуватимемо як імена деяких функцій та предикатів із FnA PrA. Такі імена нази-вають функціональними символами (ФС) та предикатними символами (ПС), іменовані ними функції та предикати називають базовими. Множину функціональних та предикатних символів називають сигнатурою. Нехай Fs - множина функціональних символів, Ps - множина предикатних символів. Тоді сигнатура =Fs Ps.
АС iз носiєм A та сигнатурою =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 називають константним символом.
Обмежимося розглядом алгебраїчних систем фінарних функцій та предикатів, причому базові функції та предикати п-арні. Тому вважаємо, що з кожним ФС та ПС зв'язане натуральне число арність такого символа. При цьому для кожного h арність hA pівна арності символу h.
АС B=(B, I, ) назвемо розширенням АС A=(A, I, ), якщо A B і для всіх h та а А маємо hA hВ . В цьому випадку АС A називають підсистемою АС B, а B називають підсистемою АС A. Цей факт позначатимемо A B.
Нехай A=(A, ). Множина С А утворює підсистему C=(C, ) алгебраїчної системи A = (A, ), якщо C замкнена відносно базових функцій fA , де f .
Hе для кожної С А можна говорити про підсистему (C, ).
Наприклад, для АС (N, ), де ={+, =}, а символи + та = інтерпретуються природним чином, множина непарних чисел Nн N незамкнена відносно +, тому Nн не утворює підсистеми. В той же час множина парних чисел Nп N утворює власну підсистему (Nп , ) системи (N, ).
Нехай множини А1 А та А2 А замкнені відносно всіх базових функцій АС (A, ). Тоді А1 А2 теж замкнена відносно всіх базових функцій АС (A, ), якщо тільки А1 А2 . Отже, якщо (A1, ) та (A2 , ) підсистеми системи (A , ), то (А1 А2 , ) або підсистема системи (A , ), або .
Підсистему (А1 А2 , ) назвемо перетином підсистем (A1, ) та (A2 , ).
Теорема 1.1. Перетин М носіїв всіх підсистем системи (A, ) або утворює підсистему (М, ), або є .
Така підсистема (М, ) називається найменшою підсистемою системи (A , ).
Зрозуміло, що якщо сигнатура містить константні символи, АС (A , ) має найменшу підсистему.
Нехай {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в:
предметнi імена (змiннi) x, y, z,...;
функцiональнi символи f0, f1, f2,... заданої арностi;
предикатнi символи p0, p1, p2,... заданої арностi;
символи логiчних операцiй , та .
В множині Fs може виділятися підмножина константних символів Сп Fs. Символ рівності завжди інтерпретуватиметься як предикат рівності, причому таку рівність трактуватимемо як тотожність.
Символи , , , = та предметнi імена називають логiчними символами, функцiональнi та предикатнi символи називають нелогiчними символами. Множину функцiональних та предикатних символів =Fs Ps називають сигнатурою мови 1-го порядку.
Основними конструкціями мови 1-го порядку є терми та формули. Терми використовують для позначення, назви суб'єктiв, формули для запису тверджень про суб'єкти.
Індуктивне визначення терма таке:
1) кожне предметне ім'я та кожна константа є термом; такі терми назвемо атомарними;
2) якщо t1,..., tn терми, f n-арний функцiональний символ, то ft1...tn терм.
Атомарною формулою називається вираз виду pt1...tn, де p - n-арний предикатний символ, t1, ..., tn терми.
Індуктивне визначення формули таке:
1) кожна атомарна формула є формулою;
2) якщо та формули, то та формули;
3) якщо формула, x предметне iм'я, то x формула.
Аналогiчно мовi ЛВ, вирази & , та вважаємо вiдповiдно скороченнями формул , та . Користуємося також символом , вважаючи вираз x скороченням формули x .
Для бiнарних функцiональних та предикатних символiв i символiв , &, та звичайно застосовуємо iнфiксну форму запису. Прiоритет символiв логiчних зв'язок вважаємо нижчим за прiоритет предикатних символiв, а прiоритет предикатних символiв нижчим запрiоритет функцiональних символiв. Використовуючи додатковi символи кому , і дужки ( та ), для термiв вигляду ft1...tn вживатимемо скорочення f(t1...tn), або t1ft2, якщо символ f бiнарний. Те ж для атомарних формул. Для атомарних формул вигляду =t1 t2 вживатимемо скорочення t1 t2.
Скорочення термiв та формул будемо називати просто термами та формулами. Множини термів та формул мови 1-го порядку звичайно позначатимемо вiдповiдно як Тr та Fr. Формули мови 1-го порядку сигнатури називатимемо формулами 1-го порядку сигнатури .
Можна вказати 2 рiвнi вiдмiнностi мов 1-го порядку:
1) варiанти мови одної сигнатури, що вiдрiзняються наборами символiв логiчних операцiй та способами запису термiв i формул;
2) iстотно рiзнi мови, що вiдрiзняються сигнатурами.
Мова 1-го порядку L' сигнатури ' називається розширенням мови 1-го порядку L сигнатури , якщо '
Loading...

 
 

Цікаве