【正文】 摩根律 ⑸ p∨ p,p→ q, p→ q q 證明 : ⑴ q P(附加前提 ) ⑵ p→ q P ⑶ p T⑴⑵拒取式 ⑷ p→ q P ⑸ q T⑶⑷假言推理 ⑹ q∧ q(矛盾 ) T⑴⑸合取引入 ⑹ p∨ s， p→ q， r→ s p∨ r 證明 : ⑴ ( p∨ r) P(附加前提 ) ⑵ p∧ r T⑴條件等價(jià)式 ⑶ p T⑵化簡律 ⑷ r T⑵化簡律 ⑸ r→ s P ⑹ s T⑷⑸假言推理 ⑺ p∨ s P ⑻ p T⑹⑺ 析取三段論 ⑼ p∧ p(矛盾 ) T⑶⑻合取引入
。 ⑴ (p→ (q→ r)),p∧ q r ((p→ (q→ r))∧ (p∧ q))→ r ((p→ (q→ r))∧ (p∧ q))∨ r (( p∨ q∨ r)∧ (p∧ q))∨ r 第 1章 習(xí)題解答 35 (p∧ q∧ r)∨ (p∧ q)∨ r (p∧ q∧ r)∨ (p∧ q∧ r) 1 所以 (p→ (q→ r)),p∧ q r ⑵ p∨ q, (q∧ r), r p (( p∨ q)∧ ( (q∧ r))∧ r)→ p (( p∨ q)∧ ( (q∧ r))∧ r)∨ p ((p∧ q)∨ (q∧ r)∨ r)∨ p (p∧ q)∨ (q∧ r)∨ r∨ p ((p∧ q)∨ p)∨ ((q∧ r)∨ r) ( p∨ q)∨ (q∨ r) 1 所以 p∨ q, (q∧ r), r p ⑶ p∨ q,r→ q p→ r (( p∨ q)∧ (r→ q))→ (p→ r) (( p∨ q)∧ ( r∨ q))→ ( p∨ r) (( p∨ q)∧ ( r∨ q))∨ ( p∨ r) ((p∧ q)∨ (r∧ q))∨ ( p∨ r) ((p∧ q)∨ p)∨ ((r∧ q)∨ r) ( p∨ q)∨ (q∨ r) 1 所以 p∨ q,r→ q p→ r ⑷ p→ q， q→ r p→ r ((p→ q)∧ (q→ r))→ (p→ r) (( p∨ q)∧ ( q∨ r))→ ( p∨ r) (( p∨ q)∧ ( q∨ r))∨ ( p∨ r) (p∧ q)∨ ( r∧ q)∨ p∨ r ((p∧ q)∨ p)∨ (( r∧ q)∨ r) ( p∨ q)∨ (q∨ r) 1 所以 p→ q， q→ r p→ r ⑸ p∨ p,p→ q, p→ q q ((p∨ p)∧ (p→ q)∧ ( p→ q))→ q (1∧ ( p∨ q)∧ (p∨ q))→ q (( p∨ q)∧ (p∨ q))∨ q (p∧ q)∨ ( p∧ q)∨ q q∨ q 1 所以 p∨ p,p→ q, p→ q q 第 1章 習(xí)題解答 36 ⑹ p? q， q? r p? r ((p? q)∧ (q? r))→ (p? r) (( p∨ q)∧ ( q∨ p)∧ ( q∨ r)∧ ( r∨ q))→ (p? r) (( p∨ q)∧ ( q∨ p)∧ ( q∨ r)∧ ( r∨ q))∨ (p∧ r)∨ ( p∧ r) (p∧ q)∨ (p∧ r)∨ (r∧ q)∨ (q∧ r)∨ (q∧ p)∨ ( p∧ r) ((p∧ ( q∨ r))∨ ( q∨ r))∨ (r∧ q)∨ (q∧ p)∨ ( p∧ r) (( ( q∨ r)∨ ( q∨ r))∧ (p∨ ( q∨ r)))∨ (r∧ q)∨ (q∧ p)∨ ( p∧ r) (T∧ (p∨ ( q∨ r)))∨ (r∧ q)∨ (q∧ p)∨ ( p∧ r) p∨ (q∧ r)∨ (r∧ q)∨ (q∧ p)∨ ( p∧ r) p∨ (q∧ r)∨ ((q∧ p)∨ ( p∧ r))∨ (r∧ q) p∨ (q∧ r)∨ (( p∧ (q∨ r))∨ (q∨ r)) p∨ (q∧ r)∨ p∨ ( q∧ r) T 所以 p? q， q? r p? r 。 表 p q r p? q q? r p? r (p? q)∧ (q? r) ((p? q)∧ (q? r))→ (p? r) 0 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 由真值表可知： ((p? q)∧ (q? r))→ (p? r)是永真式，所以 p? q， q? r p? r。 表 p q r p∨p p→ q p→q (p∨ p)∧ (p→ q)∧ ( p→q) ((p∨ p)∧ (p→ q)∧ ( p→ q))→ q 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 由真值表可知： ((p∨ p)∧ (p→ q)∧ ( p→ q))→ q 是永真式，所以 p∨ p,p→ q, p→ q q。 表 p q r p→ q q→ r p→ r (p→ q)∧ (q→ r) ((p→ q)∧ (q→ r))→ (p→ r) 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 第 1章 習(xí)題解答 34 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 由真值表可知： ((p→ q)∧ (q→ r))→ (p→ r)是永真式，所以 p→ q， q→ r p→ r。 表 p q r p∨ q r→q p→r ( p∨ q)∧ (r→q) (( p∨ q)∧ (r→ q))→ (p→r) 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 由真值表可知： (( p∨ q)∧ (r→ q))→ (p→ r)是永真式，所以 p∨ q,r→ q p→ r。 表 p q r p∨q ?r ?(q∧ ?r) ( p∨ q)∧ ( (q∧ r))∧r (( p∨ q)∧ ( (q∧ r))∧ r)→p 0 0 0 1 1 1 1 1 第 1章 習(xí)題解答 33 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 1 0 1 0 0 1 0 1 1 1 0 1 1 0 0 1 1 1 1 1 0 1 0 1 由真值表可知： (( p∨ q)∧ ( (q∧ r))∧ r)→ p 是永真式，所以 p∨ q， (q∧ r)， r p。 表 p q r q→ r p→ (q→ r) p∧ q (p→ (q→ r))∧ (p∧ q) ((p→ (q→ r))∧ (p∧ q))→ r 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 由真值表可知 ， ((p→ (q→ r))∧ (p∧ q))→ r 是永真式，所以 (p→ (q→ r))， p∧ q r。 第 1章 習(xí)題解答 32 習(xí)題 證明下列各題的有效結(jié)論。 所以 ， 原蘊(yùn)含式成立。 ⑹ q∧ (p→ q) p 證明： 假設(shè)前件 q∧ (p→ q)為真，證明后件 p 也為真。因?yàn)?p∧ (p→ q)為真，所以 p 為真， p→ q 也為真，根據(jù)條件的定義 q 必為真。 所以 ， 原蘊(yùn)含式成立。 ⑷ p→ (q→ r) (p→ q)→ (p→ r) 證明 :假設(shè)后件 (p→ q)→ (p→ r)為假 , 證明前件 p→ (q→ r)必為假。 即： p→ q p→ (p∧ q) ⑶ p p→ q 證明 :假設(shè)前件 p 為真 ,則 p 為假 , 根據(jù)條件的定義可知 p→ q 必為真。 因?yàn)?p∧ q 為真，所以 p 為真并且 q 也為真，根據(jù)條件的定義可知 p→ q 也為真 。 表 p q q p→ q q∧ (p→q) ( q∧ (p→ q))→ p 0 0 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 1 0 1 由以上真值表可知： ( q∧ (p→ q))→ p 是一個(gè)永真式，所以 q∧ (p→ q) p “假設(shè)前件為真，推證后件也為真或假設(shè)后件為假，推證前件也為假“的方法證明下列蘊(yùn)含式。 表 p q p→ q p∧ q p→ (p∧ q) (p→ q)→ (p→ (p∧ q)) 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 由以上真值表可知： (p→ q)→ (p→ (p∧ q))是一個(gè)永真式，所以 p→ q p→ (p∧ q) ⑶ p p→ q 證明： p→ ( p→ q) p∨ p∨ q p∨ p∨ q 第 1章 習(xí)題解答 30 T 所以， p p→ q ⑷ p→ (q→ r) (p→ q)→ (p→ r) 證明： (p→ (q→ r))→ ((p→ q)→ (p→ r)) ( p∨ q∨ r)∨ ( ( p∨ q)∨ ( p∨ r)) (p∧ q∧ r)∨ (p∧ q)∨ p∨ r ((p∧ q∧ r))∨ r)∨ ((p∧ q)∨ p) ((p∨ r)∧ (q∨ r)∧ ( r∨ r))∨ ((p∨ p)∧ ( p∨ q)) ((p∨ r)∧ (q∨ r))∨ p∨ q ((p∨ r∨ p)∧ (q∨ r∨ p))∨ q q∨ r∨ p∨ q 1 所以， p→ (q→ r) (p→ q)→ (p→ r) ⑸ p∧ (p→ q) q 證明： 作 (p∧ (p→ q))→ q 的真值表，如 表 所示。證明： ⑴ 公式與它的逆反式等價(jià)，即 p→ q??q→ ?p 證明： p→ q p∨ q 而 q→ p q∨ p p∨ q 所以 p→ q q→ p ⑵ 公式的逆換式與公式的反換式等價(jià)，即 q→ p p→ q 證明： q→ p q∨ p 而 p→ q p∨ q p∨ q q∨ p 所以 q→ p p→ q 等價(jià)演算證明下列蘊(yùn)含式。 ⑴ p (p∧ p) p↑ p ⑵ p∨ q ( p∧ q) p↑ q (p↑ p)↑ (q↑ q) ⑶ p∧ q (p∧ q) (p↑ q) (p↑ q)↑ (p↑ q) 習(xí)題 1. 寫出下列命題公式的對偶式。 ⑴ (p↑ q) p↓ q 證明： (p↑ q) (p↑ q) (p∧ q) p∧ q p↓ q ( p∨ q) p∧ q 所以： (p↑ q) p↓ q 第 1章 習(xí)題解答 28 ⑵ (p↓ q) p↑ q 證明： (p↓ q) (p∨ q) p∨ q p↑ q ( p∧ q) p∨ q 所以： (p↓ q) p↑ q “ ↓ ”表示。 p↓ (q↓ r) p↓ (q∨ r) (p∨ (q∨ r)) p∧ (q∨ r) ( p∧ q∧ r)∨ ( p∧ q∧ r)∨ ( p∧ q∧ r) ↖ 1,2,3 而 (p↓ q)↓ r (p∨ q)↓ r ( (p∨ q)∨ r) (p∨ q)∧ r (p∧ q∧ r)∨ (p∧ q∧ r)∨ ( p∧ q∧ r) ↖ 2,4,6 顯然上式不成立。 p↓ q (p∨ q) (q∨ p) q↓ p ⑶ p↑ (q↑ r) (p↑ q)↑ r 不成立 。 ⑴ p↑ q q↑ p 成立。 第 1章 習(xí)題解答 27 ⑴ p∨ q∨ ( r→ p) p∨ q∨ (r∨ p) (p∧ q∧ r∧ p) ⑵ (p∨ q)→ ( p? r) (p∨ q)∨ ( p∧ r)∨ (p∧ r) (( p∧ q)∧ ( p∧ r)∧ (p∧ r)) ⑶ ( p∨ q)∨ (p→ q) ( p∨ q)∨ ( p∨ q) p∨ q (p∧ q) ⑷ ( p→ q)→ (p? q) (p∨ q)∨ (p? q) ( p∧ q)∨ ((p∧ q)∨ ( p∧ q)) ( ( p∧ q)∧ ( (p∧ q)∧ ( p∧ q))) ⑸ (p→ (q∨ r))∨ ( p→ r) ( p∨ q∨ r)∨ (p∨ r)