离散数学作业-2.doc

离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（ r∧s）→(p∧ q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则 SKIPIF 1 0 也是无理数。另外只有6能被2整除，6才能被4整除。” 解： p: π是无理数 1 q: 3是无理数 0 r: SKIPIF 1 0 是无理数 1 s:　6能被2整除 1 t: 6能被4整除 0 命题符号化为： p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁ q) （6）((p→q) ∧(q→r)) →(p→r) 解： （4） p q p→q q p q→ p (p→q)→( q→ p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 ，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁ p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ? ￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111 P q r ￢p∧￢q p∧r (￢p∧￢q) ∨(p∧r) 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 所以公式类型为可满足式 2.4 用等值演算法证明下面等值式： (2) ( (p→q)∧(p→r) ) ? (p→(q∧r)) (4)(p∧﹁q)∨(﹁p∧q) ? (p∨q)∧﹁(p∧q) 证明（2）(p→q)∧(p→r) ?( ﹁p∨q)∧(﹁p∨r) ?﹁p∨(q∧r)) ?p→(q∧r) （4）(p∧﹁q)∨(﹁p∧q) ? (p∨(﹁p∧q)) ∧(﹁q∨(﹁p∧q) ) ? (p∨﹁p)∧(p∨q)∧(﹁q∨﹁p) ∧(﹁q∨q) ?1∧(p∨q)∧ (﹁p∨﹁q)∧1 ?