离散数学(第二版)课后习题答案详解(完整版)

习题一1.下列句子中，哪些是命题?在是命题的句子中，哪些是简单命题?哪些是真命题?哪些命题的真值现在还不知道?(1)中国有四大发明.答：此命题是简单命题，其真值为1.(2)5/是无理数.答：此命题是简单命题，其真值为1.(3)3是素数或4是素数.答：是命题，但不是简单命题，其真值为1.(5)你去图书馆吗?答：不是命题.(6)2与3是偶数.答：是命题，但不是简单命题，其真值为0.答：此命题是简单命题，其真值还不知道.(8)这朵玫瑰花多美丽呀!答：不是命题.(9)吸烟请到吸烟室去!答：不是命题.(10)圆的面积等于半径的平方乘以π.答：此命题是简单命题，其真值为1.(11)只有6是偶数，3才能是2的倍数.答：是命题，但不是简单命题，其真值为0.(12)8是偶数的充分必要条件是8能被3整除.答：是命题，但不是简单命题，其真值为0.(13)2008年元旦下大雪.答：此命题是简单命题，其真值还不知道.2.将上题中是简单命题的命题符号化.解：(1)p:中国有四大发明.(2)p:V5是无理数.(10)p:圆的面积等于半径的平方乘以π.(13)p:2008年元旦下大雪.(1)5/是有理数.答：否定式：5/是无理数.p:5是有理数.q:5是无理数.其否定式q的真值 (2)85不是无理数. 真值为1.(3)2.5是自然数.答：否定式：2.5不是自然数.p:2.5是自然数.q:2.5不是自然数.其否定式q的真值(4)ln1是整数.答：否定式：In1不是整数.p:ln1是整数.q4.将下列命题符号化，并指出真值.(1)2与5都是素数答：p:2是素数，q:5是素数，符号化为pq^,其真值为1.(2)不但π是无理数，而且自然对数的底e也是无理数.答：p:π是无理数，q:自然对数的底e是无理数，符号化为pqλ,其真值为1.(3)虽然2是最小的素数，但2不是最小的自然数.答：p:2是最小的素数，q:2是最小的自然数，符号化为pq^,其真值为1.(4)3是偶素数.答：p:3是素数，q:3是偶数，符号化为pq^,其真值为0.(5)4既不是素数，也不是偶数.答：p:4是素数，q:4是偶数，符号化为-A-pq,其真值为0.5.将下列命题符号化，并指出真值.(1)2或3是偶数.(2)2或4是偶数.(3)3或5是偶数.(4)3不是偶数或4不是偶数.(5)3不是素数或4不是偶数.(1)小丽只能从筐里拿一个苹果或一个梨.答：p:小丽从筐里拿一个苹果，q:(2)这学期，刘晓月只能选学英语或日语中的一门外语课.设p:王冬生于1971年，q:王冬生于1972Pq00000111101111011)只要2<1,就有3<2(2)如果2<1,则3≥2,(3)只有2<1,才有3≥2,5)除非2<1,否则3<2符号化真值p→q11000p→q1答：根据题意，p为假命题，q为真命题.自然语言真值只要俄罗斯位于南半球，亚洲人口就最多1只要亚洲人口最多，俄罗斯就位于南半球0只要俄罗斯不位于南半球，亚洲人口就最多1只要俄罗斯位于南半球，亚洲人口就不是最多1只要亚洲人口不是最多，俄罗斯就位于南半球1只要俄罗斯不位于南半球，亚洲人口就不是最多0只要亚洲人口不是最多，俄罗斯就不位于南半球110.设p:9是3的倍数，g:英国与土耳其相邻，将下面命题用自然语言表述，并指出真值(2)p→-q:答：根据题意，p为真命题，q为假命题.自然语言真值9是3的倍数当且仅当英语与土耳其相邻09是3的倍数当且仅当英语与土耳其不相邻19不是3的倍数当且仅当英语与土耳其相邻19不是3的倍数当且仅当英语与土耳其不相邻011.将下列命题符号化，并给出各命题的真值：(1)若2+2=4,则地球是静止不动的；(2)若2+2=4,则地球是运动不止的；(4)若地球上没有水，则是无理数.命题1命题2符号化真值p:2+2=4q:地球是静止不动的p→q0p:2+2=4q:地球是静止不动的1p:地球上有树木q:人类能生存1p:地球上有树木q:人类能生存—p→q112.将下列命题符号化，并给出各命题的真值：(1)2+2=4当且仅当3+3=6;(2)2+2=4的充要条件是3+36;(3)2+2丰与3+3=6互为充要条件；(4)若2+2≠4,则3+3≠6,反之亦然.答：设p:2+2=4,q:3+3=6.符号化真值p⇔q100113.将下列命题符号化，并讨论各命题的真值：(1)若今天是星期一，则明天是星期二；(2)只有今天是星期一，明天才是星期二；(4)若今天是星期一，则明天是星期三.答：设p:今天是星期一，g:明天是星期二，r:明天是星期三符号化真值讨论p→q不会出现前句为真，后句为假的情况不会出现前句为真，后句为假的情况p⇔q必然为1若p为真，则真值为0;若p为假，则真值为114.将下列命题符号化：(12)2与4都是素数，这是不对的；(13)“2或4是素数，这是不对的”是不对的.命题1命题2符号化p:刘晓月跑得快q:刘晓月跳得高p:老王是山东人q:老王是河北人 p:天气冷q:我穿羽绒服p→qp:王欢与李乐组成一个小组p:王欢与李乐组成一个小组p:李辛与李末是兄弟p:李辛与李末是兄弟p:王强学过法语q:刘威学过法语pAqp:他吃饭q:他听音乐pAqp:天下大雨q:他乘车上班p→qp:天下大雨q:他乘车上班p:天下大雨q:他乘车上班p:下雪q:路滑r:他迟到了p:2是素数q:4是素数-(p^q)p:2是素数q:4是素数一(-(pVq))15.设p:2+3=5.真值为1,q真值为1,r真值为0.(1)pV(qAr);(3)(-p^-qAr)⇔(pAqA-r);外，只有6能被2整除，6才能被4整除.”-pV-9真值为1.P→9真值为0.可得，p真值为1,q真值为0.所以，小王会唱歌，小李不会跳舞。(2)(→-p)→-qipPqr00010011010101111001101111011111此式为重言式P9001010101111此式为可满足式qr000010100110此式为矛盾式Pq001011101111此式为重言式Pqr00000010010101111001101011011110此式为可满足式P9r00010011010101111001101111011111此式为重言式P9rS00001000100010000111010010101001100011111000010010101011011111001110101110011111此式为可满足式20.求下列公式的成真赋值：Pq一(pVq)→q000110011011101111111101(3)的成真赋值是00,01,10(4)的成真赋值是01,10,1121.求下列各公式的成假赋值：Pqr一(一pAq)V-r00011100111101010101101110011010111011010111111(3)的成假赋值是100,101由此可得：该式无成假赋值。而成真赋值为：000,001,010,011,100,101,110,111(p→(pVq))A((p^q)→p都是重言式。AB000010100111由真值表可得，当且仅当A和B都是重言式时，AAB是重言式。矛盾式的结论吗?为什么?AB000010100111同样由真值表可得，AAB的成假赋值有00,01,10.所以无法得到A和B都是矛盾式。ABAVB000011101111由真值表可得，当且仅当A和B都是矛盾式时，AAB是矛盾式。重言式的结论吗?AB000011101111PqAB001011011000100100110002.公式A和B同题(1),用真值表验证公式A和B适合蕴涵等值式AB→⇔-VABAB→001000011000100111110003.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出答：原式=-AV((pqq))=0是矛盾式.用等值演算法证明下面等值式.(1)p=AVA-(pqpq)()答：答：右式=-VApqr()=(VAVpq)(p=(pV-ʌAV-A(pq))(q(pq))=(pqVA-A)(pq)=(pqVʌ-ʌ)(pq)=(-A-V-AV-VAV-pq)(qpp(成真赋值为00,10,11.所以为矛盾式。答(pqrvʌ→vv=-V^VVV=-A-AVVV())(pqr)(pqr())=(7A-V-VVV=-AV-A=(-A-AV-V-AV-ʌ-VAV-ʌV-pqrr()(pqq(VV-ʌʌV-V((ppqrr)())((ppqqrv-ʌv-ʌ)())=(-A-Av-ʌ-pqr)(pqrʌ-V-AA-VAAVA-AV)(pqr)(pqr)(pqr)000,001,010,011,100,101,110,111.(ppqqrv-^V-^)())=(pqrrʌʌv-v())((ppqqrv-=(pqrʌAV^A-VA-AV-AAV-A-A)(pqr)(pqr)=mmmmmMMM₁VVVV₃7=0A₂λ4(pqqr→ʌ→=-VA-V=-A-V-AVA-VA)()(pq)(qr)(pq)(prqqqr)()()=(-A-AV-v-ʌV-ʌvpqrr())(pqqr())((ppqrv-ʌʌ))=mmmmMMMMoVVV₁37=2V₄VsV₆A-V)r((pq)(pqr))((pq)(pqr))=((-V-AVV=-VVAVVpq)(A6=mmmmmmVVvvv₂3457Ai₂A₃A4AsAAi₂A₃A4AsA6A₇因此为矛盾式.pqr一Apr000100000110110101100111111000101010101100101111010mmmmmmmiVVVVVV234567P9pq→001100010111101011110100rqrʌv=VʌV)()()=MMMoA2A4=MMMM₂A4A5A6pqrp→VV(pgr)00001001001011001011000110(2)由真值表可得无成假赋值，故主析取范式为7,主合取范式为1.MMMoAA12A3=mmmmmiVVVV34579→→=-V-V(pr)pqr=mmmmmmmoVVVvvV₁45(2)A(pq)与-v(pq)答：+V=-A(pq)pq-AV(pqrM)=6(pq→→)rMMM=₀^2A6(qr)))=--V⇔ʌ(pq((qr)))rrpq→ʌ→)())λ=((-vA=vpr)(rpq))A)))A--VAV-V(((qrqr)=+A-AA-((p(qr))p)A-AA=77-V7V(qpqr))((p(2)(pt(qtr))≈(ptq)tr),(pl(qlr))=((plà)lr).l(pq)(qp)qp(2)令p=0,q=0,r=1则pqrtt=01,(pqrtt(1)ptq(2)plq(1)等值关系有自反性：A⇔A(2)等值关系有对称性：若A⇔B,则B⇔A⇔-V⇔(AAAA)()AAAA1若ABBC⇔且⇔⇔→A→A→A→(ABBABCCB)OC⇔24.设A、B为任意的命题公式，证明：-⇔-AB当且仅当AB=答：-→-台V+AV-⇔→A→⇔→AB(ABBA)()(ABBA)()AB.因此-⇔-AB当且仅当AB⇔。(2)若A^C⇔BAC,举例说明A⇔B不一定成立。由(1)、(2)可知，联结词v与^不答：(1)设ApBq=v1,=A0,Cr=v1,则ACv=⇔V=1BC1,但AB=1,=0,二者不等价。(2)设ApBq=v1,=ʌ0,Cr=v0,则ACʌ=⇔A=0BC0,但AB=1,=0,二者不等价。定成立?又若已知AAC⇔BAC,在什么条件下，A⇔B一定成立?解：若C=0;则ACBCV⇔V,AB⇔一定成立。若C=1;则ACBCA⇔A,AB⇔一定成立。某电路中有一个灯泡和三个开关A、B、C。已知在且仅在下述四种情况下灯亮：(b)在联结词完备集{-,A}上构造F。(c)在联结词完备集{-,→,→}上构造F。FsA-A-V-A+AV-AAVʌA-(pqr)(pqr)(pqr)(pqr)(b)FsA-A-V-N-AV-AAVAʌ-(pqr)(pqr)(pqr)(p28.一个排队线路，输入为A、B、C,其输出分别为A、B、c.本线路中，在同一时间只能有一个信号通过，若同时有两个或两个以上信号申请输出时，则按A、B、C的顺序F⇔A-A-VA-^VAA-VAA(pqr)(pqr)(pqr)Fc⇔-AApqr29.在某班班委成员的选举中，已知王小红、李强、丁金生3位同学被选进了班委会.乙说：丁金生为班长，王小红为生活委员.丙说：李强为班长，王小红为学习委员.班委会分工名单公布后发现，甲、乙、丙三人都恰好猜对了一半.问王小红、李强、丁金生各任何职(用等值等演求解)?为真.若p为真，则q为假，那么r为假，则s为真，这样p与s矛盾，因此这种假设行不通.李强、丁金生的职位分别是：学习委员、生活委员、班长.(1)若赵去，钱也去.(2)李、周两人中必有一人去.(3)钱、孙两人中去且仅去一人(5)若周去，则赵、钱也同去.s:派孙去，t:派周去首先以条件(2)为基础，有三种情况：①若周去，李不去，由条件(5)得则赵、钱同去，由条件(3)得那么孙不去，符合5个条件，即pqrstʌλ-A-A.②若李去，周不去，由条件(4)得则孙去，从而由条件(3)得钱不去，而由条件(1)得赵也不去，即→A→AAA-pqrst.③若周、李都去，那么由条件(4)得则孙去，由条件(5)得赵、钱都去，这样孙和钱都去，与条件(3)矛盾，因此这种情况不存在.1.从日常生活或数学中的各种推理中，构造两个满足附加律的推理定律，并将它们符号化。解(1)“若3是素数，则3是素数或5是奇数”。令p:3是素数，q:5是奇数，则该附加该附加律符号化为-p=-pVqc2.从日常生活或数学的各种推理中，构造两个满足化简律的推理定律，并将它们符号化。例解(1)“6能被2和3整除，所以6能被2整除”。令p:6能被2整除，p:6能被2整除，q:6能被3整除，则该化简律符号化为p^q=p。(p→q)A-q=-p。明天是周末,t:小明要去游泳，该构造性二难定律符号化为小明没有去上学或者小明没有去游泳，所以明天不是周一或者明天不是周末”。令p:明天是5.分别写出德摩定律、吸收律所产生的推理定律(每个等值式产生两条推理定律)。解：的摩6.判断下列推理是否正确。先将简单命题符号化，再写出前提、结论、推理的形式结构(以蕴涵式的形式给出)和判断过程(至少给出两种判断方法):(1)若今天是星期一，则明天是星期三。今天是星期一，所以明天是星期三。(2)若今天是星期一，则明天是星期二。明天是星期二，所以今天是星期一。(3)若今天是星期一，则明天是星期三。明天不是星期三，所以今天不是星期一。(4)若今天是星期一，则明天是星期二。今天不是星期一，所以明天不是星期二。(5)若今天是星期一，则明天是星期二或星期三。(6)今天是星期一当且仅当明天是星期三。今天不是星期一，所以明天不是星期三。②p。等值演算法：,可见该式不是重言式，所以推理不正确。⇔M₁⇔mo,从而可知不是重言式，故推理不正确。③设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)A-q→-p,判断该推理是否正确，即判断(p-4)A-q→-p是否为重言式，不难看出，该式满足拒取式定律，所以推理正确。④设p:今天是星期一，q:明天是星期二，推理的形式结构为pʌ-p)v(qʌ-p))→-q,可见该式不是重言式，所以推理不正确。(-pvg)ʌ-p→-q⇔主析取范式法：,从而可知不是重言式，故推理不正确。⇔M₄⇔moVmiVmzVm₃Vm4VmsVm6Vmr,由此可知p→(qVs)不为故推理不正确。显然该式不是重言式，所以推理不正确。⑥设p:今天是星期一，r:明天是星期三，推理的形式结构为(p→r)A-p→-r。-(-pvr)v-(-rvp)VpV-r,由此可知不为重言式，故推理不正确。(2)前提：(p^q)→r,-r,q(3)前提：p→(q→r),p,q解(1)结论1:p→r为有效的(假言三段论)结论2:p为无效的。是有效的(拒取式)结论2:p是无效的是有效的(假言三段论)结论2:r是无效的(1)只有天气热，我才去游泳。我正在游泳，所以……结论1:p,有效结论(假言推理)结论2:-p,无效结论结论1:-p,有效结论(拒取式)结论2:p,无效结论结论1:-r,有效结论(拒取式)结论2:r,无效结论。*011111011010111011110由真值表可知(*)为重言式，故推理是正确的。(-pvg)v(-qv-)。-pv(qv-q)v-r①p→-q前提引入①置换前提引入论主析取范式法由方法2可以得知推理的形式结构(*)的主析取范式为(*)⇔moVmiVmzVm₃Vm₄VmsVm6Vmr,则(*)为重言式，推理正确。10.用两种方法(真值表法，主析取范式法)证明下面推理不正确：如果a,b两数之积是负数，则a,b之中恰有一个是负数。a,b两数之积不是负数，所以a,b中一A-qrA0111001000100001110111010001推理不正确⇔-VA+V+AA-→-A-(pqr()(qr)p(qr由于主析取范式只含有5个极小项，所以(3.8)不是重言式，推理不正确。②-pVq④-qVr⑦s析取三段论析取三段论附加前提引入化简规则化简规则⑤q→r前提引入③⑤假言推理前提引入⑧r→s③⑦假言推理⑥⑧假言推理结论1:r结论2:s结论3:rVs(1)证明从此前提出发，推出结论1,结论2,结论3的推理都是正确的。(2)证明从此前提出发，推任何结论的推理都是正确的。(1)证明：结论1:((-→AAVA→→pqq))(pqrs)()r⇔^V^→→0(pgrs)()r结论2:((-→AAVA→→pqq))(pqrs)()s⇔AV^→→0(pgrs)()s结论3:⇔AVʌ→→v0(pgrs)()rs⇔A-AAv^→→(pqg)(pgrs)()水水⇔^V^→→0(pgrs)()水pAq(1)p→→(qr)(1)(2)假言推理(5)pq→(3)(-VA-Vpq)(4)-vʌpqp()(5)p→ʌ(pq)(4)证明(3)tr→(7)qs-(5)证明(6)证明前提引入(1)置换前提引入论前提引入(4)(5)拒取式前提引入(1)置换(pp)(2)置换(3)置换(4)置换()前提引入(1)置换(2)换件前提引入(4)化简(3)(5)假言推理前提引入(8)化简(6)(9)假言推理前提引入(10)(11)假言推理(10)(12)合取前提引入(1)化简(1)化简前提引入(2)(4)假言推理前提引入(3)(6)假言推理(5)(7)合取前提引入(1)化简(1)化简前提引入(2)(4)析取三段论(3)(6)析取三段论(5)(7)合取ʌtrs()(8)附加(9)置换(1)前提：p→(q→r),s→p,q(2)前提：(pvq)→(rʌs),(svt)→u(2)sp→(2)pqV附加前提引入(1)(2)假言推理(3)(4)假言推理(5)(6)假言推理(1)附加(4)rsA(2)(3)假言推理(5)s(4)化简(6)stV(5)附加(8)u(6)(7)假言推理结论否定引入前提引入(2)(1)假言推理(1)设论(6)rA-s(7)r(6)化简(8)-Arr(5)(7)合取(1)-v(rs)结论否定引入(2)-A-rs(1)置换(3)-r(2)化简(4)-s(2)化简(6)-p(3)(5)拒取式(8)-q(4)(7)拒取式(9)-A-pq(9)置换17.在自然系统p中构造下面推理的证明：只要A曾到过受害者房间并且11点前没离开，A就犯了谋杀罪。A曾到过受害者房间，如果A在11点以前离开，看门人会看见他。看门人没有看见他，所以A犯了谋杀罪。设p:A到过受害者房间q:A在11点前离开r:A是谋杀嫌疑犯I证明qS→前提引入前提引入7q(2)(1)拒取式p前提引入pqʌ-(3)(4)合取前提引入r(5)(6)假言推理18.在自然系统p中构造下面各推理的证明：(1)如果今天是星期六，我们就要去颐和园或圆明园玩。如果颐和园游人太多，我们就不去颐和园玩。今天是星期六，颐和园游人太多，所以我们去圆明园玩。(2)如果小王是理科学生，则他的数学成绩一定很好。如果小王不是文科生，则他一定是理科生。小王的数学成绩不好，所以小王是文科学生。p:今天是星期六q:我们到颐和园玩多p:小王是理科学生q:小王数学成绩好r:小王是文科学生(4)-→rp前提引入(1)(2)假言推理(4)(5)假言推理论(1)(2)拒取式习题四1.将下列命题0元谓词符号化：(1)小王学习过英语和法语。(2)除非李建是东北人，否则他一定怕冷。(3)2大于3仅当2大于4.(4)3不是偶数。(5)2或3是素数。解(1)设一元谓词Fx():小王学习过x。a:英语，b:法语。(1)中命题符号化为0元谓Fa()。设二元谓词Gxy(,):x设一元谓词Fx():x大于y;abc:2,:3,:4.符号化为：不是偶数。a:3。命题符号化为0元谓词的蕴含式：是素数。a:2,b:3.符号化为FaFb()v()。2.在一阶逻辑中将下面命题符号化，并分别讨论个体域限制为(a),(b)条件时命题的真值：(1)凡有理数都能被2整除。(2)有的有理数都能被2整除。其中(a)个体域为有理数集合。(b)个体域为实数集合。(a)(1)VxFx(),真值为0,(2)3xFx()真值为1.(b)(1)VxGxFx(()→())真值为0,(2)3xGxFx(()λ()),真值为1.3.在一阶逻辑中将下列命题符号化，并分别讨论个体域限制为(a)(b)条件时的命题的真值：(a)(1)VxFx(),真值为0,(2)3xGx()真值为1.(b)(1)VxFx(),真值为1,(2)3xGx()真值为1.4.在一阶逻辑中将下列命题符号化：(2)在北京卖菜的人不全是外地人。(3)乌鸦都是黑色的。(4)有的人天天锻炼身体。解：(1)-3xFx(()A-Gx())成分数(3)VxFxGx(()→()),说凡是汽车就比火车慢是不对的。解：(3)-3xGx(()^VyFy(()→Hxy(,)),(4)-VxGx(()→VyFy(()→Hxy(,)),在y,使得xy*=0。(2)存在着x,对所有y都有xy*=0。(3)对所有的x,都存在y,使得yx=+1。(4)对所有的x和y,都有yxxy*=*。(5)对任意的x和y,都有yxxy*=+。(6)对任意的x,存在y,使得xy²+<²0。(3)√3=+xyyx(1),(4)√Vxyyxxy(*=*),(5)√Vxyyxxy(*=+),(6)V3xyxy(²+<²0)。(1)√V3-=xyzxy=1)(3)3√√+=x(2)VxFxy(,)→3yGxy(,)(3)V3xyFxyGyz((,)λ(,))v3xHxyz(,,)D(1).VVxyGxy((,)→-Fxy(,))(3)VVxyGxy((,)→-Ffxya((,),))(4)VVxyGfxyaFxy(((,),)→(,))其中(1)(3)真值为1,(2)(4)真值为0。(c)D上函数fxyxygxyxy(,)=+,(,)=*.说明下列各式在I的含义，并讨论其真值：(3)√V3xyzFfxyz((,)(4)3xFfxxgxx((,),(,)).其中(1)(2)真值为0,(3)(4)真值为1。11.判断下列各式的类型：(1).Fxy(,)→((GxyFxy,)→(,))(2)VxFx(()→Fx())→3yGy(()A-Gy()).(3)√3xyFxy(,)→3VxyFxy(,).3xyFxy(,).(5)VVxyFxy((,)→Fyz(,)).(6)-V(xFx()→3yGy())^3yGy().12.设I为一个任意的解释，在解释I下，下面哪些公式一定是命题?(1).VxFxy(,)→3yGxy(,).(2)VxFxGx(()→())ʌ3yFyHy(()A())..(3)√VxyFxy((,)→3yGxy(,)).(4)VxFxGxHy(()A()λ())(2)(3)一定是命题，因为他们是闭式。3xFx(()AVyGyHx():能被5整除。则存在30能被，2,3,5整除。成假的情况是：Fx():x是偶数，Gx既是偶数又是素数同时还能被5整除。Fx():x是偶数，Gyy():能被2整除，Hxyxy(,):比小。则对偶数2,(1).VxFx(()→3yGyHxy(()A(,)))(2)√VxyFxGy(()ʌ()→Hxy(,)))解：(1),成真的情况是：Fx():x是正偶数，G整除且xy≠。则对任意一个正偶数x,都存在2,整除x。y≠。则对任意一个正数x(比如3),不一定存在不等于x的整数，整除x。能被6整除.成15.(1)给出一个非闭式的永真式。(2)给出一个非闭式的永假式。(3)给出一个非闭式(1)(FxGxFxGx()→())λ()→(),它是重言式(ABAB→A→)的代(2)-(Fx()→Fx()),它是矛盾式-→(AA)的代换实例。1.设个体域D={a,b,c},在D中消去公式VxFx(()A3yGy())的量词。甲、乙用了不同VxFx(()^3yGy())VxFx(()A3yGy())(FaFbFc()A()^())A(Ga显然，乙的演算过程简单，试指出乙在推演过程中的关键步骤。答：乙在演算中的关键步骤是，开始利用量词辖域收缩与扩张等值式，将量词的辖域缩小，从而简化了演算。2.设个体域D={a,b,c},消去下列各式的量词：(2)VVxyFxGy(()v())(3)VxFx()→VyGy()(4)VxFxy((,)→3yGy())答：1)(()FaFbFcʌ()ʌ())A(()GaGbGcv()v())FbFc()ʌ()ʌ())ʌ(GaGbGc()ʌ()ʌ())FbFcʌ()λ())→(()Ga4)(FayFbyFcy(,)v(,)v(,))→(GaGbGc()v()v())(1)VxFx(()→Gx())a)在解释I1中，个体域D1={a},证明公式A在I1下的真值为1。b)在解释I2中，个体域D2={al,a2,…,an},n≥2,A在I2下的真值还一定是1吗?为什么?答：1.在I1下，3xFx()→VxFx()⇔FaFa()→()⇔-FaFa()v()⇔1在I2下，3xFx()→VxFx()⇔(FaFa(1)v(2)…vFan())→(FaFa(1)ʌ(2)……^Fan(故蕴含式真值为0。若将F(x)改为真值为1。问题的关键是n≥2,n项的析取为真，只需要其中的一项为真，而不能保证所有的项为真。5.给定解释I如下：(a)个体域D={3,4};(1)V3xyFxy(,)(2)3VxyFxy(,)(3)VVxyFxyFfxfy((,)→((),()))答：(1)V3xyFxy(,)⇔VxFx((,3)vFx(,4))⇔(F(3,3)vF(3,4))ʌ(F(4,3)vF(4,4))⇔A⇔1113VxyFxy(,)⇔3xFx((,3)ʌFx(,4))⇔(F(3,3)AF(3,4))v(F(4,3)ʌF(4,4))⇔ʌ⇔000VVxyFxy((,)→Ffxfy((),()))⇔VxFx(((,3)→Ffxf(),(3)))A(Fx(,4)→Ffxf(),(4))))6.甲使用量词辖域收缩与扩张等值式进行如下演算：VxFx(()→Gxy(,))⇔3xFx()→Gxy(,)乙说甲错了，乙说的对吗?为什么?答：乙说的对，甲错了。本题中，全称量词V的指导变元为x,辖域为FxGxy()→(,),其中F(x)与G(x,y)中的x都是约束变元，因而不能将量词的辖域缩小。7.请指出下面等值演算中的两处错误。答：演算的第一步，应用量词否定等值式时丢掉了否定连接词“-”,演算的第二步，在原(FxGy()ʌ(()→Hxy(,)))错的基础上又用错了等值式即，8.在一阶逻辑中将下面命题符号化，要求用两种不同的等值形式。(1)没有小于负数的正数(2)相等的(1).3xFxGx(()A())VxGx(()→-Fx()),-VxFxGx(()→()⇔3xFx(()A-Gx()),两个角是对顶角可是某人却说这是真命题，其理由如下：设F(x):x是有理数，G(x):x是无理数。3xFx()与3xGx()都是真命题，于是，3xFx()A3xGx()⇔xFxGx(()A()),由于3xFxxGx()ʌ3()是真命题，故3xFxGx(()ʌ())也是真命题，即有的实数是有理数，也是无理数，问此人的结论对吗?为什么?10.在求前束范式时，有人说-3xFxGxy(()A(,))已是前束范式，理由是量词已在公式的前面。他说的对吗?为什么?答：前束范式中，否定连联接词不能在量词前面出现。VxFxGx(()→())→3xGxy(,)的前束范式，因为公式中的两个量词的指导变元相同。他的理由正确吗?为什么?答：用换名规则可使两个指导规则不同。(2)√xFxy((,)→3yGxyz(,,))(4)VxFxGxx₁((i)→(1,2))→3(xHx₂(₂)→3xLxx₃(2,(4)3V3yyyFyGyx₁23(((i)→(1,2))→(HyLxy(₂)→(2,3)))(5)VVyyFyx₁2((1,2)→(Fx(i)→-Gxy(i,2)))33xyFxGyHxy(()ʌ()λ(,))yFxGy(()ʌ(()→Hxy(,)))VVxyFxGy(()ʌ()→-Hxy(,))、o23xFxGx(()→())o₁EG规则o23xFxGx(()A()o₁EG规则o₂VxFxGx(()→())V3xyFxGy(()→()),(3)在自然推理系统F中，EG规则为,其中c为特定的个体常项，这里(4)这里使F(a)为真的a不一定使G(a)为真，同样地使G(b)为真的b不一定使F(b)为真，如的个体。VxHx(()→→Fx()VxFx(()→(()GaRx^())),3xFx()o₂3xFx()→VyFyGy((()v())→Ry(o₅(FcGc()v())o₇FcRc()ʌ()o2V-xFx()