Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Очевидно, что формула А выполнима в данной интерпретации тогда и только тогда, когда она не является ложной в этой интерпретации. Данная интерпретация называется моделью для множества формул G, если каждая формула из G истинна в этой интерпретации. Можно доказать следующие свойства формул в данной интерпретации (некоторые из них очевидны, другие читатель легко докажет самостоятельно). Формула А ложна в данной интерпретации тогда и только тогда, когда -пА истинно в этой же интерпретации. Формула А истинна в данной интерпретации тогда и только тогда, когда —А ложна в этой же интерпретации. Никакая формула не может быть одновременно истинной и ложной в од­ ной и той же интерпретации. Если в данной интерпретации истинны А и А^В, то истинно и В. Это ут­ верждение легко доказать методом от противного (сравни с теоремой 1.1). Формула А=>В ложна в данной интерпретации тогда и только тогда, когда А истинно в этой интерпретации, а В ложно. Доказательство этого утверждения следует из определения импликации. Формула А&В выполнима в данной интерпретации тогда и только тогда, когда А и В принимают значение И одновременно хотя бы для одной совокуп­ ности значений своих свободных переменных. Если же свободных переменных нет, то формула Л cfeS выполнима в данной интерпретации тогда и только тогда, когда обе формулы АиВ истинны в этой интерпретации. Формула AvB выполнима в данной интерпретации, если хотя бы одна из них выполнима в этой интерпретации. Формула А=В выполнима в данной интерпретации тогда и только тогда, когдаА и В принимают значение И одновременно или значение Л (тоже одно­ временно) хотя бы для одной совокупности значений своих свободных пере­ менных. Если же свободных переменных нет, то формула А=В выполнима в данной интерпретации тогда и только тогда, когдаА и В принимают одинако­ вые истинностные значения в этой интерпретации. Формула ЗхА выполнима в данной интерпретации тогда и только тогда, когда А принимает значение И хотя бы для одной совокупности значений её свободных переменных и хотя бы одного значения переменной х. Формула VxA истинна в данной интерпретации тогда и только тогда, когда в этой интерпретации истинно А. Как следствие из этого утверждения получаем, что формула А истинна в данной интерпретации тогда и только тогда, когда истинна в этой интерпрета­ ции замыкание формулы А. Если формула А замкнута, то в данной интерпретации А означает некото­ рое высказывание (нет свободных переменных), следовательно, А истинно либо ложно. Иначе, если А замкнуто, то в любой данной интерпретации либо истин­ но А, либо истинно —А. 38