真值表与等价公式

第一章命逻辑第三讲回顾一、命题公式命题公式也称命题演算的合式公式(Wellformformula,简写为wff)。定义1-6命题公式的递归定义如下：(1)单个的命题常元或命题变元是命题公式；(2)如果A是一个命题公式，则(┐A)也是命题公式；(3)如果A和B都是命题公式，则(A∧B)、(A∨B)、(A→B)、(A↔B)也是命题公式；(4)当且仅当有限次地应用（1）、(2)、（3）所得到的符号串是命题公式。思考：命题公式是命题吗？为什么？解答：命题公式不一定是命题。因为命题公式没有确定的真值。把符号命题翻译成自然语言命题：这种翻译比较简单，只要求用词准确，力求保持原命题的意思。例设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）练习：设P:天下雨。Q：我将进城。R：我有时间。试将下列命题形式化或翻译成自然语言命题。1.3.1真值表命题公式没有确定的真值，但可以假设公式中各个分量的不同取值来分析命题公式的真值情况。这样命题公式的真值情况就依赖于命题公式的结构和命题公式中各分量的真值指派。定义1-8设A是一个命题公式，为出现在A中的所有命题变元。给指定一组真值，称为对A的一组赋值（或真值指派）。为了使命题公式的真值情况一目了然，可采用真值表的形式表示。定义1-9对命题公式分量真值的各种可能指派，就确定了命题公式的各种真值情况，将其汇成表，就是该公式的真值表。真值表的构造规则：（1）在真值表左栏按字母顺序列出所有分量，右栏列出结果命题。（2）用0~2n-1的二进制计数顺序给命题分量指派真值。（3）为了使真值表更加明了，可将中间命题列在命题分量和结果命题之间。例1-9构造命题公式的真值表。Pq0001011110001001011例1-10构造公式的真值表。解：Pqr00000101001100101101110100010001001100101101110101011练习：Q∧(P→Q)→Q1．3．2命题公式的分类从真值表中可以发现，某些命题公式不论其分量真值作何指派，其真值总为真，或者总为假。例1-11构造下列命题的真值表。（1）（2）（3）解(1)1111000111010001011(p∧(p→q))→qp∧(p→q)p→qpq解（2）00000010110100011011¬(p→q)∧q¬(p→q)p→qpq解（3）101000101010101011110011000001010011100101110111(p→q)∧¬r¬rp→qpqr定理1-1任何两个重言式的合取或析取仍然是一个重言式。证明：根据定义，因为任何重言式不论分量真值作何指派，其真值总为真，而两个真值为真的命题的合取或析取一定为真。练习1.判别下列命题公式中哪些是重言式?矛盾式?偶然式?①(P→Q)↔(¬Q→¬P)②(P→Q)∧(Q→P)→(¬P∧Q)③(P↔Q)→(P∧Q→P)1.3.3等价公式从真值表中可以发现，两个有相同命题分量但结构不同的命题公式，对其分量真值的不同指派，其真值总相同，如：例1-12构造下列命题公式的真值表。（1）构造命题公式的真值表。（2）构造命题公式的真值表。解(1)Pq00010111100100110111011101解（2）Pq000101110110000100001010011001１.３.１命题公式的等价定义1-11给定两个命题公式A和B，设是所有出现在A和B中的命题分量，若对的任一组真值指派，A和B的真值都相同，则称A和B等价或逻辑相等。记为A⇔B。从真值表中可知，命题公式等价；等价。定理1-2设A和B是任意两个命题公式，A⇔B当且仅当A↔B为重言式。证明：若A⇔B，则A和B的真值相同，即同为真或同为假。根据双条件命题的定义A↔B为真，所以A↔B为重言式。若A↔B为重言式，则A↔B为永真，根据双条件命题的定义，A和B的真值相同，所以A⇔B。常用的命题等价公式有：其中包含否定、合取和析取联结词的等价命题公式称为命题定律，包含条件和双条件联结词的等价命题公式称为联结词归化。联结词归化交换律E1结合律E2分配律E3同一律E4互否律E5双否律E6等幂律E7零一律E8吸收律E9德·摩根律E10联结词归化E12E13E11E14E151．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推导证明吸收律。证明：同一律分配律零律同一律例1-14推导证明下列各式（1）证明：联结词规化分配律德.摩根公式（2）证明：联结词归化联结词归化结合律德.摩根公式联结词归化例1-15已知程序流程图如下,试化简该流程。PSRSWynyn解：运行S程序段的条件：p∨(¬p∧r)运行W程序段的条件：¬p∧¬r经过等价变换：执行程序段S的条件为：执行程序段W的条件为：P∨RSWyn例1-16化简下列各式（1）解：（2）解：利用等价演算可以证明公式的等价，也可以化简形式较复杂的命题公式。除此之外，还可以利用等价演算判断命题公式的类型。若命题公式A通过等价演算后A等价于1，则A必为重言式；若A等价于0，则A必为矛盾式。