1、1.3 命題公式與翻譯,1、命題公式：由命題變元、聯(lián)結(jié)詞和圓括號按一定規(guī)則組成的合式公式。 定義 合式公式定義如下： （1）單個命題變元是一個合式公式； （2）如果A是合式公式，則A也是合式公式； （3）如果A和B是合式公式，則AB，AB，AB，AB均是合式公式； （4）當(dāng)且僅當(dāng)能有限次地利用（1）（3）形成的符號串才是合式公式。,1.3 命題公式與翻譯,例如，(PQ)，P(PQ)等都是命題公式，而(P)，(P) ，RP等不是命題公式。 2、命題符號化（翻譯） 命題邏輯里討論的對象是命題公式，而日常生活中的推理問題是用自然語言描述的，因此要進行推理演算必須先把自然語言符號化（或形式化）成邏輯語

2、言，即命題公式。然后再根據(jù)邏輯演算規(guī)律進行推理演算。,1.3 命題公式與翻譯,例 將下列命題符號化 （1）李明是計算機系的學(xué)生，他住在312室。 （2）張三和李四是朋友。 （3）雖然交通堵塞，但是老王還是準(zhǔn)時到達了車站。 （4）只有一個角是直角的三角形才是直角三角形。 （5）老王或小李中有一個去上海出差。,1.3 命題公式與翻譯,解： （1）首先用字母表示簡單命題。 P：李明是計算機系的學(xué)生。 Q：李明住在312室。 該命題符號化為：P Q （2）張三和李四是朋友。是一個簡單句 該命題符號化為：P,1.3 命題公式與翻譯,（3）首先用字母表示簡單命題。 P：交通堵塞。 Q：老王準(zhǔn)時到達了車站。

3、 該命題符號化為：PQ （4）首先用字母表示簡單命題。 P：三角形的一個角是直角。 Q：三角形是直角三角形。 該命題符號化為：P Q（ Q P ）,1.3 命題公式與翻譯,（5）首先用字母表示簡單命題。 P：老王去上海出差。 Q：小李去上海出差。 該命題符號化為：P Q（ 不可兼或） 也可符號化為：（PQ）（PQ）或者 （P Q） （PQ）,1.3 命題公式與翻譯,從以上例子中可以看出，所謂命題符號化是指把一個用自然語言敘述的命題相應(yīng)地寫成由命題變元、聯(lián)結(jié)詞和圓括號表示的命題公式。符號化應(yīng)該注意下列事項： 確定給定句子是否為命題。 句子中連詞是否為命題聯(lián)結(jié)詞。 要正確地表示原子命題和適當(dāng)選擇命

4、題聯(lián) 結(jié)詞。,1.3 命題公式與翻譯,例：假如上午不下雨，我去看電影，否則就在家里讀書或看報。,解：設(shè)P：上午下雨； Q：我去看電影； R：我在家里讀書； S：我在家里看報。 本例可表示為： （PQ） （P（RS）,1.4 真值表與等價公式,1、命題公式的真值表 定義1.4.1 在命題公式中，對于分量指派真值的各種可能組合，就確定了這個命題的各種真值情況，把它匯列稱表，就是命題公式的真值表。,1.4 真值表與等價公式,2、構(gòu)造真值表的步驟 1)找出給定命題公式中所有的命題變元，列出所有可能的真值。 2)按照從低到高順序?qū)懗雒}公式的各層次。 3)對應(yīng)每個真值，計算命題公式各層次的值，直到最后計

5、算出整個命題公式的值。,1.4 真值表與等價公式,例構(gòu)造命題公式 的真值表,1.4 真值表與等價公式,例2構(gòu)造命題公式(P Q） 的真值表,1.4 真值表與等價公式,例3構(gòu)造命題公式 (P Q） （ P Q）的真值表,1.4 真值表與等價公式,由上例可見，個命題變元有組真值指派；個命題變元有23 組真值指派，個則有個2n個真值指派。,1.4 真值表與等價公式,、命題公式的永真式、永假式和可滿足式 定義 設(shè)公式中有n個不同的命題變元 p1,pn,(n為正整數(shù))。該變元組的任意一組確定的值（ u1,un）稱為關(guān)于p1,pn的一個完全指派，其中ui或為，或為。如果對于中部分變元賦以確定值，其余變元沒

6、有賦以確定的值，則這樣的一組值稱為公式的關(guān)于該變元組的部分指派。,1.4 真值表與等價公式,、命題公式的永真式、永假式和可滿足式 例 設(shè)A=(P(QR)S， 其變元組為(P,Q,R,S)。 (P,Q,R,S)=(1,0,1,1)為A的完全指派， (P,Q,R,S)=(0,0,1,S)為A的部分指派。,1.4 真值表與等價公式,、命題公式的永真式、永假式和可滿足式 定義 對于任一公式A，凡使得A為真的指派，不管是完全指派還是部分指派，都稱為A的成真指派，凡使得A為假的指派，也不管是完全指派還是部分指派，都稱為A的成假指派。,1.4 真值表與等價公式,、命題公式的永真式、永假式和可滿足式 例 設(shè)A

7、=(P(QR)(RS)，則 完全指派(P,Q,R,S)=(0,1,0,1)和 部分指派(P,Q,R,S)=(0,1,0,S) 都是A的成真指派， 而指派(P,Q,R,S)=(1,0,1,0)為A的成假指派。,1.4 真值表與等價公式,定義 如果一個命題公式的所有完全指派均為成真指派，則該公式稱為永真式。 如果一個命題公式的所有完全指派均為成假指派，則該公式稱為永假式。 既不是永真式，又不是永假式，則稱此命題公式是可滿足式。,1.4 真值表與等價公式,4、等價公式 定義給定兩個命題公式和，設(shè)p1,pn為所有出現(xiàn)于A和B中的原子變元，若給p1,pn任一組真值指派，A和B的真值均相同，則稱，是邏輯等

8、價的，亦說（）等價于（）,并記作：,1.4 真值表與等價公式,4、等價公式 例：利用真值表證明,1.4 真值表與等價公式,4、等價公式 例：AB （A B） （B A）,1.4 真值表與等價公式,4、等價公式 練習(xí)：判斷公式A：(PQ)(PQ)與 B：(PR)(PR)是否等價。,1.4 真值表與等價公式,解：列該公式的真值表：,1.4 真值表與等價公式,下面列出組等價公式 （1）雙重否定律 （2）同等律 ； （3）交換律 ； ； ,1.4 真值表與等價公式,（4）結(jié)合律 （）（）； （）（）； （） （） （5）分配律 （）（）（）； （）（）（）,1.4 真值表與等價公式,（6）摩根律 （）

9、； （） （7）吸收律 （） ； （） ,1.4 真值表與等價公式,（8）蘊含律 （9）等價律 （）（） （10）零律；,1.4 真值表與等價公式,（11）同一律； （12）互補律； （13）輸出律 （）,1.4 真值表與等價公式,（14）歸繆律 （）（） （15）逆反律 說明： （）證明上述組等價公式的方法可用真值表法，把改為所得的命題公式為永真式，則成立。,1.4 真值表與等價公式,（2） 、 均滿足結(jié)合律， 則在單一用、 聯(lián)結(jié)詞組成的命題公式中，括號可以省去。 （3）每個等價模式實際給出了無窮多個同類型的具體的命題公式。 例如：(PQ) (P Q)， (PQ) (RS) (P Q) (R

10、 S)， (PQ) R) (P Q) R),1.4 真值表與等價公式,5、置換規(guī)則 定義給定一命題公式，其中P1、P2Pn 是中的原子命題變元， 若（1）用某些命題公式代換中的一些原子命題變元Pi （2）用命題公式i代換Pi，則必須用i代換中的所有Pi 由此而得到的新的命題公式稱為命題公式的代換實例,1.4 真值表與等價公式,討論定義： （1）要用命題公式同時代換同一個原子命題變元 例設(shè)：（Q） 若用（）代換中的，得 ：（）（Q（）是的代換實例， 而：（）（Q）不是B的代換實例。,1.4 真值表與等價公式,討論定義： （2）永真式的代換實例仍為永真式；反之代換實例為永真式時，則不能斷定原公式也一定是永真式。 例2：為一永真式，若用任何命題公式代換，則仍為永真式 為一個可滿足的命題公式，若用代換，則得（）為永真式，但（）并不是永真式。,1.4 真值表與等價公式,討論定義： （3）一個命題公式的代換實例有許多個，但不一定都等價于原來的命題公式 例3的代換實例有：（），（），（）等 所以，一個命題公式的代換實例有無限個。,1.4 真值表與等價公式,下面討論取代過程（置換規(guī)則）： 定義給定一命題公式，是的任何部分，若也是一命題公式，則稱是的子命題公式。 例：（）（） 的子命題公式有：、（）、（）、（）、（）（）等