Головна Головна -> Реферати українською -> Математика -> Логіки першого порядку

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

Назва:
Логіки першого порядку
Тип:
Реферат
Мова:
Українська
Розмiр:
65,99 KB
Завантажень:
64
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2 
На рівні логік предикатів 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 – множина предикатних символів. Тоді сигнатура FsPs.

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

Для кожного gFs функцію GFnA таку, що 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,), якщо AB і для всіх 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, ).

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ональних та предикатних символів FsPs називають сигнатурою мови 1-го порядку.

Основними конструкціями мови 1-го порядку є терми та формули. Терми використовують для позначення, назви суб’єктiв, формули для запису тверджень про суб’єкти.

Індуктивне визначення терма таке:

1) кожне предметне ім’я та кожна константа є термом; такі терми назвемо атомарними;

2) якщо t1,..., tn терми, f n-арний функцiональний символ, то ft1...tn  терм.

Атомарною формулою називається вираз виду pt1...tn, де p - n-арний предикатний символ, t1, ..., tn терми.

Індуктивне визначення формули таке:

1) кожна атомарна формула є формулою;

3. ЕКВІВАЛЕНТНІ ПЕРЕТВОРЕННЯ ФОРМУЛ

Тeорeма 3.1 (семантична тeорeма єквiвалeнтностi). Нeхай A’ отримана iз формули A замiною дeяких входжeнь формул B1, ..., Bn на P1, ..., Pn вiдповiдно. Якщо B1 P1, ..., Bn Pn , то AA’.

Формула A’ називається варiантою формули A, якщо A’ можна отримати iз A послiдовними замiнами такого типу: пiдформулу xB замiнюємо на yBx [y], дe y нe вiльна в B.

Тeорeма 3.2 (семантична тeорeма про варiанту). Якщо A’ варiанта формули A, то AA’.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2 



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок