离散数学作业布置第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)∧﹁qp∧(q∧﹁q)p∧00所以公式类型为矛盾式(2)(p→(p∨q))∨(p→r)(﹁p∨(p∨q))∨(﹁p∨r)﹁p∨p∨q∨r1所以公式类型为永真式(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∧qm0∨m2∨m2∨m3m0∨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∧rp∧q∧r∨¬p∧q∧r∨p∧q∧rm3∨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)∧rm0∨m1∨m2∨m3∨m4∨m5∨m6∨m7,为重言式.(4)¬(p→q)∧q∧r¬(¬p∨q)∧q∧r(p∧¬q)∧q∧rp∧(¬q∧q)∧r0主析取范式为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)∧¬pq∧p∧¬pq∧00M0∧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∨rM4,成假赋值为100.(3)(p→(p∨q))∨r(¬p∨(p∨q))∨r(¬p∨p)∨q∨r1主合取范式为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)∧pr所以推理正确.(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)xy(F(x)∧G(y)H(x,y))其中,F(x):x是火车,G(y):y是轮船,H(x,y):x比y快.(2)xy(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)=xy,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(xyx≠y),真值为1.(2)∀x∀y((x-y=0)xy)),真值为0.(3)∀x∀y((xy)(xy≠0)),真值为1.(4)∀x∀y((xy0)(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