Термин (логика)

редактировать

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

A терм первого порядка - это рекурсивно построенный из постоянных символов, переменных и функциональных символов. Выражение, сформированное путем применения символа предиката к соответствующему количеству терминов, называется атомарной формулой , которая принимает значение истина или ложь. в бивалентной логике, учитывая интерпретацию. Например, (x + 1) ∗ (x + 1) {\ displaystyle (x + 1) * (x + 1)}{\ displaystyle (x + 1) * (x + 1)} - это член, построенный из константы 1, переменной x и двоичные функциональные символы + {\ displaystyle +}+и ∗ {\ displaystyle *}* ; это часть атомарной формулы (x + 1) ∗ (x + 1) ≥ 0 {\ displaystyle (x + 1) * (x + 1) \ geq 0}{\ displaystyle (x + 1) * (x + 1) \ geq 0} , которая оценивается как истина для каждого вещественного значения x.

Помимо логики, термины играют важную роль в универсальной алгебре и системах переписывания.

Содержание
  • 1 Формальное определение
    • 1.1 Структура терминов и представление
    • 1.2 Структурное равенство
    • 1.3 Основные и линейные термины
    • 1.4 Построение формул из терминов
  • 2 Операции с терминами
  • 3 Понятия, связанные с данным
    • 3.1 Сортированные термины
    • 3.2 Лямбда-термины
      • 3.2.1 Мотивация
  • 4 См. Также
  • 5 Примечания
  • 6 Ссылки
Формальное определение
Древовидная структура терминов (n⋅ (n + 1)) / 2 и n ⋅ ((n + 1) / 2)

Для данного набора V переменных символов, набора C постоянных символов и набора F n n-арных функциональных символов, также называемых символами операторов, для для каждого натурального числа n ≥ 1 набор (неотсортированных) термов первого порядка T рекурсивно определен как наименьший набор со следующими свойствами:

  • каждый переменный символ является термом: V ⊆ T,
  • каждый постоянный символ представляет собой терм: C ⊆ T,
  • из каждых n членов t 1,..., t n, и каждая н-арная функция по символу f ∈ F n можно построить больший член f (t 1,..., t n).

Используя интуитивно понятный, псевдо- грамматическая нотация, иногда это записывается как: t :: = x | c | f (t 1,..., t n). Обычно заселяются только первые несколько наборов функциональных символов F n. Хорошо известными примерами являются унарные функциональные символы sin, cos ∈ F 1 и двоичные функциональные символы +, -, ⋅, / ∈ F 2, а троичные операции менее известны, не говоря уже о функциях более высокой степени арности. Многие авторы рассматривают постоянные символы как 0-арные функциональные символы F 0, поэтому для них не требуется специального синтаксического класса.

Термин обозначает математический объект из области дискурса. Константа c обозначает именованный объект из этого домена, переменная x охватывает объекты в этом домене, а n-арная функция f отображает n- кортежей объектов в объекты. Например, если n ∈ V - переменный символ, 1 ∈ C - постоянный символ, а add ∈ F 2 - двоичный функциональный символ, то n ∈ T, 1 ∈ T, и (следовательно) add (n, 1) ∈ T по первому, второму и третьему правилу построения членов соответственно. Последний термин обычно записывается как n + 1 с использованием инфиксной записи и более распространенного символа оператора + для удобства.

Структура термина и представление

Первоначально логики определяли термин как строку символов, придерживающуюся определенных строительных правил. Однако, поскольку концепция дерева стала популярной в компьютерных науках, оказалось, что удобнее рассматривать термин как дерево. Например, несколько отдельных строк символов, например «(n⋅ (n + 1)) / 2», «((n⋅ (n + 1))) / 2» и «n (n + 1) 2 {\ displaystyle {\ frac {n (n + 1)} {2}}}{\ frac {n (n + 1)} {2}} ", обозначают тот же термин и соответствуют одному и тому же дереву, а именно. левое дерево на картинке выше. Отделив древовидную структуру термина от его графического представления на бумаге, также легко учесть скобки (являющиеся только представлением, а не структурой) и невидимые операторы умножения (существующие только в структуре, а не в представлении).

Структурное равенство

Два термина считаются структурно, буквально или синтаксически равными, если они соответствуют такое же дерево. Например, левое и правое дерево на приведенном выше рисунке являются структурно и равными элементами, хотя их можно считать «семантически равными », поскольку они всегда оценивают одно и то же значение в рациональная арифметика. В то время как структурное равенство можно проверить без каких-либо знаний о значении символов, семантическое равенство - нет. Если функция /, например, интерпретируется не как рациональное, а как усекающее целое число деление, то при n = 2 левый и правый член оценивается как 3 и 2, соответственно. Структурно одинаковые термины должны согласовываться в именах переменных.

Напротив, термин t называется переименованием или вариантом терма u, если последний возник в результате последовательного переименования всех переменных первого, т.е. если u = tσ для некоторой подстановки переименования σ. В этом случае u также является переименованием t, поскольку подстановка переименования σ имеет обратный σ и t = uσ. Оба члена также называются равными по модулю переименования . Во многих контекстах конкретные имена переменных в термине не имеют значения, например аксиома коммутативности для сложения может быть сформулирована как x + y = y + x или как a + b = b + a; в таких случаях можно переименовать всю формулу, в то время как произвольный подтермин обычно не может, например x + y = b + a не является допустимой версией аксиомы коммутативности.

Основные и линейные члены

Набор переменных терма t обозначается vars (t). Термин, не содержащий переменных, называется основным термином ; термин, который не содержит нескольких экземпляров переменной, называется линейным термином . Например, 2 + 2 - основной член и, следовательно, также линейный член, x⋅ (n + 1) - линейный член, n⋅ (n + 1) - нелинейный член. Эти свойства важны, например, при перезаписи термов.

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

, сокращая количество констант как f 0, а количество i-арных функциональных символов как f i, число θ h отдельных основных членов высотой до h можно вычислить по следующей формуле рекурсии:

  • θ0= f 0, поскольку основной член высоты 0 может быть только константой,
  • θ h + 1 = ∑ i = 0 ∞ fi ⋅ θ hi {\ displaystyle \ theta _ {h + 1} = \ sum _ {i = 0} ^ {\ infty} f_ {i} \ cdot \ theta _ {h} ^ {i}}\ theta _ {h +1} = \ sum _ {i = 0} ^ {\ infty} f_ {i} \ cdot \ theta _ {h} ^ {i} , поскольку основной член высотой до h + 1 можно получить, составив любые i обозначают члены высотой до h, используя символ i-арной корневой функции. Сумма имеет конечное значение, если имеется только конечное число констант и функциональных символов, что обычно и имеет место.

Построение формул из членов

Для данного набора R n из n-арные символы отношения для каждого натурального числа n ≥ 1 атомарная формула (неотсортированная первого порядка) получается путем применения n-арного символа отношения к n терминам. Что касается функциональных символов, набор символов отношения R n обычно непустой только для малых n. В математической логике более сложные формулы строятся из элементарных формул с использованием логических связок и кванторов. Например, если обозначить ℝ набор действительных чисел, ∀x: x ∈ ℝ ⇒ (x + 1) ⋅ (x + 1) ≥ 0 - это математическая формула, истинная в алгебре комплексные числа. Атомарная формула называется основной, если она полностью построена на основных терминах; все основные атомарные формулы, составленные из заданного набора символов функций и предикатов, составляют базу Хербрана для этих наборов символов.

Операции с терминами
Древовидная структура черного примера термина a ∗ ((a + 1) ∗ (a + 2)) 1 ∗ (2 ∗ 3) {\ displaystyle {\ frac { a * ((a + 1) * (a + 2))} {1 * (2 * 3)}}}{\ frac { a * ((a + 1) * (a + 2))} {1 * (2 * 3)}} , с синим редексом x ∗ (y ∗ z) {\ displaystyle x * (y * z)}x * (y * z)
  • Поскольку термин имеет структуру древовидной иерархии, каждому из его узлов может быть назначена позиция или путь, что есть строка натуральных чисел, указывающая место узла в иерархии. Пустая строка, обычно обозначаемая ε, назначается корневому узлу. Строки позиции внутри черного члена обозначены на рисунке красным.
  • В каждой позиции p термина t начинается уникальный подтерм, который обычно обозначается t | р. Например, в позиции 122 черного термина на картинке субтерм a + 2 имеет корень. Отношение «является подтермом из» является частичным порядком на множестве терминов; он рефлексивен, поскольку каждый термин является тривиальным подтермом самого себя.
  • Термин, полученный заменой в термине t подтерм в позиции p новым термином u обычно обозначается t [u] p. Термин t [u] p также можно рассматривать как результат обобщенного конкатенации термина u с термоподобным объектом t [.]; последний называется контекстом или термином с пробелом (обозначенным "."; его положение - p), в котором u называется вложенным . Например, если t - черный член на картинке, то t [b + 1] 12 дает член a ∗ (b + 1) 1 ∗ (2 ∗ 3) {\ displaystyle {\ frac {a * (b + 1)} {1 * (2 * 3)}}}{\ frac {a * (b + 1)} {1 * (2 * 3)}} . Последний термин также является результатом встраивания члена b + 1 в контекст a ∗ (.) 1 ∗ (2 ∗ 3) {\ displaystyle {\ frac {a * (\;. \;)} {1 * (2 * 3)}}}{\ frac {a * (\;. \;)} {1 * (2 * 3)}} . В неформальном смысле операции создания экземпляра и встраивания обратны друг другу: в то время как первые добавляют функциональные символы в нижней части термина, последний добавляет их вверху. Порядок охвата связывает термин и любой результат добавлений с обеих сторон.
  • К каждому узлу термина его глубина (называемая высота некоторыми авторами) может быть задано, т.е. расстояние (количество ребер) от корня. В этой настройке глубина узла всегда равна длине его строки позиции. На рисунке уровни глубины в черном элементе обозначены зеленым.
  • размер термина обычно относится к количеству его узлов или, что эквивалентно, к длине письменное представление термина, считая символы без скобок. Черный и синий члены на картинке имеют размер 15 и 5.
  • Термин u соответствует члену t, если экземпляр подстановки u структурно равен подтерму t, или формально, если uσ = t | p для некоторой позиции p в t и некоторой подстановки σ. В этом случае u, t и σ называются термином шаблона, предметным термином и совпадающей заменой соответственно. На рисунке термин синего шаблона x ∗ (y ∗ z) {\ displaystyle x * (y * z)}x * (y * z) совпадает с термином черного субъекта в позиции 1 с соответствующей заменой {x ↦ a, y ↦ a + 1, z ↦ a + 2}, обозначенные синими переменными, сразу оставленные их черным заменителям. Интуитивно понятно, что образец, за исключением его переменных, должен содержаться в теме; если переменная встречается в шаблоне несколько раз, в соответствующих позициях предмета требуются одинаковые подтермы.
  • объединяющие термины
  • перезапись терминов
Понятия, связанные с данной

Сортированные термины

Когда область дискурса содержит элементы принципиально разного типа, полезно соответственно разделить набор всех терминов. С этой целью каждой переменной и каждому константному символу присваивается sort (иногда также называемый type ), а каждому функциональному символу присваивается объявление сортировки по домену и сортировки по диапазону. отсортированный термин f (t 1,..., t n) может быть составлен из отсортированных субтермов t 1,..., t n, только если сортировка i-го подтермина соответствует объявленному i-му сорту домена f. Такой термин также называется хорошо отсортированный ; любой другой термин (т. е. подчиняющийся несортированным правилам) называется плохо отсортированным .

. Например, векторное пространство имеет связанное с ним поле скалярных чисел. Пусть W и N обозначают сорт векторов и чисел, соответственно, пусть V W и V N - набор векторных и числовых переменных, соответственно, и C W и C N набор векторных и числовых констант соответственно. Тогда, например, 0 → ∈ CW {\ displaystyle {\ vec {0}} \ in C_ {W}}{\ vec {0}} \ in C_ {W} и 0 ∈ C N, а также сложение векторов, скалярное умножение, а внутренний продукт декларируется как +: W × W → W, ∗: W × N → W {\ displaystyle +: W \ times W \ to W, *: W \ times N \ to W}+: W \ times W \ to W, *: W \ times N \ to W и ⟨.,. ⟩: W × W → N {\ displaystyle \ langle.,. \ Rangle: W \ times W \ to N}\ langle.,. \ Rangle: W \ раз от W \ до N соответственно. Предполагая символы переменных v →, w → ∈ VW {\ displaystyle {\ vec {v}}, {\ vec {w}} \ in V_ {W}}{\ vec {v}}, {\ vec {w}} \ in V_ {W} и a, b ∈ V N, термин ⟨(v → + 0 →) ∗ a, w → ∗ b⟩ {\ displaystyle \ langle ({\ vec {v}} + {\ vec {0}}) * a, {\ vec {w}} * b \ rangle}\ langle ({\ vec {v}} + {\ vec {0}}) * a, {\ vec {w}} * b \ rangle хорошо отсортировано, а v → + a {\ displaystyle {\ vec {v}} + a}{\ vec {v}} + a не является (поскольку + не принимает термин типа N в качестве второго аргумента). Чтобы сделать a ∗ v → {\ displaystyle a * {\ vec {v}}}a * {\ vec {v}} хорошо отсортированным термином, необходимо дополнительное объявление ∗: N × W → W { \ displaystyle *: N \ times W \ to W}*: N \ times W \ to W является обязательным. Функциональные символы, имеющие несколько объявлений, называются перегруженными .

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

Лямбда-члены

Термины со связанными переменными
Обозначение. примерСвязанные. переменныеСвободные. переменныеЗаписывается как. лямбда-член
limn → ∞ x / nnxпредел (λn. Div (x, n))
∑ i = 1 ni 2 {\ displaystyle \ sum _ {i = 1} ^ {n} я ^ {2}}\ sum _ {i = 1} ^ {n} i ^ {2} inсумма (1, n, λi. Степень (i, 2))
∫ ab sin ⁡ (k ⋅ t) dt {\ displaystyle \ int _ { a} ^ {b} \ sin (k \ cdot t) dt}\ int _ {a} ^ {b} \ sin (k \ cdot t) dt ta, b, kинтеграл (a, b, λt. sin (k⋅t))

Мотивация

Математические обозначения, показанные в таблице, не вписываются в схему члена первого порядка, как определено выше, поскольку все они вводят собственный локальный или bound, переменная, которая не может появляться за пределами области нотации, например t ⋅ ∫ ab sin ⁡ (к ⋅ t) dt {\ displaystyle t \ cdot \ int _ {a} ^ {b} \ sin (k \ cdot t) \; dt}t \ cdot \ int _ {a} ^ {b} \ sin (k \ cdot t) \; dt не не имеет смысла. Напротив, другие переменные, называемые free, ведут себя как обычные термальные переменные первого порядка, например к ⋅ ∫ ab sin ⁡ (k ⋅ t) dt {\ displaystyle k \ cdot \ int _ {a} ^ {b} \ sin (k \ cdot t) \; dt}k \ cdot \ int _ {a} ^ {b} \ sin (k \ cdot t) \; dt делает имеет смысл.

Все эти операторы можно рассматривать как принимающие функцию, а не член значения в качестве одного из своих аргументов. Например, оператор lim применяется к последовательности, то есть к отображению положительного целого числа на, например, вещественные числа. В качестве другого примера, функция C для реализации второго примера из таблицы, ∑, будет иметь аргумент указателя функции (см. Рамку ниже).

Лямбда-термины могут использоваться для обозначения анонимных функций, которые должны быть предоставлены в качестве аргументов для lim, ∑, ∫ и т. Д.

Например, функция square из приведенной ниже программы на языке C может быть анонимно записана как лямбда-член λi. я. Затем общий оператор суммы ∑ можно рассматривать как троичный функциональный символ, принимающий значение нижней границы, значение верхней границы и функцию, которая должна быть суммирована. Из-за последнего аргумента оператор ∑ называется символом функции второго порядка . Другой пример - лямбда-член λn. x / n обозначает функцию, которая отображает 1, 2, 3,... в x / 1, x / 2, x / 3,..., соответственно, то есть обозначает последовательность ( х / 1, х / 2, х / 3,...). Оператор lim берет такую ​​последовательность и возвращает ее предел (если он определен).

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

int sum (int lwb, int upb, int fct (int)) {// реализует общий оператор суммы int res = 0; for (int i = lwb; i <=upb; ++i) res += fct(i); return res; } int square(int i) { return i*i; } // implements anonymous function (lambda i. i*i); however, C requires a name for it #include int main (void) {int n; scanf ("% d", n); printf ("% d \ n", sum (1, n, square)); / / применяет оператор суммы для суммирования квадратов return 0;}
См. также
Примечания
Ссылки
Последняя правка сделана 2021-06-10 14:01:45
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте