离散数学作业.doc

. 第一章命题逻辑的基本概念一、判断下列语句是否是命题,若是命题是复合命题则请将其符号化(1)中国有四大发明。(2)2是有理数。(3)“请进!”(4)刘红和魏新是同学。(5) a+b (6)你去图书馆吗? (7)如果买不到飞机票,我哪儿也不去。(8)侈而惰者贫,而力而俭者富。(韩非:《韩非子?显学》) (9)火星上有生命。(10)这朵玫瑰花多美丽啊! 二、将下列命题符号化,其中 p:2<1,q:3<2 (1)只要 2<1 ,就有 3<2 。( 2)如果 2<1 ,则 3?2。( 3)只有 2<1 ,才有 3?2。(4)除非 2<1 ,才有 3?2。(5)除非 2<1 ,否则 3 ?2。(6) 2<1 仅当 3<2 。三、将下列命题符号化(1) 小丽只能从筐里拿一个苹果或一个梨。(2) 王栋生于 1992 年或 1993 年。. 四、设 p、 q的真值为 0; r、 s的真值为 1,求下列各命题公式的真值。( 1) p∨(q∧r) (2)(p ?r)∧(﹁q∨s) (3)(? p∧? q∧r) ?(p∧q∧﹁r) (4) (? r∧s)→(p∧? q) :“?是无理数。并且,如果 3是无理数,则2 也是无理数。另外 6能被 2整除, 6才能被 4整除。”六、用真值表判断下列公式的类型: (1) p∧(p→ q)∧(p→? q) (2) (p∧ r)?(? p∧? q) (2)((p → q)∧(q→ r))→(p→ r) . 第二章命题逻辑等值演算一、用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值. (1)?(p∧ q→ q) (2)(p →(p∨ q)) ∨(p→ r) (3)(p ∨ q)→(p∧ r) 二、用等值演算法证明下面等值式(1)(p →q)∧(p→r)?(p→(q∧r)) (2)(p ∧? q)∨(? p∧q)?(p∨q)∧?(p∧q) . 三、用等值演算求下列公式的主析取范式与主合取范式,并求成真赋值(1)( ? p→q)→(? q∨p) (2)?(p→q)∧q∧r(3)(p ∨(q∧r)) →(p∨q∨r) 四、用真值表法求下列公式的主析取范式,再用主析取范式求主合取范式(1) (p∨ q)∧ r (2)p →(p∨ q∨ r) . 第三章命题逻辑的推理理论一、填空 。推理是指,前提是,结论是。 : A 1,A ,2, ?,A ,k推B的推理正确当且仅当二、先把下列命题符号化,再写出前提、结论、推理的形式结构,然后用 3 种方法证明(真值表法、等值演算法、主析取范式法)证明下列推理是正确的。若a是奇数,则a不能被 2整除。若a是偶数,则a能被 2整除。因此,若a 是偶数,则 a不是奇数。设p:a是奇数,q: a能被 2整除,r: a是偶数. 三、在自然推理系统下用直接法或用附加前提法或用归谬法构造下列推理的证明(1) 前提: p? q,?(q? r),r 结论: ? p (2) 前提:q? p,q? s,s? t,t? r 结论: p? q (3)前提:p?(q? r),s ? p,q (4)前提:p?? q,? r? q,r?? s 结论: s? r结论: ? p 四、在自然推理系统下构造下列推理的证明如果我学习,那么我数学不会不及格。如果不热衷于玩游戏,那么我将学习。但我数学不及格。因此我热衷于玩游戏。. 第四章一阶逻辑的基本概念一、将下列命题用 0元谓词符号化. (1) 小王学过英语和法语。(2) 除非李建是东北人,否则他一定怕冷。(3)2 大于 3仅当 2大于 4。(4)3 不是偶数。(5)2 或 3是素数。二、在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b) 条件时命题的真值:(1) 对于任意 x,均有)2 )(2(2 2????xxx (2) 存在 x,使得 x+5=9. 其中(a) 个体域为自然数集合. (b) 个体域为实数集合. 三、在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数。(2) 在北京卖菜的人不全是外地人。(3) 乌鸦都是黑的。(4) 有的人天天锻炼身体。. 四、给定解释 I如下:(a) 个体域 D为实数集合 R. (b) D中特定元素 a =0. (c) 特定函数 f (x,y)=x-y,x,y D?(d) 特定谓词 F (x,y):x=y, G (x,y):x<y,x,y D?. 说明下列公式在 I下的含义,并指出各公式的真值: (1) )),(),((yxFyxGyx????(2) )),() ),,(((yxGayxfFyx???(3) )) ),,((),((ayxfFyxGyx????(4) )),() ),,(