离散数学课后习题答案第二章

1第四章部分课后习题参考答案3.在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:(1)对于任意x,均有2=(x+)(x).(2)存在x,使得x+5=9.其中(a)个体域为自然数集合.(b)个体域为实数集合.解：F(x):2=(x+)(x).G(x):x+5=9.(1)在两个个体域中都解释为)(xxF，在（a）中为假命题，在(b)中为真命题。(2)在两个个体域中都解释为)(xxG，在（a）(b)中均为真命题。4.在一阶逻辑中将下列命题符号化:(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人.解:(1)F(x):x能表示成分数H(x):x是有理数命题符号化为:))()((xHxFx(2)F(x):x是北京卖菜的人H(x):x是外地人命题符号化为:))()((xHxFx5.在一阶逻辑将下列命题符号化:(1)火车都比轮船快.(3)不存在比所有火车都快的汽车.解:(1)F(x):x是火车;G(x):x是轮船;H(x,y):x比y快命题符号化为:)),())()(((yxHyGxFyx(2)(1)F(x):x是火车;G(x):x是汽车;H(x,y):x比y快命题符号化为:))),()(()((yxHxFxyGy9.给定解释I如下:(a)个体域D为实数集合R.2(b)D中特定元素=0.(c)特定函数(x,y)=xy,x,yD.(d)特定谓词(x,y):x=y,(x,y):xy,x,yD.说明下列公式在I下的含义,并指出各公式的真值:(1))),(),((yxFyxGyx(2))),()),,(((yxGayxfFyx答:(1)对于任意两个实数x,y,如果xy,那么xy.真值1.(2)对于任意两个实数x,y,如果x-y=0,那么xy.真值0.10.给定解释I如下：（a）个体域D=N(N为自然数集合).（b）D中特定元素=2.（c）D上函数=x+y,(x,y)=xy.（d）D上谓词(x,y):x=y.说明下列各式在I下的含义，并讨论其真值.(1)xF(g(x,a),x)(2)xy(F(f(x,a),y)→F(f(y,a),x)答:(1)对于任意自然数x,都有2x=x,真值0.(2)对于任意两个自然数x,y,使得如果x+2=y,那么y+2=x.真值0.11.判断下列各式的类型:(1)(3)yF(x,y).解:(1)因为1)()(pqppqp为永真式；所以为永真式；(3)取解释I个体域为全体实数F(x,y)：x+y=5所以,前件为任意实数x存在实数y使x+y=5，前件真；后件为存在实数x对任意实数y都有x+y=5，后件假，]此时为假命题再取解释I个体域为自然数N，F(x,y)：:x+y=5所以,前件为任意自然数x存在自然数y使x+y=5，前件假。此时为假命题。此公式为非永真式的可满足式。313.给定下列各公式一个成真的解释，一个成假的解释。(1)(F(x)(2)x(F(x)G(x)H(x))解:(1)个体域:本班同学F(x)：x会吃饭,G(x)：x会睡觉.成真解释F(x)：x是泰安人,G(x)：x是济南人.（2）成假解释(2)个体域:泰山学院的学生F(x)：x出生在山东,G(x):x出生在北京,H(x):x出生在江苏,成假解释.F(x)：x会吃饭,G(x)：x会睡觉,H(x)：x会呼吸.成真解释.第五章部分课后习题参考答案5.给定解释Ｉ如下:(a)个体域D={3,4};(b))(xf为3)4(,4)3(ff(c)1)3,4()4,3(,0)4,4()3,3(),(FFFFyxF为.试求下列公式在Ｉ下的真值.(1)),(yxyFx(3))))(),((),((yfxfFyxFyx解:(1)))4,()3,((),(xFxFxyxyFx))4,4()3,4(())4,3()3,3((FFFF1)01()10((2))))(),((),((yfxfFyxFyx))))4(),(()4,(()))3(),(()3,(((fxfFxFfxfFxFx)))3),(()4,(())4),(()3,(((xfFxFxfFxFx)))3),3(()4,3(())4),3(()3,3(((fFFfFF)))3),4(()4,4(())4),4(()3,4(((fFFfFF)))3,4()4,3(())4,4(0((FFF)))3,3(0())4,3(1((FF)11()00()00()11(112.求下列各式的前束范式。(1)),()(yxyGxxF4(5))),()((),(2121211xxGxxHxxFx(本题课本上有错误)解:(1)),()(yxyGxxF),()(ytyGxxF)),()((ytGxFyx(5))),()((),(2121211xxGxxHxxFx)),()((),(2323211xxGxxHxxFx)),()((),(2332411xxGxHxxxFx))),()((),((2334121xxGxHxxFxx15.在自然数推理系统F中,构造下面推理的证明:(1)前提:))())()((()(yRyGyFyxxF,)(xxF结论:xR(x)(2)前提:x(F(x)→(G(a)∧R(x))),xF(x)结论:x(F(x)∧R(x))证明(1)①)(xxF前提引入②F(c)①EI③))())()((()(yRyGyFyxxF前提引入④))())()(((yRyGyFy①③假言推理⑤(F(c)∨G(c))→R(c))④UI⑥F(c)∨G(c)②附加⑦R(c)⑤⑥假言推理⑧xR(x)⑦EG(2)①xF(x)前提引入②F(c)①EI③x(F(x)→(G(a)∧R(x)))前提引入④F(c)→(G(a)∧R(c))③UI⑤G(a)∧R(c)②④假言推理⑥R(c)⑤化简⑦F(c)∧R(c)②⑥合取引入⑧x(F(x)∧R(x))⑦EG