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

Информацию о связанных переменных в компьютерном программировании см. в разделе «Привязка имен» .

О свободных переменных в системах линейных уравнений см. Свободные переменные (система линейных уравнений) .

«Свободная переменная» перенаправляется сюда. Не путать со свободным параметром или фиктивной переменной (статистикой) .

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

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

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

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

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

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

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

Примеры

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

В выражении

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

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

В выражении

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

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

В выражении

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

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

В выражении

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

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

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

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

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

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

Следующее

$\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. Каждый из них

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

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

на суммы или

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

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

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

Дерево, обобщающее синтаксис выражения $\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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Однако возвратные местоимения , такие как «сам» , «сама» , «сам» и т. д., а также взаимные местоимения , такие как друг друга , действуют как связанные переменные. В таком предложении:

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

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

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

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

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

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

в котором Джейн является аргументом-референтом субъекта, а λx.x больно x — предикатная функция (лямбда-абстракция) с лямбда-нотацией, а x указывает как семантический субъект, так и семантический объект предложения как связанные. Это возвращает семантическую интерпретацию: ДЖЕЙН причинила боль ДЖЕЙН, причем ДЖЕЙН является одним и тем же человеком.

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

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

Местоимение «ее» может относиться только к женщине, не являющейся Эшли. Это означает, что это никогда не может иметь рефлексивного значения, эквивалентного удару Эшли себя . Грамматические и грамматические интерпретации:

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

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

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

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

См. также

• Замыкание (информатика)
• Комбинаторная логика
• Лямбда лифтинг
• Привязка имени
• Область применения (программирование)
• Область применения (логика)

Ссылки

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

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

• Гауэрс, Тимоти ; Барроу-Грин, июнь ; Лидер, Имре , ред. (2008). Принстонский спутник математики . Принстон, Нью-Джерси : Издательство Принстонского университета . стр. 15–16. дои : 10.1515/9781400830398 . ISBN  978-0-691-11880-2 . JSTOR   j.ctt7sd01 . LCCN   2008020450 . МР   2467561 . OCLC   227205932 . ОЛ   19327100М . Збл   1242.00016 .