|
§5. Выполнимость
формул логики предикатов.
Формулу Á сигнатуры s
назовем выполнимой, если существует такая
алгебраическая система Â = á M ; s ñ, что Á истинна в Â при некоторых значениях свободных
переменных. Формулу Á сигнатуры s назовем тождественно истинной ( или
тавтологией) , если Á
истинна в любой алгебраической системе
сигнатуры sÁ семантически следует
из множества формул Г ( символически Г ╞ Á ), если для любой алгебраической
системы Â из истинности в ÂÁ в Â при тех же
значениях переменных. Если Á ╞
В и В¦ Á
, то пишем Á ~ В . при любых значениях
свободных переменных. Будем говорить, что
формула всех формул из Г при некоторых
значениях переменных следует истинность
Формулы вида Q1 x1…QnxnÁ , где Á
-- бескванторная формула, Qi есть " или $ , называется предваренной (или пренексной)
нормальной формой. Если все Qi равны " , то эта
форма называется "-формулой
(универсальной
формулой), если все Qi равны
$ , то эта форма называется $ -формулой. Если существует i
(0 £ i £ n) такое, что Q1 ,… ,Qi суть $ , а Qi+1 ,… ,Qn суть " , то эта форма
называется скулемовской нормальной формой ( $ " -формулой ).
Пусть Р—одноместный предикатный символ, не входящий в s
. Любой формуле Á сигнатуры s сопоставим формулу r Р(Á ) (называемую
релятивизацией Á относительно Р )
следующим образом:
r Р(B)
= B для атомной формулы В,
r Р((B1
& B2)) = (r Р(B1)
& r Р(B2)),
r Р((B1
È B2)) = (r Р(B1) È r Р(B2)),
r Р((B1
É B2)) = (r Р(B1) É r Р(B2)),
r Р(ù B) = ù r
Р ( B ),
r Р(" x B) = " x( P (x) É r Р(B)),
r Р($ x B) = $ x( P (x) &
r Р(B)).
Пусть s содержит двуместный
предикатный символ =. Обозначим через КЕs класс алгебраических систем
сигнатуры s таких, что в системах
из класса КЕs х = у истинно в том
и только том случае, когда элементы х и у
совпадают.
Системы из класса КЕs называем
нормальными системами.
|
