首页 您的当前位置:www.6538.com > www.6538.net >

设 Ai ( i ? 1

发布时间:2019-09-07

  第二章 命题逻辑等值运算 第1节 等值式 第2节 析取范式取合取范式 第3节 联合词的完整集 第2节 析取范式取合取范式 一、简单合取式和简单析取式 二、范式 三、范式的独一性——从范式 四、几点留意 每种数字尺度形都能供给良多消息,如代数式 的因式分化可判断代数式的根环境。 逻辑公式正在等值演算下也有尺度形—范式,范 式有两种:析取范式和合取范式。 一、简单合取式和简单析取式 定义2.2 命题变项及其否认统称做文字. 仅由无限个文字形成的析取式称做简单析取式. 仅由无限个文字形成的合取式称做简单合取式. 如,p, ┐q 等为一个文字形成简单析取式, p∨┐p,┐p∨q 等为2个文字形成的简单析取式, ┐p∨┐q∨r, p∨┐q∨r 等为3个文字形成的简单析取 式. 留意 ① 一个文字既是简单析取式,又是简单合取式. ② 为便利起见,有时用 A1 , A2 ,? As 暗示 s 个简单 析取式或 s 个简单合取式. 2.1 (1)一个简单析取式是沉言式当且仅当它同时含 有某个命题变项及它的否认式; (2)一个简单合取式是矛盾式当且仅当它同时含 有某个命题变项及它的否认式。 证明: 设 Ai 是含 n 个文字的简单析取式. 若 Ai 中既含有某个命题变项 Pj ,又含有它的 否认式 ?Pj ,由互换律、排中律和零律可知,Ai 为沉言式。 反之,若 Ai 为沉言式,则它必同时含某个命 题变项及它的否认式,不然,若将 Ai 中的不带 否认号的命题变项都取0,带否认号的命题变项 都取1,此赋值为 Ai 的成假赋值,这取 Ai 是沉 言式相矛盾。 雷同的会商可知,若 Ai 是含n个命题变项的 简单合取式,且 Ai 为矛盾式,则 Ai 中必同时含 有某个命题变项及它的否认式,反之亦然. 如:p∨┐p,p∨┐p∨r 都是沉言式. ┐p∨q,┐p∨┐q∨r 都不是沉言式. 二、范式 1、范式的定义 定义2.3 (1)由无限个简单合取式形成的析取式称为析取范式. (2)由无限个简单析取式形成的合取式称为合取范式. (3)析取范式取合取范式统称为范式. 设 Ai ( i ? 1,2,? , s ) 为简单的合取式,则 A ? A1 ? A2 ? ? ? As 为析取范式。 设 Ai ( i ? 1,2,? , s ) 为简单的析取式,则 A ? A1 ? A2 ? ? ? As 为合取范式. 2 、范式的性质 2.2 (1)一个析取范式是矛盾式当且仅当它的每个简单 合取式都是矛盾式. (2)一个合取范式是沉言式当且仅当它的每个简单 析取式都是沉言式. 2.3 (范式存正在)任一命题公式都存正在 着取之等值的析取范式取合取范式。 证明: (1) 由蕴涵等值式取等价等值式可知 A→B ? ┐A∨B A? B? (┐A∨B)∧(A∨┐B) (2.17) 因此正在等值的前提下,可消去任何公式中的联 结词→和?. (2) 用双沉否认律和德摩根律,可得 ┐┐A ? A ┐(A∧B) ? ┐A∨┐B ┐(A∨B) ?┐A∧┐B (3) 操纵分派律,可得 A∧(B∨C) ?(A∧B)∨(A∧C) A∨(B∧C) ?(A∨B)∧(A∨C) (2.19) (2.18) 由(2.17),(2.18),(2.19)3步,可将任一公 式化成取之等值的析取范式或合取范式. 3 、求范式的步调: (1) 消去联合词→ 、 ? (2) 否认号的消去(操纵双沉否认律)或内移(利 用德摩根律)。 (3) 操纵分派律:操纵∧对∨的分派律求析取范式, 操纵∨ 对∧的分派律求合取范式。 留意 为了清晰和无误,演算中操纵互换律,使得 每个简单析取式或合取式中命题变项的呈现都是 按字典挨次,这对下文中求从范式更为主要. 例2.7 求公式 (p→q) ? r 的析取范式取合取范式: 解:(1)先求合取范式 (p→q) ?r r ? (┐p∨q) ? (消去→) ) ? ((┐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)求析取范式 求析取范式取求合取范式的前两步是不异的,只 是正在操纵分派律时有所分歧。因此能够用(1)中前 四步的成果,接着进行∧对∨分派律演算。 (p→q) ?r ? ((p∧┐q)∨r)∧(┐p∨q∨┐r) ? (p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r) ∨(r∧┐p)∨(r∧q)∨(r∧┐r) ? (p∧┐q∧┐r)∨(┐p∧r)∨(q∧r) 正在以上演算中,从第二步到第三步是操纵矛盾律 和统一律。别的,第二步和第三步成果都是析取范式, 这正申明命题公式的析取范式是不独一的。同样,合 取范式也是不独一的。 上述范式不独一,下面逃求一种更严酷的范式 — 从范式,它是存正在且独一的。 三、范式的独一性——从范式 1、极小项(极大项) (1) 定义2.4 正在含有n个命题变项的简单合取式(简 单析取式)中,若每个命题变项和它的否认式分歧时 呈现,而二者之一必呈现且仅呈现一次,且第i个命题 变项或它的否认式呈现正在从左算起的第i位上(若命题 变项无角标,就按字典挨次陈列),称如许的简单合 取式(简单析取式)为极小项(极大项). (2) 因为每个命题变项正在极小项中以原形或否认式 形式呈现且仅呈现一次,因此n个命题变项共可发生2n 个分歧的极小项. (3) 每个极小项都有且仅有一个成实赋值. 若成实赋值所对应的二进制数转换为十进制数 i , 就将所对应极小项记做 mi . 雷同地,n个命题变项共可发生2n个极大项,每 个极大项只要一个成假赋值,将其对应的十进制数 i 做极大项的角标,记做 M i . (4) 表2.3 p, q构成的极小项取极大项 表2.4 p, q, r 构成的极小项取极大项 (5) 极小项取极大项的关系。 2.4 设 mi 取 M i 是命题变项 P1 , P2 ,? , Pn 构成的极小项和极大项,则 ?mi ? M i , ?M i ? mi . 2 、从范式 (1) 定义2.5 设由n个命题变项形成的析取范式(合取范式)中 所有的简单合取式(简单析取式)都是极小项(极大 项),则称该析取范式(合取范式)为从析取范式 (从合取范式). (2) 从范式的存正在性和独一性 2.5 任何命题公式都存正在着取之等值的从析取范 式和从合取范式,而且是独一的. 证明: 这里只证从析取范式的存正在和独一性. 起首证明存正在性. 设A是任一含n个命题变项的 公式. 由2.3可知,存正在取A等值的析取范式 A,即A ? A,若A的某个简单合取式 Ai中既不 含命题变项 Pj ,也不含┐ Pj,则将 Ai展成如下形 式: Ai ? Ai ? 1 ? Ai ? ( Pj ? ?Pj ) ? ( Ai ? Pj ) ? ( Ai ? ?Pj ) 继续下去,曲到所有的简单合取式都含肆意命题变 项或它的否认式. 若正在演算过程中反复呈现的命题变项以及极小 项和矛盾式时,都应“消去”:最初就将A化成取 之等值的从析取范式A。 下面再证明独一性。假设某一命题公式A存正在两 个取之等值的从析取范式B和C,即A ? B且A ?C, 则B ? C。因为B和C是分歧的从析取范式,不妨设 极小项mi只呈现正在B中而不呈现正在C中。于是,角标 i 的二进制暗示为B的成实赋值,而为C的成假赋值. 这取B ? C矛盾,因此B取C必不异。 从合取范式的存正在独一性可雷同证明. 正在证明2.5的过程中,曾经给出了求从析取 范式的步调. 为了夺目和便于回忆,求出某公式 的从析取范式(从合取范式)后,将极小项(极 大项)都用名称写出,而且按极小项(极大项) 名称的角标由小到大挨次陈列. 例2.7 例2.8 求公式 (p→q) ? r从析取范式和从合取范式. 解:(1)求从析取范式. 正在例2.7中已给出的公式的析取范式,即 ? (p→q) r ? (p∧┐q∧┐r)∨(┐p∧r)∨(q∧r) 正在此析取范式中,简单合取式┐p∧r,q∧r都 不是极小项。下面别离求出它们派生的极小项。 留意,由于公式含三个命题变项,所以极小项 均由三个文字构成。 (┐p∧r) ? ┐p∧(┐q∨q)∧r ? (┐p∧┐q∧r)∨(┐p∧q∧r) ? m1 ? m3 q∧r ? (┐p∨p)∧q∧r ? (┐p∧q∧r)∨(p∧q∧r) ? m 3 ? m7 而简单合取式p∧┐q∧┐r已是极小项 (p→q)?r ? m1 ? m3 ? m4 ? m7 m4. 于是 (2) 再求从合取范式. 由例2.7已求出公式的合取范式,即 (p→q) r ? ? (p∨r)∧(┐q∨r)∧(┐p∨q∨┐r) 此中简单析取式(┐p∨q∨┐r)已是极大项 M5. 操纵矛盾律和统一律将不是极大项的简单析取式 化成极大项. (p∨r) ? (p∨(q∧┐q)∨r) ? (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 ? M 0 ? M 2 ? M 5 ? M 6 记住次要步调和法则当前,能够很快的求出 公式的从析取范式和从合取范式. 例2.9 求命题公式p→q的从析取范式和从合取范式. 解: 本公式中含两个命题变项,所以极小项和极大 项均只含两个文字. (1) p→q ? ┐p∨q ? M 2 (从合取范式) (2) p→q ? ┐p∨q ? ┐p∧(┐q∨q)∨(┐p∨p)∧q ? (┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) ? (┐p∧┐q)∨(┐p∧q)∨(p∧q) ? m0 ? m1 ? m3 (从析取范式) 留意 由例2.8取2.9可知,正在求给定公式的从析取范 式(从合取范式)时,必然按照公式中命题变项 的个数决定极小项(极大项)中文字的个数. 3、从范式的使用 (1) 求公式的成实和成假赋值 成实赋值:从析取范式的极小项的下标对应的 二进制暗示的值; 成假赋值:从合取范式的极大项的下标对应的 二进制暗示的值。 (2)判断公式的类型 沉言式:从析取范式有 2n 个极小项; 矛盾式:从合取范式有 2n 个极大项; 可满脚式:从析取范式中到少有一个极小项。 (3)判断两个命题公式能否等值 两公式等价当且仅当它们有不异从范式。 (4) 处理现实问题 例2.12 某科研所要从3名科研A,B,C中 选出1~2名出国.因为工做的需要,选派是要满 脚以下前提: (1) 若A去,则C同去. (2) 若B去,则C不克不及去. (3) 若C不去,则A或B能够去. 问所里应若何选派他们? ij 四、几点留意 1. 由公式的从析取范式求从合取范式 设公式A含n个命题变项, A的从析取范式含s(0s2n) 个极小项,即 A ? mi1 ? mi2 ? ? ? mis 0 ? i j ? 2n ? 1, j ? 1,2,?, s 没呈现的极小项为 m j1 , m j2 ,? , m j2n , s 它们的角标的 ? 二进制暗示为┐A的成实赋值,因此┐A的从析取 范式为 ┐A = m j1 ? m j2 ? ? ? m j n 2 ?s 由2.4可知 A ? ┐┐A ? ?( m j1 ? m j2 ? ? ? m j2n ? s ) ? ?m j1 ? ?m j2 ? ? ? ?m j2n ? s ? M j1 ? M j2 ? ? ? M j n 2 ?s 于是,由公式的从析取范式,即可求出它的从合取 范式。 例2.13 由公式的从析取范式,求从合取范式: (1) A ? m1∨m2 ( A中含两个命题变项p, q ) (2) B ?m1∨m2∨m3 ( B中含两个命题变项p, q, r ) 解 (1) 由题可知,没呈现正在从析取范式中的 极小项为 m0 和 m3,所以A的从合取范式中含两个 极大项 M 0 和 M 3 ,故 A ? M0 ? M3 . (2) B 的从析取范式中没呈现的极小项为 m0 , m4 , m5 , m6 , m7 , 因此 B ? M 0 ? M 4 ? M 5 ? M 6 ? M 7 . 反之,由公式的从合取范式,也能够确定从析取范式. 2.沉言式取矛盾式的从合取范式 ① 矛盾式无成实赋值,因此矛盾式的从合取范 式含n 个极大项. (n为公式中命题变项个数) 2 ② 沉言式无成假赋值,因此从合取范式不含任 何极大项. 将沉言式的从合取范式记为1. 3.从析取范式有几多种分歧的环境 含n个命题变项的所有无限多合式公式中,它们 等值的从析取范式(从合取范式)共有几多种分歧的 环境? n个命题变项可发生 2n 个极小项(极大项), 因此共可发生 C ? C ??? C 0 2n 1 2n 2n 2n ?2 2n 种分歧的从析取范式(从合取范式),由2.5 可知,含n个命题变项的所有公式的从析取范式 (从合取范式)最多有 2 2n 种不怜悯况. 能够看出: A ? B 当且仅当A取B有不异的实值表, 当且仅当A取B有不异的从析取范式(从合取范式) 因此能够如许说,实值表取从析取范式(从合取 范式)是描述命题公式尺度形式的两种分歧的等价形式。 功课: P39—42 5.(3) 6.(3) 7.(2) 13