【离散数学】命题逻辑 |
您所在的位置:网站首页 › 逆命题和逆否命题一样吗 › 【离散数学】命题逻辑 |
1、命题与联结词
定义:可以判断真假的语句叫命题 **分类:**简单命题、复合命题(由简单命题与逻辑联结词构成) p或q p∨p q且q p∧q 否定 ¬ 与(合取-结合,同时)∧ 或(析xi取-或)∨ 条件 →-如果 则 双条件 ↔ 四种命题: 原命题 若p则q 逆命题 若q则p 否命题 若¬p则¬q 逆否命题 若¬q则¬p 命题的否定与否命题 (1)命题的否定:(只否定结论). P表示命题,非P叫做命题的否定; 若P则q,则命题的否定为:若P则¬9q (2)否命题(既否定条件,又否定结论) 充分条件与必要条件 充分条件 若P=>q,则P是q的充分条件 必要条件 若P=> q,则q是P的充分条件 充要条件 若P=>q且若q=>p则p是q的充要条件 充分条件与必要条件判定 (1)数轴法 (2)集合法 (3)等价法 全称量词与存在量词 2、命题公式与解释逻辑联结词优先级递增次序 ↔、→、∨、^、¬ 命题的翻译(符号化) 命题公式的解释(赋值) A:含有n个命题变元的公式有2的n次方 组不同的真值指派,对每一组真值指派,公式都有一个确定的真值 B:命题变元:指命题中真值的还不确定-通常,如果p代表真值未指定的任意命题,我们就称p为命题变元。所以命题变元仍然是个命题,只是真值还未被赋予。 作 命题公式的真值表 命题公式的类型 •永真式:不依赖于命题变元的真值指派,而总是取值为T的命题公式; •永假式:不依赖于命题变元的真值指派,而总是取值为F的命题公式; •可满足式: 给定一个逻辑公式,如果存在一个解释(模型),使得该公式在该解释中取真值,则称该公式是可满足的。 否则,该公式是不可满足的。 可满足式的求解是逻辑学中的一个重要问题,它涉及到如何判断一个逻辑公式是否可以被满足。 在离散数学中,可满足式的研究也是非常重要的一部分。 求解可满足式的方法包括使用定理证明、消解法、回溯法等。 例如,考虑以下逻辑公式: (P ∨ Q) ∧ ¬(P ∧ Q) 该公式是可满足的,因为它可以通过解释P和Q的真值来满足。 具体来说,我们可以选择P为真,Q为假,或者选择P为假,Q为真,这样公式中的每个子句都取真值。 因此,该公式是一个可满足式。 命题公式的逻辑等值 A↔B和A⇔B 的区别:后者表示命题之间的关系,及同真同假A=0,也B=0。前者本质上是逻辑链接词,意为等价,A和B的值随意。 逻辑等值的性质: 自反性:自己等于自己-A⇔A 对称性:A⇔B-B⇔A 传递性:A⇔B,B⇔C,A⇔C 逻辑等值的相关公式 双重否定律 ┐┐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 ∨ ( A ∧ B ) ⟺ A A ∧ ( A ∨ B ) ⟺ A 分配律:1、A ∨ ( B ∧ C ) ⟺ ( A ∨ B ) ∧ ( A ∨ C ) 2、A ∧ ( B ∨ C ) ⟺ ( A ∧ B ) ∨ ( A ∧ C ) 德摩根律:1、¬ ( A ∨ B ) ⟺ ¬ A ∧ ¬ B 2、¬ ( A ∧ B ) ⟺ ¬ A ∨ ¬ B 零一律:1、A ∨ 1 ⟺ 1 2、A ∧ 0 ⟺ 0 同一律:1、A ∨ 0 ⟺ A 2、A ∧ 1 ⟺ A 排中律:A∨¬A⟺1 矛盾律:A∧¬A⟺0 蕴含等值式:A→B⟺¬A∨B 通过A→B的运算发现无论A,B真假,与后面的式子永远等价 假言易位:A→B⟺¬B→¬A 说白了就是逆否命题 等价等值式:A↔B⟺(A→B)∧(B→A) 等价否定等值式:A↔B⟺¬A↔¬B 归谬论:(A→B)∧(A→¬B)⟺¬A A↔B⟺(A∧B)∨(¬A∧¬B) 左边等于右边,右边等于左边 3、范式 概念 命题变元或命题变元的否定称为文字:P、¬P、Q、¬Q 有限个文字析取称为简单析取式(或字句)P∨Q∨¬R、...P、¬P 有限个文字合取称为简单合取式(或字句)P∧Q∧¬R、...P、¬P 有限个(大于等于1)简单合取式(短语)的析取式称为析取范式(disjunctive normal form); 如 (P ∧ Q) ∨ (¬P ∧ Q) 又如 P ∧ ¬Q,P,¬P 有限个(大于等于1)简单析取式(子句)的合取式称为合取范式(conjunctive normal form)。 如 (P ∨ Q) ∧ (¬P ∨ Q),又如 P ∨ ¬Q,P, ¬P 单独一个的短语(子句),也可以构成析取范式(合取范式) 范式存在的定理对于任意命题公式,都存在与其等价的析取范式和合取范式。 范式与真值命题公式的析取范式可以指出公式何时为真,而合取范式可以指出公式何时为假,从而能够替代真值表。((¬P ∨ Q) ∧ (P ∨ ¬R),¬P ∨ (¬Q ∧ R)) 命题公式的范式表达并不唯一,比如对公式 (P ∨ Q) ∧ (P ∨ R) 而言,对应的析取范式有很多: P ∨ (Q ∧ R) (P ∧ P) ∨ (Q ∧ R) P ∨ (Q ∧ ¬Q) ∨ (Q ∧ R) P ∨ (P ∧ R) ∨ (Q ∧ R) 一般而言,求解范式时,需要进行最后的化简步骤; 主范式极小项和极大项 为什么要定义主范式 由于范式的不唯一性,我们考虑对构成范式的子句或短语进一步规范化,从而形成唯一的 主析取范式和主合取范式。 在含有 n 个命题变元 P1, P2, P3, · · · , Pn 的短语或子句中,若每个命题变元与其否定不同时存在, 但二者之一恰好出现一次且仅一次,并且出现的次序与 P1, P2, P3, · · · , Pn 一致,则称此短语或子句为关于 P1, P2, P3, · · · , Pn 的一个极小项或极大项。 极小项的性质 极大项的性质 极小项和极大项的性质 在给定的析取范式中,若每一个短语都是极小项,且按照编码从小到大的顺序排列, 则称该范式为主析取范式(principal disjunctive normal form)。 在给定的合取范式中,若每一个子句都是极大项,且按照编码从小到大的顺序排列, 则称该范式为主合取范式(principal conjunctive normal form)。 如果一个主析取范式不包含任何极小项,则称该主析取范式为 “空”;如果一个主合 取范式不包含任何极大项,则称主合取范式为 “空”。 求解方法 3、主析取范式和主合取范式的转化 由真值表技术可知,对于任一个命题公式而言,主析取范式所使用的极小项的编码和主合 取范式所使用的极大项的编码是 “互补” 的关系。从而我们在求主析取范式和主合取范式 时,可根据公式特点,先求出二者之一,然后可直接写出另一个。 主范式可用于了解公式的真值情况,进行公式类型的判定以及等价关系的判定。 如果主析取范式包含所有的极小项,则该公式为永真公式; 如果主合取范式包含所有的极大项,则该公式为永假公式; 若两个公式具有相同的主析取范式或主合取范式,则两公式等价。 基本推理形式和蕴涵公式推理的判定定理 公式 H 是前提集合 Γ = {G1, G2, · · · , Gn} 的逻辑结果当且仅当 (G1 ∧ G2 ∧ · · · ∧ Gn) → H 为永真公式。 基本蘊含关系 自然演绎法推 1.推理规则 规则 P (称为前提引用规则):在推导的过程中,可随时引入前提集合中的任意一个前提; 规则 T (称为逻辑结果引用规则):在推导的过程中,可以随时引入公式 S,该公式 S 是由其 前的一个或多个公式推导出来的逻辑结果。(可以直接使用推导出的中间结果) 规则 CP (称为附加前提规则):如果能从给定的前提集合 Γ 与公式 P 推导出 S,则能从此前提集合 Γ 推导出 P → S。(结论中的前件,可以当作前提条件来使用)
|
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |