離散數(shù)學(xué)-馮欒石陳編-習(xí)題答案

./習(xí)題一利用邏輯聯(lián)結(jié)詞把下列命題翻譯成符號(hào)邏輯形式他既是本片的編劇,又是導(dǎo)演 P∧Q銀行利率一降低,股價(jià)隨之上揚(yáng) P→Q盡管銀行利率降低,股價(jià)卻沒(méi)有上揚(yáng) P∧Q占據(jù)空間的、有質(zhì)量而且不斷變化的對(duì)象稱為物質(zhì) M<S∧P∧T>他今天不是乘火車去北京,就是隨旅行團(tuán)去了九寨溝 P▽Q小張身體單薄,但是極少生病,并且頭腦好使 P∧Q∧R不識(shí)廬山真面目,只緣身在此山中 P→Q〔解釋：因?yàn)樯碓诖松街?所以不識(shí)廬山真面目?jī)蓚€(gè)三角形相似,當(dāng)且僅當(dāng)他們的對(duì)應(yīng)角相等或者對(duì)應(yīng)邊成比例S<E∨T>如果一個(gè)整數(shù)能被6整除,那么它就能被2和3整除.如果一個(gè)整數(shù)能被3整除,那么它的各位數(shù)字之和也能被3整除解：設(shè)P–一個(gè)整數(shù)能被6整除 Q–一個(gè)整數(shù)能被2整除 R–一個(gè)整數(shù)能被3整除 S–一個(gè)整數(shù)各位數(shù)字之和能被3整除 翻譯為：〔P→〔Q∧R∧〔R→S判別下面各語(yǔ)句是否命題,如果是命題,說(shuō)出它的真值〔1BASIC語(yǔ)言是最完美的程序設(shè)計(jì)語(yǔ)言 Y,T/F〔2這件事大概是小王干的 N〔3x2=64 N〔4可導(dǎo)的實(shí)函數(shù)都是連續(xù)函數(shù) Y,T/F〔5我們要發(fā)揚(yáng)連續(xù)作戰(zhàn)的作風(fēng),再接再厲,爭(zhēng)取更大的勝利 N〔6客觀規(guī)律是不以人們意志為轉(zhuǎn)移的 Y,T〔7到2020年,中國(guó)的國(guó)民生產(chǎn)總值將趕上和超過(guò)美國(guó) Y,N/A〔8凡事都有例外 Y,F構(gòu)造下列公式的真值表,并由此判別哪些公式是永真式、矛盾式或可滿足式〔1〔P∨〔～P∧Q→Q解：PQ～P∧QP∨〔～P∧Q〔P∨〔～P∧Q→Q可滿足式00001011111001011011〔2~〔4略利用真值表方法驗(yàn)證下列各式為永真式〔1~〔8略證明下列各等價(jià)式〔1～〔〔～P∧Q∨〔～P∧～Q∨〔P∧QP證明：左式〔〔P∨～Q∧〔P∨Q∨〔P∧QP∨〔P∧Q∨〔P∧～Q∨T∨〔P∧QP右式〔2〔P→Q∧〔R→Q〔P∨R→Q證明：左式 〔～P∨Q∧〔～R∨Q〔～P∧～R∨Q～〔P∨R∨Q〔P∨R→Q右式〔3P→〔Q∨R〔P→Q∨〔P→R證明：左式 ～P∨Q∨R～P∨Q∨～P∨R〔～P∨Q∨〔～P∨R〔P→Q∨〔P→R右式〔4〔P∧Q∨〔R∧Q∨〔R∧P〔P∨Q∧〔R∨Q∧〔R∨P證明：左式 <〔P∨R∧Q∨〔R∧P<〔P∨R∨R>>∧<〔P∨R∨P>>∧〔Q∨R∧〔Q∨P〔P∨Q∧〔R∨Q∧〔R∨P右式如果P∨QQ∨R,能否斷定PR？如果P∧QQ∧R,能否斷定PR？如果～P～R,能否斷定PR？解： 〔1如果P∨QQ∨R,不能判斷PR,因?yàn)槿绻鸔=P∨R,那么P∨QP∨P∨RQ∨R,但P可以不等價(jià)于R. 〔2如果P∧QQ∧R,不能判斷PR,因?yàn)槿绻鸔=P∧R,那么P∧QP∧P∧RQ∧R,但P可以不等價(jià)于R. 〔3如果～P～R,那么有PR,因?yàn)椤玃～R,則～P<->～R為永真式,及有P<->R為永真式,所以PR.檢查↑和↓是否滿足結(jié)合率解：用真值表方式檢查PQRP↑QQ↑R<P↑Q>↑RP↑<Q↑R>00011110011101010111101110011001110101110011001101110011由上表可知,↑不滿住結(jié)合率PQRP↓QQ↓R<P↓Q>↓RP↓<Q↓R>00011000011001010001101100011000110101000011000101110000由上表可知,↓不滿住結(jié)合率把下列各式用↑等價(jià)表示出來(lái)〔1<P∧Q>∨～P解：原式 <<P↑Q>↑<P↑Q>>∨<P↑P><<<P↑Q>↑<P↑Q>>↑<<P↑Q>↑<P↑Q>>>↑<<P↑P>↑<P↑P>>〔2P→〔～P→Q解：原式 ～P∨P∨QQ<Q↑Q>↑<Q↑Q>〔3〔P→〔Q∨～R∧～P解：原式 〔～P∨～Q∨R∧～P～P∨〔～Q∧～P∨〔R∧～P<P↑P>∨〔<Q↑Q>∧<P↑P>∨〔R∧<P↑P><P↑P>∨〔〔<Q↑Q>↑<P↑P>↑〔<Q↑Q>↑<P↑P>∨〔〔R↑<P↑P>↑〔R↑<P↑P>設(shè)： <P↑P>=N〔〔<Q↑Q>↑<P↑P>↑〔<Q↑Q>↑<P↑P>=L 〔〔R↑<P↑P>↑〔R↑<P↑P>=M則上式 <<<N↑N>↑<L↑L>>↑<<N↑N>↑<L↑L>>>↑<M↑M>〔4～P∧～Q∧〔～R→P解：原式 ～P∧～Q∧〔R∨P<P↑P>∧<Q↑Q>∧〔<P↑P>↑<R↑R><〔<P↑P>↑<Q↑Q>↑〔<P↑P>↑<Q↑Q>>∧〔<P↑P>↑<R↑R>設(shè)： <〔<P↑P>↑<Q↑Q>↑〔<P↑P>↑<Q↑Q>>=N 〔<P↑P>↑<R↑R>=M則上式 <N↑M>↑<N↑M>證明：{～→}是最小功能完備集合證明: 因?yàn)閧～,∨}是最小功能完備集合,所以,如果{～→}能表示出∨,則其是功能完備集合.由于P∨Q<～P>→Q,所以{～→}是功能完備集合.因?yàn)椤荒芟嗷ケ硎?所以{～→}是最小功能完備集合；同理可證：{非,條件非}也能將或表示出來(lái)：P∨Q～<～P!→Q>證明:{～,▽}不是功能完備集證明：P∨Q沒(méi)有辦法通過(guò)～,▽的公式表達(dá)出來(lái),因?yàn)镻QP∨QP▽P～<P▽P>P▽Q000010011011101011111010所以,通過(guò)～,▽不能表達(dá)出真值為三個(gè)1或1個(gè)1的情況,因此,不能表達(dá)出P∨Q,所以不是功能完備集.用～和∧把公式P▽Q▽R和〔P▽Q→R表示出來(lái)解：〔P▽Q▽R <〔P∧～Q∨〔～P∧Q>▽R<<〔P∧～Q∨〔～P∧Q>∧～R>∨<～<〔P∧～Q∨〔～P∧Q>∧R><～〔～〔P∧～Q∧～〔～P∧Q∧～R>∨〔〔～〔P∧～Q∧～〔～P∧Q∧～R～〔～〔<～〔～〔P∧～Q∧～〔～P∧Q∧～R>∧～〔〔〔～〔P∧～Q∧～〔～P∧Q∧～R〔P▽Q→R ～〔～<～〔～〔P∧～Q∧～〔～P∧Q∧～R>分別利用真值表法和等價(jià)變換法求下列公式的主合取范式及主析取范式:<1>P→<<R∧Q>→S>解：真值表法PQRSR∧Q<R∧Q>→SP→<<R∧Q>→S>0000011000101100100110011011010001101010110110101011111110000111001011101001110110111100011110101111101001111111所以：主合取范式為=～P∨～Q∨～R∨S=M14主析取范式為=m1∨m2∨m3∨m4∨m5∨m6∨m7∨m8∨m9∨m10∨m11∨m12∨m13∨m14∨m16等價(jià)變換法〔略<2>〔～P∨～Q→〔P<->～Q解：真值表法PQ～P∨～QP<->～Q〔～P∨～Q→〔P<->～Q00100011111011111001所以：主合取范式為=P∨Q=M0主析取范式為=<～P∧Q>∨<P∧～Q>∨<P∧Q>=m1∨m2∨m3等價(jià)變換法〔略<3>P→<R∧<Q→P>>解：真值表法PQRQ→PR∧<Q→P>P→<R∧<Q→P>>000101001111010001011001100100101111110100111111所以：主合取范式為=<～P∨Q∨R>∧<～P∨～Q∨R>=M4∧M6主析取范式為=<～P∧～Q∧～R>∨<～P∧～Q∧R>∨<～P∧Q∧～R>∨<～P∧Q∧R>∨<P∧～Q∧R>∨<P∧Q∧R>=m0∨m1∨m2∨m3∨m5∨m7等價(jià)變換法〔略<4><P→<Q∧R>>∧<～P→<～Q∧～R>>解：真值表法PQRQ∧R～Q∧～RP→<Q∧R>～P→<～Q∧～R><P→<Q∧R>>∧<～P→<～Q∧～R>>0000111100100100010001000111010010001010101000101100001011110111所以：主合取范式為=<P∨Q∨～R>∧<P∨～Q∨R>∧<P∨～Q∨～R>∧<～P∨Q∨R>∧<～P∨Q∨～R>∧<～P∨～Q∨R>=M1∧M2∧M3∧M4∧M5∧M6主析取范式為=<～P∧～Q∧～R>∨<P∧Q∧R>=m0∨m7等價(jià)變換法〔略用轉(zhuǎn)化范式的方法判別下面各組公式是否等價(jià)〔1〔P→Q→〔P∧Q和〔～P→Q∧〔Q→P解： 〔P→Q→〔P∧Q～〔～P∨Q∨〔P∧Q〔P∧～Q∨〔P∧Q--合取范式 〔～P→Q∧〔Q→P〔P∨Q∧〔～Q∨PP∨<Q∧～Q>P〔P∧～Q∨〔P∧Q--合取范式兩式的合取范式相同,所以等價(jià)〔2〔P→Q∧〔P→R和P→〔Q∧R解：〔P→Q∧〔P→R〔～P∨Q∧〔～P∨R--合取范式P→〔Q∧R～P∨〔Q∧R〔～P∨Q∧〔～P∨R--合取范式兩式的合取范式相同,所以等價(jià)從A,B,C,D4個(gè)人中派2人出差,要求滿足下列條件：如果A去,則必須在C或D中選一人同去；B和C不能同時(shí)去；C和D不能同時(shí)去.用構(gòu)造范式的方法決定選派方案.解：由題設(shè)A：A去,B：B去,C：C去,D：D去則滿足條件的選派應(yīng)滿足如下范式：〔A→〔CD∧～〔B∧C∧～〔C∧D構(gòu)造和以上范式等價(jià)的主析取范式〔A→〔CD∧～〔B∧C∧～〔C∧D〔～A∧～B∧～C∧D∨〔～A∧～B∧～C∧～D∨〔～A∧～B∧C∧～D∨〔～A∧B∧～C∧～D∨〔A∧～B∧C∧～D∨〔A∧～B∧～C∧D∨〔～A∧B∧～C∧D∨〔A∧B∧～C∧D共有八個(gè)極小項(xiàng),但根據(jù)題意,需派兩人出差,所以,只有其中三項(xiàng)滿足要求：〔A∧～B∧C∧～D,〔A∧～B∧～C∧D,〔～A∧B∧～C∧D即有三種方案：A和C去或者A和D去或者B和D去.證明下列蘊(yùn)含試：〔1P→Q=>P→<P∧Q>證明：P→Q～P∨QT∧<～P∨Q><～P∨P>∧<～P∨Q>～P∨<P∧Q>P→<P∧Q>所以,這是個(gè)等價(jià)式,因此也是個(gè)蘊(yùn)含式〔2<P→Q>→Q=><P∨Q>證明：<P→Q>→Q～<～P∨Q>∨Q<P∧～Q>∨Q<P∨Q>∧<Q∨～Q><P∨Q>∧T<P∨Q>所以,這是個(gè)等價(jià)式,因此也是個(gè)蘊(yùn)含式〔3P∧～P∧R=>S證明：P∧～P∧RF=>S<F可蘊(yùn)含任何命題公式>〔4P=>Q∨R∨～R證明：P=>TQ∨R∨～R證明蘊(yùn)含關(guān)系的性質(zhì)1、性質(zhì)2和3證明：性質(zhì)1A=>A因?yàn)樵谌我獾慕忉屜?公式A的真值顯然和自己相同,當(dāng)然在為真時(shí)也相同,所以蘊(yùn)含成立.性質(zhì)2如果A=>B且B=>A,則AB因?yàn)锳=>B且B=>A及<A→B>∧<B→A>為永真式,則A<->B為永真式.所以AB.性質(zhì)3如果A=>B且A永真式,則B必為永真式因?yàn)?lt;A→B>為永真式,且A為永真式,那么只有B為永真式才能滿足<A→B>為永真式成立.所以結(jié)論為真.證明定理1.12證明：A=>B,當(dāng)且僅當(dāng)～B=>～A證明： ∵A=>BA→B為永真式～B→～A為永真式～B=>～A∴A=>B,當(dāng)且僅當(dāng)～B=>～A一個(gè)有錢人生前留下了一筆珍寶,藏在一個(gè)隱秘處.在他留下的遺囑中指出尋找珍寶的線索如下：如果藏寶的房子靠近池塘,那么珍寶不會(huì)藏在東廂房.如果房子的前院栽有大柏樹(shù),那么珍寶就藏在東廂房.藏寶房子靠近池塘.要么前院栽有大柏樹(shù),要么珍寶埋在花園正中地下.如果后院栽有香樟樹(shù),珍寶藏在附近.請(qǐng)利用蘊(yùn)含關(guān)系找出藏寶處.解：根據(jù)給定的條件有下述命題：P：珍寶藏在東廂房Q：藏寶的房子靠近池塘R：房子的前院栽有大柏樹(shù)S：珍寶藏在花園正中地下T：后院栽有香樟樹(shù)M：珍寶藏在附近根據(jù)題意,得出：〔Q→～P∧〔R→P∧Q∧〔R∨S∧〔T→M？〔Q→～P∧〔R→P∧Q∧〔R∨S∧〔T→M～P∧〔R→P∧〔R∨S∧〔T→M～R∧〔R∨S∧〔T→MS∧〔T→MS即珍寶藏在花園正中地下判斷下列蘊(yùn)含關(guān)系式是否成立：〔1Q∧<P→Q>P解：當(dāng)左端公式解釋為1時(shí),Q必須為1；Q為1,P比為1；所以,右端公式也為1；因此,蘊(yùn)含關(guān)系成立〔2<P→<Q∨～R>>∧<Q→<P∧R>>P→R解：左端公式Q<-><P∧R>,當(dāng)解釋為1是,分兩種情況,P∧R與Q同為1,那么P→R也為1；P∧R與Q同為0,如果此時(shí)P=1,R=0,則P→R為0；因此,此蘊(yùn)含式不成立〔3～P∧<P→Q>～Q解：左端公式解釋為1時(shí),P必為0；當(dāng)P為0時(shí),則Q可為0,也可為1；因此,此蘊(yùn)含式不成立〔4<P∨Q>∧<P→～Q>∧<P→R>R解：當(dāng)左端公式按P=0,Q=1,R=0解釋時(shí),為1,但右端不為1；因此,此蘊(yùn)含式不成立〔5<<P∧～Q>→R>∧<P∨Q>∧<Q→P>R解：當(dāng)左端公式按P=1,Q=1,R=0解釋時(shí),真值為1,但右端為0；因此,此蘊(yùn)含式不成立演繹證明下面各蘊(yùn)含式：〔1～P∨Q,R→～QP→～R證明：運(yùn)用cp法,將結(jié)論條件式的前件作為前提,證明步驟如下[1] P p<附加前提>[2] ～P∨Q p[3] Q T[1,2]I[4] R→～Q p[5] ～R T[3,4]I[6] P→～R CP[1,5]〔2<P∨Q>→<R∧S>,<S∨E>→BP→B證明：運(yùn)用cp法,將結(jié)論條件式的前件作為前提,證明步驟如下[1] P p〔附加前提[2] <P∨Q>→<R∧S> p[3] R∧S T[1,2]I[4] <S∨E>→B p[5] B T[3,4]I[6] P→B CP[1,5]〔3P→<Q→R>,<R∧S>→E,～B→<S∧～E>P→<Q→B>證明：運(yùn)用cp法,將結(jié)論條件式的前件作為前提,先將結(jié)論進(jìn)行等價(jià)變換為〔P∧Q→B,因此P∧Q可作為附加前提,證明步驟如下[1] P∧Q p<附加前提>[2] P→<Q→R> p[3] 〔P∧Q→R T[2]E[4] R T[1,3]I[5] <R∧S>→E p[6] E T[4,6]I[7] ～B→<S∧～E> p[8] B T[6,7]I[9] 〔P∧Q→B cp[1,8]〔4<R→Q>∧<R→S>,<Q→E>∧<S→B>,～<E∧B>,<P→R>～P證明：運(yùn)用反證方法,將結(jié)論的非納入前提,證明步驟如下[1] P p<附加前提>[2] P→R p[3] R T[1,2]I[4] <R→Q>∧<R→S> p[5] Q∧S T[3,4]I[6] <Q→E>∧<S→B> p[7] E∧B T[5,6]I[8] ～<E∧B> p[9] F<矛盾式> T[7,8]E〔5P→<Q→R>,Q→<R→S>P→<Q→S>證明：運(yùn)用cp法,將結(jié)論條件式的前件作為前提,證明步驟如下[1] P p<附加前提>[2] P→<Q→R> p[3] Q→R T[1,2]I[4] Q→<R→S> p[5] R→<Q→S> T[4]E[6] Q→S T[3,5]I[7] P→<Q→S> CP[1,6]把下列句子演繹成邏輯形式,并給出證明如果資方拒絕增加工資,那么罷工不會(huì)結(jié)束；除非罷工超過(guò)一年,并且資方撤換了經(jīng)理；現(xiàn)在資方拒絕了增加工資,罷工剛開(kāi)始.判斷罷工能否停止.解：根據(jù)題意,有如下命題P:資方拒絕增加工資Q:罷工結(jié)束R:罷工超過(guò)一年S:資方撤換了經(jīng)理所以,前提條件符號(hào)化為P→～Q；Q→R∧S；P∧～R因此,推理過(guò)程如下：[1] P∧～R p[2] P→～Q p[3] ～Q T[1,2]I所以,罷工不會(huì)結(jié)束某公司發(fā)生了一起盜竊案,經(jīng)仔細(xì)偵察,掌握了如下一些事實(shí)：被盜現(xiàn)場(chǎng)沒(méi)有留下任何痕跡失盜時(shí),小花或則小英正在卡拉ok廳如果失竊時(shí)小胖正在附近,他就會(huì)習(xí)慣性地破門而入偷走東西后揚(yáng)長(zhǎng)而去如果失盜時(shí)小花正在卡拉ok廳唱歌,那么金剛是最大的嫌疑者如果失盜時(shí)小胖不在附近,那么他的女友小英會(huì)和他一起外出旅游如果失盜時(shí)小英正在卡拉ok廳唱歌,那么瘦子是最大的嫌疑者根據(jù)以上事實(shí),請(qǐng)通過(guò)演繹推理找出偷竊者解：根據(jù)給定的條件有下述命題：P：現(xiàn)場(chǎng)無(wú)任何痕跡Q：失竊時(shí),小花在OK廳R：失竊時(shí),小英在OK廳S：失竊時(shí),小胖在附近T：金剛是偷竊者M(jìn)：瘦子是偷竊者則根據(jù)案情有如下命題公式：{P,Q∨R,S→～P,Q→T,～S→～R,R→M}PPS→～PP～ST①②I～S→～RP～RT③④IQ∨RPQT⑤⑥IQ→TPTT⑦⑧I即金剛是偷竊者設(shè)A1,A2,…,An是一組命題公式,如果存在一個(gè)解釋使A1∧A2∧…∧An取值真,就稱這組公式是相容的,否則稱為不相容的.不相容意味著A1∧A2∧…∧An蘊(yùn)含一個(gè)矛盾式,現(xiàn)在判別下列各命題組是否相容〔1P→<Q→R>,S→<Q∧～R>,P∧S解：根據(jù)題意〔P→<Q→R>∧〔S→<Q∧～R>∧〔P∧S<Q→R>∧<Q∧～R>R∧～RF所以,這組命題公式不相容〔2P∨Q,～R∨S,～Q,～S解：根據(jù)題意<P∨Q>∧<～R∨S>∧～Q∧～SP∧～R所以,當(dāng)P=1,Q=0,R=0,S=0時(shí),合取式解釋為1,因此這組命題公式相容〔3P<->Q,Q→R,～R∨S,～P→S,～S解：根據(jù)題意〔P<->Q∧〔Q→R∧〔～R∨S∧〔～P→S∧～S〔P<->Q∧〔Q→R∧～R∧P〔P<->Q∧～Q∧PF所以,這組命題公式不相容〔4P→Q,P→R,Q→～R,P解：根據(jù)題意〔P→Q∧〔P→R∧〔Q→～R∧PQ∧R∧〔Q→～RR∧～RF所以,這組命題公式不相容利用消解法證明下列各蘊(yùn)含式：〔1R→～Q,R∨S,S→～Q,P→Q～P證明： R→～Q～R∨～Q S→～Q～S∨～Q P→Q～P∨Q因此子句集合={～R∨～Q,～S∨～Q,R∨S,～P∨Q,P}消解過(guò)程如下：[1] ～R∨～Q p[2] ～S∨～Q p[3] R∨S p[4] ～P∨Q p[5] P p[6] Q 由[4,5]歸結(jié)[7] ～R 由[1,6]歸結(jié)[8] ～S 由[2,6]歸結(jié)[9] S 由[3,7]歸結(jié)[10] FLASE□由[8,9]歸結(jié) 導(dǎo)出空子句〔2～<P→Q>→<R∨S>,<Q→P>∨～R,RP<->Q證明： ～<P→Q>→<R∨S>～P∨Q∨R∨S <Q→P>∨～R～Q∨P∨～R ～<P<->Q> ～〔〔P→Q∧〔Q→P～〔P→Q∨～〔Q→P<P∧～Q>∨<Q∧～P><P∨Q>∧<～P∨～Q>因此子句集合={～P∨Q∨R∨S,～Q∨P∨～R,P∨Q,～P∨～Q,R}消解過(guò)程如下：[1] ～P∨Q∨R∨S p[2] ～Q∨P∨～R p[3] P∨Q p[4] ～P∨～Q p[5] R p[6] ～Q∨P 由[2,5]歸結(jié)[7] P 由[3,6]歸結(jié)[8] Q∨R∨S 由[1,7]歸結(jié)[9] P∨S 由[2,8]歸結(jié)[10] P∨～R 由[2,3]歸結(jié)[11] ～Q 由[4,6]歸結(jié)[12] R∨S 由[8,11]歸結(jié)[13] ～Q∨P∨S 由[2,12]歸結(jié)[14] P∨R∨S <此題可能有問(wèn)題>〔3P→<Q→R>,Q→<R→S>P→<Q→S>證明： P→<Q→R>～P∨～Q∨R Q→<R→S>～Q∨～R∨S ～〔P→<Q→S>P∧Q∧～S因此子句集合={～P∨～Q∨R,～Q∨～R∨S,P,Q,～S}消解過(guò)程如下：[1] ～P∨～Q∨R p[2] P p[3] ～Q∨R 由[1,2]歸結(jié)[4] Q p[5] R 由[3,4]歸結(jié)[6] ～Q∨～R∨S p[7] ～S p[8] ～Q∨～R 由[6,7]歸結(jié)[9] ～R 由[4,8]歸結(jié)[10] FLASE□由[5,9]歸結(jié) 導(dǎo)出空子句習(xí)題二把下列謂詞翻譯成謂詞公式〔1每個(gè)有理數(shù)都是實(shí)數(shù),但是并非每個(gè)實(shí)數(shù)都是有理數(shù),有些實(shí)數(shù)是有理數(shù)解： R<x> -- x是實(shí)數(shù) Ra<x> -- x是有利數(shù)翻譯如下：<x><Ra<x>→R<x>>∧～<x><R<x>→Ra<x>>∧<x><R<x>>∧Ra<x>〔2直線a和b平行當(dāng)切僅當(dāng)a和b不相交解： A<x> -- x是直線 F<x,y> -- x與y平行 G〔x,y> -- ｘ與ｙ相交翻譯如下：<ａ><ｂ>〔A<ａ>∧A<ｂ>→<F<ａ,ｂ>～G〔ａ,ｂ>>〔3除非所有的會(huì)員都參加,這個(gè)活動(dòng)才有意義解： A<x> -- ｘ是會(huì)員 B<x> -- x有意義ａ -- 這個(gè)活動(dòng)F<x,y> -- ｘ參加ｙ翻譯如下：B〔ａ→<x>〔A<x>→F<x,ａ>或～<x>〔A<x>→F<x,ａ>→～B〔ａ〔4任何正整數(shù)不是合數(shù)就是質(zhì)數(shù)解： A<x> -- ｘ是正整數(shù) Ｂ<x> -- ｘ是合數(shù) Ｃ<x> -- ｘ是質(zhì)數(shù)翻譯如下：<x>〔A<x>→Ｂ<x>Ｃ<x>凡是存錢的人都想有利息,如果沒(méi)有利息,人們就不會(huì)存錢解： A<x> -- ｘ是存錢的人F<x,y> -- ｘ想有ｙP -- 存錢沒(méi)有利息Q: -- 人們不存錢a: -- 利息翻譯如下：<x>〔A<x>→F<x,a>∧〔P→Q設(shè)論域D={0,1,2},把下列公式用不含量詞的公式表示出來(lái)〔1<x>P<x>∧<x>Q<x>解：上式P<0>∧P<1>∧P<2>∧〔Q<0>∨Q<1>∨Q<2>〔2<x>[P<x>→Q<x>]解：上式〔P<0>→Q<0>∧〔P<1>→Q<1>∧〔P<2>→Q<2>〔3<x>[～P<x>]∨<x>Q<x>解：上式〔～P<0>∧～P<1>∧～P<2>∨Q<0>∨Q<1>∨Q<2>指出下列公式中的約束變?cè)妥杂勺冊(cè)?并確定公式的轄域略對(duì)下列公式中的變?cè)M(jìn)行代換,以使任何變?cè)荒芗仁羌s束變?cè)质亲杂勺冊(cè)?<x><y>[P<x,y>→Q<y,z>]∨<z>R<x,y,z>解：代換如下<x><y>[P<x,y>→Q<y,z>]∨<s>R<u,v,s>〔2<<x>[P<x>→R<x>]∨Q<x>>∧<<x>R<x>→<z>S<x,z>>解：代換如下<<x>[P<x>→R<x>]∨Q<u>>∧<<y>R<y>→<z>S<u,z>>把下列語(yǔ)句符號(hào)化,并確定相應(yīng)謂詞公式是永真式、可滿足式、還是矛盾式〔1如果兩個(gè)數(shù)的積等于0,那么至少其中一個(gè)數(shù)為0,數(shù)x-1不等于0,所以數(shù)x-1和x+1的積也不等于0解：設(shè)論域在任意數(shù)域集合,運(yùn)用常規(guī)的數(shù)學(xué)符號(hào),翻譯如下<x><y><xy=0→<x=0∨y=0>>∧<<x-1≠0>→<<x-1><x+1>≠0>>這是一個(gè)可滿足式,但不是永真式,因?yàn)榇嬖趚=-1時(shí),謂詞公式不成立,但其它情況均成立,如果論域中不包含-1,為真,包含就不成立〔2誠(chéng)實(shí)的人都講實(shí)話.小林不是誠(chéng)實(shí)的,因而小林不講實(shí)話解： H<x> -- x誠(chéng)實(shí) T<x> -- x講真話 a -- 小林翻譯如下： 〔<x><H<x>→T<x>>∧～H<a>→～T<a>這是一個(gè)可滿足式,因?yàn)榉穸l件命題前件,不一定后件命題一定為假.及小林雖然不誠(chéng)實(shí),但也可能講實(shí)話〔3好貨不便宜.小王買的衣服很貴,所以小王買的是優(yōu)質(zhì)衣服解： G<x> -- x是好貨 C<x> -- x便宜 a -- 小王買的衣服翻譯如下：<<x><G<x>→～C<x>>∧～C<a>→G<a>此謂此公式成立,是永真式〔4每個(gè)懂得人性的作家都很高明,不能刻畫人們內(nèi)心世界的詩(shī)人都不是真正的詩(shī)人.莎士比亞創(chuàng)作了哈姆雷特.沒(méi)有一個(gè)不懂得人性本質(zhì)的作家能夠刻畫人們的內(nèi)心世界.只有真正的詩(shī)人才能創(chuàng)作哈姆雷特.因此,莎式比亞是個(gè)高明的作家.解： A<x> -- x懂人性 B<x> -- x很高明 C<x> -- x能刻畫人們內(nèi)心世界 D<x,y> -- x創(chuàng)作y h -- 哈姆雷特 s -- 莎士比亞翻譯如下： 〔<x>[<A<x>→B<x>>∧<～C<x>→～B<x>>∧<B<x>→D<x,h>∧<～A<x>→～C<x>>]∧D<s,h>→B<s>此謂詞公式成立〔但沒(méi)有區(qū)分詩(shī)人和作家,還可有更好的表達(dá)形式對(duì)于題目給定的解釋,求下列各公式相應(yīng)的真值〔1A=<x>[P<x>∨Q<x>]∧R<a>,解釋D={1,2,3},P<x>:x2+x=2;Q<x>:x是素?cái)?shù)；R<x>:x<3;a=1解：根據(jù)解釋,A變?yōu)椤睵<1>∨Q<1>∧〔P<2>∨Q<2>∧〔P<3>∨Q<2>∧R<1>,根據(jù)P<x>,Q<x>,R<x>的定義,顯然P<1>∨Q<1>=1,P<2>∨Q<2>=1,P<3>∨Q<2>=1,R<1>=1,所以整個(gè)公式解釋為真〔2A=P<a,f<b>>∧P<b,f<a>>,B=<x><y>P<y,x>,C=<y><x>P<y,x>,E=<x><y>[P<x,y>→P<f<x>,f<y>>],解釋：D={2,3},a=3,b=2,f<2>=3,f<3>=2,P<2,2>=0,P<2,3>=0,P<3,2>=P<3,3>=1解：根據(jù)解釋,A變?yōu)镻<3,3>∧P<2,2>=1∧0=0,真值為假 B變?yōu)?lt;P<2,2>∨P<3,2>>∧<P<2,3>∨P<3,3>>=〔0∨1∧〔0∨1=1,真值為真 C變?yōu)?lt;P<2,2>∧P<2,3>>∨<P<3,2>∧P<3,3>>=〔0∧0∨〔1∧1=1,真值為真 E變?yōu)?lt;P<2,2>→P<3,3>>∧<P<2,3>→P<3,2>>∧<P<3,2>→P<2,3>>∧<P<3,3>→P<2,2>>=〔0→1∧〔0→1∧〔1→0∧〔1→0=0,真值為假設(shè)論域?yàn)檎麛?shù)集合Z,試判定下面各公式是否是永真式,矛盾式或可滿足式〔1<x>[x>-10∧x2≥0]答：為假命題〔2<x>[2x>8∧x2-6x+5≤0]答：為真命題,當(dāng)4,5使?jié)M足謂詞公式〔3<x><y>[x+y=1024]答：為真命題,對(duì)任意整數(shù)x,y取值為1024-x及可〔4<y><x>[xy<10∨x+y≥2]答：為真命題,y=0及成立試對(duì)公式<x><y>[P<x,y>→Q<x>]構(gòu)造一個(gè)解釋,使在該解釋下公式取值真例如：在整域內(nèi),P<x,y>為xy>0,Q<x>為x為不為0,那么上述公式解釋為,對(duì)任意一個(gè)整數(shù)x,都存在整數(shù)y,如果x乘y大于0,則x不等于0.顯然是個(gè)真命題.證明下列各式成立：〔1<x><y>[P<x>→Q<y>]<x>P<x>→<y>Q<y>證明：右式<x><y>[~P<x>∨Q<y>]<x>~P<x>∨<y>Q<y><x>P<x>→<y>Q<y>〔2<x><y>[P<x>→Q<y>]<x>P<x>→<y>Q<y>證明：右式<x><y>[~P<x>∨Q<y>]<x>~P<x>∨<y>Q<y><x>P<x>→<y>Q<y>〔3~<y><x>P<x,y><y><x>[~P<x,y>]證明：右式<y>~<x>P<x,y><y><x>[~P<x,y>]判別<x>[P<x>→Q<x>]<x>P<x>→<x>Q<x>是否成立,如果成立,請(qǐng)給出證明；如果不成立,找一個(gè)解釋予以說(shuō)明解：<x>[P<x>→Q<x>]<x>[～P<x>∨Q<x>]<x>～P<x>∨<x>Q<x><x>P<x>→<x>Q<x>顯然和<x>P<x>→<x>Q<x>不等價(jià),現(xiàn)構(gòu)造如下解釋設(shè)論域?yàn)镈={a,b},P<a>=0,P<b>=1,Q<a>=0,Q<b>=0,則<x>[P<x>→Q<x>]解釋為真,而<x>P<x>→<x>Q<x>解釋為假,所以不等價(jià)把下列公式化為等價(jià)的前束范式,再求出對(duì)應(yīng)的SKolem范式〔1~<<x>P<x>→<y>P<y>>解：原式~〔~<x>P<x>∨<y>P<y><x>P<x>∧<y>~P<y><x><P<x>∧~P<x>>F〔2~<<x>P<x>→<y><z>Q<y,z>>解：原式<x>P<x>∧<y><z>~Q<y,z><x><z>〔P<x>∧~Q<x,z>其SKolem范式為：<x>〔P<x>∧~Q<x,f<x>>〔3<x><y>[<z>P<x,y,z>∧<u>Q<x,u>∧<v>Q<y,v>]解：原式<x><y><z><u><v>[P<x,y,z>∧Q<x,u>∧Q<y,v>]其SKolem范式為：<x><y>[P<x,y,f<x,y>>∧Q<x,g<x,y>>∧Q<y,l<x,y>>]〔4<x>[～P<x,0>→<<y>P<y,f<x>>∧<z>Q<x,z>>]解：原式<x>[P<x,0>∨<<y>P<y,f<x>>∧<z>Q<x,z>>]<x><y><z>[P<x,0>∨<P<y,f<x>>∧Q<x,z>>]其SKolem范式為：<x><z>[P<x,0>∨<P<g<x>,f<x>>∧Q<x,z>>]設(shè)G的前束范式為<x><y>P<x,y>,其中P<x,y>不含x,y以外的變?cè)?；設(shè)f是不出現(xiàn)在P<x,y>中的函數(shù)符號(hào).證明：G是永真式當(dāng)且僅當(dāng)<x>P<x,f<x>>為永真式證明： 1充分性： 當(dāng)G為永真式,及至少存在一個(gè)x=a,使得<y>P<a,y>為永真,及對(duì)論域中任意的元素b,P<a,b>為真,設(shè)函數(shù)f〔a=b,那么P<a,f<a>>為真,及<x>P<x,f<x>>為真 2必要性： 當(dāng)<x>P<x,f<x>>為永真時(shí),及至少存在一個(gè)x=a,在任意的f<a>取任意論域中的值時(shí),都為真,及<y>P<a,y>為真,所以G為永真綜上所述,命題成立證明下列各式成立〔1<x><y>[P<x>∧Q<y>]<x>P<x>證明：左式<x>P<x>∧<y>Q<y><x>P<x>〔2~<<x>P<x>∧Q<a>><x>P<x>→~Q<a>證明：左式~<x>P<x>∨~Q<a><x>P<x>→~Q<a>〔3<x>[~P<x>→Q<x>]∧<x>[~Q<x>]P<x>證明：左式<x>[<~P<x>→Q<x>>∧~Q<x>]<~P<x>→Q<x>>∧~Q<x>P<x>〔4<x>[P<x>∨Q<x>]∧<x>[~P<x>]<x>Q<x>證明：左式<x>[<P<x>∨Q<x>>∧~P<x>]<x>Q<x>〔5<x>[P<x>→~Q<x>]∧<x>[P<x>]~<x>Q<x>證明：左式<<x>P<x>∨~<x>Q<x>>∧<x>[P<x>~<x>Q<x>判別下面各式是否成立,并說(shuō)明理由〔1P<x>→<x>Q<x><x>[P<x>∧Q<x>]答：不成立,因?yàn)楫?dāng)P<x>恒為假時(shí),左式成立,但右式不成立〔2<x>P<x>→<x>Q<x><x>[P<x>→Q<x>]答：成立,因?yàn)樽笫?lt;x>~P<x>∨<x>Q<x>]<x>[~P<x>∨Q<x>]<x>[P<x>→Q<x>]〔3<x>[P<x>→Q<x>]<x>P<x>→<x>Q<x>答：不成立,因?yàn)樵谌缦陆忉屒闆r,左式成立,而右式不成立D={a,b},P<a>=Q<a>=0,P<b>=Q<b>=1下面給出了對(duì)<x>[P<x>∨Q<x>]<x>P<x>∨<x>Q<x>]的證明：〔證明過(guò)程略試判斷這個(gè)證明是否正確.你能給出一個(gè)證明嗎？答：這個(gè)證明不正確,因?yàn)椋喝绻鸓Q則~Q~P而~P~Q不一定成立,因此在這個(gè)證明過(guò)程中,第二步到第三步的蘊(yùn)含不成立.演繹下列各式〔1<x>[P<x>→Q<x>]<x>P<x>→<x>Q<x>證明：運(yùn)用CP法[1] <x>[P<x>→Q<x>] p[2] P<a>→Q<a> ES[2][3] <x>P<x> p<附加前提>[4] P<a> US[1][5] Q<a> T[2,3]I[6] <x>Q<x> EG[5][7] <x>P<x>→<x>Q<x> CP[3,6]〔2<x>P<x>→<x>Q<x><x>[P<x>→Q<x>]證明：[1] <x>P<x>→<x>Q<x> p[2] ~<x>P<x>∨<x>Q<x> T[1]E[3] <x>~P<x>∨<y>Q<y> T[2]E[4] <x><y><~P<x>∨Q<y>> T[3]E[5] <y><~P<a>∨Q<y>> ES[4][6] <~P<a>∨Q<a>> GS[5][7] P<a>→Q<a> T[6]E[8] <x>[P<x>→Q<x>] EG[7]〔2<x>[P<x>→Q<x>]<x>[P<x>→Q<x>]證明：[1] <x>[P<x>→Q<x>] p[2] <x>[~P<x>∨Q<x>] T[1]E[3] ~P<a>∨Q<a> US[2][4] P<a>→Q<a> T[3]E[5] <x>[P<x>→Q<x>] EG[4]〔3<x>[P<x>→Q<x>],<x>[R<x>→~Q<x>]<x>[R<x>→~P<x>]證明：[1] <x>[R<x>→~Q<x>] p[2] R<x>→~Q<x> US[1][3] Q<x>→~R<x> T[2]E[4] <x>[P<x>→Q<x>] p[5] P<x>→Q<x> US[4][6] P<x>→~R<x> T[3,5]I[7] R<x> →~P<x> T[6]E[8] <x>[R<x>→~P<x>] UG[7]〔4<x>[P<x>→<Q<y>∧R<x>>],<x>P<x>Q<y>∧<x>[P<x>∧R<x>]證明：[1] <x>[P<x>→<Q<y>∧R<x>>] p[2] P<a>→<Q<y>∧R<a>> US[1][3] <x>P<x> p[4] P<a> ES[3][5] Q<y>∧R<a> T[2,4]I[6] Q<y>∧R<a>∧P<a> T[4,5]I[7] Q<y>∧<x>[P<x>∧R<x>] EG[6]判別下面各個(gè)推理是否正確,如果不正確,指出錯(cuò)在什么地方〔題目不再重復(fù)〔1答：不正確,全稱指定應(yīng)該變?yōu)槠渌莤的變?cè)?可修改為：P<y>→Q<x>〔2答：正確〔3答：不正確,全稱指定應(yīng)該使用相同的個(gè)體常量,可修改為：P<a>∨Q<a>〔4答：題目不正確,存在量詞的指導(dǎo)變?cè)獞?yīng)該是另外的變?cè)?hào)〔5答：不正確,存在量詞的轄域應(yīng)該包含全部的謂詞,可修改為：<x>[P<x>→Q<x>]〔6答：不正確,對(duì)不同的個(gè)體常元應(yīng)該用不同的變?cè)M(jìn)行存在指定,可修改為：<x>[P<x>→Q<b>]〔7答：不正確,推理過(guò)程中,應(yīng)該先使用存在指定,然后使用全稱指定把下面蘊(yùn)含式變成SKolem范式,然后用消解法證明其正確性〔1<x>[P<x>→Q<x>]<x>[<y>[P<y>∧R<x,y>]]→<y>[Q<y>∧R<x,y>]證明：首先,把結(jié)論否定后作為附加前提,與原有前提一起轉(zhuǎn)化為skolem范式<x>[P<x>→Q<x>]∧~〔<x>[<y>[P<y>∧R<x,y>]→<y>[Q<y>∧R<x,y>]<x>[~P<x>∨Q<x>]∧<x>[<y>[P<y>∧R<x,y>]∧<y>[~Q<y>∨~R<x,y>]]進(jìn)行變量替換：<x>[~P<x>∨Q<x>]∧<u>[<y>[P<y>∧R<u,y>]∧<v>[~Q<v>∨~R<u,v>]]<u><y><x><v>[[~P<x>∨Q<x>]∧[P<y>∧R<u,y>]∧[~Q<v>∨~R<u,v>]]<x><v>[[~P<x>∨Q<x>]∧[P<a>∧R<b,a>]∧[~Q<v>∨~R<b,v>]]由skolem范式得到子句集合為：{~P<x>∨Q<x>,P<a>,R<b,a>,~Q<v>∨~R<b,v>}利用代換進(jìn)行消解的過(guò)程如下：[1] ~Q<v>∨~R<b,v>[2] R<b,a>[3] ~Q<a> [1]和[2],代換{a/v}[4] ~P<x>∨Q<x>[5] ~P<a> [3]和[4], 代換{a/x}[6] P<a>[7] □〔2<x>P<x>→<x>[<P<x>∨Q<x>>→R<x>],<x>P<x>,<x>Q<x><x><y>[R<x>∧R<y>]證明：首先,把結(jié)論否定后作為附加前提,與原有前提一起轉(zhuǎn)化為skolem范式<<x>P<x>→<x>[<P<x>∨Q<x>>→R<x>]>∧<x>P<x>∧<x>Q<x>∧~<<x><y>[R<x>∧R<y>]><<x>~P<x>∨<x>[<~P<x>∧~Q<x>>∨R<x>]>∧<x>P<x>∧<x>Q<x>∧<x><y>[~R<x>∨~R<y>]<x><y>[~P<x>∨<~P<y>∧~Q<y>∨R<y>]∧<z>P<z>∧<u>Q<u>∧<x><y>[~R<x>∨~R<y>]<x><y>[[~P<x>∨<~P<y>∧~Q<y>∨R<y>]∧[~R<x>∨~R<y>]]∧<z>P<z>∧<u>Q<u><z><u><x><y>[~P<x>∨R<y>∨~P<y>]∧[~P<x>∨R<y>∨~Q<y>]∧[~R<x>∨~R<y>]∧P<z>∧Q<u><x><y>[~P<x>∨R<y>∨~P<y>]∧[~P<x>∨R<y>∨~Q<y>]∧[~R<x>∨~R<y>]∧P<a>∧Q<b>由skolem范式得到子句集合為：{~P<x>∨R<y>∨~P<y>,~P<x>∨R<y>∨~Q<y>,~R<x>∨~R<y>,P<a>,Q<b>}[1] ~P<x>∨R<y>∨~Q<y>[2] P<a>[3] R<y>∨~Q<y> [1]和[2],代換{a/x}[4] Q<b> [5] R<b> [3]和[4],代換{b/y}[6] ~R<x>∨~R<y>[7] ~R<y> [5]和[6],代換{b/x}[8] ~P<x>∨R<y>∨~P<y>[9] ~P<x>∨R<a > [2]和[8],代換{a/y}[10] ~P<x> [7]和[9],代換{a/y}[11] □ [2]和[10],代換{a/x}習(xí)題三給出下列集合的表示法：〔1 A={1,2,3,4,6,8,9,12,18,24,36,72}〔2 B={<x,y>|x∈R∧y∈R∧y=2x}〔3 C={x|x∈Z∧<i><i∈Z∧<x=15i>}證明：集合之間子集關(guān)系的自反性、反對(duì)稱性和傳遞性證明： 〔1因?yàn)閷?duì)任意集合A而言,AA成立,所以子集關(guān)系的自反性成立 〔2對(duì)任意兩個(gè)集合A,B而言,如果AB同時(shí)BA,則A=B,所以子集關(guān)系的反對(duì)稱性成立 〔3對(duì)任意三個(gè)集合而言,如果AB,BC,那么AC成立,所以子集關(guān)系的傳遞性成立試寫出第一題中集合A,B,C對(duì)應(yīng)的特征函數(shù)略仔細(xì)區(qū)分集合中的關(guān)系符號(hào)∈和,并判斷下列各蘊(yùn)含關(guān)系的真假題目?jī)?nèi)容,見(jiàn)課本〔1真,根據(jù)子集的定義,任何屬于B集合的元素也屬于C集合〔2假,例如：A={1,2}B={{1,2},2,3}C=B,1屬于A,但并不是C集的元素〔3假,例如：A={1,2}B={1,2,3}C={{1,2,3}},A不是C的元素〔4假,例如：A={1,2}B={1,2,3}C={{1,2,3}},A不是C的子集〔5假,例如：A=1B={1,2,3}C={{1,2,3}},A不是C的元素〔6真,子集關(guān)系具有傳遞性利用3.1節(jié)例3.3中已證明的Russell悖論來(lái)證明Cantor悖論：合于A={S|S是任意的集合}的集合A不存在證明：假設(shè)A存在,顯然A屬于A,但確實(shí)存在有集合不是自己的元素,所以由所有不是自己的元素的集合夠成的集合B應(yīng)該存在并包含在A中,但根據(jù)Russell悖論,這樣的集合B不存在,所以A集合也不存在假設(shè)已知集合的元素是整數(shù),試寫一個(gè)程序判定某個(gè)對(duì)象是否是該集合的元素,判定某個(gè)給定集合是已知集合的子集編程題目,略略略證明下列各式〔1A∩<B-C>=<A∩B>-<A∩C>證明：左式=A∩<B∩~C>=<A∩B∩~C>∪<A∩B∩~A>=<A∩B>∩<~C∪~A>=<A∩B>∩~<A∩C>=<A∩B>-<A∩C>=右式〔2A-<B∪C>=<A-B>∩<A-C>證明：右式=<A∩~B>∩<A∩~C>=A∩~B∩~C=A∩~<B∪C>=A-<B∪C>=左式〔3<A-B>-C=A-<B∪C>=<A-C>-B證明：<A-B>-C=A∩~B∩~C=A∩~<B∪C>=A-<B∪C>=A∩~C∩~B=<A-C>-B〔4A∩<B∪C>=<A∩B>∪CCA證明：充分性∵A∩<B∪C>=<A∩B>∪C<A∩B>∪<A∩C>=<A∩B>∪C假設(shè)C不是A的子集,則C中必存在元素c在C中而不在A中,那么c一定不在等式的左端集合中,而一定在右端集合中,矛盾∴CA必要性∵CA,∴A∩C=C,等式兩端同時(shí)并上另一個(gè)集合,等式成立∴<A∩B>∪<A∩C>=<A∩B>∪CA∩<B∪C>=<A∩B>∪C〔5A∩<B⊕C>=<A∩B>⊕<A∩C>證明：左式=A∩〔B∪C-B∩C=A∩〔<B∪C>∩<~B∪~C>=A∩<B∪C>∩<~B∪~C>=AB~C+AC~B右式=〔<A∩B>∪<A∩C>-〔<A∩B>∩<A∩C>=〔A∩<B∪C>∩~〔A∩B∩C=A∩<B∪C>∩<~A∪~B∪~C>=AB~C+AC~B所以,左式=右式下面三式中,哪個(gè)可得出B=C的結(jié)論〔1A∪B=A∪C答：不能得出此結(jié)論,因?yàn)槿绻鸅≠C,但B,C都是A的子集,A∪B=A∪C成立〔2A∩B=A∩C答：不能得出此結(jié)論,因?yàn)锽≠C,但A是C∩B子集,A∩B=A∩C成立A⊕B=A⊕C答：能,因?yàn)锳⊕A=Φ,Φ⊕A=A⊕Φ=A,同時(shí),〔A⊕B⊕C=A⊕〔B⊕C所以,已知等式兩端A⊕A⊕B=A⊕A⊕CΦ⊕B=Φ⊕CB=C設(shè)X=A-<B∩~C>,Y=A∪~<B∪C>,試用集合ABC的特征函數(shù)表示出集合X和Y對(duì)應(yīng)的特征函數(shù)解：χA-<B∩~C>〔x=1χA<x><1-χB∩~C<x>>=χA<x><1-χB<x>χ~C<x>>=χA<x>-χA<x>χB<x><1-χC<x>>=χA<x>-χA<x>χB<x>+χA<x>χB<x>χC<x>=1χA∪~<B∪C><x>=1χA<x>+χ~<B∪C><x>-χA<x>χ~<B∪C><x>=χA<x>+1-χB∪C<x>-χA<x><1-χB∪C<x>>=χA<x>+1–<χB<x>+χC<x>-χB<x>χC<x>>-χA<x>+χA<x><χB<x>+χC<x>-χB<x>χC<x>>=1-χB<x>-χC<x>+χB<x>χC<x>+χA<x>χB<x>+χA<x>χC<x>-χA<x>χB<x>χC<x>=1證明定理3.3中的〔4和〔5式〔4χ-A<x>=1–χA〔x證明：χ-A<x>=1 x~AxAχA<x>=01-χA<x>=1所以：χ-A<x>=1–χA〔xχA⊕B<x>=χA〔x+χB〔x-2χA〔xχB〔x證明：χA⊕B<x>=1 xA⊕Bx<A-B>∪<B-A>χA-B<x>+χB-A<x>-χA-B<x>χB-A<x>=1χA<x><1-χB<x>>+χB<x><1-χA<x>>-χA<x><1-χB<x>>χB<x><1-χA<x>>=χA<x>-χA<x>χB<x>+χB<x>-χA<x>χB<x>–0=1所以：χA⊕B<x>=χA〔x+χB〔x-2χA〔xχB〔x〔注：因?yàn)閤不能同時(shí)屬于A-B和B-A,所以χA-B<x>χB-A<x>必為0設(shè)A,B,C是任意集合,判別下面各式是否正確：〔1<A-B>∪<B-C>=A-C答：不成立,因?yàn)楫?dāng)A=C但不等于B時(shí),<A-B>∪<B-C>不為空,但A-C為空,等式不成立〔2A∪<B-C>=<A∪B>-<A∪C>答：不成立,假設(shè)B=C,但A不為空,那么A∪<B-C>=A,但<A∪B>-<A∪C>=,等式不成立〔3<A∩B>∪C=A∩<B∪C>答：不成立,因?yàn)槿绻鸄為空集,C不為空,那么等式右端為空,而左端為C,不為空〔4ABA∩CB∩C答：正確,因?yàn)锳∩C中任意元素a,即是A的元素也是C的元素,因此也一定是B的元素,所以也是B∩C的元素,所以A∩CB∩C〔5A∩C=B∩C∧A∪C=B∪CA=B答：正確,假設(shè)A≠B,那么當(dāng)C為空集時(shí),A∪C=B∪C就不成立,所以A=B〔6AC∧BCA∪BC答：正確.因?yàn)?A∪B中的任意元素,要么屬于A,要么屬于B,所以也屬于C,所以A∪BC〔7AB∧ACAB∩C答：正確.因?yàn)?A集中的任意元素,及是B的元素又是C的元素,所以是B∩C的元素,所以A是B∩C的子集〔8AB~B~A答：正確.∵AB <x>[xA->xB]<x>[xB->xA]<x>[x~B->x~A]~B~A有人對(duì)~A∪~B~<A∪B>的證明如下：<x>[x~A~B]<x>[x~Ax~B]<x>[xAxB]<x>[xAB]<x>[x~<AB>]這個(gè)證明有效嗎？為什么？答：這個(gè)證明是錯(cuò)誤的,因?yàn)椋?lt;x>[xAxB]<x>[~<xAxB>]<x>[xAB]<x>[x~<AB>]設(shè)A={1,2,3},B={c,d},求A×B,A×A,<A×B>×B解：A×B={<1,c>,<1,d>,<2,c>,<2,d>,<3,c>,<3,d>}A×A={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}<A×B>×B={<<1,c>,c>,<<1,c>,b>,<<1,d>,c>,<<1,d>,d>,<<2,c>,c>,<<2,c>,b>,<<2,d>,c>,<<2,d>,d>,<<3,c>,c>,<<3,c>,d>,<<3,d>,c>,<<3,d>,d>}求A={,a,}的冪集解：2A={,{},{a},{},{,a},{,},{a,},{設(shè)A,B是任意兩集合,證明〔12A2B2A證明：X2A2BX2AXXAXB=>XABX2A等號(hào)成立的條件:AB或BA<因?yàn)槿鬉和B沒(méi)有子集關(guān)系,必有aA–B和bB–A,使{a,b}2AB,但{a,b}2A2〔22A2B=2A證明：X2A2BX2AXXAXBXABX2A設(shè)A是含n個(gè)元素的集合,a和b是A中的兩個(gè)因素,試決定在2A中含有a的元素〔即A的子集有多少個(gè)？同時(shí)含a和b解：〔1在2A中含有元素a的子集與不含a的子集一樣多,故在2A中含有元素a的子集為2n-1個(gè);因?yàn)锳〔2在2A中含有元素a,b的子集與不含a,b的子集一樣多,故在2A中含有元素a,b的子集為2n-設(shè)A,B,C是3個(gè)任意集合,C,證明：ABA×CB×C證明：充分性：AB=>A×CB×C因?yàn)?對(duì)任意一個(gè)A×C中元素〔a,c,有aA,因?yàn)锳是B的子集,所以aB,所以〔a,c是B×C的元素,所以A×CB×C必要性：A×CB×C=>AB因?yàn)?對(duì)A中任意一個(gè)元素a,和C中任意一個(gè)元素c,那么<a,c>A×C,又因?yàn)锳×CB×C,所以<a,c>B×C,因此aB,所以AB綜上所述,ABA×CB×C附加題：證明等式<A⊕B>⊕C=A⊕<B⊕C>證明：A⊕<B⊕C>=A⊕<<B-C>∪<C-B>>=<A-<<B-C>∪<C-B>>>∪<<<B-C>∪<C-B>>-A> =~AB~C+~A~BC+A~B~C+ABC<A⊕B>⊕C=C⊕<A⊕B>那么按上式的劃簡(jiǎn)方式,就是把C替換為A,把A替換為B,將B替換為C,所以C⊕<A⊕B>=~CA~B+~C~AB+C~A~B+CAB=~AB~C+~A~BC+A~B~C+ABC習(xí)題四設(shè)A={1,2,3,4},B={0,1,4,9,12}.分別把下面定義的從集合A到集合B的二元關(guān)系R用序偶的集合表示出來(lái)〔1xRyx|y解:R={<1,0>,<1,1>,<1,4>,<1,9>,<1,12>,<2,0>,<2,4>,<2,12>,<3,0>,<3,9>,<3,12>,<4,0>,<4,4>,<4,12>}〔2xRyxy<mod3>解:R={<1,1>,<1,4>,<3,0>,<3,9>,<3,12>,<4,1>,<4,4>}〔3xRyy/x∟<y-x>/2」解:R={<3,9>,<3,12>,<4,9>,<4,12>}用關(guān)系圖和關(guān)系矩陣表示第1題中的各個(gè)關(guān)系略設(shè)A=2{0,1,2},定義A上的二元關(guān)系R為xRyx∩y≠Φ；用集合表示出這個(gè)關(guān)系,并畫出對(duì)應(yīng)的關(guān)系圖解：關(guān)系R={<{0},{0}>,<{0},{0,1}>,<{0},{0,2}>,<{0},{0,1,2}>,<{1},{1}>,<{1},{0,1}>,<{1},{1,2}>,<{1},{0,1,2}>,<{1},{1}>,<{1},{0,1}>,<{1},{1,2}>,<{1},{0,1,2}>,<{2},{2}>,<{2},{0,2}>,<{2},{1,2}>,<{2},{0,1,2}>,<{0,1},{0}>,<{0,1},{1}>,<{0,1},{0,1}>,<{0,1},{0,2}>,<{0,1},{1,2}>,<{0,1},{0,1,2}>………}設(shè)A是含n個(gè)元素的集合,請(qǐng)問(wèn)在A上可以定義出多少個(gè)二元關(guān)系？解:因?yàn)镽是A上的二元關(guān)系,RAA,所以R的數(shù)量及為AA冪集的數(shù)量,而|AA|=n2,所以共2n2個(gè)二元關(guān)系判別第1題和第3題中定義的二元關(guān)系各具有哪些性質(zhì)？答：第1題中由于不是A上的關(guān)系,所以不具備討論本章定義的性質(zhì)第3題所定義的關(guān)系由于〔Φ,Φ不在關(guān)系中,所以不是自反的；又由于〔{0},{0}在關(guān)系中,所以不是反自反的由于x∩y≠Φ,那么y∩x≠Φ,所以關(guān)系是對(duì)稱的由于x∩y≠Φ同時(shí)y∩z≠Φ,并不能一定得到x∩z≠Φ,例如x={0},y={0,1},z={1,2},但是x∩z=Φ所以,這個(gè)關(guān)系是一個(gè)對(duì)稱關(guān)系設(shè)在整數(shù)集Z上定義如下二元關(guān)系,試填寫下表：解：填表如下R自反性反自反性對(duì)稱性反對(duì)稱性傳遞性x|y√×××√x≡y<modm>√×√×√xy>0××√×√xy≧0√×√××x=y或|x-y|=1√×√××x2>y2×√×√√因?yàn)閤|x成立,所以自反性成立；所以反自反性不成立；因?yàn)閤≠0時(shí),x|0成立,但0|x不成立,所以對(duì)稱性不成立,因?yàn)?|-1,和-1|1成立,所以反對(duì)稱性不成立；但x|y,y|z成立,就一定有x|z成立,所以傳遞性成立因?yàn)槟相等是整數(shù)集合上的等價(jià)關(guān)系,所以具有自反、對(duì)稱、傳遞性因?yàn)?0=0,所以自反性不成立；因?yàn)閤≠0時(shí)必有xx>0,所以反自反性不成立；因?yàn)閤y>0必有yx>0,所以對(duì)稱性成立；因此反對(duì)稱性不成立；因?yàn)閤y>0,yz>0,能得到x,y,z同號(hào)且不為0,所以,xz>0,所以傳遞性成立因?yàn)閤x≧0,所以自反性成立；因此,反自反性不成立；因?yàn)閤y≧0,所以yx≧0,因此對(duì)稱性成立；因此,反對(duì)稱性不成立；因?yàn)?1*0≧0,0*1≧0,但-1*1<0,所以傳遞性不成立因?yàn)閤=x,所以自反性成立；因此反自反性不成立；因?yàn)閨x-y|=1,所以|y-x|=1,因此對(duì)稱性成立；所以反對(duì)稱性不成立；因?yàn)閨1-2|=1,|2-3|=1,但|1-3|=2,所以傳遞性不成立因?yàn)閤x=xx,所以自反性不成立；反自反性成立；因?yàn)閤2>y2成立,那么y2>x2就不成立,所以對(duì)稱性不成立,反對(duì)稱性成立；傳遞性成立設(shè)R是集合A上的一個(gè)二元關(guān)系,合于xRy∧yRz=>~xRz,稱R是A上的一個(gè)反傳遞關(guān)系.試舉一個(gè)實(shí)際的反傳遞關(guān)系的例子解：比如在人群集合上,建立父子關(guān)系,那么就是一個(gè)反傳遞關(guān)系,因?yàn)槿绻资且业母赣H,乙是丙的父親,那么甲和丙就一定不存在父子關(guān)系；另外,在正整數(shù)域上建立的倍數(shù)關(guān)系,也是一個(gè)反傳遞關(guān)系,因?yàn)槿绻鸻是b的2倍,b是c的2倍,那么a一定不是c的2倍設(shè)R和S都是集合A上的二元關(guān)系,它們經(jīng)過(guò)關(guān)系運(yùn)算后得到A上的一個(gè)新關(guān)系.試判別當(dāng)R和S同時(shí)具有下表左列某種指定性質(zhì)時(shí),經(jīng)過(guò)指定的運(yùn)算后所得到新關(guān)系也仍保持這種性質(zhì),把所得結(jié)論以√,×的形式填在下表中相應(yīng)的位置上R∩SR∪SR-SR○S-RR-1自反性√√×√×√反自反性√√√××√對(duì)稱性√√√×√√反對(duì)稱性√×√××√傳遞性√××××√自反性的保持情況說(shuō)明：因?yàn)镽,S都具有自反性,所以IAR,IAS,因此IAR∩S,IAR∪S,所以自反性在R∩S,R∪S上保持因?yàn)镮AS,所以IA不是S補(bǔ)集的子集,因此也不是R∩-S的子集,所以自反性在R-S上不保持因?yàn)镽,S是自反的,所以對(duì)任意的a∈A,〔a,a∈R,S,所以〔a,a∈R○S,因此自反性在R○S上保持因?yàn)椤瞐,a∈R,所以〔a,a不屬于-R,所以-R不具有自反性因?yàn)椤瞐,a∈R,所以〔a,a∈R-1,因此R-1具有自反性反自反性的保持情況說(shuō)明：因?yàn)镽,S都具有反自反性,等價(jià)于IA∩R=Φ,IA∩S=Φ因?yàn)镮A∩R∩S=Φ,IA∩〔R∪S=Φ,所以R∩S,R∪S都是反自反的因?yàn)镮A∩R∩-S=Φ,所以R-S也是自反的對(duì)于R○S,假設(shè)〔a,b∈R,〔b,a∈S,那么〔a,a∈R○S,所以反自反在R○S上不一定保持因?yàn)椤瞐,a不屬于R,所以〔a,a一定屬于-R,所以-R一定是自反的,一定不是反自反的因?yàn)椤瞐,a不屬于R,所以〔a,a也不屬于R-1,因此R-1一定是反自反的對(duì)稱性的保持情況說(shuō)明：因?yàn)镽,S是對(duì)稱的,所以R=R-1,S=S-1因?yàn)椤睷∩S-1=R-1∩S-1=R∩S,所以R∩S具有對(duì)稱性因?yàn)椤睷∪S-1=R-1∪S-1=R∪S,所以R∪S具有對(duì)稱性因?yàn)椤睷-S-1=〔R∩-S-1=R-1∩〔-S-1=R-1∩-S-1=R∩S,所以R-S具有對(duì)稱性因?yàn)?lt;R○S>-1=S-1○R-1=S○R,但S○R通常情況下與R○S不相同,所以對(duì)稱性不一定保持,例如：R={<a,b>,<b,a>},S={<b,c>,<c,b>},則R○S={〔a,c},并不對(duì)稱因?yàn)椤?R-1=-R-1=-R,所以R的補(bǔ)是對(duì)稱的因?yàn)镽逆的逆就是R,既等于R的逆,所以R的逆是對(duì)稱的反對(duì)稱性的保持情況說(shuō)明：因?yàn)镽,S是反對(duì)稱的,所以R∩R-1IAS∩S-1IA因?yàn)椤睷∩S∩〔R∩S-1=〔R∩R-1∩〔S∩S-1IA,所以R∩S具有反對(duì)稱性因?yàn)槿绻鸕={<a,b>}S={<b,a>},都是反對(duì)稱的,但R∪S={<a,b>,<b,a>}是對(duì)稱的,所以R∪S不一定再保持對(duì)稱性因?yàn)镽是反對(duì)稱的,而R-S在R的基礎(chǔ)上減少集合元素,因此也一定是反對(duì)稱的因?yàn)槿绻鸕={<a,b>,<c,a>},S={<b,c>,<a,a>},那么R○S={〔a,c,〔c,a},變?yōu)閷?duì)稱的,所以反對(duì)稱性,在復(fù)合運(yùn)算下不一定保持傳遞性的保持情況說(shuō)明：因?yàn)镽,S是傳遞的,所以R2R,S2S因?yàn)椤睷∩S2=〔R∩S○〔R∩SR2∩S2∩<R○S>∩<S○R>R∩S,所以傳遞性保持如果R={<a,b>},S={<b,c>},都是傳遞關(guān)系,但R∪S={<a,b>,<b,c>}不再是傳遞關(guān)系,所以傳遞性在R∪S上不一定保持如果R={<a,b>,<b,c>,<a,c>},S={<a,c>},分別是兩個(gè)傳遞關(guān)系,但R-S={<a,b>,<b,c>}不再是傳遞關(guān)系,所以傳遞性在R-S上不一定保持如果R={<a,b>,<c,d>},S={<b,c>,<d,e>},分別是兩個(gè)傳遞關(guān)系,但R○S={<a,c>,<c,e>}不再是傳遞關(guān)系,所以傳遞性在R○S上不一定保持如果A={a,b,c},R={<a,b>},那么–R=A×A–R,顯然不是傳遞的,所以傳遞性在-R上不一定保持因?yàn)镽2R,所以〔R2-1R-1,即〔R-12R-1,所以傳遞性在逆運(yùn)算下保持判定滿足下述每一種條件的關(guān)系是否存在,如果存在,舉例說(shuō)明〔1既是自反的又是反自反的答：不存在,因?yàn)閷?duì)集合中任意元素x而言,〔x,x∈R,和〔x,x不屬于R,不能同時(shí)成立〔2既是對(duì)稱的又是反對(duì)稱的答：存在,凡是RIA,的關(guān)系,既是對(duì)稱的,又是反對(duì)稱的〔3既是傳遞的又是反傳遞的答：存在,例如A={a,b,c},則A上關(guān)系R={<a,b>},是傳遞的,也是反傳遞的,因?yàn)榇岁P(guān)系滿足這兩個(gè)關(guān)系性質(zhì)的定義既是自反的,反對(duì)稱的,又是傳遞的答：存在,例如在整數(shù)集合上,定義的小于等于關(guān)系,就是一個(gè)自反的,反對(duì)稱的,傳遞關(guān)系設(shè)R是集合A上的一個(gè)二元關(guān)系,證明〔1R是自反的IAR證明:R是自反的=>IAR因?yàn)?R是自反的,所以對(duì)任意的A中元素a,有〔a,a∈R,即IA中任意元素都屬于R,所以IARIAR=>R是自反的因?yàn)?對(duì)任意的A中元素a,有〔a,a∈IA,又IAR,所以〔a,a∈R,所以R是自反的綜上所述,R是自反的IAR〔2R是反自反的IA∩R=Φ證明：R是反自反的=>IA∩R=Φ因?yàn)?IA中的任意元素<a,a>,都不屬于R,所以IA∩R=ΦIA∩R=Φ=>R是反自反的因?yàn)镮A∩R=Φ,所以IA中的任意元素<a,a>,都不屬于R,即對(duì)任意的A中元素a,有〔a,a∈IA,都不屬于R,所以R是反自反的綜上所述,R是反自反的IA∩R=Φ〔3R是對(duì)稱的R=R-1證明：R是對(duì)稱的=>R=R-1因?yàn)閷?duì)R中的任意元素〔a,b,應(yīng)為R是對(duì)稱的,所以〔b,a∈R,那么〔a,b∈R-1,所以RR-1因?yàn)閷?duì)R-1中的任意元素〔a,b,那么〔b,a∈R,因?yàn)镽是對(duì)稱的,那么〔a,b∈R,所以R-1R所以R=R-1R=R-1=>R是對(duì)稱的對(duì)R中的任意元素〔a,b,因?yàn)镽=R-1,所以〔a,b也屬于R-1,所以〔b,a∈R,因此R是對(duì)稱的綜上所述,R是對(duì)稱的R=R-1〔4R是反對(duì)稱的R∩R-1IA證明:R是反對(duì)稱的=>R∩R-1IA因?yàn)閷?duì)任意<a,b>∈R∩R-1,那么其就同時(shí)屬于R和R-1,那么〔b,a也屬于R,根據(jù)反對(duì)稱的定義,a=b,所以〔a,b∈IA,所以R∩R-1IAR∩R-1IA=>R是反對(duì)稱的假設(shè)R不是反對(duì)稱的,那么必定存在a≠b∧<a,b>∈R∧<b,a>∈R,那么〔a,b∈R∩R-1,但〔a,b不屬于IA,矛盾；因此R必是反對(duì)稱的綜上所述,R是反對(duì)稱的R∩R-1IAR是傳遞的R2R證明：R是傳遞的=>R2R因?yàn)閷?duì)任意〔a,b∈R2,必存在c,使得〔a,c,<c,b>屬于R,因?yàn)镽是傳遞的,所以<a,b>屬于R,因此R2RR2R=>R是傳遞的因?yàn)閷?duì)任意的R中的元素〔a,b,<b,c>,那么<a,c>必定屬于R2,也就屬于R,所以R是傳遞的綜上所述,R是傳遞的R2R設(shè)A={1,2,3,4},定義A上的關(guān)系R={<a,b>|a=b+2},S={<x,y>|y=x+1∨x=2y}求：R.S,R.S-1.R,R2,<S-1>2解：根據(jù)題意,R={<3,1>,<4,2>},S={<4,2>,<1,2>,<2,3>,〔3,4}所以：R.S={〔3,2,〔4,3}S-1={〔2,4,〔2,1,〔3,2,〔4,3}所以：R.S-1={<4,4>,<4,1>} R.S-1.R={<4,2>} R2= <S-1>2 ={<2,3>,<3,4>,<3,1>,<4,2>}設(shè)A={a,b,c,d,e,f,g,h},A上的二元關(guān)系R對(duì)應(yīng)的關(guān)系圖4-5所示,求使Rm=Rn的最小整數(shù)m和n<m<n>答：R=R16；簡(jiǎn)要說(shuō)明如下：本關(guān)系圖分為兩個(gè)部分,R=R1∪R2,因?yàn)镽1.R2=R2.R1=,所以R2=R12∪R22,同理Rn=R1n∪R2n,又因?yàn)镮1=R13,I2=R25；3,5的最小公倍數(shù)為15,所以I=R15,所以R=RoI=RoR15=R16設(shè)R是集合A上的二元關(guān)系,證明：〔1IAn=IA證明：因?yàn)閱挝魂P(guān)系的關(guān)系矩陣為單位矩陣,而復(fù)合運(yùn)算就是矩陣的乘法,根據(jù)單位矩陣的性質(zhì),IAn=IA〔2IAoR=RoIA=R證明：同上,因?yàn)閱挝痪仃囎蟪?、右乘一個(gè)矩陣,結(jié)果不變；所以IAoR=RoIA=R〔3<R∪IA>n=IA∪R∪R2∪R3…∪Rn證明：根據(jù)書中并集關(guān)系復(fù)合的定理〔4.2,展開(kāi),并利用上述1,2的結(jié)論,及可得證證明定理4.7,4.8定理4.7設(shè)R1,R2是集合A上的二元關(guān)系,且R1?R2,則r<R1>?r<R2>,s<R1>?s<R2>,t<R1>?t<R2>證明：因?yàn)镽1?R2所以,對(duì)任意<a,b>r<R1>,那么〔a,bR1或〔a,bIa,所以〔a,bR2或〔a,bIa,因此<a,b>r<R2>,所以r<R1>?r<R2>所以,對(duì)任意<a,b>s<R1>,那么〔a,bR1或〔a,bR1’,所以〔a,bR2或〔a,bR2’,因此<a,b>s<R2>,所以s<R1>所以,對(duì)任意<a,b>t<R1>,則必有<a,b>R1j