离散数学(第二章).ppt

§1.5 联结词的完备集 联结词完备集 定义：一个联结词集合，若对于任何一个公式均可以用该集合中的联结词来表示或等值表示，就称为联结词完备集。 如果该集合任意去掉一个联结词，就不再具备这种特性，就称为最小完备集。 定理：{┐,∧,∨}是联结词完备集。 推论：{┐,∧,∨,→}，{┐,∧,∨,→,?}， 等都是联结词完备集。 §1.5 联结词的完备集 * 因为p∨q ? ┐（┐p∧┐q） p∧q ? ┐（┐p∨┐q） p∨q ? ┐p → q p∧q ? ┐（p → ┐q） 推论：{┐、∧}、{┐、∨}、{┐、→}是联结词完备集，并且是最小联结词完备集。 §1.5 联结词的完备集 {┐，?}是否是完备集？ 可以证明任何一个仅含“?”和“┐”的二元命题合式公式真值中有1和0 的个数都是偶数的。 不是 §1.5 联结词的完备集 {∧ ， ∨ ，→ ，?}不是完备集 （只需证明┐p无法由仅含此联结词集中的联结词的公式表示即可 ） 总取0值的真值函数不能由只含此联结词集中的联结词的命题形式来表示。因为这样的命题形式在其中的命题变元都取1时也取值1, 而不为0. {∧}，{∨}，{?}，{→}，{?}都不是完备集 §1.5 联结词的完备集 设p、q为二命题，复合命题“p与q的否定”称为p与q的与非式，记作p?q，?称与非联结词 易见：1、 p?q ? ┐（p∧q） 2、 p?q为真当且仅当p与q不同时为真 与非联结词?的性质： （1）p?p ? ┐(p∧p) ? ┐p （2）(p?q)?(p?q) ? ┐(p?q) ? p∧q （3）(p?p)?(q?q) ? ┐p?┐q ? ┐(┐p∧┐q) ? p∨q 定义 与非联结词 §1.5 联结词的完备集 p q p ? q 0 0 1 0 1 1 1 0 1 1 1 0 与非联结词 §1.5 联结词的完备集 设p、q为二命题，复合命题“p或q的否定”称为p与q的或非式，记作p?q，?称或非联结词 易见：1、 p?q ? ┐（p∨q） 2、 p?q为真当且仅当p与q同时为假 或非联结词 或非联结词?的性质： （1）p?p ? ┐(p∨p) ? ┐p （2）(p?q)?(p?q) ? ┐(p?q) ? p∨q （3）(p?p)?(q?q) ? ┐p?┐q ? ┐(┐p∨┐q) ? p∧q §1.5 联结词的完备集 或非联结词 p q p ? q 0 0 1 0 1 0 1 0 0 1 1 0 §1.5 联结词的完备集 p?q ?(p∧┐q)∨(┐p∧q) p q p?q 0 0 0 0 1 1 1 0 1 1 1 0 不可兼或 §1.5 联结词的完备集 定理：{?}是联结词完备集 证：┐P?┐(P?P)?P↑P P?Q?┐┐(P?Q)?┐(P↑Q) ?(P↑Q)↑(P↑Q) P?Q?┐(┐P?┐Q) ?┐((P↑P)?(Q↑Q)) ?(P↑P)↑(Q↑Q) §1.5 联结词的完备集 定理： {?}是联结词完备集 p∨q?┐(p↓q) ┐p?p↓p §1.5 联结词的完备集 作业： 习题2:19、20、24、25 §1.4 析取范式与合取范式 ?????例2：求(P ? Q) ? R的析取范式与合取范式 解: 原式?((P?Q) ?R)∧(R?(P?Q) ) ?(┐(P?Q)∨R)∧(┐R ∨(P?Q) ) ?(┐(┐P∨Q)∨R)∧(┐R∨┐P∨Q ) ?((P∧ ┐Q)∨R)∧(┐R∨┐P∨Q ) ?((P∨R)∧(┐Q∨R)∧(┐R∨┐P∨Q ) (合取范式) ?((P∧┐Q)∧(┐R∨┐P∨Q ) )∨(R ∧(┐R∨┐P∨Q ) ?(P∧┐Q∧┐R)∨(R∧┐P)∨(R∧Q) (析取范式) §1.4 析取范式与合取范式 命题公式的主析(合)取范式 (由于一个命题公式的析(合)取范式不是唯一, 因而它们不能作为命题公式的规范形式(标准形 式), 为了使任意命题公式化为唯一的标准形式, 下 面引入主范式的概念. §1.4 析取范式与合取范式 1.命题公式的主析取范式 定义3：在含有n个命题变元的简单合取式中, 若每个命题变元和它的否定不同时出现，而二者 之一必出现且仅出现一次，称这样的简单合取式 为小项. 例如,三个命题变元P,Q,R,其小