命題邏輯基本概念

命題邏輯基本概念第1頁(yè)，共31頁(yè)，2023年，2月20日，星期一本課程是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支，是計(jì)算機(jī)科學(xué)基礎(chǔ)理論的核心課程。研究的對(duì)象是離散數(shù)據(jù)結(jié)構(gòu)及相互關(guān)系。主要內(nèi)容：數(shù)理邏輯、集合論及代數(shù)、圖論和組合數(shù)學(xué)等。第2頁(yè)，共31頁(yè)，2023年，2月20日，星期一離散數(shù)學(xué)與數(shù)學(xué)

連續(xù)型、離散型、隨機(jī)型離散數(shù)學(xué)與計(jì)算機(jī)科學(xué)

數(shù)據(jù)結(jié)構(gòu)、算法與軟件理論、人工智能、數(shù)據(jù)挖掘、信息安全、......離散數(shù)學(xué)與我第3頁(yè)，共31頁(yè)，2023年，2月20日，星期一數(shù)理邏輯關(guān)于邏輯的故事：上帝能否造出一塊自己搬不動(dòng)的石頭？理發(fā)師悖論集合論悖論…第4頁(yè)，共31頁(yè)，2023年，2月20日，星期一什么是邏輯？研究人的思維形式和規(guī)律的學(xué)科。由研究對(duì)象和方法的差異可分為：

1.形式邏輯

2.數(shù)理邏輯

3.思辨邏輯第5頁(yè)，共31頁(yè)，2023年，2月20日，星期一什么是數(shù)理邏輯？字面含義：數(shù)學(xué)理論的邏輯。邏輯是研究演繹（推理）規(guī)律的學(xué)科。廣義理解：用數(shù)學(xué)方法研究演繹規(guī)律的學(xué)科。狹義理解：用數(shù)學(xué)方法研究數(shù)學(xué)中演繹規(guī)律和數(shù)學(xué)基礎(chǔ)的學(xué)科。我們只介紹命題邏輯和一階邏輯第6頁(yè)，共31頁(yè)，2023年，2月20日，星期一第一章命題邏輯

§1.1命題與聯(lián)結(jié)詞第7頁(yè)，共31頁(yè)，2023年，2月20日，星期一稱能判斷真假而不是可真可假的陳述句為命題。作為命題的陳述句所表達(dá)得的判斷結(jié)果稱為命題的真值。真值只取兩個(gè)：真與假(T,F)。真值為真的命題稱為真命題。真值為假的命題稱為假命題。感嘆句、疑問(wèn)句、祈使句都不能稱為命題。判斷結(jié)果不唯一確定的陳述句不是命題。陳述句中的悖論不是命題。說(shuō)明第8頁(yè)，共31頁(yè)，2023年，2月20日，星期一4是素?cái)?shù)。

x大于y。充分大的偶數(shù)等于兩個(gè)素?cái)?shù)之和。今天是星期二。

請(qǐng)不要吸煙！這朵花真美麗??！我正在說(shuō)假話。例

判斷下列句子是否為命題。

是，假命題是，真命題不是，無(wú)確定的真值是，真值客觀存在是，真值根據(jù)具體情況而定。不是，疑問(wèn)句不是，祈使句不是，感嘆句不是，悖論第9頁(yè)，共31頁(yè)，2023年，2月20日，星期一r：充分大的偶數(shù)等于兩個(gè)素?cái)?shù)之和。s：今天是星期二。p：4是素?cái)?shù)。q：命題和真值的符號(hào)化用小寫英文字母p,q,r…,pi,qi

,ri

…表示命題用“1”表示真，用“0”表示假

不能被分解成更簡(jiǎn)單的陳述句，稱這樣的命題為簡(jiǎn)單命題或原子命題。由簡(jiǎn)單陳述句通過(guò)聯(lián)結(jié)詞而成的陳述句，稱這樣的命題為復(fù)合命題。

第10頁(yè)，共31頁(yè)，2023年，2月20日，星期一命題常元我們把表示具體命題及表示常命題的p，q，r，s等與1，0統(tǒng)稱為命題常元。命題變?cè)且浴罢妗⒓佟被颉?，0”為取值范圍的變?cè)?，它未指出符?hào)所表示的具體命題，可以代表任意命題。指派當(dāng)命題變?cè)靡粋€(gè)特定命題取代時(shí)，該命題變?cè)拍苡写_定的真值，從而成為一個(gè)命題。稱對(duì)命題變?cè)M(jìn)行指派。第11頁(yè)，共31頁(yè)，2023年，2月20日，星期一數(shù)理邏輯研究方法的主要特征是將論述或推理中的各種要素都符號(hào)化。即構(gòu)造各種符號(hào)語(yǔ)言來(lái)代替自然語(yǔ)言。將聯(lián)結(jié)詞（connective）符號(hào)化，消除其二義性，對(duì)其進(jìn)行嚴(yán)格定義。例如： 他學(xué)過(guò)英語(yǔ)或法語(yǔ)。

魚香肉絲或西紅柿炒雞蛋，加一碗湯。第12頁(yè)，共31頁(yè)，2023年，2月20日，星期一定義1.1否定(NOT)設(shè)p為命題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式,記作┐p，符號(hào)┐稱作否定聯(lián)結(jié)詞，并規(guī)定┐p為真當(dāng)且僅當(dāng)p為假。

例如：p： 哈爾濱是一個(gè)大城市。

┐p：哈爾濱是一個(gè)不大城市。

┐p：哈爾濱不是一個(gè)大城市。p┐p1001第13頁(yè)，共31頁(yè)，2023年，2月20日，星期一定義1.2合取(AND)設(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í)為真（遇假則假）。使用合取聯(lián)結(jié)詞時(shí)要注意的兩點(diǎn)：描述合取式的靈活性與多樣性。

自然語(yǔ)言中的“既……又……”、“不但……而且……”、“雖然……但是……”、“一面……一面……”等聯(lián)結(jié)詞都可以符號(hào)化為∧。分清簡(jiǎn)單命題與復(fù)合命題。

不要見(jiàn)到“與”或“和”就使用聯(lián)結(jié)詞∧。

pqp∧q1

11100010000第14頁(yè)，共31頁(yè)，2023年，2月20日，星期一例將下列命題符號(hào)化吳穎既用功又聰明。吳穎不僅用功而且聰明。吳穎雖然聰明，但不用功。張輝與王麗都是三好學(xué)生。張輝與王麗是同學(xué)。

p:吳穎用功。q:吳穎聰明。r:張輝是三好學(xué)生。s:王麗是三好學(xué)生。t:張輝與王麗是同學(xué)。

(1)p∧q(2)p∧q(3)q∧┐p(4)r∧s(5)t解題要點(diǎn)：正確理解命題含義。找出原子命題并符號(hào)化。選擇恰當(dāng)?shù)穆?lián)結(jié)詞。

第15頁(yè)，共31頁(yè)，2023年，2月20日，星期一合取舉例p：我們?nèi)タ措娪啊?/p>

q：房間里有十張桌子。

p∧q：我們?nèi)タ措娪安⑶曳块g里有十張桌子。

在數(shù)理邏輯中，關(guān)心的只是復(fù)合命題與構(gòu)成復(fù)合命題的各原子命題之間的真值關(guān)系，即抽象的邏輯關(guān)系，并不關(guān)心各語(yǔ)句的具體內(nèi)容(與語(yǔ)義無(wú)關(guān))。說(shuō)明第16頁(yè)，共31頁(yè)，2023年，2月20日，星期一定義1.3 析取(OR)設(shè)p，q為二命題，復(fù)合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結(jié)詞，并規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同時(shí)為假（遇真為真）。

自然語(yǔ)言中的“或”具有二義性，用它聯(lián)結(jié)的命題有時(shí)具有相容性，有時(shí)具有排斥性，對(duì)應(yīng)的聯(lián)結(jié)詞分別稱為相容或和排斥或(排異或)。說(shuō)明pqp∨q1

11101011000第17頁(yè)，共31頁(yè)，2023年，2月20日，星期一例將下列命題符號(hào)化

張曉靜愛(ài)唱歌或愛(ài)聽(tīng)音樂(lè)。張曉靜只能挑選202或203房間。張曉靜是江西人或安徽人。他昨天做了二十或三十道習(xí)題。設(shè)p：張曉靜愛(ài)唱歌，q：張曉靜愛(ài)聽(tīng)音樂(lè)。

相容或，符號(hào)化為

p∨q設(shè)t：張曉靜挑選202房間，

u：張曉靜挑選203房間。

排斥或，符號(hào)化為：(t∧┐u)∨(┐t∧u)設(shè)r：張曉靜是江西人，

s：張曉靜是安徽人。

排斥或，符號(hào)化為：r∨s。

(排斥或聯(lián)結(jié)的兩個(gè)命題事實(shí)上不可能同時(shí)為真)

或符號(hào)化為：(r∧┐s)∨(┐r∧s)原子命題，因?yàn)椤盎颉敝槐硎玖肆?xí)題的近似數(shù)目。第18頁(yè)，共31頁(yè)，2023年，2月20日，星期一定義1.4蘊(yùn)涵設(shè)p，q為二命題，復(fù)合命題“如果p，則q”稱作p與q的蘊(yùn)涵式，記作p→q，并稱p是蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件，→稱作蘊(yùn)涵聯(lián)結(jié)詞,并規(guī)定p→q為假當(dāng)且僅當(dāng)p為真q為假。

說(shuō)明p→q的邏輯關(guān)系表示q是p的必要條件。

q是p的必要條件有許多不同的敘述方式

只要p，就q

—

因?yàn)閜，所以q—

p僅當(dāng)q—

只有q才p—

除非q才p—

除非q，否則非p

pqp→q1

11100011001第19頁(yè)，共31頁(yè)，2023年，2月20日，星期一例將下列命題符號(hào)化，并指出其真值

如果3+3＝6，則雪是白的。如果3+3≠6，則雪是白的。如果3+3＝6，則雪不是白的。如果3+3≠6，則雪不是白的。解：令p：3+3＝6，p的真值為1。

q：雪是白色的，q的真值也為1。

（1）p→q1（2）┐p→q 1（3）p→┐q0（4）┐p→┐q

1第20頁(yè)，共31頁(yè)，2023年，2月20日，星期一以下命題中出現(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不能被4整除。(9)

只有a能被2整除，a才能被4整除。(10)只有a能被4整除，a才能被2整除。

解：令r：a能被4整除

s：a能被2整除(5)至(9)五個(gè)命題均敘述的是a能被2整除是a能被4整除的必要條件，因而都符號(hào)化為r→s。其真值為1。在(10)中，將a能被4整除看成了a能被2整除的必要條件，因而應(yīng)符號(hào)化為s→r。a值不定時(shí)，真值未知。第21頁(yè)，共31頁(yè)，2023年，2月20日，星期一關(guān)于蘊(yùn)含的進(jìn)一步說(shuō)明作為一種規(guī)定，當(dāng)p為假時(shí)，無(wú)論q是真是假，p→q均為真。也就是說(shuō)，只有p為真q為假這一種情況使得復(fù)合命題p→q為假。例：如果x>5，則x>2。

(1)x=6 如果6>5，則6>2。

(2)

x=3

如果3>5，則3>2。

(3)x=1 如果1>5，則1>2。

例：如果我有車，那么我去接你常出現(xiàn)的錯(cuò)誤，沒(méi)有分清充分條件與必要條件。第22頁(yè)，共31頁(yè)，2023年，2月20日，星期一定義1.5 等價(jià)設(shè)p，q為二命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價(jià)式，記作pq，稱作等價(jià)聯(lián)結(jié)詞，并規(guī)定pq為真當(dāng)且僅當(dāng)p與q同時(shí)為真或同時(shí)為假。說(shuō)明“當(dāng)且僅當(dāng)”（ifandonlyif）pq的邏輯關(guān)系為p與q互為充分必要條件。

(p→q)∧(q→p)與pq的邏輯關(guān)系完全一致。pqpq1

11100010001第23頁(yè)，共31頁(yè)，2023年，2月20日，星期一例將下列命題符號(hào)化，并討論它們的真值

π是無(wú)理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲。2+3＝5的充要條件是π是無(wú)理數(shù)。若兩圓A，B的面積相等，則它們的半徑相等；反之亦然。當(dāng)王小紅心情愉快時(shí)，她就唱歌；反之，當(dāng)她唱歌時(shí)，一定心情愉快。設(shè)p：π是無(wú)理數(shù)，q：加拿大位于亞洲。

符號(hào)化為pq，真值為0。設(shè)p：2+3＝5，q：π是無(wú)理數(shù)。

符號(hào)化為pq，真值為1。設(shè)p：兩圓A，B的面積相等，q：兩圓A，B的半徑相等。

符號(hào)化為pq，真值為1。設(shè)p：王小紅心情愉快，q：王小紅唱歌。

符號(hào)化為pq，真值由具體情況而定。第24頁(yè)，共31頁(yè)，2023年，2月20日，星期一關(guān)于基本聯(lián)結(jié)詞的說(shuō)明{┐,∧,∨,→,}，稱為一個(gè)聯(lián)結(jié)詞集。由聯(lián)結(jié)詞集{┐,∧,∨,→,}中的一個(gè)聯(lián)結(jié)詞聯(lián)結(jié)一個(gè)或兩個(gè)原子命題組成的復(fù)合命題是最簡(jiǎn)單的復(fù)合命題，可以稱它們?yōu)榛镜膹?fù)合命題?；緩?fù)合命題的真值見(jiàn)下表：

第25頁(yè)，共31頁(yè)，2023年，2月20日，星期一多次使用聯(lián)結(jié)詞集中的聯(lián)結(jié)詞，可以組成更為復(fù)雜的復(fù)合命題。求復(fù)雜復(fù)合命題的真值時(shí)，除依據(jù)上表外，還要規(guī)定聯(lián)結(jié)詞的優(yōu)先順序，將括號(hào)也算在內(nèi)。本書規(guī)定的聯(lián)結(jié)詞優(yōu)先順序?yàn)椋?)，┐，∧，∨，→，，對(duì)于同一優(yōu)先級(jí)的聯(lián)結(jié)詞，先出現(xiàn)者先運(yùn)算。

第26頁(yè)，共31頁(yè)，2023年，2月20日，星期一例:令 p：北京比天津人口多。

q：2+2＝4.

r：烏鴉是白色的。

求下列復(fù)合命題的真值：

(1)((┐p∧q)∨(p∧┐q))→r

(2)(q∨r)→(p→┐r)

(3)(┐p∨r)(p∧┐r)

解：p、q、r的真值分別為

1、1、0

(1)1

(2)1

(3)0我們關(guān)心的是復(fù)合命題中命題之間的真值關(guān)系，而不關(guān)心命題的內(nèi)容。說(shuō)明第27頁(yè)，共31頁(yè)，2023年，2月20日，星期一例題：命題符號(hào)化(1)我和他既是兄弟又是同學(xué)

p：我和他是兄弟，q：我和他是同學(xué)。 故命題可符號(hào)化為：p∧q。(2)張三或李四都可以做這件事。

p：張三可以做這件事。q：李四可以做這件事。 故命題可符號(hào)化為：p∨q。(3)僅當(dāng)我有時(shí)間且天不下雨，我將去鎮(zhèn)上。

對(duì)于“僅當(dāng)”，實(shí)質(zhì)上是“當(dāng)”的逆命題?！爱?dāng)A則B”是A→B，而“僅當(dāng)A則B”是B→