Свободные переменные и связанные переменные

Понятие в математике или информатике

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

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

Экземпляр символа переменной связан , напротив, если значение этого символа переменной было связано с определенным значением или диапазоном значений в области дискурса или вселенной . Это может быть достигнуто с помощью логических квантификаторов, операторов связывания переменных или явного указания допустимых значений для переменной (например, "...где - положительное целое число".) Символ переменной в целом связан , если связано хотя бы одно его вхождение. ^{[1] стр. 142--143} Поскольку один и тот же символ переменной может появляться в нескольких местах выражения, некоторые вхождения символа переменной могут быть свободными, а другие - связанными, ^{[1] стр. 78} , следовательно, "свободный" и "связанный" сначала определяются для вхождений, а затем обобщаются на все вхождения указанного символа переменной в выражении. Как бы это ни было сделано, переменная перестает быть независимой переменной, от которой зависит значение выражения, будь то значение истинности или числовой результат вычисления или, в более общем смысле, элемент множества изображений функции. ${\displaystyle n}$

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

${\displaystyle \forall y\,\exists x\,\left(x={\sqrt {y}}\right).}$

Это выражение оценивается как ложное, если областью значений и являются действительные числа, и как истинное , если областью значений являются комплексные числа. ${\displaystyle x}$ ${\displaystyle y}$

Термин «фиктивная переменная» также иногда используется для связанной переменной (чаще в общей математике, чем в информатике), но его не следует путать с идентично названной, но не связанной концепцией фиктивной переменной , используемой в статистике, чаще всего в регрессионном анализе. ^{[2] стр. 17}

Примеры

Прежде чем дать точное определение свободной переменной и связанной переменной, приведем несколько примеров, которые, возможно, сделают эти два понятия более понятными, чем само определение:

В выражении

${\displaystyle \sum _{k=1}^{10}f(k,n),}$

n — свободная переменная, а k — связанная переменная; следовательно, значение этого выражения зависит от значения n , но нет ничего с именем k , от чего оно могло бы зависеть.

В выражении

${\displaystyle \int _{0}^{\infty }x^{y-1}e^{-x}\,dx,}$

y — свободная переменная, а x — связанная переменная; следовательно, значение этого выражения зависит от значения y , но нет ничего с именем x , от чего оно могло бы зависеть.

В выражении

${\displaystyle \lim _{h\rightarrow 0}{\frac {f(x+h)-f(x)}{h}},}$

x — свободная переменная, а h — связанная переменная; следовательно, значение этого выражения зависит от значения x , но нет ничего с именем h , от чего оно могло бы зависеть.

В выражении

${\displaystyle \forall x\ \exists y\ {\Big [}\varphi (x,y,z){\Big ]},}$

z — свободная переменная, а x и y — связанные переменные, связанные с логическими квантификаторами ; следовательно, логическое значение этого выражения зависит от значения z , но нет ничего, называемого x или y, от чего оно могло бы зависеть.

Более широко, в большинстве доказательств, используются связанные переменные. Например, следующее доказательство показывает, что все квадраты положительных четных целых чисел делятся на ${\displaystyle 4}$

Пусть будет положительным четным целым числом. Тогда существует целое число такое, что . Так как , то делится на ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n=2k}$ ${\displaystyle n^{2}=4k^{2}}$ ${\displaystyle n^{2}}$ ${\displaystyle 4}$

В доказательстве в качестве связанных переменных в целом использовались не только k , но и n .

Операторы привязки переменных

Следующее

${\displaystyle \sum _{x\in S}\quad \quad \prod _{x\in S}\quad \quad \int _{0}^{\infty }\cdots \,dx\quad \quad \lim _{x\to 0}\quad \quad \forall x\quad \quad \exists x}$

некоторые общие операторы связывания переменных . Каждый из них связывает переменную x для некоторого множества S.

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

${\displaystyle \sum _{1,\ldots ,10}\left(k\mapsto f(k,n)\right)}$

для сумм или

${\displaystyle D\left(x\mapsto x^{2}+2x+1\right)}$

для дифференциации.

Формальное объяснение

Дерево, обобщающее синтаксис выражения ${\displaystyle \forall x\,((\exists y\,A(x))\vee B(z))}$

Механизмы связывания переменных встречаются в разных контекстах в математике, логике и информатике. Однако во всех случаях они являются чисто синтаксическими свойствами выражений и переменных в них. Для этого раздела мы можем обобщить синтаксис, отождествив выражение с деревом , конечные узлы которого являются переменными, константами, константами функций или константами предикатов, а неконечные узлы являются логическими операторами. Затем это выражение можно определить, выполнив симметричный обход дерева. Операторы связывания переменных — это логические операторы , которые встречаются почти в каждом формальном языке. Оператор связывания Q принимает два аргумента: переменную v и выражение P , и при применении к его аргументам создает новое выражение Q( v , P ). Значение операторов связывания предоставляется семантикой языка и здесь нас не касается.

Связывание переменных связывает три вещи: переменную v , местоположение a для этой переменной в выражении и неконечный узел n формы Q( v , P ). Примечание: мы определяем местоположение в выражении как конечный узел в синтаксическом дереве. Связывание переменных происходит, когда это местоположение находится ниже узла n .

В лямбда-исчислении , xявляется связанной переменной в термине M = λx. Tи свободной переменной в термине T. Мы говорим, xчто является связанной в Mи свободной в T. Если Tсодержит подтерм, λx. Uто xявляется отскоком в этом термине. Говорят, что эта вложенная внутренняя привязка x"тенит" внешнюю привязку. Вхождения xв Uявляются свободными вхождениями нового x. ^[3]

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

Закрытый терм — это терм, не содержащий свободных переменных.

Функциональные выражения

Чтобы привести пример из математики, рассмотрим выражение, которое определяет функцию

${\displaystyle f=\left[(x_{1},\ldots ,x_{n})\mapsto t\right]}$

где t — выражение. t может содержать некоторые, все или ни одного из x ₁ , …, x _n и может содержать другие переменные. В этом случае мы говорим, что определение функции связывает переменные x ₁ , …, x _n .

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

${\displaystyle \sum _{x\in S}{x^{2}}}$

можно рассматривать как обозначение для

${\displaystyle \sum _{S}{(x\mapsto x^{2})}}$

где — оператор с двумя параметрами — однопараметрической функцией и множеством для оценки этой функции. Другие перечисленные выше операторы могут быть выражены аналогичным образом; например, квантификатор всеобщности можно рассматривать как оператор, который вычисляет логическую конъюнкцию булевой функции P , примененной к (возможно бесконечному) множеству S. ${\displaystyle \sum _{S}{f}}$ ${\displaystyle \forall x\in S\ P(x)}$

Естественный язык

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

Лиза нашла свою книгу.

В предложении выше притяжательное местоимение her является свободной переменной. Оно может относиться к ранее упомянутой Лизе или к любой другой женщине. Другими словами, her book может относиться к книге Лизы (пример кореференции ) или к книге, которая принадлежит другой женщине (например, Jane's book). Кто бы ни был референтом her , его можно установить в соответствии с ситуативным (т. е. прагматическим ) контекстом. Идентичность референта может быть показана с помощью коиндексных нижних индексов, где i указывает на одного референта, а j указывает на второго референта (отличного от i ). Таким образом, предложение Lisa found her book имеет следующие интерпретации:

Лиза _{, я} нашла ее _книгу . (интерпретация №1: ее = Лизы )

Лиза _{, я} нашла ее книгу _{на букву J.} (интерпретация №2: ее = женщины, которая не является Лизой)

Это различие представляет не только академический интерес, поскольку в некоторых языках на самом деле существуют разные формы her _i и her _j : например, в норвежском и шведском языках кореферентный her _i переводится как sin , а некореферентный her _{j —} как hennes .

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

Лиза, _я нашла ее _{собственную} книгу. (интерпретация №1: ее = Лизы )

* Лиза, _я нашла ее _{собственную} книгу. (интерпретация №2: она = женщины, которая не является Лизой)

Однако возвратные местоимения , такие как yourself , yourself , yourself и т. д., и взаимные местоимения , такие как each other , действуют как связанные переменные. В предложении, подобном следующему:

Джейн поранилась .

возвратная сама может ссылаться только на ранее упомянутый антецедент , в данном случае Джейн , и никогда не может ссылаться на другую женскую персону. В этом примере переменная сама связана с существительным Джейн , которое находится в позиции субъекта . Указывая на коиндексацию, первая интерпретация с коиндексацией Джейн и сама является допустимой, но другая интерпретация, где они не коиндексированы, является неграмматической :

Джейн, _{я причинила себе} боль . (интерпретация №1: сама = Джейн )

* Джейн, _я причинила себе боль _j . (интерпретация №2: сама = женщина, которая не является Джейн)

Связывание кореферентности может быть представлено с помощью лямбда-выражения , как упоминалось в предыдущем разделе Формальное объяснение. Предложение с возвратным падежом может быть представлено как

(λ x . x больно x )Джейн

в котором Jane — это аргумент референта субъекта, а λx.x hurt x — это функция предиката (абстракция лямбда) с нотацией лямбда и x, указывающей как семантический субъект, так и семантический объект предложения как связанные. Это возвращает семантическую интерпретацию JANE hurt JANE , где JANE — это одно и то же лицо.

Местоимения также могут вести себя по-разному. В предложении ниже

Эшли ударил ее .

местоимение her может относиться только к женщине, которая не является Ashley. Это означает, что оно никогда не может иметь возвратного значения, эквивалентного Ashley hit yourself . Грамматические и неграмматические интерпретации следующие:

* Эшли, _я ударил ее _. ( интерпретация №1: она = Эшли )

Эшли, _я ударил ее _j . (интерпретация №2: она = женщина, которая не является Эшли)

Первая интерпретация невозможна. Грамматикой допускается только вторая интерпретация.

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

Смотрите также

• Закрытие (компьютерные науки)
• Комбинаторная логика
• Лямбда-подъем
• Имя привязки
• Область применения (программирование)
• Область действия (логика)

Ссылки

1. WVO Quine, Математическая логика (1981). Издательство Гарвардского университета, 0-674-55451-5.
2. Роберт С. Вольф, Путешествие по математической логике (2005). 978-0-88385-036-7
3. Томпсон 1991, стр. 33.

• Томпсон, Саймон (1991). Теория типов и функциональное программирование . Уокингем, Англия: Addison-Wesley. ISBN 0201416670. OCLC  23287456.
• Вольф, Роберт С. (2005). Путешествие по математической логике . Том 30. Математическая ассоциация Америки. ISBN 978-0-88385-042-8. JSTOR  10.4169/j.ctt5hh94h.

Дальнейшее чтение

• Gowers, Timothy ; Barrow-Green, June ; Leader, Imre , ред. (2008). The Princeton Companion to Mathematics . Princeton, New Jersey : Princeton University Press . стр. 15–16. doi :10.1515/9781400830398. ISBN 978-0-691-11880-2. JSTOR  j.ctt7sd01. LCCN  2008020450. МР  2467561. OCLC  227205932. ОЛ  19327100М. Збл  1242.00016.