文章目录
abstract
元真值函数和
- 由
- 这从理论上解释了为什么仅使用
三个联结词就可以表示任意命题公式
- 甚至可以用更少的联结词(比如2个或1个)来描述任意命题公式
- 高级联结词与非联结词和或非联结词可以单独构成联结词完备集
联结词的完备集
元真值函数
- 定义
为**
元真值函数**
- 函数
的自变量为
个命题变项
- 定义域
=
,即有
组成的长度为
- 值域为
个不同的真值函数(类比于
- 不妨设所有
- 函数
在
个赋值下分别有
- 类似的设函数
在
- 若存在
使得
说明
是不同的函数,否则相同
- 显然,
函数取值仅有2种可能(0或1),
;若逐个指定
在
(
,
个不同的序列,对应
- 在不需要讨论具体函数而只需知道其变量个数时,不妨将
,若需要区分不同的函数,则指定下标:
- 例如,一元真值函数有
个
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
真值函数和命题公式的对应关系
- 每个主析取范式对应无穷多个等值的命题公式,每个命题公式又都有唯一等值的主析取范式
- 主合取范式和主析取范式相仿
- 每个真值函数对应于无穷多个等值的命题公式,每个命题公式又都对应唯一的真值函数
联结词完备集
- 设
是一个联结词集合,若任何
元真值函数都可以由仅含
是联结词完备集
- 证明:
- 任何
元真值函数都可以表示成唯一的一个主析取范式(真值函数
(变量-函数值表)真值表
- 而主析取范式中仅含
中的联结词,所以
是联结词完备集
推论
- 设
- 若为
添加更多联结词,得到
,则
- 例如:{
};{
}
- 若
可以被
={
}
- 因为
={
}
- 因为
- 若联结词完备集
={
}
- 考虑到
以及
- 有
- 可见
能够表示
,所以
常见的复合(高级)联结词
与非联结词
- 设
是两个命题,复合命题"
与(合取)
的否定式"
称作
是与非联结词
- 显然
为真
p |
q |
|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
或非联结词
- 复合命题"
=
称为或非联结词
- 显然仅当
p |
q |
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
两个复合联结词的完备性
- {
},{
}都是联结词完备集
- 又因为
,
,都是完备集,所以结论成立