统计&信计课件 1-2 命题逻辑.pptx

复习思考题11.符号化命题符号化命题:(1)派小王或小李中的一人去开会派小王或小李中的一人去开会3)经一事，长一智；并且不经一事，不长一智经一事，长一智；并且不经一事，不长一智2.命题公式共有命题公式共有_、_和和_三种类型三种类型3.3.公式公式 p p属于属于_类型类型4.公式公式(p q ) r 属于属于_类型类型5.4个命题变项共有个命题变项共有_种不同的赋值种不同的赋值复习思考题1n三位客人坐在餐馆，三位客人坐在餐馆，服务生：服务生：“每个人都要咖啡吗？每个人都要咖啡吗？”第一位客人：第一位客人：“我不知道我不知道第二位客人：第二位客人：“我不知道我不知道第三位客人：第三位客人：“不是每个人都要咖啡不是每个人都要咖啡一会儿，服务生回来，将咖啡递给需要的一会儿，服务生回来，将咖啡递给需要的客人请问服务生是如何判断哪位客人需客人请问服务生是如何判断哪位客人需要咖啡的？要咖啡的？第1章命题逻辑1.1命题符号化及联结词1.2命题公式及分类1.3等值演算1.4范式1.5联结词全功能集1.7推理理论u每个命题变每个命题变项在真值表中都项在真值表中都有有1、0两种可能，两种可能，u故两个命题变项共有故两个命题变项共有22=4种不同的可能赋值，种不同的可能赋值，u而每个赋值在公式中对应的而每个赋值在公式中对应的非非0即即1，即有，即有个不个不同的真值表，同的真值表，pq公式001或0011或0101或0111或0真值函数n问题问题: 含含2个个命题变项的所有公式共产生多少个命题变项的所有公式共产生多少个互互不不相同相同的的真值表？真值表？p q0001101100000000000011110011001101010101p q0001101111111111000011110011001101010101二元真值函数对应的真值表真值函数 nn元真值元真值函数函数F F :0,1n0,1即即定义域为定义域为00,01,11，值域值域为为0,1n共有共有个个n元真值函数元真值函数.n对对于于任任何何一一个个含含n个个命命题题变变项项的的公公式式A，都都存在惟一存在惟一的一个的一个n元真值元真值函数为函数为A的的真值表真值表n等值的公式对应的真值函数等值的公式对应的真值函数相同相同。

1.3等值演算n命题之间的等价关系n设设A和和B是两个命题公式，是两个命题公式， 若若等价式等价式AB是重言式是重言式， 则则称称A与与B等值 记为记为AB，并称并称AB是是等值等值式n如：p pn注意：是关系符，是关系符，是联结词是联结词n用真值表可验证两个公式是否用真值表可验证两个公式是否等值 A B AB000110111001例1.8判断下列命题公式是否等值？(1)(p q )与 p q (2)( p q )与 p q p q 0 0 0 1 1 0 1 1p11001000p q 1110(pq)q1010p qpq01111000不等值不等值等值等值基本等值式(等价式)双重否定律双重否定律:A A等幂律等幂律：A A A,A A A交交换换律律:A B B A,A B B A结合律结合律:(A B) C A (B C)(A B) C A (B C)分配律分配律:A (B C)(A B) (A C)A (B C)(A B) (A C)A,B,C代表任意的代表任意的命题公式命题公式基本等值式(等价式)德德摩根律摩根律: (A B) AB (A B) AB吸吸收收律律:A (A B)A,A (A B)A零律零律:A 11,A 00同一律同一律:A 0A, A 1A排中律排中律:AA 1矛盾律矛盾律:AA 0A,B代表任意代表任意的命题公式的命题公式基本等值式(等价式)蕴涵等值式蕴涵等值式:AB A B等价等值式等价等值式:AB (AB) (BA)假言易位假言易位:AB BA等价否定等值式等价否定等值式:AB AB归谬论归谬论:(AB) (AB) AA,B,C代表任意的代表任意的命题公式命题公式 ABABABAB(AB)0011101011001010010101100010基本等值式(等价式)证明举例n原则上说，上面的公式均可用真值表证明。

下面仅验证德摩根律A B)A B等值演算与置换规则n等值演算 n由已知的等值式推演出新的等值式的过程由已知的等值式推演出新的等值式的过程n如如: A C C A 则则: B A C B C An置换规则置换规则：若若AB,则则 (B) (A)n如如: A A 1 则则 B (A A) B 1n等值演算的基础： (1) 等值关系的性质：自反、对称、传递等值关系的性质：自反、对称、传递 (2) 基本的等值式基本的等值式 (3) 置换规则置换规则 AB A B 几个重要的等值式 (A B) A B (A B) A BA B (A B) (B A) ( A B) ( A B)(A B ) ( A B)等值演算应用1证明两个公式等值P10:例例1.9(1)证明证明:p(qr)(p q)r证证:(p q)r (p q) r (蕴涵等值蕴涵等值式式)( pq) r(德摩根律德摩根律) p ( q r)(结合律结合律) p (qr)(蕴涵等值蕴涵等值式式) p(qr)(蕴涵等值蕴涵等值式式)p(qr)q(pr)应用举例证明两个公式不等值n例例2：证明：证明p(qr)(pq)rn方法：找到一个反例即可方法：找到一个反例即可。

n注意：注意：n不能用等值演算直接证明两个公式不等值！不能用等值演算直接证明两个公式不等值！n方法方法1：真值表法真值表法n方法方法2：赋值法赋值法n易看出易看出000、010是是左边的成真赋值，却是右左边的成真赋值，却是右边的成假赋值边的成假赋值n方法方法3：先用等值演算化简两个公式，再观察先用等值演算化简两个公式，再观察证明两个公式不等值真值表法 p q r qr p(qr) pq (pq)r00000101001110010111011111011101111111011111001101011101等值演算应用2判断公式的类型(1)q(pq)解解q(pq)q( p q)（蕴涵等值式）（蕴涵等值式）q (pq)（德摩根律）（德摩根律）p ()（交换律，结合律）（交换律，结合律）p 0（矛盾律）（矛盾律）0（零律）（零律）由最后一步可知，该式为由最后一步可知，该式为矛盾式矛盾式.等值演算应用2判断公式的类型(2)(pq)( qp)解解(pq)( qp)( p q)(qp)（蕴涵等值式）（蕴涵等值式）( p q)( p q)（交换律）（交换律）1由最后一步可知，该式为由最后一步可知，该式为重言式重言式.问：最后一步为什么等值于问：最后一步为什么等值于1？等值演算应用2判断公式的类型(3)(p q) (pq) r解解:(p q) (pq) r(p () r（分配律）（分配律）p 1 r（排中律）（排中律）p r（同一律）（同一律）这不是矛盾式，也不是重言式，而是非重言式的这不是矛盾式，也不是重言式，而是非重言式的可可满足式满足式.如如111是它的成真赋值是它的成真赋值,000是它的成假赋值是它的成假赋值.总结：总结：A为矛盾式当且仅当为矛盾式当且仅当A0 A为重言式当且仅当为重言式当且仅当A1等值演算应用3化简逻辑电路：ABFABF等值演算应用4化简下面程序段:if A if B X else Y elseif B X else Yn执行执行X的条件为：的条件为：(A B) ( A B)n执行执行Y的条件为：的条件为：(A B) ( A B)B Bif B Xelse YABBXYTTTFFFXYBXYTFP11例1.11等值式应用举例nA、B、C、D四人做百米竞赛，观众甲、乙、丙预测比赛结果如下：甲：C第一，B第二；乙：C第二，D第三；丙：A第二，D第四；比赛结束后发现他们每人都说对一半，试问实际名次如何(假设无并列者)？n解：首先，将命题符号化:设用设用Ai“A第第i名名”、Bi“B第第i名名”、Ci“C第第i名名”、Di“D第第i名名”(i=1,2,3,4)Ai、Bi、Ci、Di中均各有一个真命中均各有一个真命题，按题意要寻找使下列题，按题意要寻找使下列3式式成立的真命题成立的真命题(C1 B2) ( C1 B2)1(C2 D3) ( C2 D3)1(A2 D4) ( A2 D4)1等值式的应用举例(C1 B2) ( C1 B2)1(C2 D3) ( C2 D3)1(A2 D4) ( A2 D4)1n因为真命题的合取式仍为真命题（因为真命题的合取式仍为真命题（1 11），故得），故得1 (C1 B2) ( C1 B2) (C2 D3) ( C2 D3)(C1 B2) (C2 D3) (C1 B2) ( C2 D3) ( C1 B2) (C2 D3) ( C1 B2) ( C2 D3)等值式的应用举例(C1 B2) ( C1 B2)1(C2 D3) ( C2 D3)1(A2 D4) ( A2 D4)1n1 (C1 B2 C2 D3) ( C1 B2 C2 D3)1 (C1 B2 C2 D3 A2 D4) (C1 B2 C2 D3 A2 D4) ( C1 B2 C2 D3 A2 D4) ( C1 B2 C2 D3 A2 D4)等值式的应用举例(C1 B2) ( C1 B2)1(C2 D3) ( C2 D3)1(A2 D4) ( A2 D4)1n1 C1 B2 C2 D3 A2 D4A2 B2 (C1 C2) (D3 D4)A第二第二C第一第一D第三第三B第四第四1.4范式n范式提出的背景n与 P Q 等值的公式有P Q P QP Q ( P Q) ( P Q) (P Q)n与 P Q等值的公式有 P Q(P Q) (Q P) P Q ( P Q) (PQ) PQ(P Q) ( PQ)n可见同一公式可以有多种表示形式，能否有统一可见同一公式可以有多种表示形式，能否有统一的规范等值式，使真值表相等的公式形式相同？的规范等值式，使真值表相等的公式形式相同？范式范式范式n简单析取式 n仅由有限个命题变项或其否定构成的仅由有限个命题变项或其否定构成的析取式析取式。

n如如:p，q， p， q，p q，p q， p qn它是它是重言式重言式当且仅当它同时含一个命题变项及当且仅当它同时含一个命题变项及其否定；其否定；n如：如：p p q 是是重言式n简单合取式n仅由有限个命题变项或其否定构成的仅由有限个命题变项或其否定构成的合取式合取式n如如:p，q， p， q， p q，p qn它是它是矛盾式矛盾式当且仅当它同时含一个命题变项及当且仅当它同时含一个命题变项及其否定n如：如：p p q 是是矛盾式矛盾式 范式n析取范式n由有限个由有限个简单合取式简单合取式组成的组成的析取式析取式A1 A2 . An（n 1，Ai都是简单都是简单合合取式取式）n如：如：(p q r) ( p q) qn一个析取范式是一个析取范式是矛盾式矛盾式，当且仅当其，当且仅当其每个每个简单合取式简单合取式都是矛盾式都是矛盾式n合取范式n由有限个由有限个简单析取式简单析取式组成的组成的合取式合取式 A1 A2 . An（n 1,Ai都都是是简单析取式简单析取式）n如：如：(p q r ) ( p q)qn一一个个合合取取范范式式是是重重言言式式，当当且且仅仅当当其其每每个个简简单单析析取取式式都是重言式都是重言式n范式范式析取范式与合取范式的总称析取范式与合取范式的总称.范式存在定理任任何何命命题题公公式式都都存存在在着着与与之之等值的析取范式与合取范式等值的析取范式与合取范式命题公式的范式n求公式A的范式的步骤：(1)消去消去A中的中的,（若存在）（若存在）(2)否定联结词否定联结词 的内移或消去（德摩根定律）的内移或消去（德摩根定律）(3)使用分配律使用分配律 对对 分配（析取范式）分配（析取范式） 对对 分配（合取范式）分配（合。