《数理逻辑与集合论：2-1 命题逻辑的等值和推理演算》由会员分享，可在线阅读，更多相关《数理逻辑与集合论：2-1 命题逻辑的等值和推理演算（24页珍藏版）》请在金锄头文库上搜索。
1、第2章 命题逻辑的等值和推理演算2.1 等值定理2.2 等值公式2.3 命题公式与真值表的关系2.4 联结词的完备集2.5 对偶式2.6 范式2.7 推理形式2.8 基本的推理公式2.9 推理演算2.10 归结推理法讨论讨论等值演算等值演算讨论讨论推理演算推理演算公式的类型定义定义 设设A为一个合式公式为一个合式公式 (1) 若若A无成假赋值，则称无成假赋值，则称A为为重言式重言式( (也称也称永真式永真式) ) (2) 若若A无成真赋值，则称无成真赋值，则称A为为矛盾式矛盾式( (也称也称永假式永假式) ) (3) 若若A不是矛盾式，则称不是矛盾式，则称A为为可满足式可满足式P Q F F
2、F T F T T TP QTTFTTTTT (P Q) QFFFF可满足式可满足式永真式永真式矛盾式矛盾式 (P Q) (P Q)2.1 等值定理n等价的定义n设设A和和B是两个命题公式，对是两个命题公式，对A和和B的任一赋值，的任一赋值，A和和B的真值都相同，则称的真值都相同，则称A和和B是等值的（或等价的），是等值的（或等价的），记为记为A = B或或ABn注意：是关系符，是关系符，是联结词是联结词n显然，根据显然，根据真值表真值表可判明任何两个公式是否等值可判明任何两个公式是否等值n如(P Q)与与P Q和和P QP Q F F F T T F T T PTTFFTFFF P Q TT
3、TF(P Q) QTFTFP Q P Q FTTTTFFF等值定理n等值定理对公式对公式A和和B，A=B的充分必要条件是的充分必要条件是AB是重言式是重言式n即即若若AB是重言式，则在任一解释下，是重言式，则在任一解释下，A和和B都都只能有相同的真值只能有相同的真值n命题公式的等值关系“=”有下面的性质：1.自反性自反性A = A2.对称性对称性若若A = B，则，则B = A3.传递性传递性若若A = B，B = C，则，则A = C对任意命题公式对任意命题公式A，B和和C A B AB0001101110012.2 等值公式1.基本的等值公式（命题定律）基本的等值公式（命题定律）双重否定律
4、双重否定律: A = A等幂律等幂律：A A = A,A A = AAA=T，AA=T交换律交换律:A B = B A, A B = B AAB=BA，ABBAA,B,C代表任意的代表任意的命题公式命题公式ABAB BAFFTTFTTFTFFTTTTT2.2 等值公式1.基本的等值公式（命题定律）基本的等值公式（命题定律）结合律结合律:(A B) C = A (B C),(A B) C = A (B C)(AB)C=A(BC),(AB)CA(BC)分配律分配律:A (B C)=(A B) (A C),A (B C)=(A B) (A C) A(BC)=(AB)(AC)A (BC)(A B)(A
5、C)A,B,C代表任意的代表任意的命题公式命题公式：满足结合律，满足结合律， 不满足交换律不满足交换律：不满足结合律，不满足结合律， 满足交换律满足交换律等值公式1.基本的等值公式（命题定律）基本的等值公式（命题定律）摩根律摩根律: (A B)= AB， (A B)= AB吸收律吸收律:A (A B)=A,A (A B)=A零律零律:A T=T,A F=F同一律同一律:A F=A, A T=ATA=A，TA=A，补余律补余律:AA = T，AA = F，A,B代表任意代表任意的命题公式的命题公式等值公式2.常用等值公式常用等值公式nAB = A B （由联结词的真值表得）nAB = BA （由
6、逆否命题=原命题得）nA(BC)=(A B)CnA(BC)=B(AC)（前提条件可交换次序）n(AC) (BC)=(A B)CnAB = (AB) (BA)(由联结词的定义得)nAB = ( A B) (AB)nAB = (A B) ( A B)（由联结词的真值表得）A,B代表任意代表任意的命题公式的命题公式 ABABABAB (AB)FFTTTFTFTTFFTFTFFTFTFTTFFFTF基本等值公式的证明举例n原则上说，上面的公式均可用真值表证明。下面仅验证摩根律。 (AB) = AB等值演算与置换规则n等值演算 n由已知的等值公式推演出新的等值公式的过程由已知的等值公式推演出新的等值公式
7、的过程n如已知如已知: A A = A 则则: B A A = B An置换规则置换规则：若若AB,则则 (B) (A)n如如: A AA 则则 B (A A) B An等值演算的基础：(1)等值关系的性质：自反、对称、传递等值关系的性质：自反、对称、传递(2)基本的等值式基本的等值式(3)置换规则置换规则 六个重要的等值式AB = A B P Q=(P Q) (Q P) PQ=(P Q) ( P Q) P Q = (P Q) ( P Q) (A B)= AB (A B)= AB等值演算举例1例例1证明证明P(QR)=(P Q)R证证:P(QR)= P ( Q R)（蕴涵等值式，置换规则）（蕴
8、涵等值式，置换规则）=( PQ) R（结合律，置换规则）（结合律，置换规则）= (P Q) R（德摩根律，置换规则）（德摩根律，置换规则）=(P Q)R(蕴蕴涵涵等等值值式式，置置换换规规则则）也可以从右边开始演算也可以从右边开始演算P(QR)=Q(PR)等值演算举例2例例2证明：证明：PQ = (P Q) ( P Q) 证证:P Q=(PQ) (QP)=(P Q) (Q P)=(P Q) (P P) (Q Q) (Q P)=(P Q) F F (Q P)(矛盾律矛盾律)=(P Q) (Q P)(同一律同一律) P Q = (P Q) (P Q)(分配律分配律)P19例1等值演算举例3:n证证
9、明：明：( P ( Q R) (Q R) (P R)=Rn证：左左边边=( PQ) R) (Q P) R)=( (P Q) R) (P Q) R)=( (P Q) (P Q) R)=T R = R =右右边边分分 配配 律律 A (B C)=(A B) (A C)结结合合律律：(A B) C = A (B C)摩根律：摩根律： (A B)= AB分分 配配 律律 A (B C)=(A B) (A C)补余律：补余律：AA = TP19例2等值演算举例4：试证(P Q)( P ( QR) ( PQ) ( P R)=T证证：左左边边=(P Q) ( P(Q R) ( P ( QR)=(P Q) (
10、P (Q R) ( P (Q R)=(P (Q (Q R)(P (Q R)=(P (Q R)(P (Q R)=T可见，能用等值演算证明公式的类型，此例说明它为重言式可见，能用等值演算证明公式的类型，此例说明它为重言式摩根律：摩根律： (A B)= AB ， (A B)= AB用等值演算法判断下列公式的类型(1)Q(PQ)解解Q(PQ)=Q( P Q)（蕴涵等值式）（蕴涵等值式）=Q (PQ)（德摩根律）（德摩根律）=P (QQ)（交换律，结合律）（交换律，结合律）=P F（矛盾律）（矛盾律）=F（零律）（零律）由最后一步可知，该式为由最后一步可知，该式为矛盾式矛盾式.用等值演算法判断下列公式的
11、类型(2)(P Q) (PQ) R解解:(P Q) (PQ) R=(P (QQ) R（分配律）（分配律）=P T R（排中律）（排中律）=P R（同一律）（同一律）这不是矛盾式，也不是重言式，而是非重言式的这不是矛盾式，也不是重言式，而是非重言式的可可满足式满足式.如如101是它的成真赋值是它的成真赋值,000是它的成假赋值是它的成假赋值.总结：总结：A为矛盾式当且仅当为矛盾式当且仅当A = F A为重言式当且仅当为重言式当且仅当A = T命题公式等值演算的应用化简下面程序段:if A if B X else Y elseif B X else Yn执行执行X的条件为：的条件为：(A B) (
12、 A B)n执行执行Y的条件为：的条件为：(A B) ( A B)=B= Bif B Xelse YABBXYTTTFFFXYBXYTF2.3 命题公式与真值表的关系n按真值表列出命题公式的方法n从从T来列出来列出n如下表中如下表中A为为T有三种可能有三种可能所以，所以，A的命题公式形式为：的命题公式形式为：而取而取T相应的相应的P、Q解释分别为：解释分别为： P Q、 PQ、PQn所以，所以，A=( P Q) ( PQ) (PQ)n同理，可列出同理，可列出B=( P Q) ( PQ)= P A=P QC= Q P Q AB ACFFFTTFTTTTFTTTFFFFTFTFT任意任意 P Q
13、PQPQ命题公式与真值表的关系n按真值表列出命题公式的方法n从从F来列出来列出n如下表中如下表中B为为F有二种可能有二种可能所以，所以，B的命题公式形式为：的命题公式形式为：而取而取F相应的相应的P、Q解释分别为：解释分别为： PQ、 P Qn所以，所以，B=( PQ)( P Q)= Pn同理，同理，A= PQ P Q AB ACFFFTTFTTTTFTTTFFFFTFTFT任意任意 PQ P Q2.4 联结词的完备集复合联结词排排斥斥或或: P Q = (PQ) ( P Q)(异异或或)与非式与非式: P Q = (P Q)或非式或非式: P Q = (P Q)PQP QP QP QFFFT
14、TFTTTFTFTTFTTFFF如如:P:他在家里他在家里.Q:他在做作业他在做作业.P Q:并非并非他在家里或在做作业他在家里或在做作业.联结词“”的性质 n定义：定义：PQ = (P Q)n性质性质PP = (P P)=P(PQ)(PQ)=(PQ)=(P Q)=P Q(PP)(QQ)=(P)(Q)=(P Q)=P Q类似地，可用类似地，可用“”表表示命题公式间的示命题公式间的“与与”、“或或”和和“非非”关系关系真真值值表表中中每每个个公公式式的的真真值值都都有有T、F两两种种可可能能，所所以以命命题题公公式式的的真真值值有有24=16种种可可能能，既既有有个不同的真值表。故有个不同的真值表。故有种不等价的公式。种不等价的公式。PQ公式FTT或FFTT或FTFT或FTTT或F真值函数问题：两个命题变项可构成多少个不等价的合式公式？n即两个命题变项构成的合式公式有多少个不同的真值表即两个命题变项构成的合式公式有多少个不同的真值表？结论：结论：含含n个命题变项的所有公个命题变项的所有公式共产生式共产生个互不相同个互不相同的真值表的真值表作业2P37: 1 (1)(3)P37: 2P37: 3注意：下次上课前交作业
