离散数学
第一章 命题逻辑
定义1。设P为一命题,P的否定是一个新的命题,记作¬P。若P为T,¬P为F;若P为F,¬P为T。联结词“¬”表示命题的否定。否定联结词有时亦可记作“¯”。(P3)
定义2。两个命题P和Q的合取是一个复合命题,记作P∧Q。当且仅当P,Q同时为T时,P∧Q为T,在其他情况下,P∧Q的真值都是F。(P4)
定义3。两个命题P和Q的析取是一个复合命题,记作P∨Q。当且仅当P,Q同时为F时,P∨Q的真值为F,否则P∨Q的真值为T。(P5)
定义4。给定两个命题P和Q,其条件命题是一个复合命题,记作P→Q,读作“如果P,那么Q”或者“若P则Q”。当且仅当P的真值为T,Q的真值为F时,P→Q的真值为F,否则P→Q的真值为T。我们称P为前件,Q为后件。(P6)
定义5。给定两个命题P和Q,其复合命题P Q的真值为F。(P7)
定义6。命题演算的合式公式(wff),规定为:
(1)单个命题变元本身是一个合式公式。
(2)如果A是合式公式,那么¬A是合式公式。
(3)如果A和B是合式公式,那么(A∧B),(A∨B),(A→B)和(A B)都是合式公式。
(4)当且仅当能够有限次地应用(1),(2),(3)所得到的包含命题变元,联结词和括号的符号串是合式公式。(P9)
定义7。在命题公式中,对于分量指派真值得各种可能组合,就确定了这个命题公式的各种真值情况,把它汇列成表,就是命题公式的真值表。(P12)
定义8。给定两个命题公式A和B,设P1,P2, ,Pn为所有出现于A和B中的原子变元,若给P1,P2, ,Pn任一组真值指派,A和B的真值都相同,则称A和B是等价的或逻辑相等。记作A B。(P15)
定义9。如果X是合式公式的A的一部分,且X本身也是一个合式公式,则称X为公式A的字公式。(P16)
定理1。设X是合式公式A的字公式,若X Y,如果将A中的X用Y来置换,所得到公式B与公式A等价,即A B。(P16)
定义10。给定一命题公式,若无论对分量做怎样的指派,其对应的真值永为T,则称该命题公式为重言式或永真公式。(P19)
定义11。给定一命题公式,若无论对分量做怎样的指派,其对应的真值永为F,则称该命题公式为矛盾式或永假公式。(P19)
定理2。任何两个重言式的合取或析取,仍然是一个重言式。(P19)
定理3。一个重言式,对同一分量都用任何合式公式置换,其结果仍为一重言式。(P19) 定理4。设A,B为两个命题公式,A B当且仅当A B为一个重言式。(P20)
定义12。当且仅当PQ是一个重言式时,我们称“P蕴含Q”,并记作P Q。(P20) 定理5。设P,Q为任意两个命题公式,P Q的充分必要条件是P Q且Q P。(P22) 定义13。设P和Q是两个命题公式,复合命题P Q称作P和Q的不可兼析取。P Q的真值为T,当且仅当P与Q的真值不相同时为T,否则,PQ的真值为F。(P24)
定理6。设P,Q,R为命题公式。如果P Q R,则P R Q,Q R P,且P Q R为一矛盾式。(P25)
定义14。设P和Q是两个命题公式,复合命题P Q称作命题P和Q的条件否定,P Q的真值为T,当且仅当P的真值为T,Q的真值为F,否则P Q的真值为F。(P25)
离散数学定义定理(下)_数学_自然科学_专业资料。离散数学定义定理定义4.1.1 设 A,B 为仸意集合,一个从 An 到 B 的映射,称为集合 A 上的一个 n 元运算...
1.E等价I蕴含 2.主析取范式小项p为1公式的真值为T的指派对应小项析取 3.US全部指定规则 UG全部推广规则 ES存在指定规则 EG存在推广规则离散数学定义定理 1.3....
离散数学定义定理 1.3.1 命题演算的合式公式规定为: (1)单个命题变元本身是一个合式公式。 (2)如果 A 是合式公式,那么┐A 是合式公式。 (3)如果 A ...
离散数学定义定理 1.3.1 命题演算的合式公式规定为: (1)单个命题变元本?是?个合式公式。 (2)如果 A 是合式公式,那么┐A 是合式公式。 (3)如果 A 和...
离散数学定义定理(下)_数学_自然科学_专业资料。1、设 A 为任意非空集合,*是集合 A 上的二元运算。 (1)封闭性: (3)交换律: a*b=b*a (2)结合律: a...
8页 免费 考研数学线性代数概念、性... 6页 免费喜欢此文档的还喜欢 离散之...定理 7.1.6: 设*是 A 上的可结合的二元运算,e 是关于*的 : 单位元,al...
离散数学(二)第七讲计算机学院: 焦晓鹏 拉格朗日定理主要内容: 11 陪集 2 拉格朗日定理 重点和难点: 重点: 陪集的性质 一、陪集陪集的定义:设<H,?>为<G,?>...
《离散数学(本)》主要概念、定理与方法第1章一、概念集合(元素)——集合是一些具有确定的、可以区分的若干事件的全体,而集合中的事件 称为元素. 因此, 集合是由...
离散数学重要公式定理汇总大一上 Formula ? 基本的等价公式⑴ 对合律 ??P?P ...自反性定义 :设 R是集合 A中的关系,如果对于任意x∈A都 有<x,x>∈R (...
2013-7-25 离散数学 32 一、无向图及相关概念(续) (补充)奇点的数目为偶数只是图的度系列的必要条件, Erdǒs等给出了一个充分必要条件: 定理:和为偶数的...
热门文档