離散數(shù)學課件第一章(第1講)

1、第一篇 數(shù)理邏輯邏輯：通常指人們思考問題，從某些已知條件出發(fā)推出合理的結(jié)論的規(guī)律。數(shù)理邏輯：用數(shù)學方法來研究推理的規(guī)律。包括命題邏輯和謂詞邏輯。數(shù)理邏輯研究方法：采用一套數(shù)學的符號系統(tǒng)來描述和處理思維的形式和規(guī)律。第一章 命題邏輯1.命題與命題聯(lián)結(jié)詞2.命題公式與真值表3.命題公式的翻譯4. 等價式與蘊含式5.對偶與范 式6.命題邏輯的推理理論7.其他聯(lián)結(jié)詞1 命題與命題聯(lián)結(jié)詞定義： 具有唯一值的陳述句叫命題。討論定義：(1)命題的值：命題值可以是真的，也可以是假的，但不能同時既為真又為假。(2)命題的真假值表示： 命題中所有的“真”用“ ” 或“ 1”表示 命題中所有的“假”用“ ”或 “0

2、 ”表示。1 命題(3)命題分類：)原子命題：一個命題，不能分解成為更簡單的命題。 例：我是一位學生。) 復合命題：若干個原子命題使用適當?shù)穆?lián)結(jié)詞所組成的新命題。 例：我是一位老師和他是一位學生(4)命題的表示：常用26個大寫的英文字母表示命題。注意：(1) 命令句，感嘆句，疑問句都不是命題。如： 1）把門關(guān)上！ 2）你到哪里去？(2) 語句既為真，同時又包含假的不是命題，這樣的句子稱為“悖論”。 如：我正在說謊。 在命題邏輯中不討論悖論問題。例：判斷下列語句是否為命題，若是，請給出其真值。（1）十是整數(shù)。 （2）上海是一個城市。 （3）加拿大是一個國家。 （4）是偶數(shù)而不是奇數(shù)。 （5）請勿

3、闖紅燈?。?）你今天出差嗎？（7）x-y=6( T )( T )( T )( F )下面先介紹五個常用的命題聯(lián)結(jié)詞。()否定詞：（否定運算、非運算） ）符號 ,讀作“非”，“否定” 設命題為，則讀做“的否定”或“非” ）否定運算真值表PPTFFT2 命題聯(lián)結(jié)詞 ）舉例： 北京是一座城市。：北京不是一座城市。： 每一種生物是動物。 ：有一些生物不是動物。 這里不能講成“每一種生物都不是動物” 。 對量化命題的否定，除對動詞進行否定外，同時對量詞也要加以否定。(2) 合取詞（“合取”、 “與”運算） 1) 符號“”設，為兩個命題，則稱與的合取，讀作：“與”“與的合取” “并且” PQP QQPFF

4、FFFTFFTFFFTTTT2) 合取運算真值表 注： 當且僅當和的真值均為 ，則 的真值為 。否則，其真值為 。 和地位是平等的，和的位置可以交換而不會影響的結(jié)果。3)舉例： P：王華的成績很好 Q：王華的品德很好。 則：王華的成績很好并且品德很好。 P：我們?nèi)シN樹 Q：房間里有一臺電視機 則：我們?nèi)シN樹與房間里有一臺電視機。 P：今天下大雨 Q：3+3=6 則：今天下大雨和3+3=6注：在日常生活中，合取詞應用在二個有關(guān)系的命題之間。由例 ， 可知，在邏輯學中，合取詞可以用在二個毫不相干的命題之間。 P: 王大和王二是親兄弟。 注：這是原子命題。 ()析取詞（或運算） )符號“” 設、為二

5、個命題，則（）稱作與的“析取”，讀作：“或”。)析取運算真值表：注： 當且僅當、均為 時， 為 。否則，其真值為 。 和地位是平等的，和的位置可以交換,不會影響的結(jié)果。PQP QQPFFFFFTTTTFTTTTTT3)區(qū)分“可兼或”與“不可兼或（異或，排斥或）”析取聯(lián)結(jié)詞為可兼或例如：燈泡有故障或開關(guān)有故障。今天下雨或打雷。以上例句均為可兼或?！安豢杉婊颉北硎緸椋?(異或),當P和Q均為“T”時，則P異或Q為“F”。PQPQFFFFTTTFTTTF例： 他通過電視看雜技或到劇場看雜技。 他乘火車去北京或乘飛機去北京。以上兩句均為不“可兼或”。() 單條件聯(lián)結(jié)詞：（“蘊含”聯(lián)結(jié)詞、蘊含詞）) 符

6、號“”設、為二個命題，則 讀作：“如果則”，“蘊含”，“僅當”，“當且”，“是的充分條件” ：稱為前件、條件、前提、假設 ：稱為后件、結(jié)論 ) 蘊含運算真值表 PQPQFFTFTTTFFTTT注:當為“”，為“”時，則（）為“”，否則（）都為“”。) 舉例： P：我拿起一本書 Q：我一口氣讀完了這本書PQ：如果我拿起一本書，則我一口氣讀完了這本書。 P：月亮出來了 Q：33=9 PQ：如果月亮出來了，則33=9。(5) 雙條件聯(lián)結(jié)詞（“等價”詞） )符號“”設、為二個命題，則讀作： 當且僅當 等價 是的充分必要條件 注： 每當和的真值相同時，（）的真值為“”，否則（）的真值為“”。、的地位是平

7、等的，、交 換位置不會改變的值。 PQPQQPFFTTFTFFTFFFTTTT ) 等價運算真值表 )舉例： ：ABC是等腰三角形 ：ABC有兩只角相等：ABC是等腰三角形當且僅當ABC中有兩只角相等。 ：春天來了 ：燕子飛回來了：春天來了當且僅當燕子飛回來了。 ：平面上兩直線平行 ： 二直線不相交：平面上二直線平行，當且僅當這二直線不相交。 ：2+2=4 ：雪是白色的 ： 當且僅當雪是白色的。 4) 單條件聯(lián)結(jié)詞與雙條件聯(lián)結(jié)詞的表達 當且僅當 僅當 當且 3命題聯(lián)結(jié)詞的運算要求(1)先括號內(nèi)，后括號外(2)運算時聯(lián)結(jié)詞的優(yōu)先次序由高到低排序為： (3)含有相同 聯(lián)結(jié)詞的命題公式，如果聯(lián)結(jié)詞滿足結(jié)合律，則可省去括號，否則不可省去括號。 例：（）可省去括號而（）中的括號不能省去，因為“”不滿足結(jié)合律。(4)命題公式最