離散數(shù)學第1章-命題邏輯基本概念

1、 離散數(shù)學Discrete Mathematics8/27/2022 1Discrete Math. , Chen Chen第一部分數(shù) 理 邏 輯Part One Mathematics logic8/27/2022 2Discrete Math. , Chen Chen 邏輯學: 研究人的思維形式和規(guī)律的科學由于研究的對象和方法各有側重而又分為形式邏輯、辯證邏輯和數(shù)理邏輯 數(shù)理邏輯是用數(shù)學方法來研究推理的形式結構和推理規(guī)律的數(shù)學學科。這里所指的數(shù)學方法就是引進一套符號體系的方法。所以數(shù)理邏輯又稱符號邏輯，它是從量的側面來研究思維規(guī)律的。 現(xiàn)代數(shù)理邏輯可分為邏輯演算、證明論、公理集合論、遞歸論

2、和模型論。 本部分僅介紹計算機科學領域中所必需的數(shù)理邏輯基礎知識： 命題邏輯和謂詞邏輯（一階邏輯）。8/27/2022 3Discrete Math. , Chen Chen第一章 命題邏輯基本概念Chapter OneFoundations of Proposition Logic8/27/2022 4Discrete Math. , Chen Chen1.1 命題與聯(lián)結詞1.2 命題公式及其賦值命題與真值命題符號化聯(lián)結詞及其邏輯關系復合命題命題常項與變項命題公式及其賦值命題公式的類型公式類型的判斷方法8/27/2022 5Discrete Math. , Chen Chen一 、命題 命題

3、：能判斷真假(非真即假)的陳述句。 命題的真值：命題的判斷結果。1.1 命題與聯(lián)結詞 它只有兩種可能：真或假，分別用1和0來表示。 真值為1的命題稱為真命題；真值為0的命題稱為假命題。 判斷一個句子是否為命題： 首先判斷它是否為陳述句;其次判斷它是否有唯一的真值。 定義 一個命題若不能被分解成更簡單的陳述句，則稱為簡單命題或原子命題； 若一個命題是由幾個簡單陳述句通過聯(lián)結詞聯(lián)結而成的，則稱為復合命題。 例 命題“因為32, 所以32.”的組成。8/27/2022 6Discrete Math. , Chen Chen （1） 4是素數(shù)。例 1.1 判斷下列句子是否為命題 注：通常用小寫字母p

4、, q , r 等來表示命題。（9）我正在說假話。（8）這朵花真美麗?。。?）請不要吸煙?。?） 大于 嗎？（5）2050年元旦是晴天。（4）火星上有水。（3） x 大于 y,其中x和y是任意的兩個數(shù)。（2） 是無理數(shù) 。8/27/2022 7Discrete Math. , Chen Chen定義 1.1 設 p 為命題，復合命題“非 p ” (即 “p 的否定”)稱為 p 的否定式，記為 p 。 符號 稱為否定聯(lián)結詞。規(guī)定：p 為真當且僅當 p 為假。二聯(lián)結詞與復合命題則: (1) p ； (2) q .例 符號化：（1）張偉不是三好學生;（2） 不是有理數(shù) 。 解：記 p：張偉是三好學生

5、。 q： 是有理數(shù)。 例 1.2 將下列命題符號化。 (1) 是有理數(shù)是不對的.（2）2是偶素數(shù). (3) 2或4是偶素數(shù). (4) 如果2是素數(shù)，則3也是素數(shù). (5) 2是素數(shù)當且僅當3是素數(shù).解：記 p： 是有理數(shù). q：2是素數(shù). r：2是偶數(shù). s：3是素數(shù). t：4是偶數(shù).則各語句表述為：非p; (2) q與r; (3) p或t; (4)如果q,則s；(5) q當且僅當s . 8/27/2022 8Discrete Math. , Chen Chen 定義1.2 設 p , q 為兩個命題。復合命題“ p 與q” 即“p 并且q” 稱為 p 與 q 的合取式，記為 p q。符號稱為

6、合取聯(lián)結詞。規(guī)定： p q為真當且僅當 p 與q 同時為真。注：自然語言中 “與”, “和”, “且”, “既.又”, “不僅而且”, “雖然但是”, “一面一面”等聯(lián)結詞都可以符號化為； 但并不是所有的“與”、“和”等都能用聯(lián)結詞替代。8/27/2022 9Discrete Math. , Chen Chen (1) 吳穎既用功又聰明. (2)吳穎不僅用功而且聰明. (3)吳穎雖然聰明，但不用功. (4) 張輝和王麗都是三好學生. (5) 張輝和王麗是同學.例1.3 將下列命題符號化 pq; pq; qp；rs。(5) 是原子命題,符號化為t: 張輝和王麗是同學。則符號化分別為： 解: (1

7、)、(2)、(3)、(4)： 令p:吳穎用功；q:吳穎聰明， r: 張偉是三好學生；s: 王輝是三好學生.8/27/2022 10Discrete Math. , Chen Chen定義1.3 設 p , q 為兩個命題 , 復合命題 “ p 或 q ” 稱為 p 與 q 的析取式, 記為 pq。符號稱為析取聯(lián)結詞。規(guī)定： pq 為假當且僅當 p 與 q 同時為假。注: 自然語言中的 “或” 聯(lián)結的兩個命題可以具有相容性，也可以具有排斥性。前者稱為相容或，后者稱為排斥或。析取聯(lián)結詞指的是“相容或”。8/27/2022 11Discrete Math. , Chen Chen（1）張曉靜愛唱歌或

8、愛聽音樂。（2）張曉靜只能挑選202房或203房。（3）張曉靜是江西人或安徽人。解：(1)令p:張曉靜愛唱歌；q:張曉靜愛聽音樂， 則：例1.4 將下列命題符號化pq ; (2)令r:張曉靜住202房；s:張曉靜住203房，則:(rs)(rs);(3)令t:張曉靜是江西人；u:張曉靜是安徽人，則：(tu)(tu).8/27/2022 12Discrete Math. , Chen Chen 定義1.4 設 p,q為兩個命題。復合命題 “如果 p,則 q ”稱為p與q的蘊涵式，記作pq。符號稱為蘊涵聯(lián)結詞， 稱p是蘊涵式的前件，q是蘊涵式的后件，q是p的必要條件。規(guī)定： pq為假當且僅當 p 為

9、真q為假。 注： 1.在自然語言中，“如果p, 則q”這種命題還有其它敘述方式，比如：“只要p, 就q”，“ 因為p，所以 q”, “p僅當q”, “只有q才p”，“除非q才p”, “除非q，否則非p ”等等，它們都可符號化為 pq。2.在數(shù)學或其它自然科學中，“如果p,則q” 往往表達的是前件p為真，后件q也為真的推理關系。但在數(shù)理邏輯中，作為一種規(guī)定，當 p為假時，無論q是真是假，pq均為真（因為考慮的整個語句）。3.在自然語言中，“如果 p, 則 q ” 中的前件 p 和后件 q 往往具有某種內(nèi)在聯(lián)系，而在數(shù)理邏輯中，p 與 q 可以無任何內(nèi)在聯(lián)系。8/27/2022 13Discret

10、e Math. , Chen Chen(1) 如果3+3 = 6,則雪是白色的。(2) 如果3+3 6,則雪是白色的。(3) 如果3+3 = 6,則雪不是白色的。(4) 如果3+3 6,則雪不是白色的。(5) 只要 a 能被整除，則 a 一定能被整除。(6) a 能被整除，僅當 a 能被整除。(7) 除非 a 能被整除，a 才能被整除。(8) 除非 a 能被整除，否則 a 不能被整除。(9) 只有 a 能被整除，a 才能被整除。(10) 只有 a 能被整除，a 才能被整除。(a 是一個給定的正整數(shù)）。例1.5 將下列命題符號化，并指出各復合命題的真值。解：令p：3+3=6； q：雪是白色的。則

11、 (1) 到 (4) 的符號化形式分別為： 令r：a 能被整除； s: a能被整除。 (5) 到 (9) 都可符號化為:pq；pq；pq；pq。它們的真值分別為：,。(10)可符號化為rs,真值為。sr，真值視 a 的值而定。8/27/2022 14Discrete Math. , Chen Chen定義1.5設 p, q 是兩個命題，復合命題 “ p 當且僅當 q ”稱為 p 與 q 的等價式，記為 pq。符號稱為等價聯(lián)結詞。規(guī)定： pq 為真當且僅當 p 與 q 同時為真或同時為假。注：pq 可理解為“q與p互為充分必要條件”； 它與(pq)(qp)的邏輯關系完全一致。8/27/2022

12、15Discrete Math. , Chen Chen (1) 3 是無理數(shù)當且僅當加拿大位于亞洲。(2) 2+3=5的充要條件是3是無理數(shù)。(3)若兩圓的面積相等, 則它們的半徑相等, 反之亦然。(4)當王小紅心情愉快時, 她就唱歌, 反之, 當她唱歌時, 一定心情愉快。解：(1)令p:3是無理數(shù)；q: 加拿大位于亞洲，則符號化為(4)令x:王小紅心情愉快；y:王小紅唱歌，則符號化為p q , 真值為0。(2)令r:2+3=5；令p:3是無理數(shù)，則符號化為r p , 真值為1。 (3)令s:兩圓面積相等；t:兩圓半徑相等，則符號化為x y , 真值由具體情況而定。s t ,真值為1。例 1

13、.6 將下列命題符號化，并討論它們的真值。8/27/2022 16Discrete Math. , Chen Chen 以上定義的五種最基本的聯(lián)結詞組成一個聯(lián)結詞集， 。由其中某個聯(lián)結詞聯(lián)結兩個原子命題（聯(lián)結一個原子命題）所形成的復合命題稱為基本復合命題，它們的真值情況如下表。 p qppqpqpqpq小 結110000010111110110010 00 11 01 18/27/2022 17Discrete Math. , Chen Chen 多次使用聯(lián)結詞集中的聯(lián)結詞，可組成更為復雜的復合命題。求復雜的復合命題的真值時，可依據(jù)上述真值表逐次求取。但運算過程中應注意聯(lián)結詞的優(yōu)先順序(包括括

14、號)： ( ), , , , ，。對同一優(yōu)先級的聯(lián)結詞，按出現(xiàn)的先后次序運算。例1.7 令：p：北京比天津人口多；q：2+2=4；r：烏鴉是白色的。求下列命題的真值：(1) (pq)(pq) r ; (2) ( qr) (p r); (3) (pr) (pr).解： p , q , r 的真值分別為1, 1, 0 ， 按照真值表及命題式，(1), (2), (3)的真值分別為1, 1, 0。8/27/2022 18Discrete Math. , Chen Chen定義1.6 簡單命題（原子命題）稱為命題常項，而稱真值可以變化的陳述句為命題變項。命題變項一般也用小寫字母p,q,r,來表示。 將

15、命題變項用聯(lián)結詞和括號按一定邏輯關系聯(lián)結起來的符號串稱為合式公式或命題公式。具體地說, 合式公式定義如下: (1)單個命題變項是合式公式, 稱為原子命題公式. (2)若A是合式公式, 則(A)也是合式公式. (3)若A,B是合式公式,則(AB),(AB),(AB),(AB)也是合式公式. (4)只有有限次地應用(1)(3)形成的符號串才是合式公式.設A是合式公式, B是中的一部分, 若B是合式公式, 則稱B為A的子公式. 例如: p, (pq)(r), (pq)(qr), (pq)r, p(qr) 都是命題公式。 說明：元語言與對象語言, 外層括號可以省去1.2 命題公式及其賦值8/27/20

16、22 19Discrete Math. , Chen Chen 定義1.7 (1) 若命題公式A是單個命題變項，則稱A為0層公式。 (2) 稱命題A是n+1(n0) 層公式，只要A是下列情況之一： (a) A = B, B 是 n層公式; (b) A= BC, B, C 分別為 i 層和j 層公式，且max (i , j)= n。 (c) A=BC, B, C 分別為 i 層和j 層公式，且max ( i , j)= n。 (d) A= BC, B, C 分別為 i 層和j 層公式，且max ( i , j)= n。 (e) A= BC, B, C 分別為 i 層和j 層公式，且max (i

17、, j)= n。 例如: (pq)r, (pq)( rs) p) 分別為 3層和 4 層公式。8/27/2022 20Discrete Math. , Chen Chen 由于命題公式中含有命題變項，故其真值一般是不確定的。當公式中所有命題變項都解釋成具體的命題后，命題公式就成了真值確定的命題了。 例如，命題公式 (pq)r :則命題公式 (pq)r 就被解釋成了一個真命題。 若將 p 解釋成:2 是素數(shù), q 解釋成:3是偶數(shù), r 解釋成： 是無理數(shù)。則 (pq)r 就被解釋成了一個假命題。另外，如果p, q 的解釋不變，而將r解釋成： 是有理數(shù)，8/27/2022 21Discrete

18、Math. , Chen Chen定義 1.8 設在命題公式A 中出現(xiàn)的所有命題變項為p1 , p2 , pn ， 給它們各指定一個真值，稱為對公式A的一個賦值 (或解釋)。若一個賦值使A的真值為1，則稱該賦值為A的成真賦值，否則稱為A的成假賦值。注：設A中的變項為p1 , p2 , , pn ，給A的賦值 a1 , a2 , an 是指p1 =a1, p2 =a2 , pn=an ，其中ai 為 0 或 1, (i = 1,2, n)。 例如：公式 (p1p2p3)(p1p2)中，000 (即 p1 =0, p2 =0, p3=0)和 110 都是而 001(即 p1 =0 , p2 =0,

19、 p3=1)和 011 都是成真賦值；成假賦值。賦值8/27/2022 22Discrete Math. , Chen Chen 定義 1.9 將命題公式A在所有賦值下的取值情況列成表，稱為A的真值表。 含n個命題變項的公式共有2n 個不同的賦值。構造真值表的一般步驟如下：列出命題公式中的所有命題變項 p1, p2, pn，(無下標時按字典序排列)。列出這些變項的所有2n 個賦值。一般從000開始，按二進制加法依次列到111為止。(2) 按從低到高的順序依次列出公式的各個層。 (3) 對應于變項的2n 個賦值分別計算出各層的真值，直至算出公式的真值。真值表8/27/2022 23Discret

20、e Math. , Chen Chen例1.8 寫出下列公式的真值表，并求它們的成真、成假賦值。 (1)(pq)r; (2)(pp)(qq); (3) (pq)qrp q rprpq(pq)r解： (pq)r 的真值表 111100000 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 11010101000110000111011118/27/2022 24Discrete Math. , Chen Chen(pp)(qq)的真值表 p qpqppqq(pp)(qq)0 00 11 01 1(pq)qr 的真值表 p q rpq(pq)(pq)q(pq)qr0 0

21、00 0 10 1 00 1 11 0 01 0 11 1 01 1 111111100101000000000111100110000110000000000000000008/27/2022 25Discrete Math. , Chen Chen定義1.10 設A是一個命題公式。若A在各種賦值下取值總為1，則稱A是永真式或重言式。(2) 若A在各種賦值下取值總為0，則稱A是永假式或矛盾式。(3) 若A不是矛盾式，則稱A為可滿足式。 注：A是可滿足式當且僅當A至少存在一個成真賦值。 1. 重言式必是可滿足式，但反之不真。 2. 可用真值表來判斷公式的類型：若真值表最后一列全為1，則公式為重言式；(2) 若真值表最后一列全為0，則公式為矛盾式；(3)若真值表最后一列至少有一個1，則公式為可滿足式。公式分類8/27/2022 26Discrete Math. , Chen Chen 給定n個命題變項，使用聯(lián)結詞和括號，可構成無窮多個命題公式。 個命題變項共有 2n 個可能的賦值，而在每個賦值下公式只能取值或1。因此含個命題變項的公