第2講命題公式與賦值

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

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

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

(4)她或許數(shù)學(xué)成績(jī)好，或許英語(yǔ)成績(jī)好。p∨q(5)開往煙臺(tái)的2547次火車三點(diǎn)或四點(diǎn)出發(fā)。(p∧┐q)∨

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

確定的簡(jiǎn)單命題。

2023/2/1命題邏輯7命題變?cè)}變?cè)簆,q,r,p1,q1,r1,…

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

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

pq→

什么樣的符號(hào)串才能表示命題呢？2023/2/1命題邏輯10命題公式遞歸定義單個(gè)命題變?cè)敲}公式，稱為原子（atomic）公式若A是命題公式，則(?A)是命題公式若A,B是命題公式，則(A∧B),(A∨B),(A→B),(A?B)也是命題公式只有有限次地應(yīng)用上述規(guī)則形成的符號(hào)串才是命題公式（合式公式），簡(jiǎn)稱為公式。A,B為元語(yǔ)言符號(hào)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

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

每個(gè)命題公式都是有限符號(hào)串2023/2/1命題邏輯14分層命題公式若公式A是單個(gè)的命題變?cè)?，則稱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注意！命題公式并不是命題，因此并無(wú)確定的真假值。當(dāng)命題公式中的命題變?cè)么_定的命題代入時(shí)，才得到一個(gè)命題。其真值由代換變?cè)拿}真值決定2023/2/1命題邏輯17賦值(assignment,解釋,指派)命題公式的真假由其中命題變?cè)闹低耆_定。定義1.8設(shè)A為一個(gè)命題公式，p1,

p2,…,

pn

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

p2,…,

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

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

p2,…,

pn}到{0，1}的一個(gè)函數(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非合取析取蘊(yùn)含等價(jià)不

和或如果…那么當(dāng)且僅當(dāng)00110101110000010111110110012023/2/1命題邏輯23啞元?p也可以看作是含有命題變?cè)猵，q，的公式，q稱為該公式的啞元。公式(p∧q)?(?p∨?q)也可以看作是含有命題變?cè)猵，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)重言式:在各種賦值下取值均為真(永真式)矛盾式:在各種賦值下取值均為假(永假式)可滿足式：有一個(gè)賦值下取值為真（非永假式）2023/2/1命題邏輯28重言式性質(zhì)任何兩個(gè)重言式的合取與析取仍然是一個(gè)重言式.