【正文】 由以上真值表可知： (p∧ (p→ q))→ q 是一個永真式，所以 p∧ (p→ q) q ⑹ q∧ (p→ q) p 證明： 作 (p∧ (p→ q))→ 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 是一個永真式，所以 q∧ (p→ q) p “假設(shè)前件為真，推證后件也為真或假設(shè)后件為假，推證前件也為假“的方法證明下列蘊含式。 ⑴ p∧ q p→ q 第 1章 習(xí)題解答 31 證明： 假設(shè)前件 p∧ q 為真，證明后件 p→ q 也為真。 因為 p∧ q 為真，所以 p 為真并且 q 也為真，根據(jù)條件的定義可知 p→ q 也為真 。 所以 ， p∧ q p→ q ⑵ p→ q p→ (p∧ q) 證明 :假設(shè)后件 p→ (p∧ q)為假 ,證明前件 p→ q 必為假； 因為 p→ (p∧ q)為假，則 p 為真 ,q 為假；根據(jù)條件的定義可知 p→ q 也為假。 即： p→ q p→ (p∧ q) ⑶ p p→ q 證明 :假設(shè)前件 p 為真 ,則 p 為假 , 根據(jù)條件的定義可知 p→ q 必為真。 所以 ， 原蘊含式成立。 ⑷ p→ (q→ r) (p→ q)→ (p→ r) 證明 :假設(shè)后件 (p→ q)→ (p→ r)為假 , 證明前件 p→ (q→ r)必為假。 因為 (p→ q)→ (p→ r)為假，所以 ， p→ q 為真， p→ r 為假；因為 p→ r 為假 ， 所以 p 為真，r 為假；所以 ， q 必為真； 因為 q 為真， r 為假，所以 q→ r 必為假；因為 p 為真，所以 ， p→ (q→ r)必為假。 所以 ， 原蘊含式成立。 ⑸ p∧ (p→ q) q 證明： 假設(shè)前件 p∧ (p→ q)為真，證明后件 q 也為真。因為 p∧ (p→ q)為真，所以 p 為真， p→ q 也為真，根據(jù)條件的定義 q 必為真。 所以 ， 原蘊含式成立。 ⑹ q∧ (p→ q) p 證明： 假設(shè)前件 q∧ (p→ q)為真，證明后件 p 也為真。 因為 q∧ (p→ q)為真，所以 ， q 為真， q 為假，又因為 p→ q 為真，根據(jù)條件的定義 p 為假，所以 p 必為真。 所以 ， 原蘊含式成立。 A是任意的命題公式，證明 A A 證明： 由條件的定義可知： A→ A 是一個永真式；根據(jù)蘊含式的定義可知 A A。 第 1章 習(xí)題解答 32 習(xí)題 證明下列各題的有效結(jié)論。 ⑴ (p→ (q→ r))， p∧ q r ((p→ (q→ r))∧ (p∧ q))→ r 的 全 真值表 如 表 所示。 表 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。 ⑵ p∨ q, (q∧ r), r p (( p∨ q)∧ ( (q∧ r))∧ r)→ p 的 全 真值表 如 表 所示。 表 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 p→ r (( p∨ q)∧ (r→ q))→ (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， q→ r p→ r ((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 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∨ p,p→ q, p→ q q ((p∨ p)∧ (p→ q)∧ ( p→ q))→ q 的真值表 如 表 所示。 表 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， q? r p? r ((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。 ，主析取范式法或蘊含演算法證明上題中的各有效結(jié)論。 ⑴ (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)， (t∨ s)→ p， (t∨ s) q∨ r 證明： ⑴ t∨ s P ⑵ (t∨ s)→ p P ⑶ p T⑴⑵假言推理 ⑷ p→ (q∨ r) P ⑸ q∨ r T⑶⑷假言推理 ⑵ p∧ q， (p? q)→ (t∨ s) (t∨ s) 證 明 : ⑴ p∧ q P ⑵ p T⑴化簡律 ⑶ q T⑴化簡律 ⑷ p→ q T⑶例 (2) ⑸ q→ p T⑵例 (2) ⑹ (p→ q)∧ (q→ p) T⑷⑸ 合取引入 ⑺ p? q T⑹雙條件等價式 ⑻ (p? q)→ (t∨ s) P ⑼ t∨ s T⑺⑻假言推理 ⑶ (p→ q)→ (r∨ s)， (q→ p)∨ r,r p? q 證明 : ⑴ r P 第 1章 習(xí)題解答 37 ⑵ (q→ p)∨ r P ⑶ q→ p T⑴⑵ 析取三段論 ⑷ r∨ s T⑴附加律 ⑸ (p→ q)→ (r∨ s) P ⑹ p→ q T⑷⑸ 拒取式 ⑺ (p→ q)∧ (q→ p) T⑶⑹ 合取引入 ⑻ p? q T⑹雙條件等價式 ⑷ p∧ q→ r， r∨ s， s p∨ q 證明 : ⑴ s P ⑵ r∨ s P ⑶ r T⑴⑵ 析取三段論 ⑷ p∧ q→ r P ⑸ (p∧ q) T⑶⑷拒取式 ⑹ p∨ q T⑸ 德摩根律 ⑸ 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⑴條件等價式 ⑶ p T⑵化簡律 ⑷ r T⑵化簡律 ⑸ r→ s P ⑹ s T⑷⑸假言推理 ⑺ p∨ s P ⑻ p T⑹⑺ 析取三段論 ⑼ p∧ p(矛盾 ) T⑶⑻合取引入