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

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

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

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

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

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

6、真式、永假式和可滿足式、命題公式的永真式、永假式和可滿足式 定義定義 設(shè)公式中有設(shè)公式中有n個(gè)不同的命題變?cè)獋€(gè)不同的命題變?cè)?p1,pn,(n為正整數(shù)為正整數(shù))。該變?cè)M的任意一組。該變?cè)M的任意一組確定的值（確定的值（ u1,un）稱為關(guān)于）稱為關(guān)于p1,pn的一個(gè)的一個(gè)完全指派完全指派，其中，其中ui或?yàn)椋驗(yàn)?。如果?duì)于或?yàn)?，或?yàn)椤Ｈ绻麑?duì)于中部分變?cè)x以確定值，其余變?cè)獩](méi)有賦以中部分變?cè)x以確定值，其余變?cè)獩](méi)有賦以確定的值，則這樣的一組值稱為公式的關(guān)于確定的值，則這樣的一組值稱為公式的關(guān)于該變?cè)M的該變?cè)M的部分指派部分指派。1.4 真值表與等價(jià)公式、命題公式的永真式、永假式和可滿足式、命

7、題公式的永真式、永假式和可滿足式 例例 設(shè)設(shè)A=(P (QR) S， 其變?cè)M為其變?cè)M為(P,Q,R,S)。 (P,Q,R,S)=(1,0,1,1)為為A的完全指派，的完全指派， (P,Q,R,S)=(0,0,1,S)為為A的部分指派。的部分指派。1.4 真值表與等價(jià)公式、命題公式的永真式、永假式和可滿足式、命題公式的永真式、永假式和可滿足式 定義定義 對(duì)于任一公式對(duì)于任一公式A A，凡使得，凡使得A A為真的指派，為真的指派，不管是完全指派還是部分指派，都稱為不管是完全指派還是部分指派，都稱為A A的的成真成真指派指派，凡使得凡使得A A為假的指派，也不管是完全指派為假的指派，也不管是完全

8、指派還是部分指派，都稱為還是部分指派，都稱為A A的的成假指派成假指派。 1.4 真值表與等價(jià)公式、命題公式的永真式、永假式和可滿足式、命題公式的永真式、永假式和可滿足式例例 設(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 真值表與等價(jià)公式 定義定義 如果一個(gè)命題公式的所有完全指派均為成真如果一個(gè)命題公式的所有完全指派均為成真指派，則該公式稱為指派，則該公式稱為永真式永真式。 如果一個(gè)命題公式的所有完全指派均為成假如果一個(gè)命題公式的所有完全指派均為成假指派，則該公式稱為指派，則該公式稱為永假式永假式。 既不是永真式，又不是永假式，則稱此命題既不是永真式，又不是永假式，則稱此命題公式是公式是可滿足式可滿足式。1.4 真值表與等價(jià)公式4 4、等價(jià)公式、等價(jià)公式 定義定義 給定兩個(gè)命題公式和，設(shè)給定兩個(gè)命題公式和，設(shè)p1,pn為為所有出現(xiàn)于所有出現(xiàn)于A和和B中的原子變?cè)艚o中的原子變?cè)?，若給p1,pn任任一組真

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

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

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

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