《离散数学》课程PPT教学课件讲稿（数理逻辑）第二章 命题逻辑的等值和推理演算

第二章 命题逻辑的等值和推理演算 ■推理形式和推理演算是数理逻辑研究的基 本内容 推理过程是从前提出发,根据所规定的规 则来推导出结论的过程 ■重言式是重要的逻辑规律,正确的推理形 式,等值式都是重言式

第二章 命题逻辑的等值和推理演算 ◼ 推理形式和推理演算是数理逻辑研究的基 本内容 ◼ 推理过程是从前提出发，根据所规定的规 则来推导出结论的过程 ◼ 重言式是重要的逻辑规律，正确的推理形 式，等值式都是重言式

■本章对命题等值和推理演算进行讨论,是 以语义的观点进行的非形式的描述,不仅 直观且容易理解,也便于实际问题的逻辑 描述和推理。 ■严格的形式化的讨论见第三章所建立的公 理系统

◼ 本章对命题等值和推理演算进行讨论，是 以语义的观点进行的非形式的描述，不仅 直观且容易理解，也便于实际问题的逻辑 描述和推理。 ◼ 严格的形式化的讨论见第三章所建立的公 理系统

2.1等值定理 ■若把初等数学里的+、一、×、÷等运算符看作 是数与数之间的联结词,那么由这些联结词所表 达的代数式之间,可建立许多等值式如下 2-y2=(X+y)(x-y) (X+y)2=x2+2Xy+y2 sin2xcos2x= 1 在命题逻辑里也同样可建立一些重要的 等值式

2.1 等值定理 ◼ 若把初等数学里的＋、－、×、÷等运算符看作 是数与数之间的联结词，那么由这些联结词所表 达的代数式之间，可建立许多等值式如下： x 2－y 2 = (x＋y)(x－y) (x＋y)2 = x2＋2xy＋y 2 sin2x＋cos2x = 1 …… 在命题逻辑里也同样可建立一些重要的 等值式

2.1.1等值的定义 ■给定两个命题公式A和B,而P1…Pn是出现 于A和B中的所有命题变项,那么公式A和B 共有2个解释,若对其中的任一解释,公式 A和B的真值都相等,就称A和B是等值的 (或等价的)。记作A=B或A分B

2.1.1 等值的定义 ◼ 给定两个命题公式A和B, 而P1…Pn是出现 于A和B中的所有命题变项, 那么公式A和B 共有2n个解释, 若对其中的任一解释, 公式 A和B的真值都相等, 就称A和B是等值的 (或等价的)。记作A = B或A  B

■显然,可以根据真值表来判明任何两个公 式是否是等值的

◼ 显然，可以根据真值表来判明任何两个公 式是否是等值的

例1:证明(P∧_P)Q=Q 证明:画出(P∧P)∨Q与Q的真值表可看出 等式是成立的。 PQP∧PP∧P)∨Q FFTT FTFT FTFT 图21.1

例1: 证明(P∧P)∨Q = Q 证明: 画出(P∧P)∨Q与Q的真值表可看出 等式是成立的

例2:证明PV_P=Q∨_Q ■证明:画出P∨_PQ∨_Q的真值表,可看 出它们是等值的,而且它们都是重言式

例2: 证明P∨P = Q∨Q ◼ 证明: 画出P∨P, Q∨Q的真值表, 可看 出它们是等值的, 而且它们都是重言式

■从例1、2还可说明,两个公式等值并不要 求它们一定含有相同的命题变项。若仅在 等式一端的公式里有变项P出现,那么等式 两端的公式其真值均与P无关。例1中公式 (P∨_P)∨Q与Q的真值都同P无关,例2 中P∨_P,Q∨Q都是重言式,它们的真值 也都与P、Q无关

◼ 从例1、2还可说明, 两个公式等值并不要 求它们一定含有相同的命题变项。若仅在 等式一端的公式里有变项P出现, 那么等式 两端的公式其真值均与P无关。例1中公式 (P∨P) ∨Q与Q的真值都同P无关, 例2 中P∨P, Q∨Q都是重言式, 它们的真值 也都与P、Q无关

2.1.2等值定理 ■定理对公式A和B,A=B的充分必要条 件是A<>B是重言式。 若AQB为重言式(A、B不一定都是简单 命题,可能是由简单命题P1…,Pn构成的 对A,B的一个解释,指的是对P1…,Pn的 组具体的真值设定),则在任一解释下A 和B都只能有相同的真值,这就是定理的意 思

2.1.2 等值定理 ◼ 定理 对公式A和B, A = B的充分必要条 件是A  B是重言式。 ◼ 若A  B为重言式(A、B不一定都是简单 命题, 可能是由简单命题P1 , …, Pn构成的 对A, B的一个解释, 指的是对P1 , …, Pn的 一组具体的真值设定), 则在任一解释下A 和B都只能有相同的真值, 这就是定理的意 思

证明 若AB的真值都为T。依A<>B的定义只有 在A、B有相同的值时,才有A<>B=T。 于是在任一解释下,A和B都有相同的真值, 从而有A=B。反过来,若有A=B,即在 任一解释下A和B都有相同的真值,依AB是 重言式

证明 ◼ 若A  B是重言式, 即在任一解释下, A  B的真值都为T。依A  B的定义只有 在A、B有相同的值时, 才有A  B = T。 于是在任一解释下, A和B都有相同的真值, 从而有A=B。反过来，若有A = B, 即在 任一解释下A和B都有相同的真值, 依A  B的定义, A  B只有为真, 从而A  B是 重言式