工科离散数学课件 第一章 1_6_范式(2) - 小项与大项.pptx

1.6.2 大项与小项1.6 范式-大项与小项1. [小项] n 个命题变元的合取式，它包含每个变元的文字一次且仅一次。小项 = 极小项 = 布尔合取。 ——值小，多是0问： n 个命题变元能组成多少个小项？观察：小项有什么其他特点呢？[编码方法] 每个小项只有一种赋值使其为1，用作对其编码： ——起个名字m11= p?q = m3 m10= p?┐q = m2m01= ┐p?q = m1 m00 = ┐p?┐q = m0答：2n个。2个变元的小项：p?q p?┐q ┐p?q ┐p?┐q1 1 1 0 0 1 0 1 1.6 范式-大项与小项(1)每个小项，只有变元赋值与其二进制编码相同时其值为1，其余全0。(2)任何一组赋值，能使唯一的一个小项为1，其余全0，即2个小项不能同时为1： mi ? mj = 0，0≤ i?j ≤ 2n-1[小项的特点（性质）]——m11= p?q = m3 m10= p?┐q = m2——m01= ┐p?q = m1 m00 = ┐p?┐q = m0(3) ?i=0 mi = 1 。2n-1 1.6 范式-大项与小项2. [大项] n 个命题变元的析取式，它包含每个变元的文字一次且仅一次。大项 = 极大项 = 布尔析取。 ——值大，多是1问： n 个命题变元能组成多少个大项？答：2n个。2个变元的大项：p?q p?┐q ┐p?q ┐p?┐q观察：大项有什么特点呢？ 0 0 0 1 1 0 1 1[编码] 每个大项只有一种赋值使其为0，用作对其编码：M00= p?q = M0 M01= p?┐q = M1M10= ┐p?q = M2 M11= ┐p?┐q = M3 1.6 范式-大项与小项(1)每个大项，只有变元赋值与其二进制编码相同时其值为0，其余全1。(2)任何一组赋值，能使唯一的一个大项为0，其余全1，即2个大项不能同时为0： Mi ? Mj = 1，0≤ i?j ≤ 2n-1 。[大项的特点（性质）]1. 对2个变元p和q的命题，m1、M1各是什么？ m1?m2=? M2?M3=?——m1=m01= ┐p?q； M1=M01= p?┐q； m1?m2=0；M2?M3=12. 对2个变元p和q的命题，p? ┐q、 p?┐q的编码是？——m10=m2；M01=M1——M00= p?q = M0 M01= p?┐q = M1——M10= ┐p?q = M2 M11= ┐p?┐q = M3(3) ?i=0 mi = 0 。2n-1 演算法求小项和大项：1.6 范式-大项与小项小项析取：添加与 1 的合取，将 1用缺少的变元替换，再施以分配律。大项合取：添加与 0 的析取，将 0用缺少的变元替换，再施以分配律。例1-24：将含3个变元 p、q 和 r的公式 A = p?┐q转换为小项的析取式 。解：A = p?┐q ?(合取，添1) (p?┐q)?1 ?(添加变元) (p?┐q)?(r?┐r) ?(分配律) (p?┐q?r)?(p?┐q?┐r)小项与大项转换定理： ┐mi = Mi，┐Mi = mi，0? i ?2n-1。——证明？ ┐m01= ┐( ┐p?q) = p?┐q=M01 1.6 范式-大项与小项1. 对2个变元p和q的命题，把公式p转换为小项的析取、大项的合取。——p? p?1 ? p?(q ?┐q) ? (p?q) ?(p? ┐q)= m11?m10——p? p?0 ? p?(q ? ┐q) ? (p?q) ? (p?┐q)= M00?M01