命題與聯(lián)結(jié)詞

1、離 散 數(shù) 學(xué)（ Discrete Mathematics ）1課程介紹一、簡史“離散數(shù)學(xué)”是一門相對于“連續(xù)數(shù)學(xué)”而命名的數(shù)學(xué)分支。 產(chǎn)生于數(shù)學(xué)游戲(如一筆畫、過渡、組合、計(jì)數(shù)等)，分散于各個(gè)分支，計(jì)算機(jī)的產(chǎn)生推動了其形成和發(fā)展。二、知識模塊數(shù)理邏輯集合論和關(guān)系圖論初步代數(shù)系統(tǒng)三、學(xué)習(xí)要求1.首先要精確嚴(yán)格地掌握好概念和術(shù)語、理解基本定理的本質(zhì)；2. 獨(dú)立完成每一次作業(yè)，每次作業(yè)完成之后，能自覺地歸納出其中用到的基本解題方法；3.自學(xué)相關(guān)參考教材。2 數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門學(xué)科. 所謂數(shù)學(xué)方法是指:用一套數(shù)學(xué)的符號系統(tǒng)來描述和處理思維的形式與規(guī)律. 因此, 數(shù)理邏輯又稱為符號

2、邏輯.第一部分 數(shù)理邏輯3第一章 命題邏輯基本概念第二章 命題邏輯等值演算 第四章 一階邏輯基本概念第三章 命題邏輯的推理理論第五章 一階邏輯等值演算與推理4第一章 命題邏輯基本概念第1節(jié) 命題與聯(lián)結(jié)詞第2節(jié) 命題公式及其賦值5一、命題的概念二、復(fù)合命題與聯(lián)結(jié)詞第1節(jié) 命題與聯(lián)結(jié)詞6一、命題的概念1 命題：能判斷真假的陳述句稱為命題。 （1） 真值 : 命題判斷真假的結(jié)果真值只取兩個(gè)值：真或假。（2）真命題：真值為真的命題； 假命題：真值為假的命題。（4） 判斷命題分兩步：是否為陳述句 是否有唯一真值（3）任何命題的真值都是唯一的。 7例1.1 判斷下列句子是否為命題(1) 4是素?cái)?shù)。(2)

3、是無理數(shù)。(3) x大于y。 (4) 月球上有冰。 (5) 2100年元旦是晴天。 (6) 大于 嗎？ (7) 請不要吸煙！ (8) 這朵花真美麗??！ (9) 我正在說假話。8 解: 本題的(9)個(gè)句子中，(6)是疑問句，(7)是祈使句，(8)是感嘆句，因而這3個(gè)句子都不是命題。剩下的6個(gè)句子都是陳述句，(3)無確定的真值：根據(jù)x,y的不同取值情況它可真可假，即無唯一的真值，因而不是命題。若(9)的真值為真，即“我正在說假話”為真，也就是“我正在說真話”，則又推出(9)的真值應(yīng)為假；反之，若(9)的真值為假，即“我正在說假話”為假，也就是“我正在說假話”，則又推出(9)的真值應(yīng)為真。于是(9)

4、既不為真又不為假，因此它不是命題。9像(9)這樣由真推出假，又由假推出真的陳述句稱為悖論。凡是悖論都不是命題。本例中，只有(1)，(2)，(4)，(5)是命題。(1)為假命題，(2)為真命題。雖然今天我們不知道(4)，(5)的真值，但它們的真值客觀存在，而且是唯一的，將來總會知道(4)的真值，到2100年元旦(5)的真值就真相大白了。 注：真值唯一與現(xiàn)在能否確定是不同的!102 命題和真值的符號化 （1）用真值來描述命題是“真” 還是“假”，分別用“1”和“0”表示（或用“F”和“T”表示） （2）命題用小寫的英文字母 、 、 、 或者帶下標(biāo) 的小寫的字母 、 、 、 來表示.11二、復(fù)合命題

5、與聯(lián)結(jié)詞各種論述和推理中，出現(xiàn)的命題多數(shù)比例1.1中的命題更加復(fù)雜。例1.2 下列句子全是命題 是有理數(shù)是不對的;2 是偶素?cái)?shù);2或4是素?cái)?shù); 如果2是素?cái)?shù)則3也是素?cái)?shù);2 是素?cái)?shù)當(dāng)且僅當(dāng)3是素?cái)?shù). 這些命題是通過諸如“或”“如果，則”等連詞聯(lián)結(jié)而成.121 命題分類 （1） 簡單（原子）命題 ：由簡單句（不含聯(lián)結(jié)詞的陳述句）形成的命題； （2） 復(fù)合（分子）命題 ：由一個(gè)或幾個(gè)簡單句通過聯(lián)結(jié)詞的聯(lián)接而構(gòu)成的命題.132 聯(lián)結(jié)詞（1） 否定聯(lián)結(jié)詞定義1.1 設(shè)為命題，復(fù)合命題“非（或“的否定”）稱為的否定式，記作，符號稱作否定聯(lián)結(jié)詞.（一元復(fù)合命題）規(guī)定： 為真當(dāng)且僅當(dāng)為假命題取值為真時(shí)，命題

6、取值為假；命題取值為假時(shí)，命題取值為真14（2） 合取聯(lián)結(jié)詞定義1.2 設(shè)、 為二命題，復(fù)合命題“并且 ”（或“與”）稱為與的合取式，記作符號稱作合取聯(lián)結(jié)詞.規(guī)定： 為真當(dāng)且僅當(dāng)與同時(shí)為真15使用合取聯(lián)結(jié)詞是要注意兩點(diǎn)： 自然語言的靈活性：自然語言中的“既又”、“不但而且”、“雖然但是”、“一面一面”等聯(lián)結(jié)詞基本含義是“和”、“并且” ，都可符號化； 多義性:不要見到“與”或“和”就使用聯(lián)結(jié)詞（有時(shí)“和”不能符號化為） pq 中p與q在自然語言上未必有某種被認(rèn)可的聯(lián)系（只是形式化處理的需要）16例1. 將下列命題符號化(1) 吳穎既用功又聰明.(2) 吳穎不僅用功而且聰明.(3) 吳穎雖然聰明

7、，但不用功.(4) 張輝和王麗都是三好學(xué)生.(5) 張輝與王麗是同學(xué).17解： 首先將原子命題符號化： p: 吳穎用功. q: 吳穎聰明. r: 張輝是三好學(xué)生. s: 王麗是三好學(xué)生. t: 張輝與王麗是同學(xué).（1）到(4)都是復(fù)合命題，它們使用的聯(lián)結(jié)詞表面看來各不相同，但都是合取聯(lián)結(jié)詞，都應(yīng)符號化為，(1)到(4)分別符號化為：pq，pq，qp，rs .（5）是原子命題，符號化為t .18（3） 析取聯(lián)結(jié)詞定義1.3 設(shè)、 為二命題，復(fù)合命題“或” 稱為與的析取式，記作，符號稱作析取聯(lián)結(jié)詞.規(guī)定： 為假當(dāng)且僅當(dāng)與同時(shí)為假；等價(jià)于當(dāng)且僅當(dāng)和至少一個(gè)取值為真時(shí)， 取值為真19注意： 自然語言中

8、的“或”有二義性：相容“或”（可兼）；排斥“或”(排異). pq 中p與q的關(guān)系可任意.例1.4 將下列命題符號化(1) 張曉靜愛唱歌或愛聽音樂.(2)張曉靜是江西人或安徽人.(3) 張曉靜只能挑選202或203房間.20 解： 在解題時(shí)，先將原子命題符號化。 (1) p：張曉靜愛唱歌. q：張曉靜愛聽音樂 (1)中“或”為相容或，符號化為pq. (2) r：張曉靜是江西人. s：張曉靜是安徽人. (2)中“或”應(yīng)為排斥或，但 r 與 s 不能同時(shí)為真，因而也可以符號化為 rs.21 (3) t：張曉靜挑選202房間. u：張曉靜挑選203房間. 由題意可知，(3)中“或”應(yīng)為排斥或. t，u

9、的聯(lián)合取值情況有四種：同真，同假，一真一假(兩種情況). 如果也符號化為tu，張曉靜就可能同時(shí)得到兩個(gè)房間，這違背題意. 因而不能符號化為 tu. 如何達(dá)到只能挑一個(gè)房間的要求呢？可以使用多個(gè)聯(lián)結(jié)詞，符號化為 (tu)(tu). 此復(fù)合命題為真當(dāng)且僅當(dāng)t，u中一個(gè)為真，一個(gè)為假，它準(zhǔn)確地表達(dá)了(3)的要求. 當(dāng)t為真u為假時(shí)，張曉靜得到202房間，t為假u為真時(shí)，張曉靜得到203房間，其它情況下，她得不到任何房間.22（4） 蘊(yùn)涵聯(lián)結(jié)詞定義1.4 設(shè)、 為二命題，復(fù)合命題“如果則” 稱為與的蘊(yùn)涵式，記作，符號稱作蘊(yùn)涵聯(lián)結(jié)詞.規(guī)定： 為假當(dāng)且僅當(dāng)為真為假；的邏輯關(guān)系為是的必要條件、是的充分條件2

10、3注意： 在自然語言里，特別是在數(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)符號化為 ，上述各種敘述方式都應(yīng)符號化為 . “只要p，就q”， 24注意： 在自然語言里，“如果p，則q”中的前件p與后件q往往具有某種內(nèi)在聯(lián)系. 而在數(shù)理邏輯中，前件和后件未必是因果關(guān)系，p與q可以無任何內(nèi)在聯(lián)系. 在數(shù)學(xué)或其它自然科學(xué)中，“如果p，則q”往往表達(dá)的是前件p為真，后件q也為真的推理關(guān)系. 但

11、在數(shù)理邏輯中，作為一種規(guī)定，當(dāng)p為假時(shí)，無論q是真是假， 均為真。也就是說，只有p為真q為假這一種情況使得復(fù)合命題 為假 . 25例1.5 將下列命題符號化，并指出各復(fù)合命題的真值：(1) 如果 336 ，則雪是白色的.(2) 如果 336 ，則雪是白色的.(3) 如果 336 ，則雪不是白色的.(4) 如果 336 ，則雪不是白色的.26以下命題中出現(xiàn)的 a 是給定的一個(gè)正整數(shù):(5)只要a 能被 4 整除，則 a 一定能被 2 整除.(6) a 能被4 整除，僅當(dāng) a 一定能被 2 整除.(7) 除非 a 能被 2 整除， a 才能被 4 整除.(8) 除非 a 能被 2 整除，否則 a

12、不能被 4 整除.(9) 只有a 能被 2 整除， a 才能被 4 整除.(10) 只有a能被 4 整除， a 才能被 2 整除.27（5）等價(jià)聯(lián)結(jié)詞定義1.5 設(shè)、 為二命題，復(fù)合命題“ 當(dāng)且僅當(dāng)” 稱為與的等價(jià)式，記作 ，符號稱作等價(jià)聯(lián)結(jié)詞.規(guī)定： 為真當(dāng)且僅當(dāng)與同時(shí)為真或同時(shí)為假；的邏輯關(guān)系為與互為充分必要條件注意：p、q的關(guān)系可任意。28例1.6 將下列命題符號化，將下列命題符號化，并討論它們的真值：(1) 是無理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲.(2) 235 的充要條件是 是無理數(shù).(3) 若兩圓的面積相等，則它們的半徑相等，反之亦然.(4) 當(dāng)王小紅心情愉快時(shí)，她就唱歌，反之當(dāng)她唱歌時(shí)，一定心情愉快.293 幾點(diǎn)說明 以上定義了五種最基本、最常用、也是最重要的聯(lián)結(jié)詞 將它們組成一個(gè)集合 , 稱為一個(gè)聯(lián)結(jié)詞集. 其中 為一元聯(lián)結(jié)詞，其余的都是二元聯(lián)結(jié)詞. （1）由聯(lián)結(jié)詞集 中的一個(gè)聯(lián)結(jié)詞聯(lián)結(jié)一個(gè)或兩個(gè)簡單命題組成的的復(fù)