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

Так, можно за М взять множество всех студентов Казани, за 61 - студента Иванова, а (x,y,z) поставить в соответствие предикат: <а и у учатся в той же группе, что и z ». Тогда исходная формула \fxA^(x,y,b[) в этой интерпретации означает утверждение: Vx(x и у учатся в той же группе, что и Иванов). Это утверждение явля­ ется ложным при каждом у, ибо не может быть, чтобы любой х и некоторый учились в той же группе, что и Иванов, При данной интерпретации всякая формула без свободных пе­ ременных (замкнутая формула) представляет собой высказывание, которое истинно либо ложно, а всякая формула со свободными пере­ менными выралсает некоторое отношение на !М, которое может быть истинно для одних значений из Ж и ложно для других. Формула называется выполнимой в данной интерпретации, если она принимает значение И хотя бы для одной совокупности возмож­ ных значений ее свободных переменных (если они есть). Если форму­ ла не содержит свободных переменных, то она называется выполни­ мой в том случае, если принимает значение И в этой интерпретации. Формула называется истинной в данной интерпретации, если рна принимает значение И для всех возможных значений ее свобод­ ных переменных (если они есть). Если же свободных переменных нет, то формула называется истинной, когда она принимает значение И в этой интерпретации. Формула называется ложной в данной интерпретации, если она принимает значение Л для всех возможных значений ее свободных переменных (если они есть). Если же свободных переменных нет, то формула называется ложной, когда она принимает значение Л в этой интерпретации. Очевидно, что формула ложна в данной интерпретации тогда и только тогда, когда она не выполнима в этой интерпретации. Так же ясно, что формула А выполнима в данной интерпретации тогда и только тогда, когда она не является ложной в этой интерпретации. Данная интерпретация называется моделью для множества фор­ мул G, если каждая формула из G истинна в этой интерпретации. 58