§4联结词的完全集 为什么只考虑五个联结词?即 这五个联结词能否表示所有联结词? 这五个联结词是否有多余的? 要回答这两个问题,必须回答 什么是联结词 什么是一些联结词表示了一个联结词? 什么是联结词的“多余”? 2005-5-31 §264联结词的完全集
2005-5-31 §26.4 联结词的完全集 1 §4 联结词的完全集 为什么只考虑五个联结词？即 这五个联结词能否表示所有联结词？ 这五个联结词是否有多余的？ 要回答这两个问题，必须回答： 什么是联结词？ 什么是一些联结词表示了一个联结词？ 什么是联结词的“多余”？
什么是联结词? 新联结词确定了新的复合命题构造方式。 新命题建立了新的真假值对应方式。 例如: p建立了如下对应 0—→>1,1>0 pvq建立了如下对应 (0,0)—>0,(1,0)—)1 2005-5-31 §264联结词的完全集
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 . ……
真值函数 定义10{0,1}上的元函数 f:{0,1}—{0,1} 就称为一个n元真值函数(布尔函数)。 每个联结词确定了一个真值函数。 每个真值函数也确定了一个联结词。 2005-5-31 §264联结词的完全集
2005-5-31 §26.4 联结词的完全集 3 真值函数 定义10 {0, 1}上的n元函数 f: { 0, 1}n —→ { 0, 1} 就称为一个n元真值函数（布尔函数）。 每个联结词确定了一个真值函数。 每个真值函数也确定了一个联结词
真值函数确定联结词 设f为如下二元真值函数 f(0,0)=0,f(1,0)=0,f(0,1)=0,f(1,1)=1 则f确定了联结词C,p℃q的真假值为: p00 pCq 甲C为A 10 即.pCq在指派下的值为ft,t)。 2005-5-31 §264联结词的完全集
2005-5-31 §26.4 联结词的完全集 4 真值函数确定联结词 设f为如下二元真值函数: f(0, 0) = 0, f(1, 0) = 0 , f(0, 1) = 0, f(1, 1) = 1. 则f确定了联结词Cf ，p Cf q的真假值为： 即Cf 为∧ 即： p Cf q在指派下的值为f(t1, t2) 。 1 1 1 1 0 0 0 1 0 0 0 0 p q p Cf q
命题形式确定的联结词 设命题形式所含的命题变元都在p1p2 pn中。如下定义的n元真值函数称为α确定 真值函数,记为f 0关于p1p2…pn在指派t1t21…t下的值。 例如,若α为p(一q),则f为: f(0,0)=1,f(0,1)=0,6(1,0)=1,f(1,1)= 2005-5-31 §264联结词的完全集
2005-5-31 §26.4 联结词的完全集 5 命题形式确定的联结词 设命题形式α所含的命题变元都在p1, p2 ,… pn中。如下定义的n元真值函数称为α确定 真值函数，记为fα: fα(t1, t2 , … tn) = α关于p1, p2 , … pn在指派t1, t2 , … tn下的值。 例如，若α 为p∨(¬q)，则fα为： f(0,0) = 1, f(0,1) = 0, f(1,0) = 1, f(1,1) = 1
联结词的表示 用c,C.C表示c( 仅用c1C2…C可以构造一个命 题α与由c(f)构造的命题等价。 存在使在任意指派下 的值即为f(t,t,…t)(ft1,t2…t) 2005-5-31 §264联结词的完全集
2005-5-31 §26.4 联结词的完全集 6 联结词的表示 用c1, c2, …ck表示c (f) 仅用c1, c2, … ck可以构造一个命 题α与由c (fc)构造的命题等价。 存在α使α在任意指派下 的值即为fc(t1, t2, …tn) (f(t1, t2, …tn))
联结词的完全集 直观地,说联结词集合A是完全的,指的 是A中联结词能表示任意联结词。 定义211设A一个联结词集合,称A为联 结词的一个完全集,如果任一个真值函 数f都可用A联结词来表示,即:对任真 值函数f,都存在仅含A中联结词的命题 〔使得在任意指派<t1,t2,…t下的 值即为f(t1,t2…t) 2005-5-31 §264联结词的完全集
2005-5-31 §26.4 联结词的完全集 7 联结词的完全集 直观地，说联结词集合A是完全的，指的 是A中联结词能表示任意联结词。 定义2.11 设A一个联结词集合，称A为联 结词的一个完全集，如果任一个真值函 数f都可用A联结词来表示，即：对任真 值函数f，都存在仅含A中联结词的命题 α使得α在任意指派下的 值即为f(t1, t2, …tk)
{,v,∧,→ 定理2{一,V,∧,→}是联结词的一个完全集。 证:只要证: 对任k元真值函数f,都存在仅含{_,, ∧,→}中联结词的k元命题形式使得α在 任意指派下的值即为f(1, t)。对k归纳证明 2005-5-31 §264联结词的完全集
2005-5-31 §26.4 联结词的完全集 8 {¬，∨，∧，→} 定理2 {¬，∨，∧，→}是联结词的一个完全集。 证：只要证： 对任k元真值函数f，都存在仅含{¬，∨， ∧，→}中联结词的k元命题形式α使得α在 任意指派下的值即为f(t1, t2, …tk)。对k归纳证明
{-,v,∧,→}(续1) k=1时,一元真值函数有四个f1、f2、f2、f f1:0—>0,1—>0 f:0—>1,1→>1 0,1—>1 f:0 1,1->0 它们分别可以用p(-p)、p√(-p)、p和-p表 示。此时命题成立 2005-5-31 §264联结词的完全集
2005-5-31 §26.4 联结词的完全集 9 {¬，∨，∧，→}（续1） k=1时，一元真值函数有四个f1、f2、f3、f4： f1: 0 —→ 0，1 —→ 0 f2: 0 —→ 1，1 —→ 1 f3: 0 —→ 0，1 —→ 1 f4: 0 —→ 1，1 —→ 0 它们分别可以用p∧(¬p)、 p∨(¬p)、p和¬p表 示。此时命题成立
{-,v,∧,→}(续2) 设kn时命题成立,要证k=n时命题也成立 设f(x,x23…,x)是一个n元真值函数, 定义如下两个n-1元真值函数f、f”: f X, X )≡f(0,x2,Xx,…,x n f2( )=f(1,xy,x n 由归纳假设,f和f”都可由仅含{,V,A,→} 中联结词的n-1元命题形式a1、a2表示。设a1、2 中所含的命题变元设为p2,p3,…,D 则f可由(-p1→a1)∧(p1→2)表示。 2005-5-31 §264联结词的完全集
2005-5-31 §26.4 联结词的完全集 10 {¬，∨，∧，→} （续2） 设k<n时命题成立, 要证k=n时命题也成立. 设f(x1, x2,…,xn)是一个n元真值函数, 定义如下两个n-1元真值函数f’、f’’: f’(x2,x3,…,xn) = f(0,x2, x3,…,xn) f’’(x2,x3,…,xn) = f(1,x2, x3,…,xn) 由归纳假设，f’和f’’都可由仅含{¬，∨，∧，→} 中联结词的n-1元命题形式α1、α2表示。设α1、α2 中所含的命题变元设为p2，p3，…，pn. 则f可由(¬p1 → α1) ∧ (p1 → α2)表示