Языки и исчисления

Языки первого порядка

Разбить на страницы
Показывать лекцию целиком

Помимо логических связок, в математических рассуждениях часто встречаются кванторы "для любого" ( $$\forall$$ ) и "существует" ( $$\exists$$ ). Например, определение непрерывности начинается словами "для любого положительного $$\varepsilon$$ найдется положительное $$\delta$$, для которого, ...". А одна из аксиом теории групп (существование обратного элемента) записывается так: $$\forall x \exists y ((xy\hm=1)\land(yx\hm=1))$$.

Можно сформулировать различные логические законы, включающие в себя кванторы. Например, высказывание "существует такое $$x$$, что $$A$$ " (где $$A$$ — некоторое свойство объекта $$x$$ ) логически эквивалентно высказыванию "не для всех $$x$$ верно $$\lnot A$$ ".

Мы будем записывать такого рода законы с помощью формул, дадим определение истинности формул (при данной интерпретации входящих в них символов) и исследуем, какого рода свойства можно выражать с помощью формул и какие нельзя.

Формулы и интерпретации

Начнем с примера. Пусть $$M$$ — некоторое непустое множество, а $$R$$ — бинарное отношение на нем, то есть подмножество декартова произведения $$M\hm\times M$$. Вместо $$\langle x,y\rangle\hm\in R$$ мы будем писать $$R(x,y)$$. Рассмотрим формулу$$\forall x\, \exists y\, R(x,y).$$ Эта формула выражает некоторое свойство бинарного отношения $$R$$ (для любого элемента $$x\in M$$ найдется элемент, находящийся с ним в отношении $$R$$ ) и может быть истинна или ложна. Например, если $$M$$ есть множество натуральных чисел $$\mathbb{N}$$, а $$R$$ — отношение "строго меньше" (другими словами, $$R$$ есть множество всех пар $$\langle x,y\rangle$$, для которых $$x\hm<y$$ ), то эта формула истинна. А для отношения "строго больше" (на том же множестве) эта формула ложна.

Вопрос о том, будет ли истинна формула$$\exists y\, R(x,y)$$ для данного множества $$M$$ и для данного бинарного отношения $$R$$ на нем, не имеет смысла, пока не уточнено, каково значение переменной $$x$$. Например, если $$M=\mathbb{N}$$ и $$R(x,y)$$ есть $$x\hm>y$$, то эта формула будет истинной при $$x=3$$ и ложной при $$x=0$$. Для данных $$M$$ и $$R$$ она задает некоторое свойство элемента $$x$$ и тем самым определяет некоторое подмножество множества $$M$$.

Перейдем к формальным определениям. Пусть $$M$$ — непустое множество. Множество $$M^k$$ состоит из всех последовательностей $$\langle m_1,\dots,m_k\rangle$$ длины $$k$$, составленных из элементов множества $$M$$. Назовем $$k$$ -местной функцией на множестве $$M$$ любое отображение $$M^k$$ в $$M$$ (определенное на всем $$M^k$$ ). Синонимы: "функция $$k$$ аргументов", "функция валентности $$k$$ ", "функция местности $$k$$ " и даже "функция арности $$k$$ " (последнее слово происходит от слов "унарная" для функций одного аргумента, "бинарная" (операция) для функций двух аргументов и "тернарная" для трех аргументов).

Назовем $$k$$ -местным предикатом на множестве $$M$$ любое отображение $$M^k$$ в множество $$\mathbb{B}=\{\text{И},\text{Л}\}$$. Такой предикат будет истинным на некоторых наборах $$\langle m_1,\dots,m_k\rangle$$ множества $$M$$ и ложным на остальных наборах. Поставив ему в соответствие множество тех наборов, где он истинен, мы получаем взаимно однозначное соответствие между $$k$$ -местными предикатами на $$M$$ и подмножествами множества $$M^k$$. Говоря о предикатах, также употребляют термины "валентность", "число аргументов" и др.

Мы будем рассматривать также функции и предикаты валентности нуль. Множество $$M^0$$ одноэлементно (содержит единственную последовательность длины $$0$$ ). Поэтому функции $$M^0\to M$$ отождествляются с элементами множества $$M$$, а нульместных предикатов ровно два — истинный и ложный.

Естественно, что в формулы будут входить не сами функции и предикаты, а обозначения для них, которые называют функциональными и предикатными символами. В качестве символов можно использовать любые знаки. Важно лишь, что каждому символу приписана валентность, которая определяет, со сколькими аргументами он может встречаться в формуле. Произвольный набор предикатных и функциональных символов, для каждого из которых указано неотрицательное число, называемое валентностью, мы будем называть сигнатурой.

Остается определить три вещи: что такое формула данной сигнатуры, что такое интерпретация данной сигнатуры и когда формула является истинной (в данной интерпретации).

Фиксируем некоторый набор символов, называемых индивидными переменными. Они предназначены для обозначения элементов множества, на котором определены функции и предикаты; обычно в таком качестве используют латинские буквы $$x,y,z,u,v,w$$ с индексами. В каждой формуле будет использоваться конечное число переменных, так что счетного набора переменных нам хватит. Мы предполагаем, что переменные отличны от всех функциональных и предикатных символов сигнатуры (иначе выйдет путаница).

Определим понятие терма данной сигнатуры. Термом называется последовательность переменных, запятых, скобок и символов сигнатуры, которую можно построить по следующим правилам:

  • Индивидная переменная есть терм.
  • Функциональный символ валентности $$0$$ есть терм.
  • Если $$t_1,\dots,t_k$$ — термы, а $$f$$ — функциональный символ валентности $$k>0$$, то $$f(t_1,\dots,t_k)$$ есть терм.
    •

    В принципе можно было не выделять функциональные символы валентности $$0$$ (которые также называют константами) в отдельную группу, но тогда бы после них пришлось писать скобки (как это делается в программах на языке Си).

    Если $$A$$ — предикатный символ валентности $$k$$, а $$t_1,\dots,t_k$$ — термы, то выражение $$A(t_1,\dots,t_k)$$ считается атомарной формулой. Кроме того, любой предикатный символ валентности $$0$$ считается атомарной формулой.

    Формулы строятся по таким правилам:

  • Атомарная формула есть формула.
  • Если $$\varphi$$ — формула, то $$\lnot\varphi$$ — формула.
  • Если $$\varphi$$ и $$\psi$$ — формулы, то выражения $$(\varphi \land\psi)$$, $$(\varphi\hm\lor\psi)$$, $$(\varphi\to\psi)$$ также являются формулами.
  • Если $$\varphi$$ есть формула, а $$\xi$$ — индивидная переменная, то выражения $$\forall \xi \,\varphi$$ и $$\exists \xi\,\varphi$$ являются формулами.
    •

    Во многих случаях в сигнатуру входит двуместный предикатный символ $$=$$, называемый равенством. По традиции вместо $$=(t_1,t_2)$$ пишут $$(t_1=t_2)$$.

    Итак, понятие формулы в данной сигнатуре полностью определено. Иногда такие формулы называют формулами первого порядка данной сигнатуры, или формулами языка первого порядка с данной сигнатурой.

    Наш следующий шаг — определение интерпретации данной сигнатуры. Пусть фиксирована некоторая сигнатура $$\sigma$$. Чтобы задать интерпретацию сигнатуры $$\sigma$$, необходимо:

  • указать некоторое непустое множество $$M$$, называемое носителем интерпретации;
  • для каждого предикатного символа сигнатуры $$\sigma$$ указать предикат с соответствующим числом аргументов, определенный на множестве $$M$$ (как мы уже говорили, $$0$$ -местным предикатным символам ставится в соответствие либо И, либо Л );
  • для каждого функционального символа сигнатуры $$\sigma$$ указать функцию соответствующего числа аргументов с аргументами и значениями из $$M$$ (в частности, для $$0$$ -местных функциональных символов надо указать элемент множества $$M$$, с ними сопоставляемый).
    •

    Если сигнатура включает в себя символ равенства, то среди ее интерпретаций выделяют нормальные интерпретации, в которых символ равенства интерпретируется как совпадение элементов множества $$M$$.

    Приведем несколько примеров сигнатур, используемых в различных теориях.

    Сигнатура теории упорядоченных множеств включает в себя два двуместных предикатных символа (равенство и порядок) и не имеет функциональных символов. Здесь также вместо $$\le(x,y)$$ по традиции пишут $$x \le y$$.

    Аксиомы порядка (рефлексивность, антисимметричность, транзитивность) могут быть записаны формулами этой сигнатуры. Например, требование антисимметричности записывается так:$$\forall x\,\forall y (((x\le y)\land (y\le x))\to(x=y)).$$

    Иногда в сигнатуру теории упорядоченных множеств вместо символа $$\le$$ включают символ $$<<$$ ; большой разницы тут нет.

    39. Как записать с помощью формулы свойство линейной упорядоченности? свойство не иметь наибольшего элемента? свойство плотности (отсутствия соседних элементов)? свойство фундированности (отсутствия бесконечных убывающих последовательностей — или, что эквивалентно, наличия минимального элемента в любом подмножестве)? свойство полной упорядоченности? (Указание: не для всех перечисленных свойств это возможно.)

    Сигнатуру теории групп можно выбирать по-разному. Можно считать, что (помимо равенства) она имеет двуместный функциональный символ $$\times$$ (который по традиции записывают между множителями), константу (нульместный функциональный символ) $$1$$ и одноместный функциональный символ $$\inv(x)$$ для обращения. Тогда аксиомы теории групп записываются с использованием лишь кванторов всеобщности:$$\begin{align*} \forall x\,\forall y\,\forall z (((x\times y)\times z)=(x\times(y\times z))),\\ \forall x\, (((x\times 1)= x)\land((1\times x)=x)),\\ \forall x\, (((x\times inv(x))= 1)\land((inv(x)\times x)=1)). \end{align*}$$

    Если не включать операцию обращения в сигнатуру, придется использовать квантор существования и переписать последнюю аксиому так:$$\forall x\, \exists y\,((( x\times y)= 1)\land((y\times x)=1)).$$

    40. Как записать аксиомы теории групп, если в сигнатуре нет константы $$1$$? (Указание: аксиома о существовании обратного станет частью аксиомы о существовании единицы.)

    41. Как записать в виде формулы требование коммутативности группы? утверждение о том, что любой элемент (кроме единицы) имеет порядок $$11$$? конечность группы? (Указание: не все из перечисленного можно записать, хотя пока у нас нет средств это установить.)

    Сигнатура теории множеств содержит два двуместных предикатных символа: для принадлежности и для равенства. Аксиомы теории множеств можно записывать в виде формул этой сигнатуры. Чаще всего рассматривают вариант аксиоматической теории множеств, называемый теорией Цермело-Френкеля и обозначаемый ZF. Приведем для примера одну из аксиом теории ZF, называемую аксиомой объемности, или экстенсиональности:$$\begin\forall x\,\forall y\,((\forall z\,((z\in x)\to(z\in y))\land \forall z\,((z\in y)\to(z\in x))) \to\\ {}\to(x=y)). \end$$

    42. Сформулировать словесно эту аксиому.

    43. Записать в виде формулы аксиому регулярности, или фундирования, которая говорит, что у всякого множества есть минимальный (с точки зрения отношения $$\in$$ ) элемент, то есть элемент, не пересекающийся с самим множеством.

    44. Какова естественная сигнатура для теории полей? Можно ли записать в виде формулы этой сигнатуры утверждение о том, что поле имеет характеристику $$2$$? конечную характеристику? алгебраически замкнуто?

    Определение истинности

    Из приведенных выше примеров, вероятно, понятен смысл формулы, то есть ясно, в каких интерпретациях данной сигнатуры и для каких элементов формула истинна. Тем не менее для любителей строгости мы приведем формальное определение истинности. (Его детали понадобятся, когда мы будем проверять истинность выводимых формул, см. раздел "Корректность исчисления предикатов"

    Прежде всего, определим формально понятие параметра формулы (переменной, от значения которой может зависеть истинность формулы). Согласно этому определению, скажем, формула $$\forall x\,\exists y\, A(x,y)$$ не имеет параметров, а формулы $$\exists y\, A(x,y)$$ и $$(A(x)\land \forall x\, B(x,x))$$ имеют единственный параметр $$x$$. Вот как выглядит это определение:

  • Параметрами терма являются все входящие в него индивидные переменные.
  • Параметрами атомарной формулы являются параметры всех входящих в нее термов.
  • Параметры формулы $$\lnot \varphi$$ те же, что у формулы $$\varphi$$.
  • Параметрами формул $$(\varphi\land\psi)$$, $$(\varphi\lor\psi)$$ и $$(\varphi\to\psi)$$ являются все параметры формулы $$\varphi$$, а также все параметры формулы $$\psi$$.
  • Параметрами формул $$\forall\xi\,\varphi$$ и $$\exists\xi\,\varphi$$ являются все параметры формулы $$\varphi$$, кроме переменной $$\xi$$.
    •

    Параметры иногда называют свободными переменными формулы. Заметим, что формула может иметь одновременно параметр $$x$$ и использовать (в другом месте) квантор $$\forall x$$. Как говорят в этом случае, одна и та же переменная имеет свободные и связанные вхождения. Свободное вхождение переменной — это такое вхождение, которое не входит в область действия одноименного квантора. Если аккуратно определить эту область действия, несложно проверить, что параметры формулы — это как раз переменные, имеющие свободные вхождения.

    Теперь мы хотим определить понятие формулы, истинной в данной интерпретации при данных значениях параметров. Технически проще считать, что всем индивидным переменным приписаны какие-то значения, а потом доказать, что переменные, не являющиеся параметрами, не влияют на истинность формулы.

    Итак, пусть фиксирована сигнатура и некоторая интерпретация этой сигнатуры. Оценкой назовем отображение, которое ставит в соответствие каждой индивидной переменной некоторый элемент множества, являющегося носителем интерпретации. Этот элемент будем называть значением переменной при данной оценке.

    Определим индуктивно значение терма $$t$$ при данной оценке $$\pi$$, которое мы будем обозначать $$[t](\pi)$$.

  • Для переменных оно уже определено.
  • Если $$t$$ является константой (нульместным функциональным символом), то $$[t](\pi)$$ не зависит от $$\pi$$ и равно значению этой константы при данной интерпретации (напомним, в интерпретации с каждой константой сопоставляется некоторый элемент носителя).
  • Если $$t$$ имеет вид $$f(t_1,\dots,t_m)$$, где $$f$$ — функциональный символ валентности $$m$$, а $$t_1,\dots,t_m$$ — термы, то $$[t](\pi)$$ есть $$[f]([t_1](\pi),\dots,[t_m](\pi))$$, где $$[f]$$ есть функция, соответствующая символу $$f$$ в нашей интерпретации, а $$[t_i](\pi)$$ есть значение терма $$t_i$$ при оценке $$\pi$$.
    •

    Теперь можно определить значение формулы $$\varphi$$ при данной оценке $$\pi$$ в данной интерпретации, которое обозначается $$[\varphi](\pi)$$ и может быть равно И или Л ; в первом случае формула называется истинной, во втором — ложной. Это определение также индуктивно:

  • Значение атомарной формулы $$A(t_1,\dots,t_m)$$ определяется как $$[A]([t_1](\pi),\dots,[t_m](\pi))$$, где $$[A]$$ — предикат, соответствующий предикатному символу $$A$$ в рассматриваемой интерпретации. Если формула представляет собой нульместный предикатный символ, то ее значение не зависит от оценки и есть значение этого символа.
  • $$[\lnot \varphi](\pi)$$ определяется как $$\lnot [\varphi(\pi)]$$, где $$\lnot$$ понимается как операция в $$\mathbb{B}$$. Другими словами, формула $$\lnot \varphi$$ истинна при оценке $$\pi$$ тогда и только тогда, когда формула $$\varphi$$ ложна при этой оценке.
  • $$[\varphi \land \psi](\pi)$$ определяется как $$[\varphi](\pi)\land [\psi](\pi)$$, где $$\land$$ в правой части понимается как операция в $$\mathbb{B}$$. (Другими словами, формула $$(\varphi\land\psi)$$ истинна при оценке $$\pi$$ тогда и только тогда, когда обе формулы $$\varphi$$ и $$\psi$$ истинны при этой оценке.) Аналогичным образом $$[\varphi \lor \psi](\pi)$$ определяется как $$[\varphi](\pi)\lor [\psi](\pi)$$, а $$[\varphi \to \psi](\pi)$$ — как $$[\varphi](\pi)\to [\psi](\pi)$$.
  • Формула $$\forall \xi\,\varphi$$ истинна на оценке $$\pi$$ тогда и только тогда, когда формула $$\varphi$$ истинна на любой оценке $$\pi'$$, которая совпадает с $$\pi$$ всюду, кроме значения переменной $$\xi$$ (которое в оценке $$\pi'$$ может быть любым). Другими словами, если обозначить через $$\pi+(\xi\mapsto m)$$ оценку, при которой значение переменной $$\xi$$ равно $$m$$, а остальные переменные принимают те же значения, что и в оценке $$\pi$$, то$$[\forall \xi\, \varphi](\pi)= \bigwedge_{m\in M} [\varphi](\pi+(\xi\mapsto m)).$$ (В правой части стоит бесконечная конъюнкция, которая истинна, если все ее члены истинны.)
  • Формула $$\exists \xi\,\varphi$$ истинна на оценке $$\pi$$ тогда и только тогда, когда формула $$\varphi$$ истинна на некоторой оценке $$\pi'$$, которая совпадает с $$\pi$$ всюду, кроме значения переменной $$\xi$$ (которое в оценке $$\pi'$$ может быть любым). Другими словами,$$[\forall \xi\, \varphi](\pi)= \bigvee_{m\in M} [\varphi](\pi+(\xi\mapsto m)).$$ (В правой части стоит бесконечная дизъюнкция, которая истинна, если хотя бы один из ее членов истинен.)
    •

    Заметим, что в двух последних пунктах значение переменной $$\xi$$ в оценке $$\pi$$ не играет роли. Это позволяет легко доказать (индукцией по построению формулы) такое утверждение: если две оценки $$\pi_1$$ и $$\pi_2$$ придают одинаковые значения всем параметрам формулы $$\varphi$$, то $$[\varphi](\pi_1)\hm= [\varphi](\pi_2)$$. Другими словами, истинность формулы определяется значениями ее параметров.

    45. Проведите это индуктивное рассуждение подробно.

    46. Приведенные выше определения применимы к любой формуле, в том числе и к странной формуле $$\forall y\, A(x)$$. Какие у нее параметры? При каких значениях параметров она истинна? (Ответ: она имеет единственный параметр $$x$$ и эквивалентна формуле $$A(x)$$.)

    47. В каком случае будет истинна формула $$\forall x\,\exists x\,A(x)$$? Тот же вопрос для формулы $$\exists x\,\forall x\, A(x)$$. (Ответ: первая из этих формул эквивалентна формуле $$\exists x\, A(x)$$, а вторая — формуле $$\forall x\, A(x)$$.)

    Формула называется замкнутой, если она не имеет параметров. Замкнутые формулы называют также суждениями. Как мы доказали, истинность замкнутой формулы определяется выбором интерпретации (и не зависит от значений переменных).

    Выразимые предикаты

    Пусть фиксирована некоторая сигнатура $$\sigma$$ и ее интерпретация с носителем $$M$$. Мы хотим определить понятие выразимого (с помощью формулы данной сигнатуры в данной интерпретации) $$k$$ -местного предиката.

    Выберем $$k$$ переменных $$x_1,\dots, x_k$$. Рассмотрим произвольную формулу $$\varphi$$, все параметры которой содержатся в списке $$x_1,\dots,x_k$$. Истинность этой формулы зависит только от значений переменных $$x_1,\dots,x_k$$. Тем самым возникает отображение $$M^k\to\mathbb{B}=\{И, Л\}$$, то есть некоторый $$k$$ - местный предикат на $$M$$. Говорят, что этот предикат выражается формулой $$\varphi$$. Все предикаты, которые можно получить таким способом, называются выразимыми. (Ясно, что конкретный выбор списка переменных роли не играет.) Соответствующие им подмножества множества $$M^k$$ (области истинности выразимых предикатов) также называют выразимыми.

    48. Докажите, что пересечение, объединение и разность двух выразимых множеств являются выразимыми. Докажите, что проекция $$k$$ - мерного выразимого множества вдоль одной из "осей координат" является $$(k-1)$$ -мерным выразимым множеством.

    Пример. Сигнатура содержит одноместный функциональный символ $$S$$ и двуместный предикатный символ равенства ( $$=$$ ). Рассмотрим интерпретацию этой сигнатуры. В качестве носителя выберем натуральный ряд $$\mathbb{N}$$. Символ $$S$$ будет обозначать функцию прибавления единицы (можно считать $$S$$ сокращением от слова successor — последователь). Знак равенства интерпретируется как совпадение элементов.

    Легко проверить, что одноместный предикат "быть нулем" выразим в этой интерпретации, несмотря на то, что константы для нуля в сигнатуре не предусмотрено. В самом деле, он выражается формулой$$\lnot\exists y (x=S(y))$$ с единственным параметром $$x$$.

    Еще проще выразить в этой сигнатуре двуместный предикат "быть больше на $$2$$ ", при этом даже не нужны кванторы: $$y=S(S(x))$$.

    Любопытно, что уже в такой простой ситуации можно сформулировать содержательную задачу: выразить предикат $$y=x+N$$, где $$N$$ — большое число (скажем, миллиард), с помощью существенно более короткой формулы, чем $$y=S(S(\dots(S(x))\dots))$$. Как ни удивительно, это вполне возможно, и соответствующую формулу вполне можно уместить на листе бумаги.

    49. Докажите, что предикат $$y=x+N$$ можно выразить формулой указанной сигнатуры, длина которой есть $$O(\log N)$$. (Указание. Если мы научились выражать $$y=x+n$$, можно выразить $$y=x+2n$$ с помощью формулы$$\exists z\, ((z=x+n)\land(y=z+n))$$ (в которой через $$z=x+n$$ и $$y=z+n$$ обозначены соответствующие формулы). Это само по себе ничего не дает, так как длина формулы увеличилась вдвое, но можно использовать такой трюк:$$\exists z\, \forall u\,\forall v (((u=x\land v=z)\lor(u=z\land v=y))\to(v=u+n)).$$ Далее можно воспользоваться записью числа $$N$$ в двоичной системе счисления.)

    Можно доказать, что в этой сигнатуре кванторы почти не увеличивают набор выразимых предикатов: всякий выразимый предикат будет выражаться бескванторной формулой (возможно, гораздо более длинной), если добавить к сигнатуре константу $$0$$. Мы вернемся к этому вопросу в разделе "Элиминация кванторов".

    Чтобы привыкнуть к понятию выразимости, рассмотрим еще один пример. Пусть сигнатура содержит предикат равенства и трехместный предикат $$C$$. Рассмотрим интерпретацию, в которой носителем является множество точек плоскости, равенство интерпретируется как совпадение точек, а $$C(x,y,z)$$ означает, что точки $$x$$ и $$y$$ равноудалены от точки $$z$$. Оказывается, что этого предиката достаточно, чтобы выразить более или менее все традиционные понятия элементарной геометрии.

    Как, например, записать, что три различные точки $$A,B,C$$ лежат на одной прямой? Вот как: "не существует другой точки $$C'$$, которая находилась бы на тех же расстояниях от $$A$$ и $$B$$, что и точка $$C$$ ".

    50. Напишите соответствующую формулу указанной сигнатуры.

    Теперь легко выразить такое свойство четырех точек $$A,B,C,D$$: "точки $$A$$ и $$B$$ различны, точки $$C$$ и $$D$$ различны и прямые $$AB$$ и $$CD$$ параллельны". В самом деле, надо написать, что нет точки, которая бы одновременно лежала на одной прямой с $$A$$ и $$B$$, а также на одной прямой с $$C$$ и $$D$$.

    После этого можно выразить свойство четырех точек "быть вершинами параллелограмма". Это позволяет переносить отрезок параллельно себе. После этого несложно выразить такое свойство: "расстояние $$AB$$ равно расстоянию $$CD$$ ".

    51. Запишите соответствующую формулу.

    Аналогичным образом можно двигаться и дальше.

    52. Выразите свойство $$|OA|\le |OB|$$ трех точек $$O$$, $$A$$, $$B$$. (Указание. Напишите, что все прямые, проходящие через $$A$$, пересекаются с окружностью радиуса $$OB$$ с центром в $$O$$.)

    53. Запишите в виде формулы: (а) равенство треугольников; (б) равенство углов; (в) свойство угла быть прямым.

    54. Рассмотрим естественную интерпретацию сигнатуры $$({=},{<})$$ на множестве целых чисел. Как выразить предикат $$y=x+1$$?

    55. Рассмотрим множество действительных чисел как интерпретацию сигнатуры $$({=},{+}, {y=x^2})$$. Как выразить трехместный предикат $$xy=z$$?

    56. Рассмотрим множество целых положительных чисел как интерпретацию сигнатуры, содержащей равенство и двуместный предикат " $$x$$ делит $$y$$ ". Выразите свойства "равняться единице" и "быть простым числом".

    57. Рассмотрим плоскость как интерпретацию сигнатуры, содержащей предикат равенства (совпадение точек) и двуместный предикат "находиться на расстоянии $$1$$ ". Выразите двуместные предикаты "находиться на расстоянии $$2$$ " и "находиться на расстоянии не более $$2$$ ". Выразите двуместный предикат "находиться на расстоянии $$1/2$$.

    Страницы:

    Помимо логических связок, в математических рассуждениях часто встречаются кванторы "для любого" ( $$\forall$$ ) и "существует" ( $$\exists$$ ). Например, определение непрерывности начинается словами "для любого положительного $$\varepsilon$$ найдется положительное $$\delta$$, для которого, ...". А одна из аксиом теории групп (существование обратного элемента) записывается так: $$\forall x \exists y ((xy\hm=1)\land(yx\hm=1))$$.

    Можно сформулировать различные логические законы, включающие в себя кванторы. Например, высказывание "существует такое $$x$$, что $$A$$ " (где $$A$$ — некоторое свойство объекта $$x$$ ) логически эквивалентно высказыванию "не для всех $$x$$ верно $$\lnot A$$ ".

    Мы будем записывать такого рода законы с помощью формул, дадим определение истинности формул (при данной интерпретации входящих в них символов) и исследуем, какого рода свойства можно выражать с помощью формул и какие нельзя.

    Формулы и интерпретации

    Начнем с примера. Пусть $$M$$ — некоторое непустое множество, а $$R$$ — бинарное отношение на нем, то есть подмножество декартова произведения $$M\hm\times M$$. Вместо $$\langle x,y\rangle\hm\in R$$ мы будем писать $$R(x,y)$$. Рассмотрим формулу$$\forall x\, \exists y\, R(x,y).$$ Эта формула выражает некоторое свойство бинарного отношения $$R$$ (для любого элемента $$x\in M$$ найдется элемент, находящийся с ним в отношении $$R$$ ) и может быть истинна или ложна. Например, если $$M$$ есть множество натуральных чисел $$\mathbb{N}$$, а $$R$$ — отношение "строго меньше" (другими словами, $$R$$ есть множество всех пар $$\langle x,y\rangle$$, для которых $$x\hm<y$$ ), то эта формула истинна. А для отношения "строго больше" (на том же множестве) эта формула ложна.

    Вопрос о том, будет ли истинна формула$$\exists y\, R(x,y)$$ для данного множества $$M$$ и для данного бинарного отношения $$R$$ на нем, не имеет смысла, пока не уточнено, каково значение переменной $$x$$. Например, если $$M=\mathbb{N}$$ и $$R(x,y)$$ есть $$x\hm>y$$, то эта формула будет истинной при $$x=3$$ и ложной при $$x=0$$. Для данных $$M$$ и $$R$$ она задает некоторое свойство элемента $$x$$ и тем самым определяет некоторое подмножество множества $$M$$.

    Перейдем к формальным определениям. Пусть $$M$$ — непустое множество. Множество $$M^k$$ состоит из всех последовательностей $$\langle m_1,\dots,m_k\rangle$$ длины $$k$$, составленных из элементов множества $$M$$. Назовем $$k$$ -местной функцией на множестве $$M$$ любое отображение $$M^k$$ в $$M$$ (определенное на всем $$M^k$$ ). Синонимы: "функция $$k$$ аргументов", "функция валентности $$k$$ ", "функция местности $$k$$ " и даже "функция арности $$k$$ " (последнее слово происходит от слов "унарная" для функций одного аргумента, "бинарная" (операция) для функций двух аргументов и "тернарная" для трех аргументов).

    Назовем $$k$$ -местным предикатом на множестве $$M$$ любое отображение $$M^k$$ в множество $$\mathbb{B}=\{\text{И},\text{Л}\}$$. Такой предикат будет истинным на некоторых наборах $$\langle m_1,\dots,m_k\rangle$$ множества $$M$$ и ложным на остальных наборах. Поставив ему в соответствие множество тех наборов, где он истинен, мы получаем взаимно однозначное соответствие между $$k$$ -местными предикатами на $$M$$ и подмножествами множества $$M^k$$. Говоря о предикатах, также употребляют термины "валентность", "число аргументов" и др.

    Мы будем рассматривать также функции и предикаты валентности нуль. Множество $$M^0$$ одноэлементно (содержит единственную последовательность длины $$0$$ ). Поэтому функции $$M^0\to M$$ отождествляются с элементами множества $$M$$, а нульместных предикатов ровно два — истинный и ложный.

    Естественно, что в формулы будут входить не сами функции и предикаты, а обозначения для них, которые называют функциональными и предикатными символами. В качестве символов можно использовать любые знаки. Важно лишь, что каждому символу приписана валентность, которая определяет, со сколькими аргументами он может встречаться в формуле. Произвольный набор предикатных и функциональных символов, для каждого из которых указано неотрицательное число, называемое валентностью, мы будем называть сигнатурой.

    Остается определить три вещи: что такое формула данной сигнатуры, что такое интерпретация данной сигнатуры и когда формула является истинной (в данной интерпретации).

    Фиксируем некоторый набор символов, называемых индивидными переменными. Они предназначены для обозначения элементов множества, на котором определены функции и предикаты; обычно в таком качестве используют латинские буквы $$x,y,z,u,v,w$$ с индексами. В каждой формуле будет использоваться конечное число переменных, так что счетного набора переменных нам хватит. Мы предполагаем, что переменные отличны от всех функциональных и предикатных символов сигнатуры (иначе выйдет путаница).

    Определим понятие терма данной сигнатуры. Термом называется последовательность переменных, запятых, скобок и символов сигнатуры, которую можно построить по следующим правилам:

  • Индивидная переменная есть терм.
  • Функциональный символ валентности $$0$$ есть терм.
  • Если $$t_1,\dots,t_k$$ — термы, а $$f$$ — функциональный символ валентности $$k>0$$, то $$f(t_1,\dots,t_k)$$ есть терм.
    •

    В принципе можно было не выделять функциональные символы валентности $$0$$ (которые также называют константами) в отдельную группу, но тогда бы после них пришлось писать скобки (как это делается в программах на языке Си).

    Если $$A$$ — предикатный символ валентности $$k$$, а $$t_1,\dots,t_k$$ — термы, то выражение $$A(t_1,\dots,t_k)$$ считается атомарной формулой. Кроме того, любой предикатный символ валентности $$0$$ считается атомарной формулой.

    Формулы строятся по таким правилам:

  • Атомарная формула есть формула.
  • Если $$\varphi$$ — формула, то $$\lnot\varphi$$ — формула.
  • Если $$\varphi$$ и $$\psi$$ — формулы, то выражения $$(\varphi \land\psi)$$, $$(\varphi\hm\lor\psi)$$, $$(\varphi\to\psi)$$ также являются формулами.
  • Если $$\varphi$$ есть формула, а $$\xi$$ — индивидная переменная, то выражения $$\forall \xi \,\varphi$$ и $$\exists \xi\,\varphi$$ являются формулами.
    •

    Во многих случаях в сигнатуру входит двуместный предикатный символ $$=$$, называемый равенством. По традиции вместо $$=(t_1,t_2)$$ пишут $$(t_1=t_2)$$.

    Итак, понятие формулы в данной сигнатуре полностью определено. Иногда такие формулы называют формулами первого порядка данной сигнатуры, или формулами языка первого порядка с данной сигнатурой.

    Наш следующий шаг — определение интерпретации данной сигнатуры. Пусть фиксирована некоторая сигнатура $$\sigma$$. Чтобы задать интерпретацию сигнатуры $$\sigma$$, необходимо:

  • указать некоторое непустое множество $$M$$, называемое носителем интерпретации;
  • для каждого предикатного символа сигнатуры $$\sigma$$ указать предикат с соответствующим числом аргументов, определенный на множестве $$M$$ (как мы уже говорили, $$0$$ -местным предикатным символам ставится в соответствие либо И, либо Л );
  • для каждого функционального символа сигнатуры $$\sigma$$ указать функцию соответствующего числа аргументов с аргументами и значениями из $$M$$ (в частности, для $$0$$ -местных функциональных символов надо указать элемент множества $$M$$, с ними сопоставляемый).
    •

    Если сигнатура включает в себя символ равенства, то среди ее интерпретаций выделяют нормальные интерпретации, в которых символ равенства интерпретируется как совпадение элементов множества $$M$$.

    Приведем несколько примеров сигнатур, используемых в различных теориях.

    Сигнатура теории упорядоченных множеств включает в себя два двуместных предикатных символа (равенство и порядок) и не имеет функциональных символов. Здесь также вместо $$\le(x,y)$$ по традиции пишут $$x \le y$$.

    Аксиомы порядка (рефлексивность, антисимметричность, транзитивность) могут быть записаны формулами этой сигнатуры. Например, требование антисимметричности записывается так:$$\forall x\,\forall y (((x\le y)\land (y\le x))\to(x=y)).$$

    Иногда в сигнатуру теории упорядоченных множеств вместо символа $$\le$$ включают символ $$<<$$ ; большой разницы тут нет.

    39. Как записать с помощью формулы свойство линейной упорядоченности? свойство не иметь наибольшего элемента? свойство плотности (отсутствия соседних элементов)? свойство фундированности (отсутствия бесконечных убывающих последовательностей — или, что эквивалентно, наличия минимального элемента в любом подмножестве)? свойство полной упорядоченности? (Указание: не для всех перечисленных свойств это возможно.)

    Сигнатуру теории групп можно выбирать по-разному. Можно считать, что (помимо равенства) она имеет двуместный функциональный символ $$\times$$ (который по традиции записывают между множителями), константу (нульместный функциональный символ) $$1$$ и одноместный функциональный символ $$\inv(x)$$ для обращения. Тогда аксиомы теории групп записываются с использованием лишь кванторов всеобщности:$$\begin{align*} \forall x\,\forall y\,\forall z (((x\times y)\times z)=(x\times(y\times z))),\\ \forall x\, (((x\times 1)= x)\land((1\times x)=x)),\\ \forall x\, (((x\times inv(x))= 1)\land((inv(x)\times x)=1)). \end{align*}$$

    Если не включать операцию обращения в сигнатуру, придется использовать квантор существования и переписать последнюю аксиому так:$$\forall x\, \exists y\,((( x\times y)= 1)\land((y\times x)=1)).$$

    40. Как записать аксиомы теории групп, если в сигнатуре нет константы $$1$$? (Указание: аксиома о существовании обратного станет частью аксиомы о существовании единицы.)

    41. Как записать в виде формулы требование коммутативности группы? утверждение о том, что любой элемент (кроме единицы) имеет порядок $$11$$? конечность группы? (Указание: не все из перечисленного можно записать, хотя пока у нас нет средств это установить.)

    Сигнатура теории множеств содержит два двуместных предикатных символа: для принадлежности и для равенства. Аксиомы теории множеств можно записывать в виде формул этой сигнатуры. Чаще всего рассматривают вариант аксиоматической теории множеств, называемый теорией Цермело-Френкеля и обозначаемый ZF. Приведем для примера одну из аксиом теории ZF, называемую аксиомой объемности, или экстенсиональности:$$\begin\forall x\,\forall y\,((\forall z\,((z\in x)\to(z\in y))\land \forall z\,((z\in y)\to(z\in x))) \to\\ {}\to(x=y)). \end$$

    42. Сформулировать словесно эту аксиому.

    43. Записать в виде формулы аксиому регулярности, или фундирования, которая говорит, что у всякого множества есть минимальный (с точки зрения отношения $$\in$$ ) элемент, то есть элемент, не пересекающийся с самим множеством.

    44. Какова естественная сигнатура для теории полей? Можно ли записать в виде формулы этой сигнатуры утверждение о том, что поле имеет характеристику $$2$$? конечную характеристику? алгебраически замкнуто?

    Определение истинности

    Из приведенных выше примеров, вероятно, понятен смысл формулы, то есть ясно, в каких интерпретациях данной сигнатуры и для каких элементов формула истинна. Тем не менее для любителей строгости мы приведем формальное определение истинности. (Его детали понадобятся, когда мы будем проверять истинность выводимых формул, см. раздел "Корректность исчисления предикатов"

    Прежде всего, определим формально понятие параметра формулы (переменной, от значения которой может зависеть истинность формулы). Согласно этому определению, скажем, формула $$\forall x\,\exists y\, A(x,y)$$ не имеет параметров, а формулы $$\exists y\, A(x,y)$$ и $$(A(x)\land \forall x\, B(x,x))$$ имеют единственный параметр $$x$$. Вот как выглядит это определение:

  • Параметрами терма являются все входящие в него индивидные переменные.
  • Параметрами атомарной формулы являются параметры всех входящих в нее термов.
  • Параметры формулы $$\lnot \varphi$$ те же, что у формулы $$\varphi$$.
  • Параметрами формул $$(\varphi\land\psi)$$, $$(\varphi\lor\psi)$$ и $$(\varphi\to\psi)$$ являются все параметры формулы $$\varphi$$, а также все параметры формулы $$\psi$$.
  • Параметрами формул $$\forall\xi\,\varphi$$ и $$\exists\xi\,\varphi$$ являются все параметры формулы $$\varphi$$, кроме переменной $$\xi$$.
    •

    Параметры иногда называют свободными переменными формулы. Заметим, что формула может иметь одновременно параметр $$x$$ и использовать (в другом месте) квантор $$\forall x$$. Как говорят в этом случае, одна и та же переменная имеет свободные и связанные вхождения. Свободное вхождение переменной — это такое вхождение, которое не входит в область действия одноименного квантора. Если аккуратно определить эту область действия, несложно проверить, что параметры формулы — это как раз переменные, имеющие свободные вхождения.

    Теперь мы хотим определить понятие формулы, истинной в данной интерпретации при данных значениях параметров. Технически проще считать, что всем индивидным переменным приписаны какие-то значения, а потом доказать, что переменные, не являющиеся параметрами, не влияют на истинность формулы.

    Итак, пусть фиксирована сигнатура и некоторая интерпретация этой сигнатуры. Оценкой назовем отображение, которое ставит в соответствие каждой индивидной переменной некоторый элемент множества, являющегося носителем интерпретации. Этот элемент будем называть значением переменной при данной оценке.

    Определим индуктивно значение терма $$t$$ при данной оценке $$\pi$$, которое мы будем обозначать $$[t](\pi)$$.

  • Для переменных оно уже определено.
  • Если $$t$$ является константой (нульместным функциональным символом), то $$[t](\pi)$$ не зависит от $$\pi$$ и равно значению этой константы при данной интерпретации (напомним, в интерпретации с каждой константой сопоставляется некоторый элемент носителя).
  • Если $$t$$ имеет вид $$f(t_1,\dots,t_m)$$, где $$f$$ — функциональный символ валентности $$m$$, а $$t_1,\dots,t_m$$ — термы, то $$[t](\pi)$$ есть $$[f]([t_1](\pi),\dots,[t_m](\pi))$$, где $$[f]$$ есть функция, соответствующая символу $$f$$ в нашей интерпретации, а $$[t_i](\pi)$$ есть значение терма $$t_i$$ при оценке $$\pi$$.
    •

    Теперь можно определить значение формулы $$\varphi$$ при данной оценке $$\pi$$ в данной интерпретации, которое обозначается $$[\varphi](\pi)$$ и может быть равно И или Л ; в первом случае формула называется истинной, во втором — ложной. Это определение также индуктивно:

  • Значение атомарной формулы $$A(t_1,\dots,t_m)$$ определяется как $$[A]([t_1](\pi),\dots,[t_m](\pi))$$, где $$[A]$$ — предикат, соответствующий предикатному символу $$A$$ в рассматриваемой интерпретации. Если формула представляет собой нульместный предикатный символ, то ее значение не зависит от оценки и есть значение этого символа.
  • $$[\lnot \varphi](\pi)$$ определяется как $$\lnot [\varphi(\pi)]$$, где $$\lnot$$ понимается как операция в $$\mathbb{B}$$. Другими словами, формула $$\lnot \varphi$$ истинна при оценке $$\pi$$ тогда и только тогда, когда формула $$\varphi$$ ложна при этой оценке.
  • $$[\varphi \land \psi](\pi)$$ определяется как $$[\varphi](\pi)\land [\psi](\pi)$$, где $$\land$$ в правой части понимается как операция в $$\mathbb{B}$$. (Другими словами, формула $$(\varphi\land\psi)$$ истинна при оценке $$\pi$$ тогда и только тогда, когда обе формулы $$\varphi$$ и $$\psi$$ истинны при этой оценке.) Аналогичным образом $$[\varphi \lor \psi](\pi)$$ определяется как $$[\varphi](\pi)\lor [\psi](\pi)$$, а $$[\varphi \to \psi](\pi)$$ — как $$[\varphi](\pi)\to [\psi](\pi)$$.
  • Формула $$\forall \xi\,\varphi$$ истинна на оценке $$\pi$$ тогда и только тогда, когда формула $$\varphi$$ истинна на любой оценке $$\pi'$$, которая совпадает с $$\pi$$ всюду, кроме значения переменной $$\xi$$ (которое в оценке $$\pi'$$ может быть любым). Другими словами, если обозначить через $$\pi+(\xi\mapsto m)$$ оценку, при которой значение переменной $$\xi$$ равно $$m$$, а остальные переменные принимают те же значения, что и в оценке $$\pi$$, то$$[\forall \xi\, \varphi](\pi)= \bigwedge_{m\in M} [\varphi](\pi+(\xi\mapsto m)).$$ (В правой части стоит бесконечная конъюнкция, которая истинна, если все ее члены истинны.)
  • Формула $$\exists \xi\,\varphi$$ истинна на оценке $$\pi$$ тогда и только тогда, когда формула $$\varphi$$ истинна на некоторой оценке $$\pi'$$, которая совпадает с $$\pi$$ всюду, кроме значения переменной $$\xi$$ (которое в оценке $$\pi'$$ может быть любым). Другими словами,$$[\forall \xi\, \varphi](\pi)= \bigvee_{m\in M} [\varphi](\pi+(\xi\mapsto m)).$$ (В правой части стоит бесконечная дизъюнкция, которая истинна, если хотя бы один из ее членов истинен.)
    •

    Заметим, что в двух последних пунктах значение переменной $$\xi$$ в оценке $$\pi$$ не играет роли. Это позволяет легко доказать (индукцией по построению формулы) такое утверждение: если две оценки $$\pi_1$$ и $$\pi_2$$ придают одинаковые значения всем параметрам формулы $$\varphi$$, то $$[\varphi](\pi_1)\hm= [\varphi](\pi_2)$$. Другими словами, истинность формулы определяется значениями ее параметров.

    45. Проведите это индуктивное рассуждение подробно.

    46. Приведенные выше определения применимы к любой формуле, в том числе и к странной формуле $$\forall y\, A(x)$$. Какие у нее параметры? При каких значениях параметров она истинна? (Ответ: она имеет единственный параметр $$x$$ и эквивалентна формуле $$A(x)$$.)

    47. В каком случае будет истинна формула $$\forall x\,\exists x\,A(x)$$? Тот же вопрос для формулы $$\exists x\,\forall x\, A(x)$$. (Ответ: первая из этих формул эквивалентна формуле $$\exists x\, A(x)$$, а вторая — формуле $$\forall x\, A(x)$$.)

    Формула называется замкнутой, если она не имеет параметров. Замкнутые формулы называют также суждениями. Как мы доказали, истинность замкнутой формулы определяется выбором интерпретации (и не зависит от значений переменных).

    Выразимые предикаты

    Пусть фиксирована некоторая сигнатура $$\sigma$$ и ее интерпретация с носителем $$M$$. Мы хотим определить понятие выразимого (с помощью формулы данной сигнатуры в данной интерпретации) $$k$$ -местного предиката.

    Выберем $$k$$ переменных $$x_1,\dots, x_k$$. Рассмотрим произвольную формулу $$\varphi$$, все параметры которой содержатся в списке $$x_1,\dots,x_k$$. Истинность этой формулы зависит только от значений переменных $$x_1,\dots,x_k$$. Тем самым возникает отображение $$M^k\to\mathbb{B}=\{И, Л\}$$, то есть некоторый $$k$$ - местный предикат на $$M$$. Говорят, что этот предикат выражается формулой $$\varphi$$. Все предикаты, которые можно получить таким способом, называются выразимыми. (Ясно, что конкретный выбор списка переменных роли не играет.) Соответствующие им подмножества множества $$M^k$$ (области истинности выразимых предикатов) также называют выразимыми.

    48. Докажите, что пересечение, объединение и разность двух выразимых множеств являются выразимыми. Докажите, что проекция $$k$$ - мерного выразимого множества вдоль одной из "осей координат" является $$(k-1)$$ -мерным выразимым множеством.

    Пример. Сигнатура содержит одноместный функциональный символ $$S$$ и двуместный предикатный символ равенства ( $$=$$ ). Рассмотрим интерпретацию этой сигнатуры. В качестве носителя выберем натуральный ряд $$\mathbb{N}$$. Символ $$S$$ будет обозначать функцию прибавления единицы (можно считать $$S$$ сокращением от слова successor — последователь). Знак равенства интерпретируется как совпадение элементов.

    Легко проверить, что одноместный предикат "быть нулем" выразим в этой интерпретации, несмотря на то, что константы для нуля в сигнатуре не предусмотрено. В самом деле, он выражается формулой$$\lnot\exists y (x=S(y))$$ с единственным параметром $$x$$.

    Еще проще выразить в этой сигнатуре двуместный предикат "быть больше на $$2$$ ", при этом даже не нужны кванторы: $$y=S(S(x))$$.

    Любопытно, что уже в такой простой ситуации можно сформулировать содержательную задачу: выразить предикат $$y=x+N$$, где $$N$$ — большое число (скажем, миллиард), с помощью существенно более короткой формулы, чем $$y=S(S(\dots(S(x))\dots))$$. Как ни удивительно, это вполне возможно, и соответствующую формулу вполне можно уместить на листе бумаги.

    49. Докажите, что предикат $$y=x+N$$ можно выразить формулой указанной сигнатуры, длина которой есть $$O(\log N)$$. (Указание. Если мы научились выражать $$y=x+n$$, можно выразить $$y=x+2n$$ с помощью формулы$$\exists z\, ((z=x+n)\land(y=z+n))$$ (в которой через $$z=x+n$$ и $$y=z+n$$ обозначены соответствующие формулы). Это само по себе ничего не дает, так как длина формулы увеличилась вдвое, но можно использовать такой трюк:$$\exists z\, \forall u\,\forall v (((u=x\land v=z)\lor(u=z\land v=y))\to(v=u+n)).$$ Далее можно воспользоваться записью числа $$N$$ в двоичной системе счисления.)

    Можно доказать, что в этой сигнатуре кванторы почти не увеличивают набор выразимых предикатов: всякий выразимый предикат будет выражаться бескванторной формулой (возможно, гораздо более длинной), если добавить к сигнатуре константу $$0$$. Мы вернемся к этому вопросу в разделе "Элиминация кванторов".

    Чтобы привыкнуть к понятию выразимости, рассмотрим еще один пример. Пусть сигнатура содержит предикат равенства и трехместный предикат $$C$$. Рассмотрим интерпретацию, в которой носителем является множество точек плоскости, равенство интерпретируется как совпадение точек, а $$C(x,y,z)$$ означает, что точки $$x$$ и $$y$$ равноудалены от точки $$z$$. Оказывается, что этого предиката достаточно, чтобы выразить более или менее все традиционные понятия элементарной геометрии.

    Как, например, записать, что три различные точки $$A,B,C$$ лежат на одной прямой? Вот как: "не существует другой точки $$C'$$, которая находилась бы на тех же расстояниях от $$A$$ и $$B$$, что и точка $$C$$ ".

    50. Напишите соответствующую формулу указанной сигнатуры.

    Теперь легко выразить такое свойство четырех точек $$A,B,C,D$$: "точки $$A$$ и $$B$$ различны, точки $$C$$ и $$D$$ различны и прямые $$AB$$ и $$CD$$ параллельны". В самом деле, надо написать, что нет точки, которая бы одновременно лежала на одной прямой с $$A$$ и $$B$$, а также на одной прямой с $$C$$ и $$D$$.

    После этого можно выразить свойство четырех точек "быть вершинами параллелограмма". Это позволяет переносить отрезок параллельно себе. После этого несложно выразить такое свойство: "расстояние $$AB$$ равно расстоянию $$CD$$ ".

    51. Запишите соответствующую формулу.

    Аналогичным образом можно двигаться и дальше.

    52. Выразите свойство $$|OA|\le |OB|$$ трех точек $$O$$, $$A$$, $$B$$. (Указание. Напишите, что все прямые, проходящие через $$A$$, пересекаются с окружностью радиуса $$OB$$ с центром в $$O$$.)

    53. Запишите в виде формулы: (а) равенство треугольников; (б) равенство углов; (в) свойство угла быть прямым.

    54. Рассмотрим естественную интерпретацию сигнатуры $$({=},{<})$$ на множестве целых чисел. Как выразить предикат $$y=x+1$$?

    55. Рассмотрим множество действительных чисел как интерпретацию сигнатуры $$({=},{+}, {y=x^2})$$. Как выразить трехместный предикат $$xy=z$$?

    56. Рассмотрим множество целых положительных чисел как интерпретацию сигнатуры, содержащей равенство и двуместный предикат " $$x$$ делит $$y$$ ". Выразите свойства "равняться единице" и "быть простым числом".

    57. Рассмотрим плоскость как интерпретацию сигнатуры, содержащей предикат равенства (совпадение точек) и двуместный предикат "находиться на расстоянии $$1$$ ". Выразите двуместные предикаты "находиться на расстоянии $$2$$ " и "находиться на расстоянии не более $$2$$ ". Выразите двуместный предикат "находиться на расстоянии $$1/2$$.

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^