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

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

На рівні логік предикатів 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, () породжується
підмножиною В(А. Зрозуміло, що різні підмножини можуть породжувати
одну і ту ж підсистему.

Приклад 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 сигнатури ?, якщо ?’(?.

В формулi вигляду ?x( або (x( формулу P називають областю дiї
квантора по x. Вираз вигляду ?x або (x називають кванторним
префiксом.

Входження імені (змінної) x в формулу ? зв’язане, якщо воно
знаходиться в областi дiї деякого квантора по x, iнакше таке
входження x в ? вiльне.

Якщо iснує вiльне входження імені x в формулу ?, то x ? вiльне
ім’я (вільна змiнна) формули ?.

Формулу ? iз вiльними іменами x1,.., xn позначаємо ?(x1,.., xn).

Формула замкнена, якщо вона не має вiльних імен.

Терм, який не мiстить входжень предметних імен, називається замкненим
термом. Зокрема, таким є кожний константний символ.

Наведемо кiлька прикладiв мов 1-го порядку.

Приклад 1. Мова арифметики Lar визначається сигнатурою ?ar={0, 1,
+, (, =}, де 0 та 1 ? константні символи, + та ( ? бiнарнi
функцiональнi символи, = ? бiнарний предикатний символ.

Терм мови арифметики назвемо арифметичним термом.

Формулу мови арифметики назвемо арифметичною формулою.

Наприклад, 1+1 ? замкнений арифметичний терм; x((y+z) ? арифметичний
терм; ?z(x+z=y) ? арифметичнa формула.

Приклад 2. Мова теорiї множин Lset визначається сигнатурою
?set={(, =}, де ( та = ? бiнарнi предикатнi символи.

Наприклад, z(x ? атомарна формула, (z(z(x(z(y) ? формула, ?x?(y(y(x)
? замкнена формула мови Lset . Зауважимо, що останні дві формули
відповідно означають «x(y» та «існує (»

Приклад 3. Мова теорiї впорядкованих множин Lord визначається
сигнатурою ?ord={<, =}, де < та = ? бiнарнi предикатнi символи. Наприклад, x1, i тiльки на них.

.

Із визначень випливає семантична теорема замикання:

.

Приклад 6. Кожна формула вигляду (x[t]??x( всюди істинна.

Нехай Х ? множина вільних імен формули (x[t]??x(. Припу-стимо
супротивне: існує A=(A, ?) така, що A ?(?(x[t]??x(. Тоді iснує
d(AX таке, що ((x[t]??x()А(d)=F, звідки ((x[t])А(d)=Т та
(?x()А(d)=F. Нехай tА(d)=b(A; в силу ((x[t])А(d)=Т тоді
(А(d(х(b)=Т. Але (?x()А(d)=F, тому для всіх a(A маємо
(А(d(х(а)=F, зокрема, (А(d(х(b)=F. Дістали суперечнiсть.

Окремим випадком всюди iстинних формул є тавтологiї, тобто формули, якi
мають структуру тавтологiй мови ЛВ. Наприклад, кожна формула виду
?A?A ? це тавтологiя. Точне визначення тавтологiї 1-го порядку можна
дати таким чином.

Формулу назвемо пропозиційно нерозкладною, якщо вона атомарна або має
вигляд ?x(.

Нехай Fr0 ? множина всiх пропозиційно нерозкладних формул мови L,
Fr ? множина всiх формул мови L. Iстиннiсною оцiнкою мови L назвемо
довiльне вiдображення (?: Fr0 ?{T, F}.

Продовжимо ( до вiдображення (?: Fr?{T, F} таким чином:

??((??)=T ???((?)=F;

??((???)=T ???((?)=T або ((?)=T.

Формула ? мови L тавтологiя, якщо для кожної iстинiсної оцiнки (
мови L маємо ((?)=T.

Зрозум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валентнi, що позначатимемо ???, якщо
???? та ????.

Зрозумiло, що ??? ? формули ??? та ??? всюди iстиннi.

Формула ? є слабким логiчним наслiдком формули ?, що позначатимемо
?????, якщо для кожної iнтерпретацiї A iз умови A??? випливає
A???.

Формула ?? є логiчним наслiдком множини формул {?1,…,?n}, що
позначатимемо {?1,…,?n}???, якщо ?1&…&?n???.

Аналогічно визначаємо {?1,…,?n}? ? та {?1,…,?n}????.

Замість (? ?, (??? та (???? писатимемо відповідно ? ?, ???
та ?????

Вкажемо основні властивості відношень ?, ??, ??? та ?:

1) ???тавтологія ???? ??

2) ???всюди істинна ?????? ??? ?????

3) якщо ?? ?, то ????; але не завжди із ???? випливає ?? ?;

4) якщо ????, то ?????? але не завжди із ????? випливає ????;

5) ???????????;

6) відношення ? , ?? та ??? рефлексивні і транзитивні;

7) відношення ? рефлексивне, транзитивне і симетричне.

Враховуючи 2), той факт, що ? всюди істинна, позначаємо ???.

Для 3) та 4) маємо такi контрприклади:

Приклад 7. ?x?y(x=y)???y?x(x=y), але невiрно ?x?y(x=y)? ?y?x(x=y).

Приклад 8. (x=0)???(x(x=0) але невiрно (x=0)??(x(x=0).

(x=0)N (0)=T та ((x(x=0))N =F, тому (x=0((x(x=0))N (0)=F, звідки
невiрно (x=0)??(x(x=0). Але (x=0)???(x(x=0) за теоремою замикання.

Приклад 9. Якщо х не вільне в ?, то ???????x???.

Нехай Х ? множина вільних імен формули ???. Припустимо супротивне:
існує A=(A, ?) така, що A ?????? та A ?(??x???. Тоді iснує d(AX
таке, що (?x???)А(d)=F, звідки (?x?)А(d)=Т та ?А(d)=F. В силу
(?x?)А(d)=Т маємо (А(d(х(b)=Т для деякого b(A. Але ім’я х не
вільне в ?, тому ?А(d(х(b)=?А(d)=F. Звiдси дістаємо
(???)А(d(х(b)=F, що суперечить A ??????.

Формулу ( мови L називають k-iстинною, якщо A??? для кожної
k-елементної iнтерпретацiї A мови L.

Формула ( скiнченно-iстинна, якщо ? є k-iстинною для кожного k>0.
Отже, скiнченно-iстинна формула є iстинною при кожнiй скiнченнiй
iнтерпретацiї.

Приклад 10. Формула
?x1?x2…?xk((x1(x2)&…&(x1(xk)&(x2(x3)&…&(xk-1(xk)), яку позначимо
Ek, стверджує, що iснує (k рiзних елементiв областi iнтерпретацiї.
Отже, Ek є n-істинною для всіх n(k.

Приклад 11. Формула ?x1?x2…?xk(y((y=x1)(…( (y=xk)), яку позначимо
Gk, cтверджує, що iснує (k рiзних елементiв областi iнтерпретацiї.
Отже, Gk є n-iстинною для всiх 1(n(k.

Приклад 12. Формула Ek&Gk k-iстиннa, причому Ek&Gk не є n-iстинною
для кожного n(k.

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 , то A?A’. ?

Формула 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, то A?A’.

Формула A знаходиться в прeнeкснiй формi, якщо вона має вигляд Qx1
…Qxn B, дe Qxk ? кванторний прeфiкс ?xk або (xk , B ?
бeзкванторна формула, яку називають матрицeю формули A.

Формулу в прeнeкснiй формi називають прeнeксною формулою.

У визначeннi прeнeксної форми насправдi фiгурують формули, для яких така
прeнeксна форма є скорочeнням. Алe, коли мовиться про прeнeксну форму,
квантор ( нe прийнято виражати чeрeз ? та ?.

Тeорeма 3.3. 1) (xB ??x?B та ??xB ?(x?B;

2) ?xB?C??x(B?C) та (xB?C?(x(B?C), якщо x нe вiльна в C;

3) B??xC??x(B?C) та B?(xC?(x(B?C), якщо x нe вiльна в B.

Ввeдeмо прeнeкснi опeрацiї над формулами, якi дозволять кожну формулу
пeрeтворити до eквiвалeнтної їй прeнeксної формули. Цi опeрацiї
грунтуються на тeорeмах 4.3.2 та 4.3.3.

Пiд прeнeксними опeрацiями над формулою A розумiють такi опeрацiї:

a) замiна A дeякою її варiантою;

b) замiна в A пiдформул вигляду ??xB та ?(xB на (x?B та ?x?B
відповідно;

c) замiна в A пiдформул вигляду QxB?C на Qx(B?С), якщо x нe
вiльне в C;

замiна в A пiдформул вигляду B?QxC на Qx(B?C), якщо x нe вiльне
в B.

Прeнeксною формою формули A називатимeмо прeнeксну формулу A’,
утворeну iз A за допомогою прeнeксних опeрацiй.

Тeорeма 3.4. Кожна формула має прeнeксну форму, причому якщо A’ ?
прeнeксна форма формули A, то A?A’.

Розглянутий мeтод побудови прeнeксної форми пeрeдбачає роботу в систeмi
логiчних опeрацiй {?, ?, ?х, (х}. Для уникнення елiмiнацiї логiчних
зв’язок & та ? можна ввести додатковi прeнeкснi опeрацii:

d) замiна в A пiдформул вигляду QxB&C на Qx(B&C), якщо x нe
вiльнe в C, та пiдформул вигляду B&QxC на Qx(B&C), якщо x нe
вiльнe в B;

e) замiна в A пiдформул вигляду B?QxC на Qx(B?C), якщо x нe
вiльнe в B;

f) замiна в A пiдформул вигляду ?xB?C на (x(B?C), та пiдформул
вигляду (xB?C на ?x(B?C), якщо x нe вiльнe в C.

Нeважко пeрeконатись, що виконання кожної з опeрацiй типу d), e) чи
f) зводиться до виконання пeвної послiдовностi опeрацiй b) та с).
В той жe час для ( подiбних опeрацiй нeма.

Приклад 1. Знайдeмо прeнeксну форму для формули
?z(x=y+z)?(x=y)??z((x=y+z)&?(z=0)):

?z(x=y+z)?(x=y)??t((x=y+t)&?(t=0)) ? опeрацiя a);

?z(x=y+z)??t(x=y)?(x=y+t)&?(t=0) ??опeрацiя c);

(z((x=y+z)??t(x=y)?(x=y+t)&?(t=0)) ? опeрацiя f);

(z?t((x=y+z)?(x=y)?(x=y+t)&?(t=0)) ? опeрацiя e).

4. ВИРАЗИМІСТЬ В АС. АРИФМЕТИЧНІ ПРЕДИКАТИ, МНОЖИНИ, ФУНКЦІЇ.

Нехай A=(A, I, () ? деяка АС. Предикат Р на А виразимий
формулою ? сигнатури (, якщо Р ? суть предикат ?A .

Предикат Р на А виразимий в АС A=(A, I, (), якщо Р виразимий
деякою формулою ? сигнатури (.

Інакше кажучи, предикат Р на А виразимий в АС A=(A, I, (), якщо
існує така формула ? сигнатури (, що Р ? суть предикат ?A .

Множина, що є областю істинності предикату, виразимого в АС A,
називається виразимою в АС A множиною.

Функція, графік якої ? виразима в АС A множина, називається
виразимою в АС A функцією.

Приклад 1. Предикат “х=0” в АС (N, {(, =}), (Q, {(, =}) та (R, {(, =})
виражається формулою (y(x(y=х).

Приклад 2. Предикат “х=1” в АС (N, {(, =}), (Z, {(, =}) та (R, {(, =})
виражається формулою (y(x(y=y).

Приклад 3. Предикат “х=0” в АС (N, {+, =}), (Z, {+, =}) та (R, {+, =})
виражається формулою х+х=х.

Приклад 4. Предикат “х=1” в АС (N, {+, =}) виражається формулою
(u(v(x=u+v( u=u+u&v=v+v)&(x=x+x.

Приклад 5. Предикат “y=x+4” в АС (R, {y=x+2, =}) виражається формулою
(z(y=z+2&z=x+2).

Приклад 6. Предикат “|x?y|=2” в АС (Z, {|x?y|=1, =}) виражається
формулою (z(|x?z|=1&|z?y|=1&(x=y.

Приклад 7. Предикат “|x?y|=3” в АС (Q, {y=x+3, =}) виражається
формулою y=x+3 ( x=y+3.

Приклад 8. Предикат “z=x+1” виражається в AC (Z, {<, =}) формулою (x

Похожие записи