离散数学作业-(2)

离散数学作业布置第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=11.17判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外只有6能被2整除，6才能被4整除。”解：p:π是无理数1q:3是无理数0r:2是无理数1s:6能被2整除1t: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）pqp→qqpq→p(p→q)→(q→p)0011111011011110010011110011所以公式类型为永真式，最后一列全为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,111Pqr￢p∧￢qp∧r(￢p∧￢q)∨(p∧r)000101001101010000011000100000101011110000111011所以公式类型为可满足式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(p∨q)∧﹁(p∧q)第3次作业（P38）2.5求下列公式的主析取范式,并求成真赋值:(1)(￢p→q)→(￢q∨p)(2)(￢p→q)∧q∧r(3)(p∨∧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,无成真赋值,为矛盾式.第4次作业（P38）2.6求下列公式的主合取范式,并求成假赋值:(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∧M3这是矛盾式.成假赋值为00,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,为重言式.第5次作业（P41）2.32用消解原理证明下述公式是矛盾式:(1)(￢p∨q)∧(￢p∨r)∧(￢q∨￢r)∧(p∨￢r)∧r(2)￢((p∨q)∧￢p→q)解：(1)(￢p∨q)∧(￢p∨r)∧(￢q∨￢r)∧(p∨￢r)∧r第一次循环S0=Φ,S1=｛￢p∨q,￢p∨r,￢q∨￢r,p∨￢r,r｝,S2=Φ由￢p∨r,p∨￢r消解得到λ输出“no”，计算结束(2)￢((p∨q)∧￢p→q)￢(￢((p∨q)∧￢p)∨q)((p∨q)∧￢p)∧￢q(p∨q)∧￢p∧￢q第一次循环S0=Φ,S1=｛p∨q,￢p,￢q｝,S2=Φ由p∨q,￢p消解得到q,由q,￢q消解得到λ,输出“no”，计算结束2.33用消解法判断下述公式是否可满足的:(1)p∧(￢p∨￢q)∧q(2)(p∨q)∧(p∨￢q)∧(￢p∨r)解：(1)p∧(￢p∨￢q)∧q第一次循环S0=Φ,S1=｛p,￢p∨￢q,q｝,S2=Φ由p,￢p∨￢q消解得到￢q,由q,￢q消解得到λ,输出“no”，计算结束(2)(p∨q)∧(p∨￢q)∧(￢p∨r)第一次循环S0=Φ,S1=｛p∨q,p∨￢q,￢p∨r｝,S2=Φ由p∨q,p∨￢q消解得到p,由p∨q,￢p∨r消解得到q∨r,由p∨￢q,￢p∨r消解得到￢q∨r,由p,￢p∨r消解得到r,S2=｛p,q∨r,￢q∨r,r｝第二次循环S0=｛p∨q,p∨￢q,￢p∨r｝,S1=｛p,q∨r,￢q∨r,r｝,S2=Φ由p∨q,￢q∨r消解得到p∨r,由p∨￢q,q∨r消解得到p∨r,由p∨￢q,q∨r消解得到p∨r,由￢p∨r,p消解得到r,S2=｛p∨r｝第三次循环S0=｛p,q∨r,￢q∨r,r｝,S1=｛p∨r｝,S2=ΦS2=Φ输出“yes”，计算结束第6次作业（P52）3.6判断下面推理是否正确.先将简单命题符号化,再写出前提,结论,推理的形式结构(以蕴涵式的形式给出)和判断过程(至少给出两种判断方法):(1)若今天是星期一,则明天是星期三；今天是星期一.所以明天是星期三.(2)若今天是星期一,则明天是星期二；明天是星期二.所以今天是星期一.(3)若今天是星期一,则明天是星期三；明天不是星期三.所以今天不是星期一.(4)若今天是星期一,则明天是星期二；今天不是星期一.所以明天不是星期二.(5)若今天是星期一,则明天是星期二或星期三.今天是星期一.所以明天是星期二.(6)今天是星期一当且仅当明天是星期三；今天不是星期一.所以明天不是星期三.设p:今天是星期一,q:明天是星期二,r:明天是星期三.(1)推理的形式结构为(p→r)∧p→r此形式结构为重言式,即(p→r)∧pr所以推理正确.(2)推理的形式结构为(p→q)∧q→p此形式结构不是重言式,故推理不正确.(3)推理形式结构为(p→r)∧￢r→￢p此形式结构为重言式,即(p→r)∧￢r￢p故推理正确.(4)推理形式结构为(p→q)∧￢p→￢q此形式结构不是重言式,故推理不正确.(5)推理形式结构为(p→(q∨r))∧p→q它不是重言式,故推理不正确.(6)推理形式结构为(p↔r)∧￢p→￢r此形式结构为重言式,即(p↔r)∧￢p￢r故推理正确.推理是否正确,可用多种方法证明.证明的方法有真值表法,等值演算法.证明推理正确还可用构造证明法.下面用等值演算法和构造证明法证明(6)推理正确.1.等值演算法(p↔r)∧￢p→￢r(p→r)∧(r→p)∧￢p→￢r￢((￢p∨r)∧(￢r∨p)∧￢p)∨￢r￢(￢p∨r)∨￢(￢r∨p)∨p∨￢r(p∧￢r)∨(r∧￢p)∨p∨￢r(r∧￢p)∨p∨￢r吸收律(r∧￢p)∨￢（￢p∨r）德摩根律1即(p↔r)∧￢p￢r故推理正确2.构造证明法前提:(p↔r),￢p结论:￢r证明:①p↔r前提引入②(p→r)∧(r→p)①置换③r→p②化简律④￢p前提引入⑤￢r③④拒取式所以,推理正确.第7次作业（P53-54）3.15在自然推理系统P中用附加前提法证明下面各推理:(1)前提:p→(q→r),s→p,q结论:s→r(2)前提:(p∨q)→(r∧s),(s∨t)→u结论:p→u(1)证明:①s附加前提引入②s→p前提引入③p①②假言推理④p→(q→r)前提引入⑤q→r③④假言推理⑥q前提引入⑦r⑤⑥假言推理(2)证明:①P附加前提引入②p∨q①附加③(p∨q)→(r∧s)前提引入④r∧s②③假言推理⑤S④化简⑥s∨t⑤附加⑦(s∨t)→u前提引入⑧u⑥⑦假言推理3.16在自然推理系统P中用归谬法证明下面推理:(1)前提:p→￢q,￢r∨q,r∧￢s结论:￢p(2)前提:p∨q,p→r,q→s结论:r∨s(1)证明:①P结论否定引入②p→￢q前提引入③￢q①②假言推理④￢r∨q前提引入⑤￢r③④析取三段论⑥r∧￢s前提引入⑦r⑥化简规则⑧￢r∧r⑤⑦合取引入规则⑧为矛盾式,由归谬法可知,推理正确.(2)证明:①￢(r∨s)结论否定引入②p∨q前提引入③p→r前提引入④q→s前提引入⑤(p→r)∧(q→s)∧(p∨q)②③④合取引入规则⑥r∨s⑤构造性二难⑦(r∨s)∧￢(r∨s)④⑤合取引入规则⑦为矛盾式,所以推理正确.第8次作业（P65-66）4.5在一阶逻辑中将下列命题符号化:(1)火车都比轮船快.(2)有的火车比有的汽车快.(3)不存在比所有火车都快的汽车.(4)“凡是汽车就比火车慢”是不对的.解：因为没指明个体域,因而使用全总个体域(1)xy(F(x)∧G(y)H(x,y))其中,F(x):x是火车,G(y):y是轮船,H(x,y):x比y快.(2)xy(F(x)∧G(y)∧H(x,y))其中,F(x):x是火车,G(y):y是汽车,H(x,y):x比y快.(3)￢∃x(F(x)∧y(G(y)H(x,y)))或x(F(x)∃y(G(y)∧￢H(x,y)))其中,F(x):x是汽车,G(y):y是火车,H(x,y):x比y快.(4)￢∀x∀y(F(x)∧G(y)H(x,y))或∃x∃y(F(x)∧G(y)∧￢H(x,y))其中,F(x):x是汽车,G(y):y是火车,H(x,y):x比y慢.4.9给定解释I如下:(a)个体域为实数集合R.(b)特定元素a=0.(c)特定函数f(x,y)=xy,x,y∈R.(d)谓词F(x,y):x=y,G(x,y):xy,x,y∈R.给出下列公式在I下的解释,并指出它们的真值:(1)∀x∀y(G(x,y)￢F(x,y))(2)∀x∀y(F(f(x,y),a)G(x,y))(3)∀x∀y(G(x,y)￢F(f(x,y),a))(4)∀x∀y(G(f(x,y),a)F(x,y))解：(1)∀x∀y(xyx≠y),真值为1.(2)∀x∀y((x-y=0)xy)),真值为0.(3)∀x∀y((xy)(xy≠0)),真值为1.(4)∀x∀y((xy0)(x=y)),真值为0.第9次作业（P79-80）5.5给定解释I如下:(a)个体域D={3,4}；(b)f(x)：f(3)=4,f(4)=3；(c)F(x,y)：F(3,3)=F(4,4)=0,F(3,4)=F(4,3)=1.试求下列公式在I