真值表与等价公式.ppt

 第一章 命题逻辑 把符号命题翻译成自然语言命题： 这种翻译比较简单，只要求用词准确，力求保持原命题的意思。 例 设 A: 今天下雨。 B: 今天下雪。 C: 今天天晴。试把下列命题翻译成自然语言: 1) ┐(A∧B) 2) C? (┐A∧┐B) 3) A∨B→┐C 解 :1) 说今天下雨且下雪是不对的。 2) 今天天晴当且仅当今天既不下雨又不下雪。 3) 如果今天下雨或者下雪, 今天就不是晴天。 ①天没下雨，我也没有进城。 ②如果我有时间，我将进城。 ③如果天不下雨而且我又有时间，我将进城。 ④ ?（R∨Q） ⑤ Q?（R∧?P） ⑥（Q→R）∧（R→Q） 1.3.1 真值表 命题公式没有确定的真值，但可以假设公式中各个分量的不同取值来分析命题公式的真值情况。这样命题公式的真值情况就依赖于命题公式的结构和命题公式中各分量的真值指派。 定义1-8 设A是一个命题公式， 为出现在A中的所有命题变元。给 指定一组真值，称为对A的一组赋值（或真值指派）。 为了使命题公式的真值情况一目了然，可采用真值表的形式表示。 定义1-9 对命题公式分量真值的各种可能指派，就确定了命题公式的各种真值情况，将其汇成表，就是该公式的真值表。 ?真值表的构造规则： （1）在真值表左栏按字母顺序列出所有分量，右栏列出结果命题。 （2）用0~2n -1的二进制计数顺序给命题分量指派真值。 （3）为了使真值表更加明了，可将中间命题列在命题分量和结果命题之间。 例1-9 构造命题公式 的真值表。 例1-10 构造公式 的真值表。 解： 解（2） 定理1-1 任何两个重言式的合取或析取仍然是一个重言式。 证明：根据定义，因为任何重言式不论分量真值作何指派，其真值总为真，而两个真值为真的命题的合取或析取一定为真。 练习 1.3.3 等价公式 从真值表中可以发现，两个有相同命题分量但结构不同的命题公式，对其分量真值的不同指派，其真值总相同，如： 例1-12 构造下列命题公式的真值表。 （1）构造命题公式 的真值表。 （2）构造命题公式 的真值表。 解(1) 解（2） 定理1-2 设A和B是任意两个命题公式，A ?B 当且仅当A?B为重言式 。 证明： 若A ?B ，则A和B的真值相同，即同为真或同为假。根据双条件命题的定义A?B 为真，所以 A?B 为重言式。 若A?B 为重言式，则A?B 为永真，根据双条件命题的定义，A和B的真值相同，所以A ?B 。 常用的命题等价公式有： 1．3．4 命题公式的等价演算 在算术运算中,我们可以根据运算符的优先次序，将算术表达式中某一部分用其结果代替，得到的新表达式与原表达式相等。在命题演算中，我们同样可以用命题公式某一部分的等价命题公式代入，所得的新命题公式与原公式等价，这个过程称为置换。置换时要求被置换部分应该是命题合式公式。 定义1-12 如果X是命题公式A的一部分，且X本身是一个合式公式，则称X为公式A的子公式。 定理1-3 设X是命题公式A的子公式，若X?Y，如果将A中的X用Y置换，所得的公式B与命题公式A等价。 证明： 因为在相应分量的任一种真值指派下，X和Y的真值都相同，用Y置换X后，公式B与A在相应分量的真值指派下，其真值仍相同，所以A?B 。 例1-13 推导证明吸收律 。 证明： 同一律 分配律