離散數(shù)學(xué)及其應(yīng)用 課件 孫志海 第0-2章 概述、命題邏輯、謂詞邏輯

離散數(shù)學(xué)

DiscreteMathematics

我愛你中國定義及學(xué)習(xí)范疇離散數(shù)學(xué)(DiscreteMathematics):是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科，是現(xiàn)代數(shù)學(xué)的一個重要分支。計算機專業(yè)核心基礎(chǔ)課程研究離散量的結(jié)構(gòu)和相互間的關(guān)系理論2學(xué)分+實踐1學(xué)分離散的含義是指不同的連接在一起的元素，主要是研究基于離散量的結(jié)構(gòu)和相互間的關(guān)系，其對象一般是有限個或可數(shù)個元素。離散數(shù)學(xué)在各學(xué)科領(lǐng)域，特別在計算機科學(xué)與技術(shù)領(lǐng)域有著廣泛的應(yīng)用，同時離散數(shù)學(xué)也是許多專業(yè)課程，如面向?qū)ο蟪绦蛟O(shè)計、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、人工智能、數(shù)據(jù)庫、算法設(shè)計與分析等必不可少的先行課程。通過離散數(shù)學(xué)的學(xué)習(xí)，不但可以掌握處理離散結(jié)構(gòu)的描述工具和方法，為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件，而且可以提高抽象思維和嚴(yán)格的邏輯推理能力，為將來參與算法應(yīng)用、創(chuàng)新性的研究和開發(fā)工作打下堅實的基礎(chǔ)。學(xué)習(xí)的意義1數(shù)據(jù)結(jié)構(gòu)

2操作系統(tǒng)3計算機網(wǎng)絡(luò)4編譯原理5數(shù)字電路6數(shù)據(jù)庫7算法分析

8計算機圖形圖像9計算機程序設(shè)計10計算機網(wǎng)絡(luò)11大數(shù)據(jù)12人工智能《離散數(shù)學(xué)》是多門專業(yè)課程的先行課離散數(shù)學(xué)九十九何愁沒有女朋友6《離散數(shù)學(xué)》與古詩詞離散與連續(xù)7離散數(shù)學(xué)與數(shù)字信號離散數(shù)學(xué)與音頻信號我愛你中國演示羅剎海市離散數(shù)學(xué)與數(shù)字圖像離散數(shù)學(xué)與數(shù)字圖像白瑪木洛李蘭娟/s/g2Hs1lNNId-434bEqI2shA離散數(shù)學(xué)與數(shù)字視頻時間空間時間空間離散視頻序列應(yīng)用案例離散數(shù)學(xué)與人臉識別離散數(shù)學(xué)與人臉識別17大學(xué)食堂裝上人臉識別機師生可"刷臉吃飯"離散數(shù)學(xué)與人臉識別18離散數(shù)學(xué)與摳圖技術(shù)離散數(shù)學(xué)與芯片設(shè)計離散數(shù)學(xué)與程序優(yōu)化if(!((!p||q)&&p)||q){

//for(inti=0;i<5;i++)

//{//for(intj=0;j<100000000;j++)b++;//}}C++程序：0040D9CBmovedx,dwordptr[ebp-2Ch]0040D9CEandedx,0FFh0040D9D4testedx,edx0040D9D6jemain+114h(0040d9e4)0040D9D8moveax,dwordptr[ebp-30h]0040D9DBandeax,0FFh0040D9E0testeax,eax0040D9E2jemain+12Eh(0040d9fe)0040D9E4movecx,dwordptr[ebp-2Ch]0040D9E7andecx,0FFh0040D9EDtestecx,ecx0040D9EFjemain+12Eh(0040d9fe)0040D9F1movedx,dwordptr[ebp-30h]0040D9F4andedx,0FFh0040D9FAtestedx,edx0040D9FCjemain+137h(0040da07)0040D9FEmoveax,dwordptr[ebp-20h]0040DA01addeax,1匯編語言程序：A=((

p

q)

p)

q教學(xué)內(nèi)容1．命題邏輯2．謂詞邏輯3．集合論4．圖論5.離散數(shù)學(xué)的應(yīng)用舉例22教材及參考文獻23授課教材：離散數(shù)學(xué)及其應(yīng)用，孫志海、張蒙，西安電子科技大學(xué)出版社，2023年.參考教材：1.應(yīng)用離散數(shù)學(xué)（第3版），周麗、方景龍，人民郵電出版社，2021年.2.應(yīng)用離散數(shù)學(xué)（第2版），方景龍、周麗，人民郵電出版社，2020年.3.屈婉玲、耿素云、張立昂,《離散數(shù)學(xué)》(第2版),高等教育出版社,2015.4.KennethH.Rosen.DescreteMathematicsanditsApplications(SeventhEdition,影印版).機械工業(yè)出版社，2012.5.B.Kolman,R.C.Busby,S.C.Ross.DiscreteMathematicalStructures(FifthEdition).PrenticeHall.羅平譯，離散數(shù)學(xué)結(jié)構(gòu)（第五版），高等教育出版社，20056.D.S.Malik,DiscreteMathematicalStructures–TheoryandApplications,高等教育出版社,2005.7.左孝凌等,《離散數(shù)學(xué)》,上海科技文獻出版社,2002.8.李盤林等,《離散數(shù)學(xué)》,高等教育出版社,1999.9.張青、陳更力，《離散數(shù)學(xué)及其應(yīng)用》，清華大學(xué)出版社，2016.小結(jié)離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及相互關(guān)系的數(shù)學(xué)學(xué)科，應(yīng)用廣泛。數(shù)據(jù)結(jié)構(gòu)與算法芯片設(shè)計計算機圖形圖像《離散數(shù)學(xué)及其應(yīng)用》第1章命題邏輯目錄1.1命題和邏輯聯(lián)結(jié)詞1.2命題公式及其真值表1.3命題公式的等價演算1.4命題公式的范式1.6命題公式的推理演算1.5聯(lián)結(jié)詞的完備集讓計算機按業(yè)務(wù)需求工作，離不開程序設(shè)計，那什么是程序？程序=算法+數(shù)據(jù)算法=邏輯+控制可見“邏輯”對于編程是多么重要。要想學(xué)好、使用好計算機，邏輯是重要學(xué)習(xí)要素。此外，通過學(xué)習(xí)邏輯，掌握邏輯推理規(guī)律和證明方法，可以培養(yǎng)邏輯思維能力，掌握證明問題的技巧。邏輯學(xué)是一門研究思維形式及思維規(guī)律的科學(xué)，也是研究推理過程規(guī)律的科學(xué)。邏輯規(guī)律就是客觀事物在人的主觀意識中的反映。思維的形式結(jié)構(gòu)包括了概念、判斷和推理之間的結(jié)構(gòu)和聯(lián)系，其中概念是思維的基本單位，通過概念對事物是否具有某種屬性進行肯定或否定的回答，就是判斷；由一個或幾個判斷推出另一個判斷，就是推理。用數(shù)學(xué)方法來研究推理的規(guī)律稱為數(shù)理邏輯。這里所指的數(shù)學(xué)方法，就是引進一套符號體系的方法，在其中表達和研究推理的規(guī)律。數(shù)理邏輯也叫符號邏輯，它已在數(shù)字邏輯電路、控制理論、程序設(shè)計、人工智能、自然語言以及計算機科學(xué)等領(lǐng)域有著廣泛應(yīng)用。最早提出用數(shù)學(xué)方法描述和處理邏輯問題的是德國數(shù)學(xué)家、哲學(xué)家萊布尼茨（G.W.Leibniz），從此數(shù)理邏輯形成了專門的學(xué)科。數(shù)理邏輯的主要內(nèi)容包括邏輯演算（logicalcalculus）、公理化集合論（axiomaticsettheory）、模型論（modeltheory）、證明論（prooftheory）和遞歸論（recursivetheory），第1章和第2章主要介紹作為數(shù)理邏輯基礎(chǔ)部分的命題邏輯和謂詞邏輯（一階邏輯）。本章首先介紹命題邏輯。命題邏輯是研究命題如何通過一些邏輯聯(lián)結(jié)詞構(gòu)成更復(fù)雜的命題以及邏輯推理的方法。命題是指具有確定真假含義的陳述句。如果把命題看作運算對象，如同代數(shù)中的數(shù)字、字母或代數(shù)式，而把邏輯聯(lián)結(jié)詞看作運算符號，就像代數(shù)中的“加、減、乘、除”那樣，這樣由簡單命題組成復(fù)合命題的過程就可以當(dāng)作邏輯運算的過程，也就是命題演算。戈特弗里德·威廉·萊布尼茨1646年-1716年邏輯運算同代數(shù)運算一樣具有一定的性質(zhì)，滿足一定的運算規(guī)律。例如，滿足交換律、結(jié)合律、分配律，同時還滿足邏輯上的雙重否定律、吸收律、零律、同一律、德摩根律等。利用這些定律，可以進行邏輯推理，可以對復(fù)雜的復(fù)合命題進行簡化，可以判斷兩個命題是否等價等。這些推理和證明在計算機程序設(shè)計、程序正確性證明、計算機硬件設(shè)計、人工智能等諸多方面都有應(yīng)用。本章主要介紹命題、邏輯聯(lián)結(jié)詞、命題公式及其真值表、命題公式的等價演算、命題公式的范式、聯(lián)結(jié)詞的完備集和命題公式的推理演算等命題邏輯中的相關(guān)內(nèi)容。1.1命題和邏輯聯(lián)結(jié)詞數(shù)理邏輯是研究推理的數(shù)學(xué)分支，而推理的前提和結(jié)論都是表達判斷的陳述句（命題），因此，表達判斷的陳述句（命題）構(gòu)成了推理的基本單位。推理由一系列的陳述句（命題）組成。例如，因為5>4，所以5≠4。在這里“5>4”和“5≠4”是兩個陳述句，整個“因為5>4，所以5≠4”也是一個陳述句。這三個陳述句都成立，即為真。這種能區(qū)分真假的陳述句稱為命題（proposition）。作為命題的陳述句所表達的判斷結(jié)果稱作命題的真值，真值只取兩個值：真或假。真值為真的命題稱作真命題，真值為假的命題稱作假命題。真命題表達的判斷正確，假命題表達的判斷錯誤。任何命題的真值都是唯一的，沒有二義性。當(dāng)一個命題是真命題時，我們稱它的真值為“真”，用“T”或“1”表示；當(dāng)一個命題是假命題時，我們稱它的真值為“假”，用“F”或“0”表示。在命題邏輯中，對命題的組成部分不再進一步細分，以命題為基本研究單位，研究的粒度比較粗。1.1.1命題命題“因為5>4，所以5≠4”由兩個更簡單的命題“5>4”和“5≠4”組成?！?>4”和“5≠4”不能再分解成更簡單的命題了。這種不能被分解成更簡單的陳述句的命題稱作簡單命題或原子命題（simpleproposition）。在命題邏輯中，簡單命題是最小的基本單位，對它不再細分。但在各種論述和推理中，所出現(xiàn)的命題多數(shù)不是簡單命題，如上面的“因為5>4，所以5≠4”。由簡單命題通過“聯(lián)結(jié)詞”連接而成的命題，稱作復(fù)合命題（compoundproposition）。簡單命題邏輯聯(lián)結(jié)詞+復(fù)合命題1.1.1命題判斷給定的句子是否為命題，可以分兩步進行：（1）判斷所給定的語句是否為陳述句；（2）判斷給定的語句所表達的判斷結(jié)果是否有唯一的真值。1.1.1命題陳述句？真值唯一？+

1.1.1命題

解例1.1.1的13個句子中，語句（1)、（2）、（4）、（9）、（10）和（12）是命題，語句（3）、（5）、（6）、（7）、（8）、（11）和（13）不是命題。語句（1）和（2）是真命題。語句（3）的真值不確定，因為根據(jù)x和y的不同取值情況“x大于y”可真可假，即無唯一的真值，因而不是命題。語句（4）也是命題，雖然限于現(xiàn)在的認(rèn)知，語句（4）的真值還不能確定，但該語句的真值客觀存在而且唯一。語句（5）是感嘆句，語句（6）是祈使句，語句（7）、（11）和（13）是疑問句，因而這5個語句都不是命題，語句（9）和（12）是真命題，語句（10）是假命題。1.1.1命題解例1.1.1的13個句子中，語句（1)、（2）、（4）、（9）、（10）和（12）是命題，語句（3）、（5）、（6）、（7）、（8）、（11）和（13）不是命題。語句（8）特別有意思，假設(shè)語句（8）為真，即“我正在說假話”是真的，那么我正在說真話，因而語句（8）的真值應(yīng)為假，這與假設(shè)矛盾；反之，假設(shè)語句（8）為假，即“我正在說假話”是假的，那么我正在說假話，因而語句（8）的真值應(yīng)為真，同樣這與假設(shè)也矛盾?？梢娬Z句（8）既不能為真，也不能為假，真值無法確定，所以語句（8）也不是命題。像語句（8）這樣由真能推出假，又由假能推出真，從而既不能為真也不能為假的陳述句稱作悖論（paradox）。悖論的例子很多，例如，“我正在說謊”、“這句話是錯的”、“本命題是假的”等語句也是悖論。悖論不是命題。由例1.1.1可知，命題是陳述句，而不能是疑問句、祈使句、感嘆句等。判斷結(jié)果不唯一確定的陳述句不是命題（有時需根據(jù)該命題所涉及的時間、空間來確定）。陳述句中的悖論不是命題。1.1.1命題

1.1.1命題

1.1.1命題1.1.1命題

說明

例1.1.2中出現(xiàn)的5個命題都是復(fù)合命題。不妨稱“非p”，“q并且r”，“s或t”，“如果r，則u”和“r當(dāng)且僅當(dāng)u”上述表述形式為半形式化的，這種半形式化的表述形式不能令人滿意。在數(shù)理邏輯中，經(jīng)常將論述或推理中的各種要素都進行符號化，即構(gòu)造各種符號語言來代替自然語言。為達到這個目的，需要進一步抽象化，即將聯(lián)結(jié)詞也符號化。在例1.1.2中出現(xiàn)的聯(lián)結(jié)詞共有5個，分別如下：“非”、“并且”、“或”、“如果……則……”、“當(dāng)且僅當(dāng)”以上這些聯(lián)結(jié)詞是自然語言中常用的聯(lián)結(jié)詞，但往往具有二義性（ambiguity），為了排除二義性，在數(shù)理邏輯中必須給出聯(lián)結(jié)詞的嚴(yán)格定義，并且將它們用特定的符號表示。完全由符號構(gòu)成的語言稱為形式語言（formallanguage）。1.1.1命題自然語言中常常使用下面的一些聯(lián)結(jié)詞，例如：（1）“非”、“不”、“沒有”、“無”、“并非”、“并不”等來表示否定；（2）“并且”、“同時”、“以及”、“而（且）”、“不但……，而且……”、“既……，又……”、“盡管……，仍然……”、“和”、“也”、“同”、“與”等來表示同時；（3）“雖然……，也……”、“可能……，可能……”“或許……，或許……”等和“或（者）”的意義一樣；（4）“若……，則……”、“當(dāng)……，則……”、“如果……，就……”與“如果……，那么……”意義相同；（5）“充分必要”、“等同”、“一樣”、“相同”與“當(dāng)且僅當(dāng)”的意義一樣。也就是說，在自然語言中，這些聯(lián)結(jié)詞一般是同義的。在數(shù)理邏輯中將這些同義的聯(lián)結(jié)詞統(tǒng)一用專用符號表示，消除其二義性，以便書寫、推演和討論。1.1.2邏輯聯(lián)結(jié)詞與命題符號化命題邏輯中常用的5種邏輯聯(lián)結(jié)詞（logicalconnectives）有：否定詞、合取詞、析取詞、蘊涵詞和等值詞。類似實數(shù)的加、減、乘、除運算，這5種邏輯聯(lián)結(jié)詞也可稱為命題的5種運算。通過這些邏輯聯(lián)結(jié)詞可以把多個原子命題復(fù)合成一個復(fù)合命題。否定詞合取詞析取詞蘊涵詞等值詞1.1.2邏輯聯(lián)結(jié)詞與命題符號化1.1.2邏輯聯(lián)結(jié)詞與命題符號化定義1.1.1設(shè)p為命題，復(fù)合命題“非p”（或“p的否定”）稱作p的否定式，記作

p。符號

稱作否定詞（negation）。規(guī)定：

p

為真，當(dāng)且僅當(dāng)p為假。定義1.1.2設(shè)p，q為兩個命題，復(fù)合命題“p并且q”（或“p與q”）稱為p與q的合取式，記作p∧q。∧稱作合取詞（conjunction）。規(guī)定：p∧q為真，當(dāng)且僅當(dāng)p與q同時為真。定義1.1.3設(shè)p，q為兩個命題，復(fù)合命題“p或q”稱作p與q的析取式，記作p∨q?！欧Q作析取詞（disjunction）。規(guī)定：p∨q為假，當(dāng)且僅當(dāng)p與q同時為假。（相容或、排斥或）定義1.1.4

設(shè)p，q為兩個命題，復(fù)合命題“如果p，則q”稱作p與q的蘊涵式，記作p

q，p稱作是蘊涵式的前件，q稱作蘊涵式的后件，

稱作蘊涵詞（implication）。規(guī)定：“p

q為假，當(dāng)且僅當(dāng)p為真、q為假”。1.1.2邏輯聯(lián)結(jié)詞與命題符號化使用蘊涵詞

時，要特別注意以下幾點：在自然語言里，特別是在數(shù)學(xué)中，q是p的必要條件有許多不同的敘述方式，例如，“若p則q”、“如果p，則q”、“只要p，就q”、“因為p，所以q”、“p僅當(dāng)q”、“只有q才p”、“除非q才p”、“除非q，否則‘非p’”、“若不q，則不p”等等。以上各種敘述方式表面看來有所不同，但都表示q是p的必要條件，因而都應(yīng)使用蘊涵詞

，符號化為p

q的形式，如下表所示。自然語義邏輯形式如果p，那么qp

q如果p，就qp

q只要p，就qp

q因為p，所以qp

q若p，則qp

qp僅當(dāng)qp

q只有q，才pp

q除非q才pp

q除非q，否則非pp

q若不q，則不pp

qq是p的必要條件p

qpq

pp∧qp∨qp

q001001011011100010110111表1.1.1

p、p∧q、p∨q

與p

q的真值1.1.2邏輯聯(lián)結(jié)詞與命題符號化例1.1.3

將下列命題符號化（合取詞）。（1）陳穎既用功又聰明。（2）陳穎不僅用功而且聰明。（3）陳穎雖然聰明，但不用功。（4）吳麗與林晗都是三好學(xué)生。（5）吳麗與林晗是同學(xué)。（6）2+2=4且雪是白色的。（7）你喜歡用微信，但我喜歡用QQ。解解題時，首先將涉及的原子命題符號化。（1）設(shè)p：陳穎用功；q：陳穎聰明。則命題（1）符號化為：p∧q。（2）設(shè)p：陳穎用功；q：陳穎聰明。則命題（2）符號化為：p∧q。（3）設(shè)p：陳穎用功；q：陳穎聰明。則命題（3）符號化為：q∧

p。（4）設(shè)r：吳麗是三好學(xué)生；s：林晗是三好學(xué)生。則命題（4）符號化為：r∧s。1.1.2邏輯聯(lián)結(jié)詞與命題符號化例1.1.3

將下列命題符號化（合取詞）。（5）吳麗與林晗是同學(xué)。（6）2+2=4且雪是白色的。（7）你喜歡用微信，但我喜歡用QQ。解解題時，首先將涉及的原子命題符號化。（5）這里雖然使用了“與”，但這個“與”是連接該句主語中的“吳麗”與“林晗”的，而整個句子仍是簡單陳述句，即（5）是原子命題，可將該原子命題符號化為如下形式：f：吳麗與林晗是同學(xué)。（6）設(shè)p：2+2=4；q：雪是白的。則命題（6）符號化為p∧q。（7）設(shè)p：你喜歡用微信；q：我喜歡用QQ。則命題（7）符號化為p∧q。1.1.2邏輯聯(lián)結(jié)詞與命題符號化例1.1.4將下列命題符號化（析取詞）。（1）張靜愛唱歌或愛跳舞。（2）張靜只能選擇1號樓的101或102寢室。（3）張靜是浙江人或福建人。解先給出原子命題，并將其符號化，然后再將整個（復(fù)合）命題符號化。（1）設(shè)p：張靜愛唱歌；q：張靜愛跳舞。命題（1）符號化為：p∨q。顯然這里的“或”為相容或，即當(dāng)p與q有一個為真或同時為真時，這個復(fù)合命題為真。1.1.2邏輯聯(lián)結(jié)詞與命題符號化（2）設(shè)r：張靜選擇1號樓101寢室；s：張靜選擇1號樓102寢室。結(jié)合題意，這里的“或”應(yīng)該為排斥或。r與s的取值有4種可能：同時為真，同時為假，一真一假和一假一真。如果符號化為r∨s，則當(dāng)r和s都為真時r∨s為真，即表示張靜可能同時選擇1號樓的101和102兩間寢室，這不符合原意。原意是張靜只能選擇1號樓101和102中的一間。然而，如何實現(xiàn)只能挑選一間寢室的要求呢？可以使用多個聯(lián)結(jié)詞，符號化為：(r∧

s)∨(

r∧s)。可以驗證，該復(fù)合命題為真當(dāng)且僅當(dāng)r與s中一個為真，一個為假，而式子(r∧

s)∨(

r∧s)準(zhǔn)確地表達了原意。當(dāng)r為真s為假時，張靜選擇了1號樓的101寢室；當(dāng)r為假s為真時，張靜選擇了1號樓的102寢室。r與s同時為真的情況是不允許的。(r∧

s)∨(

r∧s)的真值情況如表所示。rs(r∧

s)∨(

r∧s)FFFFTTTFTTTF1.1.2邏輯聯(lián)結(jié)詞與命題符號化例1.1.4將下列命題符號化（析取詞）。（3）張靜是浙江人或福建人。解

設(shè)t：張靜是浙江人；u：張靜是福建人。結(jié)合題意，這里的“或”應(yīng)為排斥或。與例1.1.4（2）一樣，可以將其符號化為(t∧

u)∨(

t∧u)。然而，張靜不可能既是浙江人又是福建人，即t與u實際上不能同時為真，因而這種情況下也可以簡單符號化為：t∨u。1.1.2邏輯聯(lián)結(jié)詞與命題符號化

1.1.2邏輯聯(lián)結(jié)詞與命題符號化自然語義邏輯形式如果p，那么qp

q如果p，就qp

q只要p，就qp

q因為p，所以qp

q若p，則qp

qp僅當(dāng)qp

q只有q，才pp

q除非q才pp

q除非q，否則非pp

q若不q，則不pp

qq是p的必要條件p

q解在解題時，首先將涉及的原子命題符號化，然后再符號化復(fù)合命題。（1）設(shè)p：你的月工資收入超過5000元；q：你必須繳納個人所得稅。則命題（1）符號化為：

p

q（2）設(shè)p：1+1=2；q：雪是白色的。則命題（2）符號化為：

p

q設(shè)r：a能被4整除，s：a能被2整除。（3）~（7）描述的都是a能被2整除是a能被4整除的必要條件，因而均可符號化為：r

s在（3）~（7）中，由于a是給定的正整數(shù)，因而r與s的真值是客觀存在的，但是真是假與a的具體取值有關(guān)，現(xiàn)在并不知道。然而，仔細分析可知，r與s是存在內(nèi)在聯(lián)系的，當(dāng)r為真（即a能被4整除）時，s必為真（a能被2整除）。當(dāng)r為假時，蘊涵式r

s前件為假，蘊涵式r

s也為真。綜上，r

s真值為1。1.1.2邏輯聯(lián)結(jié)詞與命題符號化定義1.1.5

設(shè)p，q為兩個命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等值式，記作p

q，

稱作等值詞。規(guī)定：p

q為真，當(dāng)且僅當(dāng)p與q同時為真，或同時為假。p

q的邏輯關(guān)系為p與q互為充分必要條件，即當(dāng)p

q為真時，p取1（0）時q必須取1（0），而q取1（0）時p也必須取1（0），因此，p

q與(p

q)∧(q

p)等價。還需要注意的是，“p成立僅當(dāng)q成立”表示“僅當(dāng)q成立時p才可能成立，但q成立時p并不一定成立”，這與“p成立當(dāng)且僅當(dāng)q成立”意思不一樣，前者的符號化結(jié)果是“p

q”，而后者的符號化結(jié)果是“p

q”。1.1.2邏輯聯(lián)結(jié)詞與命題符號化

1.1.2邏輯聯(lián)結(jié)詞與命題符號化

1.1.2邏輯聯(lián)結(jié)詞與命題符號化以上共定義了5種基本且常用，也是最重要的邏輯聯(lián)結(jié)詞，它們組成一個邏輯聯(lián)結(jié)詞集{

，∧，∨，

，

}，其中

為一元邏輯聯(lián)結(jié)詞，其余4個是二元邏輯聯(lián)結(jié)詞。這5個邏輯聯(lián)結(jié)詞的真值情況如表1.1.3所示。表1.1.3

p、p∧q、p∨q、p

q與

p

q的真值pq

pp∧qp∨qp

qp

q00100110110110100010011011111.1.2邏輯聯(lián)結(jié)詞與命題符號化使用多個聯(lián)結(jié)詞可以組成更復(fù)雜的復(fù)合命題，此外還可以使用圓括號“(”和“)”，“(”和“)”必須成對出現(xiàn)。復(fù)合命題也是命題，是陳述句，可以判斷真假，并且真值唯一。在求解比較復(fù)雜的復(fù)合命題的真值時，除依據(jù)表1.1.3的取值以外，還要規(guī)定聯(lián)結(jié)詞的優(yōu)先順序。將圓括號計算在內(nèi)，規(guī)定運算的優(yōu)先順序為（從左到右）：（高優(yōu)先級）()，

，∧，∨，

，

（低優(yōu)先級）由于基于運算的先后次序來理解邏輯表達式往往費時費力，而且容易出錯，因而建議采用添加括號的辦法，按先括號內(nèi)后括號外的規(guī)則進行命題運算。本書推薦采用添加括號的方法來處理邏輯運算的先后次序。實際寫程序的時候，添加一些成對的括號也有利于程序的解讀和維護。

注意：布爾運算（例如C語言中的按位布爾運算）和命題運算的符號相同（

，∧，∨），但在推導(dǎo)過程中，布爾運算一般讀作“非”、“與”和“或”，而在命題運算中則對應(yīng)為“否定”、“合取”和“析取”。1.1.2邏輯聯(lián)結(jié)詞與命題符號化例1.1.7

令p：中國是世界四大文明古國之一，q：π是無理數(shù)，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），（2），（3）的真值分別為1，1，0。例1.1.8

將命題“鍥（qiè）而舍之，朽木不折；鍥而不舍，金石可鏤（lòu）”符號化。解設(shè)p：你鍥，q：你舍，r：金石可鏤，s：朽木可折。則該命題符號化為：((p∧

q)

r)∧((p∧q)

s)1.1.2邏輯聯(lián)結(jié)詞與命題符號化例1.1.9

將命題“只有努力學(xué)習(xí)、認(rèn)真復(fù)習(xí)，才能取得好成績”符號化。解

設(shè)p：努力學(xué)習(xí)，q：認(rèn)真復(fù)習(xí)，s：取得好成績，則該命題可符號化為：s

(p∧q)注意，該命題不能符號化為(p∧q)

s，符號化時要考慮條件的必要性和充分性。1.1.2邏輯聯(lián)結(jié)詞與命題符號化邏輯聯(lián)結(jié)詞與C語言的邏輯運算符有所不同，在C語言中，邏輯運算符有“&&”、“||”和“!”，其用法如下：（1）“&&”表示“與”的意思，需要兩端的表達式的值都為True，該式的值才為True。（2）“||”表示“或”的意思，兩端的表達式的值只要有一端為True，該式的值就為True。（3）“!”表示“非”的意思，將該式的真值換成相反的真值，即False和True互換。下表給出了邏輯聯(lián)結(jié)詞與C語言邏輯運算符的對應(yīng)關(guān)系示例。1.1.2邏輯聯(lián)結(jié)詞與命題符號化邏輯聯(lián)結(jié)詞C語言邏輯運算符否定：

!p合?。骸膒&&q析取：∨p||q蘊涵：

if(p)q;等值：

(p&&q)||(!p&&!q)異或：⊕(p||q)&&(!p||!q)1.2命題公式及其真值表1.2.1命題公式簡單命題是命題邏輯中最基本的研究單位，其真值是確定的，它又稱作命題常項或命題常元（propositionalconstant）。命題常項相當(dāng)于初等數(shù)學(xué)中的常量。初等數(shù)學(xué)中還有變量，對應(yīng)的，這里有命題變項。取值1（真）或0（假）的變項稱作命題變項或命題變元（propositionalvariable）。用命題變項可以表示真值可變的陳述句。命題變項不是命題。命題變項與命題常項的關(guān)系如同初等數(shù)學(xué)中變量與常量的關(guān)系。今后也用p，q，r等表示命題變項。這樣一來，p、q、r、s、t等既可以表示命題常項，又可以表示命題變項，具體可結(jié)合上下文（context）確定。1.2.1命題公式將命題變項用邏輯聯(lián)結(jié)詞和圓括號按照一定的邏輯關(guān)系連接起來的符號串稱作命題公式（又稱為合式公式，簡稱為公式）。當(dāng)使用聯(lián)結(jié)詞集{

，∧，∨，

，

}時，命題公式的定義如下。定義1.2.1

命題公式是按下列規(guī)則定義的符號串。（1）單個命題變項和命題常項（0和1）是命題公式，稱為原子命題公式。（2）若X是命題公式，則(

X)是命題公式。（3）若X，Y是命題公式，則(X∧Y)，(X∨Y)，(X

Y)，(X

Y)均是命題公式。（4）有限次地應(yīng)用（1）~（3）形成的符號串是命題公式。上述定義是以遞歸的形式給出的，其中（1）稱為基礎(chǔ)，（2）和（3）稱為歸納，（4）稱為界限。設(shè)X為命題公式，Y為X中的一部分，若Y也是命題公式，則稱Y為X的子公式。1.2.1命題公式說明：（1）定義1.2.1給出的命題公式的定義方式稱作歸納定義或遞歸定義方式。（2）為方便起見，當(dāng)(

X)，(X∧Y)，(X∨Y)，(X

Y)，(X

Y)等公式單獨出現(xiàn)時，外層括號可以省去，寫成

X，X∧Y，X∨Y，X

Y，X

Y等。另外，公式中不影響運算次序的括號也可以省去，例如公式(p∨r)∨(

s)可以寫成p∨r∨

s。（3）由以上定義可知，如(p

q)∧(r

s)、(s∧q)∧

r、s∧(q∧

r)等都是命題公式，而sq

r、sqr、s

(r

q、p(r

q)和p∧q∧

等都不是命題公式。（4）一個含有命題變項的命題公式，該命題公式的真值是不確定的，這種情況下，命題公式本身不是命題。只有對該命題公式中的每個命題變項用指定的命題常項代替后，該命題公式才變成命題，其真值也唯一確定了。1.2.1命題公式

1.2.2真值表

1.2.2真值表

1.2.2真值表例1.2.1

寫出下列命題公式真值表，并求它們的成真賦值和成假賦值。（1）(

p

q)

(q

p)（2）(p

q)∨(q

r)（3）

(p

q)∧q∧r解命題公式（1）是含2個命題變項的3層命題公式，它的真值表如表1.2.1所示。從表1.2.1可知，命題公式（1）的成假賦值為01，其余3個賦值（00、10、11）都是成真賦值。pq

pq

p

p

q(

p

q)

(q

p)001101011010100111110111表1.2.1(

p

q)

(q

p)的真值表1.2.2真值表命題公式（2）是含3個命題變項的2層命題公式，它的真值表如表1.2.2所示。由表1.2.2可以看出，該命題公式的8個賦值全是成真賦值，即無成假賦值。pqrp

qq

r(p

q)∨(q

r)000111001111010101011111100011101011110101111111表1.2.2(p

q)∨(q

r)的真值表1.2.2真值表命題公式（3）是含3個命題變項的4層命題公式，它的真值表如表1.2.3所示。不難看出，該命題公式的8個賦值全是成假賦值，無成真賦值。pqrp

q

(p

q)

(p

q)∧q

(p

q)∧q∧r00010000011000010100001110001000100101010011010001111000表1.2.3

(p

q)∧q∧r的真值表1.2.2真值表定義1.2.5

設(shè)X為任一命題公式。（1）若X在它的各種賦值下取值均為真，則稱X為永真式或重言式（tautology）。（2）若X在它的各種賦值下取值均為假，則稱X為永假式或矛盾式（contradictory）。（3）若X不是永假式，則稱X是可滿足式（satisfiable）。從定義1.2.5不難看出以下幾點：（1）X是可滿足式說明X至少存在一個成真賦值。（2）永真式一定是可滿足式，但可滿足式不一定是永真式。若公式X是可滿足式，且它至少存在一個成假賦值，則稱X為非永真式的可滿足式。（3）真值表可用來判斷公式X的類型。①若真值表最后一列全為1，則公式X為永真式。②若真值表最后一列全為0，則公式X為永假式。③若真值表最后一列中至少有一個為1，則公式X為非永真的可滿足式。永真式可滿足式1.2.2真值表pq(

p

q)

(q

p)001010101111表1.2.1(

p

q)

(q

p)的真值表pqr(p

q)∨(q

r)00010011010101111001101111011111表1.2.2(p

q)∨(q

r)的真值表pqrp

q

(p

q)

(p

q)∧q

(p

q)∧q∧r00010000011000010100001110001000100101010011010001111000表1.2.3

(p

q)∧q∧r的真值表非永真式的可滿足式永假式永真式1.2.2真值表

1.2.2真值表例1.2.2

下列各公式均含2個命題變項p與q，它們中哪些具有相同的真值表？（1）p

q（2）p

q（3）

q∨p（4）

(p∧

q)（5）(p

q)∧(q

p)解表1.2.4給出了5個公式的真值表。從表1.2.4中可以看出，公式（1）與公式（4）具有相同真值表，公式（2）與公式（5）具有相同的真值表。pqp

qp

q

q∨p

(p∧

q)(p

q)∧(q

p)0011111011001010001001111111表1.2.45個公式的真值表1.2.2真值表

1.2.2

真值表解本例中給出的4個公式，總共有3個命題變項p，q和r，r是公式（1）的啞元，p是公式（2）的啞元，在討論它們是否有相同的真值表時，均按照3個命題變項列出它們的真值表。表1.2.5列出了4個公式的真值表，中間過程省略了。從表1.2.5中可以看出，公式（1）與公式（4）有相同的真值表，公式（2）與公式（3）有相同的真值表。pqrp

q

q∨r(q

r)∧(p

p)(

p∨q)∧((p∧r)

p)00011110011111010100101111111000110101011011010011111111表1.2.54個公式的真值表1.2.2

真值表—啞元應(yīng)用舉例啞元參數(shù)：

（1）定義函數(shù)時，只有類型而沒有變量名的形參被稱為啞元；（2）啞元參數(shù)在函數(shù)實體中無法使用，但還必須傳。需要使用啞元的場景：（1）在操作符重載函數(shù)中，區(qū)分前后++、--；（2）為了兼容舊的代碼。例如布爾函數(shù)f(x，y，z)，其中f(x，y，1)=f(x，y，0)，即z取1或0都不影響函數(shù)f，這里z就成了啞元。在C++函數(shù)中，有類型無名字的形參可看成啞元，如：voidfun(double){cout<<"啞元"<<endl;}某函數(shù)升級中，以下形式可以實現(xiàn)新版本兼容老版本：老版本：voidfun(intn1,intn2,intn3){……}新版本：voidfun(intn1,intn2,int){……}1.3命題公式的等價演算1.3命題公式的等價演算

1.3命題公式的等價演算

1.3命題公式的等價演算

st

s

ts∨t

(s∨t)

s∧

t

(s∨t)

s∧

t00110111011010011001100111001001表1.3.1

(s∨t)，

s∧

t與

(s∨t)

(

s∧

t)的真值表1.3命題公式的等價演算

st

ts∧

ts

t(s∧

t)(s

t)001010010010101100110010

表1.3.2s∧

t，s

t與(s∧

t)

(s

t)的真值表1.3命題公式的等價演算

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1.3命題公式的等價演算

1.3命題公式的等價演算（7）吸收律X∨(X∧Y)?X，X∧(X∨Y)?X（8）零律X∨1?1，X∧0?0（9）同一律X∨0?X，X∧1?X（10）否定律X∨

X?1，X∧

X?0（11）蘊涵律X

Y?

X∨Y（12）等值律X

Y?(X

Y)∧(Y

X)（13）逆反律X

Y?

Y

X（14）歸謬律(X

Y)∧(X

Y)?

X1.3命題公式的等價演算

1.3命題公式的等價演算

左邊=A

(B

A)

?A

(

B∨A)（蘊涵律）?

A∨(

B∨A)（蘊涵律）?(

A∨A)∨

B（交換律、結(jié)合律）?1∨

B（否定律）?1（零律）右邊=

A

(A

B)

?

A

(

A∨

B)（蘊涵律）?

(

A)∨(

A∨

B)（蘊涵律）?A∨(

A∨

B)（雙重否定律）?(A∨

A)∨

B（結(jié)合律）?1∨

B（否定律）?1（零律）所以A

(B

A)?

A

(A

B)1.3命題公式的等價演算

右邊=(A∨B)∧(

A

B)

?(A∨B)∧((

A

B)∧(B

A))（等值律）?(A∨B)∧((A∨B)∧(

B∨

A))（蘊涵律）?(A∨B)∧(A∨B)∧(

A∨

B)（交換律）?(A∨B)∧(

A∨

B)（冪等律）1.3命題公式的等價演算例1.3.2

證明下面命題公式等價。（2）

(A

B)?(A∨B)∧(

A

B)解（2）再從左邊開始演算：左邊=

(A

B)

?

((A

B)∧(B

A))

（等值律）?

(A

B)∨

(B

A)

（德?摩根律）?

(

A∨B)∨

(

B∨A)

（蘊涵律）?(A∧

B)∨(B∧

A)

（德?摩根律）?(A∨(B∧

A))∧(

B∨(B∧

A))

（分配律）?(A∨B)∧(A∨

A)∧(

B∨B)∧(

B∨

A)（分配律）?(A∨B)∧1∧1∧(

B∨

A)

（否定律）?(A∨B)∧(

A∨

B)（同一律、交換律）所以

(A

B)?(A∨B)∧(

A

B)。1.3命題公式的等價演算例1.3.2

證明下面命題公式等價。（3）((A∧B)

C)∧(B

(D∨C))?(B∧(D

A))

C解（3）先從左邊開始演算：左邊=((A∧B)

C)∧(B

(D∨C))

?(

(A∧B)∨C)∧(

B∨(D∨C))（蘊涵律）?(

A∨

B∨C)∧(D∨

B∨C)（德?摩根律、交換律）?(

A∨(

B∨C))∧(D∨(

B∨C))（結(jié)合律）?(

A∧D)∨(

B∨C)（分配律）右邊=(B∧(D

A))

C

?(B∧(

D∨A))

C（蘊涵律）?

(B∧(

D∨A))∨C（蘊涵律）?

B∨

(

D∨A)∨C（德?摩根律）?

B∨(D∧

A)∨C（德?摩根律）?(

A∧D)∨(

B∨C)（交換律）再從右邊開始演算：所以((A∧B)

C)∧(B

(D∨C))?(B∧(D

A))

C。1.3命題公式的等價演算

也可以從右邊開始演算：

左邊=(A∧B)

C

（蘊涵律）（結(jié)合律）（蘊涵律）（蘊涵律）右邊=A

(B

C)

（蘊涵律）（蘊涵律）（結(jié)合律）（蘊涵律）

1.3命題公式的等價演算

左邊=(A∧

B)∨(

A∧B)

（分配律）

（否定律）

（同一律）

（交換律）

（交換律）1.3命題公式的等價演算例1.3.3

化簡程序段 ifp∧qthen ifq∨rthen

X else

Y end else ifp∧rthen

Y else

X end end解從左邊程序段可知，執(zhí)行程序段X的條件為：((p∧q)∧(q∨r))∨(

(p∧q)∧

(p∧r))?(p∧(q∧(q∨r)))∨((

p∨

q)∧(

p∨

r))?(p∧q)∨(

p∨(

q∧

r))?((p∧q)∨

p)∨(

q∧

r)?((p∨

p)∧(

p∨q))∨(

q∧

r)?(1∧(

p∨q))∨(

q∧

r)?(

p∨q)∨(

q∧

r)?((

p∨q)∨

q)∧((

p∨q)∨

r)?(

p∨q∨

q)∧(

p∨q∨

r)?1∧(

p∨q∨

r)?

p∨q∨

r?

(p∧

q∧r)1.3命題公式的等價演算例1.3.3

化簡程序段 ifp∧qthen ifq∨rthen

X else

Y end else ifp∧rthen

Y else

X end end解從左邊程序段可知，執(zhí)行程序段Y

的條件為：((p∧q)∧

(q∨r))∨(

(p∧q)∧(p∧r))?(p∧q∧

q∧

r)∨((

p∨

q)∧(p∧r))?0∨((

p∨

q)∧(p∧r))?(

p∨

q)∧(p∧r)?(

p∧(p∧r))∨(

q∧(p∧r))?(

p∧p∧r)∨(

q∧p∧r)?0∨(p∧

q∧r)?p∧

q∧r因此例1.3.3的程序段可以化簡為： ifp∧

q∧rthen

Y else

X end1.3命題公式的等價演算例1.3.4

設(shè)A，B，C是任意的命題公式，請用等價演算法化簡下列命題公式并將最后結(jié)果用只含

和∨聯(lián)結(jié)詞表示。（1）

A∧

B∧(

C

A)（2）(A

(B∨

C))∧

A∧B解（1）

A∧

B∧(

C

A)

（蘊涵律）（雙重否定律）（分配律）（否定律）（同一律）1.3命題公式的等價演算例1.3.4

設(shè)A，B，C是任意的命題公式，請用等價演算法化簡下列命題公式并將最后結(jié)果用只含

和∨聯(lián)結(jié)詞表示。（1）

A∧

B∧(

C

A)（2）(A

(B∨

C))∧

A∧B解（2）(A

(B∨

C))∧

A∧B

（蘊涵律）（結(jié)合律）（吸收律）1.4命題公式的范式古代文獻中多用來表示模子、法則。

1.4.1析取范式和合取范式本節(jié)給出命題公式的兩種規(guī)范化表示方法，這種規(guī)范化的表達式能表達真值表所能提供的一切信息。定義1.4.1

單個命題變項及其否定統(tǒng)稱為文字（literals）。如果文字包含否定符號“

”，將其稱為負文字（negativeliteral），否則稱為正文字（positiveliteral）。L為文字，形如L、

L的一對字符稱為互補文字對。僅由有限個文字構(gòu)成的析取式稱作簡單析取式（初等和）。僅由有限個文字構(gòu)成的合取式稱作簡單合取式（初等積）。例如，p、

p、q、

r等均為文字，p、q為正文字，

p、

r為負文字。p、

p為互補文字對。s、

t，s∨

s、

s∨t和

s∨

t∨r、s∨

t∨

r、

s∨

t∨

r都是簡單析取式，分別由1個文字、2個文字和3個文字構(gòu)成。

s、t，s∧

s、s∧

t和s∧

t∧

r、

s∧t∧

r、

s∧

t∧

r都是簡單合取式，分別由1個文字、2個文字和3個文字構(gòu)成。注意，一個文字既是簡單合取式，又是簡單析取式。所以，如s，

t，

r既是簡單析取式又是簡單合取式。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1.4.1析取范式和合取范式設(shè)Xi是含n個文字的簡單析取式，若Xi中既含某個命題變項pj，又含它的否定式

pj，則由交換律、否定律和零律可知，Xi為永真式。反之，若Xi為永真式，則它必同時含有某個命題變項及它的否定式。否則，若將Xi中的不帶否定符的命題變項都取0值，帶否定符的命題變項都取1，此賦值為Xi的成假賦值，這與Xi是永真式相矛盾。類似地，設(shè)Xi是含n個文字的簡單合取式，若Xi中既含某個命題變項sj，又含有它的否定式

sj，則Xi為永假式。反之，若Xi為永假式，則Xi中必同時含某個命題變項及它的否定式。1.4.1析取范式和合取范式

1.4.1析取范式和合取范式例如，(

s∧t)∨(

t∧

r)、(s∧

t)∨

r是析取范式，(

s∨t)∧(

s∨

t∨

r)、(s∨

r)∧

t是合取范式。

s∧t∧

r既是由一個簡單合取式構(gòu)成的析取范式，又是由3個簡單析取式構(gòu)成的合取范式；類似情況，

s∨t∨

r既是由3個簡單合取式構(gòu)成的析取范式，又是由一個簡單析取式構(gòu)成的合取范式。析取范式和合取范式具有下述性質(zhì)。定理1.4.2

（1）一個析取范式是永假式，當(dāng)且僅當(dāng)它的每個簡單合取式都是永假式。（2）一個合取范式是永真式，當(dāng)且僅當(dāng)它的每個簡單析取式都是永真式。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1.4.1析取范式和合取范式常見命題公式中含有5個邏輯聯(lián)結(jié)詞{∧，∨，

，

，

}，如何把這些命題公式化成等價的析取范式和合取范式呢？首先，可以利用蘊涵律和等值律X

Y?

X∨YX

Y?(X

Y)∧(Y

X)消去任何命題公式中的邏輯聯(lián)結(jié)詞

和

。其次，對范式中出現(xiàn)的如下形式：

X、

(X∧Y)、

(X∨Y)，利用雙重否定律和德?摩根律，即

X?X

(X∧Y)?

X∨

Y

(X∨Y)?

X∧

Y1.4.1析取范式和合取范式再次，對析取范式中出現(xiàn)的X∧(Y∨Z)形式，和合取范式中出現(xiàn)的X∨(Y∧Z)形式，利用分配律，即X∧(Y∨Z)?(X∧Y)∨(X∧Z)X∨(Y∧Z)?(X∨Y)∧(X∨Z)由以上3步，可將任一公式化成與之等價的析取范式和合取范式。于是得到下述定理。定理1.4.3

任意命題公式都存在與之等價的析取范式和合取范式。求給定命題公式的范式的步驟如下：（1）消去邏輯聯(lián)結(jié)詞“

”“

”；（2）用雙重否定律消去雙重否定詞，用德?摩根律內(nèi)移否定詞；（3）利用分配律，即求析取范式時使用∧對∨的分配律，求合取范式時使用∨對∧的分配律。1.4.1析取范式和合取范式例1.4.1

求下面公式的析取范式和合取范式。

r

(r

s)

解

先消去蘊涵聯(lián)結(jié)詞

r

(r

s)

（消去

）（雙重否定律）（合取范式、析取范式）1.4.1析取范式和合取范式例1.4.2求下面公式的析取范式和合取范式。

(r∨s)

(r∧s)

解

先消去等值聯(lián)結(jié)詞

(r∨s)

(r∧s)

（消去

）（消去

）（分配律、德?摩根律）（冪等律、分配律）（合取范式）（∧對∨的分配律）（∧對∨的分配律）（否定律）（交換律）（析取范式）1.4.1析取范式和合取范式例1.4.3求下面公式的析取范式和合取范式。(r

s)

t

解

為了讓演算過程盡可能清晰和無誤，利用交換律使每個簡單析取式和簡單合取式中的命題變項都按照字典順序出現(xiàn)。

（1）求合取范式(r

s)

t

（消去

）（消去

）（消去

）（德?摩根律、交換律）（∨對∧的分配律）這是由3個簡單析取式構(gòu)成的合取范式。1.4.1析取范式和合取范式（2）求析取范式求析取范式與求合取范式的前兩步相同，只是在利用分配律時有所不同，因而前4步與（1）相同，接著使用∧對∨的分配律，具體如下：(r

s)

t

?(

r∨s)

t（消去

）?((

r∨s)

t)∧(t

(

r∨s))（消去

）?(

(

r∨s)∨t)∧(

t∨(

r∨s))（消去

）?((r∧

s)∨t)∧(

r∨s∨

t)（德?摩根律、交換律）?((r∧

s)∧(

r∨s∨

t))∨(t∧(

r∨s∨

t))（∧對∨的分配律）?(r∧

s∧

r)∨(r∧

s∧s)∨(r∧

s∧

t)

∨(t∧

r)∨(t∧s)∨(t∧

t)（∧對∨的分配律）?0∨0∨(r∧

s∧

t)∨(t∧

r)∨(t∧s)∨0（否定律）?(r∧

s∧

t)∨(

r∧t)∨(s∧t)（同一律、交換律）可以看出，最后一步與倒數(shù)第三步的結(jié)果都是析取范式。一般情況下，命題公式的析取范式是不唯一的。同樣，合取范式也是不唯一的。為了使命題公式的范式唯一，需進一步將簡單合取式和簡單析取式規(guī)范化。1.4.2標(biāo)準(zhǔn)析取范式和標(biāo)準(zhǔn)合取范式由于一般范式的不唯一性，機器仍然不能以此機械地作出識別和判定，因此本小節(jié)追求一種更為嚴(yán)格的范式形式——標(biāo)準(zhǔn)范式（主范式），它存在且唯一。定義1.4.4

在含有n個命題變項的簡單合取式（簡單析取式）中，若每個命題變項和它的否定式恰好出現(xiàn)一個且僅出現(xiàn)一次，而且命題變項或它的否定式按照下標(biāo)從小到大或按照字典順序排列，稱這樣的簡單合取式（簡單析取式）為極小項（極大項）。例如，r∧

s是關(guān)于r、s的極小項，

t是關(guān)于t的極小項，r∧s∧t、r∧

s∧

t、

r∧s∧

t均是關(guān)于r、s、t的極小項，但r∧

s、

t就不是關(guān)于r、s、t的極小項。又如r∨

s是關(guān)于r、s的極大項，

t是關(guān)于t的極大項，r∨s∨t、r∨

s∨

t、

r∨s∨

t均是關(guān)于r、s、t的極大項，但r∨

s、t就不是關(guān)于r、s、t的極大項。1.4.2標(biāo)準(zhǔn)析取范式和標(biāo)準(zhǔn)合取范式由于每個命題變項在極小項中以原形或否定式形式出現(xiàn)且僅出現(xiàn)一次，因而n個命題變項共可以構(gòu)成2n個不同的極小項，而且每個極小項都有且僅有一個成真賦值。利用二進制數(shù)討論極小項最方便：以mk表示極小項，其下標(biāo)k是二進制數(shù)，當(dāng)最小項中出現(xiàn)第i個命題變項時，二進制下標(biāo)k左起的第i位為1；當(dāng)極小項中出現(xiàn)第i個命題變項的否定時，二進制下標(biāo)k左起的第i位為0。例如，命題變項s，t形成的極小項

s∧t的符號是m01。同理，n個命題變項可以構(gòu)成2n個極大項：以Mk表示極大項，其下標(biāo)k是二進制數(shù)，當(dāng)極大項中出現(xiàn)第i個命題變項時，二進制下標(biāo)k左起的第i位為0；當(dāng)極大項中出現(xiàn)第i個命題變項的否定時，二進制下標(biāo)k左起的第i位為1。例如，命題變項s，t形成的極大項

s∨t的符號是M10。~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1.4.2標(biāo)準(zhǔn)析取范式和標(biāo)準(zhǔn)合取范式表1.4.1列出了含s、t的全部極小項與極大項。極小項極大項公式成真賦值符號（二進制）符號（十進制）公式成假賦值符號（二進制）符號（十進制）

s∧

t00m00m0s∨t00M00M0

s∧t01m01m1s∨

t01M01M1s∧

t10m10m2

s∨t10M10M2s∧t11m11m3

s∨

t11M11M3表1.4.1含s、t的全部極小項與極大項1.4.2標(biāo)準(zhǔn)析取范式和標(biāo)準(zhǔn)合取范式表1.4.2列出了含r、s、t的全部極小項和極大項。表1.4.2含r、s、t的全部極小項與極大項極小項極大項公式成真賦值符號（二進制）符號（十進制）公式成假賦值符號（二進制）符號（十進制）

r∧

s∧

t000m000m0r∨s∨t000M000M0

r∧

s∧t001m001m1r∨s∨

t001M001M1

r∧s∧

t010m010m2r∨

s∨t010M010M2

r∧s∧t011m011m3r∨

s∨

t011M011M3r∧

s∧

t100m100m4

r∨s∨t100M100M4r∧

s∧t101m101m5

r∨s∨

t101M101M5r∧s∧

t110m110m6

r∨

s∨t110M110M6r∧s∧t111m111m7

r∨

s∨

t111M111M71.4.2標(biāo)準(zhǔn)析取范式和標(biāo)準(zhǔn)合取范式定義1.4.5

在析取范式中，若每個簡單合取式都是極小項，且極小項按下標(biāo)遞增排序，則稱該析取范式為標(biāo)準(zhǔn)析取范式（主析取范式，principaldisjunctivenormalform）。若這個標(biāo)準(zhǔn)析取范式與命題公式X等價，則稱它為公式X的標(biāo)準(zhǔn)析取范式。定義1.4.6

在合取范式中，若每個簡單析取式都是極大項，且極大項按下標(biāo)遞增排序，則稱該合取范式為標(biāo)準(zhǔn)合取范式（主合取范式，principalconjunctivenormalform）。若這個標(biāo)準(zhǔn)合取范式與命題公式X等價，則稱它為公式X的標(biāo)準(zhǔn)合取范式。1.4.2標(biāo)準(zhǔn)析取范式和標(biāo)準(zhǔn)合取范式定理1.4.4

任意含n個命題變項的非永假式的命題公式X都存在唯一的與之等價的標(biāo)準(zhǔn)析取范式。證明

這先證明存在性。（1）先把命題公式X化成析取范式。（2）將簡單合取式中重復(fù)出現(xiàn)的命題變項、永假式及重復(fù)出現(xiàn)的極小項都“消去”，即用t代替t∧t，0代替t∧

t，mi代替mi∨mi等。（3）用同一律和否定律補進簡單合取式中未出現(xiàn)的其他變項。例如，根據(jù)t?1∧t?(s∨

s)∧t?(s∧t)∨(

s∧t)補進命題變項s，根據(jù)t?1∧1∧t?(r∨

r)∧(s∨

s)∧t?(r∨

r)∧((s∧t)∨(

s∧t))?((r∨

r)∧(s∧t))∨((r∨

r)∧(

s∧t))