nbhkdz.com冰点文库

1.4 联结词全功能集

时间:2014-06-17


2C%2023%20Aug%202017%2014%3A56%3A10%20%2B0800&authorization=bce-auth-v1%2Ffa1126e91489401fa7cc85045ce7179e%2F2017-08-23T06%3A56%3A00Z%2F-1%2Fhost%2Fd10d53b59838bd6b44f530907306858c95f93106c7d62a4c6e47246f99277c59&x-bce-range=0-476&token=b916320c274725357c8e6c5ac65f5e70bd617103b8110761031a52657504dc72&expire=2027-07-02T06:56:00Z" style="width: 100%;">
山东政法学院教案模版 授课时间 授课章节 教学方法 板书和电子课件结合 与手段 使用教材和 主要参考书 1、教材: 耿素云等,离散数学,清华大学出版社,2008 2.参考书 左孝琳、李为槛、刘永才,离散数学(上海科技文献版)2006 课时安排 1 课时 第一周 任课教师 1.4 联接词全功能集 及职称 讲师 第 2 唐新华 次课

教学与目的要求: 理解真值函数 、了解联结词全功能集

教学重点、难点: 教学重点:真值函数 联结词的全功能集 教学难点:真值函数 联结词的全功能集

教学内容: 1.4 联结词全功能集 一、本节主要内容 复合联结词 排斥或 与非式 或非式 真值函数 联结词全功能集 二、教学内容 复合联结词 排斥或(异或): “p、q 之中恰好有一个成立” p?q?(p??q)?(?p?q) 与非式: “p 与 q 的否定” p?q??(p?q) 或非式: “p 或 q 的否定” 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 元真值 函数. 共有 个 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 个命题变项的公式的真值表都可以在下表中找到. 例对于任何一个含 n 个命题变项的命题公式 A,都存在 惟一的一个 n 元真值函数 F 为 A 的真值表. 等值的公式对应的真值函数相同. 下表给出所有 2 元真值函数对应的真值表, 每一个含 2 个命题变项的公式的真值表都可以在下表中找到. 例如:p?q, ?p?q, (?p?q)?(?(p?q)?q) 等都对应 表中的 如:p?q, ?p?q, (?p?q)?(?(p?q)?q) 等都对应 表中的 F ( 2) 13 2 元真值函数对应的真值表 p q 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 1 p q 1 0
( 2) F10 ( 2) F11

0 0 0

0 0 1

0 0 1 1
( 2) F12 ( 2) F13

0 1 0 0
( 2) F14

0 1 0 1
( 2) F15

0 1 1 0

F8( 2)

F9( 2)

山东政法学院教案模版 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1 联结词的全功能集 定义 在一个联结词的集合中,如果一个联结词可 由集合中的其他联结词定义,则称此联结词为冗余 的联结词,否则称为独立的联结词. 例如,在联结词集{?, ?, ?, ?, ?}中,由于 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={?} 而{?},{ ?}等则不是联结词全功能集. 例 如已知{?, ?}是全功能集,证明{?, ?}也是全功能集 证: 因为{?, ?}是全功能集,任意一个真值函数可以用 {?, ?}联结词的命题公式表示。 1 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1

山东政法学院教案模版 对于任意的命题公式,A ?B ? ?A ?B,因此任意一个真值函数可以用{?, ?}联 结词的命题公式表示。 例 ?p ? ?(p ? p) ? p ? p ?p ? ?(p ? p) ? p ? p p ? ?(?p ) ? ?( p ? p) ? ( p ? p) ? ( p ? p) p ? ?(?p ) ? ?( p ? p) ? ( p ? p) ? ( p ? p)

复习思考题、作业题: 去掉下面连接词集中冗余的联接词 (1) S1={?, ?, ?, ?} (2) S2={?, ?, ?, ?, ?}

下次课预习要点: 1.5.1 对偶原理 1.5.2 析取范式与合取范式 1.5.2.1 基本概念 1.5.2.2 命题公式的范式 1.5.2.3 求公式的范式举例 1.5.3 主析取范式与主合取范式 1.5.3.1、极小项与极大项 1.5.3.2、主析取范式与主合取范式 1.5.3.3、命题公式 A 的主析取范式与主合取范式 1.5.3.4、用等值演算法求公式的主范式的步骤 1.5.4 主范式的用途——与真值表相同

山东政法学院教案模版

实施情况及教学效果分析:

院系部审核意见:

院系部负责人签字 年 月 日


更多相关标签