Подстановка (логика)

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

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

Логика высказываний

Определение

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

(Р → С) и (Т → С)

является подстановочным экземпляром:

П&К

(А ↔ А) ↔ (А ↔ А)

является подстановочным экземпляром:

(А ↔ А)

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

Тавтологии

Пропозициональная формула является тавтологией , если она истинна при каждой оценке (или интерпретации ) ее предикатных символов. Если Φ является тавтологией, а Θ является подстановочным примером Φ, то Θ снова является тавтологией. Этот факт подразумевает обоснованность правила вывода, описанного в предыдущем разделе.

Логика первого порядка

В логике первого порядка подстановка — это полное отображение σ : V → T переменных в термины ; многие, ^[1]^{: 73}^[2]^{: 445} , но не все ^[3]^{: 250} авторы дополнительно требуют σ ( x ) = x для всех, кроме конечного числа переменных x . Обозначение { x ₁ ↦ t ₁ , …, x _k ↦ t _k } ^{[примечание 1]} относится к подстановке, отображающей каждую переменную x _i в соответствующий термин t _i , для i = 1,…, k , и каждую другую переменную в себя; x _i должны быть попарно различны. Большинство авторов дополнительно требуют, чтобы каждый термин t _i синтаксически отличался от x _i , чтобы избежать бесконечного множества различных обозначений для одной и той же подстановки. Применение этой подстановки к термину t записывается в постфиксной нотации как t { x ₁ ↦ t ₁ , ..., x _k ↦ t _k }; это означает (одновременную) замену каждого вхождения x i _в t на t i _. [ ^{примечание 2]} Результат tσ применения подстановки σ к термину t называется экземпляром этого термина t . Например, применение подстановки { x ↦ z , z ↦ h ( a , y ) } к термину

Область dom ( σ ) подстановки σ обычно определяется как множество фактически замененных переменных, т. е. dom ( σ ) = { x ∈ V | xσ ≠ x }. Подстановка называется базовой подстановкой, если она отображает все переменные своей области в базовые , т. е. свободные от переменных, термы. Экземпляр подстановки tσ базовой подстановки является базовым термом, если все переменные t находятся в области σ , т. е. если vars ( t ) ⊆ dom ( σ ). Подстановка σ называется линейной подстановкой, если tσ является линейным термом для некоторого (и, следовательно, каждого) линейного термома t, содержащего точно переменные области σ , т. е. с vars ( t ) = dom ( σ ). Подстановка σ называется плоской подстановкой , если xσ является переменной для каждой переменной x . Подстановка σ называется переименовывающей подстановкой, если она является перестановкой на множестве всех переменных. Как и каждая перестановка, переименовывающая подстановка σ всегда имеет обратную подстановку σ ⁻¹ , такую, что tσσ ⁻¹ = t = tσ ⁻¹σ для каждого термина t . Однако невозможно определить обратную подстановку для произвольной подстановки.

Например, { x ↦ 2, y ↦ 3+4 } является базовой заменой, { x ↦ x ₁ , y ↦ y ₂ +4 } является не базовой и не плоской, но линейной, { x ↦ y ₂ , y ↦ y ₂ +4 } является нелинейной и не плоской, { x ↦ y ₂ , y ↦ y ₂ } является плоской, но нелинейной, { x ↦ x ₁ , y ↦ y ₂ } является как линейной, так и плоской, но не переименованием, поскольку она отображает как y , так и y ₂ в y ₂ ; каждая из этих замен имеет множество { x , y } в качестве своей области определения. Примером переименования является подстановка { x ↦ x ₁ , x ₁ ↦ y , y ↦ y ₂ , y ₂ ↦ x }, она имеет обратную { x ↦ y ₂ , y ₂ ↦ y , y ↦ x ₁ , x ₁ ↦ x }. Плоская подстановка { x ↦ z , y ↦ z } не может иметь обратную, поскольку, например, ( x + y ) { x ↦ z , y ↦ z } = z + z , и последний член не может быть преобразован обратно в x + y , поскольку информация о происхождении a z теряется. Основная подстановка { x ↦ 2 } не может иметь обратной из-за аналогичной потери исходной информации, например, в ( x +2) { x ↦ 2 } = 2+2, даже если замена констант переменными допускалась некоторым фиктивным видом «обобщенных подстановок».

Две подстановки считаются равными, если они отображают каждую переменную в синтаксически равные результирующие термы, формально: σ = τ, если xσ = xτ для каждой переменной x ∈ V. Композиция двух подстановок σ = { x ₁ ↦ t ₁ , …, x _k ↦ t _k } и τ = { y ₁ ↦ u ₁ , …, y _l ↦ u _l } получается путем удаления из подстановки { x ₁ ↦ t ₁τ , …, x _k ↦ t _k τ , y ₁ ↦ u ₁ , …, y _l ↦ u _l } тех пар y _i ↦ u _{i ,} для которых y _i ∈ { x ₁ , …, x _k }. Композиция σ и τ обозначается как στ . Композиция является ассоциативной операцией и совместима с применением подстановки, т. е. ( ρσ ) τ = ρ ( στ ) и ( tσ ) τ = t ( στ ) соответственно для любых подстановок ρ , σ , τ и каждого термина t . Тождественная подстановка , которая отображает каждую переменную в себя, является нейтральным элементом композиции подстановки. Подстановка σ называется идемпотентной , если σσ = σ , и, следовательно, tσσ = tσ для каждого термина t . Когда x _i ≠ t _i для всех i , подстановка { x ₁ ↦ t ₁ , …, x _k ↦ t _k } является идемпотентной тогда и только тогда, когда ни одна из переменныхx _i встречается в любом t _j . Подстановочная композиция не коммутативна, то есть στ может отличаться от τσ , даже если σ и τ идемпотентны. ^[1]^{: 73–74}^[2]^{: 445–446}

Например, { x ↦ 2, y ↦ 3+4 } равно { y ↦ 3+4, x ↦ 2 }, но отличается от { x ↦ 2, y ↦ 7 }. Подстановка { x ↦ y + y } является идемпотентной, например, (( x + y ) { x ↦ y + y }) { x ↦ y + y } = (( y + y )+ y ) { x ↦ y + y } = ( y + y )+ y , в то время как подстановка { x ↦ x + y } является неидемпотентной, например, (( x + y ) { x ↦ x + y }) { x ↦ x + y } = (( x + y )+ y ) { x ↦ x + y } = (( x + y )+ y )+ y . Примером некоммутирующих замен является { x ↦ y } { y ↦ z } = { x ↦ z , y ↦ z }, но { y ↦ z } { x ↦ y } = { x ↦ y , y ↦ z }.

Математика

В математике существует два распространенных применения подстановки: подстановка переменных на константы (также называемая присваиванием для этой переменной) и свойство подстановки равенства , ^[4] также называемое законом Лейбница . ^[5]

Рассматривая математику как формальный язык , переменная — это символ из алфавита , обычно буква типа $x$ , $y$ и $z$ , которая обозначает диапазон возможных значений . ^[6] Если переменная свободна в данном выражении или формуле , то ее можно заменить любым значением в ее диапазоне. ^[7] Некоторые виды связанных переменных также могут быть заменены. Например, параметры выражения (например, коэффициенты многочлена ) или аргумент функции . Более того, переменные, являющиеся универсально квантифицированными, можно заменить любым значением в ее диапазоне, и результатом будет истинное утверждение . (Это называется универсальной инстанциацией )

Для неформализованного языка, то есть в большинстве математических текстов за пределами математической логики , для отдельного выражения не всегда возможно определить, какие переменные являются свободными, а какие связанными. Например, в , в зависимости от контекста, переменная может быть свободной и связанной, или наоборот, но они не могут быть оба свободными. Определение того, какое значение предполагается свободным, зависит от контекста и семантики . ${\textstyle \sum _{i<k}a_{ik}}$ ${\textstyle я}$ ${\textstyle к}$

Свойство подстановки равенства , или закон Лейбница (хотя последний термин обычно зарезервирован для философских контекстов), обычно гласит, что если две вещи равны, то любое свойство одной из них должно быть свойством другой. Это можно формально сформулировать в логической нотации как: Для каждого и и любой правильно сформированной формулы (со свободной переменной x). Например: Для всех действительных чисел $a$ и $b$ , если $a$ $=$ $b$ , то $a$ $\geq 0$ подразумевает $b$ $\geq 0$ (здесь, x $\geq 0$ ). Это свойство, которое чаще всего используется в алгебре , особенно при решении систем уравнений , но применяется почти в $каждой$ области математики, где используется равенство. Это, взятое вместе с рефлексивным свойством равенства, образует аксиомы равенства в логике первого порядка. ^[8] $(a=b)\implies {\bigl [}\phi (a)\Rightarrow \phi (b){\bigr ]}$ ${\textstyle а}$ ${\textstyle б}$ ${\textstyle \фи (х)}$ $\фи (x)$

Подстановка связана с композицией функций , но не идентична ей ; она тесно связана с β -редукцией в лямбда-исчислении . Однако, в отличие от этих понятий, акцент в алгебре делается на сохранении алгебраической структуры операцией подстановки, на том факте, что подстановка дает гомоморфизм для данной структуры (в случае полиномов — кольцевой структуры). ^{[ необходима цитата ]}

.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}@media screen{html.skin-theme-clientpref-night .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}Алгебра

Подстановка — это базовая операция в алгебре , в частности в компьютерной алгебре . ^[9]^[10]

Обычный случай подстановки включает полиномы , где подстановка числового значения (или другого выражения) для неопределенного одномерного полинома равносильна оценке полинома при этом значении. Действительно, эта операция происходит так часто, что обозначение для полиномов часто адаптируется к ней; вместо обозначения полинома именем типа P , как это делается для других математических объектов, можно определить

P(X)=X^{5}-3X^{2}+5X-17

так что замена для X может быть обозначена заменой внутри « P ( X )», скажем

P(2)=13

или

P(X+1)=X^{5}+5X^{4}+10X^{3}+7X^{2}+4X-14.

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

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

Примечания

^ Некоторые авторы используют [ t ₁ / x ₁ , …, t _k / x _k ] для обозначения этой подстановки, например, М. Вирсинг (1990). Ян ван Леувен (ред.). Алгебраическая спецификация . Справочник по теоретической информатике. Т. B. Elsevier. С. 675–788., здесь: стр. 682.
^ С точки зрения алгебры термов множество термов T является алгеброй свободных термов над множеством переменных V , следовательно, для каждого отображения подстановки σ: V → T существует единственный гомоморфизм σ : T → T , который согласуется с σ на V ⊆ T ; определенное выше применение σ к термому t тогда рассматривается как применение функции σ к аргументу t .

Цитаты

^ ab Дэвид А. Даффи (1991). Принципы автоматического доказательства теорем . Wiley.
^ ab Franz Baader , Wayne Snyder (2001). Alan Robinson и Andrei Voronkov (ред.). Unification Theory (PDF) . Elsevier. стр. 439–526. Архивировано из оригинала (PDF) 2015-06-08 . Получено 2014-09-24 .
^ N. Dershowitz; J.-P. Jouannaud (1990). "Rewrite Systems". В Jan van Leeuwen (ред.). Formal Models and Semantics . Handbook of Theoretical Computer Science. Vol. B. Elsevier. pp. 243–320.
^ Соболев, СК (создатель). " Аксиомы равенства" . Энциклопедия математики . Springer . ISBN 1402006098.
^ Дойч, Гарри и Павел Гарбач, «Относительная идентичность», Стэнфордская энциклопедия философии (издание осень 2024 г.), Эдвард Н. Залта и Ури Нодельман (ред.), предстоящий URL: https://plato.stanford.edu/entries/identity-relative/#StanAccoIden
^ Соболев, СК (создатель). "Индивидуальная переменная". Энциклопедия математики . Springer . ISBN 1402006098. Получено 2024-09-05 .
^ Соболев, СК (создатель). Свободная переменная. Энциклопедия математики . Springer . ISBN 1402006098.
^ Фитинг, М. , Логика первого порядка и автоматическое доказательство теорем (Берлин/Гейдельберг: Springer, 1990), стр. 198–200.
^ Маргрет Х. Хофт; Хартмут Ф.В. Хофт (6 ноября 2002 г.). Вычисления с помощью Mathematica. Эльзевир. ISBN 978-0-08-048855-4.
^ Андре Хек (6 декабря 2012 г.). Введение в Maple . Springer Science & Business Media. ISBN 978-1-4684-0484-5. замена.

Ссылки

Краббе, М. (2004). О понятии подстановки . Logic Journal of the IGPL, 12, 111–124.
Карри, Х. Б. (1952) Об определении субституции, замещения и родственных понятий в абстрактной формальной системе . Revue philosophique de Louvain 50, 251–269.
Хантер, Г. (1971). Металогика: Введение в метатеорию стандартной логики первого порядка . Издательство Калифорнийского университета. ISBN 0-520-01822-2
Kleene, SC (1967). Математическая логика . Переиздано в 2002 г., Дувр. ISBN 0-486-42533-9

Внешние ссылки

Замена в n-й лаборатории