www.7894.com

用德莫根律将┐内移

  • 日期: 2019-09-16
  • 浏览次数:

  请盲目恪守互联网相关的政策律例,严禁发布、、的言论。用户名:验证码:匿名?颁发评论

  1.本坐不应用户上传的文档完整性,不预览、不比对内容而间接下载发生的问题本坐不予受理。

  一个公式正在等值的意义下,能够有很多种分歧的形式。 反过来,几个形式上完全分歧的公式可能是统一个公式(正在等值的意义下)。 那么,正在一个公式的诸多暗示形式中,有没有一种尺度的形式呢?更进一步的说,有没有一种尺度形式是一个公式的独一暗示形式呢? 第二章 命题逻辑等值演算 定义2.1(文字) 命题变项及其否认统称为文字。 定义2.2(简单析取式、简单合取式) 仅由无限个文字形成的析取式(或单个文字)称做简单析取式。 仅由无限个文字形成的合取式(或单个文字)称做简单合取式。 留意:单个文字既是简单析取式,又是简单合取式 例:p,q,┐p,┐q,p∨┐q,p∨┐q∨r为简单析取式 p,q,┐p,┐q,p∧┐q,p∧┐q∧r为简单合取式 析取范式、合取范式 定义2.3 (1)由无限个简单合取式的析取形成的析取式称为析取范式。 (2)由无限个简单析取式的合取形成的合取式称为合取范式。 (3)析取范式和合取范式统称为范式。 由定义可知: 若A1,A2,…,An为简单合取式,则A1∨A2∨…∨An为析取范式 例如:p∨(p∧q)∨(p∧┐q∧r)为析取范式 若A1,A2,…,An为简单析取式,则A1∧A2∧…∧An为合取范式 例如:p∧(p∨q)∧(p∨┐q∨r)为合取范式 析取范式、合取范式 定义2.3 (1)由无限个简单合取式的析取形成的析取式称为析取范式。 (2)由无限个简单析取式的合取形成的合取式称为合取范式。 (3)析取范式和合取范式统称为范式。 析取范式和合取范式的性质:(2.2) (1)一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。 (2)一个合取范式是沉言式当且仅当它的每个简单析取式都是沉言式。 (3)对于每个命题公式,都有取之等值的析取范式和合取范式。 范式的构制步调(p24): 例:求(p→q)?r的析取范式和合取范式。 解: (1)合取范式 (p→q)?r =(┐p∨q)?r (消去→) =((┐p∨q)→r)∧(r→(┐p∨q))(消去?) =(┐(┐p∨q)∨r)∧(┐r∨(┐p∨q)) (消去→) =((p∧┐q)∨r)∧(┐p∨q∨┐r) (德莫根律将┐内移) =(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r) (∨对∧的分派律) (2)析取范式 (p→q)?r =((p∧┐q)∨r)∧(┐p∨q∨┐r) (∧对∨的分派律) 求下列公式的析取范式和合取范式。 (1)(p→q)→r (2)(p→q)∧(q→r) 定义(极小项):正在共含有n个命题变项p1,p2,…,pn的简单合取式 中,每个命题变项pi或其否认式┐pi,均呈现且两者仅呈现一个,而且按命题变项的下标陈列(或字母按字典序列),如许的简单合取式称为极小项。 例如:对于含三个命题变项p、q、r的公式 p∧┐q∧r,┐p∧q∧┐r是极小项 p∧┐q不是极小项,此中没呈现r p∧┐p∧┐r不是极小项,p,┐p同时呈现 关于极小项的两点申明 关于极小项的两点申明 例:3个命题变项p,q,r可构成的极小项。 定义(从析取范式):若是析取范式中所有的简单合取式都是极小项,则称该析取范式为从析取范式。 例如:对于含三个命题变项p、q、r的公式 (1) p∨(┐p∧q) (2)(p∧q)∨(┐p∧r) (3)(p∧┐q∧r)∨(┐p∧q∧┐r) 明显公式(1)和(2)不是从析取范式。而公式(3)是从析取范式。 (从析取范式独一存正在性): 任何一个命题公式均存正在独一取之等值的从析取范式。 求给定数题公式A的从析取范式的步调 (1)将公式A化为析取范式A’ (2)若A’的某简单合取式B不是极小项,即B中缺命题变项pi,也不含它的否认, 则对B做如劣等值变换: B=B∧(pi∨┐pi)=(B∧pi)∨(B∧┐pi) (3)用幂等律将反复的极小项消去,即 mi∨mi= mi, 然后将各极小项按挨次陈列,从而获得从析取范式 例:求(p→q)?r的从析取范式。 解: (p→q)?r(求析取范式) =(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r) = m4∨(┐p ∧r)∨(q∧r) ┐p∧r =(┐p ∧r)∧(q∨┐q) =(┐p ∧q∧r)∨(┐p ∧┐q∧r) = m1∨m3 q∧r =(p∨┐p)∧(q∧r) =(p∧q∧r)∨(┐p∧q∧r) = m3∨m7 所以(p→q)?r= m1∨m3∨m4∨m7 求下列公式的从析取范式。 (1)(p→q)→r (2)(p→q)∧(q→r) 从析取范式的用处: 2、判断公式的类型 设公式A中含n个命题变项,则 (1)A为沉言式 当且仅当A的从析取范式含全数2n个极小项 (2)A为矛盾式 当且仅当A的从析取范式不含任何极小项, 此时,记A的从析取范式为0 (3)A为可满脚式 当且仅当A的从析取范式中至多含一个极小项 极大项 对极大项的申明 例:3个命题变项p,q,r可构成的极小项和极大项。 从合取范式 求给定数题公式A的从合取范式的步调: (1)将公式A化为合取范式A’ (2)若A’的某简单析取式B不是极大项,即B中缺命题变项pi,也不含它的否认,则对B做如劣等值变换: B=B∨(pi∧┐pi)=(B∨pi)∧(B∨┐pi) (3)用幂等律将反复的极大项消去,即Mi∧Mi= Mi,然后将各极大项按挨次陈列。 例:求(p→q)?r的从合取范式。 解:(p→q)?r(求合取范式) =(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r) =(p∨r)∧(┐q∨r)∧ M5 (p∨r) =(p∨r)∨(q∧┐q) =(p∨q∨r)∧(p∨┐q∨r) = M0∧M2 (┐q∨r) =(p∧┐p)∨(┐q∨r) =(p∨┐q∨r)∧(┐p∨┐q∨r) = M2∧M6 所以(p→q)?r= M0∧M2∧M5∧M6 求下列公式的从合取范式。 (1)(p→q)→r (2)(p→q)∧(q→r) 从析取范式和从合取范式的关系 :设mi和Mi是由n个命题变项p1,p2,…,pn构成的极小项和极大项,那么┐mi=Mi,mi=┐Mi 由公式的从析取范式求从合取范式: 设公式A含n个命题变项,A的从析取范式含s个极小项, 设A=mi1∨mi2∨…∨mis , 0≤ij≤2n-1 A的从析取范式中,没呈现的极小项是mj1,mj2,…,mj2n-s 易见mj1∨mj2∨…∨mj2n-s为┐A的从析取范式 即┐A=mj1∨mj2∨…∨mj2n-s ┐┐A=┐(mj1∨mj2∨…∨mj2n-s) A=┐mj1∧┐mj2∧…∧┐mj2n-s =Mj1∧Mj2∧…∧Mj2n-s 例:由公式的从析取范式求从合取范式。 (1)A= m1∨m2(A中含2个命题变项) (2)B= m1∨m2∨m3(B中含3个命题变项) 操纵从合取范式判断公式的类型 思虑题:求公式(┐p∧q)→┐r的从析取范式和从合取范式。(注:不答应利用等值演算法) 解: (1)(p→q)→r=(p∨r)∧(┐q∨r) (2)(p→q)∧(q→r)=(┐p∨q)∧(┐q∨r) (p→q)→r= M0∧M2∧M6 (p→q)∧(q→r)= M2∧M4∧M5∧M6 (p→q)→r= m1∨m3∨m4∨m5∨m7 (p→q)∧(q→r)= m0∨m1∨m3∨m7 解: (1)由题意可知,A的从析取范式中的极小项是m1,m2,没呈现的极小项是m0,m3,所以A的从合取范式中的极大项是M0,M3。 A= M0∧M3 (2)由题意可知,B的从析取范式中的极小项是m1,m2,m3,没呈现的极小项是m0,m4,m5,m6,m7,所以A的从合取范式中的极大项是M0,M4,M5,M6,M7。 B= M0∧M4∧M5∧M6∧M7 设公式A中含n个命题变项,则 (1)A为沉言式 当且仅当A的从合取范式不含任何极大项, 此时,记A的从合取范式为1。 (2)A为矛盾式 当且仅当A的从合取范式含全数2n个极大项 (3)A为可满脚式 当且仅当A的从合取范式中的极大项个数必然小于2n * 2.2 范 式 命题公式的尺度型:(从)析取范式取(从)合取范式 以下会商尺度型相关的概念: 文字?简单析取式、简单合取式 ?析取范式、合取范式(+极小项、极大项) ?从析取范式、从合取范式 问1: p∨┐q∨r是什么范式? 问2: p∧┐q∧r是什么范式? 留意:简单合取式和简单析取式既是析取范式,也是合取范式。 2.3(范式存正在) 肆意一个命题公式均存正在一个取之等值的析取范式和合取范式。 设A1,A2,…,An为简单合取式,则A=A1∨A2∨…∨An为析取范式。 设A1,A2,…,An为简单析取式,则A=A1∧A2∧…∧An为合取范式。 第一步: 消去公式中呈现的→ ,?。 A→B = ┐A∨B A?B =(A→B)∧(B→A) =(┐A∨B)∧(A∨┐B) 第二步:用双沉否认律┐┐A=A消去双沉否认联合词, 用德莫根律将┐内移,一曲移到命题变项之前 ┐(A∨B)=┐A∧┐B ┐(A∧B)=┐A∨┐B 第三步:用分派律、连系律化去二沉以上的刮号,成为析 取范式或合取范式 操纵∧对∨的分派律求析取范式; 操纵∨对∧的分派律求合取范式; =(((p∧┐q)∨r)∧┐p)∨ (((p∧┐q)∨r)∧q)∨ (((p∧┐q)∨r)∧┐r) (∧对∨的分派律) =(p∧┐q∧┐p)∨(r∧┐p)∨ =(p∧┐q∧┐r)∨(┐p ∧r)∨(q∧r) (析取范式) 命题公式的析取范式和合取范式不是独一的。 (p∧┐q∧q)∨(r∧q)∨ (p∧┐q∧┐r)∨(r∧┐r) (析取范式) 解: (1)(p→q)→r=(p∧┐q)∨r(析取范式) (p→q)→r=(p∨r)∧(┐q∨r)(合取范式) (2)(p→q)∧(q→r)=(┐p∨q)∧(┐q∨r) (合取范式) (p→q)∧(q→r)=(┐p∧┐q)∨(┐p∧r)∨(q∧r) (析取范式) 教材内容组织布局: 文字?简单析取式、简单合取式?析取范式、合取范式 + 极小项、极大项?从析取范式、从合取范式 讲堂讲授内容组织布局: 文字?简单析取式、简单合取式?析取范式、合取范式 析取范式+极小项?从析取范式 合取范式+极大项?从合取范式 从析取范式?从合取范式 或 从合取范式?从析取范式 熟练从析取范式的求解 控制从合取范式的求解 熟练控制 教材内容组织布局: 文字?简单析取式、简单合取式?析取范式、合取范式 + 极小项、极大项?从析取范式、从合取范式 讲堂讲授内容组织布局: 文字?简单析取式、简单合取式?析取范式、合取范式 析取范式+极小项?从析取范式 合取范式+极大项?从合取范式 从析取范式?从合取范式 或 从合取范式?从析取范式 (1)极小项和其成实赋值逐个对应 每一个极小项只要一个赋值使其为线个赋值使其为假。 例如对于含有三个分歧命题变项p,q,r的极小项┐p∧q∧┐r。 赋值010使其为线个赋值使其为假。如许极小项取成实赋值成立了逐个对应关系。 (2)极小项的简记法 每一个极小项对应着一个二进制数(成实赋值),也对应一个十进制数(成实赋值的十进制暗示)。 若是极小项对应的成线,把其看做二进制数,化为十进制数为0?k?2n-1,则该极小项记做mk 。 n个命题变项的生2n个极小项,别离记为m0,m1,m2,…,m2n-1。 例如上例中的极小项┐p∧q∧┐r应记做m2 。 解: (1)(p→q)→r=(p∧┐q)∨r(析取范式) (2)(p→q)∧(q→r)=(┐p∧┐q)∨(┐p∧r)∨(q∧r) (析取范式) 解: (1)(p→q)→r=m1∨m3∨m4∨m5∨m7 (2)(p→q)∧(q→r)= m0∨m1∨m3∨m7 1、公式的成实取成假赋值 若公式A中含有n个命题变项,A的从析取范式含s(0≤s≤2n)个极小项,则A有s个成实赋值,它们是所含极小项的成线n-s个赋值是成假赋值。 例:(p→q)?r= m1∨m3∨m4∨m7 则(p→q)?r的 成线 现实上┐((p→q)?r)= m0∨m2∨m5∨m6 问┐((p→q)?r)的从析取范式是什么? 3、判断两个公式能否等值 两命题公式A和B等值,当且仅当A和B具有不异的从析取范式。 4、阐发和处理现实问题 解:设p:派A去; q:派B去; r:派C去 则由题意可得: (p→r)∧(q→┐r)∧(┐r→(p∨q)) 求公式从析取范式: (p→r)∧(q→┐r)∧(┐r→(p∨q)) =m1∨m2∨m5 例 从ABC三人中挑选出1-2人出国,选派时满脚下列要求: (1)若A去,则C同去。 (2)若B去,则C不去。 (3)若C不去,则A或B能够去。 问若何选派他们? 因为 m1 = ┐p∧┐q∧r; m2 = ┐p∧q∧┐r; m5 = p∧┐q∧r 所以选派方案有3种: (a)C去,A,B都不去。 (b)B去,A,C都不去。 (c)A,C同去,B不去。 教材内容组织布局: 文字?简单析取式、简单合取式?析取范式、合取范式 + 极小项、极大项?从析取范式、从合取范式 讲堂讲授内容组织布局: 文字?简单析取式、简单合取式?析取范式、合取范式 析取范式+极小项?从析取范式 合取范式+极大项?从合取范式 从析取范式?从合取范式 或 从合取范式?从析取范式 定义:正在共含有n个命题变项p1,p2,…,pn的简单析取式 中,每个命题变项pi或其否认式┐pi,均呈现且两 者仅呈现一个,而且按命题变项的下标陈列(或字 母按字典序列),如许的简单析取式称为极大项。 例如:对于含三个命题变项p、q、r的公式 p∨┐q∨r,┐p∨q∨┐r是极大项 p∨┐q不是极大项,此中没呈现r p∨┐p∨┐r不是极大项,p,┐p同时呈现 例如:对于含有三个分歧命题变项p,q,r的极大项┐p∨q∨┐r,赋值101使其为假,其余23-1=7个赋值使其。如许极大项取成假赋值成立了逐个对应关系。 (2)极大项的记法:每一个极大项对应着一个二进制数(成假赋值),也对应一个十进制数(成假赋值的十进制暗示)。如极大项对应的成假赋值a1a2a3,把其看做二进制数,化为十进制数为0?k?2n-1,则该极大项记做Mk 。n个命题变项的生2n个极大项,别离记为M0,M1,M2,…,M2n-1。 (1)极大项和其成假赋值逐个对应: 每一个极大项只要一个赋值使其为假,其余2n-1个赋值使其。 如极大项┐p∨q∨┐r记做M5 不难发觉┐mi=Mi,mi=┐Mi 定义:若是合取范式中所有的简单析取式都是极大项,则称该合取范式为从合取范式。 例如:对于含三个命题变项p、q、r的公式 p∧(┐p∨q),(p∨q)∧(┐p∨r)是合取范式 但不是从合取范式。 (p∨┐q∨r)∧(┐p∨q∨r)是从合取范式。 (从合取范式独一存正在性): 任何一个命题公式均存正在一个取之等值的从合取范式,并且是独一的。 *