命题公式分类及等值演算

命题公式分类及等值演算第1页，课件共29页，创作于2023年2月1.2命题公式及其赋值简单命题是真值唯一确定的命题逻辑中最基本的研究单位，所以也称简单命题为命题常项或命题常元。用p,q,r,…等小写字母表示命题常项。称真值可以变化的陈述句为命题变项或命题变元。也用p,q,r,…表示命题变项。当p,q,r,…表示命题变项时，它们就成了取值0或1的变项，因而命题变项已不是命题。这样一来，p,q,r,…既可以表示命题常项，也可以表示命题变项。在使用中，需要由上下文确定它们表示的是常项还是变项。将命题常项或命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为合式公式或命题公式。第2页，课件共29页，创作于2023年2月定义1.6合式公式(1)单个命题常项或命题变项是合式公式，并称为原子命题公式。(2)若A是合式公式，则(┐A)也是合式公式。(3)若A，B是合式公式，则(A∧B)，(A∨B)，(A→B)，(AB)也是合式公式。(4)只有有限次地应用(1)～(3)组成的符号串才是合式公式。合式公式也称为命题公式或命题形式，并简称为公式。设A为合式公式，B为A中一部分，若B也是合式公式，则称B为A的子公式。

第3页，课件共29页，创作于2023年2月关于合式公式的说明(┐A)、(A∧B)等公式单独出现时，外层括号可以省去，写成┐A、A∧B等。公式中不影响运算次序的括号可以省去，

如公式(p∨q)∨(┐r)可以写成p∨q∨┐r。合式公式的例子：

(p→q)∧(qr)

(p∧q)∧┐r

p∧(q∧┐r)不是合式公式的例子

pq→r

(p→(r→q)

第4页，课件共29页，创作于2023年2月定义1.7公式层次

(1)若公式A是单个命题（常项或变项），则称A为0层合式。

(2)称A是n+1(n≥0)层公式是指下面情况之一：

(a)A＝┐B，B是n层公式；

(b)A＝B∧C，其中B,C分别为i层和j层公式，且n=max(i,j)；

(c)A＝B∨C，其中B,C的层次及n同(b)；

(d)A＝B→C，其中B,C的层次及n同(b)；

(e)A＝BC，其中B,C的层次及n同(b)。

(3)若公式A的层次为k，则称A是k层公式。例如：(┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)

分别为3层和4层公式第5页，课件共29页，创作于2023年2月公式的解释在命题公式中，由于有命题符号的出现，因而真值是不确定的。当将公式中出现的全部命题符号都解释成具体的命题之后，公式就成了真值确定的命题了。例如：(p∨q)→r若p：2是素数，q：3是偶数，r：π是无理数，则p与r被解释成真命题，q被解释成假命题，此时公式(p∨q)→r被解释成：若2是素数或3是偶数，则π是无理数。（真命题）r被解释为：π是有理数，则(p∨q)→r被解释成：若2是素数或3是偶数，则π是有理数。（假命题）第6页，课件共29页，创作于2023年2月定义1.8赋值或解释设p1,p2,…,pn是出现在公式A中的全部命题变项，给p1,p2,…,pn各指定一个真值，称为对A的一个赋值或解释。若指定的一组值使A的真值为1，则称这组值为A的成真赋值；若使A的真值为0，则称这组值为A的成假赋值。对含n个命题变项的公式A的赋值情况做如下规定：

(1)若A中出现的命题符号为p1,p2,…,pn，给定A的赋值α1α2,…,αn

是指p1＝α1，p2＝α2,…，pn＝αn。

(2)若A中出现的命题符号为p,q,r...,给定A的赋值α1,α2,…,αn是指p＝α1，q＝α2,…，最后一个字母赋值αn。上述αi取值为0或1，i＝1,2,…,n。

第7页，课件共29页，创作于2023年2月赋值举例在公式(┐p1∧┐p2∧┐p3)∨(p1∧p2)中，

000(p1＝0，p2＝0，p3＝0)，

110(p1＝1，p2＝1，p3＝0)都是成真赋值，

001(p1＝0，p2＝0，p3＝1)，

011(p1＝0，p2＝1，p3＝1)都是成假赋值。在(p∧┐q)→r中，

011(p1＝0，p2＝1，p3＝1)为成真赋值，

100(p1＝1，p2＝0，p3＝0)为成假赋值。重要结论：

含n(n≥1)个命题变项的公式共有2n个不同的赋值。

第8页，课件共29页，创作于2023年2月真值表将命题公式A在所有赋值下取值情况列成表，称作A的真值表。构造真值表的具体步骤如下：(1)找出公式中所含的全体命题变项p1,p2,…,pn(若无下角标就按字典顺序排列)，列出2n个赋值。本书规定，赋值从00…0开始，然后按二进制加法依次写出各赋值，直到11…1为止。(2)按从低到高的顺序写出公式的各个层次。(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。

公式A与B具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考虑构造真值表的中间过程。

说明第9页，课件共29页，创作于2023年2月例

求下列公式的真值表，并求成真赋值和成假赋值。(1)(┐p∧q)→┐r(2)(p∧┐p)(q∧┐q)(3)┐(p→q)∧q∧r

第10页，课件共29页，创作于2023年2月定义1.9重言式、永真式、可满足式设A为任一命题公式(1)若A在它的各种赋值下取值均为真,则称A是重言式或永真式。(2)若A在它的各种赋值下取值均为假,则称A是矛盾式或永假式。(3)若A不是矛盾式,则称A是可满足式。

第11页，课件共29页，创作于2023年2月定义1.9的进一步说明A是可满足式的等价定义是：A至少存在一个成真赋值。重言式一定是可满足式，但反之不真。因而，若公式A是可满足式，且它至少存在一个成假赋值，则称A为非重言式的可满足式。真值表可用来判断公式的类型:若真值表最后一列全为1，则公式为重言式。若真值表最后一列全为0，则公式为矛盾式。若真值表最后一列中至少有一个1，则公式为可满足式。第12页，课件共29页，创作于2023年2月例题例下列各公式均含两个命题变项p与q，它们中哪些具有相同的真值表?

(1)p→q (4)(p→q)∧(q→p)

(2)pq (5)┐q∨p

(3)┐(p∧┐q)

第13页，课件共29页，创作于2023年2月例题例下列公式中,哪些具有相同的真值表?

(1)p→q

(2)┐q∨r

(3)(┐p∨q)∧((p∧r)→p)

(4)(q→r)∧(p→p)

第14页，课件共29页，创作于2023年2月两公式什么时候代表了同一个命题呢？抽象地看，它们的真假取值完全相同时即代表了相同的命题。设公式A,B共同含有n个命题变项，若A与B有相同的真值表，则说明在2n个赋值的每个赋值下，A与B的真值都相同。于是等价式AB应为重言式。第15页，课件共29页，创作于2023年2月等值的定义及说明定义1.10设A,B是两个命题公式，若A,B构成的等价式AB为重言式，则称A与B是等值的，记作AB。

说明在A或B中命题变项可能不同。

p→q(┐p∨q)∨(┐r∧r)用真值表可以验证两个公式是否等值。第16页，课件共29页，创作于2023年2月例题例判断下面两个公式是否等值

┐(p∨q)与┐p∧┐q解答说明在用真值表法判断AB是否为重言式时，真值表的最后一列可以省略。等值第17页，课件共29页，创作于2023年2月例题例判断下列各组公式是否等值

(1)p→(q→r)与(p∧q)→r

(2)(p→q)→r与(p∧q)→r

解答等值不等值第18页，课件共29页，创作于2023年2月常用的等值式1.双重否定律 A┐┐A2.幂等律 AA∨A, AA∧A3.交换律 A∨BB∨A， A∧BB∧A4.结合律 (A∨B)∨CA∨(B∨C)

(A∧B)∧CA∧(B∧C)5.分配律

A∨(B∧C)(A∨B)∧(A∨C)

（∨对∧的分配律）

A∧(B∨C)(A∧B)∨(A∧C)

（∧对∨的分配律）6.德·摩根律

┐(A∨B)┐A∧┐B

┐(A∧B)┐A∨┐B7.吸收律

A∨(A∧B)A，

A∧(A∨B)A

第19页，课件共29页，创作于2023年2月

8.零律

A∨11,A∧009.同一律

A∨0A，A∧1A10.排中律

A∨┐A111.矛盾律

A∧┐A012.蕴涵等值式

A→B┐A∨B13.等价等值式

AB(A→B)∧(B→A)14.假言易位

A→B┐B→┐A15.等价否定等值式

AB┐A┐B16.归谬论

(A→B)∧(A→┐B)┐A第20页，课件共29页，创作于2023年2月等值演算与置换规则每个等值式模式都给出了无穷多个同类型的具体的等值式。

例：在蕴涵等值式A→B┐A∨B中，其中A,B,C可以代表任意的公式，例如

取A=p，B=q时，得等值式p→q┐p∨q

取A=p∨q∨r，B=p∧q时，得等值式

(p∨q∨r)→(p∧q)┐(p∨q∨r)∨(p∧q)第21页，课件共29页，创作于2023年2月这些具体的等值式都被称为原来的等值式模式的代入实例。由已知的等值式推演出另外一些等值式的过程为等值演算。置换规则设Φ(A)是含公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中所有的A后得到的命题公式，若BA，则Φ(B)Φ(A)。第22页，课件共29页，创作于2023年2月关于等值演算的说明等值演算的基础等值关系的性质：

自反性：AA。

对称性：若AB，则BA。

传递性：若AB且BC，则AC。基本的等值式置换规则等值演算的应用证明两个公式等值判断公式类型解判定问题第23页，课件共29页，创作于2023年2月等值演算的应用举例证明两个公式等值

(p→q)→r(p∨r)∧(┐q∨r)(p→q)→r(┐p∨q)→r

（蕴含等值式、置换规则）

┐(┐p∨q)∨r （蕴含等值式、置换规则）(p∧┐q)∨r

（德摩根律、置换规则）(p∨r)∧(┐q∨r) （分配律、置换规则）说明也可以从右边开始演算因为每一步都用置换规则，故可不写出熟练后，基本等值式也可以不写出通常不用等值演算直接证明两个公式不等值解答第24页，课件共29页，创作于2023年2月例用等值演算法验证等值式

(p∨q)→r(p→r)∧(q→r)(p→r)∧(q→r)

(┐p∨r)∧(┐q∨r) (蕴含等值式)(┐p∧┐q)∨r (分配律) ┐(p∨q)∨r (德摩根律) (p∨q)→r (蕴含等值式)解答第25页，课件共29页，创作于2023年2月例

证明：(p→q)→r与p→(q→r)不等值方法一、真值表法。

方法二、观察法。易知，010是(p→q)→r的成假赋值，而010是p→(q→r)的成真赋值，所以原不等值式成立。

方法三、通过等值演算化成容易观察真值的情况，再进行判断。

A=(p→q)→r(┐p∨q)→r

（蕴涵等值式）

┐(┐p∨q)∨r （蕴涵等值式）

(p∧┐q)∨r

（德摩根律）

B=p→(q→r)┐p∨(┐q∨r)

（蕴涵等值式） ┐p∨┐q∨r

（结合律）

000，010是A的成假赋值，而它们是B的成真赋值