离散数学——精选推荐

离散数学

第一章 命题逻辑

定义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）