联结词全功能集3(张).ppt

联结词全功能集 福建师范大学数学与计算机科学学院 回顾 命题符号化 符号 联结词 运算 等值演算 运算律与化简 用等值演算法证明公式类型用等值演算法证明等值式求解实际问题 例应用题 在某次研讨会的中间休息时间 3名与会者根据王教授的口音对他是哪个省市的人进行了判断 甲说王教授不是苏州人 是上海人 乙说王教授不是上海人 是苏州人 丙说王教授既不是上海人 也不是杭州人 听完以上3人的判断后 王教授笑着说 他们3人中有一人说的全对 有一人说对了一半 另一人说的全不对 试用逻辑演算法分析王教授到底是哪里人 设命题p 王教授是苏州人 q 王教授是上海人 r 王教授是杭州人 p q r中或者全假 或者有一个真命题 两个假命题 甲说王教授不是苏州人 是上海人A p q乙说王教授不是上海人 是苏州人B p q丙说王教授既不是上海人 也不是杭州人C q r 解答 列真值表 根据王教授说 他们3人中有一人说的全对 有一人说对了一半 另一人说的全不对 可知 A 恰有一个为真 于是可得 的赋值只能是 或 如果是 则甲 乙都说对了一半 与已知不符 所以 的赋值为 即王教授是上海人 联结词全功能集 复合联结词排斥或与非式或非式真值函数联结词全功能集 排斥或 异或 排斥或 两个命题公式P和Q的排斥或是一个新命题公式 记作PQ 当且仅当P Q真值不同时 PQ为T 其他情况下的真值都是F 异或联结词的性质 1 PQ P Q P Q 2 PQ P Q 3 PP 0 0P P 1P P 4 PQ QP交换律 5 PQ R P QR 结合律 6 P QR 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 全假为真见真为假 问题 多少个联结词最合适 真值函数 问题 含n个命题变项的所有公式共产生多少个互不相同的真值表 答案为个 为什么 定义称定义域为 00 0 00 1 11 1 值域为 0 1 的函数是n元真值函数 定义域中的元素是长为n的0 1串 常用F 0 1 n 0 1 表示F是n元真值函数 真值函数共有个 例如F 0 1 2 0 1 且F 00 F 01 F 11 0 F 10 1 则F为一个确定的2元真值函数 命题公式与真值函数 对于任何一个含n个命题变项的命题公式A 都存在惟一的一个n元真值函数F为A的真值表 等值的公式对应的真值函数相同 下表给出所有2元真值函数对应的真值表 每一个含2个命题变项的公式的真值表都可以在下表中找到 例如 p q p q p q p q q 等都对应表中的 2元真值函数对应的真值表 书上表1 6 联结词的全功能集 定义在一个联结词的集合中 如果一个联结词可由集合中的其他联结词定义 则称此联结词为冗余的联结词 否则称为独立的联结词 例如 在联结词集 中 由于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 布尔代数系统 3 S3 极小 4 S4 极小 5 S5 极小 6 S6 极小 大规模集成电路 7 S7 极小 大规模集成电路 例如已知 是全功能集 证明 也是全功能集证 因为 是全功能集 任意一个真值函数可以用 联结词的命题公式表示 对于任意的命题公式 A B A B 因此任意一个真值函数可以用