第一章-命题逻辑5

1、数理逻辑马殿富马殿富北航计算机学院北航计算机学院202012-912-9第第5 5节节 联结词的完全集联结词的完全集 计算机学院2计算机学院21.5 1.5 联结词的完全集联结词的完全集 例：例：pqpq p pq q p pq q( (pqpq) )( (qpqp) )( (p pq q) )(p(pq) q) p pq q (p (pq) q) ( (p pq q) ) 结论：结论： ，不是不是相互相互独立的独立的问题：问题： 命题逻辑的最少命题逻辑的最少联结联结词集是什么？词集是什么？计算机学院3计算机学院3完全集完全集 定义定义1.121.12：设：设F是是n n元联结词，元联结词，p

2、 p1 1, p, p2 2, , , , p pn n是不同是不同的命题变元。如果公式的命题变元。如果公式A A中不出现除中不出现除p p1 1, p, p2 2, , , , p pn n之外的命题变元，并且之外的命题变元，并且A A Fp p1 1, p, p2 2, , , , p pn n，则称，则称A A定义定义F。 如果存在由联结词集合如果存在由联结词集合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）元真值函数）元真值函数F F，都可以找到一个由，都可以找到一个由 , , , , 生成的公式来定义

4、。生成的公式来定义。pqF1F2F3F4F5F6F7F8F9F10F11F12F13F14F15F16000101010101010101010011001100110011100000111100001111110000000011111111计算机学院5计算机学院5定义定义1.131.13完全集完全集 设设S S是联结词集合。如果每个是联结词集合。如果每个n(n0)n(n0)元的联结元的联结词都可由词都可由S S定义，则称定义，则称S S为为完全集完全集。计算机学院6计算机学院6完全集定理完全集定理计算机学院7计算机学院7完全集定理完全集定理计算机学院8计算机学院8 定理定理：如果完全集：

5、如果完全集S S1 1中的每个联结词都可由联中的每个联结词都可由联结词集合结词集合S S2 2定义，则定义，则S S2 2也是完全集。也是完全集。 证明：设证明：设n 1，F是是n元联结词，由元联结词，由S1生成的公式生成的公式A来来定义定义F. 以下递归地确定由以下递归地确定由S2生成的公式生成的公式A*来定义来定义F： 若若A是命题变元是命题变元p，则，则A*也是也是p 若若A是是FA1,Am，其中，其中F是是S1中的中的m元联结词，元联结词，根据条件，则有根据条件，则有S2生成的公式生成的公式B定义定义F： BFp1,pm完全集完全集导出导出定理定理计算机学院9计算机学院9计算机学院10

6、计算机学院10极小完全集极小完全集 定义：定义：如果从完全集如果从完全集S S中去掉任何一个联结中去掉任何一个联结词就成为不完全的了，就称词就成为不完全的了，就称S S为为极小完全集极小完全集。计算机学院11计算机学院11极小完全集定理极小完全集定理 定理定理以下联结词集合是极小完全集。以下联结词集合是极小完全集。 , ， , ， , 证明：（先证明是完全集，证明：（先证明是完全集，再再证明缺一不可）证明缺一不可） p pq q ( (p pq) q)，所以，所以可由可由 , , 定义。定义。 因此因此 , , , ,都可由都可由 , , 定义。由于定义。由于 , , , , 是完全集，所以是

7、完全集，所以 , , 也是完全集。也是完全集。计算机学院12计算机学院12 接下来证明接下来证明 , , 是极小完全集。是极小完全集。首先证明首先证明 不是完全集。不是完全集。 任取由任取由生成的公式生成的公式A A，其中，其中A A不出现除不出现除p p之之外的命题变元，其公式模式：外的命题变元，其公式模式： p pp pp p 令真值赋值令真值赋值v=(p/1)v=(p/1)，则，则v(A)=1v(A)=1，但，但v( v(p)=0p)=0，所以所以A A不能定义不能定义。 结论结论: :不能由不能由定义。定义。计算机学院13计算机学院13 再证明再证明 不是完全集。不是完全集。 取一元联

8、结词取一元联结词F使使F(0)=(0)=F(1)(1)。 令真值赋值令真值赋值v v1 1=(p/1)=(p/1)和和v v2 2=(p/0)=(p/0)， 任取由任取由 生成只出现命题变元生成只出现命题变元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)。 任取由任取由 生成的仅出现命题变元生成的仅出现命题变元p p的公的公式式A A，v(A)=1v(A)=1，而，而v( v(p)=0p)=0，A A不能定义不能定义。 不是完全集。不是完全集。 也不是完全集。也不是完全集。 结论：结论： , , 是极小完