《离散数学(第2讲)命题逻辑2》由会员分享，可在线阅读，更多相关《离散数学(第2讲)命题逻辑2（41页珍藏版）》请在金锄头文库上搜索。
1、第1章 命题逻辑(2)栾新成 四川大学软件学院 85997822 13808024081主要内容v 命题公式及其赋值 命题公式与赋值 永真式 矛盾式v 命题公式的等价 基本等价式 等价式的判断 对偶原理*21.2 命题合适公式与真值表 v 一个特定的命题是一个常值命题，它不是具有值“T”(“1”)，就是具有值“F”(“0”) 。(具体内容的原子命题)v 而一个任意的没有赋予具体内容的原子命题是一个变量命 题，常称它为命题变量(或命题变元)，该命题变量无具体的真值，它的值域是集合T，F(或0，1)。v 当原子命题是命题变元时，其复合命题也即为命题变元的 “函数”，且该“函数”的值仍为“真”或“
2、假”值，这样的函数可形象地称为“真值函数”,或称为命题公式, 此命题公式没有确切真值。*3命题公式v 定义1-2.1 由命题变元、逻辑联结词和括号按照下述规则构成的表达式称为（命题）合适公式。v 原子命题变元是合适公式；v 如果，是合适公式，则（），（）， （），（），（）都是合适公式；v 只有经过有限次使用或得到的命题表达式才是合适公式。v 该公式常用符号G、H、等表示。v 哪些形式可以组成命题公式（？）*4命题公式v 为书写和输入计算机及计算方便起见，约定：v （1）最外层括号可以省略v （2）按联结词的优先级的括号可以省略v 联结词的优先顺序：括号最优先， 符合优先次序者，可省去括号。v
3、 相同联结词，按从左到右。v 最外层括号可省去。*5命题公式v 例2.1 v 符号串：(P(QR)(Q(SR)； v (PQ)； (P(PQ)； v (PQ)(RQ)(PR)。 v 等都是命题公式。 v 符号串： v (PQ)Q)；(PQ； v (PQ(R； PQ。 v 等都不是合法的命题公式。 v 定义1-2.2：如公式A是公式B的一部分，则称A是B的子 公式。*6公式的解释与真值表v 定义1-2.3 设P1、P2、Pn是出现在公式G中的所有 命题变元，指定P1、P2、Pn的一组真值（如1，0， 1，0，1），则这组真值称为G的一个解释。v 一般来说，若有个命题变元，则应有2n个不同的解释。
4、v 定义1-2.4 如果公式G在某一解释下是真的，则称这一 解释为G的成真赋值；v 如果G在某一解释下是假的，则称这一解释为G的成假赋值。v 将公式G在其所有可能解释下的真值情况列成的表，称为 G的真值表。*7公式的解释与真值表v如何构造真值表 v1）把表分成3部分 v2）最左边为原子变员 v3）中间为子式 v4）最后为公式 v例2.2构造公式G1： PQ的真值表如下：vPQ和PQ的真值表 完全一致PQPPQ0011011110001101*8公式的解释与真值表v例2.3 v构造公式G2：(PQ) ()的真值表PQPQ(PQ) ()001100010100101010110100*9该公式对所
5、有可能的解释取值均为0公式的解释与真值表v例2.4 v构造公式G3： (PQ)的真值 表 v该公式对所有可能 的解释取值均为1PQPQ(PQ)0011011110011111*10公式的解释与真值表v 从这三个真值表可以看到一个非常有趣的事实：v 公式G3 ：(PQ)对所有可能的解释具有“真”值v 公式G2：(PQ) ()对所有可能的解释均具有“假”值v 公式G1： PQ则具有“真”和“假”值*11永真式、矛盾式、可满足公式v定义1-2.5v公式G3称为永真公式(重言式)，如果在它的所有解释之下都为“真”。v公式G2称为永假公式(矛盾式，不可满足公式),如果在它的所有解释之下都为“假”。v公式
6、G1称为可满足公式，如果它不是永假的（即存在解释使公式取值1）。*12永真式、矛盾式、可满足公式v 永真式的特点 v 永真式G的否定G是矛盾式；矛盾式G的否定G是永 真式。 v 永真式一定是可满足式,可满足式不一定是永真式。v 两个永真式的合取、析取、条件、双条件均为永真式。v 这样由简单的重言式，可以推出无数个复杂的重言式。 判定给定公式是否为永真式，永假式或可满足式的问题 ，称为给定公式的判定问题。v 在逻辑研究和计算机推理以及决策判断时，人们对于所 研究的命题，最关心的莫过于“真”、“假”问题，所以永真 公式在数理逻辑的研究中占有特殊且重要的地位。 *13永真式的判断v 命题逻辑的基本任
7、务之一，就是找出那些属于永真式的命题公式。v （1）真值表法（简单、直观）*14永真式的判断v （2）置换（代换，代入）法 v 如果公式A中的一些变元，用一些公式代入，而且每次出 现同一变元时，总用同一公式代入，就可从公式A得到公 式B，则称公式B为公式A的置换（代入）实例（例式）。 v 置换定理：永真式的任何置换（代入）实例仍是一个永真 式。 v 例如：（RS）（M N）（RS）是否为永真 式 v PQ P（永真式） v 对上式中的P，用（RS）代入， v 对Q，用（M N）代入后得到： v （RS）（M N）（RS） v 该公式也是一个永真式*15永真式的判断v （3）公式推演法（等价变换
8、、替换（取代）规（范）则）v 具体方法在下节中介绍*161.3 命题公式的等价v 定义1-3.1 设G、H是公式，如果在任意解释下，G与 H的真值相同，则称公式G、H是等价的 ，记作GH。v 定理1-3.2 公式G、H等价的充分必要条件是公式 GH是永真公式。v 此定理是从另一角度来看待等价性 等价式的性质: 1）自反性：A A 2）对称性：若 A B，则 B A 3）可传递性:若 A B，B C，则A C*17基本等价式v “” 与“”的区别v 首先，双条件词“”是一种逻辑联结词，公式GH是命 题公式，其中“”是一种逻辑运算，GH的结果仍是一个命题公式。v 而逻辑等价“”则是描述了两个公式G
9、与H之间的一种逻 辑等价关系，GH表示“命题公式G等价于命题公式H”， GH 的结果不是命题公式。（公式是否可以替换）v 其次，如果要求用计算机来判断命题公式G、H是否逻辑 等价，即GH那是办不到的，然而计算机却可“计算”公 式GH是否是永真公式*18基本等价式v基本等价式命题定律 Equivalence v设G，H，S是任何的公式，则： v1:(G H)(GH)(HG)(等价) v2：(GH) (GH) (蕴涵) v3：GG G ( 幂等律) v4：GG G v5：GH HG ( 交换律) v6：GH HG v7：G(HS) (GH)S (结合律) v8: G(HS) (GH)S v9：G(
10、GH) G ( 吸收律) v10：G(GH) G*19基本等价式v11：G(HS) (GH)(GS) (分配律)v12：G(HS) (GH)(GS)v13：GF G(同一律)v14：GT Gv15：GT T(零律)v16：GF Fv17：GG T ( 矛盾律)*20基本等价式v 18：GG Fv 19： (G) G (双重否定律)v 20：（GH)S G（HS） （输出律）v 21：（GH）(GH)(GH) (排中律)v 22：PQ QP （逆反律）v 23： (GH) GH (De Morgan 定律)v 24： (GH) GH。*21基本等价式v 替换定理v 定理1-3.1 设G1是G的子
11、公式(即 G1是公式G的一部分)，H1是任意的命题公式，在G中凡出现G1处都以H1替换后得到新的命题公式H，若G1 H1，则G H。v 替换定理是经常使用的重要定理。 *22等价式的判定v 1.真值表法v 2.公式推演（等价变换）v 例3.1：试证 PQ QPv 证：PQ PQ 蕴涵 E2v PQ 双重否定 E19v QP 交换律 E5v QP E2*23等价式的判定v 例3.2v 试用较少的开关设计一个与下图有相同功能的电路。*24等价式的判定v 解：可将上图所示之开关电路用下述命题公式表示： v (PQS)(PRS)v 利用基本等价公式，将上述公式转化为：(PQS)(PRS) v (PS)
12、Q)(PS)R)(结合律) v (PS)(QR)（分配律）v 所以其开关设计图可简化为：*25等价式的判定v 例3.3v 试将下图所示之逻辑电路简化。*26P QR并联符号ANDANDANDOROR与门或门PQR等价式的判定v 解: 可将上述电路写成如下命题公式：(PQ)(PR)(QR)v 利用基本等价公式转化为：(PQ)(PR)(QR) (P(QR)(QR)（分配律） P(QR) (幂等律)v 所以该电路图可简化为：*27PQ R等价式的判定v 例3.4v 证明 P(PQ)Q) 是永真公式。v 证：P(PQ)Q)v P(PQ)Q (De Morgan 定律)v (PQ)(PQ) (交换律)
13、(结合律)v T （矛盾律）*28等价式的判定v 例3.5v 证明P(QR) (PQ)Rv 证：P(QR)v P(QR)（蕴涵）v P(QR) （蕴涵）v (PQ)R (结合律)v (PQ)R （蕴涵）v (PQ)R （蕴涵）*29等价式的判定v 例3.6v 试证明(P(QR)(PQR) Pv 证明： (P(QR)(PQR) v P(QR)(QR)（分配律）v P(QR)(QR) (De Morgan 定律)v PT（矛盾律）v P(同一律)*30等价式的判定v 例3.7v 试证明(P(QR)(QR)(PR)Rv 证明：(P(QR)(QR)(PR) v (PQ)R）(QP)R)（结合律、分配律）v (PQ)R)(QP)R) (De Morgan 定律)v (PQ)(QP)）R（分配律）v TR(交换律、矛盾律）v R （同一律）*31等价式的判定v 将下列语句化简：情况并非如此：如果他不来，那么我也不去。v 解：设P：他来，Q：我去v 此语句为： （ PQ）v 化简（ PQ）v （ P Q ）v （P Q ）v P Q v 我去了但他没来。*32等价式的判定
