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

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

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

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

.
В формул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 символи.
Наприклад, xЗамиканням формули з вiльними iменами x1, ..., xn назвемо замкнену формулу x1... xn , яку звичайно позначатимемо .
Із визначень випливає семантична теорема замикання:
для кожних iнтерпретацiї A та формули A A .
Приклад 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 хab)=Т. Але ( x )А(d)=F, тому для всіх a A маємо А(d хaа)=F, зокрема, А(d хab)=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 хab)=Т для деякого b A. Але ім'я х не вільне в , тому А(d хab)= А(d)=F. Звiдси дістаємо ( )А(d хab)=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дформул
Loading...

 
 

Цікаве