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

Здесь знак 0 означает, что функции не задаются, так как в исходной фор- муле нет функциональных букв. Тогда формула VxAj (x,y,ai) в заданной интер­ претации запишется: \/х(х + у >\) и будет означать, что для любого х (х е [О, оо)) сумма х + у больше или равна 1. Очевидно, что это отношение истинно при некоторых у (у >1J и ложно при других значениях у f0<y<lj. Если предметной постоянной cij поставить в соответствие О, а не 1, т.е. положить /2 = ([О, ос); {x+j ;>z},{0},{O}). то утверждение Vx(x +у > 0J будет истинно при любом значении свобод­ ной переменной у. Легко видеть, что для той же формулы \/^cAj (x,y,aj) можно построить бес­ численное множество других интерпретаций, выбирая различные множества фиксируя из каким-то образом элемент, соответствуюш,ий cij и задавая раз­ личным образом на трехместный предикат. Так, можно за взять множество всех студентов Казани, за a j - студента Иванова, а Aj (x,y,z) поставить в соответствие предикат: «х и у учатся в той же группе, что и Z ». Тогда исходная формула VxAj (x,y,ai) в этой интерпретации означает утверждение: Vx{x и у учатся в той же группе, что и Иванов). Это ут­ верждение является ложным при каждом у, ибо не может быть, чтобы любой х и некоторый у учились в той же группе, что и Иванов. При данной интерпретации каждая формула без свободных переменных (замкнутая формула) представляет собой высказывание, которое истинно либо ложно, а формула со свободными переменными выражает некоторое отноше­ ние на !М, которое может быть истинно для одних значений из и ложно для других. Формула называется выполнимой в данной интерпретации, если она при­ нимает значение И хотя бы для одной совокупности возможных значений её свободных переменных (если они есть). Если формула не содержит свободных переменных, то она называется выполнимой в том случае, если принимает зна­ чение И в этой интерпретации. Формула называется истинной в данной интерпретации, если она прини­ мает значение И для всех возможных значений её свободных переменных (если они есть). Если же свободных переменных нет, то формула называется истин­ ной, когда она принимает значение И в этой интерпретации. Формула называется ложной в данной интерпретации, если она принима­ ет значение Л для всех возможных значений её свободных переменных (если они есть). Если же свободных переменных нет, то формула называется ложной, когда она принимает значение Л в этой интерпретации. 37