離散數(shù)學(xué)22060VIP

1、第1章習(xí)題解答11 除（3），（4），（5），（11）外全是命題，其中，（1），（2），（8），（9），（10），（14），（15）是簡(jiǎn)單命題，（6），（7），（12），（13）是復(fù)合命題。分析首先應(yīng)注意到，命題是陳述句，因而不是陳述句的句子都不是命題。本題中，（3）為疑問句，（5）為感嘆句，（11）為祈使句，它們都不是陳述句，所以它們都不是命題。其次，（4）這個(gè)句子是陳述句，但它表示的判斷結(jié)果是不確定。又因?yàn)椋?），（2），（8），（9），（10），（14），（15）都是簡(jiǎn)單的陳述句，因而作為命題，它們都是簡(jiǎn)單命題。（6）和（7）各為由聯(lián)結(jié)詞“當(dāng)且僅當(dāng)”聯(lián)結(jié)起來的復(fù)合命題，（12）是由聯(lián)結(jié)詞

2、“或”聯(lián)結(jié)的復(fù)合命題，而（13）是由聯(lián)結(jié)詞“且”聯(lián)結(jié)起來的復(fù)合命題。這里的“且”為“合取”聯(lián)結(jié)詞。在日常生活中，合取聯(lián)結(jié)詞有許多表述法，例如，“雖然，但是”、“不僅，而且”、“一面，一面”、“和”、“與”等。但要注意，有時(shí)“和”或“與”聯(lián)結(jié)的是主語，構(gòu)成簡(jiǎn)單命題。例如，（14）、（15）中的“與”與“和”是聯(lián)結(jié)的主語，這兩個(gè)命題均為簡(jiǎn)單命題，而不是復(fù)合命題，希望讀者在遇到“和”或“與”出現(xiàn)的命題時(shí)，要根據(jù)命題所陳述的含義加以區(qū)分。12 （1）p : 2是無理數(shù)，p為真命題。（2）p : 5能被2 整除，p為假命題。（6）p q 。其中， p : 2是素?cái)?shù)，q：三角形有三條邊。由于p 與q都是真

3、命題，因而p q 為假命題。（7）p q ，其中，p：雪是黑色的，q：太陽從東方升起。由于p為假命題，q 為真命題，因而p q 為假命題。（8）p : 2000年10月1 日天氣晴好，今日（1999 年2 月13日）我們還不（10）p：小李在宿舍里. p 的真值則具體情況而定，是確定的。（12）p q，其中，p : 4是偶數(shù)，q : 4是奇數(shù)。由于q是假命題，所以，q 為假命題，p q 為真命題。（13） p q ，其中， p : 4是偶數(shù)，q : 4是奇數(shù)，由于q是假命題，所以， p q為假命題。（14） p：李明與王華是同學(xué)，真值由具體情況而定（是確定的）。（15） p：藍(lán)色和黃色可以調(diào)配

4、成綠色。這是真命題。分析命題的真值是唯一確定的，有些命題的真值我們立即可知，有些則不能馬上知道，但它們的真值不會(huì)變化，是客觀存在的。13 令p : 2 + 2 = 4,q : 3 + 3 = 6,則以下命題分別符號(hào)化為（1）p q（2）p ¬q（3）¬p q（4）¬p ¬q（5）p q（6）p ¬q（7）¬p q（8）¬p ¬q以上命題中，（1），（3），（4），（5），（8）為真命題，其余均為假命題。分析本題要求讀者記住p q 及p q 的真值情況。p q 為假當(dāng)且僅當(dāng)p 為真,q為假,而p q為真當(dāng)且僅當(dāng)p 與

5、q 真值相同.由于p 與q都是真命題，在4 個(gè)蘊(yùn)含式中，只有（2）p r，其中，p同（1），r：明天為3 號(hào)。15 （1）p q，其中，p：2 是偶數(shù)，q：2是素?cái)?shù)。此命題為真命題。（2）p q ，其中，p：小王聰明，q：小王用功（3）p q，其中，p：天氣冷，q：老王來了（4）p q ，其中，p：他吃飯，q：他看電視（5）p q ，其中，p：天下大雨，q：他乘公共汽車上班（6）p q ，其中，p，q的含義同（5）（7）p q ，其中，p，q的含義同（5）（8）¬p ¬q，其中，p：經(jīng)一事，q：長(zhǎng)一智分析1°在前4 個(gè)復(fù)合命題中，都使用了合取聯(lián)結(jié)詞，都符號(hào)化為合取

6、式，這正說明合取聯(lián)結(jié)詞在使用時(shí)是很靈活的。在符號(hào)化時(shí)，應(yīng)該注意，不要將聯(lián)結(jié)詞部分放入簡(jiǎn)單命題中。例如，在（2）中，不能這樣寫簡(jiǎn)單命題：p：小王不但聰明，q：小王而且用功。在（4）中不能這樣寫：p：他一邊吃飯， q：他一邊看電視。2° 后4 個(gè)復(fù)合命題中，都使用了蘊(yùn)含聯(lián)結(jié)詞，符號(hào)化為蘊(yùn)含式，在這里，關(guān)鍵問題是要分清蘊(yùn)含式的前件和后件。p q 所表達(dá)的基本邏輯關(guān)系為，p 是q的充公條件，或者說q 是p的必要條件，這種邏輯關(guān)系在敘述上也是很靈活的。例如，“因?yàn)閜，所以q”，“只要p，就q”“p 僅當(dāng)q”“只有q 才p”“除非q，否則¬p”“沒有q，就沒有p”等都表達(dá)了q 是p 的

7、必要條件，因而都符號(hào)化為p q 或¬p ¬q 的蘊(yùn)含式。在（5）中，q 是p 的必要條件，因而符號(hào)化為p q，而在（6）（7）中，p 成了q 的必要條件，因而符號(hào)化為q p 。在（8）中，雖然沒有出現(xiàn)聯(lián)結(jié)詞，但因兩個(gè)命題的因果關(guān)系可知，應(yīng)該符號(hào)化為蘊(yùn)含式。001，111 題中指派p, q為0, r為1，于是就是考查001是該公式p (q r )的成真賦值，還是成假賦值，易知001 是它的成假賦值。2° 在公式（2），（3），（4）中均含4 個(gè)命題就項(xiàng)，因而共有24 = 16個(gè)賦值：0000，0001，1111。現(xiàn)在考查0011 是它的成假賦值。1.7 （1），（2

8、），（4），（9）均為重言式，（3），（7）為矛盾式，（5），（6），（8），（10）為非重言式的可滿足式。一般說來，可用真值表法、等值演算法、主析取范式（主合取范式）法等判斷公式的類型。（1）對(duì)（1）采用兩種方法判斷它是重言式。真值表法表1.2 給出了（1）中公式的真值表，由于真值表的最后一列全為1，所以，（1）為重言式。p q r p q r p(p q r)0 0 0 0 10 0 1 1 10 1 0 1 10 1 1 1 11 0 0 1 11 0 1 1 11 1 0 1 11 1 1 1 1等值演算法p ( p q r ) ¬p ( p p r ) （蘊(yùn)含等值式） (&

9、#172;p p ) p r （結(jié)合律）1q r （排中律）由最后一步可知，（1）為重言式。（2）用等值演算法判（2）為重言式。( p ¬p ) ¬p(¬p ¬)¬p （蘊(yùn)含等值式） ¬p ¬p （等冪律） p ¬p （蘊(yùn)含等值式）1 （排中律）（3）用等值演算法判（3）為矛盾式¬( p q ) q ¬(p¬q ) q （蘊(yùn)含等值式） p ¬q q （德·摩根律） p (¬q q) （結(jié)合律） p 0 （矛盾律） 0 （零律）由最后一步可知，（3）為矛盾式

10、。（5）用兩種方法判（5）為非重言式的可滿足式。真值表法p q ¬p ¬p q q ¬p(¬p q)(q ¬p)0 0 1 0 1 10 1 1 1 1 11 0 0 1 1 11 1 0 1 0 0由表1.3 可知（5）為非重言式的可滿足式。 ( p q) (¬q ¬p)¬(p q) (¬q ¬p) (¬p ¬q ) ¬q ¬p ¬p ¬q (¬p 1) (1 ¬q)(¬p (¬q q) (&#

11、172;p p) ¬q) (¬p ¬q ) (¬p q ) (¬p ¬q ) ( p ¬q )(¬p ¬q)(¬p q) (¬p ¬q)0 1 2 m m m .在（3）的主析取范式中不含全部（4 個(gè)）極小項(xiàng)，所以（3）為非重言式的可滿足式，請(qǐng)讀者在以上演算每一步的后面，填上所用基本的等值式。其余各式的類型，請(qǐng)讀者自己驗(yàn)證。分析1o 真值表法判斷公式的類別是萬能。公式A為重言式當(dāng)且僅當(dāng)A的真值表的最后一旬全為1；A 為矛盾式當(dāng)且僅當(dāng)A 的真值表的最后一列全為0；A為非重言式的

12、可滿足式當(dāng)且僅當(dāng)A 的真值表最后一列至少有一個(gè)1，又至少有一個(gè)0。真值表法不易出錯(cuò)，但當(dāng)命題變項(xiàng)較多時(shí)，真值表的行數(shù)較多。2o 用等值演算法判斷重言式與矛盾式比較方例，A為重言式當(dāng)且僅當(dāng)A與1 等值；A 為矛盾式當(dāng)且僅當(dāng)A 與0 等值，當(dāng)A 為非重言式的可滿足式時(shí)，經(jīng)過等值演算可將A 化簡(jiǎn)，然后用觀察法找到一個(gè)成真賦值，再找到一個(gè)成假賦值，就可判斷A 為非重言式的可滿足式了。例如，對(duì)（6）用等值演算判斷它的類型。( p ¬p )q 0q （矛盾律）(p q) (q 0) （等價(jià)等值式）1¬q （零律） ¬q （同一律）到最后一步已將公式化得很簡(jiǎn)單。由此可知，無論p

13、 取0 或1 值，只要q 取0 值，原公式取值為1，即00 或10 都為原公式的成真賦值，而01，11 為成假賦值，于是公式為非重言式的可滿足式。用主析取范式判斷公式的類型也是萬能的。A 為重言式當(dāng)且僅當(dāng)A 的主析取范式含2n（n為A 中所含命題變項(xiàng)的個(gè)數(shù)）個(gè)極小項(xiàng)；A為矛盾式當(dāng)且僅當(dāng)A的主析取范式中不含任何極小項(xiàng)，記它的主析取范式為0；A 為非重言式的可滿足式當(dāng)且僅當(dāng)A 的主析取范式中含極小項(xiàng)，但不是完全的。當(dāng)命題變項(xiàng)較多時(shí)，用主析取范式法判公式的類型，運(yùn)算量是很大的。用主合取范式判斷公式的類型也是萬能的。A 為重言式當(dāng)且僅當(dāng)A 的主合取范式中不含任何極大項(xiàng)，此時(shí)記A 的主合取范式為1；A

14、為矛盾式當(dāng)且僅當(dāng)A 的主合取范式含2n個(gè)極大項(xiàng)（n 為A中含的命題變項(xiàng)的個(gè)數(shù)）；A 為非重言式的可滿足式當(dāng)且僅當(dāng)A 的主析取范式中含含極大項(xiàng)，但不是全部的。1.8 （1）從左邊開始演算( p q ) ( p ¬q) p (q ¬q ) （分配律） p 1 （排中律） p. （同一律）（2）從右邊開始演算p (q r )¬p (q r) （蘊(yùn)含等值式） (¬p q) (¬p r ) （分配律）¬( p q )(p q) (q p) ¬(¬p q ) (¬p q) ¬(¬p ¬q

15、 ) ( p q )(p q)¬(p q).請(qǐng)讀者填上每步所用的基本等值式。本題也可以從右邊開始演算(p q)¬(p q) ¬¬( p q ) ¬( p q ) ¬(¬( p q ) ¬¬(p q)¬(¬p ¬q) (p q) ¬(¬p q) (¬p q ) (¬q p) (¬q q)¬(1 p q) (¬q p) 1 ¬( p q) (q p) ¬( p q).讀者填上每步所用的基本的

16、等值式。1.9 （1）¬( p q) p) ¬(¬( p q ) p （蘊(yùn)含等值式）¬(¬(p q) p) （德·摩根律） ¬(¬p q ) (¬p) (q ¬q ) ( p q) 0. （零律）由最后一步可知該公式為矛盾式。（2）( p q) (q p) ( p q )¬(¬(p q) p) （蘊(yùn)含等值式）由于較高層次等價(jià)號(hào)兩邊的公式相同，因而此公式無成假賦值，所以，它為重言式。（3）(¬p q)(q ¬p) ( p q) (¬q ¬

17、p ) （蘊(yùn)含等值式）¬(p q) (¬q ¬p) （蘊(yùn)含等值式） (¬p q) ¬q ¬p （德·摩根律） ¬q ¬p （吸收律） ¬p ¬q. （交換律）由最后一步容易觀察到，11 為該公式成假賦值，因而它不是重言式，又00，01，10 為成真賦值，因而它不是矛盾式，它是非重言式的可滿足式。1.10 題中給出的F，G，H，R 都是2 元真值函數(shù)。給出的5 個(gè)聯(lián)結(jié)詞集都是全功能集，可以用觀察法或等值演算法尋找與真值函數(shù)等值的公式。首先尋找在各聯(lián)結(jié)詞集中與F 等值的公式。（1）設(shè)A =

18、 ¬( p q )，易知A 是¬,中公式且與F 等值，即F A.（2）設(shè)B = p ¬q，易知B 是¬,中公式且與F 等值，即F B.（3）設(shè)C = ¬(¬p q)，易知C 是¬,中公式，且F C.（4）設(shè)D = ( p (q q) ( p (q q)，易知D 為中公式，且F D.（5）設(shè)E = ( p p) q ，易知E 為中公式，且F E.分析1° 只要找到一個(gè)聯(lián)結(jié)詞集中與F 等值的公式，經(jīng)過等值演算就可以進(jìn)行等值演算，消去聯(lián)結(jié)詞 ，用¬ ， 取代，得A = ¬( p q )¬(&

19、#172;p q) p ¬q記為B.則B 為¬,中公式，且F B。再對(duì)A 進(jìn)行等值演算，消去，用¬， 取代，得A =¬(p q) ¬(¬p q)記為C.則C 為¬,中公式，且F C 。再對(duì)B 進(jìn)行演算，消去¬，用取代，在演算中，注意，對(duì)于任意的公式A，有¬A ¬(A A) A A.B = p ¬q p (q q ) ¬¬( p (q q) ¬( p (q q) ( p (q q) (p (q q )記為D.則D 為中公式，且F D.再對(duì)C 進(jìn)行演算，消去&

20、#172;,用取代，在演算中注意，對(duì)于任意的公式A¬A ¬(A A) A A.C = ¬(¬p q) ¬p q ( p p ) q記為E.2° 開始找一個(gè)與某真值函數(shù)等值的公式的方法，除觀察法外，就是根據(jù)該真值函數(shù)的真值表，求它的主析取范式，而后進(jìn)行等值演算即可。例如，由G的真值表可知G 的主析取范式為1 3 m m ，于是1 3 G m m(¬p q) (p q) (¬p p) q q.由于公式q 不帶聯(lián)結(jié)詞，所以，它應(yīng)該為任何聯(lián)結(jié)詞集中的合式公式。3° 在各聯(lián)結(jié)詞集中找到的與某真值函數(shù)等值的公式并不唯

21、一。例如，取A = ¬q q. (¬,中公式)B = q q. (¬,中公式)C = q q. (¬,中公式)D = (q q ) (q q). (中公式)E = (q q) (q q ). (中公式)則G A B C D E,對(duì)于同一個(gè)真值函數(shù)G ，找到與它等值的形式各異的公式。對(duì)于H 和R，請(qǐng)讀者自己去完成。1.11 （1）對(duì)C 是否為矛盾式進(jìn)行討論。當(dāng)C 不是矛盾式時(shí)，A C B C，則一定有A B ，這是因?yàn)?，此時(shí)，A C A,B C B，所以，有A A C B B必有A B而當(dāng)C 不是矛盾式時(shí)，A C B C ，不一定有A B ，舉反例如下：表

22、1.4p q A B C AVC BVC0011010100100011001100110011(2) 對(duì)C 是否為重言式進(jìn)行討論:若C 為重言式,則A C A,C B,于是A A C B C B.因而有A B當(dāng)C 不是重言式時(shí),請(qǐng)讀者舉反例說明, A C B C 時(shí), 不一定有A B .(3) 若¬A¬B,則A B .證明如下:A ¬¬A (雙重否定律) ¬¬B ( ¬A ¬B ) B (雙重否定律)所以A B1.12 (1) 設(shè)(1)中公式為A.A ( p (q r ) ( p q r )A¬(p (

23、q r ) (p q r)A ¬p (¬q ¬r ) ( p q r )A(¬p ¬q) (¬q ¬r) (p q r)0 1 7 A m m m于是,公式A 的主析取范式為0 1 2 7 m m m m易知,A 的主合取范式為3 4 5 6 M M M MA 的成真賦值為000, 001, 010, 111A 的成假賦值為011,100,101,110(2)設(shè)(2)中公式為BB (¬p q ) (¬q p )(¬¬p q)(¬q p) ( p q ) (¬q p)

24、 ¬( p q ) (¬q p)(¬p ¬q) ¬q p ¬q p (吸收律)(¬p q)¬) p (¬q p) (¬p ¬q) p ( p ¬q ) (p q )0 2 3 m m m所以,B 的主析取范式為0 2 3 m m m .B 的主合取范式為1 MB 的成真賦值為00,10,11.B 的成假賦值為01.(p ¬q)q r p (¬q q)r p 0r 0.所以,C 的主析取范式為0.C 的主合取范式為0 1 2 3 M M M MC 的成假賦值

25、為00,01,10,11C 無成真賦值,C 為矛盾式.分析1°設(shè)公式A 中含n(n 1)個(gè)命題變項(xiàng),且A 的主析取范式中含l (0 l 2n )個(gè)極小項(xiàng),則A的主合鄧范式中含2n l 個(gè)極大項(xiàng),而且極大項(xiàng)的角標(biāo)分別為0 到2n 1這2n個(gè)十進(jìn)制數(shù)中未在A的主析取范式的極小項(xiàng)角標(biāo)中出現(xiàn)過的十進(jìn)制數(shù).在(1)中,n=3,A 的主析取范式中含4 個(gè)極小項(xiàng),所以,A 的主合取范式中必含23 4 = 4個(gè)極大項(xiàng),它們的角標(biāo)為0到7 中未在主析取范式的極小項(xiàng)角標(biāo)中出現(xiàn)過的3,4,5,6. 這樣,只要知道A 的主析取范式,它的主合鄧范式自然也就知道了在(2),(3)中情況類似.2° A

26、的主析取范式中極小項(xiàng)角標(biāo)的二進(jìn)制表示即為A 的成真賦值.在(1)中由于主析取范式中的極小項(xiàng)角標(biāo)分別為0,1,2,7,它們的二進(jìn)制表示分別為000,001,010,111,所以,A 的成真賦值為以上各值.類似地,A 的主合取范式中所含極大項(xiàng)角標(biāo)的二進(jìn)制表示,即為A 的成假賦值.1.13 (1) 首先求p (q r )的主析取范式.p (q r) ¬p (¬q r )¬p ¬q r)中含3 個(gè)命題變項(xiàng),所以,極小項(xiàng)長(zhǎng)度為3.¬p ¬p (¬q q) (¬r r )(¬p ¬q r) (¬p

27、 ¬q r) (¬p q ¬r ) (¬p ¬q r )0 1 2 3 m m m m¬p (¬p p)¬q (¬r r) (¬p ¬q ¬r ) (¬p ¬q r ) (¬p ¬q ¬r) (p ¬q r)0 1 4 5 m m m mr (¬p p) (¬q q ) r(¬p ¬q r) (¬p ¬q r) ( p ¬q r ) ( p q r

28、 )1 31 5 7 m m m m0 1 2 3 4 5 7 p (q r ) m m m m m m m類似地,可求出q (p r)主的析取范式也為上式,由于公式的主析取范式的唯一性,可知,(p (q r )(q (p r).(2) p q ¬(p q) ¬p ¬q (¬p (¬q q ) (¬p p) ¬q) (¬p ¬q) (¬p q ) (p ¬p). 0 1 2 m m mp q¬(p q) ¬p ¬q. 0 m由于p q與p q 的主析取范式

29、不同.因而它們不等值,即p q p q .1.14 設(shè)p:A 輸入;設(shè)q:B 輸入;設(shè)r:C 輸入;由題的條件,容易寫出A B C F ,F ,F 的真值表,見表1.5所示.由真值表分別寫出它們的主析范鄧范式,而后,將它們都化成與之等值的中的公式即可.表1.5p q r A F B F C F0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1000011110011000001000000F ( p q r ) ( p q r ) (p q r ) ( p q r ) A ¬ ¬ ¬ ¬ p ¬¬( p

30、q) ¬( p q ) ¬( p q ) ( p q) ( p p)FB ( p q r ) ( p q r ) ¬ ¬ ¬ (¬p q ) (¬r r )(¬p q) ¬¬(¬p q ) ¬( p ¬q) p ¬q) p (q q) .F ( p p r ) C ¬ ¬ ¬(p q) r ( p q ) r ¬¬( p q ) r ¬(¬( p q ) ¬r ¬(

31、p q) ¬r ( p q ) ( p q) (r r ) 分析在將公式化成或中公式時(shí),應(yīng)分以下幾步:(1)先將公式化成全功能集¬,中的公式.或¬A ¬(A A) A A.使用雙重否定律A B ¬¬(A B ) ¬(A B ) (A B) (A B)或A B ¬¬(A B ) ¬(A B ) (A B) (A B)使用德·摩根律A B ¬¬(A B)¬(¬A ¬B) ¬A ¬B (A A) (B B )或A B &#

32、172;¬(A B ) ¬(¬A ¬B) ¬A ¬B (A A) (B B )115 設(shè)p：礦樣為鐵；q：礦樣為銅；r：礦樣為錫.設(shè)( ) ( ) ( ) 1 F 甲全對(duì) 乙對(duì)一半 丙全錯(cuò)，(¬p ¬q) (¬p ¬r) (p r) (¬p r) (¬p ¬q ¬p ¬r ¬p r ) (¬p ¬q p r ¬p r ) 0 0 0 . (¬p ¬q p ¬r p r ) (&

33、#172;p ¬q p r ¬p ¬r)( ) ( ) ( ) 3 F 甲對(duì)一半 乙全對(duì) 丙全錯(cuò) (¬p q ) ( p ¬q ) (¬p r ) (¬p ¬r )(¬p q ¬p r ¬p r ( p ¬q ¬p r ¬p r )(¬p q r ) 0 ¬p q r.F4 (甲對(duì)一半) (乙全錯(cuò)) (丙全對(duì)) (¬p q) ( p ¬q ) ( p ¬r ) ( p ¬r )(¬p q

34、¬¬r p ¬r ( p ¬q p ¬r p ¬r ) 0 ( p ¬q ¬r ) p ¬q ¬r.( ) ( ) ( ) 5 F 甲會(huì)錯(cuò) 乙對(duì)一半 丙全對(duì) ( p q ) (¬p ¬r ) (p r ) ( p ¬r ) ( p q ¬p ¬r p ¬r (p q p r p ¬r ) 0 0 0.( ) ( ) ( ) 6 F 甲全錯(cuò) 乙全對(duì) 丙對(duì)一半 0 0 0 ( p q ¬p r p r (p q 

35、2;p r ¬p ¬r) 0 0 0.設(shè)F (一人全對(duì)) (一人對(duì)一半) (一人全錯(cuò))則F 為真命題，并且1 2 3 4 5 6 F F F F F F F (¬p q r ) (p ¬q ¬r ) 1.但，礦樣不可能既是銅又是錫，于是q,r中必有假命題，所以¬p q r 0,因而必有p ¬q ¬r 1.于是，必有P 為真，q 與r 為假，即礦樣為鐵。1.16 令p：今天是1 號(hào)；q：明天是5 號(hào).由于本題給出的推理都比較簡(jiǎn)單，因而可以直接判斷推理的形式結(jié)構(gòu)是否為重言式。（1）推理的形式結(jié)構(gòu)為( p q) p q.

36、可以用多種方法判斷上公式為重言式，其實(shí)，本推理滿足假言推理定律，即( p q) p q.所以，推理正確。（2）推理的形式結(jié)構(gòu)為( p q) p q.形式結(jié)構(gòu)不是重方式，故，推理不正確。（3）推理的形式結(jié)構(gòu)為( p q) ¬p ¬q.可以用多種方法證明上面公式為重言式，其實(shí)，它滿足拒取式推理定律，即( p q) ¬p ¬q.所以，推理正確。（4）推理的形式結(jié)構(gòu)為( p q) ¬p ¬q.可以用多種方法證明上公式不是重言式，01 為上公式的成假賦值，所以，推理不正確。分析對(duì)于前提與結(jié)論都比較簡(jiǎn)單的推理，最好直接判推理的形式結(jié)構(gòu)是否為重言式

37、，來判斷推理是否正確，若能觀察出一個(gè)成假賦值，立刻可知，推理不正確。117 (1)證明¬q r 前提引入¬r 前提引入¬q 析取三段論¬( p ¬q) 前提引入¬p q 置換¬p 析取三段論（2）證明p (q s) 前提引入q (q s) 置換q 前提引入r p 置換r s 假言三段論（3）證明 p 附加前提引入p q 前提引入q 假言推理p q 合取或者證明p q 前提引入¬p q 置換(¬p p) (¬p q ) 置換¬p (p q) 置換p (p q) 置換（4）證明 前提引入(

38、s t ) (t s ) 置換 化簡(jiǎn)t r 前提引入ts 假言推理 前提引入(q s) (s q) 置換s q 化簡(jiǎn)p 假言推理r 化簡(jiǎn)p q s r 合取分析由于( ) ( ) 1 2 A A A C B k L ( ) ( ) 1 2 A A A C B k ¬ L ¬ A A A C B k ¬( ) 1 2 LA A A C B k 1 2 L 所以,當(dāng)推理的結(jié)論也為蘊(yùn)含式時(shí),可以將結(jié)論的前件作為推理的前提,稱為附加前提,并稱使用附加前提的證明方法為附加前提證明法.(3)中第一個(gè)證明,即為附加前提證明法.1.18 設(shè)p：他是理科生q：他是文科生r：他學(xué)好數(shù)

39、學(xué)前提p r , ¬q p,¬r結(jié)論q通過對(duì)前提和結(jié)論的觀察，知道推理是正確的，下面用構(gòu)造證明法給以證明。證明 p r 前提引入¬r 前提引入¬p 拒取式¬q p 前提引入¬¬q 拒鄧式q 置理p (q ¬r )2 4 5 6 7 m m m m m所以，成真賦值為010，100，101，110，111，由給也，成假賦值為000，001，011，由給出，公式是非重言式的可滿足式，由給出。120 答案A：； B：； C：分析解本題的方法不限于求主析取范式或主合取范式，也可以利用真值表法。方法1： 求主析取范式

40、2;( p q) r ( p q) r(p q) (r ¬r) (p ¬p) (q ¬q) r1 3 5 6 7 m m m m m從上式可知，¬( p q ) r 的主析取范式中含5 個(gè)極小項(xiàng)。極小項(xiàng)角碼的二進(jìn)制表示為成真賦值，因而成真賦值為001，011，101，110，111。由成真賦值立即可知成假賦值為000，010，100，成假賦值的十進(jìn)制的十進(jìn)表示為極大項(xiàng)的角碼，因而極大項(xiàng)為0 2 4 M ,M ,M ，故有3 個(gè)極大項(xiàng)。方法2：求主合取范式，分析類似主析取范式法。方法3：真值表法由真值表，求出成真賦值，將成真賦值轉(zhuǎn)化成十進(jìn)制數(shù)做為極小項(xiàng)的角

41、碼，這樣就求出了全部極小項(xiàng)，也容易求出極大項(xiàng)。121 答案A：； B：； C：分析可用構(gòu)造證明法解此題。（1） ¬q r 前提引入¬(p ¬q) 前提引入¬p q 置換¬p 析取三段論至此可知¬p 是（1）的邏輯結(jié)論。（2） ¬r s 前提引入¬s 前提引入¬r 析取三段論(p q)r 前提引入¬( p q ) 置換¬p ¬q 置換至此可知¬p ¬q 是（2）的國(guó)邏輯結(jié)論。（3） ¬p q 前提引入p q 置換前提引入¬q r 前提引入

42、q r 置換p r 假言推理r s 前提引入p s 假言推理至此可知p s是（3）的邏輯結(jié)論。122 答案A：分析在本題中，設(shè)A，B，C 分別表示3 個(gè)開關(guān)狀態(tài)的命題變項(xiàng)，開關(guān)的扳鍵向上時(shí)，對(duì)應(yīng)命題變項(xiàng)的真值為1，否則為0，由真值表易知。 ¬A (¬B C) (B ¬C) A (¬B ¬C) (B C) (¬A (B C) (A (¬B C) (B ¬C)(¬A (B C) (A ¬(B ¬C) (¬B C) (¬A (B C) (A ¬(B C) A B

43、 C第2 章習(xí)題解答2.1 本題沒有給出個(gè)體域,因而使用全總個(gè)體域.(1) 令F (x ) : x是鳥G(x) : x會(huì)飛翔.命題符號(hào)化為x (F(x) G(x) .(2)令F (x ) : x為人.G(x) : x愛吃糖命題符號(hào)化為¬x(F(x)G(x)或者x(F(x) ¬G(x)(3)令F (x) : x為人.G(x) : x愛看小說.命題符號(hào)化為x(F(x) G(x) .(4) F (x) : x為人.G(x) : x愛看電視.命題符號(hào)化為¬x (F (x) ¬G(x ) .分析1°如果沒指出要求什么樣的個(gè)體域，就使用全總個(gè)休域，使用全總

44、個(gè)x (F(x) G(x)即用合取聯(lián)結(jié)詞取代蘊(yùn)含聯(lián)結(jié)詞，這是萬萬不可的。將（1）中命題敘述得更透徹些，是說“對(duì)于宇宙間的一切事物百言，如果它是鳥，則它會(huì)飛翔?！币蚨?hào)化應(yīng)該使用聯(lián)結(jié)詞而不能使用 。若使用 ，使（1）中命題變成了“宇宙間的一切事物都是鳥并且都會(huì)飛翔?！边@顯然改變了原命題的意義。3° （2）與（4）中兩種符號(hào)化公式是等值的，請(qǐng)讀者正確的使用量詞否定等值式，證明（2），（4）中兩公式各為等值的。2.2 (1)d (a),(b),(c)中均符號(hào)化為xF(x)其中F(x) : (x +1) 2 = x 2 + 2x +1,此命題在(a ), (b), (c)中均為真命題。（2

45、） 在(a),(b),(c)中均符號(hào)化為xG(x)其中G(x) : x + 2 = 0，此命題在（a）中為假命題，在(b)(c)中均為真命題。（3）在(a),(b),(c)中均符號(hào)化為xH(x)其中H(x) : 5x = 1.此命題在(a),(b)中均為假命題，在(c)中為真命題。分析1°命題的真值與個(gè)體域有關(guān)。2° 有的命題在不同個(gè)體域中，符號(hào)化的形式不同，考慮命題“人都呼吸”。在個(gè)體域?yàn)槿祟惣蠒r(shí)，應(yīng)符號(hào)化為xF(x)這里，F(xiàn) (x) : x呼吸，沒有引入特性謂詞。在個(gè)體域?yàn)槿倐€(gè)體域時(shí)，應(yīng)符號(hào)化為x (F(x) G(x )23 因題目中未給出個(gè)體域，因而應(yīng)采用全總個(gè)體

46、域。（1） 令：F (x) : x是大學(xué)生，G(x) : x是文科生，H(x) : x 是理科生，命題符號(hào)化為x (F(x) (G(x) H (x )（2）令F (x ) : x是人，G(y ) : y是化，H (x) : x 喜歡，命題符號(hào)化為x(F(x) y (G(y ) H (x , y )（3）令F(x ) : x是人，G(x) : x犯錯(cuò)誤，命題符號(hào)化為¬x (F (x) ¬G(x),或另一種等值的形式為x (F(x) G(x )（4）令F(x ) : x在北京工作，G(x) : x是北京人，命題符號(hào)化為¬x(F(x) G(x ),或x(F(x)

47、72;G(x),（5）令F(x ) : x是金屬，G(y ) : y是液體，H (x, y) : x溶解在y中，命題符號(hào)化為x(F(x)y(G(y)H(x, y).（6）令F(x) : x與y 是對(duì)頂角，H(x, y) : x與y 相等，命題符號(hào)化為xy(F (x, y)H(x, y).分析（2），（5），（6）中要使用2 無謂詞，用它們來描述事物之間的關(guān)系。2.4（1）對(duì)所有的x，存在著y，使得x y = 0，在(a), (b )中為真命題，在(c), (d )中為假命題。（3）對(duì)所有x，存在著y，使得x y =1，在(a),(b)(c)中均為假命題，而在(d)中為真命題。（4）存在著x，對(duì)

48、所有的y，都有x y = 1，在(a), (b)(c)(d )中都是假命題。（5）對(duì)所有的x，存在著y，使得x y = x在(a), (b)(c)(d )中都是真命題。（6）存在x，對(duì)所有的y，都有x y = x，在(a),(b)中為真命題，在(c)(d )中為假命題。（7）對(duì)于所有的x和y，存在著z，使得x y = z ，在(a), (b) 中為真命題，在(c)(d )中為假命題。2.5 （1）取解釋1 I 為：個(gè)體域D =R（實(shí)數(shù)集合）， F (x) : x為有理數(shù)，G(x) : x能表示成分?jǐn)?shù)，在I 1下，x (F(x) G(x)的含義為“對(duì)于敘何實(shí)數(shù)x 而言，若x 為有理數(shù)，則x 能表

49、示成分?jǐn)?shù)”，簡(jiǎn)言之為“有理數(shù)都能表示成分?jǐn)?shù)?！痹诖颂N(yùn)含式中，當(dāng)前件F(x)為真時(shí)，后件G(x)也為真，不會(huì)出現(xiàn)前件為真，后件為假的情況，所以在1 I 下，x(F(x) G(x)為真命題。在在I 1下，x (F(x) G(x)的含義為“對(duì)于任何實(shí)數(shù)x,x 既為有理數(shù)，又能表示成分?jǐn)?shù)?！比 = 2 ，則F( 2) g ( 2)顯然為假，所以，在I 1下，x (F(x) G(x)為假命題.(2) 取解釋I 2為:個(gè)體域D=N(自然數(shù)集合), F(x) : x為奇數(shù), G(x) : x為偶數(shù),在2 I 下, x(F (x)G(x)的含義為“存在自然數(shù)x,x 發(fā)既為奇數(shù)，又為偶數(shù)?！比 = 2，則F

50、(2)為假，于是F(2)G(2)為真，這表明x(F(x)G(x)為真命題。x(F(x) G(x) x (F(x) G(x ),這里，A B 表示A 與B 不等值，以后遇到 ，含義相同。在一階邏輯中，將命題符號(hào)化時(shí)，當(dāng)引入特性謂詞（如題中的F(x)之后，全稱量詞 后往往使用聯(lián)結(jié)詞而不使用 ，而存在量詞 后往往使用 ，而不使用，如果用錯(cuò)了，會(huì)將真命題變成假命題，或者將假命題變成真命題。26 在解釋R 下各式分別化為（1）x(x < 0);（2）xy (x y x);（3）xyz(x < y)(x z < y z);（4）xy (x < x 2y ).易知，在解釋R 下，（1

51、），（2）為假；，（3）（4）為真。27 給定解釋I 為：個(gè)體域D=N（自然數(shù)集合），F(xiàn) (x) : x為奇數(shù)，G(x) : x為偶數(shù)。（1）在解釋I 下，公式被解釋為“如果所有的自然數(shù)不是奇數(shù)就是偶數(shù)，則所有自然數(shù)全為奇數(shù)，或所有自然數(shù)全為偶數(shù)?！币?yàn)樘N(yùn)含式的前件為真，后件為假，所以真值為假。（2）在I 下，公式解釋為“如果存在著自然數(shù)為奇數(shù)，并且存在著自然為偶數(shù)，則存在著自然數(shù)既是奇數(shù)，又是偶數(shù)。”由于蘊(yùn)含式的前件為真，后件為假，后以真值為假。分析本題說明全稱量詞對(duì)析取不滿足分配律，存在量詞對(duì)合取不滿足分配律。2.8 令A(yù) = xy(F (x)G(y)L(x, y),在A中，無自由出現(xiàn)的個(gè)

52、體變項(xiàng)，所以A 為閉式?！皩?duì)于任意的整數(shù)x 和y，如果x為正整數(shù)，y 為負(fù)整數(shù)，則x > y ?！边@是真命題。設(shè)解釋I 2：個(gè)體域D=R（R 整數(shù)集合），F(xiàn) (x ) : x為有理數(shù)，G(y ) : y為無理數(shù)，L(x, y ) : x y，在2 I 下，A 的含義為“對(duì)于任意的實(shí)數(shù)x 和y，如果x為有理數(shù)，y 為元理數(shù)，則x y?！边@是假命題。分析閉式在任何解釋下不是真就是假，不可能給出解釋I, 使得閉式在I下真值不確定，這一點(diǎn)是閉式的一個(gè)重要特征。而非封閉的公式就沒有這個(gè)特征。2.9 取( ( , ), ( , ) 1 A = L f x y g x y 和( ( , ), ) 2

53、A = x f x y x ，則1A 和2 A 都是非土產(chǎn)的公式，在1A 中，x, y 都是自由出現(xiàn)的，在A2中，y 是自出現(xiàn)的。取解釋I 為， 個(gè)體域D=N （ N 為自然數(shù)集合） ，f (x, y, ) = x + y,g (x, y) = x y L(x, y )為x = y 。在I 下， 1A 為x + y = x y 為假，所以在I 下， 1A 真值不確定，即在I 下2 A 的真值也是命題。在I 下， A2為x (x + y = x),當(dāng)y = 0時(shí)，它為真；y 0時(shí)為假，在I下A2的真值也不確定。分析非閉式與閉式的顯著區(qū)別是，前者可能在某些解釋下，真值不確定，而后者對(duì)于任何解釋真值

54、都確定，即不是真就是假。當(dāng)然非閉式也可以是邏輯有效式（如F(x) F(x)），也可能為矛盾式（如F(x) ¬F (x )，也可能不存在其值不確定的解釋。210 （1）¬xA(x) ¬(A(a ) A(b) A(c) （消去量詞等值式）¬A(a)¬A(b)¬A(c) （德·摩根律） x¬A(x ) （消去量詞等值式）¬A(a) ¬A(b)¬A(c ) （德·摩根律） x¬A(x) （消去量詞等值式）211 （1） 令F (x) : x為人。G(x) : x長(zhǎng)著綠色頭發(fā)

55、。本命題直接符號(hào)化驗(yàn)為¬x (F (x ) G(x ) 而¬x(F (x)G(x) x¬(F(x) G(x) （量詞否定等值式） x (¬F(x) ¬G(x ) （德·摩根律）x(F(x)¬G(x) （蘊(yùn)含等值式）最后一步得到的公式滿足要求（使用全稱量詞），將它翻譯成自然語言，即為“所有的人都不長(zhǎng)綠色頭發(fā)”?？梢姷谩皼]有人長(zhǎng)著綠色頭發(fā)?！迸c“所有人都不長(zhǎng)綠色頭發(fā)?！笔峭幻}的兩種不同的敘述方法。（2）令F (x ) : x是北京人G(x) : x 去過香山。命題直接符號(hào)化為x(F(x) ¬G(x)而x (F(x) ¬G(x)¬¬x(F (x)¬G(x) （雙重否定律） ¬x¬(F (x ) ¬G(x) （理詞否定等值式）最后得到的公式滿足要求（只含全稱量詞），將它翻譯成自然語言，即為“并不是北京人都去過香山?！笨梢姡坝械谋本┤藳]過過香山?！迸c“并不是北京人都去過香山?！笔峭幻}不同的敘述方法。2.12 （1） xF(x ) yG(y ) (F(a) F(