离散数学作业.doc

离散数学作业布置第1次作业(P15)、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=:“π是无理数。并且,如果3是无理数,则也是无理数。另外只有6能被2整除,6才能被4整除。”解:p:π是无理数1q:3是无理数0r:是无理数1s: 6能被2整除1t:6能被4整除0命题符号化为:p∧(q→r)∧(t→s)的真值为1,所以这一段的论述为真。:(4)(p→q)→(﹁q→﹁p)(5)(p∧r)↔(﹁p∧﹁q)(6)((p→q)∧(q→r))→(p→r)解:(4)pqp→qqpq→p(p→q)→(q→p)00111110110111100**********所以公式类型为永真式,最后一列全为1(5)公式类型为可满足式(方法如上例),最后一列至少有一个1(6)公式类型为永真式(方法如上例,最后一列全为1)。第2次作业(P38),对不是重言式的可满足式,再用真值表法求出成真赋值.(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,111Pqr￢p∧￢qp∧r(￢p∧￢q)∨(p∧r)0001010011010100000110001000001010111**********:(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Û(p∨q)∧﹁(p∧q)第3次作业(P38),并求成真赋值:(1)(￢p→q)→(￢q∨p)(2)(￢p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)(4)￢(p→q)∧q∧r解:(1)(￢p→q)→(￢q∨p)Û￢(p∨q)∨(￢q∨p)Û￢p∧￢q∨￢q∨pÛ￢q∨p(吸收律)Û(￢p∨p)∧￢q∨p∧(￢q∨q)Û￢p∧￢q∨p∧￢q∨p∧￢q∨p∧qÛm0∨m2∨m2∨m3Ûm0∨m2∨m3成真赋值为00,10,11.(2)(￢p→q)∧q∧rÛ(p∨q)∧q∧rÛ(p∧q∧r)∨q∧rÛ(p∧q∧r)∨(￢p∨p)∧q∧rÛp∧q∧r∨￢p∧q∧r∨p∧q∧rÛm3∨m7成真赋值为011,111.(3)(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∨￢p∧￢r∨p∨q∨rÛ￢p∧￢q∧(r∨￢r)∨￢p∧(q∨￢q)∧￢r∨p∧(q∨￢q)∧(r∨￢r)∨(p∨￢p)∧q∧(r∨￢r)∨(p∨￢p)∧(q∨￢q)∧rÛm0∨m1∨m2∨m3∨m4∨m5∨m6∨m7,为重言式.(4)￢(p→q)∧q∧rÛ￢(￢p∨q)∧q∧rÛ(p∧￢q)∧q∧rÛp∧(￢q∧q)∧rÛ0主析取范式为0,无成真赋值,(P38),并求成假赋值:(1)￢(q→￢p)∧￢p(2)(p∧q)∨(￢p∨r)(3)(p→(p∨q))∨r解:(1)￢(q→￢p)∧￢pÛ￢(￢q∨￢p)∧￢pÛq∧p∧￢pÛq∧0Û0ÛM0∧M1∧M2∧,01,10,11.(2)(p∧q)∨(￢p∨r)Û(p∧q)∨￢p∨rÛ(p∨￢p)∧(￢p∨q)∨rÛ(￢p∨q)∨rÛ￢p∨q∨rÛM4,成假赋值为100.(3)(p→(p∨q))∨rÛ(￢p∨(p∨q))∨rÛ(￢p∨p)∨q∨rÛ1主合取范式为1,(P41):(1)