第一章命題邏輯(1.3-1.4)

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

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

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

4、結(jié)詞。u要正確地表示原子命題和適當(dāng)選擇命題聯(lián) 結(jié)詞。1.3 命題公式與翻譯 例：假如上午不下雨，我去看電影，否則就在家里讀書或看報。 解：設(shè)解：設(shè)P P：上午下雨；：上午下雨； Q Q：我去看電影；：我去看電影； R R：我在家里讀書；：我在家里讀書； S S：我在家里看報。：我在家里看報。 本例可表示為：本例可表示為： （ P PQ Q） （P P（RSRS） 1.4 真值表與等價公式1 1、命題公式的真值表、命題公式的真值表 定義定義1.4.1 1.4.1 在命題公式中，對于分量指派真值的各種可能組合，就確定了這個命題的各種真值情況，把它匯列稱表，就是命題公式的真值表命題公式的真值表。1.

5、4 真值表與等價公式2 2、構(gòu)造真值表的步驟 1)1)找出給定命題公式中所有的命題變元，列出所有可能的真值。 2)2)按照從低到高順序?qū)懗雒}公式的各層次。 3)3)對應(yīng)每個真值，計算命題公式各層次的值，直到最后計算出整個命題公式的值。1.4 真值表與等價公式例構(gòu)造命題公式 的真值表1.4 真值表與等價公式例2 2構(gòu)造命題公式(P Q） 的真值表1.4 真值表與等價公式例3 3構(gòu)造命題公式 (P Q） （ P Q）的真值表1.4 真值表與等價公式 由上例可見: :個命題變元有組真值指派；個命題變元有2 23 3 組真值指派，個則有個2 2n n個真值指派。1.4 真值表與等價公式、命題公式的永

6、真式、永假式和可滿足式、命題公式的永真式、永假式和可滿足式 定義定義 設(shè)公式中有設(shè)公式中有n個不同的命題變元個不同的命題變元 p1,pn,(n為正整數(shù)為正整數(shù))。該變元組的任意一組。該變元組的任意一組確定的值（確定的值（ u1,un）稱為關(guān)于）稱為關(guān)于p1,pn的一個的一個完全指派完全指派，其中，其中ui或為，或為。如果對于或為，或為。如果對于中部分變元賦以確定值，其余變元沒有賦以中部分變元賦以確定值，其余變元沒有賦以確定的值，則這樣的一組值稱為公式的關(guān)于確定的值，則這樣的一組值稱為公式的關(guān)于該變元組的該變元組的部分指派部分指派。1.4 真值表與等價公式、命題公式的永真式、永假式和可滿足式、命

7、題公式的永真式、永假式和可滿足式 例例 設(shè)設(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 A的的成真成真指派指派，凡使得凡使得A A為假的指派，也不管是完全指派為假的指派，也不管是完全

8、指派還是部分指派，都稱為還是部分指派，都稱為A A的的成假指派成假指派。 1.4 真值表與等價公式、命題公式的永真式、永假式和可滿足式、命題公式的永真式、永假式和可滿足式例例 設(shè)設(shè)A A=(P(Q=(P(Q R)R) ( ( R R S)S)，則，則完全指派完全指派(P,Q,R,S)=(0,1,0,1)(P,Q,R,S)=(0,1,0,1)和和部分指派部分指派(P,Q,R,S)=(0,1,0,S)(P,Q,R,S)=(0,1,0,S)都是都是A A的成真指派，的成真指派，而指派而指派(P,Q,R,S)=(1,0,1,0)(P,Q,R,S)=(1,0,1,0)為為A A的成假指派。的成假指派。1

9、.4 真值表與等價公式 定義定義 如果一個命題公式的所有完全指派均為成真如果一個命題公式的所有完全指派均為成真指派，則該公式稱為指派，則該公式稱為永真式永真式。 如果一個命題公式的所有完全指派均為成假如果一個命題公式的所有完全指派均為成假指派，則該公式稱為指派，則該公式稱為永假式永假式。 既不是永真式，又不是永假式，則稱此命題既不是永真式，又不是永假式，則稱此命題公式是公式是可滿足式可滿足式。1.4 真值表與等價公式4 4、等價公式、等價公式 定義定義 給定兩個命題公式和，設(shè)給定兩個命題公式和，設(shè)p1,pn為為所有出現(xiàn)于所有出現(xiàn)于A和和B中的原子變元，若給中的原子變元，若給p1,pn任任一組真

10、值指派，一組真值指派，A和和B的真值均相同，則稱的真值均相同，則稱，是邏輯等價的是邏輯等價的，亦說（）等價于，亦說（）等價于（）（）,并記作：并記作：1.4 真值表與等價公式4 4、等價公式、等價公式例：利用真值表證明TTT TTTT FTTF TTTF F Q QPPP Q 1.4 真值表與等價公式4 4、等價公式、等價公式例：例：AB （A B） （B A） 1.4 真值表與等價公式4 4、等價公式、等價公式練習(xí)：判斷公式A：(PQ) (P Q)與 B：(PR) (P R)是否等價。1.4 真值表與等價公式解：列該公式的真值表：FFFTTFTTFFFFFTFFFTTTFFFFFTTTFFF

11、TFFFTFFTFFTTFTTTTTTTTFFTTTTTFTTTTFTTTTTTTTFFTTTTTTFTTFTTTBAPRPRRPQPQQRQP1.4 真值表與等價公式下面列出組等價公式（1）雙重否定律 （2）同等律 ； （3）交換律 ； ； 1.4 真值表與等價公式（4）結(jié)合律 （）（）； （）（）； （） （）（5）分配律 （）（）（）； （）（）（） 1.4 真值表與等價公式（6）摩根律 （）； （） （7）吸收律 （） ； （） 1.4 真值表與等價公式（8）蘊(yùn)含律 （9）等價律 （）（）（10）零律； 1.4 真值表與等價公式（11）同一律； （12）互補(bǔ)律； （13）輸出律 （）

12、1.4 真值表與等價公式（14）歸繆律 （）（）（15）逆反律 說明：（）證明上述組等價公式的方法可用真值表法，把改為所得的命題公式為永真式，則成立。 1.4 真值表與等價公式（2） 、 均滿足結(jié)合律， 則在單一用、 聯(lián)結(jié)詞組成的命題公式中，括號可以省去。（3）每個等價模式實際給出了無窮多個同類型的具體的命題公式。例如： (P Q) ( P Q)， (P Q) (R S) ( (P Q) (R S)， (PQ) R) ( (P Q) R) 1.4 真值表與等價公式5 5、置換規(guī)則、置換規(guī)則 定義定義 給定一命題公式，其中P1、P2Pn 是中的原子命題變元，若（1）用某些命題公式代換中的一些原子

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