离散数学――公式与解释

1在命题逻辑中，命题又有命题常元和命题变元之分。一个确定的具体的命题，称为命题常元；一个不确定的泛指的任意命题，称为命题变元。公式与解释2命题常元和命题变元均可用字母P等表示。由于在命题逻辑中并不关心具体命题的涵义，只关心其真值，因此，可以形式地定义它们如下：以真或1、假或0为其变域的变元，称为命题变元；真或1、假或0称为命题常元。3命题公式定义4.2.1命题公式是由下列规则生成：①命题变元是公式;②若A是一个公式，则┐A也是一个公式。③若A、B是公式，则A∧B、A∨B、A→B和AB都是公式。④所有的公式只能有限次地使用①、②和③生成。4简化规则：①规定联结词的优先级由高到低的次序为：┐、∧、∨、→、②公式(┐A)的括号可以省略，即(┐A)写成┐A。③最外层的圆括号可以省略。5公式的解释和赋值：设G为一个命题公式，P1,P2,…，Pn为出现在G中的所有的命题变元.给P1,P2,…，Pn指定一组真值，称为对G的一个赋值或解释，记作I，公式G在I下的真值记作TI(G).例：公式G=p∧q→r，I:p=1,q=1,r=0是G的一个解释在这个解释下G的真值为0，即TI(G)=0。那么111，011，010…也是G的解释.一般来说，有n个命题变元的公式共有2n个不同的解释。6构造真值表的步骤：①命题变元按一定顺序排列。②对每个赋值，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。将公式G在其所有解释下所取的真值列成一个表，称为G的真值表。7例1:G=p→(p∨q)，其真值表为：pqp∨qp→(p∨q)00010111101111118例2:G=p∧(p→q)∧(p→┐q)，真值表为：pq┐qp→qp∧(p→q)p→┐qp∧(p→q)∧(p→┐q)00110100101010101001011011009(1)若A在它的各种赋值下取值都为真，则称A为重言式或恒真式(2)若A在它的各种赋值下取值都为假，则称A为矛盾式或恒假式(3)若A至少存在一组赋值使A为真(A不是恒假的)，则称A为可满足式恒真式是可满足式，但可满足式不一定是恒真式定义4.2.4设A为一个命题公式10当公式G对赋值I为真时，称I满足G，或I是G的成真赋值，记为TI(G)=1；反之I是G的成假赋值，或称I弄假G，记为TI(G)=0。（见教材P89）11等值演算n个命题变项只能生成个不同的真值表定义4.2.5给定两个公式A和B，设P1，P2，…，Pn为所有出现于A和B中的命题变元，若给P1，P2，…，Pn任一组赋值，A和B的真值都相同，则称A和B是等价的或逻辑相等的,记作AB.可通过判断A与B的真值表是否相同，来判断A与B是否等价。n2212例：p∧(p→q)→q与p→(p∨q)是否等价？pqp∧(p→q)→qp→(p∨q)001101111011111113定理1AB当且仅当AB是恒真式。有时也称AB是恒真双条件式。等价式有下列性质：①自反性，即对任意公式A，有AA。②对称性，即对任意公式A和B，若AB，则BA。③传递性，即对任意公式A、B和C，若AB、BC，则AC。14基本等价式——命题定律在判定公式间是否等价，有一些简单而又经常使用的等价式，称为基本等价式或称命题定律。现将这些命题定律列出如下：(1)双否定：AA。(2)交换律：A∧BB∧A，A∨BB∨A，ABBA。15(3)结合律：(A∧B)∧CA∧(B∧C)，(A∨B)∨CA∨(B∨C)，(AB)CA(BC)。(4)分配律：A∧(B∨C)(A∧B)∨(A∧C)，A∨(B∧C)(A∨B)∧(A∨C)。(5)德·摩根律：(A∧B)A∨B，(A∨B)A∧B。(6)幂等律：A∧AA，A∨AA。16(7)同一律：A∧1A，A∨0A。(8)零律：A∧00，A∨11。(9)吸收律：A∧(A∨B)A，A∨(A∧B)A。(10)矛盾律：A∧A0(11)排中律：A∨A1。(12)条件式转化律：A→BB→A，A→BA∨B。17(13)双条件式转化律：AB(A→B)∧(B→A)(A∧B)∨(A∧B)AB(AB)输出律：(A∧B)→CA→(B→C)。归谬律：(A→B)∧(A→B)A。恒真式与恒假式的判别法：A为恒真式当且仅当A1，A为恒假式当且仅当A018例：证明下列命题的等价关系：(1)(p∨q)→r(p→r)∧(q→r)(2)(q→(p→r)(p∧q)→r19if(A){if(B)x;elsey;}else{if(B)x;elsey;}20分析：执行ｘ的条件：（Ａ∧Ｂ）∨（Ａ∧Ｂ）（（Ａ∧Ｂ）∨Ａ）∧（（Ａ∧Ｂ）∨Ｂ）（Ａ∨Ａ）∧（Ｂ∨Ａ）∧ＢＴ∧ＢＢ执行y的条件：同理Ｂ故程序化为：if(B)x;elsey;与Ａ无关。21本节总结本节主要内容有:1.用递归的方法定义了命题公式；2.给出了命题的解释或赋值的概念；3.定义了公式的真值表；4.给出了恒真、恒假及可满足公式的定义;5.给出了两个命题公式等价的概念及13个基本的等价式;6.给出了命题逻辑的一个简单的实际应用.