耿素云等清华版离散数学第一章 命题逻辑4-6节.ppt

1、第四节 联结词全功能集,一、3种常用联结词 定义 设p, q为两个命题， 复合命题“p, q之中恰有一个成立”称为p与q的排斥或，记为pq称作排斥或（异或）联结词， pq为真当且仅当p、q中恰有一个为真。 pq (p q) (p q), 定义 设p, q为两个命题，复合命题“p与q的否定”称为p与q的与非式，记为：pq， 称为与非联结词， pq为真当且仅当p，q不同时为真。 pq (pq), 定义 设p, q为两个命题，复合命题“p或q的否定”称为p与q的或非式，记为：p q， 称为或非联结词， p q为真当且仅当p，q同时为假。 pq (pq) 我们可以称与为复合联结词,几点说明： 若S是联

2、结词全功能集，则任何命题公式都可由S中的联结词所表示； 极小全功能集：不含冗余联结词的全功能集； 几个常见的极小全功能集： , , 、, 、 ,，见教材14页。,第五节 对偶与范式,一、对偶 定义：在仅含有联结词, , 的命题公式A中，将换成 ， 换成, ，若A中含有0或1，将0换成1，1换成0， 所得命题公式称为A的对偶式，记作A*. 注：A与A*互为对偶，即（A*）*=A. 定理1 设 A和A*互为对偶式，则 （1） A(P1, P2,Pn) A*(P1, P2, Pn); （2）A(P1, P2, Pn) A*(P1, P2,Pn). 定理2（对偶原理） 设A，B为两命题公式，若AB，则

3、 A* B*. 注：由对偶原理，若A为重言式，A*必为矛盾式；,解： （1）(pq)r (pq)r （消去）, pqr （结合律）,注意：最后结果既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）,（2）(pq)r, (pq)r （消去第一个）, (pq)r （消去第二个）, (pq)r （否定号内移德摩根律）,最后一步已为析取范式（两个简单合取式构成） 继续： B (pq)r, (pr)(qr) （对分配律） 最后一步已为合取范式（由两个简单析取式构成）,三、主析取范式与主合取范式 1.极小项与极大项 定义1 在含有n个命题变项的简单合取式中，

4、若每个命题变项或其否定不同时存在，而二者之一必出现且仅出现一次，而且第i（1in）个命题变项或其否定出现在左起第i位上，称这样的简单合取式为极小项。.,几点说明： n个命题变项产生2n个极小项：（每个位置都可能出现该命题变项或其否定，n个变项有n个位置） 2n个极小项均互不等值； （值的理解：将极小项的每个命题变项看成1，该命题变项的否定看成0，则每个极小项对应一个二进制数，也对应一个十进制数，这些二进制数必不相等，且每个二进制数正是该极小项的成真赋值）； 用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示. 称mi为极小项的名称.,定义2 在含有n个命题变项的简单析取式中，若每个命

5、题变项或其否定不同时存在，而二者之一必出现且仅出现一次，而且第i（1in）个命题变项或其否定出现在左起第i位上，称这样的简单析取式为极大项.,几点说明： n个命题变项产生2n个极大项 2n个极大项均互不等值； （值的理解：将极大项的每个命题变项看成0，该命题变项的否定看成1，则每个极大项对应一个二进制数，也对应一个十进制数，这些二进制数必不相等，且每个二进制数正是该极小项的成假赋值）； 用Mi（i=0,12n-1）表示第i个极大项，其中i是该极大项成假赋值的十进制表示, 称Mi为极大项的名称.,（1）求主析取范式 (pq)r (pq)r （析取范式） ,(pq) (pq)(rr), (pqr)

6、(pqr), m6m7 ,r (pp)(qq)r (pqr)(pqr)(pqr)(pqr) m1m3m5m7 , 代入并排序，得 (pq)r m1m3m5 m6m7 （1，3，5，6，7） （主析取范式）,（2）求A的主合取范式 (pq)r (pr)(qr) （合取范式） ,pr p(qq)r, (pqr)(pqr), M0M2 ,qr (pp)qr (pqr)(pqr) M0M4 , 代入并排序，得 (pq)r M0M2M4 （0，2，4） （主合取范式）,3. 主范式的用途与真值表相同. （1）求公式的成真成假赋值 (pq)r m1m3m5 m6m7，其成真赋值为001, 011, 101

7、, 110, 111，当然成假赋值为000, 010, 100. 类似地，由主合取范式也立即求出成假或成真赋值.,解 p(qr) m0m1m2m3 m4m5 m7 (pq)r m0m1m2m3 m4m5 m7 (pq)r m1m3 m4m5 m7 显见，中的两公式等值，而的不等值.,4. 最后说明： 由公式A的主析取范式确定它的主合取范式，反之亦然： 极小项和极大项的关系： miMi， Mi mi,第六节 推理理论,（1）(pq)pq （2）(pq)qp,解 命题符号化: p：今天是1号，q：明天是5号. 证明的形式结构采用（1）.,证（1）（用等值演算法） (pq)pq (pq)p)q pqq 1，,是重言式，所以推理正确,解:(1) 事实符号化： p：甲盗窃；q：乙盗窃；r：作案时间发生在午夜前； s：乙的证词正确；t：午夜时灯光未灭,(2) 形式结构 前提：pq，pr，st,，s r， t 结论：q, s 拒取式, sr 前提引入, p 拒取式,r 假言推理,(3) 证