離散數學自學筆記命題公式及其真值表

　　我們把表示具體命題及表示常命題的p，q，r，s等與f，t統稱為命題常元（proposition constant）。深入的討論還需要引入命題變元（proposition variable）的概念，它們是以“真、假”或“1，0”為取值範圍的變元，為簡單計，命題變元仍用p，q，r，s等表示。相同符號的不同意義，容易從上下文來區別，在未指出符號所表示的具體命題時，它們常被看作變元。　　命題常元、變元及聯結詞是形式描述命題及其推理的基本語言成分，用它們可以形式地描述更為複雜的命題。下面我們引入高一級的語言成分——命題公式。
　　定義1.1 以下三條款規定了命題公式（proposition formula）的意義：
　　（1）命題常元和命題變元是命題公式，也稱為原子公式或原子。
　　（2）如果A，B是命題公式，那麼（┐A），（A∧B），（A∨B），（A→B），（A？B）也是命題公式。
　　（3）只有有限步引用條款（1），（2）所組成的符號串是命題公式。
　　命題公式簡稱公式，常用大寫拉丁字母A，B，C等表示。公式的上述定義方式稱為歸納定義，第四章將對此定義方式進行討論。
　　例1.8 （┐（p→（q∧r）））是命題公式，但（qp），p→r，p1∨p2∨…均非公式。
　　為使公式的表示更為簡練，我們作如下約定：

　　（1）公式最外層括號一律可省略。
　　（2）聯結詞的結合能力強弱依次為 ┐，（∧，∨），→，？，（∧，∨）表示∧與∨平等。
　　（3）結合能力平等的聯結詞在沒有括號表示其結合狀況時，採用左結合約定。
　　例如， ┐p→q∨（r∧q∨s）所表示的公式是（（┐p）→（q∨（（r∧q）∨s）））
　　設A是命題公式，A1是A 的一部分，且A1也是公式，則A1稱為公式A的子公式。
　　如對公式A：┐p→q∨（r∧q∨s），則p， ┐p ，q ，（r∧q∨s）及q∨（r∧q∨s）都是公式A的子公式，而┐q， ┐p→q，雖然是公式，但確不是A的一部分，因此不是A的子公式；q∨（r∧雖然是公式A的一部分，但不是公式，因而也不是A的子公式。

　　如果公式A含有命題變元p1，p2，…，pn，記為A（p1，…，pn），並把聯結詞看作真值運算子，那麼公式A可以看作是p1，…，pn的真值函式。對任意給定的p1，…，pn的一種取值狀況，稱為指派（assignments），用希臘字母a，b等表示，A均有一個確定的真值。當A對取值狀況 a 為真時，稱指派a弄真A，或a是A的成真賦值，記為a （A） = 1；反之稱指派a弄假A，或a是A的成假賦值，記為a （A） = 0.對一切可能的指派，公式A的取值可能可用表1.7來描述，這個表稱為真值表（truth table）。當A（p1，…，pn）中有k個聯結詞時，公式A的真值表應為2n行、k+n列（不計表頭）。
　　例1.9 作出公式┐（p→（q∧r））的真值表。
　　表1.7

p	q	r	q∧r	P→（q∧r）	┐（p→（q∧r）
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	0 0 0 1 0 0 0 1	1 1 1 1 0 0 0 1	0 0 0 0 1 1 1 0