2023/2/1命題邏輯1第1章命題邏輯命題演算或命題邏輯（Propositionalcalculusorpropositionallogic）符號化精確化——Aristotle(384B.C.-322B.C.)2023/2/1命題邏輯2命題(1)13不是偶數(shù)。(2)13是偶數(shù)也是奇數(shù)。(3)他一邊走路一邊唱歌。(4)她或許數(shù)學成績好，或許英語成績好。

(5)開往煙臺的2547次火車三點或四點出發(fā)。(6)如果你努力學習，那么就可以得獎學金。(7)只要不下雨，我就騎自行車上班。(8)只有不下雨，我才騎自行車上班。(9)兩圓的面積相等當且僅當它們的半徑相等。2023/2/1命題邏輯3常用的聯(lián)結(jié)詞(connective)合取(conjunction)：與，并且，而且，也析取(disjunction)：或，要么…要么…否定(negation)：非，不蘊涵(conditional)：如果…就…，當，只有…才…

，除非…不，若…則…，等價(biconditional)：當且僅當2023/2/1命題邏輯4命題符號化原子命題：p,q,r,p1,q1,r1,…聯(lián)結(jié)詞：合取聯(lián)結(jié)詞：∧析取聯(lián)結(jié)詞：∨否定聯(lián)結(jié)詞：?蘊涵聯(lián)結(jié)詞：→等價聯(lián)結(jié)詞：?邏輯真值：0，1或F，T2023/2/1回顧5命題符號化（舉例）(1)13不是偶數(shù)。┐p(2)13是偶數(shù)也是奇數(shù)。p∧q(3)他一邊走路一邊唱歌。p∧q

(4)她或許數(shù)學成績好，或許英語成績好。p∨q(5)開往煙臺的2547次火車三點或四點出發(fā)。(p∧┐q)∨

(p∧┐q)(6)如果你努力學習，那么就可以得獎學金。p→q(7)只要不下雨，我就騎自行車上班。┐p→q(8)只有不下雨，我才騎自行車上班。q→┐p(9)兩個圓的面積相等當且僅當它們的半徑相等。p?qp可表示任何命題p,q是簡單命題，是命題常元2023/2/1命題邏輯6命題常元命題常元（命題常項）：p,q,r,p1,q1,r1,…

確定的簡單命題。

2023/2/1命題邏輯7命題變元命題變元：p,q,r,p1,q1,r1,…

可以表示任何命題。在命題邏輯中，只研究形式推演的正確性，而不關心表示式所代表的實際含義。

2023/2/1命題邏輯8命題公式(well-formedformula)命題變元：p,q,r,p1,q1,r1,…聯(lián)結(jié)詞：∧，∨，?，→，?分隔符：（，）2023/2/1命題邏輯9命題的表示上節(jié)介紹了將命題表示為符號串。是否每個符號串都是命題的表示呢？

pq→

什么樣的符號串才能表示命題呢？2023/2/1命題邏輯10命題公式遞歸定義單個命題變元是命題公式，稱為原子（atomic）公式若A是命題公式，則(?A)是命題公式若A,B是命題公式，則(A∧B),(A∨B),(A→B),(A?B)也是命題公式只有有限次地應用上述規(guī)則形成的符號串才是命題公式（合式公式），簡稱為公式。A,B為元語言符號2023/2/1命題邏輯11子命題公式子命題公式：A，B是命題公式，若B是A中一部分則稱B是A的子命題公式，特別A自己也是A的子命題公式。

2023/2/1命題邏輯12命題公式（舉例）

p

(?(?p))，??p((?p)∧(?p))，?p∧?p(?(p∧q))，?(p∧q)((?p)∧q)，?p∧q

約定：省略多余括號最外層優(yōu)先級遞減：?；∧，∨；→，?2023/2/1命題邏輯13命題公式的簡單性質(zhì)任一個命題公式必為下列形式之一：命題變元、(?A)、(A∨B)、(A∧β)、(A→B)或(A?B)命題公式的BNF(BacusNormalForm):A::=p|(?A)|(A∨B)|(A∧B)|(A→B)|(A?B)

每個命題公式都是有限符號串2023/2/1命題邏輯14分層命題公式若公式A是單個的命題變元，則稱A是0層公式；稱A是n+1(n0)層公式是指下面情況之一A=?B，B是n層公式；A=B∧

C，其中B,C分別是i層和j層公式，且n=max（i,j）；A=B∨

C，其中B,C的層次與n同上；A=B→

C，其中B,C的層次與n同上；A=B?

C，其中B,C的層次與n同上。若公式A的層次是k，

稱A是k層公式。2023/2/1命題邏輯15命題公式（舉例）

p

(?(?p))，??p((?p)∧(?p))，?p∧?p(?(p∧q))，?(p∧q)(?p∧q)→r?(p∧q)?((?p∧s)∨

r)2023/2/1命題邏輯16注意！命題公式并不是命題，因此并無確定的真假值。當命題公式中的命題變元用確定的命題代入時，才得到一個命題。其真值由代換變元的命題真值決定2023/2/1命題邏輯17賦值(assignment,解釋,指派)命題公式的真假由其中命題變元的值完全確定。定義1.8設A為一個命題公式，p1,

p2,…,

pn

是出現(xiàn)在公式A中的所有命題變元，給p1,

p2,…,

pn各指定一個真值，稱為對A的一個賦值或解釋。若賦值后公式A的真值為1，則稱這組賦值為公式A的成真賦值，反之，則為成假賦值。

2023/2/1命題邏輯18賦值性質(zhì)性質(zhì)：n個變元，共有2n種不同的賦值賦值是從{p1,

p2,…,

pn}到{0，1}的一個函數(shù)。(p∧q)r

010為成真賦值

110為成假賦值2023/2/1命題邏輯19真值函數(shù)公式pqr可視為p,q,r的函數(shù)A(p,q,r)，稱作真值函數(shù)——只有有限多種取值及函數(shù)值。自變量有2n組不同的取值，真值函數(shù)取值只有兩種：1

T

0

F共有種不同的真值函數(shù)2023/2/1命題邏輯20例求A=(p∧q)→(?(q∨r))的成真和成假賦值。解：要使A為假，必須p∧q為真且?(q∨r)為假。從而p∧q必須為真，且q∨r也必須為真。故A的成假賦值為(1，1，1)和(1，1，0).A的成真賦值為(0，0，0)、(1，0，0)、(0，1，0)、(0，0，1)、(0，1，1)、(1，0，1)。2023/2/1命題邏輯21真值表(truth-table)定義1.9

命題公式在所有可能的賦值下所取值列成的表稱為真值表.2023/2/1命題邏輯22真值表(truth-table)pq?pp∧qp∨qp→qp?q非合取析取蘊含等價不

和或如果…那么當且僅當00110101110000010111110110012023/2/1命題邏輯23啞元?p也可以看作是含有命題變元p，q，的公式，q稱為該公式的啞元。公式(p∧q)?(?p∨?q)也可以看作是含有命題變元p，q，r的公式，r稱為該公式的啞元。2023/2/1命題邏輯24α=(p∧q)→(?(q∨r))的真值表2023/2/1命題邏輯25真值表(續(xù))pqr(p∧q)→r?p∨?q∨r00001111001100110101010111111101111111012023/2/1命題邏輯26真值表(續(xù))pqp∧q?(p∧q)?p∨?qαβ0011010100011110111011110000α=?(p∧q)?(?p∨?q)β=(p∧q)?(?p∨?q)2023/2/1命題邏輯27重言式(tautology)重言式:在各種賦值下取值均為真(永真式)矛盾式:在各種賦值下取值均為假(永假式)可滿足式：有一個賦值下取值為真（非永假式）2023/2/1命題邏輯28重言式性質(zhì)任何兩個重言式的合取與析取仍然是一個重言式.