
基本联结词与复合命题.ppt
33页第 14 章 命题逻辑,知识点 命题概念 基本联结词与复合命题 合式公式与联结词优先次序 构造真值表,证明等价式 不构造真值表,证明蕴含式 应用P规则T规则推理证明 蕴含式,推理理论 CP规格与间接推理证明,难点 命题公式化简 P、T、CP规则 推理理论及应用要求 熟练掌握 构造真值表和不构造真值表证明蕴含 式与等价式 命题与符号化与翻译及歧义性消除,P规则、T规则推理证明 应用CP规格与间接推理证明 了解 命题公式与联结词化简,14.1 命题与联结词,所谓命题就是能判断真假,但不会既能真又 能假的陈述句为命题命题的判断结果称命题的 真值真值只能取两个值“真”或“假”真”用1或 T(True)表示,“假”用0或F(False)表示在数理逻辑中,我们用大字英文字母表示命 题,称为命题变元当一个命题变元用一个具体 命题代入时,就会有确定的真值例如,用P表 示命题,则P是命题变元,当P用具体命题“雪是,黑色的”代入后,P就表示命题:雪是黑色的, 这时P有确定的真值:F用一个具体命题代 入命题变元称为对命题变元的指派 1.否定 定义1 设P为命题,P的否定是一个新命题,记 作 P。
若P为T,则 P为F,若P为F,则 P为T 2.合取 定义2 设P、Q是命题,P和Q的合取是一个复 合命题,记作 当且仅当P、Q同时,为T时, 为T ,其他情况下 为F 3.析取 定义3 设P,Q是命题,P和Q的析取也是一个命题, 记作 当且仅当P,Q同时为F时, 为 F其他情况下 为T 4.排斥析取 定义4 设P,Q是命题,P和Q的排斥析取也是个命 题,记作 当且仅当P和Q的真值不相同时,为T,其他情况下真值都是F例 指出下列命题中的“或”是析取还是排斥析取 1)今晚我去看电影或在家温书 2)我吃面包或蛋糕 3)他是百米冠军或跳远冠军 4)今晚9时,中央一台播放电视剧或播放足球比赛 5)派王一或赵平去北京学习 6)派王一或赵平中的一人去北京学习 解 1)、4)、6)中的“或”为排斥析取2)、3)、5)中的“或”为析取排斥或表示的是非此即彼,不可兼得,而可兼或表 示的是二者至少发生一个,不排除二者都发生的情况。
5.条件 定义5 设P,Q是命题,P对于Q的条件命题,记作 当且仅当P的真值为T,Q的真值为F时, 的真值为F,其他情况下的真值为T我们称 中的P为前件,Q为后件也称P蕴含Q 6.双条件 定义6 设P,Q为命题,其双条件命题,记作当P和Q真值相同时, 为T,其他 情况下 为F由命题变元和联结词组成的“复杂命题变元”称为 命题公式各变题变元称为命题公式的分量如P, , , 都是命题公式,而P,Q,R是命题公式分量联结词也称逻辑运算符,其运算顺序为:, 例 设P表示命题“天下雨”, 设Q表示命题“我去 看球赛”, 设R表示命题“我有时间”, 试以符号化 表示下列命题: 1)天不下雨 2)如果天不下雨,那么我去看球赛 3)我去看球赛,仅当我有时间 4)如果天不下雨且我有时间,那么我去看球赛 解 1) P2)3)4),,,,例 请将下列命题符号化 1)如果天不下雨,那么我去看球赛;否则我不 去看球赛。
2)如果天不下雨,那么我去看球赛;否则我在 家看电视 解 设P表示命题“天下雨”,Q表示命题“我去看球 赛”,R表示命题“我在家看电视” 1) 2),,,14.2 真值表和逻辑等价,定义7 在命题公式中,对各分量指派所有可能的 真值,从而确定命题公式的各种真值,把它汇列 成表就是命题公式的真值表 例 构造 的真值表解 的真值表如下表所示一般讲n个命题变元,组成的命题公式共有 个 真值如果命题公式在分量不同的指派下,其对应 的真值总是真,称这样的命题公式为永真式记 作T,如上例中 就是永真式如果命题公式在分量不同的指派下,其对应 的真值总是假,称这样的命题公式为永假式 定义8 在真值表中,两个命题公式A和B,在分量 的不同指派下,其真值总是相同的,则称这两个 命题公式A和B是逻辑等价的,记作 例 证明证明 列出真值表如下表所示由表知, 。
下面列出一些常用的逻辑等价公式,可用真值 表验证它1)对合律 2)幂等律 3)结合律 4)交换律 5)分配律 6)吸收律,7) 德摩根律8) 同一律 9) 零 律 10)否定律 下面介绍代换规则:设命题公式A和B逻辑等价,即 如果在 命题公式C中出现A的地方用B替换后(不一定是 每处)而得到命题公式D,则 例 证明 证明 因为 (等值公式) 所以(德摩根律)(等值公式)(德摩根律)(对合律)(等值公式),,,,,,定义9 设A是命题公式,且A中仅有联结词 在A中将 分别换成 后所的 得命题公式 称为A的对偶式 对偶原理:设A,B为仅有命题变元和联结词构成的命题公式, 为A的对偶式, 为B的对偶式;如果 ,则 14.3 永真蕴含式 定义10 设A,B是命题公式,如果 是永真 式,则称A永真蕴含B,记作 。
例 证明 证明因为(等值公式)(等值公式)(德摩根律)(德摩根律)(结合律)(否定律)所以,,,,,,永真蕴含式有以下重要性质: 1)自反性: 对任意公式A,有 2)反对称性: 对任意公式A和B,若,则 3)传递性: 对任意公式A,B和C,若,则 永真蕴含式与推理理论有密切的关系,请熟记以 下常用的永真蕴含式: 1)化简式 2)化简式,,,,,,,,,3)附加式: 4)变形附加式: 5)变形附加式: 6)变形简化式: 7)形简化式: 8)假言推论: 9)拒取式: 10)析取三段论 : 11)条件三段论 : 12)双条件三段论 :,,,,,,13)合取构造二难 : 14)析取构造二难: 15)前后件附加: 16)前后件附加: 14.4 推理理论 定义11 设 和Q是命题公式,且,由永真蕴含定义知, 当 的真值为T时,必然有Q的真值 为T。
称 为前提,Q为由这些前提推出 的有效结论例有下列事实:“如果我的论文通过答辩,那么我 能获得博士学位;如果我获得博士学位,那么我很 高兴;但我不高兴,所以我的论文没有通过答辩”试指出前提和有效结论并证明它 解 这种文字类型的推理问题,应先将命题符号化,然后写出前提和结论,以及推理的形式结构,最后再进行判断 设P:我的论文通过答辩,Q:我获得博士学位, R:我很高兴 前提为: 有效结论为: 即证明,,,,证明 因为 (条件三段论)(拒取式) 所以 1.直接证明法 直接证明法遵循以下两条规则: 1)P规则 前提在推导过程中的任何时候都可以 引入使用 2)T规则 在推导中,如果有一个或多个公式, 永真蕴含着公式S,则S可引入推导中例 证明 证明 1) P2) T1)3) T2)4) T3)5) T4)6) T5)7) T6)8) T7)9) P,,,,,,,,,,,10) T9) 11) T10)12) T11)13) T12)14) T13)15) T8)、14) 2. 间接证明法设有一组前提 ,要推出结论Q, 即证明 ,也就是要证明,,,,,,,,,即 也就是要证明即 由此可见,要证明 可将结 论的否定 加入到前提中去,然后再证明是永假式即可。












