Chapter-1-命題邏輯初步

2024/5/141邏輯與代數(shù)

Logic&Algebra靳(jìn)勇飛

904693585discretemathe@163/IfIdoIcan@20132013.3本課程的主要內(nèi)容命題邏輯初步謂詞邏輯初步集合與關(guān)系代數(shù)系統(tǒng)根底知識(shí)2024/5/14102關(guān)于數(shù)學(xué)--我的數(shù)學(xué)觀人們在認(rèn)識(shí)世界的過程中，對(duì)世界(包括物質(zhì)世界和認(rèn)識(shí)物質(zhì)世界產(chǎn)生的精神世界)的理解形成了一種共同的抽象，抽象到一定程度,這些抽象的字面含義不再與要認(rèn)識(shí)的世界有直接的關(guān)系，這就形成了數(shù)學(xué)。認(rèn)識(shí)數(shù)學(xué)要注意的的幾個(gè)特征由于是抽象，可以適用于多種場合由于是抽象，其必然受限于如何抽象，具體表現(xiàn)為不同時(shí)期的認(rèn)識(shí)不同它是一種共同的抽象，因此具有再現(xiàn)性抽象至不再具有字面的意思，區(qū)別于其他科學(xué)抽象的結(jié)果作為一種精神存在，也可以作為進(jìn)一步的認(rèn)識(shí)對(duì)象數(shù)學(xué)的開展既有應(yīng)用的推動(dòng)，又有自身開展的需要邏輯的目的邏輯的目的不是告訴你什么是對(duì)的，而是告訴你怎么做可以在前提正確的情況下保證你的結(jié)論是對(duì)的2024/5/14106數(shù)理邏輯根底數(shù)理邏輯是用數(shù)學(xué)方法研究關(guān)于推理、證明等問題的一門學(xué)科。為之做出奠基性工作的有:

萊布尼茲(Leibniz,德國,1646-1716)

布爾(Boole,英國,1815-1864)

弗雷格(Frege,法國,1848-1925)

皮亞諾(Peano,意大利,1858-1932)

希爾伯特(Hilbert,德國,1862-1943)

羅素(Russel,英國,1872-1970)

哥德爾(G?del,德國,1906-1978)

圖靈(Turing,英國,1912-1954)等所有的數(shù)學(xué)內(nèi)容都源自于一種對(duì)世界的夢想，你的夢想是什么？2024/5/141072000多年前：蘇格拉底、柏拉圖、亞里士多德新的知識(shí)是如何獲得的？歸納三段論所有的人都是要死的,蘇格拉底是人,所以蘇格拉底是要死的沒有一條魚是有理性的，所有的鯊魚都是魚，所以沒有一條鯊魚是有理性的人都是有理性的，有些動(dòng)物是人，所以有些動(dòng)物是有理性的沒有一個(gè)希臘人是黑色的，有些人是希臘人，所以有些人不是黑色的2024/5/14108大約350年前：萊布尼茲萊布尼茲的夢想我們需要一種普遍的文字，一個(gè)包含了人類全部思想領(lǐng)域的符號(hào)系統(tǒng)，有了這樣一個(gè)符號(hào)系統(tǒng)，我們就可以確定用這種語言寫成的哪些句子為真，以及他們之間存在著什么樣的邏輯關(guān)系萊布尼茲設(shè)計(jì)、制造了能做加、減、乘、除以及開方運(yùn)

算的計(jì)算機(jī),提出了“使所有推理過程實(shí)現(xiàn)機(jī)械

化”2024/5/14109萊布尼茲的邏輯演算〔草稿〕定義3A在L之內(nèi)或者L包含A,等價(jià)于L可以與以A為其中一項(xiàng)的許多項(xiàng)相一致。BN=L表示B在L之內(nèi)，B與N共同組成了L.更多的數(shù)目的項(xiàng)的情形也是一樣。公理1BN=NB公理2AA=A命題5如果A在L之內(nèi)且A=B,那么B在L之內(nèi)命題6如果A在B之內(nèi)且B=C,那么A在C之內(nèi)命題7A在A之內(nèi)…命題20如果A在M之內(nèi)，B在N之內(nèi)，那么AB在MN之內(nèi)2024/5/141010Leibniz的主要奉獻(xiàn)：

(1)創(chuàng)造微積分;創(chuàng)造了一套微積分的符號(hào)系統(tǒng).

(2)設(shè)計(jì)、制造了能做加、減、乘、除以及開方運(yùn)

算的計(jì)算機(jī),提出了“使所有推理過程實(shí)現(xiàn)機(jī)械

化”這一宏偉方案.

(3)創(chuàng)造了二進(jìn)制系統(tǒng),并用它對(duì)中國古老的八卦方

圓圖給出了合理的解釋(將中國古老的易圖解釋

成0~64的二進(jìn)制數(shù)表).

(4)提出了數(shù)理邏輯的根本思想和理論根底(手稿).2024/5/141011大約150年前：布爾…假設(shè)一個(gè)形容詞，比方說“好的”，被用作一個(gè)描述詞，那么讓我們用一個(gè)字母，比方說y來表示可以用“好的”來描述的所有事物，即“所有好的事物”或“好的事物”的類。再另xy這一組合表示同時(shí)適用于x和y所代表的名稱或描述詞的所有事物的類。于是，如果x表示“白的東西”，y表示“綿羊”，那么xy表示“白的綿羊”；類似的，如果z表示“有角的東西”…那么zxy表示“有腳的白綿羊”…2024/5/141012布爾的邏輯代數(shù)xx=x總是為真的，既是綿羊又是綿羊的東西是綿羊這個(gè)方程只有在0、1時(shí)才成立，如果只限于0和1兩個(gè)值，邏輯代數(shù)就是普通代數(shù)了！0可解釋成沒有任何東西屬于它的類，1可解釋成包含所有考慮對(duì)象的類x+y表示或者在x中或者在y中的所有事物的類，x-y表示在x中但不在y中的事物的類x+(1-x)=1表示在x中的事物或者不在x中的事物就是所有的事物

x(1-x)=0表示即在x中有不在x中的事物不存在：亞里士多德的排中律2024/5/141013用布爾代數(shù)進(jìn)行三段論的推導(dǎo)所有的x都是y,所有的y都是z,所以所有的x都是z所有的x都是y，即沒有東西在x中但不在y中，x(1-y)=0,x=xy所有的y都是z，即沒有東西在y中但不在z中，y(1-z)=0,y=yzx=xy=x(yz)=(xy)z=xz,x(1-z)=0,沒有東西在x中但不在z中，所有的x都是z布爾的工作把邏輯演繹變成了一個(gè)數(shù)學(xué)分支2024/5/141014Boole的主要奉獻(xiàn):(1)實(shí)現(xiàn)了邏輯的數(shù)學(xué)化(用符號(hào)進(jìn)行邏輯演算),創(chuàng)造了邏輯的代數(shù)系統(tǒng).(2)出版了兩部重要的數(shù)理邏輯奠基性的著作:《邏輯的數(shù)學(xué)分析》(1847)《思維規(guī)律的研究作為邏輯與概率的數(shù)學(xué)理論的根底》(1854)在這兩部著作中,他給出了現(xiàn)今稱為“Boole代數(shù)”的理論的雛形.2024/5/141015.

的主要奉獻(xiàn)131年前：弗雷格1879年費(fèi)雷格出版了一本不到100頁的小冊子《概念語言》，副標(biāo)題是“一種模仿算術(shù)語言構(gòu)造的純思維的形式語言”，被譽(yù)為“也許是自古以來最重要的一部邏輯學(xué)著作”。試圖找到一個(gè)能夠包含數(shù)學(xué)實(shí)踐中的全部演繹推理的邏輯系統(tǒng)。2024/5/141016弗雷格的形式語法弗雷格把連接命題的關(guān)系用于分析命題的結(jié)構(gòu)他考慮了“如果…那么…”、“…且…”、“…或…”、“任何…”、“某個(gè)…”、“非…”等，并給出了相應(yīng)的符號(hào)∧∨弗雷格的體系原那么上包括了通常使用的全部推理2024/5/141017弗雷格的形式語法的例子所有的馬都是哺乳動(dòng)物。(

x)(x是一匹馬x是哺乳動(dòng)物)有些馬是純種的。(

x)(x是一匹馬∧x是純種的)所有不及格的學(xué)生或者是糊涂的或者是懶惰的F(x)表示x是個(gè)不及格的學(xué)生，S(x)表示x是糊涂的，L(x)表示x是懶惰的，(

x)(F(x)

S(x)∨L(x))2024/5/141018Frege的主要奉獻(xiàn):(1)總結(jié)性著作為《概念語言》一書(1879年出版).在其中創(chuàng)造了一種所謂的“純粹思想的語言”,即表意的語言,使我們可以完全精確地表達(dá)判斷的概念內(nèi)涵.例如:他嚴(yán)格區(qū)別了命題的表達(dá)和判斷;明確提出了真值蘊(yùn)含的思想,并指出了它與日常語言的區(qū)別;他還引進(jìn)了內(nèi)容同一的符號(hào);引入了量詞的理論等等.(2)給出了歷史上第一個(gè)嚴(yán)格的現(xiàn)代邏輯系統(tǒng).這個(gè)系統(tǒng)實(shí)際上包含了作為現(xiàn)代數(shù)理邏輯根底的兩個(gè)演算系統(tǒng)------命題演算系統(tǒng)和一階謂詞演算系統(tǒng).2024/5/141019108年前：羅素康托爾對(duì)無窮集的研究：集合的基數(shù)，對(duì)角線方法羅素悖論：令A(yù)表示所有不包含自身的集合組成的集合，即A={B|BB}.現(xiàn)在的問題是AA是否成立？羅素悖論意味著集合這個(gè)概念有問題，而集合是所有數(shù)學(xué)，當(dāng)然也包括弗雷格的邏輯，的根底2024/5/141020Russel的主要奉獻(xiàn):(1)給出著名的Russel悖論,并提出了類型論以消除悖論.對(duì)數(shù)學(xué)根底產(chǎn)生了重大影響,并對(duì)數(shù)學(xué)根底的研究進(jìn)一步做出了奉獻(xiàn).(2)與合著《數(shù)學(xué)原理》一書(共三卷,1910~1913年間出版).從較簡單的邏輯系統(tǒng)出發(fā),再加上少量的非邏輯公理,推導(dǎo)出了很大一局部經(jīng)典數(shù)學(xué).

2024/5/141021Peano的主要奉獻(xiàn):(1)是符號(hào)邏輯的先驅(qū)和公理化方法的身體力行的推行人.(2)對(duì)整數(shù)作了公理化處理,給出了著名的自然數(shù)公理.見他的名著《算術(shù)原理新方法》一書(1889年出版).(3)用公理化方法研究數(shù)學(xué),寫出了5卷本巨著《數(shù)學(xué)公式匯編》(1895~1908年間出版)(4)為他的《數(shù)學(xué)公式》方案花了26年的時(shí)間進(jìn)行研究,試圖從他的邏輯記號(hào)的假設(shè)干根本公理出發(fā)來建立整個(gè)的數(shù)學(xué)體系.對(duì)當(dāng)代數(shù)學(xué)家以及后來著名的Bourbaki學(xué)派產(chǎn)生了很大的影響.2024/5/1410221900年：Hilbert的綱領(lǐng)皮亞諾的自然數(shù)公理，PA系統(tǒng)希爾伯特的《幾何根底》〔1899〕是公理化思想的代表作，書中把歐幾里得幾何學(xué)加以整理，成為建立在一組簡單公理根底上的純粹演繹系統(tǒng)，并開始探討公理之間的相互關(guān)系與研究整個(gè)演繹系統(tǒng)的邏輯結(jié)構(gòu)建議從假設(shè)干形式公理出發(fā)將數(shù)學(xué)形式化為符號(hào)語言系統(tǒng)，并從不假定實(shí)無窮的有窮觀點(diǎn)出發(fā)，建立相應(yīng)的邏輯系統(tǒng)。然后再研究這個(gè)形式語言系統(tǒng)的邏輯性質(zhì)，從而創(chuàng)立了元數(shù)學(xué)和證明論。希爾伯特的目的是試圖對(duì)某一形式語言系統(tǒng)的無矛盾性給出絕對(duì)的證明，以便克服悖論所引起的危機(jī)，一勞永逸地消除對(duì)數(shù)學(xué)根底以及數(shù)學(xué)推理方法可靠性的疑心。2024/5/141023Hilbert的主要奉獻(xiàn):(1)創(chuàng)立了現(xiàn)代公理方法.明確提出了公理系統(tǒng)的三大基本要求,即相容性、獨(dú)立性和完備性.(2)提出了著名的形式化方法.其方法的要點(diǎn)在對(duì)于整個(gè)數(shù)學(xué)的邏輯系統(tǒng)的相容性的研究，這就是著名的證明論或者“元數(shù)學(xué)”的研究,希望一勞永逸地解決數(shù)學(xué)根底中的問題。(3)數(shù)學(xué)形式主義綱領(lǐng)的代表著作(與W.Ackermann以及P.Bernays合作):《數(shù)理邏輯根底》(1928年出版)《數(shù)學(xué)根底》(1934年出版)2024/5/1410241930年：哥德爾1930年柯尼斯堡，PA系統(tǒng)是不完備的1931年，PM(懷特海和羅素的形式邏輯系統(tǒng))是不完備的PM不完備性:即使把初等數(shù)論形式化之后，在這個(gè)形式的演繹系統(tǒng)中也總可以找出一個(gè)合理的命題來，在該系統(tǒng)中既無法證明它為真，也無法證明它為假。(在系統(tǒng)外部是可以證明這個(gè)結(jié)論是真的。)2024/5/141025G?del的主要奉獻(xiàn):(1)Hilbert的形式公理系統(tǒng)的邏輯根底是謂詞演算,當(dāng)時(shí)已證明了謂詞演算的可靠性(即一致性),是G?del于1929年證明了謂詞演算也有完全性,這是對(duì)Hilbert的形式化方案的一個(gè)有力支持.(2)1934年他證明了形式算術(shù)系統(tǒng)的不完全性這一著名的定理,從而否認(rèn)了Hilbert的形式化數(shù)學(xué)方案.2024/5/1410261935年左右：圖靈1930年，哥德爾證明了弗雷格的規(guī)那么是完備的希爾伯特判定問題：是否存在一個(gè)計(jì)算程序，只用所謂的一階邏輯的符號(hào)系統(tǒng)寫出的某些前提和結(jié)論，通過這個(gè)程序總是可以判定？圖靈對(duì)計(jì)算過程進(jìn)行了分析，得出結(jié)論：判定問題的算法不存在。副產(chǎn)品：發(fā)現(xiàn)了通用計(jì)算器的數(shù)學(xué)模型！2024/5/141027Turing的主要奉獻(xiàn):(1)對(duì)計(jì)算和算法給出了完全確定的定義,第一次把計(jì)算和自動(dòng)機(jī)(現(xiàn)稱Turing機(jī))聯(lián)系了起來.(2)解決了著名的Hilbert的判定問題以及半群的字的問題等數(shù)學(xué)難題.(3)于1945年最先提出了存貯程序控制計(jì)算機(jī)的設(shè)計(jì);他還是人工智能的先驅(qū),并參與了現(xiàn)代計(jì)算機(jī)的設(shè)計(jì)工作.2024/5/141028終于有了現(xiàn)代的計(jì)算機(jī)！2024/5/141029集合(set)

集合的根本概念一般把假設(shè)干東西(元素)放在一起就構(gòu)成一個(gè)集合.假設(shè)元素a屬于集合A,記作aA,假設(shè)元素a不屬于集合A,記作aA.集合中的元素不必是具體的事物,也可以是抽象的對(duì)象,甚至集合也可以作為集合的元素.例下面是集合的幾個(gè)例子:(1)S={1,2,3,4};(2)Z=所有整數(shù)(integer)組成的集合N=自然數(shù)集合={1,2,3,4,...}Q=所有有理數(shù)(rationalnumber)組成的集合R=所有實(shí)數(shù)(realnumber)組成的集合(3)T={x:x

R且x4-10x3+35x2-50x+24=0}(4)W={z|z

Z且存在x,y,u,v

Z使得x2+y2+u2+v2=z}集合的性質(zhì)(i)集合元素確實(shí)定性:即對(duì)具體一個(gè)集合而言,一個(gè)元素或在此集合中,或不在此集合中,二者必居其一;(ii)集合元素的無重復(fù)性:即集合的元素彼此不同,沒有重復(fù)的元素在同一個(gè)集合中重復(fù)出現(xiàn);{1,3,2}和{1,3,3,2}是同一個(gè)集合(iii)集合元素的無序性:例如我們認(rèn)為{1,2}和{2,1}是同一個(gè)集合;定義沒有任何元素的集合稱為空集〔emptyset,nullset,orvoidset〕，用表示定義兩個(gè)集合A和B是相等(equal)的,當(dāng)且僅當(dāng)A和B有相同的元素,記作A=B;集合A與集合B不相等,記作AB;A=B表示：如果xA，那么必有xB,并且如果xB，那么必有xA.集合元素的個(gè)數(shù)(cardinalityofset)集合A中元素的個(gè)數(shù)，用|A|表示。定義如果一個(gè)集合中只有限多(自然數(shù)或〇)個(gè)元素,那么稱之為一個(gè)有限集(finiteset);如果有無窮多個(gè)元素那么稱之為一個(gè)無限集〔或無窮集,infiniteset〕.子集(subset)定義.設(shè)A、B是任意兩個(gè)集合,如果任取xA,都有xB,那么稱A是B的子集(subset),或A包含在B內(nèi),記作AB(或BA).如果有AB,但AB,也就是說,至少存在一個(gè)元素bB,使得bA,那么稱A是B的一個(gè)真子集(propersubset),記為AB(或BA).注意“”與“”的意義完全不同.空集是任何集合的子集；空集、集合A稱為集合A的平凡子集(trivalsubset)；集合A的其他的子集稱為A的非平凡子集。下面的圖表達(dá)了集合B與其子集合A之間的關(guān)系:

例如,A={1,2},B={1,2,3},

那么AB,且也有AB.ZQRAB“”的性質(zhì)自反性AA;傳遞性AB且BC,那么AC;反對(duì)稱性如果AB且BA,那么A=B注：我們用了反自反性來定義兩個(gè)集合相等冪集(powerset)定義假設(shè)A是一個(gè)給定的集合,將集合A的每個(gè)子集看成一個(gè)元素,那么集合A的所有子集為元素所作成的新的集合稱為集合A的冪集,記為(A).

例求空集的冪集.解由于空集只有一個(gè)子集，也就是空集自己,從而它的冪集為

(

)={

}

.

(注)請注意將空集與{

}區(qū)別開來:中沒有任何元素,而{

}中恰好有一個(gè)元素.例

設(shè)A={1,2,3},試求它的冪集

(A).

解:集合A有8個(gè)子集,

它的冪集為

(A).

={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.定理如果A有n個(gè)元素,那么冪集(A)有2n個(gè)元素.

集合的運(yùn)算集合的并unionAB={x|(xA)或(xB)}集合的交intersectionAB={x|(xA)且(xB)}.集合的差differenceAB={x|xA且xB}集合的補(bǔ)complementAC或者~A如果在考慮的問題中E表示全集(universalset)，那么AC=E－A差又稱為相對(duì)補(bǔ)(relativedifference)冪集的一些性質(zhì)定理設(shè)A和B是兩個(gè)任意的集合,那么:(A)(B)的充要條件是AB.(A)=(B)的充要條件是A=B.(A)(B)(AB).(A-B)((A)-(B)){}.(A)(B)(AB).此外,(A)(B)=(AB)的充要條件是

AB或者BA.

多集合的并和交如果S表示一組集合

S={x|存在某個(gè)A

S使得x

A}

S={x|對(duì)所有的A

S都有x

A}.如果S={A1,A2,A3,...,An}如果S={A1,A2,A3,...}邏輯(logic)2024/5/141046命題(proposition)定義有確定的真(true)或者假(false)〔不是兩者皆有〕的陳述句稱為命題。真值：指命題的判斷結(jié)果,它不是“真”(T)就是“假”(F)一個(gè)句子是否為命題,先看它是否為陳述句,再看它的真值是否唯一.2024/5/141047例北京是中華人民共和國的首都。1+1=10.在太陽系以外的天體中是否存在與人類相似的有高度智慧的生物？請努力為實(shí)現(xiàn)你自己的人生理想而奮斗！在太陽系以外不存在像人類一樣的有高度智慧的生物.只要努力，任何人都有可能實(shí)現(xiàn)自己的人生理想。我正在說謊.2024/5/141048通常用大寫字母表示命題,稱為命題標(biāo)識(shí)符.

例.A:2是素?cái)?shù)

A表示命題“2是素?cái)?shù)”。

例.P:1+1=3P表示命題“1+1=3”。2024/5/141049聯(lián)結(jié)詞(connective)2024/5/141050真值表(truthtable)設(shè)A是命題公式,對(duì)所有出現(xiàn)在A中的命題變元P1,P2,…,Pn指定一組真值,那么稱這組真值為A的一個(gè)解釋或真值指派,將公式A在其所有可能的解釋下所取真值匯列成表,稱為命題公式的真值表.2024/5/141051

否認(rèn)〔negation)否認(rèn)設(shè)P是一命題,P的否認(rèn)是一個(gè)新的命題,記作P(非P).P的真值表(truthtable)如下所示：2024/5/141052PPTFFT例P:漢城和首爾是同一個(gè)城市;那么,P:漢城和首爾不是同一個(gè)城市.P:計(jì)算機(jī)根底是所有本科生的一門必修課;那么,P:計(jì)算機(jī)根底不是所有本科生的一門必修課.2024/5/141053合取(conjunction)設(shè)P和Q是命題，P和Q的合取是一個(gè)新命題，記作PQ,合取的定義為：當(dāng)且僅當(dāng)P和Q都為T時(shí),P

Q為T.真值表如下：

2024/5/141054PQP

QTTTTFFFTFFFF例P:他在吃飯,Q:他在說話.

PQ:他在吃飯，且他在說話.P:我今天晚上去柏林看世界杯冠軍爭奪賽,Q:我家里有12把椅子。

PQ:我今天晚上去柏林看世界杯冠軍爭奪賽，并且我家里有12把椅子。

合取聯(lián)結(jié)詞是自然語言中的“并且”“不但…,而且…”等詞的邏輯抽象，但它的使用與自然語言中相應(yīng)的用法并不完全一致：在自然語言中通常兩個(gè)命題之間有某種自然的聯(lián)系，而在數(shù)理邏輯中那么不然。

2024/5/141055析取(disjunction)設(shè)P和Q是命題，P和Q的析取是一個(gè)新命題，記作PQ。它的定義是：當(dāng)且僅當(dāng)P和Q都為F時(shí),P

Q為F.

真值表如下：

2024/5/141056PQP

QTTTTFTFTTFFF例注：析取聯(lián)結(jié)詞與自然語言中的“或”的意義不完全相同,在漢語中的“或”有時(shí)表示“可兼取的或”,有時(shí)表示“不兼取的或”。而數(shù)理邏輯中的析取只能是“可兼或”。他今天晚上在家吃飯或在學(xué)校食堂吃飯.T27次從北京開往拉薩的列車是9：30或21：30開。他是奧運(yùn)會(huì)100米冠軍或是奧運(yùn)會(huì)200米冠軍.前兩例中的“或”是“不可兼或”，而最后一例中“或”是“可兼或”〕2024/5/141057例大局部程序設(shè)計(jì)語言中定義的and、or和not與我們前面定義的合取、析取和非完全一樣。例如在C語言中如果P:x<10Q:x<4那么PQ和在C語言中表示為(x<10)&&!(x>4)的式子表示一個(gè)意思Baidu搜索引擎中可用&、|和-分表表示、和2024/5/141058條件(單條件，也可稱為蘊(yùn)含,condition)設(shè)P和Q是命題,條件命題(conditionalproposition)是一個(gè)復(fù)合命題,記作PQ,其定義為：當(dāng)且僅當(dāng)P的真值為T,Q的真值為F時(shí),PQ的真值才為F.真值表如下：

2024/5/141059PQP

QTTTTFFFTTFFTP稱為前提(或假設(shè),hypothesisorantecedent),Q稱為結(jié)論(或結(jié)果,conclusionorconsequent)“如果我被選為總統(tǒng),我會(huì)鏟除腐敗”。

P:我被選為總統(tǒng),Q:我會(huì)鏟除腐敗,那么命題為:PQ;“如果太陽從西邊出,我就投降”必為真命題;“如果1+2=3,那么2+2=6”在十進(jìn)制下是假命題。函數(shù)F(x)可導(dǎo)的必要條件是F(x)是連續(xù)函數(shù)。P:函數(shù)F(x)可導(dǎo),Q:F(x)是連續(xù)函數(shù),那么命題為:PQ;函數(shù)F(x)可導(dǎo)的充分條件是F(x)是連續(xù)函數(shù)。P:函數(shù)F(x)是連續(xù)函數(shù),Q:F(x)可導(dǎo),那么命題為:PQ;2024/5/141060注當(dāng)條件命題前件為“假”時(shí),無論后件是“真”還是“假”,條件命題的真值都為“真”,稱為truebydefault或者vacuouslytrue.條件命題的真值為True，并不是說條件命題中的結(jié)論局部真值為True2024/5/141061例〔x是實(shí)數(shù)〕如果x>4，那么x+2>4.P:x>4Q:x+2>4PQ如果5>4，那么5+2>4.如果3>4，那么3+2>4.如果1>4，那么1+2>4.2024/5/141062逆換式、反換式、逆反式稱QP是PQ的逆換式(converse);稱PQ是PQ的反換式(contrary);稱QP是PQ的逆反式(contrapositive);2024/5/1463雙條件(bicondition)設(shè)P和Q是命題,雙條件命題(biconditionalpropostion)是一個(gè)復(fù)合命題,記PQ,或者P

Q其定義為：當(dāng)且僅當(dāng)P與Q的真值相同時(shí),PQ的真值為T.真值表如下：

2024/5/141064PQP

QTTTTFFFTFFFT注：雙條件聯(lián)結(jié)詞

是自然語言中“當(dāng)且僅當(dāng)”,“相當(dāng)于”,“…與…一樣”等詞匯的邏輯抽象。例“兩個(gè)三角形相似當(dāng)且僅當(dāng)它們的三個(gè)角對(duì)應(yīng)相等”是一個(gè)真命題。

“a為偶數(shù)的充要條件是a的平方被4除余1”是一個(gè)假命題。

2024/5/141065聯(lián)結(jié)詞的運(yùn)算優(yōu)先級(jí)五個(gè)聯(lián)結(jié)詞“”，“”，“”，“”，“”可理解為命題的五個(gè)根本的邏輯運(yùn)算。運(yùn)算優(yōu)先級(jí)為：有括號(hào)時(shí)，優(yōu)先計(jì)算括號(hào)內(nèi)的運(yùn)算；沒有括號(hào)時(shí)，按照從高到低優(yōu)先順序依次為：

，，，，同一聯(lián)接詞的運(yùn)算，在沒有括號(hào)時(shí)，按照從左到右的順序計(jì)算2024/5/141066合式公式(Well-FormedFormula)與翻譯命題演算的合式公式:

(1)單個(gè)命題變元是一個(gè)合式公式;

(2)如果A和B是合式公式,那么

A,(A

B),(A

B),(A

B)和(A

B)以及對(duì)它們合法添加括號(hào)所得公式都是合式公式;

(3)有限次地應(yīng)用(1)和(2)所得到的任何符號(hào)串是合式公式。換句話說，正確的使用運(yùn)算符得到的公式稱為合式公式

例如,(P

Q),

(P

Q),(P(P

Q)),((P

Q)(Q

R)

(S

T)),都是合式公式.

而(P

Q)(Q),(P

Q,(P

Q)

Q)都不是合式公式.2024/5/141067

例符號(hào)化以下命題:(1)中國人既勤勞又勇敢;(2)不在改革中前進(jìn)，就在落后中滅亡;(3)除非天下大雨,否那么我將外出散步.解:(1)設(shè)P:中國人勤勞,Q:中國人勇敢,那么命題可表為:PQ;(2)設(shè)P:在改革中前進(jìn),Q:在落后中滅亡,那么命題可表為:(PQ)(PQ);(3)原命題的意義為:如果天不下大雨,那么我將外出散步;

設(shè)P:天下大雨,Q:我將外出散步,那么命題可表為:PQ;

2024/5/141068如果你學(xué)習(xí)努力，你一定能通過離散數(shù)學(xué)考試；如果你迷戀網(wǎng)絡(luò)游戲，或者熱衷于看武俠小說，那么你就不會(huì)努力學(xué)習(xí)；你沒通過離散數(shù)學(xué)考試，你也沒有熱衷于看武俠小說；所以你一定迷戀網(wǎng)絡(luò)游戲！2024/5/141069A:你學(xué)習(xí)努力B:你通過離散數(shù)學(xué)考試C:你迷戀網(wǎng)絡(luò)游戲D:你熱衷于看武俠小說(A

B)

(C

D

A)

(

B

D)

C2024/5/141070例構(gòu)造

P

Q和PQ的真值表;

解:2024/5/141071PQ

P

P

QPQTTFTTTFFFFFTTTTFFTTT例構(gòu)造(P

Q)

P的真值表；

解:

2024/5/141072PQ

PP

Q(P

Q)

PTTFTFTFFFFFTTFFFFTFF注:象(P

Q)

P這樣恒取真值F的命題稱為永假式或矛盾式。

例構(gòu)造(P

Q)(P

Q)和PQ的真值表；

解:

2024/5/141073PQ

P

QP

Q

P

Q(P

Q)(P

Q)PQTTFFTFTTTFFTFFFFFTTFFFFFFFTTFTTT注:象(P

Q)(P

Q)和PQ這樣有可能取到真值T且又不恒取真值T的命題稱為可滿足式。例給出

(P

Q)(P

Q)的真值表;

解:

2024/5/141074PQ

P

QP

Q

P

Q

(P

Q)

(P

Q)(P

Q)TTFFTFFTTFFTFTTTFTTFFTTTFFTTFTTT注:象

(P

Q)(P

Q)這樣恒取真值T的命題稱為永真式或重言式。如果一個(gè)命題公式A對(duì)于它所包含的命題變元的任意一組真值指派,其真值恒為真,那么稱公式A為永真式或重言式,記為T;如果對(duì)于它所包含的命題變元的任意一組真值指派,其真值恒為假,那么稱公式A為永假式或矛盾式,記為F;如果至少有一組真值指派使得公式A的真值為真,那么稱公式A為可滿足式。2024/5/141075例用數(shù)字0與1構(gòu)造(PQ)(QS)的真值表;

解：

2024/5/141076PQSPQQS(PQ)(QS)111111110111101010100000011010010010001111000100等價(jià)(邏輯等價(jià)logicallyequivalent)設(shè)A和B是命題公式,P1,P2,…,Pn為A和B中的所有原子變元,如果對(duì)P1,P2,…,Pn任何一組真值指派,A和B的真值都相同,那么稱A和B是等價(jià)的或邏輯相等的,記作AB.兩個(gè)命題的等價(jià)性可用它們的真值表加以證明。由前例可知

P

Q和PQ是等價(jià)的,即(P

Q)

(PQ).(P

Q)(P

Q)和PQ是等價(jià)的,即(P

Q)(P

Q)

(PQ).

2024/5/141077命題公式之間的等價(jià)性具有如下重要性質(zhì):

(1)自反性:對(duì)任意的公式A,必有:AA;

(2)對(duì)稱性:對(duì)任意的公式A,B,假設(shè)有:AB,

那么必有:BA;

(3)傳遞性:對(duì)任意的公式A,B,C,假設(shè)有:AB,BC,那么必有:AC。

2024/5/141078例求證:PQ(PQ)(QP);

證明:列出真值表

可知(PQ)(QP)與PQ的真值表完全相同,故有

PQ(PQ)(QP)2024/5/141079PQPQQPPQ(PQ)(QP)TTTTTTTFFTFFFTTFFFFFTTTT例P與Q的不可兼或(PQ)(PQ)和(PQ)的真值表如下：

注：由此可見，P與Q的不可兼或也可以用(PQ)來表示。2024/5/141080PQPQ(PQ)(PQ)(PQ)TTTFFTFFTTFTFTTFFTFF常用的演算公式對(duì)合律(雙重否認(rèn)律):PP；冪等律:PPP,PPP；結(jié)合律:(PQ)RP(QR)；

(PQ)RP(QR)；交換律:PQQP,PQqp；分配律:P(QR)(PQ)(PR)；

P(QR)(PQ)(PR)；

2024/5/141081吸收律:P(PQ)P,

P(PQ)P；De.Morgan律:(PQ)PQ,

(PQ)PQ；同一律:PFP,PTP；零律:PTT,PFF；否認(rèn)律(補(bǔ)律):PPT,PPF；條件律:PQPQQP，

PQ(PQ)(QP)PQ；

2024/5/141082例驗(yàn)證吸收律:P(PQ)P,P(PQ)P.解:由它們的真值表

立即可以看出這兩個(gè)等價(jià)性是成立的。2024/5/141083PQP

QP

QP(PQ)P(PQ)TTTTTTTFFTTTFTFTFFFFFFFF子公式和代換如果X是合式公式A的一局部,且X本身也是一個(gè)合式公式,那么稱X是公式A的子公式。

設(shè)A是命題公式,P1,P2,…Pn是其中的命題變元,假設(shè)用某些公式代換A中的某些命題變元，且假設(shè)用公式Qi代換Pi,那么必須用Qi代換A中的所有Pi,由此得到的新公式B稱為公式A的一個(gè)代換(置換).

2024/5/141084定理設(shè)X是公式A的子公式,XY,如果將A中的X用Y來置換得到公式B,那么公式B與公式A等價(jià),即,AB。

2024/5/141085例求證:Q(P(PQ))QP;

證明:設(shè)公式A:QP,因?yàn)?P(PQ)P,(吸收律)

A中的P用P(PQ)置換得到

公式B:Q(P(PQ)),

所以:AB,

即,QPQ(P(PQ))#

當(dāng)然Q(P(PQ))QP也可用真值表來驗(yàn)證。

2024/5/141086例求證:(PQ)(PQ)P;

證明:(PQ)(PQ)P(QQ)PTP

分配律否認(rèn)律零律

2024/5/141087例求證:P(QR)Q(PR)R(QP);

證明:P(QR)P(QR)(條件律)

Q(PR)(結(jié)合律,交換律)

Q(PR)(條件律)

又,P(QR)P(QR)

R(QP)R(QP)#2024/5/141088例求證:((PQ)(P(QR))(PQ)(PR)

T;證明:((PQ)(P(QR))(PQ)(PR)

((PQ)(P(QR))(PQ)(PR)(D.M)

((PQ)(P(QR))(PQ)(PR)(D.M)

((PQ)((PQ)(PR)))((PQ)(PR))(D.M,分配律)

((PQ)(PR))((PQ)(PR))(冪等)

T(否認(rèn))#2024/5/141089定理

任何兩個(gè)重言式的合取或析取,仍然是一個(gè)重言式.

2024/5/141090定理一個(gè)公式A是一個(gè)重言式,對(duì)其含的同一分量都用任何合式公式置換得到公式B,那么B仍是一個(gè)重言式.

例.求證((PS)R)((PS)R)為重言式.

證明:因?yàn)锳AT,以((PS)R)代換A,即得,(PS)R)((PS)R)T#2024/5/141091

定理

設(shè)A和B是命題公式,A

B當(dāng)且僅當(dāng)A

B是一個(gè)重言式.

2024/5/141092例求證:(PQ)(PQ);

證明:在前例中已得:(PQ)(PQ)是重言式,所以:(PQ)(PQ)#求證：(PQ)(QP)問：PQ與QP是等價(jià)的嗎？

2024/5/141093邏輯蘊(yùn)含當(dāng)且僅當(dāng)PQ是重言式時(shí),稱“P邏輯蘊(yùn)含Q”,記作:PQ;

請注意將“蘊(yùn)含”與“邏輯蘊(yùn)含”區(qū)別開來。2024/5/141094蘊(yùn)含式公式公式名稱PQP化簡律simplificationPPQ增廣律additionP(PQ)Q析取三段論disjunctivesyllogismP(PQ)Q肯定前件假言推理modusponens

Q(PQ)P否定后件假言推理modustollens(PQ)(QR)PR假言三段論hypotheticalsyllogism

公式名稱PPQ否定前件律

QPQ肯定后件律(PQ)(PR)(QR)R兩難推理

(PQ)P(PQ)Q(PQ)(RS)(PR)(QS)(PQ)(QR)(PR)例求證：(PQ)(QR)PR證明：只需證(PQ)(QR)(PR)是重言式。(PQ)(QR)(PR)?((PQ)(QR))(PR)?((?PQ)(?QR))(?PR)?(?PQ)?(?QR))(?PR)(P?Q)(Q?R))(?PR)(P?Q)?P)(Q?R)R)(?Q?P)(QR)?QQ?PR

T2024/5/141097

定理

設(shè)P和Q為任意兩個(gè)命題公式,PQ的充分必要條件是:PQ且QP;

2024/5/141098蘊(yùn)含式的性質(zhì)(1)設(shè)A、B、C為命題公式,假設(shè)AB,且A是重言式,

那么B必是重言式;

證明:由AB,知AB的真值恒為T,所以,A為T

時(shí),B也必為T#

(2)假設(shè)AB,BC,那么AC;

證明:由AB,BC,得:AB和BC為重言式,

由定理4.2知:(AB)(BC)也是重言式,

又由假言三段論知:(AB)(BC)AC,

由性質(zhì)(1)知:AC為重言式,即AC#2024/5/141099(3)假設(shè)AB,AC,那么A(BC);

證明:因?yàn)锳B,AC皆為重言式,

1)假設(shè)A為T,那么B和C皆為T,故BC為T,

因此,A(BC)為T,

2)假設(shè)A為F,那么無論BC為何真值,

都有,A(BC)為T,

故A(BC)為重言式,即A(BC)#

2024/5/1410100(4)假設(shè)AB,CB,那么ACB;

證明:設(shè)AB,CB,那么AB為T,且CB為T,從而,(AB)(CB)也為T,而由分配律得

(AB)(CB)

=(AC)B=(AC)B=ACB

從而有ACB為T,故ACB#2024/5/1410101推理理論定義設(shè)A和C是兩個(gè)命題公式,如果AC為重言式,即AC,稱C為A的有效結(jié)論,或稱C可由A邏輯地推出。

一般地,假設(shè)H1,H2,…,Hn以及C都是命題公式,如果有H1H2…HnC,那么稱C是一組前提H1,H2,…,Hn的有效結(jié)論。

邏輯推理的方法

邏輯推理的方法主要有真值表法、直接證法和間接證法。2024/5/1410103真值表法

設(shè)P1,P2,…,Pm是H1,H2,…,Hn和C中的所有原子命題變元,如果對(duì)P1,P2,…,Pm作了全部真值指派,并求出H1,H2,…,Hn和C對(duì)應(yīng)的真值,就可判斷H1H2…HnC是否成立。例用真值表證明邏輯蘊(yùn)含式:(PQ)(RQ)PR.解:令A(yù)=(PQ)(RQ),B=PR,那么有右邊真值表。

由此表可以看出,所要證明的邏輯蘊(yùn)含式是成立的.#PQR

P

QR

QAB=P

RA

BTTTTFFFTTTFFTFTTTFTFTFFTTFFFTFTTFTTTFFTTFTFTTTTTFFTTTTTTFFFTTTTT直接證法直接證法就是由一組前提,根據(jù)的等價(jià)式和蘊(yùn)含式以及一些公認(rèn)的推理規(guī)那么,推出有效的結(jié)論。

P規(guī)那么---前提在推導(dǎo)過程中的任何時(shí)候都可以引入使用;

T規(guī)那么---在證明的任何步驟上得到的結(jié)論都可以在其后的證明中引用。例用直接證法證明邏輯蘊(yùn)含式

(

P

Q)

(R

Q)

P

R.證法一:設(shè)左方為真，來證右方也為真。證畢。

(1)

P

Q=TP(2)若

P=T,則已有P

R=T

(分情況討論)(3)若Q=T,P=TT(1)(2)(分情況討論)(4)R

Q=TP(5)

R=TT(3)(4)(6)P

R=TT(3)(5)(

P

Q)

(R

Q)

P

R證法二:設(shè)右方為假，要證左方也為假.證畢。(1)

(P

R)P(2)PRT(1)(3)PT(2)(4)RT(2)(5)(P

(R

Q))T(3)(6)

(Q

(

R

Q))T(4)(7)

(Q

(R

Q))T(6)(8)

((

P

Q)

(R

Q))

T(5)(7)間接證法(反證法)定義假設(shè)公式H1,H2,…,Hm中的原子命題變元為P1,P2,…,Pn,如果存在P1,P2,…,Pn的一組真值指派,能使H1H2…Hm的真值為T,那么稱公式H1,H2,…,Hm是相容的。如果對(duì)于P1,P2,…,Pn的任一組真值指派,H1H2…Hm的真值均為F,那么稱公式H1,H2,…,Hm是不相容的。要證明:H1H2…HmC,(即由H1,…,Hm推出C)

即證:H1H2…HmC為重言式,

即證:C(H1H2…Hm)為重言式,

即證:C(H1H2…Hm)為重言式,

即證:C(H1H2…Hm)為矛盾式,

即證:H1,H2,…,Hm與C是不相容的。例用間接證法證明

(

P

Q)

(R

Q)

P

R.證明:證畢.(1)

(P

R)P(2)PRT(1)(3)PT(2)(4)RT(2)(5)

P

QP(6)QT(3)(5)(7)R

QP(8)

Q

T(4)(7)(9)Q

QT(6)(8)用CP規(guī)那么證明H1H2…Hn(RC)記S=H1H2...Hm,問題轉(zhuǎn)化為證明:S(RC).即證S(RC)為永真，即證S(RC)為永真，因?yàn)?S(RC)S(RC)

(SR)C)(SR)C

(SR)C,故只要證(SR)C為永真，即證(SR)C。所以,要證S(RC),只需證(SR)C即可。這種證明方法稱為CP規(guī)那么，稱R為附加前提。

例用CP規(guī)那么證明

(PQ)(RQ)PR.證明:證畢。(1)PP(附加前提)(2)

P

QP(3)QT(2)(4)R

QP(5)

RT(3)(4)其他聯(lián)結(jié)詞2024/5/1410113不可兼析取設(shè)P和Q是兩個(gè)命題公式,復(fù)合命題稱作P和Q的不可兼析取.的真值當(dāng)且僅當(dāng)P與Q的真值不相同時(shí)為T;否那么的真值為F.

定理連接詞有以下性質(zhì):

(1)交換律(2)結(jié)合律

(3)分配律:

(4)(同一律)

(5)(常元律)2024/5/14114條件否認(rèn)、與非、或非(條件否認(rèn))設(shè)P和Q是兩個(gè)命題公式,復(fù)合命題PQ稱作P和Q的條件否認(rèn).PQ的真值為T,當(dāng)且僅當(dāng)P→Q的真值為F(即P=T,Q=F).(即PQ(P→Q)))(與非↑)設(shè)P和Q是兩個(gè)命題公式,復(fù)合命題P↑Q稱作P和Q的“與非”.P↑Q的真值為T,當(dāng)且僅當(dāng)PQ的真值為F.(即P↑Q(PQ))(或非↓)設(shè)P和Q是兩個(gè)命題公式,復(fù)合命題P↓Q稱作P和Q的“或非”.P↓Q的真值為T,當(dāng)且僅當(dāng)PQ的真值為F.

(即P↓Q(PQ))2024/5/1410115最小聯(lián)結(jié)詞組定義

如果一組連接詞可以表達(dá)出所有聯(lián)結(jié)詞,但去掉其中的任何一個(gè),就不能表達(dá)出所有的聯(lián)結(jié)詞，稱該聯(lián)結(jié)詞組為最小聯(lián)結(jié)詞組.{,}、{,

}、{,→}、{↑}、{↓}等都是最小聯(lián)結(jié)詞組。2024/5/1410116對(duì)命題公式的進(jìn)一步分析2024/5/1410117對(duì)偶式定義設(shè)A是命題公式,將A中的聯(lián)結(jié)詞換成,將換成,假設(shè)有特殊變元T和F,那么相互替換,所得的公式A*稱為公式A的對(duì)偶式。

顯然,假設(shè)A*是A的對(duì)偶式,那么A也是A*的對(duì)偶式,即有:(A*)*=A;

例

(PQ)R的對(duì)偶式是(PQ)R

((PQ)(PQ))((PQ)(PQ))的對(duì)偶式是((PQ)(PQ))((PQ)(PQ)).2024/5/14119例ABC的對(duì)偶式不是ABC而是A(BC)

(AB)(AC)2024/5/1410120假設(shè)P、Q均為命題公式，那么(PQ)*(P*Q*)(PQ)*P*Q*PQP*Q*(P↑Q)*=P*↓Q*(P↓Q)*=P*↑Q*(PQ)*P*Q*2024/5/1410121定理設(shè)A和A*是對(duì)偶式,P1,P2,…,Pn是出現(xiàn)在A和A*中的原子變元,那么有:

(1)(A*)*=A

(2)A(P1,P2,…,Pn)A*(P1,P2,…,Pn),

(3)A(P1,P2,…,Pn)A*(P1,P2,…,Pn);

(4)A(P1,P2,…,Pn)B(P1,P2,…,Pn)的充要條件是A*(P1,P2,…,Pn)B*(P1,P2,…,Pn).前述定理說明，在等價(jià)的意義下，命題公式的對(duì)偶式是唯一的。我們將和命題公式A等價(jià)的命題公式的對(duì)偶式都稱之為A的對(duì)偶式。例寫出以下公式的對(duì)偶式.(1)(PQ)R(2)(PQ)(PQ)(3)(P↑Q)↓R.2024/5/1410124解:(1)(PQ)R(PQ)R,故它的對(duì)偶式為(PQ)R.(2)(PQ)(PQ)(PQ)(PQ)((PQ)(PQ))((PQ)(PQ))((PQ)(PQ))((PQ)(PQ)),故而它的對(duì)偶式為((PQ)(PQ))((PQ)(PQ)).

(3)(P↑Q)↓R((PQ))↓R(((PQ))R),故而它的對(duì)偶式為

(((PQ))R).

(注)經(jīng)過化簡可以得到

(((PQ))R)

(((PQ))↑R

(P↓Q)↑R.范式和主范式2024/5/14127析取范式定義一個(gè)命題公式稱為析取范式,當(dāng)且僅當(dāng)它具有形式:A1A2…An(n1),其中A1,A2,…,An都是由原子命題變元或其否認(rèn)所組成的合取式。

定義和一個(gè)命題公式等價(jià)的析取范式，稱為這個(gè)命題公式的一個(gè)析取范式例：析取范式

P(

P

Q)(PQR),PQ,

P

Q

R都是析取范式。問：PQR是不是析取范式？2024/5/1410129例：析取范式并不唯一顯然P

(Q

R)是一個(gè)析取范式;然而

P

(Q

R)(PP)P

(Q

R)這顯然也是它的一個(gè)形式不完全相同的析取范式.2024/5/1410130定理

每個(gè)命題公式都有與之等價(jià)的析取范式存在.例判斷以下各命題公式是否是析取范式:(1)P

Q

R

S

U(2)(P

Q)

(Q

R)解:(1)是的，因?yàn)樗慈缦滦问?/p>

(P

Q

R)

S

U

(2)不是范式,但可通過等價(jià)找到它的一個(gè)析取范式:(P

Q)

(Q

R)

(P

Q)

(Q

R)

(

P

Q)

(Q

R)

(

P

Q)

Q

R.例將下述命題公式化為析取范式:

(P

Q)

(P

Q).解:原式

(P

Q)

(P

Q)((P

Q)

(Q

P))

(P

Q)((

P

Q)

(

Q

P))

(P

Q)((P

Q)

(Q

P))

(

P

Q).這就是原公式的一個(gè)析取范式.將命題公式化為析取范式的一般方法(1)將公式中所有的聯(lián)結(jié)詞化為,,這三種聯(lián)結(jié)詞;(2)利用德摩根律將否認(rèn)聯(lián)結(jié)詞移到各個(gè)原子命題變量的前面;(3)再利用分配律和結(jié)合律等等價(jià)的命題公式將原命題公式化為析取范式.小項(xiàng)定義

形如P1*

P2*

…Pn*的命題公式稱為是由命題變元P1,P2,…,Pn產(chǎn)生的小項(xiàng)(也稱布爾小項(xiàng)、極小項(xiàng)、最小項(xiàng)、布爾合取式),其中Pi*為Pi或?yàn)?/p>

Pi。兩個(gè)命題變元P和Q的全部小項(xiàng)共有如下4個(gè):

P

Q,P

Q,

P

Q,

P

Q;

三個(gè)命題變元P,Q,R的全部小項(xiàng)共有如下8個(gè):

P

Q

R,P

Q

R,P

Q

R,P

Q

R,

P

Q

R,

P

Q

R,

P

Q

R,

P

Q

R一般來說,n個(gè)命題變元共有2n個(gè)小項(xiàng)。2024/5/1410136兩個(gè)命題變元P和Q的小項(xiàng)的真值表為:PQP

QP

Q

P

Q

P

QTTTFFFTFFTFFFTFFTFFFFFFT

三個(gè)命題變元P、Q、R的小項(xiàng)的真值表如下所示

2024/5/14138PQRPQRPQRPQRPQR

PQR

PQR

PQR

PQRTTTTFFFFFFFTTFFTFFFFFFTFTFFTFFFFFTFFFFFTFFFFFTTFFFFTFFFFTFFFFFFTFFFFTFFFFFFTFFFFFFFFFFFT小項(xiàng)性質(zhì)(1)沒有兩個(gè)小項(xiàng)是等價(jià)的；

(2)任意兩個(gè)不同小項(xiàng)的合取是矛盾式；

例如(PQR)(PQR)

PPQRF#

(3)全體小項(xiàng)的析取必為T小項(xiàng)的編碼規(guī)那么三個(gè)命題變量P,Q,R的小項(xiàng)的編碼規(guī)那么:

m000=PQR,m001=PQR,m010=PQR,m011=PQR,m100=PQR,m101=PQR,m110=PQR,m111=PQR編碼的下標(biāo)即使得小項(xiàng)取值為T的變量值的分配主析取范式定義如果命題公式A的一個(gè)析取范式僅由小項(xiàng)的析取所組成,那么此析取范式稱為公式A的主析取范式。矛盾式的主析取范式為空范式，用0表示。定理每個(gè)的命題公式都有主析取范式存在.

定理

對(duì)命題公式A而言，它的真值表中所有使得A的真值為T的指派所對(duì)應(yīng)的小項(xiàng)的析取,即為公式A的主析取范式。

例分別求PQ,PQ,(PQ)的主析取范式。解:列出三公式的真值表:

PQPQPQ(PQ)

由真值表及前面的定理可知

PQ

m00m01m11=(PQ)(PQ)(PQ)

PQ即m11，它就是自己的主析取范式

(PQ)

m00m01m10=(PQ)(PQ)(PQ)PQPQPQ(PQ)11110100010110100101例設(shè)一公式A的真值表如右:故A的主析取范式為:

Am111m010m000

=(PQR)(PQR)(PQR)PQRA11111100101010000110010100100001例求以下公式的主析取范式:

(1)Q(P(QP))

(2)(P(QR))(P(QR))解:(1)公式Q(P(QP))的真值表如下:

故而Q(P(QP))m11m10m00=(PQ)(P┐Q)(┐P┐Q)2024/5/14146PQQPP(QP)Q(P(QP))11111101110100000111(2)(P(QR))(P(QR))

(P(QR))(P(QR))

(PP)((P(QR))

((QR)P)((QR)(QR))

F(PQR)(PQR)F

(PQR)(PQR)

=

m000m111求主析取范式的一般步驟(1)化為析取范式;(2)除去析取式中所有為永假的析取項(xiàng);(3)將析取項(xiàng)中重復(fù)出現(xiàn)的合取項(xiàng)和相同的變元