2.3 联结词的完备集

联结词的完‎备集
1.命题公式与‎真值函数的‎关系
含n个变元‎的命题公式‎可以视为一‎个n-元真值函数‎F:{0,1}n→{0,1}。

反之任何n‎-元真值函数‎都可以表示‎为一个含n‎个变元的命‎题公式。

问：用什么方法‎得到这样的‎命题公式？
答：根据真值表‎构造主析取‎范式。

例1.1 为下列真值‎函数F构造‎命题公式表‎示。

2.联接词的完‎备集
动机：一个有趣的‎问题是，用尽可能少‎的几种联结‎词所构造出‎的命题公式‎能否表示所‎有的真值函‎数？
定义2.1设S是一个‎联结词集合‎。

若由S中联‎结词所构造‎的命题公式‎可以表示所‎有真值函数‎，则称S是联‎结词的完备‎集。

定理2.2{,,}
⌝∧∨是联结词完‎备集。

证明
证毕
推论2.3 以下集合都‎是联结词完‎备集：
1）{,}
⌝∧
2）{,}
⌝∨
3）{,}
⌝→
证明
证毕定义2.4（1）与非联结词‎↑（2）或非联结词‎↓
定理2.5 {↑}与{↓}都是联结词‎完备集。

证明
证毕。

2.3 联结词的完备集一. n 元真值函数的个数*n 个命题变项p 1, p 2, …, p n , 每个p i 可取p i 或┐p i 形式, 共有2n 个极小项(极大项), 在主析取范式中, 每个极小项可以存在或不存在, 共有n22种组合方式, 每一种组合方式代表一种不同的主析取范式, 故共有n22种不同的主析取范式(主合取范式也类似).定义2.5: 称F: {0, 1}n →{0, 1}为n 元真值函数.*F 的自变量为n 个命题变项, 定义域{0, 1}n ={(0,0,…,0), (0,0,…,1), …, (1,1,…,1)}. n 个命题变项共可构成n 22个不同的真值函数. 例如: 1元真值函数有122= 4个, 如下表, 2元真值函数共有222= 16个(见下表), 3元真值函数共有322= 256个. 表1: 1元真值函数 p )1(0F )1(1F )1(2F )1(3F0 0 0 1 11 0 1 0 1表2: 2元真值函数p q )2(0F )2(1F )2(2F )2(3F )2(4F )2(5F )2(6F )2(7F 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1p q )2(8F )2(9F )2(10F )2(11F )2(12F )2(13F )2(14F )2(15F 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1*每个真值函数与唯一的一个主析取范式等值.例如: ⇔)2(0F 0 (矛盾式), )2(1F ⇔ (p ∧q) ⇔ m 3)2(3F ⇔(p ∧┐q)∨(p ∧q)⇔m 2∨m 3 ,)2(13F ⇔(┐p ∧┐q)∨(┐p ∧q)∨(p ∧q)⇔m 0∨m 1∨m 3*每个主析取范式对应无穷多个等值的命题公式, 每一个命题公式又都对应唯一的等值的主析取范式. 所以, 每一个真值函数对应无穷多个等值的命题公式, 每一个命题公式又都对应唯一的等值的真值函数.定义2.6: 设S 是一个联结词的集合, 如果任何n (n ≥ 1)元真值函数都可以由仅含S 中的联结词构成的公式表示, 则称S 是联结词完备集.定理2.4: S = {┐,∧,∨}是联结词完备集.证明: 因为任何n(n ≥ 1)元真值函数都与唯一的主析取范式等值, 而在主析取范式中, 仅含联结词┐,∧,∨, 所以S = {┐,∧,∨}是联结词完备集.推论: 以下联结词集都是联结词完备集:(1) S1 = {┐,∧,∨,→}(2) S2 = {┐,∧,∨,→,↔}(3) S3 = {┐,∧}(4) S4 = {┐,∨}(5) S5 = {┐,→}证明: (1)和(2)是显然的.(3) 由于S = {┐,∧,∨}是联结词完备集, 因而只需证∨可用┐和∧表示. 事实上, p∨q⇔┐┐(p∨q)⇔┐(┐p∧┐q), 所以S3是联结词完备集.(4) 留作练习.(5) 已知S4 = {┐,∨}是联结词完备集, 只需证∨可用┐和→表示即可. 因为有p∨q⇔┐┐p∨q⇔┐p→q, 故S5 = {┐,→}是联结词完备集.*举例说明.*可以证明: 恒取0值的真值函数不能用仅含∧,∨,→,↔的公式表示, 因而{∧,∨,→,↔}不是联结词完备集, 进而它的任何子集都不是联结词完备集.*在计算机硬件设计中, 用与非门或用或非门设计逻辑线路. 这是两种新的联结词, 并且它们各自能构成联结词完备集.定义2.7: 设p,q是两个命题, 复合命题“p与q的否定式”称作p,q的与非式, 记作p↑q. 即p↑q⇔┐(p∧q). 符号↑称作与非联结词.复合命题“p或q的否定式”称作p,q的或非式, 记作p↓q . 即p↓q⇔┐(p∨q). 符号↓称作或非联结词.*p↑q为真当且仅当p与q不同时为真, p↓q为真当且仅当p 与q同时为真.定理2.5: {↑}, {↓}都是联结词完备集.证明: 已知{┐,∧,∨}为联结词完备集, 因而只需证明其中的每个联结词都可以由↑表示即可. 事实上┐p⇔┐(p∧p)⇔p↑pp∧q⇔┐┐(p∧q)⇔┐(p↑q)⇔(p↑q)↑(p↑q)p∨q⇔┐┐(p∨q)⇔┐(┐p∧┐q)⇔(┐p)↑(┐q)⇔(p↑p)↑(q↑q)从而{↑}是联结词完备集. 类似可证{↓}是联结词完备集.2.4 可满足性问题与消解法*命题公式的可满足性问题是算法理论的核心问题之一. 我们已知这个问题可以用真值表﹑主析取范式或主合取范式解决. 但这两个方法的计算量都很大. 本节介绍一个新的方法—消解法.由于任一公式都能化成等值的合取范式, 因而一般的命题公式的可满足性问题可以归结为合取范式的可满足性问题. *举例说明合取范式的可满足性问题.*合取范式中, 简单析取式中不同时出现某个命题变项和它的否定, 否则它为永真式, 可以把它从合取范式中消去. *称不含任何文字的简单析取式为空简单析取式, 记作λ. 规定空简单析取式是不可满足的.(因为对任何赋值, 空简单析取式中都没有文字为真). 因而, 含有空简单析取式的合取范式是不可满足的.设l 是一个文字, 记⎩⎨⎧⌝==⌝=p l p p l p l C若若,, 称作文字l 的补.下面用S 表示合取范式, 用C 表示简单析取式, 用l 表示文字. 设α是关于S 中命题变项的赋值, 用α(l),α(C)和 α(S)分别表示在α下l, C 和S 的值. 又设S 和S ’是两个合取范式, 用S ≈S ’表示S 是可满足的当且仅当S ’是可满足的. 定义2.8: 设C 1, C 2是两个简单析取式, C 1含文字l, C 2含文字l C , 从C 1中删去l, 从C 2中删去l C , 然后再将所得的结果析取成一个简单析取式, 称这样得到的简单析取式为C 1, C 2的(以l 和l C 为消解文字的)消解式或消解结果, 记作Res(C 1, C 2). 即设C 1=C 1’∨l, C 2 = C 2’∨l C , Res(C 1, C 2) = C 1’∨C 2’. 根据上述定义, 由C 1, C 2得到Res(C 1, C 2)的规则称作消解规则.*可以证明, 如果C 1, C 2可对多对(不同)文字消解, 其消解结果都是等值的. 例如: C 1 = ┐p ∨q ∨r, C 2 = p ∨┐r ∨┐s ∨t, 可消解为q ∨r ∨┐r ∨┐s ∨t (以p 和┐p 为消解文字), 或消解为┐p ∨q ∨p ∨┐s ∨t (以r 和┐r 为消解文字), 都是永真式.定理2.6: C 1∧C 2≈Res(C 1, C 2).证明: 记C = Res(C 1, C 2). 设消解文字为l, l C . 不妨设C 1 = C 1’∨l, C 2 = C 2’∨l C , 于是C = C 1’∨C 2’.假设C 1∧C 2是可满足的, α是满足它的赋值, 不妨设α(l) = 1, 由于α满足C 2, C 2必含有文字l ’ ≠ l 且α(l ’) = 1. 而C 中含l ’, 故α满足C.反之, 假设C 是可满足的, α是满足它的赋值. C 必含有文字l ’使得α(l ’) =1. 不妨设C 1’含有文字l ’. 把α扩张到l(l C )上, 取赋值α’如下:⎪⎩⎪⎨⎧===其它若若),(,1,0)('p l p l p p C αα 则C 1含有l ’且α’(l ’) =α(l ’) = 1, α’满足C 1, 又C 2含有l C 且α’(l C ) = 1, α’满足C 2, 从而C 1∧C 2是可满足的. *注意: C 1∧C 2与Res(C 1, C 2)具有相同的可满足性, 但它们不一定等值.例如: p ∨q ∨r 和p ∨┐r 可消解为p ∨q. α= (0,1,1)满足p ∨q, 但不满足(p ∨q ∨r)∧(p ∨┐r). α’ = (0,1,0)满足后者的赋值.*给定一个合取范式S, 从S 的简单析取式开始, 重复使用消解规则可以得到一个简单析取式序列. 根据定理2.6, 如果S是可满足的, 得到的所有简单析取式都是可满足的. 如果最后得到空简单析取式λ, 则S 不是可满足的.定义2.9: 设S 是合取范式, C 1, C 2, …, C n 是一个简单析取式序列. 如果对每个i (1≤i ≤n ), C i 是S 中的一个简单析取式,或者C i 是它之前的某两个简单析取式C j , C k (1≤j<k<i)的消解结果, 则称此序列是由S 导出C n 的消解序列. 当C n = λ时, 称此序列是S 的一个否证.推论: 如果合式范式S 有否证, 则S 不是可满足的.引理2.7: 设S 含有简单析取式l, 从S 中删去所有包含l 的简单析取式,再从剩下的简单析取式中删去l C , 把这样得到的合取范式记作S ’, 则S ≈S ’.证明: 假设S 是可满足的, α是满足S 的赋值. 由于S 含有简单析取式l, 必有α(l) = 1, 从而α(l C ) = 0. 对S ’中的任一简单析取式C ’, S 中有一个简单析取式C 使得C = C ’或C = C ’∨l C . 因为α使C 为真, 且α(l C ) = 0, C ’必含有l ’使得α(l ’) = 1, 从而α满足C ’, 得证S ’是可满足的.反之, 假设S ’是可满足的, α’是满足S ’的赋值. 由于S ’不含l 和l C , 可把α’扩张到l 上, 得到对S 的命题变项的赋值:⎪⎩⎪⎨⎧===C l p l p S p p p 若若中出现在若,0,1'),(')(αα 于是, 对S 中的任意简单析取式C, 若C 含l, 则α满足C; 若C 不含l, 则S ’中有C ’使得C = C ’或C = C ’∨l C . 而α’满足C ’,α和α’在S’上相同, 故α满足C.得证S是可满足的.定理2.8(消解完全性): 如果合取范式S是不可满足的, 则S 有否证.证明: 设S中含有k个命题变项, 用数学归纳法证明.当k=1时, S中只有一个命题变项, 设为p. 由于S是不可满足的, S中必同时含有简单析取式p和┐p,从而S有否证. 假设当k<n (n≥2)时, 定理成立, 要证k = n时定理也成立. 任意取定S中的一个命题变项p, 令S1表示S中所有含p 的简单析取式,S2表示S中所有含┐p的简单析取式,S3表示S 中所有既不含p又不含┐p的简单析取式. S’是如下得到的合取范式: 先删除S中所有含p的简单析取式, 然后再从剩下的简单析取式中删去文字┐p. S’是两个子合取范式S2’和S3的合取, 其中S2’是删去S2的所有简单析取式中的┐p后得到的合取范式. 令S”是如下得到的子句集: 先删除S中所有含┐p的简单析取式,然后再从剩下的简单析取式中删去文字p. S”也是两个子合取范式S1’和S3的合取, 其中S1’是删去S1的所有简单析取式中的p后得到的合取范式. 由引理2.7,S∧p≈S’, S∧┐p≈S”. 由于S是不可满足的, S∧p和S∧┐p 都是不可满足的, 故S’和S”也是不可满足的. 而S’和S”中命题变项的个数都小于n, 根据归纳假设, 存在从S’和S”导出λ的消解序列C1, C2, …, C i,和D1, D2, …, D j , 其中C i = D j = λ. 如果C t(1≤t≤i)是仅由S3中简单析取式消解得到的,则称C t 是与S 2’无关的; 否则称C t 是与S 2’有关的. 可类似地定义D t (1≤t ≤j )是与S 1’无关的和是与S 1’有关的. 分两种情况讨论如下:(1) C i 是与S 2’无关的, 或者D j 是与S 1’无关的, 此时可由S 3中的简单析取式消解得到λ, 这个消解序列也是S 的一个否证.(2) C i 是与S 2’有关的且D j 是与S 1’有关的, 对每个1≤t ≤i , 令 ⎩⎨⎧⌝∨=无关与若有关与若'22',',S C C S C p C C t t t tt 对每一个1≤t ≤j, 令⎩⎨⎧∨=无关与若有关与若'1'1',,S D D S D p D D t tt t t 不难看出C 1’, C 2’, …, C i ’和D 1’, D 2’, …, D j ’都是S 的消解序列, 分别得到C i ’ = ┐p 和D j ’ = p, 而Res(C i ’, D j ’) = λ. 因此, C 1’, C 2’, …, C i ’, D 1’, D 2’, …, D j ’,λ是S 的一个否证. k=n 时定理成立得证.推论: 合取范式S 是不可满足的当且仅当它有否证. 消解算法:输入: 合式公式A输出: 当A 是可满足时, 回答“yes ”; 否则回答“no ”.1. 求A 的合取范式S2. 令S 0和S 2为不含任何元素的集合, S 1为S 的所有简单析取式组成的集合3. 对S0中的每个简单析取式C1与S1中的每一个简单析取式C2:4. 如果C1, C2可以消解, 则5. 计算C = Res(C1, C2);6. 如果C = λ, 则7. 输出“no”, 计算结束.8. 如果S0和S1都不包含C, 则9. 把C加入S2;10. 对S1中的每一对子句C1, C211. 如果C1,C2可以消解, 则12.计算C = Res(C1, C2)13. 如果C = λ, 则14. 输出“no”, 计算结束.15. 如果S0与S1都不包含C, 则16. 把C加入S217. 如果S2中没有任何元素, 则18. 输出“yes”, 计算结束.19. 否则,把S1加入S0, 令S1等于S2, 清空S2, 返回步骤3. 例2.13: 用消解法判断下述公式是否可满足:(1) (┐p∨q)∧(p∨q)∧(┐q)(2) p∧(p∨q)∧(p∨┐q)∧(q∨┐r)∧(q∨r)解: (1) 这已经是合取范式, S=(┐p∨q)∧(p∨q)∧(┐q)第一次循环, S0 =φ,S1 = {┐p∨q, p∨q, ┐q}, S2 =φ┐p∨q, p∨q 消解得到q┐p∨q, ┐q 消解得到┐pp∨q, ┐q 消解得到pS2 = {p,┐p, q}第二次循环, S0 = {┐p∨q, p∨q, ┐q}, S1={p,┐p, q}, S2=φ┐p∨q, p 消解得到qp∨q, ┐p 消解得到q┐q, q 消解得到λ输出“no”, 计算结束.(2) S= p∧(p∨q)∧(p∨┐q)∧(q∨┐r)∧(q∨r)第一次循环, S0 =φ,S1={ p, p∨q, p∨┐q, q∨┐r, q∨r}, S2=φ.p∨q, p∨┐q 消解得到pp∨┐q, q∨┐r消解得到p∨┐rp∨┐q, q∨r 消解得到p∨rq∨┐r, q∨r 消解得到qS2= { p∨r, p∨┐r, q}第二次循环, S0 = { p, p∨q, p∨┐q, q∨┐r, q∨r},S1 = { p∨r, p∨┐r, q}, S2 =φp∨┐q, q 消解得到pq∨┐r, p∨r 消解得到p∨qq∨r, p∨┐r 消解得到p∨qp∨r, p∨┐r 消解得到pS2 = φ,输出“yes”, 计算结束.作业:1.用主析取范式判断下列公式是否等值:(p→q)→r与q→(p→r)2.用主合取范式判断下列公式是否等值:p→(q→r)与┐(p∧q)∨r3. 将下列公式化成与之等值且仅含{┐,∧}中联结词的公式:(1) (p→(q∧r))∨p(2) p∨┐q∨┐r4. 将下列公式化成与之等值且仅含{┐,∨}中联结词的公式: (p→(q∧┐p))∧q∧r5. 将下列公式化成与之等值且仅含{┐,→}中联结词的公式: (p∧q)∨r6. 用消解法判断下述公式是否可满足的(1) p∧(┐p∨┐q)∧q(2) (p∨q)∧(p∨┐q)∧(┐p∨r)。