前言:第二章!
0X00 等值式
设公式 A、B 共同含有 n 个命题变项,若 A 与 B 有相同的真值表,则说明在 个赋值下,A 和 B 的真值相同。
因此:
恒为真,是「重言式」。此时称 A 与 B 是「等值式」记做
例题:判断下面两个公式是否等值
与
由于真值表完全相同!所以这两个公式等值
为了接下来的「等值演算」,我们必须学会一些等值式定律。
例:证明
0X01 析取范式和合取范式
基本概念
- 文字
命题变项及其否定的统称
比如 可以叫做文字, 也可以叫做一个文字
- 简单析取式
有限个「文字」构成的析取式
比如:
- 简单合取式
有限个「文字」构成的合取式
比如:
- 范式
「析取范式」和「合取范式」的总称
- 析取范式
有限个「简单合取式」组成的「析取式」
比如:
注意前四个,这都是「简单合取式」数目为 1 的「析取范式」
- 合取范式
有限个「简单析取式」组成的「合取式」
注意前四个,这都是「简单析取式」数目为 1 的「合取范式」
「极小项」以及「极大项」
先感性地认识「极小项」以及「极大项」首先我们拿两个「命题变相」形成「极小项」和「极大项」
同样也可以用三个命题变项,形成「极小项」和「极大项」
为了方便记忆,我是这么理解的:合取范围变小,所以是「极小项」、析取范围变大,所以是「极大项」
「主合取范式」和「主析取范式」
之前说了「合取范式」:有限个「简单析取式」组成的「合取式」
如果「简单析取式」是「极大项」那么这个范式就是「主合取范式」
相反如果,「析取范式」中的「简单合取式」是「极小项」的话这个范式就是「主析取范式」
在后面我会举一个求「主合取范式的例子」
0X02 联结词的完备集
假设 S 是一个联结词集合,如果任何 n(n>0)元真值函数都可以由仅含 S 中的联结词构成的公式表示,则 S 是「联结词的完备集」
我们有一个最基本的完备集:
也就是说所有的真值函数都能用这三个联结词表示!
0X03 用等值演算法得到「主析取范式」和「主合取范式」
举个例子,求: 的「主析取范式」和「主合取范式」
在这里不写出完整过程,只是将 转换成「极小项」的方法记录下来
这一步可以直接写,缺啥补啥
最后!「极小项」还可以和「极大项」互相转换