Формулы. Рiвносильнiсть формул. Тождественно iстиннi формулы

Формулы. Рiвносильнiсть формул. Тождественно iстиннi формулы

Наведем iндуктивне определение понятия формулы логiки предикатiв (предикатной формулы или просто формулы ) на предметнiй областi M.

1. Усi предикаты P(x1, x2,...,xn) на множинi M являются формулами. Такi формулы называют элементарными, или атомарными.

2. Если A i B - формулы, то (A), (B) (AB) (AB) (AB) (A~B) тоже являются формулами.

3. Если A - формула, а x - вiльна змiнна в A, то (x(A)) i (x(A)) тоже формулы.

4. Iнших формул, крiм образованных по правилам 1-3, нет.

Это определение позволяет утверждать, что усi формулы алгебры высказываний являются формулами логiки предикатiв, оскiльки высказывание - это нульмiснi предикаты.

С помощью приведенного определения нетрудно также убедиться, что выражения (x(y(A(x, y))(B(x)(z(C(x, z))))) i (x(y(A(x, y)B(x))(y(C(x, y)))) являются формулами логiки предикатiв, а выражение (x(A(y)(x(B(x))))) не является формулой, оскiльки в виразi (A(y)(x(B(x)))), который является правильной формулой, змiнна x является связанной, то есть нет вiльною змiнною i квантор 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во).

Пусть F(x1, x2,...,xn) - некоторая формула логiки предикатiв на множинi M. При логiчнiй (iстинностнiй) iнтерпретацiй формулы F можливi такi три основнi ситуации.

1. Iснуе набiр значений змiнних, для которого формула F превращается в iстинне высказывание. В этом разi формула F называется выполняемой в областi M.

Если для F iснуе область M, в якiй F является выполняемой, то формула F называется просто выполняемой.

2. Если формула F принимает значение 1 (то есть является выполняемой) для всiх наборiв значений из M, то она называется тождественно iстинною в M. Формула, тождественно iстинна в любых M, называется тождественно iстинною или логiчно общезначимой (сокращенно - лзз).

3. Если формула F является невыполняемой в M, то она называется тождественно ошибочной в M. Формула, невыполняемая в усiх M, называется тождественно ошибочной, или суперечнiстю.

Пример 5.7. Формула xA(x, y)xA(x, y) есть выполняемой i она же есть тождественно iстинною в усiх одноэлементных областях M. Формула F(x1, x2,...,xn)F(x1, x2,...,xn) тождественно iстинна, а формула F(x1, x2,...,xn)F(x1, x2,...,xn) тождественно ошибочная. Тождественно iстинними будут формулы xP(x)P(y) i P(y)xP(x).

Формулы F1 i F2 называются рiвносильними (еквiвалентними), если при всiх возможных пiдстановках значений замiсть их змiнних они приобретают одинаковые значения; обозначается F1 = F2.

Например, усi тождественно iстиннi (усi тождественно хибнi) формулы рiвносильнi мiж собой. Очевидно также, что когда F1 i F2 рiвносильнi, то формула F1~F2 есть тождественно iстинною, и наоборот.

Множество тождественно iстинних формул логiки предикатiв является составной частью усiх формальных математических теорiй, потому ее дослiдження i описание является важной задачей математической логiки. Значение цiей множества пiдтверджуе тот факт, что ей, как было отмечено выше, принадлежат усi рiвносильнi спiввiдношення (тотожностi) логiки предикатiв.



Вернуться назад