第一章-命題邏輯5

1、數(shù)理邏輯馬殿富馬殿富北航計算機學院北航計算機學院202012-912-9第第5 5節(jié)節(jié) 聯(lián)結(jié)詞的完全集聯(lián)結(jié)詞的完全集 計算機學院2計算機學院21.5 1.5 聯(lián)結(jié)詞的完全集聯(lián)結(jié)詞的完全集 例：例：pqpq p pq q p pq q( (pqpq) )( (qpqp) )( (p pq q) )(p(pq) q) p pq q (p (pq) q) ( (p pq q) ) 結(jié)論：結(jié)論： ，不是不是相互相互獨立的獨立的問題：問題： 命題邏輯的最少命題邏輯的最少聯(lián)結(jié)聯(lián)結(jié)詞集是什么？詞集是什么？計算機學院3計算機學院3完全集完全集 定義定義1.121.12：設(shè)：設(shè)F是是n n元聯(lián)結(jié)詞，元聯(lián)結(jié)詞，p

2、 p1 1, p, p2 2, , , , p pn n是不同是不同的命題變元。如果公式的命題變元。如果公式A A中不出現(xiàn)除中不出現(xiàn)除p p1 1, p, p2 2, , , , p pn n之外的命題變元，并且之外的命題變元，并且A A Fp p1 1, p, p2 2, , , , p pn n，則稱，則稱A A定義定義F。 如果存在由聯(lián)結(jié)詞集合如果存在由聯(lián)結(jié)詞集合S S生成的公式來定義生成的公式來定義F，則，則稱稱F可由可由S S定義定義。如：。如：S = S = , , pqpq = = p pq q p pq = (q = (pqpq) )( (qpqp) = () = (p pq)

3、 q)(p(pq) q) p pq = (pq = (pq) q)( (p pq) q)計算機學院4計算機學院4真值表的啟示真值表的啟示 (p/0,q/1), (p/1,q/0) F7 7p pq=q= p p q q p pq q (p/0,q/1) ,(p/1,q/1) F1111pq=pq= p p q q p p q q (p/0,q/1) , (p/1,q/0), (p/1,q/1) F1515pq=pq= p p q q p pq q p p q q對每個對每個n n（n n 1 1）元真值函數(shù)）元真值函數(shù)F F，都可以找到一個由，都可以找到一個由 , , , , 生成的公式來定義

4、。生成的公式來定義。pqF1F2F3F4F5F6F7F8F9F10F11F12F13F14F15F16000101010101010101010011001100110011100000111100001111110000000011111111計算機學院5計算機學院5定義定義1.131.13完全集完全集 設(shè)設(shè)S S是聯(lián)結(jié)詞集合。如果每個是聯(lián)結(jié)詞集合。如果每個n(n0)n(n0)元的聯(lián)結(jié)元的聯(lián)結(jié)詞都可由詞都可由S S定義，則稱定義，則稱S S為為完全集完全集。計算機學院6計算機學院6完全集定理完全集定理計算機學院7計算機學院7完全集定理完全集定理計算機學院8計算機學院8 定理定理：如果完全集：

5、如果完全集S S1 1中的每個聯(lián)結(jié)詞都可由聯(lián)中的每個聯(lián)結(jié)詞都可由聯(lián)結(jié)詞集合結(jié)詞集合S S2 2定義，則定義，則S S2 2也是完全集。也是完全集。 證明：設(shè)證明：設(shè)n 1，F(xiàn)是是n元聯(lián)結(jié)詞，由元聯(lián)結(jié)詞，由S1生成的公式生成的公式A來來定義定義F. 以下遞歸地確定由以下遞歸地確定由S2生成的公式生成的公式A*來定義來定義F： 若若A是命題變元是命題變元p，則，則A*也是也是p 若若A是是FA1,Am，其中，其中F是是S1中的中的m元聯(lián)結(jié)詞，元聯(lián)結(jié)詞，根據(jù)條件，則有根據(jù)條件，則有S2生成的公式生成的公式B定義定義F： BFp1,pm完全集完全集導出導出定理定理計算機學院9計算機學院9計算機學院10

6、計算機學院10極小完全集極小完全集 定義：定義：如果從完全集如果從完全集S S中去掉任何一個聯(lián)結(jié)中去掉任何一個聯(lián)結(jié)詞就成為不完全的了，就稱詞就成為不完全的了，就稱S S為為極小完全集極小完全集。計算機學院11計算機學院11極小完全集定理極小完全集定理 定理定理以下聯(lián)結(jié)詞集合是極小完全集。以下聯(lián)結(jié)詞集合是極小完全集。 , ， , ， , 證明：（先證明是完全集，證明：（先證明是完全集，再再證明缺一不可）證明缺一不可） p pq q ( (p pq) q)，所以，所以可由可由 , , 定義。定義。 因此因此 , , , ,都可由都可由 , , 定義。由于定義。由于 , , , , 是完全集，所以是

7、完全集，所以 , , 也是完全集。也是完全集。計算機學院12計算機學院12 接下來證明接下來證明 , , 是極小完全集。是極小完全集。首先證明首先證明 不是完全集。不是完全集。 任取由任取由生成的公式生成的公式A A，其中，其中A A不出現(xiàn)除不出現(xiàn)除p p之之外的命題變元，其公式模式：外的命題變元，其公式模式： p pp pp p 令真值賦值令真值賦值v=(p/1)v=(p/1)，則，則v(A)=1v(A)=1，但，但v( v(p)=0p)=0，所以所以A A不能定義不能定義。 結(jié)論結(jié)論: :不能由不能由定義。定義。計算機學院13計算機學院13 再證明再證明 不是完全集。不是完全集。 取一元聯(lián)

8、結(jié)詞取一元聯(lián)結(jié)詞F使使F(0)=(0)=F(1)(1)。 令真值賦值令真值賦值v v1 1=(p/1)=(p/1)和和v v2 2=(p/0)=(p/0)， 任取由任取由 生成只出現(xiàn)命題變元生成只出現(xiàn)命題變元p p的公式的公式A A， 公式公式: :p 則則v v1 1(A)v(A)v2 2(A)(A)，而，而v v1 1( (Fp p)=v)=v2 2( (Fp p) )，所以，所以A A不能定義不能定義F。 F不能由不能由 定義。定義。 不是完全集。不是完全集。計算機學院14計算機學院14 , , 是完全集是完全集 因為因為p pq q= =( (p pq)=q)=(p(pq) q)，所以，所以可由可由 , , 定義。定義。 , , 都可由都可由 , , 定義，并且定義，并且 , , 是完是完全集，所以全集，所以 , , 也是完全集。也是完全集。計算機學院15計算機學院15 證明證明 不是完全集。不是完全集。 取真值賦值取真值賦值v=(p/1)v=(p/1)。 任取由任取由 生成的僅出現(xiàn)命題變元生成的僅出現(xiàn)命題變元p p的公的公式式A A，v(A)=1v(A)=1，而，而v( v(p)=0p)=0，A A不能定義不能定義。 不是完全集。不是完全集。 也不是完全集。也不是完全集。 結(jié)論：結(jié)論： , , 是極小完