第一章數(shù)理邏輯 (1)

1、離散數(shù)學(xué),數(shù)理邏輯,邏輯學(xué) 是一門研究思維形式及思維規(guī)律的科學(xué),現(xiàn)代形式邏輯 在方法、目的和觀念上與現(xiàn)代數(shù)學(xué)相聯(lián)系,一開始就被稱為數(shù)理邏輯，即符號(hào)邏輯。,數(shù)理邏輯 用數(shù)學(xué)的方法（引入一套符號(hào)體系的方法）來研究邏輯。,背景知識(shí),起源： 17世紀(jì)中葉，萊布尼茲（德國(guó)的數(shù)學(xué)家、物理學(xué)家、哲學(xué)家）曾經(jīng)提出“用計(jì)算機(jī)代替思維完成推理過程”的設(shè)想。,這個(gè)想法太超前了！,發(fā)展英國(guó)數(shù)學(xué)家布爾在1847年創(chuàng)立了布爾代數(shù)，奠

2、定了數(shù)理邏輯的基礎(chǔ)。,1854年發(fā)表了《思維規(guī)律》這部杰作，他采用數(shù)學(xué)的方法處理邏輯推理，布爾代數(shù)的問世是數(shù)學(xué)史一個(gè)重要的里程碑。,布爾代數(shù)發(fā)明后沒有受到人們的重視，布爾在他的杰作出版后不久就去世了。,數(shù)學(xué)家布爾,布爾，自學(xué)成才的典范。鞋匠的兒子，從小打工幫襯家用，原想做牧師，但生活所迫16歲做了中學(xué)教師。教書時(shí)自學(xué)牛頓的《數(shù)學(xué)原理》、拉格朗日的《解析函數(shù)論》和拉普拉斯的《天體力學(xué)》，雖沒學(xué)位但成了數(shù)學(xué)教授。主要貢獻(xiàn)是創(chuàng)立了布爾代數(shù)，在

3、電子工程、計(jì)算機(jī)、數(shù)理邏輯中有很多應(yīng)用。,布爾的五朵金花,布爾40歲英年早逝，但他的五朵金花女兒很厲害。二女a(chǎn)licia在四維幾何方面卓有貢獻(xiàn)，四女是英國(guó)化學(xué)的第一個(gè)女教授，小女是《牛虻》的作者伏尼契。小女的孫女中文名字叫寒春，芝加哥大學(xué)核物理博士，參加過曼哈頓原子彈計(jì)劃；后長(zhǎng)期定居中國(guó)，拿到中國(guó)的第一張永久居留證。,完備德國(guó)的數(shù)學(xué)家弗雷格在1879年引入了量詞、約束元。為數(shù)理邏輯開辟了新的領(lǐng)域。,完善德國(guó)著名的數(shù)學(xué)家哥德爾在193

4、1年 提出了不完全性定理的證明。,此外，美國(guó)的數(shù)學(xué)家德?摩根、羅素都作出了很大的貢獻(xiàn)。,該定理與塔斯基的形式語言的真理論，圖靈機(jī)和判定問題，被贊譽(yù)為現(xiàn)代邏輯科學(xué)在哲學(xué)方面的三大成果。是現(xiàn)代邏輯史上很重要的一座里程碑。,近代馮?諾依曼、圖靈、克林等人研究了邏輯與計(jì)算的關(guān)系。邏輯程序設(shè)計(jì)語言的研制，更促進(jìn)了數(shù)理邏輯的發(fā)展。,數(shù)理邏輯,命題邏輯,一階邏輯,,中心問題：研究推理推理（前提，結(jié)論）—— 都是表達(dá)判斷的陳述句,一個(gè)土耳其商人想找

5、一個(gè)十分聰明的助手協(xié)助他經(jīng)商，有兩人前來應(yīng)聘，這個(gè)商人為了試試哪個(gè)更聰明些，就把兩個(gè)人帶進(jìn)一間漆黑的屋子里，他打開燈后說：“這張桌子上有五頂帽子，兩頂是紅色的，三頂是黑色的，現(xiàn)在，我把燈關(guān)掉，而且把帽子擺的位置弄亂，然后我們?nèi)齻€(gè)人每人摸一頂帽子戴在自己頭上，在我開燈后，請(qǐng)你們盡快說出自己頭上戴的帽子是什么顏色的?！闭f完后，商人將電燈關(guān)掉，然后三人都摸了一頂帽子戴在頭上，同時(shí)商人將余下的兩頂帽子藏了起來，接著把燈打開。這時(shí)，那兩個(gè)應(yīng)試者看

6、到商人頭上戴的是一頂紅帽子，其中一個(gè)人便喊道：“我戴的是黑帽子。”    請(qǐng)問這個(gè)人說得對(duì)嗎？他是怎么推導(dǎo)出來的呢？,第一章 命題邏輯基本概念,1.1 命題與聯(lián)結(jié)詞命題 表達(dá)判斷的陳述句。兩個(gè)條件：（1）陳述句； （2）能判斷真假。真值 命題的結(jié)果。 任何命題的真值都是唯一的。,例1.1 判斷下列句子是否為命題。 (1) 4是素?cái)?shù)。 &#

7、160; (2) √2是無理數(shù)。     (3) x大于y。      (4) 月球上有冰。 (5) 2100年元旦是晴天。   (6) π大于 嗎？ (7) 請(qǐng)不要吸煙！ (8) 這朵花真美麗??！ (9) 我正在說假話。,是,是,

8、否,是,是,否,否,否,否,世界文學(xué)名著《唐·吉訶德》中有這樣一個(gè)故事：唐·吉訶德的仆人桑喬·潘跑到一個(gè)小島上，成了這個(gè)島的國(guó)王。他頒布了一條奇怪的法律：每一個(gè)到達(dá)這個(gè)島的人都必須回答一個(gè)問題：“你到這里來做什么？”如果回答對(duì)了，就允許他在島上游玩，而如果答錯(cuò)了，就要把他絞死。對(duì)于每一個(gè)到島上來的人，或者是盡興地玩，或者是被吊上絞架。有多少人敢冒死到這島上去玩呢？一天，有一個(gè)膽大包天的人來了，他照例被問了這

9、個(gè)問題，而這個(gè)人的回答是：“我到這里來是要被絞死的?！闭?qǐng)問桑喬·潘薩是讓他在島上玩，還是把他絞死呢？如果應(yīng)該讓他在島上游玩，那就與他說“要被絞死”的話不相符合，這就是說，他說“要被絞死”是錯(cuò)話。既然他說錯(cuò)了，就應(yīng)該被處絞刑。但如果桑喬·潘薩要把他絞死呢？這時(shí)他說的“要被絞死”就與事實(shí)相符，從而就是對(duì)的，既然他答對(duì)了，就不該被絞死，而應(yīng)該讓他在島上玩。小島的國(guó)王發(fā)現(xiàn)，他的法律無法執(zhí)行，因?yàn)椴还茉趺磮?zhí)行，都使法律受到破壞

10、。他思索再三，最后讓衛(wèi)兵把他放了，并且宣布這條法律作廢。這又是一條悖論。,悖論：由真推出假，又由假推出真從而既不能為真，又不能為假的陳述句。,凡是悖論都不是命題。,1.1 命題與聯(lián)結(jié)詞,命題符號(hào)化 對(duì)自然語言描述的命題及其真值抽象化， 用符號(hào)來表示。 用小寫字母p,q,r…或pi ,qi ,ri …表示命題； 用“1”表示真，“0”表示假；如：p:2是素?cái)?shù)。q:雪是黑色的。 則 p是真

11、命題，q假命題,如：如果今天下雨，我就乘公交車上班。 用了藍(lán)天六必治，牙好，胃口就好， 吃啥啥香。,簡(jiǎn)單命題 不能被分解成更簡(jiǎn)單的陳述句的 命題，又稱為原子命題。,復(fù)合命題 由簡(jiǎn)單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成 的命題。,自然語言中，常使用的“如果，就”，“因?yàn)椤?，所以…”，“或”，“與”，“但是”等將簡(jiǎn)單的陳述句組合在一塊，構(gòu)成一個(gè)復(fù)雜的句

12、子。數(shù)理邏輯中也要用到邏輯聯(lián)結(jié)詞。但自然語言中的邏輯聯(lián)結(jié)詞常具有二義性，且沒有符號(hào)化。,定義1.1 設(shè)p為命題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式,記作┐p，符號(hào) ┐稱作否定聯(lián)結(jié)詞。并規(guī)定┐p為真當(dāng)且僅當(dāng)p為假。 如：p：3是偶數(shù)。 ┐p：3不是偶數(shù),定義1.2 設(shè)p , q為二命題，復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結(jié)詞。并規(guī)定p∧q為真當(dāng)且僅當(dāng)p與q同時(shí)為真。 “

13、既…又…”、“不但…而且…”、“雖然…但是…”、“一面…一面…” 都可用∧如：p：今天下雨。q：今天降溫。 p∧q :今天下雨且今天降溫。 ┐p∧p其真值永為假。,r：我們?cè)谏险n。s：秘書們?cè)诹奶臁 ∧s：我們?cè)谏险n且秘書們?cè)诹奶臁?在自然語言中，上面的r ∧s無意義，但在數(shù)理邏輯中是允許的， r ∧s是一個(gè)新的命題。,定義1.3 設(shè)p，q為二命題，復(fù)合命題“p或q”稱作p與q的析取式

14、，記作p∨q，∨稱作析取聯(lián)結(jié)詞。并規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同時(shí)為假。 如：p: 張曉靜愛唱歌。 q: 張曉靜愛畫畫。 p∨q: 張曉靜愛唱歌或張曉靜愛畫畫。 自然語言中的“或”有時(shí)具有二義性：相容性和排斥性。對(duì)應(yīng)的聯(lián)結(jié)詞分別稱為相容或和排斥或。 “∨”應(yīng)是相容或。,例1.2 將下列命題符號(hào)化。1）燈泡有故障或開關(guān)有故障。2）張曉靜是江西人或安徽人。3）張曉靜只能挑選202或203房間。 4）小明

15、昨天做了二十或三十道習(xí)題。,p∨q,p∨q,（p ∧ ┐q) ∨(┐p ∧ q),原子命題,排斥或有兩種表示：1）客觀上不可能為真的，可符號(hào)化為如第二個(gè)小例；2）可能會(huì)同時(shí)取真，應(yīng)符號(hào)化為如第三個(gè)小例。,定義1.4 設(shè)p，q為二命題，復(fù)合命題“如果p，則q”稱作p與q的蘊(yùn)涵式，記作p→q，→稱作蘊(yùn)涵聯(lián)結(jié)詞。并規(guī)定p→q為假當(dāng)且僅當(dāng)p為真q為假。稱p為前件，q為后件。 p→q的邏輯關(guān)系表示q是p的必要條件。 當(dāng)前件為假，不

16、論后件真假與否，條件命題為真。如：喝海水的故事； 阿基米德杠桿撬地球。,在使用聯(lián)結(jié)詞→時(shí)，要特別注意以下幾點(diǎn) ：1）在自然語言里，特別是在數(shù)學(xué)中，q是p的必要條件有許多不同的敘述方式。例如，“只要p，就q”，“因?yàn)閜，所以q”，“p僅當(dāng)q”，“只有q才p”，“除非q才p”，“除非q，否則非p”等等。以上各種敘述方式表面看來有所不同，但都表達(dá)的是q是p的必要條件，因而所用聯(lián)結(jié)詞均應(yīng)符號(hào)化為→，上述各種敘述方式都應(yīng)符號(hào)化為p

17、→q。,2）在自然語言中，“如果p，則q”中的前件p與后件q往往具有某種內(nèi)在聯(lián)系。而在數(shù)理邏輯中，p與q可以無任何內(nèi)在聯(lián)系。3）在數(shù)學(xué)或其它自然科學(xué)中，“如果p，則q”往往表達(dá)的是前件p為真，后件q也為真的推理關(guān)系。但在數(shù)理邏輯中，作為一種規(guī)定，當(dāng)p為假時(shí)，無論q是真是假，p→q均為真。也就是說，只有p為真q為假這一種情況使得復(fù)合命題p→q為假。,例1.3 將下列命題符號(hào)化。1）只要天不下雨，我就騎自行車上班。2）只有天不下雨，

18、我才騎自行車上班。解：令 p：天下雨。 q：我騎自行車上班。1） ┐p →q 2) q → ┐p例1.4 設(shè) p：月亮出來了。 q：3*3=9。則p →q 表示：如果月亮出來了，則3*3=9。p →q的真假僅依賴于前件后件的真假，與命題含義無關(guān)。,定義1.5 設(shè)p，q為二命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式，記作p? q， 稱作等價(jià)聯(lián)結(jié)詞。并規(guī)定p ? q為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假。

19、p? q的邏輯關(guān)系為p與q互為充分必要條件。 例1.4 將下列命題符號(hào)化。1）2+2=4當(dāng)且僅當(dāng)3是奇數(shù)。2）2+2=4當(dāng)且僅當(dāng)3不是奇數(shù)。 3）2+2≠4當(dāng)且僅當(dāng)3是奇數(shù)。 4）2+2≠4當(dāng)且僅當(dāng)3不是奇數(shù)。解：令 p： 2+2=4 q： 3是奇數(shù)。1） p? q 的真值是1 2) p? ┐q 的真值是03) ┐p? q 的真值是0 4） ┐p? ┐q 的真值是1,自然語言中，運(yùn)

20、用等價(jià)概念的例子： “晏子使楚，以晏子短，楚人為小門于大門之側(cè)而延晏子。晏子不入，曰：使狗國(guó)，從狗門入；今臣使楚，不當(dāng)從此門入。”以上定義了五種最基本、最常用、也是最重要的聯(lián)結(jié)詞┐，∧，∨，→，? ，將它們組成一個(gè)集合{┐，∧，∨，→， ? }，稱為一個(gè)聯(lián)結(jié)詞集。其中┐為一元聯(lián)結(jié)詞，其余的都是二元聯(lián)結(jié)詞。 說明：1）基本復(fù)合命題┐p，p∧q，p∨q，p→q，p? q 2)優(yōu)先順序 （）、 ┐、∧、∨、→、?

21、 3）研究的是命題之間的真值關(guān)系，而非命題的內(nèi)容。,例1.5 令 p：北京比天津人口多。             q：2+2＝4。              r：烏鴉是白色的。

22、60;求下列復(fù)合命題的真值：    (1) ((┐p∧q)∨(p∧┐q))→r    (2) (q∨r)→(p→┐r)     (3) (┐p∨r) ? (p∧┐r)  解 p，q，r的真值分別為1，1，0，容易算出(1)，(2)，(3)的真值分別為1，1，0。,1.2命題公式及其賦值,命題常項(xiàng)（命題

23、常元）簡(jiǎn)單命題命題變項(xiàng)（命題變?cè)┮胩囟ǖ姆?hào)來表示任一簡(jiǎn)單命題，類似數(shù)學(xué)中變量的作用。也用p,q,r…或pi ,qi ,ri …表示。命題變項(xiàng)已不是命題（無確定的真值）命題公式 將命題變項(xiàng)用聯(lián)結(jié)詞和圓括號(hào)按一定的邏輯關(guān)系聯(lián)結(jié)起來的符號(hào)串，又稱合式公式，簡(jiǎn)稱公式，記為WFF,定義1.6 1)單個(gè)命題變項(xiàng)和命題常項(xiàng)是合式公式，并稱為 原子命題公式。 2)若A是合式公式，則(┐A)也是合式公式。

24、3)若A，B是合式公式，則(A∧B)，(A∨B)， (A→B)，(A ? B)也是合式公式。 4)只有有限次地應(yīng)用(1)～(3)形式的符號(hào)串才 是合式公式。如：(p→q)∧(q ? r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r，（p→(r→q)等不是合式公式。,對(duì)象語言符號(hào)：用來描述研究對(duì)象的語言符號(hào)元語言符號(hào)： 用來描述對(duì)象語言的語言符號(hào)， 如上述定

25、義中的A、B等子公式：A是公式，B是A的一部分，也是公式。則稱B是A的子公式。,定義1.7 (1)若公式A是單個(gè)的命題變項(xiàng)，則稱A為0層合式。(2)稱A是n+1(n≥0)層公式是指下面情之一 ：       a) A＝┐B，B是n層公式； b) A＝B∧C，或 A＝B∨C，或 A＝B→C，或 A＝B? C，其中B，C分別為i層和j層公式，且n＝max(i，j)；

26、(3)若公式A的層次為k，則稱A是k層公式。 易知，(┐p∧q)→r，(┐(p→┐q))∧((r∨s) ┐p)分別為3層和4層公式。,公式 (p ∨ q ) → r p：2是素?cái)?shù)，q：3是偶數(shù)，r解釋成：√2 是無理數(shù)， 公式解釋成：若2是素?cái)?shù)或3是偶數(shù)，則 √2  是無理數(shù)。這是一個(gè)真命題。若另令 r：√2 是有理數(shù)。則上述公式就被解釋為假命題。,定義1.8 設(shè)p1,p2,…,pn是出現(xiàn)在公式A中的全部命題符號(hào)，

27、給p1,p2,…,pn各指定一個(gè)真值，稱為對(duì)A的一個(gè)賦值（指派）或解釋。若指定的一組值使A的真值為1，則稱這組值為A的成真賦值；若使A的真值為0，則稱這組值為A的成假賦值。,例如：(┐p1∧┐p2∧┐p3)∨(p1∧p2) 000(p1＝0，p2＝0，p3＝0)，110(p1＝1，p2＝1，p3＝0)都是成真賦值;001(p1＝0，p2＝0，p3＝1)，011(p1＝0，p2＝1，p3＝1)都是成假賦值。又如：(p∧┐q)→r0

28、11(p＝0，q＝1，r＝1)為成真賦值，100(p＝1，q＝0，r＝0)為成假賦值。,含n(n≥1)個(gè)命題變項(xiàng)的公式共有2n個(gè)不同的賦值。,定義1.9 將命題公式A在所有賦值下取值情況列成表，稱作A的真值表。,構(gòu)造真值表的具體步驟如下： (1) 找出公式中所含的全體命題變項(xiàng)p1,p2,…,pn (若無下角標(biāo)就按字典順序排列)，列出2n個(gè)賦值。本書規(guī)定，賦值從00…0開始，然后按二進(jìn)制加法依次寫出各賦值，直到11…1為止。,(2)

29、按從低到高的順序?qū)懗龉降母鱾€(gè)層次。 (3) 對(duì)應(yīng)各個(gè)賦值計(jì)算出各層次的真值，直到最后計(jì)算出公式的真值。,解 公式(1)是含3個(gè)命題變項(xiàng)的3層合式公式。它的真值表如下所示。,例1.6 求下列公式的真值表，并求成真賦值和成假賦值。,(1)(┐p∧q)→┐r (2)(p∧┐p)? (q∧┐q)(3) ┐(p→q)∧q∧r （4） r → (q → p),1.2命題公式及其賦值,解 公式(2)是含2個(gè)命題變項(xiàng)的3層合式公式

30、。,(p∧┐p) ? (q∧┐q) 的真值表,┐(p→q)∧q∧r的真值表,解 公式(3)是含3個(gè)命題變項(xiàng)的4層合式公式。,解 公式(4)是含3個(gè)命題變項(xiàng)的2層合式公式。,r → (q → p) 的真值表,,,根據(jù)公式的取值情況對(duì)公式進(jìn)行如下分類:,定義1.10 設(shè)A為任一命題公式，,若A在它的各種賦值下取值均為真,則稱A是重言式或永真式。(2) 若A在它的各種賦值下取值均為假,則稱A是矛盾式或永假式。(3) 若A不是矛盾式,則

31、稱A是可滿足式。,上例中（2)是重言式，（3）是矛盾式，（1）、（4）是可滿足式。,說明：  1. A是可滿足式的等價(jià)定義是： A至少存在一個(gè)成真賦值。,2. 重言式一定是可滿足式，但反之不真。因而，若公式A是可滿足式，且它至少存在一個(gè)成假賦值，則稱A為非重言式的可滿足式。,3. 真值表可用來判斷公式的類型:   (1) 若真值表最后一列全為1，則公式為重言式。   (2

32、) 若真值表最后一列全為0，則公式為矛盾式。   (3) 若真值表最后一列中至少有一個(gè)1，則公式為可滿足式。,按照公式的構(gòu)造規(guī)則，可以形成無窮多種形式各異的公式，那么產(chǎn)生的真值表是否也是無窮多種？,在例4中（1）和(4)的公式形式雖然不同，但對(duì)三個(gè)命題變項(xiàng)的每一組賦值，公式對(duì)應(yīng)的真值都是相同的，它們具有相同的真值表。,,n個(gè)命題變?cè)伯a(chǎn)生2n個(gè)不同賦值,在每個(gè)賦值下,公式的值只有0和1兩個(gè)值。于是n個(gè)命題變?cè)獦?gòu)造的