Математическая логика и теория алгоритмов

§ 5. Свойства формул в данной интерпретации Можно доказать следующие свойства формул в данной интер­ претации (некоторые из них очевидны, другие читатель легко докажет самостоятельно). 1. Формула А лоядаа в данной интерпретации тогда и только тогда, когда ~\А истинно в этой же интерпретации. Формула А истинна в данной интерпретации тогда и только тогда, когда "U ложна в этой же интерпретации. 2. Никакая формула не может быть одновременно истинной и ложной в одной и той же интерпретации. 3. Если в данной интерпретагдии истинны А и А=>В, то истинно и В. Это утверждение легко доказать методом от против­ ного (сравни с теоремой 1.1). 4. Формула А=>В ложна в данной интерпретации тогда и толь­ ко тогда, когда А истинно в этой интерпретации, а В ложно. Доказа­ тельство этого утверлодения следует из определения импликации. 5. Формула Л&В выполнима в данной интерпретации тогда и только тогда, когда Л и В принимают значение И одновременно хотя бы для одной совокупности значений своих свободных переменных. Если же свободных переменных нет, то формула А&В выполнима в данной интерпретации тогда и только тогда, когда обе формулы А а В истинны в этой интерпретации, 6. Формула AvB выполнима в данной интерпретации, если хотя бы одна т них выполнима в этой интерпретации. 7. Формула А=В выполнима в данной интерпретации тогда и только тогда, когда А я В принимают значение И одновременно или значение Л (тоже одновременно) хотя бы для одной совокупности значений своих свободных переменных. Если же свободных перемен­ ных нет, то формула А=В выполнима в данной интерпретации тогда и только тогда, когда А vi В принимают одинаковые истинностные значения в этой интерпретации. 8. Формула ЗхА выполнима в данной интерпретации тогда и только тогда, когда Л принимает значение И хотя бы для одной сово­ 59