第一章命题逻辑§1.5联结词的完全集
定义1.12设F是n元联结词,p,…,p是不同的
§1.1命题和联结词1n
命题变元。如果公式A中不出现除p,…,p之外
§1.2公式和真值赋值1n
的命题变元,并且A⇔Fp…p,则称A定义
1n
§1.3等值演算F。如果存在由联结词集合S生成的公式定义F,
§1.4对偶定理则称F可由S定义。
§1.5联结词的完全集公式¬p∨p不定义0元联结词1,因为定义0元
§1.6范式联结词的公式中不能出现命题变元。若联结词集合
§1.7逻辑推论S能够定义一个0元联结词,则S中至少有一个0
元联结词。
在数学中可定义二元函数公式p→q,¬p∨q,¬(p∧¬q)都定义联结词→。
f(x,y)=x+y,g(x,y)=x,因为
但不能定义二元函数p→q⇔¬p∨q
f(x,x)=x,h(x,y)=x+y+z。p↔q⇔(p∧q)∨(¬p∧¬q)
二元函数的两个变元应是不同变元,定义函数值的p⊕q⇔(p∧¬q)∨(¬p∧q)
公式中不能出现其它变元。所以常用联结词¬,∨,∧,→,↔,⊕都可由{¬,∨,∧}
平方函数f(x)=x2=x×x,因此f可由{×}定义。定义。
显然,若联结词F可由S定义且S⊆S,则F可
112
由S定义。联结词F可由{F}定义。
2
证明↔不能由{→}定义。定义1.13设S是联结词集合。如果每个n(n≥1)
证明用反证法。给定两个真值赋值v={p/1,q/0}元的联结词都可由S定义,则称S为完全集。如果
1
从完全集S中去掉任何一个联结词就成为不完全的
和v={p/0,q/1}。假设↔能由{→}定义,设定
2了,就称S为极小完全集。
义↔的由{→}生成的公式是A,则A中最后出现
完全集也称为全功能集。
的命题变元是p或者q。
需要注意:并不要求完全集能定义0元联结词。
1.若A中最后出现的命题变元是p,则v(A)=1,
1
而v(p↔q)=0,所以A与p↔q不等值。极小完全集是完全集,其真子集都不是完全集。
1
若S是完全集且S⊆S,则S也是完全集。
2.若A中最后出现的命题变元是q,则v(A)=1,1122
2
而v(p↔q)=0,所以A与p↔q不等值。显然,空集∅不是完全集。最少有几个联结词就
2
这与p↔q⇔A矛盾。可以构成完全集呢?一个就够了。
1
对于每个n(n≥1)元的联结词,由它的真值表可以找到一个由定理1.6{¬,∨,∧}是完全集。
生成的公式定义它。设二元联结词的真值表如下。
{¬,∨,∧}F证明任取n元联结词F,其中n≥1。我们找出定
pqF(p,q)义F的由{¬,∨,∧}生成的公式A。设p,…,p是
1n
001不同的命题变元。
011若Fp…p是永假式,则取A为p∧¬p。
1n11
101若Fp…p是可满足式,满足它的真值赋值为
1n
110(p/a1,L,p/a1),L,(p/am,L,p/am)
11nn11nn
~~~~
则取A为(p1∧L∧p1)∨L∨(pm∧L∧pm)
满足Fpq的真值赋值有三个,它们是1n1n
其中
(p/0,q/0),(p/0,q/1),(p/1,q/0)~⎧p若ai=1
pi=⎨jj
Fpq⇔(¬p∧¬q)∨(¬p∧q)∨(p∧¬q)j¬p若ai=0
⎩jj
或者Fpq⇔(¬p∨¬q)
任取真值赋值v,首先证明
定理1.7如果完全集S中的每个联结词都可由联结
~1
v(pi)=1当且仅当v(p)=aij=1,L,n
jjj词集合S定义,则S也是完全集。
~22
当ai=1时,pi为p,成立。证明设,是元联结词,…是不同
jjjn≥1Fnp,,p
~1n
当ai=0时,pi为¬p,成立。的命题变元,由S生成的公式A定义F,因此,
jjj1
~~~~A中不出现除了p,…,p之外的命题变元,并且
v((p1∧L∧p1)∨L∨(pm∧L∧pm))=11n
1n1n
~~A⇔Fp…p。我们证明存在由S生成的公式A*
当且仅当有1≤i≤m使得v((pi∧L∧pi))=11n2
1n
~~定义F,即A*中不出现除了p,…,p之外的命题变
当且仅当有1≤i≤m使得v(pi)=L=v(pi)=11n
1n元,并且A*⇔Fp…p。所以,A*⇔A。对于A
1n
当且仅当有1≤i≤m使得v=(p/ai,L,p/ai)
11nn中联结词的出现次数进行归纳,证明:可以通过等
当且仅当v(FpLp)=1值演算将A化为只出现S中联结词的公式A*。
1n2
所以,FpLp⇔A。{¬,∧,∨}是完全集。
1n
1.若A中联结词的出现次数是0,即A是命题变
因为每个A*都是由S生成的公式,并且B也是由
元p,则取A*为A即可。i2
i
S生成的公式,所以A*是由S生成的公式。因
2.若A是F′A…A,其中F′∈S。存在由S生22
1m12为B中不出现除了p,…,p之外的命题变元,每
成的公式B定义F′,即B⇔F′p…p,其中1m
1m
p,…,p是不同的命题变元,并且B中不出现个A*中不出现除了p,…,p之外的命题变元,所
1mi1n
除了p,…,p之外的命题变元。A中联结词的以A*中不出现除了p,…,p之外的命题变元。
1m1n
出现次数=A中联结词的出现次数+…+A中因此,由生成的公式*定义。由的任意性
1mSAFF
联结词的出现次数+1,所以每个A中联结词2
i知道,S是完全集。
的出现次数<A中联结词的出现次数。由归纳2
假设知道,对于每个A,存在A*⇔A。
iii
*p,,p***
令A=B1Lm,则A⇔F′ALA⇔F′ALA⇔A
A*,,A*1m1m
1Lm
2
要证明一个联结词集合是完全集比较容易,只需写定理1.8以下联结词集合是极小完全集。
出适当的等值式就可以了。而要证明一个联结词集1.{¬,∧},
合是极小完全集,除了需要证明它是完全集之外,2.{¬,∨},
还需要证明其中的每个联结词都不能由其它联结词3.{¬,→}。
定义。证明一个联结词不能由一个联结词集合定证明
义,比证明它能由一个联结词集合定义要困难得
1.因为
多。要证明由联结词集合S不能定义n元联结词
p∨q⇔¬¬(p∨q)⇔¬(¬p∧¬q)
F,只需找出一个满足以下条件的公式的语义性
所以可由{¬,∧}定义∨,又{¬,∧,∨}是完全集,
质:
所以也是完全集。需要证明和都
1.由S生成的公式都有该性质,{¬,∧}{¬}{∧}
2.公式Fp…p没有这个性质。不是完全集。
1n
首先证明{∧}不是完全集。再证明{¬}不是完全集。
设真值赋值v=(p/1)。我们归纳证明:对于每个由设一元联结词F使得F(0)=F(1)=1。我们证明{¬}
不能定义F。令真值赋值v=(p/1)和v=(p/0)。
{∧}生成的不出现除p之外命题变元的公式A,12
我们归纳证明:对于每个由{¬}生成的不出现除p
v(A)=1。
之外命题变元的公式A,v(A)≠v(A)。
12
①若A是p,则v(A)=1。①若A是p,则v(A)≠v(A)。
12
②若A是B∧C,由归纳假设知道,v(B)=1且②若A是¬B,由归纳假设知道,v(B)≠v(B),
12
所以v(A)≠v(A)。
v(C)=1,所以v(A)=1。12
若由{}生成的不出现除p之外命题变元的公式A
若由{∧}生成的不出现除p之外命题变元的公式A¬
定义F,则Fp⇔A,v(A)=v(Fp)=v(Fp)=v(A),
定义¬,则¬p⇔A,但是v(¬p)=0且v(A)=1,1122
矛盾。{¬}不能定义F,{¬}不是完全集。
矛盾。因此,不能定义,不是完全集。
{∧}¬{∧}因此,{¬,∧}是极小完全集。
2.因为p∧q⇔¬¬(p∧q)⇔¬(¬p∨¬q)例1.10证明{⊕,↔}不是完全集。
可由{¬,∨}定义∧,又{¬,∧}是完全集,所以证明设真值赋值v=(p/0,q/0),v=(p/0,q/1),
12
{¬,∨}也是完全集。需要证明{¬}和{∨}都不是完全v=(p/1,q/0),v=(p/1,q/1)。当A为p⊕q或者
集。前面已证不是完全集。采用证明不34
{¬}{∧}p↔q时,v(A),v(A),v(A),v(A)中有2个1。
是完全集的同样方法可以证明{∨}不是完全集。1234
我们归纳证明:对于每个由{⊕,↔}生成的不出现
3.因为p∨q⇔¬¬p∨q⇔¬p→q
除p,q之外命题变元的公式A,v(A),v(A),v(A),
¬和∨都可由{¬,→}定义,并且{¬,∨}是完全123
v(A)中有偶数个1。
集,所以{¬,→}也是完全集。需要证明{¬}和{→}4
1.若A是p或q,则v(A),v(A),v(A),v(A)中有
都不是完全集。前面已证{¬}不是完全集。采用1234
2个1。
证明{∧}不是完全集的同样方法可以证明{→}不
2.设A是B⊕C,v(B),v(B),v(B),v(B)中有偶
是完全集。1234
数个1,v(C),v(C),v(C),v(C)中有偶数个1。
1234
3
④设v(B),v(B),v(B),v(B)中有2个1,并且
①若v(B),v(B),v(B),v(B)全为0,v(C),v(C),1234
123412v(C),v(C),v(C),v(C)中有2个1。
v(C),v(C)中有m个1,则v(A),v(A),v(A),1234
34123I.使得B为真的真值赋值与使得C为真的真值赋
v(A)中也有m个1。
4值完全相同,这时v(A),v(A),v(A),v(A)全为
1234
②若v(B),v(B),v(B),v(B)全为1,v(C),v(C),0。
123412
v(C),v(C)中有m个1,则v(A),v(A),v(A),没有使得和全都是真的真值赋值,这时
34123II.BC
v(A)中有4−m个1。4−m是偶数。v(A),v(A),v(A),v(A)全为1。
41234
③对于v(C),v(C),v(C),v(C)全为0或全为1的III.v,v,v,v中有一个使得B和C都为真,有一
12341234
情况可同样讨论。个使得B和C都为假,有一个使得B真且C
假,有一个使得B假且C真。因为⊕的真值
表的最后一列有2个1。所以这时v(A),v(A),
12
v(A),v(A)中有2个1。
34
3.若A是B↔C,同样可证明v(A),v(A),v(A),设S是二元联结词的集合。如果下列三个条件之一
123
v(A)中有偶数个1。
4成立,则S不是完全集。
令D为p∨q,则v(D),v(D),v(D),v(D)中有3
12341.对于任意⊗∈S,1⊗1=1。(由S不能定义¬)
个,所以与任何由生成的不出现除
1D{⊕,↔}p,q2.对于任意⊗∈S,0⊗0=0。(由S不能定义¬)
之外命题变元的公式都不等值,由{⊕,↔}不能定
3.对于任意⊗∈S,0⊗0,0⊗1,1⊗0,1⊗1这4
义,所以不是完全集。
∨{⊕,↔}个值中有偶数个1。(由S不能定义∨)
在上述证明过程中,只用到了⊕和↔的真值表的
常用这三个性质证明一个联结词集合不是完全集。
最后一列有偶数个1。
由定理1.8看出,完全集可以只包括2个联结词,那练****书上27面
么是否存在一个联结词其构成完全集?1.21(2)
答案肯定的,具体见作业22
4
课程回顾
2个定义:作业:
定义1.12:公式A定义连接词F,连接词F可由连19,20(1),(2),(3),22
接词集合S定义
定义1.13完全集和极小完全集
3个定理:
定理1.6、1.7和1.8
5
