第1章命題邏輯離散數(shù)學第1章命題邏輯離散數(shù)學本章說明本章的主要內(nèi)容命題、聯(lián)結詞命題公式、命題公式的分類等值演算連接詞全功能集對偶與范式推理理論題例分析本章說明本章的主要內(nèi)容1.1命題符號化與聯(lián)結詞數(shù)理邏輯研究的中心問題是推理。推理的前提和結論都是表達判斷的陳述句。表達判斷的陳述句構成了推理的基本單位。1.1命題符號化與聯(lián)結詞數(shù)理邏輯研究的中心問題是推理。1.1命題符號化與聯(lián)結詞稱能判斷真假的陳述句為命題

（proposition）。作為命題的陳述句所表達得的判斷結果稱為命題的真值。真值只取兩個：真與假。真值為真的命題稱為真命題。真值為假的命題稱為假命題。感嘆句、疑問句、祈使句都不能稱為命題。判斷結果不唯一確定的陳述句不是命題。陳述句中的悖論不是命題。說明1.1命題符號化與聯(lián)結詞稱能判斷真假的陳述句為命題

（pr2是素數(shù)。

x大于y。充分大的偶數(shù)等于兩個素數(shù)之和。明年10月1日是晴天。π請不要吸煙！這朵花真美麗啊！我正在說假話。例1.1

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

是，真命題是，真命題不是，無確定的真值是，真值客觀存在是，真值根據(jù)具體情況而定。不是，疑問句不是，祈使句不是，感嘆句不是，悖論2是素數(shù)。例1.1判斷下列句子是否為命題。是，真命題命題可分為:原子命題和復合命題不能被分解成更簡單的陳述句，稱這樣的命題為簡單命題或原子命題。由簡單陳述句通過聯(lián)結詞而成的陳述句，稱這樣的命題為復合命題。

命題可分為:

簡單命題和真值的符號化簡單命題用小寫英文字母p,q,r…,pi,qi

,ri

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

簡單命題是真值唯一確定的命題邏輯中最基本的研究單位，所以也稱簡單命題為命題常項或命題常元。稱真值可以變化的陳述句為命題變項或命題變元。也用p,q,r,…表示命題變項。當p,q,r,…表示命題變項時，它們就成了取值0或1的變項，因而命題變項已不是命題。這樣一來，p,q,r,…既可以表示命題常項，也可以表示命題變項。在使用中，需要由上下文確定它們表示的是常項還是變項。q：

x大于y。p：4是素數(shù)。P,q成了所表示命題的代表，其中p的值是0，q為命題變項。簡單命題和真值的符號化簡單命題用小寫英文字母p,q,r…,p例1.2將下面這段陳述中所出現(xiàn)的原子命題符號化，并指出它們的真值，然后再寫出這段陳述。

是有理數(shù)是不對的；2是偶素數(shù)；2或4是素數(shù)；如果2是素數(shù)，則3也是素數(shù)；2是素數(shù)當且僅當3也是素數(shù)。

p：是有理數(shù)q：2是素數(shù)；r：2是偶數(shù)s：3是素數(shù)；t：4是素數(shù)01110非p；q并且(與)r；q或t；如果q，則s；q當且僅當s。例1.2將下面這段陳述中所出現(xiàn)的原子命題符號化，并指出它們的例1.2的討論半形式化形式數(shù)理邏輯研究方法的主要特征是將論述或推理中的各種要素都符號化。即構造各種符號語言來代替自然語言。形式化語言：完全由符號所構成的語言。將聯(lián)結詞（connective）符號化，消除其二義性，對其進行嚴格定義。例1.2的討論半形式化形式主要的五個聯(lián)結詞：否定聯(lián)結詞合取聯(lián)結詞析取聯(lián)結詞蘊涵聯(lián)結詞等價聯(lián)結詞聯(lián)結詞主要的五個聯(lián)結詞：聯(lián)結詞定義1.1 否定(negation)設p為命題，復合命題“非p”(或“p的否定”)稱為p的否定式,記作┐p，符號┐稱作否定聯(lián)結詞，并規(guī)定┐p為真當且僅當p為假。

例如：p： 哈爾濱是一個大城市。

┐p：哈爾濱是一個不大城市。

┐p：哈爾濱不是一個大城市。p┐p1001定義1.1 否定(negation)設p為命題，復合命題“非定義1.2 合取(conjunction)設p,q為二命題，復合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結詞，并規(guī)定p∧q為真當且僅當p與q同時為真。使用合取聯(lián)結詞時要注意的兩點：描述合取式的靈活性與多樣性。

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

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

pqp∧q1

11100010000定義1.2 合取(conjunction)設p,q為二命題，例1.3將下列命題符號化吳穎既用功又聰明。吳穎不僅用功而且聰明。吳穎雖然聰明，但不用功。張輝與王麗都是三好學生。張輝與王麗是同學。

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

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

例1.3將下列命題符號化吳穎既用功又聰明。p:吳穎用功。合取舉例p：我們?nèi)タ措娪啊?/p>

q：房間里有十張桌子。

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

在數(shù)理邏輯中，關心的只是復合命題與構成復合命題的各原子命題之間的真值關系，即抽象的邏輯關系，并不關心各語句的具體內(nèi)容。說明合取舉例p：我們?nèi)タ措娪啊?/p>

q：房間里有十張桌子。

p∧q定義1.3 析取(disjunction)設p，q為二命題，復合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結詞，并規(guī)定p∨q為假當且僅當p與q同時為假。

自然語言中的“或”具有二義性，用它聯(lián)結的命題有時具有相容性，有時具有排斥性，對應的聯(lián)結詞分別稱為相容或和排斥或(排異或)。析取式p∨q

表示的是一種相容或說明pqp∨q1

11101011000定義1.3 析取(disjunction)設p，q為二命題，例1.4將下列命題符號化

張曉靜愛唱歌或愛聽音樂。張曉靜只能挑選202或203房間。張曉靜是江西人或安徽人。設p：張曉靜愛唱歌，q：張曉靜愛聽音樂。

相容或，符號化為

p∨q設t：張曉靜挑選202房間，

u：張曉靜挑選203房間。

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

s：張曉靜是安徽人。

排斥或，符號化為：r∨s。

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

或符號化為：(r∧┐s)∨(┐r∧s)例1.4將下列命題符號化張曉靜愛唱歌或愛聽音樂。設p：定義1.4 蘊涵(implication)設p，q為二命題，復合命題“如果p，則q”稱作p與q的蘊涵式，記作p→q，并稱p是蘊涵式的前件，q為蘊涵式的后件，→稱作蘊涵聯(lián)結詞,并規(guī)定p→q為假當且僅當p為真q為假。

說明p→q的邏輯關系表示q是p的必要條件。q是p的必要條件有許多不同的敘述方式。只要p，就q

因為p，所以qp僅當q只有q才p除非q才p除非q，否則非p

前件p和后件q可以沒有任何內(nèi)在聯(lián)系。pqp→q1

11100011001定義1.4 蘊涵(implication)設p，q為二命題，例1.5將下列命題符號化，并指出其真值

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

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

p→q┐p→q p→┐q ┐p→┐q 1101例1.5將下列命題符號化，并指出其真值如果3+3＝6，則例1.5將下列命題符號化，并指出其真值

以下命題中出現(xiàn)的a是一個給定的正整數(shù)：(5)只要a能被4整除，則a一定能被2整除。(6)a能被4整除，僅當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)五個命題均敘述的是a能被2整除是a能被4整除的必要條件，因而都符號化為r→s。其真值為1在(10)中，將a能被4整除看成了a能被2整除的必要條件，因而應符號化為s→r。a值不定時，真值未知。例1.5將下列命題符號化，并指出其真值以下命題中出現(xiàn)的a關于蘊含的進一步說明作為一種規(guī)定，當p為假時，無論q是真是假，p→q均為真。也就是說，只有p為真q為假這一種情況使得復合命題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)的錯誤，沒有分清充分條件與必要條件。關于蘊含的進一步說明作為一種規(guī)定，當p為假時，無論q是真是假定義1.5 等價(two-way-implication)設p，q為二命題，復合命題“p當且僅當q”稱作p與q的等價式，記作p?q，稱作等價聯(lián)結詞，并規(guī)定p?q為真當且僅當p與q同時為真或同時為假。說明“當且僅當”（ifandonlyif）p?q的邏輯關系為p與q互為充分必要條件。

(p→q)∧(q→p)與p?q的邏輯關系完全一致。pqpq1

11100010001定義1.5 等價(two-way-implication)設例1.6將下列命題符號化，并討論它們的真值

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

符號化為p?q，真值為0。設p：2+3＝5，q：π是無理數(shù)。

符號化為p?q，真值為1。設p：兩圓A，B的面積相為p?q，真值為1。設p：王小紅心情愉快，q：王小紅唱歌。

符號化為p?q，真值由具體情況而定。例1.6將下列命題符號化，并討論它們的真值是無理數(shù)當關于真值（邏輯）聯(lián)結詞的說明基本聯(lián)結詞的真值見下表：關于真值（邏輯）聯(lián)結詞的說明關于真值聯(lián)結詞的說明在命題邏輯中，可用這些聯(lián)結詞將各種各樣的復合命題符號化?；静襟E如下：

（1）分析出各簡單命題，將它們符號化

（2）使用合適的聯(lián)結詞，將簡單命題逐個聯(lián)結起來，組成復合命題的符號化表示。關于真值聯(lián)結詞的說明在命題邏輯中，可用這些聯(lián)結詞將各種各樣的關于聯(lián)結詞的說明多次使用聯(lián)結詞集中的聯(lián)結詞，可以組成更為復雜的復合命題。求復雜復合命題的真值時，除依據(jù)上表外，還要規(guī)定聯(lián)結詞的優(yōu)先順序，將括號也算在內(nèi)。本書規(guī)定的聯(lián)結詞優(yōu)先順序為：()，┐，∧，∨，→，?，對于同一優(yōu)先級的聯(lián)結詞，先出現(xiàn)者先運算。關于聯(lián)結詞的說明多次使用聯(lián)結詞集中的聯(lián)結詞，可以組成更為復雜例1.7令

p：北京比天津人口多。 q：2+2＝4.

r：烏鴉是白色的。

求下列復合命題的真值：

(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我們關心的是復合命題中命題之間的真值關系，而不關心命題的內(nèi)容。說明例1.7令 p：北京比天津人口多。解：p、q、r的真值分別1.2命題公式及分類1.2命題公式及分類定義1.6合式公式(wff)命題公式的嚴格定義：(1)單個命題或命題變項p,q,r…,pi,qi

,ri

…，0，1是合式公式。(2)若A是合式公式，則(┐A)也是合式公式。(3)若A，B是合式公式，則(A∧B)，(A∨B)，(A→B)，(AB)也是合式公式。(4)只有有限次地應用(1)～(3)組成的符號串才是合式公式。合式公式也稱為命題公式，簡稱為公式。將命題變項用聯(lián)結詞和圓括號按一定的邏輯關系聯(lián)結起來的符號串稱為合式公式或命題公式。定義1.6合式公式(wff)命題公式的嚴格定義：將命題關于合式公式的說明定義1.6給出的合式公式的定義方式稱為歸納定義或遞歸定義方式。定義中引進了A,B等符號，用它們表示任意的合式公式，而不是某個具體的公式，這與p,p∧q,(p∧q)→r等具體的公式是有所不同的。(┐A)、(A∧B)等公式單獨出現(xiàn)時，外層括號可以省去，寫成┐A、A∧B等。公式中不影響運算次序的括號可以省去，

如公式(p∨q)∨(┐r)可以寫成p∨q∨┐r。合式公式的例子：

(p→q)∧(q?r)

(p∧q)∧┐r

p∧(q∧┐r)不是合式公式的例子

pq→r

(p→(r→q)關于合式公式的說明定義1.6給出的合式公式的定義方式稱為歸納定義1.7公式層次(1)若公式A是單個的命題（常項或變項），則稱A為0層合式。(2)稱A是n+1(n≥0)層公式是指下面情況之一： (a)A＝┐B，B是n層公式； (b)A＝B∧C，其中B,C分別為i層和j層公式，且n=max(i,j)； (c)A＝B∨C，其中B,C的層次及n同(b)； (d)A＝B→C，其中B,C的層次及n同(b)； (e)A＝B?C，其中B,C的層次及n同(b)。(3)若公式A的層次為k，則稱A是k層公式。例如：(┐p∧q)→r，(┐(p→┐q))∧((r∨s)?┐p) 分別為3層和4層公式定義1.7公式層次(1)若公式A是單個的命題（常項或變項）公式的解釋在命題公式中，由于有命題符號的出現(xiàn)，因而真值是不確定的。當將公式中出現(xiàn)的全部命題符號都解釋成具體的命題之后，公式就成了真值確定的命題了。(p∨q)→r若p：2是素數(shù)，q：3是偶數(shù)，r：是無理數(shù)，則p與r被解釋成真命題，q被解釋成假命題，此時公式(p∨q)→r被解釋成：若2是素數(shù)或3是偶數(shù)，則是無理數(shù)。（真命題）若p,q的解釋不變，r被解釋為：是有理數(shù)，則(p∨q)→r被解釋成：若2是素數(shù)或3是偶數(shù)，則π是有理數(shù)。（假命題）將命題變項p解釋成真命題，相當于指定p的真值為1，解釋成假命題，相當于指定p的真值為0。

公式的解釋在命題公式中，由于有命題符號的出現(xiàn)，因而真值是不確定義1.8賦值或解釋設A為一命題公式，p1,p2,…,pn是出現(xiàn)在公式A中的全部命題變項，給p1,p2,…,pn各指定一個真值，稱為對A的一個賦值或解釋。若指定的一組值使A的真值為1，則稱這組值為A的成真賦值；若使A的真值為0，則稱這組值為A的成假賦值。對含n個命題變項的公式A的賦值情況做如下規(guī)定：

(1)若A中出現(xiàn)的命題符號為p1,p2,…,pn，給定A的賦值α1,α2,…,αn

是指p1＝α1，p2＝α2,…，pn＝αn。

(2)若A中出現(xiàn)的命題符號為p，q，r...,給定A的賦值α1,α2,…,αn是指p＝α1，q＝α2,…，最后一個字母賦值αn。上述αi取值為0或1，i＝1,2,…,n。

定義1.8賦值或解釋設A為一命題公式，p1,p2,…,pn賦值舉例在公式(┐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)→r中，

011(p1＝0，p2＝1，p3＝1)為成真賦值，

100(p1＝1，p2＝0，p3＝0)為成假賦值。重要結論：

含n(n≥1)個命題變項的公式共有2n個不同的賦值。

賦值舉例在公式(┐p1∧┐p2∧┐p3)∨(p1∧p2)中，定義1.9真值表將命題公式A在所有賦值下取值情況列成表，稱作A的真值表。構造真值表的具體步驟如下：(1)找出公式中所含的全體命題變項p1,p2,…,pn(若無下角標就按字典順序排列)，列出2n個賦值。本書規(guī)定，賦值從00…0開始，然后按二進制加法依次寫出各賦值，直到11…1為止。(2)按從低到高的順序?qū)懗龉降母鱾€層次。(3)對應各個賦值計算出各層次的真值，直到最后計算出公式的真值。

公式A與B具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考慮構造真值表的中間過程。

說明定義1.9真值表將命題公式A在所有賦值下取值情況列成表，稱例1.7求下列公式的真值表，并求成真賦值和成假賦值。(1)(┐p∧q)→┐r(2)(p∧┐p)?(q∧┐q)(3)┐(p→q)∧q∧r

（1）例1.7求下列公式的真值表，并求成真賦值和成假賦值。（1）（2）（2）（3）（3）定義1.10重言式、永真式、可滿足式設A為任一命題公式(1)若A在它的各種賦值下取值均為真,則稱A是重言式或永真式。(2)若A在它的各種賦值下取值均為假,則稱A是矛盾式或永假式。(3)若A不是矛盾式,則稱A是可滿足式（satisfactable。定義1.10重言式、永真式、可滿足式設A為任一命題公式定義1.10的進一步說明A是可滿足式的等價定義是：A至少存在一個成真賦值。重言式一定是可滿足式，但反之不真。因而，若公式A是可滿足式，且它至少存在一個成假賦值，則稱A為非重言式的可滿足式。真值表可用來判斷公式的類型:若真值表最后一列全為1，則公式為重言式。若真值表最后一列全為0，則公式為矛盾式。若真值表最后一列中至少有一個1，則公式為可滿足式。說明n個命題變項共產(chǎn)生2n個不同賦值含n個命題變項的公式的真值表只有種不同情況

定義1.10的進一步說明A是可滿足式的等價定義是：A至少存在例題例題1.9下列各公式均含兩個命題變項p與q，它們中哪些具有相同的真值表?

(1)p→q (4)(p→q)∧(q→p)

(2)p?q (5)┐q∨p

(3)┐(p∧┐q)例題例題1.9下列各公式均含兩個命題變項p與q，它們中哪些例題

例1.10下列公式中,哪些具有相同的真值表?

(1)p→q

(2)┐q∨r

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

(4)(q→r)∧(p→p)例題例1.10下列公式中,哪些具有相同的真值表?

(1)本章主要內(nèi)容命題與真值（或真假值）。簡單命題與復合命題。聯(lián)結詞：┐，∧，∨，→，?。命題公式（簡稱公式）。命題公式的層次和公式的賦值。真值表。公式的類型：重言式（永真式），矛盾式（永假式），可滿足式。

本章主要內(nèi)容命題與真值（或真假值）。本章學習要求在5種聯(lián)結詞中，要特別注意蘊涵聯(lián)結的應用，要弄清三個問題：p→q的邏輯關系p→q的真值p→q的靈活的敘述方法寫真值表要特別仔細認真，否則會出錯誤。深刻理解各聯(lián)結詞的邏輯含義。熟練地將復合命題符號化。會用真值表求公式的成真賦值和成假賦值。本章學習要求在5種聯(lián)結詞中，要特別注意蘊涵聯(lián)結的應用，要弄清本章典型習題命題符號化求復合命題的真值與命題公式的賦值判斷公式的類型本章典型習題命題符號化例題：命題符號化(1)我和他既是兄弟又是同學 p：我和他是兄弟，q：我和他是同學。 故命題可符號化為：p∧q。(2)張三或李四都可以做這件事。 p：張三可以做這件事。q：李四可以做這件事。 故命題可符號化為：p∧q。(3)僅當我有時間且天不下雨，我將去鎮(zhèn)上。

對于“僅當”，實質(zhì)上是“當”的逆命題?！爱擜則B”是A→B，而“僅當A則B”是B→A。

p：我有時間。q：天不下雨。r：我將去鎮(zhèn)上。 故命題可符號化為：r→(p∧q)。

例題：命題符號化(1)我和他既是兄弟又是同學例題：命題符號化(4)張剛總是在圖書館看書，除非圖書館不開門或張剛生病。

對于“除非”，只要記住，“除非”是條件。

p：張剛在圖書館看書，q：圖書館不開門，r：張剛生病。

故命題可符號化為：﹁(q∨r)→p。(5)風雨無阻，我去上學。

可理解為“不管是否刮風、是否下雨，我都去上學”。

p：天刮風，q：天下雨，r：我去上學。 故命題可符號化為：

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

或(p∧q∧r)∨(p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧┐q∧r)理解為“四種情況必居其一,而每種情況下我都去上學”

例題：命題符號化(4)張剛總是在圖書館看書，除非圖書館不開門命題符號化的要點要準確確定原子命題，并將其形式化。要選用恰當?shù)穆?lián)結詞，尤其要善于識別自然語言中的聯(lián)結詞（有時它們被省略）。否定詞的位置要放準確。需要的括號不能省略，而可以省略的括號，在需要提高公式可讀性時亦可不省略。要注意的是,語句的形式化未必是唯一的。命題符號化的要點要準確確定原子命題，并將其形式化。例題：求公式┐(p→(q∧r))的真值表。pqr000001010011100101110111q∧r00010001p→(q∧r)11110001┐(p→(q∧r))00001110例題：求公式┐(p→(q∧r))的真值表。pqr000001第1章命題邏輯離散數(shù)學第1章命題邏輯離散數(shù)學本章說明本章的主要內(nèi)容命題、聯(lián)結詞命題公式、命題公式的分類等值演算連接詞全功能集對偶與范式推理理論題例分析本章說明本章的主要內(nèi)容1.1命題符號化與聯(lián)結詞數(shù)理邏輯研究的中心問題是推理。推理的前提和結論都是表達判斷的陳述句。表達判斷的陳述句構成了推理的基本單位。1.1命題符號化與聯(lián)結詞數(shù)理邏輯研究的中心問題是推理。1.1命題符號化與聯(lián)結詞稱能判斷真假的陳述句為命題

（proposition）。作為命題的陳述句所表達得的判斷結果稱為命題的真值。真值只取兩個：真與假。真值為真的命題稱為真命題。真值為假的命題稱為假命題。感嘆句、疑問句、祈使句都不能稱為命題。判斷結果不唯一確定的陳述句不是命題。陳述句中的悖論不是命題。說明1.1命題符號化與聯(lián)結詞稱能判斷真假的陳述句為命題

（pr2是素數(shù)。

x大于y。充分大的偶數(shù)等于兩個素數(shù)之和。明年10月1日是晴天。π請不要吸煙！這朵花真美麗啊！我正在說假話。例1.1

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

是，真命題是，真命題不是，無確定的真值是，真值客觀存在是，真值根據(jù)具體情況而定。不是，疑問句不是，祈使句不是，感嘆句不是，悖論2是素數(shù)。例1.1判斷下列句子是否為命題。是，真命題命題可分為:原子命題和復合命題不能被分解成更簡單的陳述句，稱這樣的命題為簡單命題或原子命題。由簡單陳述句通過聯(lián)結詞而成的陳述句，稱這樣的命題為復合命題。

命題可分為:

簡單命題和真值的符號化簡單命題用小寫英文字母p,q,r…,pi,qi

,ri

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

簡單命題是真值唯一確定的命題邏輯中最基本的研究單位，所以也稱簡單命題為命題常項或命題常元。稱真值可以變化的陳述句為命題變項或命題變元。也用p,q,r,…表示命題變項。當p,q,r,…表示命題變項時，它們就成了取值0或1的變項，因而命題變項已不是命題。這樣一來，p,q,r,…既可以表示命題常項，也可以表示命題變項。在使用中，需要由上下文確定它們表示的是常項還是變項。q：

x大于y。p：4是素數(shù)。P,q成了所表示命題的代表，其中p的值是0，q為命題變項。簡單命題和真值的符號化簡單命題用小寫英文字母p,q,r…,p例1.2將下面這段陳述中所出現(xiàn)的原子命題符號化，并指出它們的真值，然后再寫出這段陳述。

是有理數(shù)是不對的；2是偶素數(shù)；2或4是素數(shù)；如果2是素數(shù)，則3也是素數(shù)；2是素數(shù)當且僅當3也是素數(shù)。

p：是有理數(shù)q：2是素數(shù)；r：2是偶數(shù)s：3是素數(shù)；t：4是素數(shù)01110非p；q并且(與)r；q或t；如果q，則s；q當且僅當s。例1.2將下面這段陳述中所出現(xiàn)的原子命題符號化，并指出它們的例1.2的討論半形式化形式數(shù)理邏輯研究方法的主要特征是將論述或推理中的各種要素都符號化。即構造各種符號語言來代替自然語言。形式化語言：完全由符號所構成的語言。將聯(lián)結詞（connective）符號化，消除其二義性，對其進行嚴格定義。例1.2的討論半形式化形式主要的五個聯(lián)結詞：否定聯(lián)結詞合取聯(lián)結詞析取聯(lián)結詞蘊涵聯(lián)結詞等價聯(lián)結詞聯(lián)結詞主要的五個聯(lián)結詞：聯(lián)結詞定義1.1 否定(negation)設p為命題，復合命題“非p”(或“p的否定”)稱為p的否定式,記作┐p，符號┐稱作否定聯(lián)結詞，并規(guī)定┐p為真當且僅當p為假。

例如：p： 哈爾濱是一個大城市。

┐p：哈爾濱是一個不大城市。

┐p：哈爾濱不是一個大城市。p┐p1001定義1.1 否定(negation)設p為命題，復合命題“非定義1.2 合取(conjunction)設p,q為二命題，復合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯(lián)結詞，并規(guī)定p∧q為真當且僅當p與q同時為真。使用合取聯(lián)結詞時要注意的兩點：描述合取式的靈活性與多樣性。

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

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

pqp∧q1

11100010000定義1.2 合取(conjunction)設p,q為二命題，例1.3將下列命題符號化吳穎既用功又聰明。吳穎不僅用功而且聰明。吳穎雖然聰明，但不用功。張輝與王麗都是三好學生。張輝與王麗是同學。

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

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

例1.3將下列命題符號化吳穎既用功又聰明。p:吳穎用功。合取舉例p：我們?nèi)タ措娪啊?/p>

q：房間里有十張桌子。

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

在數(shù)理邏輯中，關心的只是復合命題與構成復合命題的各原子命題之間的真值關系，即抽象的邏輯關系，并不關心各語句的具體內(nèi)容。說明合取舉例p：我們?nèi)タ措娪啊?/p>

q：房間里有十張桌子。

p∧q定義1.3 析取(disjunction)設p，q為二命題，復合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯(lián)結詞，并規(guī)定p∨q為假當且僅當p與q同時為假。

自然語言中的“或”具有二義性，用它聯(lián)結的命題有時具有相容性，有時具有排斥性，對應的聯(lián)結詞分別稱為相容或和排斥或(排異或)。析取式p∨q

表示的是一種相容或說明pqp∨q1

11101011000定義1.3 析取(disjunction)設p，q為二命題，例1.4將下列命題符號化

張曉靜愛唱歌或愛聽音樂。張曉靜只能挑選202或203房間。張曉靜是江西人或安徽人。設p：張曉靜愛唱歌，q：張曉靜愛聽音樂。

相容或，符號化為

p∨q設t：張曉靜挑選202房間，

u：張曉靜挑選203房間。

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

s：張曉靜是安徽人。

排斥或，符號化為：r∨s。

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

或符號化為：(r∧┐s)∨(┐r∧s)例1.4將下列命題符號化張曉靜愛唱歌或愛聽音樂。設p：定義1.4 蘊涵(implication)設p，q為二命題，復合命題“如果p，則q”稱作p與q的蘊涵式，記作p→q，并稱p是蘊涵式的前件，q為蘊涵式的后件，→稱作蘊涵聯(lián)結詞,并規(guī)定p→q為假當且僅當p為真q為假。

說明p→q的邏輯關系表示q是p的必要條件。q是p的必要條件有許多不同的敘述方式。只要p，就q

因為p，所以qp僅當q只有q才p除非q才p除非q，否則非p

前件p和后件q可以沒有任何內(nèi)在聯(lián)系。pqp→q1

11100011001定義1.4 蘊涵(implication)設p，q為二命題，例1.5將下列命題符號化，并指出其真值

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

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

p→q┐p→q p→┐q ┐p→┐q 1101例1.5將下列命題符號化，并指出其真值如果3+3＝6，則例1.5將下列命題符號化，并指出其真值

以下命題中出現(xiàn)的a是一個給定的正整數(shù)：(5)只要a能被4整除，則a一定能被2整除。(6)a能被4整除，僅當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)五個命題均敘述的是a能被2整除是a能被4整除的必要條件，因而都符號化為r→s。其真值為1在(10)中，將a能被4整除看成了a能被2整除的必要條件，因而應符號化為s→r。a值不定時，真值未知。例1.5將下列命題符號化，并指出其真值以下命題中出現(xiàn)的a關于蘊含的進一步說明作為一種規(guī)定，當p為假時，無論q是真是假，p→q均為真。也就是說，只有p為真q為假這一種情況使得復合命題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)的錯誤，沒有分清充分條件與必要條件。關于蘊含的進一步說明作為一種規(guī)定，當p為假時，無論q是真是假定義1.5 等價(two-way-implication)設p，q為二命題，復合命題“p當且僅當q”稱作p與q的等價式，記作p?q，稱作等價聯(lián)結詞，并規(guī)定p?q為真當且僅當p與q同時為真或同時為假。說明“當且僅當”（ifandonlyif）p?q的邏輯關系為p與q互為充分必要條件。

(p→q)∧(q→p)與p?q的邏輯關系完全一致。pqpq1

11100010001定義1.5 等價(two-way-implication)設例1.6將下列命題符號化，并討論它們的真值

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

符號化為p?q，真值為0。設p：2+3＝5，q：π是無理數(shù)。

符號化為p?q，真值為1。設p：兩圓A，B的面積相為p?q，真值為1。設p：王小紅心情愉快，q：王小紅唱歌。

符號化為p?q，真值由具體情況而定。例1.6將下列命題符號化，并討論它們的真值是無理數(shù)當關于真值（邏輯）聯(lián)結詞的說明基本聯(lián)結詞的真值見下表：關于真值（邏輯）聯(lián)結詞的說明關于真值聯(lián)結詞的說明在命題邏輯中，可用這些聯(lián)結詞將各種各樣的復合命題符號化。基本步驟如下：

（1）分析出各簡單命題，將它們符號化

（2）使用合適的聯(lián)結詞，將簡單命題逐個聯(lián)結起來，組成復合命題的符號化表示。關于真值聯(lián)結詞的說明在命題邏輯中，可用這些聯(lián)結詞將各種各樣的關于聯(lián)結詞的說明多次使用聯(lián)結詞集中的聯(lián)結詞，可以組成更為復雜的復合命題。求復雜復合命題的真值時，除依據(jù)上表外，還要規(guī)定聯(lián)結詞的優(yōu)先順序，將括號也算在內(nèi)。本書規(guī)定的聯(lián)結詞優(yōu)先順序為：()，┐，∧，∨，→，?，對于同一優(yōu)先級的聯(lián)結詞，先出現(xiàn)者先運算。關于聯(lián)結詞的說明多次使用聯(lián)結詞集中的聯(lián)結詞，可以組成更為復雜例1.7令

p：北京比天津人口多。 q：2+2＝4.

r：烏鴉是白色的。

求下列復合命題的真值：

(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我們關心的是復合命題中命題之間的真值關系，而不關心命題的內(nèi)容。說明例1.7令 p：北京比天津人口多。解：p、q、r的真值分別1.2命題公式及分類1.2命題公式及分類定義1.6合式公式(wff)命題公式的嚴格定義：(1)單個命題或命題變項p,q,r…,pi,qi

,ri

…，0，1是合式公式。(2)若A是合式公式，則(┐A)也是合式公式。(3)若A，B是合式公式，則(A∧B)，(A∨B)，(A→B)，(AB)也是合式公式。(4)只有有限次地應用(1)～(3)組成的符號串才是合式公式。合式公式也稱為命題公式，簡稱為公式。將命題變項用聯(lián)結詞和圓括號按一定的邏輯關系聯(lián)結起來的符號串稱為合式公式或命題公式。定義1.6合式公式(wff)命題公式的嚴格定義：將命題關于合式公式的說明定義1.6給出的合式公式的定義方式稱為歸納定義或遞歸定義方式。定義中引進了A,B等符號，用它們表示任意的合式公式，而不是某個具體的公式，這與p,p∧q,(p∧q)→r等具體的公式是有所不同的。(┐A)、(A∧B)等公式單獨出現(xiàn)時，外層括號可以省去，寫成┐A、A∧B等。公式中不影響運算次序的括號可以省去，

如公式(p∨q)∨(┐r)可以寫成p∨q∨┐r。合式公式的例子：

(p→q)∧(q?r)

(p∧q)∧┐r

p∧(q∧┐r)不是合式公式的例子

pq→r

(p→(r→q)關于合式公式的說明定義1.6給出的合式公式的定義方式稱為歸納定義1.7公式層次(1)若公式A是單個的命題（常項或變項），則稱A為0層合式。(2)稱A是n+1(n≥0)層公式是指下面情況之一： (a)A＝┐B，B是n層公式； (b)A＝B∧C，其中B,C分別為i層和j層公式，且n=max(i,j)； (c)A＝B∨C，其中B,C的層次及n同(b)； (d)A＝B→C，其中B,C的層次及n同(b)； (e)A＝B?C，其中B,C的層次及n同(b)。(3)若公式A的層次為k，則稱A是k層公式。例如：(┐p∧q)→r，(┐(p→┐q))∧((r∨s)?┐p) 分別為3層和4層公式定義1.7公式層次(1)若公式A是單個的命題（常項或變項）公式的解釋在命題公式中，由于有命題符號的出現(xiàn)，因而真值是不確定的。當將公式中出現(xiàn)的全部命題符號都解釋成具體的命題之后，公式就成了真值確定的命題了。(p∨q)→r若p：2是素數(shù)，q：3是偶數(shù)，r：是無理數(shù)，則p與r被解釋成真命題，q被解釋成假命題，此時公式(p∨q)→r被解釋成：若2是素數(shù)或3是偶數(shù)，則是無理數(shù)。（真命題）若p,q的解釋不變，r被解釋為：是有理數(shù)，則(p∨q)→r被解釋成：若2是素數(shù)或3是偶數(shù)，則π是有理數(shù)。（假命題）將命題變項p解釋成真命題，相當于指定p的真值為1，解釋成假命題，相當于指定p的真值為0。

公式的解釋在命題公式中，由于有命題符號的出現(xiàn)，因而真值是不確定義1.8賦值或解釋設A為一命題公式，p1,p2,…,pn是出現(xiàn)在公式A中的全部命題變項，給p1,p2,…,pn各指定一個真值，稱為對A的一個賦值或解釋。若指定的一組值使A的真值為1，則稱這組值為A的成真賦值；若使A的真值為0，則稱這組值為A的成假賦值。對含n個命題變項的公式A的賦值情況做如下規(guī)定：

(1)若A中出現(xiàn)的命題符號為p1,p2,…,pn，給定A的賦值α1,α2,…,αn

是指p1＝α1，p2＝α2,…，pn＝αn。

(2)若A中出現(xiàn)的命題符號為p，q，r...,給定A的賦值α1,α2,…,αn是指p＝α1，q＝α2,…，最后一個字母賦值αn。上述αi取值為0或1，i＝1,2,…,n。

定義1.8賦值或解釋設A為一命題公式，p1,p2,…,pn賦值舉例在公式(┐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)→r中，

011(p1＝0，p2＝1，p3＝1)為成真賦值，

100(p1＝1，p2＝0，p3＝0)為成假賦值。重要結論：

含n(n≥1)個命題變項的公式共有2n個不同的賦值。

賦值舉例在公式(┐p1∧┐p2∧┐p3)∨(p1∧p2)中，定義1.9真值表將命題公式A在所有賦值下取值情況列成表，稱作A的真值表。構造真值表的具體步驟如下：(1)找出公式中所含的全體命題變項p1,p2,…,pn(若無下角標就按字典順序排列)，列出2n個賦值。本書規(guī)定，賦值從00…0開始，然后按二進制加法依次寫出各賦值，直到11…1為止。(2)按從低到高的順序?qū)懗龉降母鱾€層次。(3)對應各個賦值計算出各層次的真值，直到最后計算出公式的真值。

公式A與B具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考慮構造真值表的中間過程。

說明定義1.9真值表將命題公式A在所有賦值下取值情況列成表，稱例1.7求下列公式的真值表，并求成真賦值和成假賦值。(1)(┐p∧q)→┐r(2)(p∧┐p)?(q∧┐q)(3)┐(p→q)∧q∧r

（1）例1.7求下列公式的真值表，并求成真賦值和成假賦值。（1）（2）（2）（3）（3）定義1.10重言式、永真式、可滿足式設A為任一命題公式(1)若A在它