北邮函授考试离散数学期末考试复习题-第四章要点.doc

数理逻辑 §4.1 命题逻辑 一、命题与命题公式 1.命题 定义 在数理逻辑中，能够判断真假的陈述句称为命题。 注：命题包括两点：①陈述句，②能判断真假 命题的真假称为命题的真值，如果一个命题是真的（正确的判断），它的真值为真，记为T或1；如果一个命题是假的（错误的判断），它的真值为假，记为F或0。 简单命题: 不能分解成更简单的陈述句的命题,叫简单命题或原子命题。常用小写字母来表示简单命题。 命题符号化: 将一个命题用字母表示时，称为将命题符号化。 如 : 2是素数。 : 雪是黑色的。 则 是真命题, 为假命题。 有时用1表示真命题, 0表示假命题。 一个符号若表示确定的命题,称为命题常项或命题常元。上面的 , 为命题常项。 当一个符号表示任一简单命题时（起着类似数学中变元的作用），这个符号称为命题变项或命题变元。 严格来说: 命题变元不是命题。因它可以表示任一命题,故无确定的真值。 2.逻辑连接词 （1）否定联结词 定义 设为任一命题，复合命题“非”称为的否定式，记为，为否定连接词。其真值为：若为1, 则为0；若为0，则为1。 如下表: 0 1 1 0 （2）合取联结词 定义 设为二命题，复合命题“”称作 和 的合取式，记作 . 为合取联结词。规定为真当且仅当同时为真。如下表 0 0 0 0 1 0 1 0 0 1 1 1 （3）析取联结词 定义 设为二命题，则复合命题（读作“或 ”）称为、 的析取式。 为析取联结词。其真值为：当且仅当和的真值全为0时，命题 的真值才是0，否则，命题的真值为1。如下表 0 0 0 0 1 1 1 0 1 1 1 1 （4）蕴涵联结词 定义 设为二命题，复合命题“如果,则”称作与的蕴涵式，记作 . 为前件，为后件。 称作蕴涵联结词。“”又称为条件命题，规定当为真和 为假时，为假，否则为真。 0 0 1 0 1 1 1 0 0 1 1 1 由此可知：前件为假，不论后件真假与否，条件命题为真。 相当于自然语言中的“如果…则…”，“若…则…”，表明：为的必要条件（或为的充分条件）。 （5）等价联结词 定义 设为二命题，复合命题“当且仅当”称作与的等价式，记作. 称作等价联结词。规定当和的真值相同时，为真，否则为假，列表如下: 0 0 1 0 1 0 1 0 0 1 1 1 相当于自然语言中的“当且仅当”，“充分必要”。 3.命题公式及分类 定义 (1)单个命题常元、命题变元，0，1是命题公式； (2)如果是命题公式,则也是命题公式； (3)如果是命题公式,则，，，也是命题公式； (4)只有有限次地运用(1)--(3)组成的符号串才是命题公式。 在定义中引用了A、B等符号，它们表示任意的命题公式。 下面给出赋值的定义 定义 设A是一个命题公式，是出现在公式A中的全部命题变元，给 各指定一个真值，称为对命题公式A的一个赋值或解释。若指定的一组值使A的值为1，则称这组值为A的成真赋值；若使A的值为0，则称这组值为A的成假赋值。 定义 设A为命题公式． （1）如果对A中所含命题变元的任一组赋值，A的真值总为1，则称A为重言式或永真式； （2）如果对A中所含命题变元的任一组赋值，A的真值总为0，则称A为矛盾式或永假式； （3）若至少有一组赋值使A为真，则称A是可满足式。 由定义可以看出，重言式一定是可满足式，但反之不一定成立。 可满足式一般是指非重言式的可满足式。 用真值表可以判断公式的类型；若真值表的最后一列全为1，则公式为重言式。若最后一列全为0，则公式为矛盾式；若最后一列既有1又有0，则公式为非重言式的可满足式。 二、等值演算 定义 设A，B为二命题公式，若等价式为重言式，则称A与B是等值的，记作． 注意符号“”不是联结词，它是A与B等值的一种记法。不能将与或与= 混为一谈。 例如： 但不能写成 又不是命题公式。 下面给出24个常用的重要的等值式，设表示任意的命题公式，1表示永真式, 0表示永假式. 双否律 （1） 幂等律 （2） （3） 结合律 （4） （5） 交换律