離散數(shù)學(xué)(第二版)課后習(xí)題答案詳解(完整版)

習(xí)題一1.下列句子中，哪些是命題?在是命題的句子中，哪些是簡單命題?哪些是真命題?哪些命題的真值現(xiàn)在還不知道?(1)中國有四大發(fā)明.答：此命題是簡單命題，其真值為1.(2)5/是無理數(shù).答：此命題是簡單命題，其真值為1.(3)3是素數(shù)或4是素數(shù).答：是命題，但不是簡單命題，其真值為1.(5)你去圖書館嗎?答：不是命題.(6)2與3是偶數(shù).答：是命題，但不是簡單命題，其真值為0.答：此命題是簡單命題，其真值還不知道.(8)這朵玫瑰花多美麗呀!答：不是命題.(9)吸煙請到吸煙室去!答：不是命題.(10)圓的面積等于半徑的平方乘以π.答：此命題是簡單命題，其真值為1.(11)只有6是偶數(shù)，3才能是2的倍數(shù).答：是命題，但不是簡單命題，其真值為0.(12)8是偶數(shù)的充分必要條件是8能被3整除.答：是命題，但不是簡單命題，其真值為0.(13)2008年元旦下大雪.答：此命題是簡單命題，其真值還不知道.2.將上題中是簡單命題的命題符號化.解：(1)p:中國有四大發(fā)明.(2)p:V5是無理數(shù).(10)p:圓的面積等于半徑的平方乘以π.(13)p:2008年元旦下大雪.(1)5/是有理數(shù).答：否定式：5/是無理數(shù).p:5是有理數(shù).q:5是無理數(shù).其否定式q的真值 (2)85不是無理數(shù). 真值為1.(3)2.5是自然數(shù).答：否定式：2.5不是自然數(shù).p:2.5是自然數(shù).q:2.5不是自然數(shù).其否定式q的真值(4)ln1是整數(shù).答：否定式：In1不是整數(shù).p:ln1是整數(shù).q4.將下列命題符號化，并指出真值.(1)2與5都是素數(shù)答：p:2是素數(shù)，q:5是素數(shù)，符號化為pq^,其真值為1.(2)不但π是無理數(shù)，而且自然對數(shù)的底e也是無理數(shù).答：p:π是無理數(shù)，q:自然對數(shù)的底e是無理數(shù)，符號化為pqλ,其真值為1.(3)雖然2是最小的素數(shù)，但2不是最小的自然數(shù).答：p:2是最小的素數(shù)，q:2是最小的自然數(shù)，符號化為pq^,其真值為1.(4)3是偶素數(shù).答：p:3是素數(shù)，q:3是偶數(shù)，符號化為pq^,其真值為0.(5)4既不是素數(shù)，也不是偶數(shù).答：p:4是素數(shù)，q:4是偶數(shù)，符號化為-A-pq,其真值為0.5.將下列命題符號化，并指出真值.(1)2或3是偶數(shù).(2)2或4是偶數(shù).(3)3或5是偶數(shù).(4)3不是偶數(shù)或4不是偶數(shù).(5)3不是素數(shù)或4不是偶數(shù).(1)小麗只能從筐里拿一個蘋果或一個梨.答：p:小麗從筐里拿一個蘋果，q:(2)這學(xué)期，劉曉月只能選學(xué)英語或日語中的一門外語課.設(shè)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答：根據(jù)題意，p為假命題，q為真命題.自然語言真值只要俄羅斯位于南半球，亞洲人口就最多1只要亞洲人口最多，俄羅斯就位于南半球0只要俄羅斯不位于南半球，亞洲人口就最多1只要俄羅斯位于南半球，亞洲人口就不是最多1只要亞洲人口不是最多，俄羅斯就位于南半球1只要俄羅斯不位于南半球，亞洲人口就不是最多0只要亞洲人口不是最多，俄羅斯就不位于南半球110.設(shè)p:9是3的倍數(shù)，g:英國與土耳其相鄰，將下面命題用自然語言表述，并指出真值(2)p→-q:答：根據(jù)題意，p為真命題，q為假命題.自然語言真值9是3的倍數(shù)當(dāng)且僅當(dāng)英語與土耳其相鄰09是3的倍數(shù)當(dāng)且僅當(dāng)英語與土耳其不相鄰19不是3的倍數(shù)當(dāng)且僅當(dāng)英語與土耳其相鄰19不是3的倍數(shù)當(dāng)且僅當(dāng)英語與土耳其不相鄰011.將下列命題符號化，并給出各命題的真值：(1)若2+2=4,則地球是靜止不動的；(2)若2+2=4,則地球是運動不止的；(4)若地球上沒有水，則是無理數(shù).命題1命題2符號化真值p:2+2=4q:地球是靜止不動的p→q0p:2+2=4q:地球是靜止不動的1p:地球上有樹木q:人類能生存1p:地球上有樹木q:人類能生存—p→q112.將下列命題符號化，并給出各命題的真值：(1)2+2=4當(dāng)且僅當(dāng)3+3=6;(2)2+2=4的充要條件是3+36;(3)2+2豐與3+3=6互為充要條件；(4)若2+2≠4,則3+3≠6,反之亦然.答：設(shè)p:2+2=4,q:3+3=6.符號化真值p?q100113.將下列命題符號化，并討論各命題的真值：(1)若今天是星期一，則明天是星期二；(2)只有今天是星期一，明天才是星期二；(4)若今天是星期一，則明天是星期三.答：設(shè)p:今天是星期一，g:明天是星期二，r:明天是星期三符號化真值討論p→q不會出現(xiàn)前句為真，后句為假的情況不會出現(xiàn)前句為真，后句為假的情況p?q必然為1若p為真，則真值為0;若p為假，則真值為114.將下列命題符號化：(12)2與4都是素數(shù)，這是不對的；(13)“2或4是素數(shù)，這是不對的”是不對的.命題1命題2符號化p:劉曉月跑得快q:劉曉月跳得高p:老王是山東人q:老王是河北人 p:天氣冷q:我穿羽絨服p→qp:王歡與李樂組成一個小組p:王歡與李樂組成一個小組p:李辛與李末是兄弟p:李辛與李末是兄弟p:王強(qiáng)學(xué)過法語q:劉威學(xué)過法語pAqp:他吃飯q:他聽音樂pAqp:天下大雨q:他乘車上班p→qp:天下大雨q:他乘車上班p:天下大雨q:他乘車上班p:下雪q:路滑r:他遲到了p:2是素數(shù)q:4是素數(shù)-(p^q)p:2是素數(shù)q:4是素數(shù)一(-(pVq))15.設(shè)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由真值表可得，當(dāng)且僅當(dāng)A和B都是重言式時，AAB是重言式。矛盾式的結(jié)論嗎?為什么?AB000010100111同樣由真值表可得，AAB的成假賦值有00,01,10.所以無法得到A和B都是矛盾式。ABAVB000011101111由真值表可得，當(dāng)且僅當(dāng)A和B都是矛盾式時，AAB是矛盾式。重言式的結(jié)論嗎?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)等值關(guān)系有自反性：A?A(2)等值關(guān)系有對稱性：若A?B,則B?A?-V?(AAAA)()AAAA1若ABBC?且??→A→A→A→(ABBABCCB)OC?24.設(shè)A、B為任意的命題公式，證明：-?-AB當(dāng)且僅當(dāng)AB=答：-→-臺V+AV-?→A→?→AB(ABBA)()(ABBA)()AB.因此-?-AB當(dāng)且僅當(dāng)AB?。(2)若A^C?BAC,舉例說明A?B不一定成立。由(1)、(2)可知，聯(lián)結(jié)詞v與^不答：(1)設(shè)ApBq=v1,=A0,Cr=v1,則ACv=?V=1BC1,但AB=1,=0,二者不等價。(2)設(shè)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?一定成立。某電路中有一個燈泡和三個開關(guān)A、B、C。已知在且僅在下述四種情況下燈亮：(b)在聯(lián)結(jié)詞完備集{-,A}上構(gòu)造F。(c)在聯(lián)結(jié)詞完備集{-,→,→}上構(gòu)造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.在某班班委成員的選舉中，已知王小紅、李強(qiáng)、丁金生3位同學(xué)被選進(jìn)了班委會.乙說：丁金生為班長，王小紅為生活委員.丙說：李強(qiáng)為班長，王小紅為學(xué)習(xí)委員.班委會分工名單公布后發(fā)現(xiàn)，甲、乙、丙三人都恰好猜對了一半.問王小紅、李強(qiáng)、丁金生各任何職(用等值等演求解)?為真.若p為真，則q為假，那么r為假，則s為真，這樣p與s矛盾，因此這種假設(shè)行不通.李強(qiáng)、丁金生的職位分別是：學(xué)習(xí)委員、生活委員、班長.(1)若趙去，錢也去.(2)李、周兩人中必有一人去.(3)錢、孫兩人中去且僅去一人(5)若周去，則趙、錢也同去.s:派孫去，t:派周去首先以條件(2)為基礎(chǔ)，有三種情況：①若周去，李不去，由條件(5)得則趙、錢同去，由條件(3)得那么孫不去，符合5個條件，即pqrst?λ-A-A.②若李去，周不去，由條件(4)得則孫去，從而由條件(3)得錢不去，而由條件(1)得趙也不去，即→A→AAA-pqrst.③若周、李都去，那么由條件(4)得則孫去，由條件(5)得趙、錢都去，這樣孫和錢都去，與條件(3)矛盾，因此這種情況不存在.1.從日常生活或數(shù)學(xué)中的各種推理中，構(gòu)造兩個滿足附加律的推理定律，并將它們符號化。解(1)“若3是素數(shù)，則3是素數(shù)或5是奇數(shù)”。令p:3是素數(shù)，q:5是奇數(shù)，則該附加該附加律符號化為-p=-pVqc2.從日常生活或數(shù)學(xué)的各種推理中，構(gòu)造兩個滿足化簡律的推理定律，并將它們符號化。例解(1)“6能被2和3整除，所以6能被2整除”。令p:6能被2整除，p:6能被2整除，q:6能被3整除，則該化簡律符號化為p^q=p。(p→q)A-q=-p。明天是周末,t:小明要去游泳，該構(gòu)造性二難定律符號化為小明沒有去上學(xué)或者小明沒有去游泳，所以明天不是周一或者明天不是周末”。令p:明天是5.分別寫出德摩定律、吸收律所產(chǎn)生的推理定律(每個等值式產(chǎn)生兩條推理定律)。解：的摩6.判斷下列推理是否正確。先將簡單命題符號化，再寫出前提、結(jié)論、推理的形式結(jié)構(gòu)(以蘊涵式的形式給出)和判斷過程(至少給出兩種判斷方法):(1)若今天是星期一，則明天是星期三。今天是星期一，所以明天是星期三。(2)若今天是星期一，則明天是星期二。明天是星期二，所以今天是星期一。(3)若今天是星期一，則明天是星期三。明天不是星期三，所以今天不是星期一。(4)若今天是星期一，則明天是星期二。今天不是星期一，所以明天不是星期二。(5)若今天是星期一，則明天是星期二或星期三。(6)今天是星期一當(dāng)且僅當(dāng)明天是星期三。今天不是星期一，所以明天不是星期三。②p。等值演算法：,可見該式不是重言式，所以推理不正確。?M??mo,從而可知不是重言式，故推理不正確。③設(shè)p:今天是星期一，q:明天是星期三，推理的形式結(jié)構(gòu)為(p→q)A-q→-p,判斷該推理是否正確，即判斷(p-4)A-q→-p是否為重言式，不難看出，該式滿足拒取式定律，所以推理正確。④設(shè)p:今天是星期一，q:明天是星期二，推理的形式結(jié)構(gòu)為p?-p)v(q?-p))→-q,可見該式不是重言式，所以推理不正確。(-pvg)?-p→-q?主析取范式法：,從而可知不是重言式，故推理不正確。?M??moVmiVmzVm?Vm4VmsVm6Vmr,由此可知p→(qVs)不為故推理不正確。顯然該式不是重言式，所以推理不正確。⑥設(shè)p:今天是星期一，r:明天是星期三，推理的形式結(jié)構(gòu)為(p→r)A-p→-r。-(-pvr)v-(-rvp)VpV-r,由此可知不為重言式，故推理不正確。(2)前提：(p^q)→r,-r,q(3)前提：p→(q→r),p,q解(1)結(jié)論1:p→r為有效的(假言三段論)結(jié)論2:p為無效的。是有效的(拒取式)結(jié)論2:p是無效的是有效的(假言三段論)結(jié)論2:r是無效的(1)只有天氣熱，我才去游泳。我正在游泳，所以……結(jié)論1:p,有效結(jié)論(假言推理)結(jié)論2:-p,無效結(jié)論結(jié)論1:-p,有效結(jié)論(拒取式)結(jié)論2:p,無效結(jié)論結(jié)論1:-r,有效結(jié)論(拒取式)結(jié)論2:r,無效結(jié)論。*011111011010111011110由真值表可知(*)為重言式，故推理是正確的。(-pvg)v(-qv-)。-pv(qv-q)v-r①p→-q前提引入①置換前提引入論主析取范式法由方法2可以得知推理的形式結(jié)構(gòu)(*)的主析取范式為(*)?moVmiVmzVm?Vm?VmsVm6Vmr,則(*)為重言式，推理正確。10.用兩種方法(真值表法，主析取范式法)證明下面推理不正確：如果a,b兩數(shù)之積是負(fù)數(shù)，則a,b之中恰有一個是負(fù)數(shù)。a,b兩數(shù)之積不是負(fù)數(shù)，所以a,b中一A-qrA0111001000100001110111010001推理不正確?-VA+V+AA-→-A-(pqr()(qr)p(qr由于主析取范式只含有5個極小項，所以(3.8)不是重言式，推理不正確。②-pVq④-qVr⑦s析取三段論析取三段論附加前提引入化簡規(guī)則化簡規(guī)則⑤q→r前提引入③⑤假言推理前提引入⑧r→s③⑦假言推理⑥⑧假言推理結(jié)論1:r結(jié)論2:s結(jié)論3:rVs(1)證明從此前提出發(fā)，推出結(jié)論1,結(jié)論2,結(jié)論3的推理都是正確的。(2)證明從此前提出發(fā)，推任何結(jié)論的推理都是正確的。(1)證明：結(jié)論1:((-→AAVA→→pqq))(pqrs)()r?^V^→→0(pgrs)()r結(jié)論2:((-→AAVA→→pqq))(pqrs)()s?AV^→→0(pgrs)()s結(jié)論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)假言推理結(jié)論否定引入前提引入(2)(1)假言推理(1)設(shè)論(6)rA-s(7)r(6)化簡(8)-Arr(5)(7)合取(1)-v(rs)結(jié)論否定引入(2)-A-rs(1)置換(3)-r(2)化簡(4)-s(2)化簡(6)-p(3)(5)拒取式(8)-q(4)(7)拒取式(9)-A-pq(9)置換17.在自然系統(tǒng)p中構(gòu)造下面推理的證明：只要A曾到過受害者房間并且11點前沒離開，A就犯了謀殺罪。A曾到過受害者房間，如果A在11點以前離開，看門人會看見他。看門人沒有看見他，所以A犯了謀殺罪。設(shè)p:A到過受害者房間q:A在11點前離開r:A是謀殺嫌疑犯I證明qS→前提引入前提引入7q(2)(1)拒取式p前提引入pq?-(3)(4)合取前提引入r(5)(6)假言推理18.在自然系統(tǒng)p中構(gòu)造下面各推理的證明：(1)如果今天是星期六，我們就要去頤和園或圓明園玩。如果頤和園游人太多，我們就不去頤和園玩。今天是星期六，頤和園游人太多，所以我們?nèi)A明園玩。(2)如果小王是理科學(xué)生，則他的數(shù)學(xué)成績一定很好。如果小王不是文科生，則他一定是理科生。小王的數(shù)學(xué)成績不好，所以小王是文科學(xué)生。p:今天是星期六q:我們到頤和園玩多p:小王是理科學(xué)生q:小王數(shù)學(xué)成績好r:小王是文科學(xué)生(4)-→rp前提引入(1)(2)假言推理(4)(5)假言推理論(1)(2)拒取式習(xí)題四1.將下列命題0元謂詞符號化：(1)小王學(xué)習(xí)過英語和法語。(2)除非李建是東北人，否則他一定怕冷。(3)2大于3僅當(dāng)2大于4.(4)3不是偶數(shù)。(5)2或3是素數(shù)。解(1)設(shè)一元謂詞Fx():小王學(xué)習(xí)過x。a:英語，b:法語。(1)中命題符號化為0元謂Fa()。設(shè)二元謂詞Gxy(,):x設(shè)一元謂詞Fx():x大于y;abc:2,:3,:4.符號化為：不是偶數(shù)。a:3。命題符號化為0元謂詞的蘊含式：是素數(shù)。a:2,b:3.符號化為FaFb()v()。2.在一階邏輯中將下面命題符號化，并分別討論個體域限制為(a),(b)條件時命題的真值：(1)凡有理數(shù)都能被2整除。(2)有的有理數(shù)都能被2整除。其中(a)個體域為有理數(shù)集合。(b)個體域為實數(shù)集合。(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())成分?jǐn)?shù)(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,使得xy2+<20。(3)√3=+xyyx(1),(4)√Vxyyxxy(*=*),(5)√Vxyyxxy(*=+),(6)V3xyxy(2+<20)。(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上函數(shù)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.設(shè)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是偶數(shù)，Gx既是偶數(shù)又是素數(shù)同時還能被5整除。Fx():x是偶數(shù)，Gyy():能被2整除，Hxyxy(,):比小。則對偶數(shù)2,(1).VxFx(()→3yGyHxy(()A(,)))(2)√VxyFxGy(()?()→Hxy(,)))解：(1),成真的情況是：Fx():x是正偶數(shù)，G整除且xy≠。則對任意一個正偶數(shù)x,都存在2,整除x。y≠。則對任意一個正數(shù)x(比如3),不一定存在不等于x的整數(shù)，整除x。能被6整除.成15.(1)給出一個非閉式的永真式。(2)給出一個非閉式的永假式。(3)給出一個非閉式(1)(FxGxFxGx()→())λ()→(),它是重言式(ABAB→A→)的代(2)-(Fx()→Fx()),它是矛盾式-→(AA)的代換實例。1.設(shè)個體域D={a,b,c},在D中消去公式VxFx(()A3yGy())的量詞。甲、乙用了不同VxFx(()^3yGy())VxFx(()A3yGy())(FaFbFc()A()^())A(Ga顯然，乙的演算過程簡單，試指出乙在推演過程中的關(guān)鍵步驟。答：乙在演算中的關(guān)鍵步驟是，開始利用量詞轄域收縮與擴(kuò)張等值式，將量詞的轄域縮小，從而簡化了演算。2.設(shè)個體域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。問題的關(guān)鍵是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.甲使用量詞轄域收縮與擴(kuò)張等值式進(jìn)行如下演算：VxFx(()→Gxy(,))?3xFx()→Gxy(,)乙說甲錯了，乙說的對嗎?為什么?答：乙說的對，甲錯了。本題中，全稱量詞V的指導(dǎo)變元為x,轄域為FxGxy()→(,),其中F(x)與G(x,y)中的x都是約束變元，因而不能將量詞的轄域縮小。7.請指出下面等值演算中的兩處錯誤。答：演算的第一步，應(yīng)用量詞否定等值式時丟掉了否定連接詞“-”,演算的第二步，在原(FxGy()?(()→Hxy(,)))錯的基礎(chǔ)上又用錯了等值式即，8.在一階邏輯中將下面命題符號化，要求用兩種不同的等值形式。(1)沒有小于負(fù)數(shù)的正數(shù)(2)相等的(1).3xFxGx(()A())VxGx(()→-Fx()),-VxFxGx(()→()?3xFx(()A-Gx()),兩個角是對頂角可是某人卻說這是真命題，其理由如下：設(shè)F(x):x是有理數(shù)，G(x):x是無理數(shù)。3xFx()與3xGx()都是真命題，于是，3xFx()A3xGx()?xFxGx(()A()),由于3xFxxGx()?3()是真命題，故3xFxGx(()?())也是真命題，即有的實數(shù)是有理數(shù)，也是無理數(shù)，問此人的結(jié)論對嗎?為什么?10.在求前束范式時，有人說-3xFxGxy(()A(,))已是前束范式，理由是量詞已在公式的前面。他說的對嗎?為什么?答：前束范式中，否定連聯(lián)接詞不能在量詞前面出現(xiàn)。VxFxGx(()→())→3xGxy(,)的前束范式，因為公式中的兩個量詞的指導(dǎo)變元相同。他的理由正確嗎?為什么?答：用換名規(guī)則可使兩個指導(dǎo)規(guī)則不同。(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規(guī)則o23xFxGx(()A()o?EG規(guī)則o?VxFxGx(()→())V3xyFxGy(()→()),(3)在自然推理系統(tǒng)F中，EG規(guī)則為,其中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()