离散数学逻辑等价式

《离散数学逻辑等价式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§1.3逻辑等值式定义：若公式A、B构成AB为永真式，称A、B逻辑等值，记为ABAB成为永真式，即是A为0时，B为0；A为1时B为1。AB，A、B不一定具有相同变元。例如：P∧PQ∧QAB中,是联结词，AB是公式；AB中,是符号判别等值的方法真值表（适用于n<=3）等值演算法用真值表判别A、B等值例：求证A∧(A∨B)A构造公式A∧(A∨B)和A的真值表；判断两个的真值表是否相同。是，则等价。11111111010101000000A∧(A∨B)ABA返回判别等值的方法基本等值式（一）名称等值

2、式双重否定AA等幂律A∧AAA∨AA交换律A∧BB∧AA∨BB∨A结合律(A∧B)∧CA∧(B∧C)(A∨B)∨CA∨(B∨C)德·摩根律(A∧B)A∨B(A∨B)A∧B吸收律A∧(A∨B)AA∨(A∧B)A零律A∧00A∨11同一律A∧1AA∨0A基本等值式(二）名称等值式否定律A∧A0A∨A1蕴涵等值式A→BA∨B等价等值式AB（A→B）∧（B→A）逆否律A→BB→A输出律(A∧B)→CA→(B→C)归谬律(A→B)∧(A→B)A置换定理设

3、Φ(A)是含命题公式A的命题公式，Φ(B)是用命题公式B置换了Φ(A)中的A得到的公式。如果AB，则Φ(A)Φ(B)(A∧B)A∨B的证明0001011110010101101101110100(A∧B)A∨BBA1245311116A∧(A∨B)A的证明1111101000001101A∧(A∨B)ABA2111113A→BA∨B的证明11113111110100001A→BA∨BBA21311001110等价演算（等值演算）作用一：证明两公式等价例：证明(p∨(p∧q))(p

4、∧q)证明:(p∨(p∧q))((p∨p)∧(p∨q))分配律(T∧(p∨q))否定律(p∨q)同一律p∧q德·摩根律等价演算（等值演算）作用二：判别一公式的类型例：证明(p∧q)→(p∨q)是重言式证明：(p∧q)→(p∨q)(p∧q)∨(p∨q)(p∨q)∨(p∨q)(p∨p)∨(q∨q)T∨TT所以，(p∧q)→(p∨q)是重言式又例：判定公式(p∧q→p)的类型解：(p∧q→p)((p∧q)∨p)((p∧q))∧p(p∧q)∧p(p∧p)∧

5、qF∧q所以,(p∧q→p)是矛盾式F等价的传递性AB,BC,则AC化简电路图A(p,q)=(p∧q)∧(p∨q)(p∨q)∧(p∨q)(p∧p)∨(q∧p)∨q0∨qqpqA(p,q)qA(p,q)§1.4联结词的全功能集联结词的全功能集：能表达任一命题的联结词集。例如{,∨,∧}{,∨,∧,→}若一个联结词的全功能集不含冗余的联结词,则称为极小全功能集{,∧}{,∨}简介：A↑B定义为：(A∧B),(与非联结词)A↓B定义为：(A∨B),(或非联结词)则{↑}，{

6、↓}是全功能集。例1:试证{↑}是全功能集.证：┐P┐(PP)P↑PPQ┐┐(PQ)┐(P↑Q)(P↑Q)↑(P↑Q)PQ┐(┐P┐Q)┐((P↑P)(Q↑Q))(P↑P)↑(Q↑Q)例2.试证{┐，→}是全功能集证：PQ┐(┐P┐Q)┐(P→┐Q)PQ┐(┐P)Q┐P→Q从{0,1}n到{0,1}的真值函数有22n个pqF0F1…………0001101100000001F12F13F14F15110111101111取n=2为例1100本节小结1.基本等值式2.真值表的方法、

7、等价(值)演算使用真值表等值演算法判定公式类型证明公式等价子公式：公式X是公式A的组成部分，称X为A的子公式。代入规则:A(p1,p2,…,pi,…,pn),另一公式Bi处处代替pi出现的地方，得到的公式A’＝A(p1,p2,…,Bi,…,pn)，A’称为A的代入实例。例结论：如果A是永真式，则A的任一个代入实例都是永真式。