第一章-命题逻辑5.pptx

数理逻辑
马殿富
北航计算机学院
******@buaa.
2012-9
第5节联结词的完全集
联结词的完全集
例:p→q p∨q
pq(p→q)∧(q→p)(p∨q)∧(p∨q)
pq (p∧q)∨(p∧q)
结论:
,,,,,不是相互独立的
问题:
命题逻辑的最少联结词集是什么?
完全集
:设F是n元联结词,p1, p2, …, pn是不同的命题变元。如果公式A中不出现除p1, p2, …, pn之外的命题变元,并且A  Fp1, p2, …, pn,则称A定义F。
如果存在由联结词集合S生成的公式来定义F,则称F可由S定义。如:S = {, , }
p→q = pq
pq = (p→q)(q→p) = (pq)(pq)
pq = (pq)(pq)
真值表的启示
(p/0,q/1), (p/1,q/0) F7pq=pqpq
(p/0,q/1) ,(p/1,q/1) F11pq=pqpq
(p/0,q/1) , (p/1,q/0), (p/1,q/1) F15pq=pqpqpq
对每个n(n1)元真值函数F,都可以找到一个由{,,}生成的公式来定义。
p
q
F1
F2
F3
F4
F5
F6
F7
F8
F9
F10
F11
F12
F13
F14
F15
F16
0
0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1

设S是联结词集合。如果每个n(n>0)元的联结词都可由S定义,则称S为完全集。
完全集定理
完全集定理
定理⒈7:如果完全集S1中的每个联结词都可由联结词集合S2定义,则S2也是完全集。
证明:设n1,F是n元联结词,由S1生成的公式A来定义F. 以下递归地确定由S2生成的公式A*来定义F:
若A是命题变元p,则A*也是p
若A是F’A1,…,Am,其中F’是S1中的m元联结词,根据条件,则有S2生成的公式B定义F’:
BF’p1,…,pm
完全集导出定理
极小完全集
定义:如果从完全集S中去掉任何一个联结词就成为不完全的了,就称S为极小完全集。