联结词全功能集3.ppt

联结词全功能集 福建师范大学数学与计算机科学学院 回顾 等值演算 用等值演算法证明公式类型 用等值演算法证明等值式 求解实际问题 例 应用题 在某次研讨会的中间休息时间，3名与会者根据王教授的口音对他是哪个省市的人进行了判断： 甲说王教授不是苏州人，是上海人。 乙说王教授不是上海人，是苏州人。 丙说王教授既不是上海人，也不是杭州人。 听完以上3人的判断后，王教授笑着说，他们3人中有一人说的全对，有一人说对了一半，另一人说的全不对。试用逻辑演算法分析王教授到底是哪里人？ 设命题 p：王教授是苏州人。 q：王教授是上海人。 r：王教授是杭州人。 p,q,r中最多有一个真命题，至少有两个假命题，要通过逻辑演算将真命题找出来。 设 甲的判断为A1=┐p∧q 乙的判断为A2=p∧┐q 丙的判断为A3=┐q∧┐r 甲的判断全对?? B1=A1=┐p∧q 甲的判断对一半 B2=(┐p∧┐q)∨(p∧q) 甲的判断全错?? B3=p∧┐q 乙的判断全对?? C1=A2=p∧┐q 乙的判断对一半 C2=(p∧q)∨(┐p∧┐q) 乙的判断全错?? C3=┐p∧q 丙的判断全对?? D1=A3=┐q∧┐r 丙的判断对一半 D2=(q∧┐r)∨(┐q∧r) 丙的判断全错 D3=q∧r 由王教授所说 E = (B1∧C2∧D3)∨(B1∧C3∧D2)∨(B2∧C1∧D3) ∨(B2∧C3∧D1)∨(B3∨C1∧D2)∨(B3∧C2∧D1) 为真命题。 经过等值演算后,可得 E ? (┐p∧q∧┐r)∨(p∧┐q∧r) 由题设，王教授不能既是苏州人，又是杭州人，因而p,r中必有一个假命题，即p∧┐q∧r?0，于是 E ? ┐p∧q∧┐r 为真命题，因而必有p,r为假命题，q为真命题，即王教授是上海人。甲说的全对，丙说对了一半，而乙全说错了。 王教授只可能是其中一个城市的人或者三个城市都不是。 所以，丙至少说对了一半。 因此，可得甲或乙必有一人全错了。 又因为，若甲全错了，则有p∧┐q，因此乙全对。 同理，乙全错则甲全对。 所以丙必是一对一错。 根据上述推理，可对公式E进行简化，方便等值演算。 联结词全功能集 复合联结词 排斥或 与非式 或非式 真值函数 联结词全功能集 排斥或（异或,排斥或） 两个命题公式P和Q的排斥或是一个新命题公式， 记作P Q。当且仅当P、Q真值不同时， P Q 为T， 其他情况下的真值都是F。 异或联结词的性质： （1）P Q ?（P∧┐Q）∨（┐P∧Q） （2）P Q? ┐(P?Q） （3）P P?F，F P ? P，T P ? ┐P （4）P Q?P Q 交换律 （5）（P Q） R ?P （Q R） 结合律 （6）P∧（Q R）?（P∧Q） （P∧R）分配律 （课后习题） 与非 设P和Q是两个命题公式， P和Q的与非是一个新命题公式，记作P ? Q。当且仅当P和Q的真值都为 T时， P ? Q 为F ，其他情况下P ? Q的真值都是T 。 根据此定义，可知 P ? Q ? ┐（P∧Q） 或非 设P和Q是两个命题公式， P和Q的或非是一个新命题公式，记作P ? Q。当且仅当P和Q的真值都为 F 时， P ? Q 为T ，其他情况下P ? Q的真值都是F 。 根据此定义，可知 P ? Q ? ┐（P ∨ Q） 联结词的全功能集 定义 在一个联结词的集合中，如果一个联结词可 由集合中的其他联结词定义，则称此联结词为冗余 的联结词，否则称为独立的联结词. 例如,在联结词集{?, ?, ?, ?, ?}中，由于 p?q??p?q, 所以，?为冗余的联结词; 类似地，?也是冗余的 联结词. 又在{?, ?, ?}中，由于p?q??(?p??q) 所以，?是冗余的联结词，但{?, ?}无冗余的联结词. 类似地，?也是冗余的联结词，但{?, ? }无冗余的联结词. 联结词的全功能集(续) 定义 设S是一个联结词集合，如果任何n(n?1) 元 真值函数都可以由仅含S中的联结词构成的公式表 示，则称S是联结词全功能集.如果联结词全功能集 不含冗余的联结词，则称为极小功能集. 说明： 若S是联结词全功能集，则任何命题公式都可用S 中的联结词表示. 若S1, S2是两个联结词集合，且S1 ? S2. 若S1是全 功能集，则S2也是全功能集. 联结词的全功能集实例 (1) S1={?, ?, ?, ?} (2) S2={?, ?,