Реферат на тему:
Логіки першого порядку
На рівні логік предикатів 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={1, 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, {
Нашли опечатку? Выделите и нажмите CTRL+Enter