命題邏輯等值演算課件(離散數(shù)學(xué))

1、第二章第二章 命題邏輯命題邏輯等值等值演算演算1l等值式等值式l范式范式合取范式合取范式析取范式析取范式l聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集 重點(diǎn)內(nèi)容：重點(diǎn)內(nèi)容： 等值演算等值演算1.范式范式l消解法消解法2等值式等值式基本等值式基本等值式等值演算和置換規(guī)則等值演算和置換規(guī)則3 定義定義1：設(shè)設(shè)A和和B是兩個(gè)命題公式，如果是兩個(gè)命題公式，如果A、B在在任意指派下，其真值都是相同任意指派下，其真值都是相同的，則稱的，則稱A和和B是等值的，或邏輯相等，是等值的，或邏輯相等，記作記作AB，稱，稱AB為等值式為等值式。p q q pp q(p q) (q p)456 定義定義2： 若若AB是重言式，則稱是重

2、言式，則稱A與與B等等值值，記作，記作AB，并稱，并稱AB是是等值式。等值式。例如，例如， (pq) ( p q) ( r r)說明：定義中，說明：定義中，A、B、均為元語均為元語言符號(hào)言符號(hào), A或或B中可能有中可能有啞元啞元出現(xiàn)。出現(xiàn)。r是啞元是啞元7 等值式的性質(zhì)：等值式的性質(zhì)：l自反性，即對(duì)任意公式自反性，即對(duì)任意公式A，有，有A A。l對(duì)稱性，即對(duì)任意公式對(duì)稱性，即對(duì)任意公式A和和B，若，若A B，則，則B A。l傳遞性，即對(duì)任意公式傳遞性，即對(duì)任意公式A、B和和C，若，若 A B、B C，則，則A C。8例例1：“除非有時(shí)間，我才去看電影。除非有時(shí)間，我才去看電影?！?上面這句話的

3、意思相當(dāng)于上面這句話的意思相當(dāng)于 “如果沒有時(shí)間，我就不去看電影。如果沒有時(shí)間，我就不去看電影?！绷睿毫睿簆：我有時(shí)間；：我有時(shí)間；q：我去看電影：我去看電影p pq q q qp p 9p q 和和 q p是等值的。是等值的。 判斷兩個(gè)公式是否為等值式的基本方法判斷兩個(gè)公式是否為等值式的基本方法是：通過兩個(gè)公式的是：通過兩個(gè)公式的真值表真值表進(jìn)行驗(yàn)證。進(jìn)行驗(yàn)證。10二、基本等值式二、基本等值式 l雙重否定律雙重否定律 : AAl冪等律冪等律： A AA, A AAl交換律交換律: A BB A, A BB Al結(jié)合律結(jié)合律: (A B) CA (B C) (A B) CA (B C)11l分

4、配律分配律: A (B C)(A B) (A C) A (B C) (A B) (A C)l德德摩根律摩根律 : (A B)AB (A B)ABl吸收律吸收律: A (A B)A, A (A B)A12l零律零律: A 1 1, A 0 0 l同一律同一律: A 0 A, A 1 Al排中律排中律: A A 1l矛盾律矛盾律: A A 0l蘊(yùn)涵等值式蘊(yùn)涵等值式: ABA B二、基本等值式二、基本等值式13l等價(jià)等值式等價(jià)等值式: AB (AB) (BA)l假言易位假言易位: AB BAl等價(jià)否定等值式等價(jià)否定等值式: AB ABl歸謬論歸謬論: (AB) (A B) A14ABA B(p q)

5、AB等值式模式等值式模式：由元語言符號(hào)表：由元語言符號(hào)表示的等值式稱作等值式模式。示的等值式稱作等值式模式。pAB(rs)ABr (p q) rqp q( s) (rs) ( s)代代入入實(shí)實(shí)例例每一個(gè)等值模式都可以每一個(gè)等值模式都可以對(duì)應(yīng)于無窮多個(gè)同類型對(duì)應(yīng)于無窮多個(gè)同類型的具體等值式。的具體等值式。15 等值演算等值演算: 由已知的等值式推演出新的等由已知的等值式推演出新的等值式的值式的過程過程。例：由基本等值式可知例：由基本等值式可知pqp q 所以：當(dāng)用所以：當(dāng)用 p q替換替換pq時(shí)，時(shí)，r)qp(r)qp( 公式公式A公式公式B)A( )B( 16 置換規(guī)則：置換規(guī)則：設(shè)設(shè) (A)

6、是含有公式是含有公式A的命題的命題公式，用公式公式，用公式B置換置換 (A)中所有的中所有的A后得后得到新的命題公式到新的命題公式 (B)，若若AB, 則則 (B)(A) 。17 等值演算的基礎(chǔ)：等值演算的基礎(chǔ)： (1) 等值關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞等值關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞 (2) 基本的等值式基本的等值式 (3) 置換規(guī)則置換規(guī)則 18例例2 ：證明證明p pq qp pq qp p )()(p pp pq qq qp pq qp pq qp p 1)()()(證證：19例例3： 證明證明 p(qr) (p q)r證：證： p(qr) p ( q r) （蘊(yùn)涵等值式，置換規(guī)則）（

7、蘊(yùn)涵等值式，置換規(guī)則） ( pq) r （結(jié)合律，置換規(guī)則）（結(jié)合律，置換規(guī)則） (p q) r （德摩根律，置換規(guī)則）（德摩根律，置換規(guī)則） (p q) r （蘊(yùn)涵等值式，置換規(guī)則）（蘊(yùn)涵等值式，置換規(guī)則） q (p r)20 例例4: : 和和 滿足滿足等值關(guān)系嗎？等值關(guān)系嗎？)(r rq qp p)()(r rp pq qp pr rq qp pr rq qp pr rq qp pr rq qp p )()()(21r rq qp pr rp pq qp pp pr rp pq qp pr rp pq qp pr rp pq qp pr rp pq qp p )()()()()()()(

8、)()(蘊(yùn)涵等值律蘊(yùn)涵等值律蘊(yùn)涵等值律蘊(yùn)涵等值律德德.摩根律摩根律分配律分配律排中律、同一律、排中律、同一律、交換律交換律r rq qp pr rp pq qp pr rq qp p )()()()(22 例例5：通過等值演算判斷下面三個(gè)公式之間的：通過等值演算判斷下面三個(gè)公式之間的關(guān)系關(guān)系)(q qp p q qp p q qp p )()()()(pqqppqqpqp )()()()(qpqppqqpqp 23)()()()()()()()()()()()()()()()()(pqqppqppqqqppqpqqppqqppqqppqqppqqpqp )(q qp p q qp p q qp

9、 p 24l雙重否定律雙重否定律 : AAB BA AB BA AB BA A )(l德德摩根律摩根律 : (A B)AB (A B)AB否定律否定律25l冪等律冪等律： A AA, A AAl排中律排中律: A A 1l矛盾律矛盾律: A A 0A AA AA AA AA AA A ，11A AA AA AA A，冪等律冪等律26l分配律分配律: A (B C)(A B) (A C) l A (B C) (A B) (A C)()()(C CA AB BA AC CB BA A分配律分配律27 例例6：某勘探隊(duì)有：某勘探隊(duì)有3名隊(duì)員，有一天取得一塊礦樣，名隊(duì)員，有一天取得一塊礦樣，3人的判斷

10、如下：人的判斷如下： 甲說：這不是鐵，也不是銅； 乙說：這不是鐵，是錫； 丙說：這不是錫，是鐵。 經(jīng)實(shí)驗(yàn)室鑒定后發(fā)現(xiàn)，其中有一個(gè)人的判斷完全經(jīng)實(shí)驗(yàn)室鑒定后發(fā)現(xiàn)，其中有一個(gè)人的判斷完全正確，有一個(gè)人只對(duì)了一半，另一個(gè)人全錯(cuò)了。根據(jù)正確，有一個(gè)人只對(duì)了一半，另一個(gè)人全錯(cuò)了。根據(jù)這樣的情況判斷礦樣是什么類型？這樣的情況判斷礦樣是什么類型？28解：令解：令p：礦樣為鐵：礦樣為鐵 q：礦樣為銅：礦樣為銅 r：礦樣為錫：礦樣為錫000)rprpqp()rprpqp()rp()rp()rp(qp)(1 ）（丙丙全全錯(cuò)錯(cuò)）（乙乙對(duì)對(duì)一一半半）甲甲全全對(duì)對(duì)F290)rp()rp()rp(qp)(2 ）（丙丙對(duì)對(duì)

11、一一半半）（乙乙全全錯(cuò)錯(cuò)）甲甲全全對(duì)對(duì)FrqpF （丙全對(duì)）（丙全對(duì)）（乙全錯(cuò)）（乙全錯(cuò)）甲對(duì)一半甲對(duì)一半)(3rqpF （丙丙全全錯(cuò)錯(cuò)）（乙乙全全對(duì)對(duì)）甲甲對(duì)對(duì)一一半半)(4300)(5 （丙丙全全對(duì)對(duì)）（乙乙對(duì)對(duì)一一半半）甲甲全全錯(cuò)錯(cuò)F0)(6 （丙對(duì)一半）（丙對(duì)一半）（乙全對(duì)）（乙全對(duì)）甲全錯(cuò)甲全錯(cuò)F)rqp()rqp(FFFFFF)(654321 （一一人人對(duì)對(duì)一一半半）（一一人人全全對(duì)對(duì)）一一人人全全錯(cuò)錯(cuò)F31因?yàn)榈V樣不可能既是銅又是錫，因?yàn)榈V樣不可能既是銅又是錫，即即q 和和r不可能同時(shí)取得真值不可能同時(shí)取得真值1，所以所以只有只有即即q和和r為假命題，為假命題，p為真命題，礦樣為鐵為真命題，礦樣為鐵0 rqp1 rqp32(1) q(pq) 解：解：q(pq) q( p q) q (pq) 例例7： 用等值演算法判斷下列公式的類型用等值演算法判斷下列公式的類型 p (qq) p 0 0 由最后一步可知，該式為矛盾式由最后一步可知，該式為矛盾式。33解解 : (pq)( qp) ( p q)(qp) ( p q)( p q) 1 該式為重言式。該式為重言式。(2) (pq)( qp) (3) (p q) (pq) r)解：解：(p q) (pq) r) (p (qq) r p 1 r p