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

Пусть область интерпретации М- множество действительных чисел и формула А означает предикат ^>3^, тогда высказывание VJ^3a:(;C>>') (2.20) означает, что для любого числа существует число х большее, чем у. Это высказывание истинно. Высказывание, полученное из (2.20) пере­ становкой кванторов 3W>'(x>;'), означает, что существует число х больше любого другого числа и, очевидно, является лолсным. Тогда ложна импликация: Следовательно, формула (2.19) не истинна в приведенной интерпретации, т.е. не является логи­ чески общезначимой. Теорема доказана. Заметим, что в частном случае формула (2,19) может оказаться и логически общезначимой, например, когда А является замкнутой формулой. В этом случае, как известно (см. § 6), формула А равно­ сильна формуле Q]Q2.-Q i A, где QhQ2,---,Qn - любая сово­ купность кванторов. Поэтому формула (2.19) будет логически общезначимой. Однако подчеркнем еще раз, что для произвольной формулы перестановка разноименных кванторов не всегда приводит к равно­ сильным формулам. § 9.Пр а в и л а переименования связанных переменных Рассмотрим формулы \/хА(х) и \/уА(у). Очевидно, что в каждой интерпретации из истинности первой следует истинность второй, и наоборот, поэтому эти формулы равносильны: \/хА(х) ~ VyA(y). Таким образом, переименование переменной х на.у в кванторе и в области действия этого квантора привело к формуле, равносильной исходной. В математическом анализе имеется аналогичное правило. Например, замена переменной в подынтегральном выражении опреде­ ленного интеграла не меняет его величины; 68