离散数学_傅彦_命题逻辑例题精选（可编辑）

离散 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 _傅彦_命题逻辑例题精选（可编辑） 第5章 命题逻辑例题精选 例5.1 设P表示命题“天下雨”,Q表示命题“他骑自行车上班”,R表示命题“他乘公共汽车上班”,试以符号形式写出下列命题(西南交大1995年考研 试题 中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载 ): (1)只要不下雨,他才骑自行车上班; (2)只要不下雨,他就骑自行车上班; (3)除非下雨,否则他就骑自行车上班; (4)他或者骑自行上班,或者乘公共汽车上班。 分析对于命题只要Q才P,只要P就Q,除非Q,否则P等,都可以翻译成P?Q,所以上述1,2,3分别可翻译为:1 Q??P,2 ?P?Q,3 ?Q?P。句子4可翻译为QR。 例5.2 1 使用连接词?,?,构造三个命题变项P,Q,R的MATCH_ word word文档格式规范word作业纸小票打印word模板word简历模板免费word简历 _1714204928518_0L(P,Q,R),使得:?L(P,Q,R)L?P,Q,RLP,?Q,RLP,Q,?R (2)求(1)中公式L(P,Q,R)的主合取范式,(北师大2001年考研试题)。 解 1 设L(P,Q,R) 其中,Mi为关于P,Q,R的极大项。 则?LP,Q,R L?P,Q,R a0M4?a1M5?a2M6?a3M7?a4M0?a5M1?a6M2?a7M3 LP,?Q,R a0M2?a1M3?a2M0?a3M1?a4M6?a5M7?a6M1?a7M2 LP,Q,?R a0M1?a1M0?a2M3?a3M2?a4M5?a5M4?a6M7?a7M6 由?LP,Q,RL?P,Q,RLP,?Q,RLP,Q,?R 对应极大项Mi的系数应相等,为此有: 1a0 a4 a2 a1,1a4 a0 a6 a5 1a1 a5 a3 a0,1a5 a1 a7 a4 1a2 a6 a0 a3,1a6 a2 a4 a7 1a3 a7 a1 a2,1a7 a3 a5 a6 所以a0 a3 a5 a6 a1 a2 a4 a7 如令a0 a3 a5 a60,则a1 a2 a4 a71 此时LP,Q,RM1?M2?M4?M7 ??M1??M2??M4??M7 ??P?Q??R??P??Q? R???P?Q?R? ??P??Q??R 如令a0 a3 a5 a61,则a1 a2 a4 a70 此时LP,Q,RM0?M3?M5?M6??M0??M3??M5??M6 ??P?Q?R??P??Q??R ???P?Q??R? ??P??Q?R 2 LP,Q,RM1?M2?M4?M7 P?Q??R??P??Q?R??P?Q?R??P??Q ??R„主合取范式 M0?M3?M5?M6 P?Q?R?P??Q??R??P?Q??R??P? ?Q?R„主合取范式 例5.3没有命题P:明天上午七点下雨 Q:明天上午七点下雪 R:我将去学 校 符号化下列语句: (1)除非明天上午七点不下雨且不下雪,否则我将不去学校; (2)只要明天上午七点不下雨或不下雪,我就去学校; (3)只有明天上午七点不是雨夹雪,我才去学校; (4)明天上午七点我将雨雪无阻一定去学校。 分析 根据命题P?Q的定义,它可对应语句除非Q,否则?P;只要P,就Q;只有Q才P。所以上述(1),(2),(3)可分别对应符号化为: (1)R?(?P??Q) (2)?P??Q?R (3)R??(P?Q) 句子(4)是雨雪无阻一定去学校,即无论任何天气都不影响去学校,即去学校与天气无关,因此,句子(4)可简单地符号化为:R 但为了完整的表达出该句子的全部意思,应将雨雪无阻符号化。所谓雨雪无阻即是: (P?Q)?(?P?Q)?(P??Q)?(?P??Q) 所以句子(4)完整地符合号为: ((P?Q)?(?P?Q)?(P??Q)?(?P??Q)?R 或 (P?Q?R)?(?P?Q?R)?(P??Q?R)?(?P??Q?R) 说明 由于雨雪无阻与R是同时发生,没有因果关系,所以天气与去学校之间用合取。 例5.4 求公式G1P,Q,RP?Q?P?Q G2P,QP?Q?P?Q 的主析取范式和主合取范式。 分析 公式G1,G2的右端虽然是相同的,但公式的左岸表明两个公式所含的命题变元不同,在求主析取,主合取范式时,由于其极小项,极大项依赖于命题 变元,所以不能仅根据右端的公式来求,还应该根据该公司所含的命题变元的情 况来求。因此,上述两个公式的主析取范式,主合取范式安全不同。下面采用两种 方式来求。 方法1 采用真值表技术。 建立公式G1P,Q,RP?Q?P?Q的真值表如表2.4所示。 表2.4 P,Q,R P?Q?P?Q 0 0 0 100 0 0 1 100 0 1 0 100 0 1 1 100 1 0 0 000 1 0 1 000 1 1 0 111 1 1 1 111 则公式G1P,Q,R所对应的主析取范式、主合取范分别为: G1(P,Q,R)(P?Q??R)?(P?Q?R)„主析取范式 G1(P,Q,R)(P?Q?R)?(P?Q??R)?P??Q?R?P??Q??R ?(?P?Q?R)?(?P?Q??R)„主合取范式 建立公式G2P,Q(P?Q)?(P?Q)的真值表如表2.5所示。 表2.5 P Q (P?Q)?(P?Q) 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 1 1 则公式G2P,Q所对应的主析取范式、主合取范式分别为: G2(P,Q)(P?Q)„主析取范式 G2(P,Q)(P?Q)?(?P?Q)?(P??Q)„主合取范式 方法2 采用公式转换法。 G1(P,Q,R)(P?Q)?P?Q(?P?Q)?P?QP?Q P?Q??R?R(P?Q??R)?(P?Q?R)„主析取范式 G1(P,Q,R)?(?G1P,Q,R) ?(P??Q?R??P?Q?R?P??Q??R ?(?P?Q??R)?(?P??Q?R)?(?P??Q??R) ?P?Q??R?(P??Q??R)?(?P?Q?R)? ?P?Q?R?(P?Q??R)?(P?Q?R) P?Q?R?(P?Q??R)?(P??Q?R)?(P??Q??R)? ?P?Q?R?(?P?Q??R)„主合取范式 G2(P,Q)(P?Q)?(P?Q)(?P?Q)?P?Q(P?Q)„主析取范式 G2(P,Q)?(?G2P,Q)?(P??Q??P?Q??P??Q) (?P?Q)?(P??Q)?(P?Q) (P?Q)?(?P?Q)?(P??Q)„主合取范式 从上可以看出,两个公式的主析取,主合取范式安全不同。 例5.5 判断下面公式的类型(重言式,矛质式,可满足式) (1)(P?Q)?(?Q??P) (2)(P?? Q)??(P?Q) (北师大2000年考研试题) 解 判断一个公式是否是重方式、矛盾式,可满足公式,可采用三种方式:1 真值表技术;2公式等值演算;3求主析取,主合取范式。下面分别采用三种方法: 方法1 真值表技术。 建立公式1,2的真值表如表2.6所示。 表2.6 P Q (P?Q)?(?Q??P) (P?? Q)??(P?Q) 0 0 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 0 由上述真值可知,公式1是重言式,公式2是可满足式。 方法2 公式等值演算。 ? (P?Q)?(?Q??P)(P?? Q)??(P?Q) ?(?P?Q)?(?P?Q)1 所以公式?是永真式(重言式)。 方法3 求公式的主析取、主合取范式。 (P?? Q)??(P?Q)?(P?? Q)??(P?Q) ?(P?Q)??(Q?P)?(?P??Q) ?(?P?Q)??(?Q?P)?(?P??Q) (P??Q)?(?P?Q)?(?P??Q)„主析取范式 ?(?P??Q??P?Q)?(P?Q)(?P??Q)„主合取范式 显然公式?所对应的主析取范式不包括所有的极小项,所以不是重言式, 公式?所对应的主合取范式不包括所有的极大项,所以不是矛盾式,因此,?仅是 可满足式。 例5.6 符号化下列命题,并证明其结论:一公安人员审查一件盗窃案,已 知事实如下: (1)张平或王磊盗窃了机房的计算机一台; (2)若张平盗窃了计算机,则作案时间不可能发生在午夜之前; (3)若王磊的证词正确,则午夜时机房里的灯未灭; (4)若王磊的证词不正确,则作案时间发生在午夜之前; (5)午夜时机房灯光灭了。 问:盗窃计算机的是张平?王磊? 分析 首先将事实符号化: 设P:张平盗窃了计算机; Q:王磊盗窃了计算机; R:作案时间发生在午夜前; S:王磊的证词正确; T:午夜时灯光灭了。 则前提可符号化为: P?Q,P ? ?R,S ? ?T,?S ? R,T 证明的结论为P或Q。 证明 (1)T P (2)S ? ?T P (3)?S T,1,2,I (4)?S ? R P (5)R T,3,4,I (6)P ? ?R P (7)?P T,5,6,I (8)P?Q P (9)Q T,7,8,I 此结论说明是王磊盗窃了机房的计算机。 例5.7 符号化下列命题,并用演译法加以证明:如果6是偶数,则2不能 整除7;或者5不是素数,或2整除7;5是素数。因此,6是奇数。 解 首先将上述事实符号化 设P:6是偶数 Q:2能整除7 R:5是素数 则命题可符号化为 P??Q,?R?Q,R?P 证明 (1)?R?Q P (2)R P (3)Q T,1,2,I (4)P??Q P (5)?P T,3,4,I 说明 本例的证明十分简单,但该例却说明了一个十分重要的情况: 该列的结论是一个错误的结论。我们不能误认为该推导是错误的,或认为该前提不能逻辑地蕴涵结论。实际上,在逻辑推理中,完全允许在错误的假设下逻辑推导出一个错误的结论。一问题正是在错误的前提下(如6是偶数,则2不能整除7),导致了错误的结论,它们之间仍有逻辑蕴涵关系。 例5.8 符号化下列句子,并用反证法(归谬法)加以证明。 (1)如果A因病缺了许多课,那么也中学考试不及格; (2)如果A中学考试不及格,则他没有知识; (3)如果A读了许多书,则他有知识。 (4)所以,A没有缺很多课或没有读很多书。 解 首先将事实符号化: 设P:A因病缺了许多刘; Q:他中学考试及格; R:他有知识; S:他读了许多书。 则上述句子可符号化为: P??Q,?Q??R,S?R?P??S 证明 采用归谬法就是将结论的否定作为附加前提加入到前提集合之中,导致与已知条件的矛盾。 (1)?(?P??S) P附加前提 (2)P?S T,1,2,E (3)P T,2,I (4)S T,2,I (5)P??Q P (6)?Q T,3,5,I (7)S?R P (8)R T,4,7,I (9)?Q??R P (10)Q T,8,9,I (11)Q??Q T,6,10,I 所以,由归谬法知:P??Q,?Q??R,S?R?P??S。 例5.9 设前提集合为PP?Q,P?R,Q?S,GS?R,证明PG。 解 对于该题分别有用三种证明方法加以证明。 证法1 直接证明法。 (1)P?Q P (2)?P?Q T,1,E (3)Q?S P (4)?P?S T,2,3,I (5)?S?P T,4,E (6)P?R P (7)?S?R T,5,6,I (8)S?R T,7,E 证法2 带CP规则的直接证明法。 因G S?R?S?R,为此,可将?S作为附加前提加入前提集合中,如能证明 P,?SR,则由CP规则知:P?S?R即PS?R。 (1)?S P附加前提 (2)Q?S P (3)?Q T,1,2,I (4)P?Q P (5)P T,3,4,I (6)P?R P (7)R T,5,6,I (8)?S?R CP,1,7 (9)S?R T,8,E 证法3 归谬法。 (1)?(S?R) P附加前提 (2)?S??R T,1,E (3)?S T,2,I (4)?R T,2,I (5)P?R P (6)?P T,4,5,I (7)Q?S P (8)?Q T,3,7,I (9)?P??Q T,6,8,I (10)?(P?Q) T,9,E (11)P?Q P (12)(P?Q)??P?Q T,10,11,I 例5.10 证明P?Q?S是P?Q?R,R?Q?S的逻辑结果。 分析 对于这类问题结论是蕴涵的形式,采用带CP规则的直接证明法最方便。 (1)P P附加前提 (2)P?(Q?R) P (3)Q?R T1,2,I (4)R?(Q?S) P (5)Q?(Q?S) T,3,4,I (6)Q P附加前提 (7)Q?S T,5,6,I (8)P?(Q?S) CP,1,7 例5.11 一个排队线路,输入为A,B,C,其输出分别为FA,FB,FC,在同一时间内只能有一个信号通过。如果同时有两个或两个以上信号通过时,则按A,B,C的顺序输出,例如:A,B,C同时输入时,只能A有输出,写出FA,FB,FC的逻辑表达式,并化成全功能集?中的表达式。 解 设P:A输入 Q:B输入 R:C输入 由提所给的条件,易写出FA,FB,FC的真值表如表2.7所示。 表2.7 P Q R FA FB FC 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 由真值表知:它们的主析取范式分别为: FA(P?Q?R)?(P?Q??R)?(P??Q?R)?(P??Q??R) ((P?Q)?(R??R))?((P??Q)?(R??R)) (P?Q)?(P??Q) P?(Q??Q) P ? 1 P ??(P?P)?(P?P)(P?P)?(P?P) FB=(?P?Q??R)?(?P?Q?R)(?P?Q)?(?R?R) ?P?Q??(?P?Q)?(P??Q)P??QP?(Q?Q) FC=(?P??Q?R)?(P?Q)?R(P?Q)?R??(P?Q)???R ?(?(P?Q)??R)?(P?Q)??R((P?Q)?(P?Q))?(R?R) 例5.12 某勘探队有3名队员,有一天取得一块矿样,3人的判断如下: 甲说:这不是铁,也不是铜; 乙说:这不是铁,是锡; 丙说:这不是锡,是铁。 经实验鉴定后发现,其中一人两个判断正确,一个人判对一半,另一个全错 了。根据以上情况判断矿样的种类。 分析 设P:矿样是铁; Q:矿样是铜; R:矿样是锡。 则上述情况可能有: F1:甲全对、乙对一半,丙全错; F2:甲全对、乙全错、丙对一半; F3:甲对一半、乙全对、丙全错; F4:甲对一半、乙全错、丙全对; F5:甲全错、乙全对、丙对一半; F6:甲全错、乙对一半、丙全对。 由于F=(一人全对)?(一人对一半)?(一人全错),所以,上述 F1,F2,„,F6这六种情况应有一种发生,即: F=F1?F2?F3?F4?F5?F6=1 根据命题的表示:F1,F2,„,F6中分别表示如下: F1=(?P??Q)?((?P??R)?(P?R))?(R??P)= (?P??Q?R??P??P??R)?(?P??Q?R??P?P?R)= 0?0=0 F2=(?P??Q)?(P??R)?((?R??P)?(R?P))= 0?((?R?P)?(R?P))=0 F3=((P??Q)?(?P?Q))?((?P?R)?(R??P))= (P??Q??P?R?R??P)?(?P?Q??P?R?R??P) 0?(?P?Q?R) ?P?Q?R F4=((P??Q)?(?P?Q))?(P??R)?(?R?P) (P??Q?P??R??R?P)?(?P?Q??P?R?R??P) (P??Q??R)?0(P??Q??R) F5=(P?Q)?(?P?R)?((R?P)?(?R??P)) (P?Q??P?R)?((R?P)?(?R??P)) 0?((R?P)?(?R??P)) 0 F6=(P?Q)?((?P??R)?(P?R))?(?R?P) (P?Q??P??R??R?P)?(P?Q?P?R??R?P) 0?0 0 所F=0?0?(?P?Q?R)?(P??Q??R)?0?0= (?P?Q?R)?(P??Q??R) 1 但矿样即不可能既是铜又是锡,所以Q,R中必有假命题,即Q,R不能同为真, 所以?P?Q?R 0,因而必有 P??Q??R 1 所以P为真,?Q为真,?R为真,即P为真,Q为假,R为假,即矿样为铁。 例5.13 用P规则和T规则证明下列命题演算的推理关系。 (1)?P?Q,?Q?R,R?SP?S (2)A?(B?C),D?(B??C),A?D是不相容的(人大2001年考研试题) 证明(1)??P?Q P ? P?Q T,?,E ? ?Q?R P ? Q?R T,?,E ? P?R T,?,?,I ? R?S P ? P?S T,?,?,I 故 ?R?Q,?Q?R,R?SP?S (2)?Q?D P ? A?(B?C) P ? A T,?,I ? B?C T,?,?,I ? D?(B??C) P ? D T,?,I ? (B??C) T,?,?,I ? B T,?,I ? C T,?,?,I ??C T,?,I 11 C??C T,?,?,I