Верещагин Н.К., Шень А. - Языки и исчисления (1076783), страница 18
Текст из файла (страница 18)
(Ответ: первая из этих формул эквивалентнаформуле ∃x A(x), а вторая — формуле ∀x A(x).)Формула называется замкнутой, если она не имеет параметров.Замкнутые формулы называют также суждениями. Как мы доказали, истинность замкнутой формулы определяется выбором интерпретации (и не зависит от значений переменных).80Языки первого порядка[гл.
3]3.3. Выразимые предикатыПусть фиксирована некоторая сигнатура σ и её интерпретация сносителем M . Мы хотим определить понятие выразимого (с помощью формулы данной сигнатуры в данной интерпретации) k-местного предиката.Выберем k переменных x1 , . . . , xk и рассмотрим произвольнуюформулу ϕ, все параметры которой содержатся в списке x1 , . . .
, xk .Истинность этой формулы зависит только от значений переменныхx1 , . . . , xk . Тем самым возникает отображение M k → B = {И, Л}, тоесть некоторый k-местный предикат на M . Говорят, что этот предикат выражается формулой ϕ. Все предикаты, которые можно получить таким способом, называются выразимыми. (Ясно, что конкретный выбор списка переменных роли не играет.) Соответствующиеим подмножества множества M k (области истинности выразимыхпредикатов) также называют выразимыми.48. Докажите, что пересечение, объединение и разность двух выразимых множеств являются выразимыми.
Докажите, что проекция k-мерного выразимого множества вдоль одной из «осей координат» является(k − 1)-мерным выразимым множеством.Пример. Рассмотрим сигнатуру, содержащую одноместный функциональный символ S и двуместный предикатный символ равенства(=), и интерпретацию этой сигнатуры. В качестве носителя возьмёмнатуральный ряд N. Символ S будет обозначать функцию увеличения на 1 (можно считать S сокращением от слова successor — последователь).
Равенство интерпретируется как совпадение элементов.Легко проверить, что одноместный предикат «быть нулём» выразим в этой интерпретации, несмотря на то, что константы для нуляв сигнатуре не предусмотрено. В самом деле, он выражается формулой¬∃y(x = S(y))с единственным параметром x.Ещё проще выразить двуместный предикат «быть больше на 2»,при этом даже не нужны кванторы: y = S(S(x)).Любопытно, что уже в такой простой ситуации можно сформулировать содержательную задачу: выразить предикат y = x + N , гдеN — большое число (скажем, миллиард), с помощью существенноболее короткой формулы, чем y = S(S(.
. . (S(x)) . . . )). Как ни удивительно, это вполне возможно, и соответствующую формулу вполнеможно уместить на листе бумаги.[п. 3]Выразимые предикаты8149. Докажите, что предикат y = x + N можно выразить формулойуказанной сигнатуры, длина которой есть O(log N ).
(Указание. Если мынаучились выражать y = x + n, можно выразить y = x + 2n с помощьюформулы∃z ((z = x + n) ∧ (y = z + n))(в которой через z = x+n и y = z +n обозначены соответствующие формулы). Это само по себе ничего не даёт, так как длина формулы увеличиласьвдвое, но можно использовать такой трюк:∃z ∀u ∀v(((u = x ∧ v = z) ∨ (u = z ∧ v = y)) → (v = u + n)).Далее можно воспользоваться записью числа N в двоичной системе счисления.)Можно доказать, что в этой сигнатуре кванторы почти не увеличивают набор выразимых предикатов: всякий выразимый предикатбудет выражаться бескванторной формулой (возможно, гораздо более длинной), если добавить к сигнатуре константу 0.
Мы вернёмсяк этому вопросу в разделе 3.6.Чтобы привыкнуть к понятию выразимости, рассмотрим ещё итакой пример. Пусть сигнатура содержит предикат равенства и трёхместный предикат C. Рассмотрим интерпретацию, в которой носителем является множество точек плоскости, равенство интерпретируется как совпадение точек, а C(x, y, z) означает, что точки x и yравноудалены от точки z. Оказывается, что этого предиката достаточно, чтобы выразить более или менее все традиционные понятияэлементарной геометрии.Как, например, записать, что три различные точки A, B, C лежатна одной прямой? Вот как: «не существует другой точки C 0 , котораянаходилась бы на тех же расстояниях от A и B, что и точка C».50.
Напишите соответствующую формулу указанной сигнатуры.Теперь легко выразить такое свойство четырёх точек A, B, C, D:«точки A и B различны, точки C и D различны и прямые AB и CDпараллельны». В самом деле, надо написать, что нет точки, котораябы одновременно лежала на одной прямой с A и B, а также на однойпрямой с C и D.После этого можно выразить свойство четырёх точек «быть вершинами параллелограмма». Это позволяет переносить отрезок параллельно себе. После этого легко выразить и такое свойство: «расстояние AB равно расстоянию CD».51. Запишите соответствующую формулу.Аналогичным образом можно двигаться и дальше.82Языки первого порядка[гл. 3]52.
Выразите свойство |OA| 6 |OB| трёх точек O, A, B. (Указание.Напишите, что все прямые, проходящие через A, пересекаются с окружностью радиуса OB с центром в O.)53. Запишите в виде формулы: (а) равенство треугольников; (б) равенство углов; (в) свойство угла быть прямым.54. Рассмотрим естественную интерпретацию сигнатуры (=, <) на множестве целых чисел. Как выразить предикат y = x + 1?55. Рассмотрим множество действительных чисел как интерпретациюсигнатуры (=, +, y = x2 ). Как выразить трёхместный предикат xy = z?56.
Рассмотрим множество целых положительных чисел как интерпретацию сигнатуры, содержащей равенство и двуместный предикат «x делитy». Выразите свойства «равняться единице» и «быть простым числом».57. Рассмотрим плоскость как интерпретацию сигнатуры, содержащейпредикат равенства (совпадение точек) и двуместный предикат «находиться на расстоянии 1». Выразите двуместные предикаты «находитьсяна расстоянии 2» и «находиться на расстоянии не более 2».
Выразите двуместный предикат «находиться на расстоянии 1/2».3.4. Выразимость в арифметикеРассмотрим сигнатуру, имеющую два двуместных функциональных символа — сложение и умножение (как обычно, мы будем писатьx + y вместо +(x, y) и т. д.) и двуместный предикатный символ равенства. Рассмотрим интерпретацию этой сигнатуры, носителем которой является множество N натуральных чисел, а сложение, умножение и равенство интерпретируются стандартным образом.Выразимые с помощью формул этой сигнатуры предикаты называются арифметическими и играют в математической логике важную роль.
Соответствующие множества также называются арифметическими. О них подробно рассказано в другой нашей книжке [5];оказывается, что почти всякое множество, которое можно описатьсловами, является арифметическим.58. Докажите, что существует множество натуральных чисел, не являющееся арифметическим. (Указание: семейство всех подмножеств множества N несчётно, а арифметических множеств счётное число.)Для начала мы установим арифметичность довольно простыхпредикатов.• Предикат x 6 y является арифметическим. В самом деле, егоможно записать как ∃z (x + z = y).• Предикаты x = 0 и x = 1 являются арифметическими. В самом деле, x = 0 тогда и только тогда, когда x 6 y для любого[п. 4]Выразимость в арифметике83y (а также когда x + x = x).
А x = 1 тогда и только тогда, когда x представляет собой наименьшее число, отличное от нуля.(Можно также воспользоваться тем, что y · 1 = y при любом y.)• Вообще для любого фиксированного числа c предикат x = cявляется арифметическим. (Например, можно написать суммуиз большого числа единиц.)• Полезно такое общее наблюдение: если мы уже установили, чтокакой-то предикат является арифметическим, то в дальнейшемего можно использовать в формулах, как если бы он входил всигнатуру, поскольку его всегда можно заменить на выражающую его формулу.• Предикат x|y (число x является делителем числа y), очевидно,арифметичен (формула ∃z (xz = y)).• Предикат «x — простое число» арифметичен. В самом деле,число просто, если оно отлично от 1 и любой его делитель равен 1 или самому числу.
Это сразу же записывается в видеформулы.• Операции частного и остатка арифметичны (в том смысле, чтотрёхместные предикаты «q есть частное при делении a на b» и«r есть остаток при делении a на b» арифметичны. Например,первый из них записывается формулой ∃r ((a = bq +r)∧(r < b))(как мы уже говорили, использование арифметического предиката (r < b) не создаёт проблем).• Этот список можно продолжать: для многих предикатов ихопределение по существу уже является нужной формулой. Например, свойства «быть наибольшим общим делителем», «бытьнаименьшим общим кратным», «быть взаимно простыми» всеотносятся к этой категории.• Предикат «быть степенью двойки» является арифметическим(хотя это и не столь очевидно, как в предыдущих примерах).
Всамом деле, это свойство можно переформулировать так: любой делитель либо равен единице, либо чётен.Последнее из наших рассуждений годится для степеней тройкии вообще для степеней любого простого числа. Однако, скажем, для84Языки первого порядка[гл. 3]степеней шестёрки оно не проходит, и, пожалуй, мы подошли к границе, где без некоторого общего метода не обойтись.Два наиболее известных способа доказывать арифметичность основаны на возможности «кодирования» конечных множеств и последовательностей.
Один из них восходит к Гёделю (так называемаяβ-функция Гёделя), второй изложен в книге «Теория формальныхсистем» [24]. Её написал Р. Смаллиан, известный также как авторпопулярных сборников «логических задач» и анекдотов. (Один изтаких сборников имеет парадоксальное название «Как же называется эта книга?» [23].)В некоторых отношениях метод Гёделя предпочтительней, и мырассказываем о нём в книжке о вычислимых функциях [5], но сейчасдля разнообразия рассмотрим другой способ.
Зафиксируем взаимнооднозначное соответствие между натуральными числами и двоичными словами:0Λ1 2 30 1 0040151061170008 ...001 . . .Это соответствие задаётся так: чтобы получить слово, соответствующее числу n, надо записать n + 1 в двоичной системе и удалитьпервую единицу. Например, нулю соответствует пустое слово Λ, числу 15 — слово 0000 и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
