命题变元代入

代入
术语名称	代入
英语名称	subtitution

对命题变元的代入(subtitution)指在一个命题公式（或谓词公式）中，将某个命题变元的全体出现，全部用另一个公式来替换的操作。

定义

代入

从全体命题变元所构成的集合到全体公式所构成的集合的映射，称为一个代入(substitution)。

对于把 [math]\displaystyle{ p_1, \dots, p_n }[/math] 分别替换为 [math]\displaystyle{ \phi_1, \dots, \phi_n }[/math] 的代入，也记作 [math]\displaystyle{ \phi_1/p_1, \dots, \phi_n/p_n }[/math] 。这一能用 [math]\displaystyle{ n }[/math] 个列出的情况称为有穷代入。

注：特别地，映射可以将部分个体变量投影到其自身，即映射 [math]\displaystyle{ s }[/math] 允许存在某个 [math]\displaystyle{ s(p_i)=p_i }[/math] 。

公式的代入

对任意公式 [math]\displaystyle{ \phi }[/math] 和代入 [math]\displaystyle{ s }[/math] ，递归地定义公式 [math]\displaystyle{ \phi }[/math] 做代入 [math]\displaystyle{ s }[/math] 的结果 [math]\displaystyle{ \phi(s) }[/math] 为：

1. 若 [math]\displaystyle{ \phi }[/math] 是命题变元 [math]\displaystyle{ p }[/math] ，则 [math]\displaystyle{ \phi(s)=s(p) }[/math] 。
2. 若 [math]\displaystyle{ \phi }[/math] 是 [math]\displaystyle{ \lnot\psi }[/math] ，则 [math]\displaystyle{ \phi(s)=\lnot(\psi(s)) }[/math] 。
3. 若 [math]\displaystyle{ \phi }[/math] 是 [math]\displaystyle{ \psi\odot\chi, \circ\in C_2 }[/math] ，则 [math]\displaystyle{ \phi(s)=\psi(s) \odot \chi(s) }[/math] 。

[math]\displaystyle{ \psi(s) }[/math] 也记作 [math]\displaystyle{ \psi[\phi_1/p_1, \cdots, \phi_n/p_n] }[/math] 。

命题逻辑/零阶逻辑
基本概念	命题	命题、命题变元、命题常量
	真值	真 [math]\displaystyle{ \mathrm{T} }[/math]/[math]\displaystyle{ 1 }[/math]/[math]\displaystyle{ \top }[/math] 、假 [math]\displaystyle{ \mathrm{F} }[/math]/[math]\displaystyle{ 0 }[/math]/[math]\displaystyle{ \bot }[/math]
命题结构	命题结构	原子命题、复合命题
	逻辑联结词	否定（非） [math]\displaystyle{ \lnot }[/math] 、合取（且/与） [math]\displaystyle{ \land }[/math] 、析取（或） [math]\displaystyle{ \lor }[/math]
		蕴涵（推出） [math]\displaystyle{ \rightarrow }[/math] 、等价（当且仅当） [math]\displaystyle{ \leftrightarrow }[/math]
命题公式	形式定义	命题语言 [math]\displaystyle{ \mathcal{L}_0 }[/math] 、命题公式
	逻辑语义	指派、 Tarski 真理定义、解释、真值表、满足
	语义分类	重言式/永真式、偶然式/仅可满足式/可真可假式、矛盾式/永假式/不可满足式
	语义关系	重言等价/等值/等价 [math]\displaystyle{ = }[/math]/[math]\displaystyle{ \Leftrightarrow }[/math] 、重言蕴涵 [math]\displaystyle{ \Rightarrow }[/math]
	范式	析取范式、合取范式（主析取范式、主合取范式）

谓词逻辑/一阶逻辑
命题结构	项	个体词（个体常项、个体变项）、论域/个体域、函项、项、闭项
	谓词	谓词（谓词常项、谓词变项）
	量词	量词（辖域、出现）、全称量词 [math]\displaystyle{ \forall }[/math] 、存在量词 [math]\displaystyle{ \exists }[/math]
谓词公式	形式定义	谓词语言 [math]\displaystyle{ \mathcal{L}^* }[/math] 、谓词公式、闭式
	逻辑语义	结构、指派/赋值、基本语义定义、解释、满足、模型
	语义分类	普遍有效公式、可满足式、不可满足式
	语义关系	逻辑等值/逻辑等价 [math]\displaystyle{ = }[/math]/[math]\displaystyle{ \Leftrightarrow }[/math] 、逻辑蕴涵 [math]\displaystyle{ \Rightarrow }[/math]
	范式	前束范式、 Skolem 范式
	个体变项代入	可自由代入、易字、简单易字变形、易字变形
	命题变元代入	置换定理