Логіки першого порядку, Детальна інформація

Приклад 5. Формула (x(y(x=y) iстинна на всiх 1-елементних АС i тiльки на них; формула ((x(y(x=y) iстинна на всiх k-елементних АС, де k>1, i тiльки на них.

.

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

.

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

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

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

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

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

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

\xF02D\xF020((\xF0D8\xF046)=T \xF0DB\xF020\xF020((\xF046)=F;

\xF02D\xF020((\xF0DA\xF046\xF059)=T \xF0DB\xF020\xF020((\xF046)=T або ((\xF059)=T.

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

Зрозумiло, що кожна тавтологiя є всюди iстинною формулою, але зворотне твердження невiрне. Наприклад, всюди істинна формула вигляду x=x \xF02D не тавтологiя.

На множинi формул введемо відношення тавтологiчного наслiдку \x255E , логiчного наслiдку \xF07C\xF03D, слабкого логiчного наслiдку \xF07C\xF07C\xF03D та логiчної еквiвалентностi \xF07E.

Формула \xF059 є тавтологiчним наслiдком формули \xF046, що позначатимемо \xF046\x255E \xF059, якщо формула \xF046\xF0AE\xF059 – тавтологiя.

Формула \xF059 є логiчним наслiдком формули \xF046, що позначатимемо \xF046\xF07C\xF03D\xF059, якщо формула \xF046\xF0AE\xF059 всюди iстинна.

Формули \xF046 та \xF059\xF020 логiчно еквiвалентнi, що позначатимемо \xF046\xF07E\xF059, якщо \xF046\xF07C\xF03D\xF059 та \xF059\xF07C\xF03D\xF046.

Зрозумiло, що \xF046\xF07E\xF059 \xF0DB формули \xF046\xF0AE\xF059 та \xF059\xF0AE\xF046 всюди iстиннi.

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

Формула \xF059\xF020 є логiчним наслiдком множини формул {\xF0461,...,\xF046n}, що позначатимемо {\xF0461,...,\xF046n}\xF07C\xF03D\xF059, якщо \xF0461&…&\xF046n\xF07C\xF03D\xF059.

Аналогічно визначаємо {\xF0461,...,\xF046n}\x255E \xF059 та {\xF0461,...,\xF046n}\xF07C\xF07C\xF03D\xF059.

Замість (\x255E \xF046, (\xF07C\xF03D\xF046 та (\xF07C\xF07C\xF03D\xF046 писатимемо відповідно \x255E \xF046, \xF07C\xF03D\xF046 та \xF07C\xF07C\xF03D\xF046\xF02E

Вкажемо основні властивості відношень \x255E, \xF07C\xF03D, \xF07C\xF07C\xF03D та \xF07E:

1) \xF046\xF020\xF020тавтологія \xF020\xF0DB\xF020\x255E \xF046\xF03B

2) \xF046\xF020\xF020всюди істинна \xF020\xF0DB\xF020\xF07C\xF03D\xF046 \xF020\xF0DB\xF020 \xF07C\xF07C\xF03D\xF046\xF03B

3) якщо \xF046\x255E \xF059, то \xF046\xF07C\xF03D\xF059; але не завжди із \xF046\xF07C\xF03D\xF059 випливає \xF046\x255E \xF059;

4) якщо \xF046\xF07C\xF03D\xF059, то \xF046\xF07C\xF07C\xF03D\xF059\xF03B але не завжди із \xF046\xF07C\xF07C\xF03D\xF046 випливає \xF046\xF07C\xF03D\xF059;

5) \xF046\xF07E\xF059\xF020\xF0DB\xF020\xF07C\xF03D\xF046\xF0AB\xF059;

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