§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在指派<t1t2>下的值为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在指派<t1, t2>下的值为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