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

Для проверки этой статьи нужны дополнительные цитаты . Помогите улучшить эту статью , добавив ссылки на надежные источники . Неподтвержденный материал может быть оспорен и удален. Найти источники:  «Свободные переменные и связанные переменные» – новости  · газеты  · книги  · ученый  · JSTOR ( декабрь 2008 г. ) ( Узнайте, как и когда удалять это сообщение )

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

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

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

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

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

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

Термин «фиктивная переменная» также иногда используется для связанной переменной (чаще в общей математике, чем в информатике), но его не следует путать с идентично названной, но не связанной концепцией фиктивной переменной , используемой в статистике, чаще всего в регрессионном анализе. ^{[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 к}$${\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)}$

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

Механизмы связывания переменных встречаются в разных контекстах в математике, логике и информатике. Однако во всех случаях они являются чисто синтаксическими свойствами выражений и переменных в них. Для этого раздела мы можем обобщить синтаксис, отождествив выражение с деревом , конечные узлы которого являются переменными, константами, константами функций или константами предикатов, а неконечные узлы являются логическими операторами. Затем это выражение можно определить, выполнив симметричный обход дерева. Операторы связывания переменных — это логические операторы , которые встречаются почти в каждом формальном языке. Оператор связывания 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)}$

This section has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (March 2023) (Learn how and when to remove this message) This section needs expansion. You can help by adding to it. (December 2008) (Learn how and when to remove this message)

При анализе в формальной семантике можно увидеть, что естественные языки имеют свободные и связанные переменные. В английском языке личные местоимения, такие как 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: она = женщина, которая не является Эшли)

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

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

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

• Томпсон, Саймон (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.