《[工学]1-78 对偶与范式03版》由会员分享，可在线阅读，更多相关《[工学]1-78 对偶与范式03版（46页珍藏版）》请在金锄头文库上搜索。
1、1-7对偶与范式1-7.1 对偶式定义1-7.1 在给定的命题公式A中， 将联结词换成 ，将换成，若有 特殊变元F和T亦相互取代，所得公式 A*称为A的对偶式。显然，A也是A*的对偶式。1-7.1 对偶式例 : 求对偶式a)(P Q ) Rb)(P Q ) Tc)P Qd)P Q e)(P Q )( P ( Q S)(PQ)R (PQ)FP Q P Q(P Q)( P ( Q S)1-7.1 对偶式定理1-7.1 设A和A*是对偶式，P1，P2，Pn 是出现在A 和A*中的原子变元，则A(P1, P2, , Pn)A*( P1, P2, , Pn)A( P1, P2, , Pn) A*(P1,
2、 P2, , Pn)证明：由德.摩根定律 (PQ) P Q( PQ ) PQ故 A(P1, P2, , Pn)A*( P1, P2, , Pn)同理A( P1, P2, , Pn) A*(P1, P2, , Pn)1-7.1 对偶式 例题：设A * (S,W,R)是 S ( W R)，证明 ： A * ( S, W, R) A（S,W,R）解：由定理知： A* (S,W,R)即 S ( W R)A* ( S, W, R) 即S ( W R) 而 A(S,W,R) 为 S ( W R) S （W R) (S ( W R) A* ( S, W, R) 故 A* ( S, W, R) A(S,W,R
3、)1-7.1 对偶式定理1-7.2 设P1，P2，Pn 是出现在公式A和B 中的所有原子变元，如果AB，则A* B*。 证明：见P301-7.2 范式(normal form)定义1-7.2 合取范式(conjunctive normal form) ：一个命题公式称为合取范式，当且仅当它具有形 式： A1 A2 An，（n1）其中A1，A2 ，An都是由命题变元或其否定 所组成的析取式。 例 (P QR) (PQ) Q是一个合取范式。(PQ)是否是合取范式？ (PQ)是否是合取范式？是 不是1-7.2 范式定义1-7.3 析取范式(disjunctive normal form) ： 一个命
4、题公式称为析取范式，当且仅当它具有形 式： A1 A2 An，（n1）其中A1，A2 ，An都是由命题变元或其否定 所组成的合取式。 例 P (P QR) (PQ) 是一个析取范式。(PQ)是否是析取范式？ (PQ)是否是析取范式？是不是1-7.2 范式求命题公式的合取范式或析取范式的三个步骤 见P311-7.2 范式例：求P ( (Q R)S)的析取范式。 解：原式P (Q R) S) P (Q R) S) P (Q R) S 例：求(P Q) R的合取范式。 解：原式 (P Q) R (P Q) R (PR) (QR) 1-7.2 范式请做P39 (1) 求公式P( P Q) 的析取范式和
5、合取范式。 解：原式 P (PQ) 为合取范式 (PP) (PQ) 为析取范式F(PQ) PQ1-7.3 主析取范式定义1-7.4 小项 n个命题变元的合取式，称为布尔合取或小 项，其中每个变元与它的否定不能同时存 在，但两者必须出现且仅出现一次。例如：两个命题变元P、Q，其小项为PQ， P Q， PQ， P Q1-7.3 主析取范式三个命题变元P、Q、R，其小项为PQR ，PQ R ，PQR ， PQR ，PQR ， PQR ，PQR ， P Q R一般说来，n个命题变元共有2n个小项。1-7.3 主析取范式可以得出结论： （1）没有两个小项是等价的 （2）每个小项只对应P和Q的一组真值指派
6、 ，使得该小项的真值为T。 记作：m11= P Q， m10= P Q，m01= PQ， m00= P Q 总结出规律：在小项 中，看P34 小项的性质小项的性质（1）每一个小项当其真值指派与编码相同 时，其真值为T，在其余2n-1种指派情况 下均为F。（2）任意两个不同小项的合取式永假。（3）全体小项的析取式永为真，记为：1-7.3 主析取范式定义1-7.5 对于给定的命题公式，如果有 一个等价公式，它仅由小项的析取所组 成，则该等价式称作原式的主析取范式 。定理1-7.3 在真值表中，一个公式的真值为 T的指派所对应的小项的析取，即为此公 式的主析取范式。 证明见P34。1-7.3 主析取
7、范式 例：求(P Q) R的主析取范式。 解：用真值表法：PQRP Q (PQ)R TTTTT TTFTF TFTFT TFFFT FTTTT FTFTF FFTTT FFFTF1-7.3 主析取范式上式的主析取范式为： (PQR)(PQR)(PQR) (PQR)(PQR) m111 m101 m100 m011 m001 =1,3,4,5,7PQRP Q(PQ)R TTTTT TFTFT TFFFT FTTTT FFTTT1-7.3 主析取范式 求主析取范式的方法分为： （1）真值表法 （2）等价公式法 看P36 推演步骤看P35 例题8，例题91-7.3 主析取范式例：求(P Q) R的主
8、析取范式。 解：用等价公式推导法： 原式 (PQ)R(PQ)R (PQ (RR) )( (PP)(QQ)R) (PQR) (PQR)(PQR) (PQR) (PQR) (PQR)(PQR) (PQR)(PQR) (PQR) (PQR)=1,3,4,5,71-7.4 主合取范式 定义1-7.6 大项 n个命题变元的析取式，称为布尔析取或 大项，其中每个变元与它的否定不能同时 存在，但两者必须出现且仅出现一次。例如：两个命题变元P、Q，其大项为PQ， PQ， PQ， PQ1-7.4 主合取范式三个命题变元P、Q、R，其大项为P Q R ，P Q R ，P Q R ， P Q R ，P Q R ，
9、P Q R ，P Q R ， P Q R一般说来，n个命题变元共有2n个大项。1-7.4 主合取范式也可以得出结论： （1）没有两个大项是等价的 （2）每个大项只对应P和Q的一组真值指派， 使得该大项的真值为F。 记作： M00=PQ， M01=P Q，M10= PQ， M11=PQ 总结出规律：在大项 中，看P37 大项的性质大项的性质（1）每一个大项当其真值指派与编码相同 时，其真值为F，在其余2n-1种指派情况 下均为T。（2）任意两个不同大项的析取式永真。（3）全体大项的合取式为永假，记为：1-7.4 主合取范式定义1-7.7 对于给定的命题公式，如果有一个 等价公式，它仅由大项的合取
10、所组成，则该 等价式称作原式的主合取范式。定理1-7.4 在真值表中，一个公式的真值为F的 指派所对应的大项的合取，即为此公式的主 合取范式。 证明 略。1-7.4 主合取范式 例：P39 (3) e) 求( PQ) (PQ)的主合取范式 解：用真值表法：PQ PQPQ ( PQ) (PQ) TTFFF TFFTT FTTFT FFFFF原式 (PQ)(PQ)M11 M00 =0，31-7.4 主合取范式 求主合取范式的方法分为： （1）真值表法 （2）等价公式法 看P38 推演步骤看P38 例题111-7.4 主合取范式 例：求(P Q) R的主合取范式。 解：用等价公式推导法： 原式 (P
11、Q)R(PQ)R(PR)(QR)(PR (Q Q)(QR(PP) (PQR)(PQR)(PQR)(PQ R)(PQR)(PQR)(PQR)=0,2,61-7.3 主析取范式例：求(P Q) R的主析取范式。 解：用等价公式推导法： 原式 (PQ)R(PQ)R (PQ(RR) )( (PP)(QQ)R) (PQR) (PQR)(PQR) (PQR) (PQR) (PQR)(PQR) (PQR)(PQR) (PQR) (PQR) =1,3,4,5,7大家可以看到，当用等价公式推导的方 法求得一公式的主析取范式或主合取范式时 ，可以方便地用编码求得另一种主范式，比 真值表法快一些。 请做P39 (3
12、) c) 求 (PQ)的主析取范式，再用编码大 项写出主合取范式。 解：原式PQ m10 = 2 原式 M00 M01 M11 (PQ) (PQ) ( PQ) =0,1,3作业(1-7)P39 (2) e)(3) b)(4) a) ,c)1-8 推理理论 定义1-8.1 设A和C是两个命题公式，当且仅当 AC为一重言式，即AC ，称C是A的有效 结论。或C可由A逻辑地推出。 定义1-8.2 设H1，H2，Hm 和C为命题公式， 若H1 H2 Hm C，则称C为一组前提H1 ，H2，Hm 的有效结论。证明方法如下： 真值表法（分析法） 公式推导： 分为直接证法、 反证法和 CP规则， 后两种称为
13、间接证法 。1-8 推理理论要证H1 H2 Hm C是重言式 设P1，P2，Pn 是出现在H1，H2， Hm 和C中的所有命题变元。 真值表： P1，P2，Pn ， H1，H2，Hm，C 共n+m+1列1-8.1 真值表法如果有n个命题变元，则真值表n+m+1列， 使得H1，H2，Hm 均为T的真值指派，C也 为T；或者看使得C为F的真值指派的行，在每一 个这样的行中H1，H2，Hm 中至少有一个 为F也可。1-8 推理理论例：P47 (2) a) 证明：AC是前提 AB，CB的有效结论。 ABCABCBACTTTTFFTTFTTTTFTFTFTFFFTTFTTTFTFTFTTTFFTTTTFFFTTT1-8.2 直接证法任务是构造命题公式序列 P 规则：前提在论证过程中随时可以引用。 (premise)T规则：在推导中，如果有一个或多个公式蕴 含着公式S，则公式S可以引入推导之中。1-8.2 直接证法例题：如果张老师来了，这个问题可以得到解 答，如果李老师来了，这个问题也可以得到 解答，总之张老师或李老师来了，这个问题 就可以得到解答。 解：设 P：张老师来了。Q：李老师来了。R：这个问题可以得到解答。(PR)(QR)(PQ)
