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

а) предикатным буквам А" поставлены в соответствие некото­ рые п - местные предикаты (отношения) в М; б) функциональным буквам / " поставлены в соответствие некоторые н - аргументные функции, отобрай<ающие в в) каждой предметной постоянной поставлен в соответствие некоторый (фиксированный) элемент из М; г) символам 1, Vx, Зх поставлен в соответствие их обычный смысл. 3. Считается, что предметные переменные пробегают все мно­ жество М. Например, чтобы задать интерпретацию для формулы \/.х (x,y,bi), нужно задать множество !М - область интерпретации (область изменения переменных х,у). Из этой области М будем брать некоторый элемент, соответствующий предметной постоянной Ь\. Да­ лее нужно задать трехместный предикат на М, соответствующей пре­ дикатной букве Af. Так, можно положить, что £ ^[0, со); предметной постоянной bj поставить в соответствие 1, а Af (x,y,z) поставить в со­ ответствие предикат х + у >z. Тогда формула VxAf (x,y,b\) в заданной интерпретации запишется: Vx(x + j > 1) и будет означать, что для лю­ бого X (х е [О, оо)) сумма х + у больше или равна 1. Очевидно, что это отношение истинно при некоторых у {у>\) и ложно при других зна­ чениях у (0 £ >'<1). Если предметной постоянной Ъ\ поставить в соот­ ветствие О, а не 1, то утверждение Vx(x +у > 0) будет истинно при лю­ бом значении свободной переменной;^. Легко видеть, что для той же формулы VxAf(xj^,bi) можно построить бесчисленное множество других интерпретаций, выбирая различные множества фиксируя из М каким-то образом элемент, соответствующий bi и задавая различным образом на М трехместный предикат. 57