1.離散數(shù)學-命題邏輯課件

1、莊伯金 ,1,第一章,命題邏輯,莊伯金 ,2,主要內(nèi)容,命題的基本概念 等值演算 聯(lián)結(jié)詞完備集 范式 組合電路 推理理論,莊伯金 ,3,命題的基本概念,命題的定義 能判斷真假的陳述句 命題的兩個關鍵要素 必須是陳述句 能明確地判斷真假 命題的真值 判斷為正確的命題，其真值為真（1）； 判斷為錯誤的命題，其真值為假（0）。,莊伯金 ,4,命題的例,4是素數(shù)。 x大于y。 充分大的偶數(shù)等于兩個素數(shù)之和。(歌德巴赫猜想) 2020年5月1日北京的天氣是晴天 。 請不要吸煙！ 這朵花真美麗??！ 我正在說假話。 你現(xiàn)在好嗎？,莊伯金 ,5,命題符號化,命題常用小寫字母表示，如p：4是素數(shù) 命題的真值表示

2、： 1表示真 0表示假 簡單命題 不能被分解為更簡單的陳述句的命題 也稱為原子命題 命題常項與命題變項 命題常項：真值可以確定； 命題變項：真值可以變化的簡單陳述句。本質(zhì)不是命題。,莊伯金 ,6,復合命題及聯(lián)結(jié),復合命題：由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。 常見聯(lián)結(jié)詞 否定聯(lián)結(jié)詞 合取聯(lián)結(jié)詞 析取聯(lián)結(jié)詞 蘊涵聯(lián)結(jié)詞 等價聯(lián)結(jié)詞,莊伯金 ,7,例 P：今天是星期二。 p：今天不是星期二。 q：所有人都來上課了。 q：不是所有人來上課了。 有人沒來上課。,否定式,定義：復合命題“非p”稱為p的否定式，記作p。為否定聯(lián)結(jié)詞。 p為真當且僅當p為假。即p表示對p的真值取反。,莊伯金 ,8,例 小李既

3、勤奮又聰明。 小李不僅勤奮而且聰明。 小李雖然聰明，但是不勤奮。 小李和小王都很勤奮。 小李和小王是同學。 注：并不是所有的“和”、“與”都表示合取關系。,合取式,定義：復合命題“p并且q”稱為p與q的合取式，記作pq。 為合取聯(lián)結(jié)詞。 pq為真當前僅當p與q同時為真。其他情況時pq為假。,莊伯金 ,9,例 小李愛唱歌或者愛打籃球。 小李在打籃球或者在踢足球。 小李五一預訂4月30日或者5月1日的火車出去旅游。,析取式,定義：復合命題“p或者q”稱為p與q的析取式，記作pq。為析取聯(lián)結(jié)詞。 pq為假當且僅當p與q同時為假。其他情況pq為真。,莊伯金 ,10,析取式,自然語言中的“或”具有二義性

4、 相容或 不同時為真的排斥或 能同時為真的排斥或 析取式中的“或”與自然語言中的“或”含義不完全相同。 析取式可表示“相容或”和“不同時為真排斥或”； “能同時為真的排斥或”可用“異或”關系表示。,莊伯金 ,11,蘊涵式,定義：復合命題“如果p，則q”稱為p與q的蘊涵式，記作pq。 pq為假當前僅當p為真且q為假。其他情況時， pq為真。,自然語言中p與q具有聯(lián)系，而數(shù)理邏輯中p與q可以沒有聯(lián)系。 例 如果336，則雪是黑的。 如果3+36，則雪是黑的。,莊伯金 ,12,蘊涵式,pq在邏輯上表明p為q的充分條件，q為p的必要條件。 例 只要a能被4整除，則a一定能被2整除。 a能被4整除，僅當

5、a能被2整除。 除非a能被2整除，a才能被4整除。 只有a能被2整除，a才能被4整除。 只有a能被4整除，a才能被2整除。,莊伯金 ,13,等價式,定義：復合命題“p當且僅當q”稱為p與q的等價式，記作pq。稱作等價聯(lián)結(jié)詞。 pq為真當且僅當p與q真值相同。其他情況時，pq為假。,pq在邏輯上表明p與q互為充要條件。 例： 若今天為1號，則明天是2號，反之亦然。 今天是雨天當且僅當雪是黑的。,莊伯金 ,14,基本復合命題真值表,莊伯金 ,15,聯(lián)結(jié)詞的優(yōu)先順序,() ,莊伯金 ,16,練習,判斷下列命題的真值 若224，則336 若224，則336 若224，則336 若224，則336 22

6、4當且僅當336 224當且僅當336 224當且僅當336 224當且僅當336,莊伯金 ,17,練習,將下列命題符號化 2是偶數(shù)又是素數(shù) 他一邊吃飯一邊看電視 如果天下雨，他就乘公共汽車上班 只有天下雨，他才乘公共汽車上班 不經(jīng)一事，不長一智,莊伯金 ,18,練習,設p、q的真值為0，r、s的真值為1，求下列命題公式的真值 p(qr) (pr)(qs),莊伯金 ,19,命題公式,命題常項（命題常元）：簡單命題，真值唯一確定。 命題變項（命題變元）：真值可以變化的陳述句。 命題常項和命題變元都用小寫字母表示。 合式公式（命題公式）：將命題變項用聯(lián)結(jié)詞和圓括號按一定的邏輯關系聯(lián)結(jié)起來的符號串。

7、,莊伯金 ,20,合式公式的定義,遞歸定義 1. 單個命題變項是合式公式，并稱為原子命題公式； 2. 若A是合式公式，則(A)也是合式公式； 3. 若A，B是合式公式，則(AB)，(AB)，(AB)，(AB)也是合式公式； 4. 只有有限次地應用13形式的符號串才是合式公式。 子公式定義 若A為合式公式，B為A的一部分，且B也是合式公式，則稱B為A的子公式。,莊伯金 ,21,公式的賦值,定義 設A為一命題公式，p1, p2, , pn, 為所有在A中出現(xiàn)的命題變項。給p1, p2, , pn指定一組真值，稱其為A的一個賦值或解釋。 若指定的一組賦值使A的真值為真，則稱這組值為A的成真賦值。 若

8、指定的一組賦值使A的真值為假，則稱這組值為A的成假賦值。 將一個命題公式在所有賦值下的情況列成表，稱為這個公式的真值表。 n個命題變項共有2n組賦值。,莊伯金 ,22,例,p(qr)的真值表,莊伯金 ,23,例,p(pq)的真值表,莊伯金 ,24,例,p(pq)的真值表,莊伯金 ,25,重言式（永真式）： 所有的賦值都是A的成真賦值。 矛盾式（永假式）： 所有的賦值都是A的成假賦值。 可滿足式： 至少存在一組賦值使A為真。,莊伯金 ,26,等值演算,等值式（等價式） 設A，B為兩命題公式，若AB為重言式，則稱A與B為等值式，記為AB。 不是邏輯聯(lián)結(jié)詞，表示對任意的賦值，A與B的值相同。 是等價

9、聯(lián)結(jié)詞，它與不能混為一談。 等值式的性質(zhì)（等價關系的通性） 自反性：AA； 對稱性：若AB，則BA； 傳遞性：若AB和BC，則AC。,莊伯金 ,27,例,pq與pq是否等值？,莊伯金 ,28,基本等值規(guī)律(1),雙重否定律 AA 等冪律 AAA AAA 交換律 ABBA ABBA 結(jié)合律 A(BC)(AB)C A(BC)(AB)C,莊伯金 ,29,基本等值規(guī)律(2),分配律 A(BC)(AB)(AC) A(BC)(AB)(AC) 德.摩根律 (AB)AB (AB)AB 吸收律 A(AB)A A(AB)A,莊伯金 ,30,基本等值規(guī)律(3),零律 A11 A00 同一律 A0A A1A 排中律

10、AA1 矛盾律 AA0,莊伯金 ,31,基本等值規(guī)律(4),蘊涵等值式 ABAB 等價等值式 AB(AB)(BA) (AB)(BA) 假言易位 ABBA 等價否定等值式 ABAB 歸謬論 (AB)(AB)A,莊伯金 ,32,置換規(guī)則,設(A)為含公式A的命題公式，(B)為用公式B置換了A的命題公式，若AB，則(A)(B)。 利用等值規(guī)律及置換規(guī)則可以進行等值演算。 例 (pq)(qp) (qp)p (pq)(qp) (pq) r (p(pq)r,莊伯金 ,33,聯(lián)結(jié)詞的完備集,問題：含n個命題變項的命題公式其真值表的可能性有多少種？ n元真值函數(shù)：F：0,1n0,1為n元真值函數(shù)。 聯(lián)結(jié)詞完備

11、集：設S是一個聯(lián)結(jié)詞集合，如果任何n元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構成的公式表示，則稱S是聯(lián)結(jié)詞完備集。 , , , , , ,莊伯金 ,34,對偶,對偶的定義：在僅含有, , 的命題公式A中，將換成， 換成，若A中含0或1，將0換成1，1換成0，所得的命題公式稱為A的對偶式，記為A*。 定理：設A和A*互為對偶式， p1, p2, , pn是出現(xiàn)在A和A*中的全部命題變項，若將A和A*寫成n元函數(shù)形式，則： (1)A(p1, p2, , pn)A*(p1,p2, ,pn) (2) A(p1,p2, ,pn)A*(p1, p2, , pn) 對偶原理：設A、B為兩命題公式，若AB，則A*B

12、*。,莊伯金 ,35,范式的概念,命題公式的規(guī)范表示方法 析取范式 合取范式 文字：命題變項及其否定式統(tǒng)稱文字 簡單析取式 僅有有限個文字構成的析取式 簡單合取式 僅有有限個文字構成的合取式 定理： 一個簡單析取式是重言式當且僅當它同時含某個命題變項及其否定式 一個簡單合取式是矛盾式當且僅當它同時含某個命題變項及其否定式,莊伯金 ,36,析取范式,定義 由有限個簡單合取式構成的析取式 例 pq (pq)r 析取范式性質(zhì) 析取范式是矛盾式當且僅當它的每個簡單合取式是矛盾式,莊伯金 ,37,合取范式,定義: 由有限個簡單析取式構成的合取式 例 pq (pq)r 合取范式性質(zhì) 合取范式是重言式，當且

13、僅當它的每個簡單析取式是重言式,莊伯金 ,38,范式存在定理,定理：任一命題公式都存在與之等值的析取范式（合取范式）。 求范式的步驟 消除蘊含和等價：利用蘊涵等值式和等價等值式消去聯(lián)結(jié)詞 、。 否定內(nèi)移：用雙重否定律消去否定聯(lián)結(jié)詞，利用德.摩根律將否定聯(lián)結(jié)詞內(nèi)移。 調(diào)整合取與析取位置：利用分配律求析取范式或合取范式。,范式的求解,例： (pq)r,莊伯金 ,39,莊伯金 ,40,極小項與極大項,極小項的定義 在含n個命題變項的簡單合取式中，如果每個變項與其否定式不同時存在，但兩者之一恰出現(xiàn)1次，且第i個命題變項或否定式出現(xiàn)在從左起的第i位上。 極大項的定義 在含n個命題變項的簡單析取式中，如果

14、每個變項與其否定式不同時存在，但兩者之一恰出現(xiàn)1次，且第i個命題變項或否定式出現(xiàn)在從左起的第i位上。 n個命題變項共可形成2n個極小項和2n個極大項。,莊伯金 ,41,極小項的成真賦值,每個極小項僅有一個成真賦值 每個極小項的成真賦值均不相同 可以利用不同的成真賦值區(qū)別每個極小項，給予標記,莊伯金 ,42,極大項的成假賦值,每個極大項僅有一個成假賦值 每個極大項的成假賦值均不相同 可以利用不同的成假賦值區(qū)別每個極大項，給予標記,莊伯金 ,43,主析取范式與主合取范式,主析取范式的定義 若A的命題公式由若干個極小項進行析取構成，則稱該析取范式為A的主析取范式 從主析取范式中很容易得到成真賦值 主

15、合取范式的定義 若A的命題公式由若干個極大項進行合取構成，則稱該合取范式為A的主合取范式 從主合取范式中很容易得到成假賦值 定理：任何命題公式都存在與之等值的主析?。ê先。┓妒?，且唯一。,莊伯金 ,44,主析取范式的求解方法(1),用等值演算求得析取范式 依次掃描析取范式中的每個簡單合取式B 若B為極小項，則繼續(xù)掃描下一個 若B不為極小項，將不含的命題變項p及其否定式p用等值變換添入BB(pp) (Bp)(Bp) 消去重復出現(xiàn)的命題變項、極小項和矛盾式。,莊伯金 ,45,主析取范式的求解方法(2),根據(jù)公式構造真值表 寫出每個公式成真賦值對應的極小項 將極小項進行析取，即得主析取范式,莊伯金

16、,46,主析取范式,例：求(p(qr)(p(qr),莊伯金 ,47,主合取范式的求解方法(1),用等值演算求得合取范式 依次掃描合取范式中的每個簡單析取式B 若B為極大項，則繼續(xù)掃描下一個 若B不為極大項，將不含的命題變項p及其否定式p用等值變換添入BB (pp) (Bp)(Bp) 消去重復出現(xiàn)的命題變項、極大項和重言式。,莊伯金 ,48,主合取范式的求解方法(2),根據(jù)公式構造真值表 寫出每個公式成假賦值對應的極大項 將極大項進行合取，即得主合取范式,莊伯金 ,49,主合取范式,例：求(p(qr)(p(qr),莊伯金 ,50,主析取范式與主合取范式,主析取范式與主合取范式之間的關系？,莊伯金

17、 ,51,組合電路,邏輯運算可以由電子元件物理實現(xiàn) 與門 或門 非門 組合電路的設計步驟 構造輸入輸出表，得到真值表 根據(jù)真值表獲得主析取范式，獲得組合電路 優(yōu)化電路，得到最簡展開式,莊伯金 ,52,組合電路,簡單合取式的合并：兩個簡單合取式中，若二進制表示中恰有一位不同，則可將這兩個簡單合取式合并化簡 例： (pqr)(pqr) (111與011) 合并為：qr (-11) 奎因-莫可拉斯基方法 合并簡單合取式：從主析取范式的極小項開始，逐步將所有可能合并的簡單合取式進行合并，直到不能被合并為止。 確定最簡展開式中的項：從所有不能被合并的項中選擇若干項，使其覆蓋原公式的所有極小項，且運算符盡

18、可能小。,莊伯金 ,53,組合電路,例：一盞燈由2個開關控制，要求按任何一個開關都能使燈由黑變亮或由亮變黑，試設計該組合電路。 例：求(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)(pqrs)的最簡展開式,組合電路,合并 選取 （1，2）（3，4，7，8）（5，6，7，8）,莊伯金 ,54,莊伯金 ,55,推理的形式結(jié)構,設兩命題公式A、B，若AB為重言式，則稱A蘊涵B，記為AB。 設A1、A2、.、An、B為命題公式，若A1A2. An B，則稱B為A1、A2、.、An的邏輯結(jié)論或有效結(jié)論，也稱B可由一組前提A1、A2、.、An邏輯推出。記為A1，A2，

19、.，AnB。 正確推理的本質(zhì)是A1A2. AnB為重言式。 當A1A2. An為假時，不論B是真是假， A1A2. AnB均為真。所以B為有效結(jié)論并不意味B為真。,莊伯金 ,56,推理的基本方法,簡單證明法： 證明A1A2. AnB是重言式，即A1A2. AnB1。 真值表法 等值演算法 主析取范式法 例：若a能被4整除，則a能被2整除。因為a能被2整除，所以a能被4整除。,莊伯金 ,57,推理的基本方法(2),直接構造證明法 由給定的一組前提出發(fā)，利用推理規(guī)則逐步演算得到結(jié)論。 常用推理規(guī)則 前提引入規(guī)則：在證明過程的任何步驟都可以將前提引入使用 結(jié)論引入規(guī)則：在推理中，若已證出結(jié)論B，則B可以引入到以后的推理中作為前提使用 置換規(guī)則：命題公式中任何子公式都可以用等值公式置換 化簡規(guī)則： AB A， AB B 附加規(guī)則： AAB,