2005-5-31 § 26.4 联结词的完全集 1 §4 联结词的完全集 为什么只考虑五个联结词？即 这五个联结词能否表示所有联结词？ 这五个联结词是否有多余的？ 要回答这两个问题，必须回答： 什么是联结词？ 什么是一些联结词表示了一个联结词？ 什么是联结词的 “多余 ”？ 2005-5-31 § 26.4 联结词的完全集 2 什么是联结词？ 新联结词确定了新的复合命题构造方式。 新命题建立了新的真假值对应方式。 例如： ?p建立了如下对应： 0 —→ 1， 1 —→ 0 p∨q建立了如下对应 : (0, 0) —→ 0, (1, 0) —→ 1 , (0, 1) —→ 1, (1, 1) —→ 1 . …… 2005-5-31 § 26.4 联结词的完全集 3 真值函数 定义 10 {0, 1}上的 n元函数 f: { 0, 1} n —→ { 0, 1} 就称为一个 n元真值函数（布尔函数）。 每个联结词确定了一个真值函数。 每个真值函数也确定了一个联结词。 2005-5-31 § 26.4 联结词的完全集 4 真值函数确定联结词 设 f为如下二元真值函数 : f(0, 0) = 0, f(1, 0) = 0 , f(0, 1) = 0, f(1, 1) = 1. 则 f确定了联结词 C f ， pC f q的真假值为： 即 C f 为 ∧ 即 ： pC f q在指派 <t 1 , t 2 >下的值为 f(t 1 , t 2 ) 。 111 001 010 000 pC f qqp 2005-5-31 § 26.4 联结词的完全集 5 命题形式确定的联结词 ? 设命题形式 α所含的命题变元都在 p 1 , p 2 ,… p n 中。如下定义的 n元真值函数称为 α确定 真值函数，记为 f α : f α (t 1 , t 2 , … t n ) = α关于 p 1 , p 2 , … p n 在指派 t 1 , t 2 , … t n 下的值。 ? 例如，若 α 为 p∨(?q)，则 f α 为： f(0,0) = 1, f(0,1) = 0, f(1,0) = 1, f(1,1) = 1 2005-5-31 § 26.4 联结词的完全集 6 联结词的表示 用 c 1 , c 2 , …c k 表示 c (f) 仅用 c 1 , c 2 , … c k 可以构造一个命 题 α与由 c (f c )构造的命题等价。 存在 α使 α在任意指派 <t 1 , t 2 , …t n >下 的值即为 f c (t 1 , t 2 , …t n ) (f(t 1 , t 2 , …t n )) 2005-5-31 § 26.4 联结词的完全集 7 联结词的完全集 直观地，说联结词集合 A是完全的，指的 是 A中联结词能表示任意联结词。 定义 2.11 设 A一个联结词集合，称 A为联 结词的一个完全集，如果任一个真值函 数 f都可用 A联结词来表示，即： 对任真 值函数f，都存在仅含A中联结词的命题 α使得 α在任意指派<t 1 , t 2 , …t k >下的 值即为f(t 1 , t 2 , …t k )。 2005-5-31 § 26.4 联结词的完全集 8 {?， ∨， ∧， →} 定理 2 {?， ∨， ∧， →}是联结词的一个完全集。 证： 只要证： 对任k元真值函数f，都存在仅含 {?， ∨， ∧， →}中联结词的k元命题形式 α使得 α在 任意指派<t 1 , t 2 , …t k >下的值即为f(t 1 , t 2 , …t k )。对k归纳证明。 2005-5-31 § 26.4 联结词的完全集 9 {?， ∨， ∧， →}（续 1） k=1时，一元真值函数有四个f 1 、f 2 、f 3 、f 4 ： f 1 : 0 —→ 0， 1 —→ 0 f 2 : 0 —→ 1， 1 —→ 1 f 3 : 0 —→ 0， 1 —→ 1 f 4 : 0 —→ 1， 1 —→ 0 它们分别可以用 p∧(?p)、 p∨(?p)、 p和 ?p表 示。此时命题成立 2005-5-31 § 26.4 联结词的完全集 10 {?， ∨， ∧， →} （续 2） 设k<n时命题成立, 要证k=n时命题也成立. 设f( x 1 , x 2 ,…,x n )是一个n元真值函数, 定义如下两个n-1元真值函数f ’、f ’’: f’(x 2 ,x 3 ,…,x n ) = f(0,x 2 , x 3 ,…,x n ) f’’(x 2 ,x 3 ,…,x n ) = f(1,x 2 , x 3 ,…,x n ) 由归纳假设，f ’和f ’’都可由 仅含 {?， ∨， ∧， →} 中联结词 的n-1元命题形式 α 1 、 α 2 表示。设 α 1 、 α 2 中所含的命题变元设为p 2 ，p 3 ， …，p n . 则f可由( ?p 1 →α 1 ) ∧ (p 1 →α 2 )表示。 2005-5-31 § 26.4 联结词的完全集 11 对任意指派 < t 1 , t 2 ,…,t n > 当 t 1 =0时， (?p 1 →α 1 ) ∧ (p 1 →α 2 )在 < 0,t 2 ,…,t n >下的值 = α 1 在 < 0,t 2 ,…,t n >下的值 = α 1 在 <t 2 ,…,t n >下的值 = f’(t 2 ,t 3 ,…,t n ) = f(0,t 2 ,t 3 ,…,t n ) = f(t 1 ,t 2 ,t 3 ,…,t n ) 命题成立。 同理可证，当 t 1 =1时命题也成立。 2005-5-31 § 26.4 联结词的完全集 12 推论 1. 任一个 n元真函数都可由一个仅含 {?， ∨， ∧， →} 中联结词的 n元命题形式表 示 . 2. {?， ∨， ∧， →， ?}是联结词的完全 集。 3. ?可由 ?， ∨， ∧， →表示。 2005-5-31 § 26.4 联结词的完全集 13 {?， →}是联结词的完全集 证明： α∨β可由（ ?α） →β表示。 α∧β可由 ?（ α→（ ?β））表示。 即这两对命题形式在任意指派下的值相同。 2005-5-31 § 26.4 联结词的完全集 14 {?， ∨}是联结词的完全集 证明： α→β可由（ ?α） ∨β表示。 α∧β可由 ?（（ ?α） ∨（ ?β））表示。 2005-5-31 § 26.4 联结词的完全集 15 {?， ∧}是联结词的完全集 证明： α→β可由 ?（ α∧（ ?β））表示。 α∨β可由 ?（（ ?α） ∧（ ?β））表示。 2005-5-31 § 26.4 联结词的完全集 16 {∨， ∧， → ， ?}不是联结词的完全集 证明： 总取 0值的真值函数不能由只含此联结词 集中的联结词的命题形式来表示。 因为这样的命题形式在其中的命题变元 都取 1时也取值 1, 而不为 0. 2005-5-31 § 26.4 联结词的完全集 17 小结： {?， ∨， ∧， →， ?}的子集 ? {?， ∨， ∧， →， ?}是联结词的完全集。 ? 5个 4元素子集中只有 {∨， ∧， →， ?}不是联结 词的完全集。 ? 3元素子集中，只要含 ?就完全。 10个 3元素子集， 4个不完全， 6个完全。 ? 2元素子集中， {?， →}、 {?， ∨}、 {?， ∧} 是完全的。 ? {?， ?}是否完全？ ? {?}是否完全？ 2005-5-31 § 26.4 联结词的完全集 18 作业与思考题 ? 作业 p508. 5、 6、 7 、 8(p99--100) ? 思考题 o {?， ?}是否完全？ o {?}是否完全？ o 二元真值函数中，哪个是完全集？