1、离散数学Date 1离 散 数 学第一部分数理逻辑Date 2离 散 数 学第二章 命题逻辑等值演算n 等值式n 析取范式与合取范式n 联结词的完备集n 可满足性问题与消解法Date 3离 散 数 学1 等值式定义 1n 设 A, B是两个命题公式，若 A, B构成的等价式 A B为重言式，则称 A与 B是等值的，记作 A B.n 不是联结符 (语法 )，等值的一种记法，元语言符号 (语义 )n 命题公式之间的等值关系 ” ”是等价关系n 具有自反性、对称性和传递性Date 4离 散 数 学例 1 判断下面公式是否等值(p q) 与 p qp q (p q) p q (p q) ( p q)0
2、 0 1 1 10 1 0 0 11 0 0 0 11 1 0 0 1Date 5离 散 数 学例 2 等值判断练习n p q 与 p qn p (q r) 与 (p q) rn (p q) r 与 (p q) rDate 6离 散 数 学下面的逻辑电路功能等效吗X = (A B C) (A B)X = A BDate 7离 散 数 学替换性质命题 1：n 设 A是一个命题公式，含有命题变项 p1, p2, , pn, 又设 A1, A2, , An是任意的命题公式。对每一个i(i=1,2,n), 把 pi在 A中的所有出现都替换成 Ai, 所得到的新命题公式记作 B. 那么，如果 A是重言式
3、，则 B也是重言式。n p pn (a+b)2=a2+2ab+b2 n 注意：n 若将 pi替换成 Ai, 须将 pi的所有出现都换为 Ain 替换时只能替换命题变元 , 不能替换命题公式Date 8离 散 数 学文氏图Date 9离 散 数 学常用的等值式模式1. 双重否定律 (double negation law)n A A2. 幂等律 (idempotent laws)n A A A, A A A3. 交换律 (commutative laws)n A B B A, A B B A, A B B A4. 结合律 (associative laws)n (A B) C A (B C)n (A B) C A (B C)n (A B) C A (B C) 练习： 是否具有结合律 Date 10离 散 数 学
