命题逻辑复习题和答案

1、命题逻辑 一、选择题（每题3分） 1下列句子中哪个是命题 （C） A、你的离散数学考试通过了吗B 是有理数 D 2、 下列句子中哪个不是命题 (C ) A、 你通过了离散数学考试 B 我说的是真话 D 3、 下列联接词运算不可交换的是（C ） AB、C 4、 命题公式P Q不能表述为（B ） A P或QB 、非P每当Q 、请系好安全带！ 、本命题是假的 、我俩五百年前是一家 、淮海工学院是一座工厂 、D 、 C、非P仅当Q D、除非P，否则Q 5、永真式的否定是（B ） A、永真式B、永假式C 、可满足式D 、以上答案均有可能 6、 下列哪组赋值使命题公式 P （P Q）的真值为假（D ） （

2、1）2 24当且仅当3是奇数 （2） 2 24当且仅当3不是奇数; 7、 下列为命题公式 P （Q R）成假指派的是（B ） A、 100B、 101 C 、110 D、 111 Q :语法错误; R :程序错误, 则命题 “停机的原因在于语法错误或程序错误” 的符号化为（ Q R B 、Q P S C、 Q R B 、P Q R C、Q R 17、设 P：你来了； Q :他唱歌；R :你伴奏 则命题 “如果你来了，那末他唱不唱歌将看你是否伴奏而定” 的符号化为（D） (Q R) B 、P (Q R) C、P (R Q) P (Q R) 18 存在并且唯一B 、存在但不唯一 不存在 不能够确定

3、 在命运题逻辑中，任何非永真命题公式的主合取范式都是 19、 20、 21、 存在并且唯一B 、存在但不唯一 不存在 不能够确定 n个命题变元所产生互不等价的极小项项数为（ 、2n n2 2n n个命题变元所产生互不等价的极大项项数为（ 、2n n2 2n 在命题逻辑中，任何非永假命题公式的主析取范式都是（ 、填充题（每题4分） Q. 1、设P ：你努力，Q :你失败，则 “虽然你努力了，但还是失败了”符号化为P 2、 设P ：它占据空间， Q :它有质量，R :它不断运动，S :它叫做物质， 则“占据空间的，有质量的而且不断运动的叫做物质”符号化为S P Q R. 3、 一个命题含有n个原子

4、命题，则对其所有可能赋值有2n种. 4、 推理规则 A (A B) B的名称为假言推理. 5、 推理规则 B (A B) A的名称为拒取式. 6、 推理规则 A (A B) B的名称为析取三段论. 7、 推理规则 (A B) (B C)A C的名称为前提三段论 8、 当赋予极小项足标相同的指派时，该极小项的真值为1，当赋予极大项足标相同的指派 时，该极大项的真值为 0. 9、 任意两个不同极小项的合取式的真值为0，而全体极小项的析取式的真值为I 10、 任意两个不同极大项的析取式的真值为1，而全体极大项的合取式的真值为0. n 11、 n个命题变元可构造包括 F的不同的主析取范式类别为 22

5、. 12、 n个命题变元可构造包括 T的不同的主合取范式类别为 22 . 三、问答题(每题6分) 1、设A、B是任意命题公式，请问 A B, A B分别表示什么其有何关系 答：A B表示A蕴含B，A B表示A永真蕴含B ； 其关系表现为：若 A B为永真式，则有 A B . 2、 设A、B是任意命题公式，请问 A B, AB分别表示什么其有何关系 答：AB表示A等值于B，AB表示A与B逻辑等价； 其关系表现为：若 AB为永真式，则有 A B. 3、设A、B、C是任意命题公式，若 A C B C ，则AB成立吗为什么 答：不一定有AB ； 若A为真，B为假，C为真，则A C B C成立，但AB不

6、成立 4、设A、B、C是任意命题公式，若A C B C ，则AB成立吗为什么 答：不一定有AB ； 若A为真，B为假，C为假，则A C B C成立，但AB不成立. 5、 设A、B是任意命题公式，A (A B)B 一定为真吗为什么 答：一定为真；因 A (A B) B A ( A B) B (A A) (A B) B F (A B) B A B B T.(用真值表也可证明) 6、 设A、B是任意命题公式，(A B) (A B)A 一定为真吗为什么 答：一定为真；因(A B) (A B) ( A B) ( A B) A (B B) A.(用真值表也可证明) 四、填表计算题(每题10分) q)，要求

7、 (2)求该命题公式的主析取范式与主合取范式 1、对命题公式 A (p q) (p (1 )用0或1填补其真值表的空格处； 解： p q (p q) pq A 1 0 0 0 1 0 1 0 0 1 1 1 p q 00 01 10 1 0 1 0 (0,1,3). 11 主析取范式A(2);主合取范式A 2、对命题公式 A (p q) r，要求 (1 )用0或1填补其真值表的空格处；(2)求该命题公式的主析取范式与主合取范式 解： p q r p qA 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0

8、1 1 1 1 1 主析取范式 A (13,4,7) ；主合取范式 A (0,2,5,6). 3、对命题公式 A (p q) (p r)，要求 (1 )用0或1填补其真值表的空格处；(2)求该命题公式的主析取范式与主合取范式 解: r p q p r A 主析取范式A 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 (5,6,7);主合取范式 A (0,123,4) 4、对命题公式 A ( p q) (p r)，要求 (1 )用0或1填补其真值表的空格

9、处；(2)求该命题公式的主析取范式与主合取范式 解: p q r p p q p r A 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1 主析取范式A (2,3,5,7)；主合取范式 A (0,1,4,6) 5、对命题公式 A （ p q） r，要求 （1 ）用0或1填补其真值表的空格处；（2）求该命题公式的主析取范式与主合取范式 解： p q r P q p q A 0 0 0 1 1 1 0 0 0 1 1 1 1

10、1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 主析取范式A （13,5,6,7）;主合取范式A （0,2,4） 五、证明题（每题10分） 1、证明下列逻辑恒等式: (P Q) (R Q) (P R) Q. (P R) Q P R Q 右. （用真值表也可证明） 2、证明下列逻辑恒等式： P Q R R Q P 证明：左（PQ） R P QR 证明 左(P Q) ( R Q) (P R) Q R (Q P) R Q P 右. （用真值表也可证明） 3、证明下列逻辑恒等式：

11、 P Q P Q P Q . 证明：左PQ P Q P Q P Q P Q P Q PP P Q Q P QQ P Q P Q P Q P Q 右.（用真值表也可证明） 4、用逻辑推理规则证明： (a b) c ，d ， c d a b . 证明:(1) c d P (2) d P (3) c T (1),(2)( 析取三段论) (4) (a b) c P (5) (a b) T，( 拒取式) (6) a b T(德.摩根律). 5、用逻辑推理规则证明： p q , p s, s r r q. 证明：(1) P s P (2) s r P (3) P r T (1),(2)( 前提三段论) (

12、4) r p T(逆反律) (5) p q P (6) p q T(蕴含表达式) r q T，( 前提三段论 ) . 6、用逻辑推理规则证明： p q，p r， q r， r， s ps. 证明 ： (1) r P (2) q r P (3) q T (1),(2)( 析取三段论 ) (4) p q P (5) p T，( 拒取式 ) (6) s p P s T，( 析取三段论 ) . 7、用逻辑推理规则证明： (p q) (r s)，(q p)r ， r p q 证明 ： (1) r P (2) (q p) r P (3) q p T (1),(2)( 析取三段论 ) (4) r s T (

13、1)(加法式) (p q) (r s) (6) p q (7) (p q)(qp) (8) p q 8、用逻辑推理规则证明：sp, 证明：(1) s (2) S p (3) p (4) p r q (5) r q (6) q (7) s q 9、 用逻辑推理规则证明：(p q) 证明： (1)pq (2) p (3) pq (4) ( pq)r (5) r (6) (pq)r (p q) 10、 用逻辑推理规则证明：p q, 证明：(1) p (2) pq (3) q (4) qr (5) r (6) rs (7)S T，(拒取式) T (3),(合取式) T(等值表达式). p r q, r

14、 s q. P P T (1),(2)(析取三段论) P T (3)，(4)(假言推理) T (5)(简化式) CP. r (p q) r P(附加前提) T(1)(简化式) T(2)(加法式) P T (3),(4) (假言推理) r CP . q r,r s p s. P ( 附加前提 ) P T (1)，(析取三段论) P T (3) ， (4) ( 析取三段论 ) P T (5) ， (6) (假言推理) CP . (8) ps f) c, b (a s) b e. 11、用逻辑推理规则证明：（p q） （r s）, （r s） t p t . 证明： (1) P P（附加前提） P

15、q T（1）（加法式） (p q) (r s) P r s T （2） , （3）（假言推理） r T（4）（简化式） r s T （5）（加法式） (r s) t P (8) t T （6），（7）（假言推理） (9) P t CP. 12、用逻辑推理规则证明： (t w)s, q s, ts q t 证明： 1) q P（附加前提） (2) q s P (3) s T （1），（2）（析取三段论） (t w) s P (5) (t w) T，（4）（拒取式） ( t w) T（蕴含表达式） t w T（德.摩根律） (8) t T（简化式） (9) q t CP . 证明：（1） b P（

16、附加前提） ( 2) b (as) P (3) as T （1），（2）（假言推理） (4) a T（简化式） (5) a b c P (6) bc T （4） ，（5）（假言推理） (7) c T（简化式） 13、用逻辑推理规则证明：a b c, （e (8) (e f) cP (9) (e f) T， （8）（拒取式） (10) (e f) T (9)( 蕴含表达式） (11) e f T (10)( 德.摩根律） (12) e T (11)( 简化式） (13) b e CP. 14、用逻辑推理规则证明： p q， p q q. 证明： （1） q P （附加前提） (2) p q P

17、(3) p T (1),(2)( 拒取式 ） (4) p q P (5) q T ,(4)( 假言推理） (6) q q T (1),(5)( 合取式） 由（6）得出矛盾式，故原命题有效 15、用逻辑推理规则证明：p q , （p q） （t s） 证明：（1） (t s) P（附加前提） (2) (p q) (t s) P (3) (p q) T （1）,（2）（拒取式） (4) ( p q) ( pq) T （3）（等值与蕴含表达式） (5) (p q) ( p q) T (4) ( 德. 摩根律 ) (6) (p q) (p q) T （5）（结合律或范式等价 p q T（简化式） (8

18、) (p q) T（4）（德.摩根律） (9) pq P (10) ( p q) ( p q) T (9),(10)(合取式) 由（10）得出矛盾式，故原命题有效 16、用逻辑推理规则证明： p q， p r，（q r）不能同时为真. 证明：（1） p T （1）（简化式） pq P q T,（3）（假言推理） (q r) P qr T（德.摩根律） q T（简化式） (8) qq T，（合取式） 由 （8）得出矛盾式， 故原命题有效 . 17、证明下列命题推得的结论有效：或者逻辑难学，或者有少数学生不喜欢它；如果数学容 易学，那么逻辑并不难学因此，如果许多学生喜欢逻辑，那么数学并不难学 证明

19、：设p :逻辑难学；q :有少数学生不喜欢逻辑学；r :数学容易学. 该推理就是要证明：p q, r p q r. (1) pq P pq T （1）（蕴含表达式） (3) rp P rq T,（3）（前提三段论） qr T（逆反律）. 18、证明下列命题推得的结论有效： 如果今天是星期三， 那么我有一次离散数学或数字逻辑 测验；如果离散数学课老师有事， 那么没有离散数学测验； 今天是星期三且离散数学老师有 事.所以，我有一次数字逻辑测验 . 证明：设 p ： 今天是星期三； q ：我有一次离散数学测验； r： 我有一次数字逻辑测验； s ：离散数学课老师有事 . 该推理就 是要证明：p (q r), sq , p s r . (1) P s P (2) p T （1）（简化式） (3) s T （1）（简化式） (