3.命题逻辑3.1命题的有关概念1.命题2.原子命题(简单命题)3.doc

教 学 内 容 教学设计长春工业大学离散数学课程讲稿3命题逻辑3.1 命题的有关概念1命题命题的有关概念和逻辑联结词命题逻辑推理命题公式等值命题公式范式析取范式合取范式工具真值表主析取范式主合取范式2原子命题（简单命题）3复合命题4逻辑常量5逻辑变量3.2逻辑联结词1否定联结词2合取联结词3析取联结词4蕴涵联结词5等价联结词6异或联结词7与非联结词8或非联结词9条件否定联结词3.3命题公式及其真值表1命题公式的定义2命题的符号化3命题公式的真值表4命题公式的类型3.4逻辑等值的命题公式1逻辑等值的定义2基本等值式3等值演算法4对偶原理3.5 命题公式的范式1命题公式的析取范及合取范式2命题公式的主析取范及主合取范式3.6联结词集合的功能完备性（自学）3.7命题逻辑中的推理1推理形式有效性的定义2基本推理规则3命题逻辑的自然推理系统25【提出问题1】有一逻辑学家误入某部落，被拘于牢狱，酋长意欲放行，他对逻辑学家说：“今有两门，一为自由，一为死亡，你可任意开启一门。为协助你逃脱，今加派两名战士负责解答你所提的问题。惟可虑者，此两战士中一名天性诚实，一名说谎成性，今后生死由你自己选择。”逻辑学家沉思片刻，即向一战士发问，然后开门从容离去。该逻辑学家应如何发问？逻辑学家手指一门问身旁的一名战士说：“这扇门是死亡门，他（指另一名战士）将回答是，对吗？”当被问战士回答“对”，则逻辑学家开启所指的门从容离去。当被问的战士回答“否”，则逻辑学家开启另一扇门从容离去。PQRS0011010010011110事实上，如果被问者是诚实战士，他回答“对”。则另一名战士是说谎战士，他回答“是”，那么，这扇门不是死亡门。如果被问战士是诚实战士，他回答“否”。则另一名战士是说谎战士，他回答“不是”，那么，这扇门是死亡门。如果被问者是说谎战士，可以类似分析。设P：被问战士是诚实人。 Q：被问战士的回答是“对”。 R：另一名战士的回答是“是”。 S：这扇门是死亡门。【提出问题2】一家航空公司，为了保证安全，用计算机复核飞行计划。每台计算机能给出飞行计划正确或者有误的回答。由于计算机也有可能发生故障，因此采用三台计算机同时复核。由所给答案，根据“少数服从多数”的原则作出判断。试将结果用公式表示，并加以简化，画出电路图。设C1，C2，C3分别表示三台计算机的答案，S表示判断结果，根据题意其的真值表如下。S=（C1C2C3）（C1C2C3）（C1C2C3）（C1C2C3） =（C2C3）（C1C3）（C1C2）SC3C2C1C1C2C3S00000010010001111000101111011111逻辑学是研究思维形式及思维规律尤其是推理的学科, 早在两千多年前就受到人们的重视, 古希腊著名逻辑学家亚里士多德(Aristotle, 公元前384公元前322)是形式逻辑的创始人。德国数学家、哲学家莱布尼茨(G. Leibniz, 16471716)首先提出用数学方法研究逻辑,就是建立一套表意符号体系,在符号之间进行形式推理. 莱布尼茨是数理逻辑的创始人. 也正因为这样, 数理逻辑又称为符号逻辑。u 逻辑推理无处不在, 从日常生活中的实际问题的解决到数学定理的证明以及程序正确性验证.u 除了传统的数理逻辑(内容包括逻辑演算、公理化集合论、模型论、递归论和证明论)外,还出现了各种各样的应用逻辑,如多值逻辑、模态逻辑、归纳逻辑、时序逻辑、动态逻辑、模糊逻辑、非单调逻辑、缺省逻辑、算法逻辑及程序逻辑等, 这些都与计算机科学密切相关.u 命题逻辑与谓词逻辑是数理逻辑的基础部分.u 计算机的计算过程就是推理过程,而每一步推理离不开判断,判断的对象就是命题.我现在年纪大了，搞了这么多年的软件，错误不知犯了多少，现在觉悟了，我想，假如，我早年在数理逻辑上好好下点工夫的话，我就不会犯这么多的错误，不少东西逻辑学家早就说过了，可是我不知道，要是我年轻20岁的话，就回去学逻辑学。 Dijkstra警世名言3.1 命题的有关概念1. 命题 命题是能判断出真假的语句.如何理解命题?必须是一个完整的句子，包括用数学式子表达；语句必须具有真假意义（有对错之分）；祈使句、疑问句和感叹句不具有真假意义。语句具有真假意义，一般是陈述句.【例】判断下列语句是否是命题(1)2 + 3 = 5.(2)大熊猫产在我国东北.(3)x 3.(4)立正！(5)这朵花真漂亮！(6)你喜欢网络游戏吗?(7)火星上有生物.(8)我说的都是假话.(9)小王和小李是同学.(10)你只有刻苦学习,才能取得好成绩.2.命题的真值命题的真值就是命题的逻辑取值. 经典逻辑值只有两个: 1和0。它们是表示事物状态的两个量. 若一个命题是真命题,其真值为1; 若一个命题是假命题, 其真值为0. 在计算机专业课程中, 将逻辑真用1表示, 逻辑假用0表示. 在电路中通常规定, 1表示开关处于接通状态, 0表示开关处于断开状态；三极管饱和用1表示, 三极管截止用0表示；在电路分析和设计时规定, 1表示高于逻辑高电平信号, 0表示逻辑低电平信号等；在数理逻辑中, 逻辑真是用T(True), 逻辑假用F(False)表示的。3. 原子命题与复合命题【原子命题】也称简单命题。是指一个命题不包含有更小的命题。命题逻辑研究的基本单位；原子命题不能再分解为更为简单的命题，即不能拆分；通常用小写英文字母p, q, r, s,或带下标p1, p2, p3, 等来表示。例上例中, (1)(2)(7)(9)是原子命题。【复合命题】一个命题包含有更小的命题。复合命题是由原子命题构成，可以分解为更为简单的命题，即可以拆分；要想表达复合命题，需用逻辑联结词，即给定原子命题，使用逻辑联结词可以构成一个复合命题。例上例(10)是复合命题, 它包含有两个原子命题“你刻苦学习”和“你取得好成绩”. 4.逻辑常量与逻辑变量1和0称为逻辑常量；逻辑表达式中出现的p, q, r, s,或p1, p2, p3, 等称为命题变元或逻辑变量. 命题变元可以代表任意命题, 从取值的角度看, 命题变元既可以取1又可以取0.原子命题通过逻辑联结词构成复合命题。逻辑联结词就是逻辑运算。有一元和二元。3.2 逻辑联结词1. 否定联结词（p）【定义】设p是一个命题，联结词 和命题p构成p的否定复合命题p。读作“非p”。否定联结词是一元逻辑运算；p是数理逻辑中的标准符号, 也可记为p；C语言!p, 在计算机其他课程中用p 表示, 对应于门电路的“非门”。p p1 00 1其运算表：例 p: 2 + 3 = 5, 而 p : 2 + 3 5. 2. 合取联结词 （p q）【定义】设p，q是一个命题，联结词 和命题p和q构成p和q的合取复合命题p q。读作“p合取q”。合取“”相当于“并且”, “和”, “与”, “以及”、“不但且”、“虽然但是”等。在数理逻辑中, 合取联结词可以将任意两个命题联结起来以构造出新的命题。 并非所有的“和”都有合取之意。如“小王和小李是同学”中的“和”并没有合取之意。合取“”逻辑联结词是二元逻辑运算。C语言&，在计算机其他课程中用表示，门电路为“与门”。p q p q0 0 00 1 01 0 01 1 1其运算表：例p: 小李能歌, q :小李善舞.而p q :小李能歌且善舞.3. 析取联结词（p q）【定义】设p，q是一个命题，联结词 和命题p和q构成p和q的合取复合命题p q。读作“p析取q”。析取“”相当于“或者”。在数理逻辑中, 析取联结词可以将任意两个命题联结起来以构造出新的命题。自然语言中的“或”可能是“可兼或”，也可能是“不可兼或”（排斥或），而析取表达的是可兼或。析取“”逻辑联结词是二元逻辑运算。C语言|，在计算机其他课程中用+表示，门电路为“或门”。p q p q0 0 00 1 11 0 11 1 1其运算表：例 p: 这学期我选修人工智能课程, q: 这学期我选修模式识别课程 .p q: 这学期我选修人工智能课程或者模式识别课程 .4. 异或联结词p q“可兼或”, 它表示两者可同时为真, 用析取表示即可；“不可兼或”,它表示两者不能同时为真,换句话说, 两者同时为真是假命题. 这就需要异或联结词.【定义】设p，q是一个命题，联结词 和命题p和q构成p和q的异或复合命题p q。读作“p异或q”。异或“”相当于“或者”。在数理逻辑中, 异或联结词可以将任意两个命题联结起来以构造出新的命题。自然语言中的“或”可能是“可兼或”，也可能是“不可兼或”（排斥或），而析取表达的是不可兼或。异或“”逻辑联结词是二元逻辑运算。p q p q0 0 00 1 11 0 11 1 0其运算表：例p: 明天去深圳的飞机是上午八点起飞, q :明天去深圳的飞机是上午八点半起飞.p q: 明天去深圳的飞机是上午八点半起飞 .5. 蕴涵联结词 p qp q中前件为假，无论后件真假，命题均为真。与自然语言表达有出入。【定义】设p，q是一个命题，联结词和命题p和q构成p和q的蕴涵复合命题p q。读作“p蕴涵q”。“”相当于“如果那么”, “若则”等.是二元逻辑运算。在数理逻辑中, 蕴涵联结词可以将任意两个命题联结起来以构造出新的命题。在p q中，p为前件，q为后件，只有当前假为真，后件为假时，命题为假。p q p q0 0 10 1 11 0 01 1 1其运算表：6. 等价联结词 p qp q中前件为假，无论后件真假，命题均为真。与自然语言表达有出入。【定义】设p，q是一个命题，联结词和命题p和q构成p和q的蕴涵复合命题p q。读作“p等价q”。“”相当于“当且仅当”, “充分必要条件”等.是二元逻辑运算。在数理逻辑中, 等价联结词可以将任意两个命题联结起来以构造出新的命题。在p q中，只有当p、q同真、同假时复合命合命题才为真。在数字逻辑等课程中, 等价联结词称为“同”,并用“”符号表示.“p当且仅当q”有两层含义：(1) “p当q”是指q p. (2) “p仅当q”是指p q. 等价联结词也称为双蕴涵联结词或双条件联结词。p q p q0 0 10 1 01 0 01 1 1其运算表：例 p: 四边形是平行四边形, q :四边形的对边平行 .p q :四边形是平行四边形当且仅当四边形的对边平行.7. 与非联结词 p q【定义】设p，q是一个命题，联结词和命题p和q构成p和q的与非复合命题p q。读作“p与非q”。是二元逻辑运算。在数理逻辑中, 与非联结词可以将任意两个命题联结起来以构造出新的命题。p q p q0 0 10 1 11 0 11 1 0其运算表：8. 或非联结词p q【定义】设p，q是一个命题，联结词和命题p和q构成p和q的或非复合命题p q。读作“p或非q”。是二元逻辑运算。在数理逻辑中, 或非联结词可以将任意两个命题联结起来以构造出新的命题。p q p q0 0 10 1 01 0 01 1 0其运算表：pqn9. 条件否定联结词pqn 是二元逻辑运算。 在数理逻辑中, 条件否定联结词可以将任意两个命题联结起来以构造出新的命题。p q0 0 10 1 01 0 01 1 0pqn其运算表：3.3 命题公式及其真值表命题逻辑的符号体系。1.命题公式的定义命题公式是由命题常量、命题变元、逻辑联结词、左圆括号(及由圆括号)构成的有意义)的符号串, 其严格定义可借助于递归定义方式给出。命题公式就是逻辑函数或逻辑表达式, 其中的常量是逻辑常量1和0, 其中的变元是命题变元或逻辑变量.【定义】命题公式按下列方法生成：命题常量1和0以及命题变元是命题公式。若A是命题公式，则（A）是命题公式。若A和B是命题公式，则（AB）、（AB）、（AB）、（AB）、（AB）、ABqn（AB）、（AB）、（ ）是命题公式。有限次应用(1)(2)(3)所得到的符号串是仅有的命题公式. 命题公式可称为合式公式或简称为公式,其全称为命题合式公式. 该处公式实际上是书写正确、含义清楚的表达式或者说符号串,与以前所说公式不尽相同。关于括号约定：严格按照命题公式的定义,就会出现很多的括号. 一方面,这些括号使命题公式的结构清晰、含义清楚；而另一方面,括号太多给命题公式的阅读和书写带来不便. 因此,特作如下一些可以省略括号的约定:(1)最外层的括号可以省略. ABqn (2) 9个联结词运算的优先顺序依次为: 、 (3)同级运算从左至右依次进行。2.命题的符号化用一组基本的指令来编制一个计算机程序，类似于从一组公理来构造一个数学证明。 D.E.Knuth命题的符号化就是使用符号命题变元、逻辑联结词和括号将所给出的命题表示出来. 一方面说明, 符号体系来源于实际问题,另一方面也是给出进一步学习逻辑演算系统的语义解释时的一种标准模型。自然语言的形式过程：1 确定给定句子是否是命题；2 句子中连词是否为命题联结词；3 要正确地表示原子命题和适当选择命题联结词。命题的符号化的步骤Step 1 找出所给命题的所有原子命题，并用小写英文字母或带下标表示；Step 2 确定应使用的联结词，进而将原命题用符号表示出来。例 将下列命题符号化.(1)天气很好或很热.(2)如果张三和李四都不去,那么我就去.(3)仅当你走, 我留下.(4)我今天进城, 除非天下雨.(5)你只有刻苦学习, 才能取得好成绩3.命题公式的真值表对于命题公式，若对中出现的每个命题变元都指定一个真值1或者0，就对命题公式A进行了一种真值指派或一个解释，而在该指派下会求出公式A的一个真值，将A的所有可能的真值指派以及在每一个真值指派下的取值列成一个表，就得到命题公式A的真值表。要求大家能准确写出一个命题公式的真值表,这是本节的重点内容。例 写出命题公式（pq）r 的真值表.联结词的运算表是此部分内容的基础。【结论】一般来说，含n个命题变元的命题公式的不同的真值指派有2n种。4.命题公式的类型【定义】(1)在任何指派下均取真的命题公式称为永真式或重言式；(2)在任何指派下均取假的命题公式称为永假式或矛盾式；(3)至少有一种指派使其为真的命题公式称为可满足式；(4)至少有一种指派使其为真同时至少有一种指派使其为假的命题公式称为中性式。如何判断一个命题公式的类型？真值表，取值法，逻辑等值演算命题公式可满足式永假式永真式中性式【命题公式的分类】例证明：命题公式(pq)(pq)是永真式。pqpq pq(pq)(pq)11111100010111100111解取值法证明AB永真。由A真推出B真或由B假推出A假，则AB永真。同时也意味着A真B假的情况不可能出现。由真值表可知，命题公式是永真式。例证明：命题公式(p(pq)q是永真式。证明假设p(pq)取真，则p和 pq均取真，而p为真，则q为真，因此原命题为永真式。【定理】（永真式代入定理）设命题公式A（p1，p2，pn）为永真式，则分别用命题公式B1，B2，Bn替换A中的命题变元p1，p2，pn所得到的命题公式是永真式。3.4 逻辑等值的命题公式1逻辑等值的定义=可用代替。【定义】给定两个命题公式A和B，若在任何真值指派下A和B的真值都相同，则称命题公式A和B逻辑等价或逻辑等值或简称为等值或相等，记为 A = B。= 或 与的区别：前是关系符号，后者是运算符号。【定理】 设A和B是命题公式，则A = B的充要条件是A B永真。【定理】若A1（p1，p2，pn）= A2（p1，p2，pn），在A1和A2中分别用命题公式B1，B2，Bn代替p1，p2，pn所得到的两个命题公式等值。【定理】命题公式间的等值关系是等价关系：对于任意命题公式A，B，C有：(1)自反性：A=A。(2)对称性：若A=B则B=A。(3)传递性：若A=B，B=C，则A=C。例证明：对于任意命题公式A和B，有A B = （AB）（AB）。【思考？】用真值表法可以判断任何两个命题公式是否等值，但当命题变项较多时，工作量是很大的。我们先用真值表验证一组基本的又是重要的等值式，以它们为基础进行公式之间的演算，来判断公式之间是否等值。2基本等值式(AB) C = A (BC)(AB)CA(BC)1）双重否定律A =A2）结合律(AB) C = A(BC)(AB) C = A(BC)AB= BAABBA 3）交换律AB = BAAB= BAA(BC) = (AB)(AC)A (BC)(AB) (AC)4）分配律A(BC) = (AB)(AC)A(BC) = (AB)(AC)AA = TAA= T5）幂等律(恒等律、重叠律)AA = AAA = A (AB) = AB (AB) =AB = AB=(AB)(AB)6）吸收律A(AB) = AA(AB) = AA0 = A 0A = A 各等值式都是用元语言符号书写的称这样的等值式为等值式模式，每个等值式模式都给出了无穷多个同类型的具体的等值式。7）德摩根律 (AB) = AA（AB) = AB 8）同一律A0 =AA1 =A1A = A0A = AA1 = 10A = 1运算时用AB来表示AB方便。问题是这种表示丢失了A、B间的因果关系。AA = AAA = AAA = 09）零律A1 = 1A0 = 010）补余律AA = 1AA = 011）AB = AB 12) AB = BA 如将AB视为正定理, 那么BA就是相应的逆否定理, 它们必然同时为真, 同时为假。13) A (BC) = (AB)CA是(BC)的前提, B是C的前提, 于是可将两个前提的合取AB作为总的前提。 即如果A则如果B则C, 等价于如果A与B则C。14) AB = (AB)(AB)基本等值式在化简命题公式、判断命题公式的类型、证明等值式、计算命题公式的范式、命题逻辑中的推理等中均有体现。这可解释为AB为真, 有两种可能的情形, 即(AB)为真或(AB)为真。而AB为真, 必是在A = B = 1的情况下出现, AB为真, 必是在A = B = 0的情况下出现。从而可说, AB为真, 是在A、B同时为真或同时为假时成立。这就是从取真来描述这等式。15) AB = (AB)(AB)这可解释为AB为假, 有两种可能的情形, 即(AB)为假或(AB)为假, 而AB为假, 必是在A = 0，B = 1的情况下出现, AB为假, 必是在A = 1, B = 0的情况下出现。从而可说AB为假, 是在A真B假或A假B真时成立。这就是从取假来描述这等式。16) AB = (AB)(BA) 这表明AB成立, 等价于正定理AB和逆定理BA都成立。17) A(BC) = B(AC)前提条件A、B可交换次序。18) (AC) (BC)=(AB)C左端说明的是由A而且由B都有C成立。从而可以说由A或B就有C成立, 这就是等式右端。3等值演算法【定理】（等值置换定理）设C是命题公式A的子公式，若C = D，则将A中的C部分或全部替换为D所得到的命题公式与A等值。【等值演算法】利用基本等值式以及等值置换定理求解问题的方法。【例】利用等值演算，化简命题公式设A, B, C是任意的命题公式, 化简命题公式并将最后结果用只含和表示。（A（BC）AB AB(CA)【例】利用等值演算法, 判断一个命题公式的类型设A, B, C是任意的命题公式，判断下列命题公式的类型。（A（BC）(AB）C） A（ABC）【例】利用等值演算，证明两个命题公式等值设A, B, C是任意的命题公式,证明下列等值式. （AB）=(AB）（AB） A（BC）=（AB）C4对偶原理【定义】设命题公式A中只含有3个逻辑联结词, , , 将A中的换成 ；A中的换成 ；A中的1换成0；A中的0换成1, 所得到的命题公式称为是A的对偶式, 记为A*。【对偶原理】 设A和B是命题公式, 若A = B, 则A* = B*.【等值演算举例】由已知的等值式可以推演出更多的等值式，我们称由已知的等值式推演出另外一些等值式的过程称为等值演算。等值演算是布尔代数或逻辑代数的重要的组成部分。在等值演算的过程中，我们要不断使用等值置换定理。证明：(P(QR)(QR)(PR) = R证明左端= (P(QR)(QP)R) (分配律)=(PQ)R)(QP)R) (结合律)=( (PQ)R)(QP)R) (摩根律)=( (PQ)(QP)R (分配律)=( (PQ)(PQ)R (交换律)=1R (置 换)=R (同一律)上面的例子说明，用等值演算法可以验证两个公式等值。但一般情况下，不能用等值演算法直接验证两个公式不等值。我们看下面的例子。例题2 证明：(PQ)RP(QR)解：方法一：真值表法。方法二：取值法。易知，010是(PQ)R的成假解释，而010是P(QR)的成真解释，所以原不等式成立。方法三：设A = (PQ)R，B = P(QR)先将A，B通过等值演算化成容易观察真值的情况，再进行判断。A = (PQ)R = (PQ)R （蕴涵等值式）= (PQ)R （蕴涵等值式）= (PQ)R （摩根律）B = P(QR)= P(QR) （蕴涵等值式）= PQR （结合律）容易观察到，000，010是A的成假赋值，而它们是B的成真赋值。例题3试证： (PQ) (P(QR)(PQ)(PR) = T证明左端=(PQ)(P(QR)(PQ)(PR) (德摩根律)=(PQ)(PQ)(PR)(PQ)(PR) (分配律)=(PQ)(PR)(PQ)(PR) (等幂律)=1 (代 入)从例中可看出，一个命题公式的表示形式并不是唯一的，可以有多种不同的表达式，通过等值演算可以寻求出最简单的逻辑表达式。这在数字电路中，当电路的功能明确后，如何寻求简单而又可靠的电子线路，提供了有力的手段。命题公式与真值表的关系对任一依赖于命题变元P1Pn的命题公式A来说, 可根据P1Pn的真值给出A的真值, 从而建立起由P1Pn到A的真值表。这个由公式列写真值表的过程是容易的。反过来，若给定了由P1Pn到A的真值表, 是否可以写出命题公式A对P1Pn的逻辑表达式呢? 回答是肯定的。 从上图看B的真值F, 如何依赖于P、Q的真值。在图中的第三、第四行，B值为F。即B取F两种可能的情形, 或第一种情形, 或第二种情形。从而有B = ()1()2 进而分析每种使B为假的情形。第一种情形是P = T Q = F出现, 也即PQ为假, 于是可将()1写成(PQ)。同理()2写成(PQ)。于是得B = (PQ)(PQ)同样可得A = (PQ)要注意的是这两种列写公式的区别, 首先是区分从T还是从F来列写, 分别得到()()() 形和()()()形的不同结构。再者, 在填写文字P、Q时, 何时加否定也是有区别的。再有当列写公式C时, 因上2.3.1中对解释P、Q = T, T时, C取何值可任意, 或说C与P, Q = T, T无关, 这时可适当选取C的真值, 以使C的表达式简单。例如有上图所示的真值表, 可列写出A, B由P、Q表达的公式来。一、从1来列写看A的真值1, 如何依赖于P、Q的真值。在图中的第一、第二和第四行，A值为1。即A取1有三种可能的情形, 或第一种情形, 或第二种情形, 或第三种情形。从而有A = ()1 ()2 ()3 进而分析每种使A为真的情形。第一种情形是P = 0， Q = 0同时出现, 也即PQ出现(为真)。于是可将()1写成(PQ)。同理()2和()3应分别写成(PQ)和(PQ)。于是得A = (PQ)(PQ)(PQ)同样可得B = (PQ)(PQ)考虑到对A来说, 取1的解释个数(为3)多于取0的解释个数(为1), 自然在真值表中补上A列为好, 以便对A列写A = PQ便可得A = (PQ)二、从0来列写（自己总结）3.5 命题公式的范式【分析问题】给定一个命题公式，根据真值表显然可以方便地得出其在每种指派下的真值，从理论上讲，这是一个能行可判定问题. 但随着所给公式中命题变元个数的增加，在实际计算中就变成不可行的了，如含100个命题变元的命题公式其真值指派就有2100种。一个命题公式有各种形式的与其等值的命题公式，在它们中间欲找到一种标准形式或规范形式，也就是命题公式的范式，使其不用写出真值表就能确定在何真值指派下取真以及在何真值指派下取假。3.5.1 命题公式的析取范式及合取范式1析取范式及合取范式的定义 【定义】析取范式设A是命题公式, 若A = A1 A2 An (n 1), 其中Ai(1 i n)是由命题变元或其否定组成的合取式, 则称A1 A2 An为A的析取范式. 注意Ai(1 i n)是由命题变元或其否定组成的合取式，也可以单个命题变元或其否定，并满足在每个中Ai中，命题变元及其否定不同时出现；命题变元或其否定按字典顺序出现或按下标从小到顺序出现；相同的合取式不重复出现。如：Ai= p q r； p q； q r； q； r ？（p q） （p q）= p qn = 1，单个由命题变元或其否定组成的合取式看成一个整体是命题公式A的析取范式。如：A = p q r = (p q r ).【定义】合取范式设A是命题公式, 若A = A1 A2 An (n 1), 其中Ai(1 i n)是由命题变元或其否定组成的析取式, 则称A1 A2 An为A的合取范式. 注意Ai(1 i n)是由命题变元或其否定组成的析取式，也可以单个命题变元或其否定，并满足在每个中Ai中，命题变元及其否定不同时出现；命题变元或其否定按字典顺序出现或按下标从小到顺序出现；相同的析取式不重复出现。如：Ai= p q r, p q, q r, q, r ?（p q）（p q）=（p q）n = 1，单个由命题变元或其否定组成的合取式看成一个整体是命题公式A的析取范式。如： A = p q r = (p q r ).若A = p q r , 则p q r也是A的析取范式。2析取范式及合取范式的计算步骤计算命题公式的析取范式及合取范式的主要步骤如下：Step1 使用等值式, 将命题公式中的联结词归约为, , ；Step2 利用De Morgan律将移到命题变元的前面；Step3 根据分配律得到命题公式的析取范式及合取范式：A(BC) = (AB)(AC)(求析取范式用).求命题公式的析取范式及合取范式的Step1和Step2是相同。A(BC) = (AB)(AC)(求合取范式用).【例】 设p, q和r是命题变元,求命题公式A = (p q) r的析取范式及合取范式.解3析取范式及合取范式的应用应用1确定真值指派根据命题公式的析取范式及合取范式可以得出该命题公式取真、假的指派例1 给出析取范式A=（pqr）(pr)(qr）取真的指派；给出合取范式A=(pr)(qr)(pqr)取真的指派；例2从p, q, r, s四人中选派2人出差,求满足下列3个条件的选派方法有哪几种.(1)若p去,则r和s中只去1人；(2)q和r不能都去；(3)若r去, 则s不能去.解p: p去出差, q: q去出差, r: r去出差, s: s去出差,则(1)prs;(2) (qr)；(3) rs同时成立。即：A= （prs）（(qr)） （rs）3.5.2 命题公式的主析取范式及主合取范式提出问题一个命题公式的析取范式及合取范式不是唯一的.如A = (p q) (p q) = p都是A的析取范式. 这种不唯一, 给有些问题的讨论带来不便. 解决方案 给定命题公式的唯一的标准形式：主析取范式以及主合取范式.1主析取范式【定义】 最小项对于给定的命题变元,若由命题变元或其否定组成的合取式满足(1) 每个命题变元或其否定二者之一只出现一次；(2)按字典顺序或按下标从小到大顺序出现, 称这样的合取式为