成真指派、成假指派（命题逻辑）
| 成真指派 | |
|---|---|
| 术语名称 | 成真指派 |
| 英语名称 | satisfying assignment |
| 别名 | 满足指派 |
| 成假指派 | |
|---|---|
| 术语名称 | 成假指派 |
| 英语名称 | falsifying assignment |
成真指派(satisfying assignment)和成假指派(falsifying assignment)描述命题公式在特定指派下的行为，指这个命题公式在这一指派下成为真命题或假命题，也即这个指派是否满足这个命题公式。
定义
基本概念
对于命题公式 [math]\displaystyle{ \phi }[/math] 和指派 [math]\displaystyle{ \sigma }[/math] ：
- 若 [math]\displaystyle{ \sigma\vDash\phi }[/math] ，称指派 [math]\displaystyle{ \sigma }[/math] 是公式 [math]\displaystyle{ \phi }[/math] 的一个成真指派(satisfying assignment)；
- 若 [math]\displaystyle{ \sigma\nvDash\phi }[/math] ，则称 [math]\displaystyle{ \sigma }[/math] 是 [math]\displaystyle{ \phi }[/math] 的一个成假指派(falsifying assignment)。
性质
- 互补性：对于任意公式 [math]\displaystyle{ \phi }[/math] 和指派 [math]\displaystyle{ \sigma }[/math] ， [math]\displaystyle{ \sigma }[/math] 要么是 [math]\displaystyle{ \phi }[/math] 的成真指派，要么是成假指派，二者必居其一。
- 可数性：包含 [math]\displaystyle{ n }[/math] 个命题变元的公式，可能的真值赋值总数为 [math]\displaystyle{ 2^n }[/math]，成真指派和成假指派的数量之和为 [math]\displaystyle{ 2^n }[/math] 。
与主范式的关系
- 成真指派和成假指派与主析取范式、主合取范式及其中极小项、极大项有深刻联系，见对应条目。
- 成真指派和成假指派对应真值表中的一行，也就是一个解释。
- 成真指派和成假指派的数量与命题公式分类及可满足性密切相关，见对应条目。