命题逻辑基本概念课件幻灯片.pptVIP

关于合式公式的说明 定义1.6给出的合式公式的定义方式称为归纳定义或递归定义方式。 定义中引进了A,B等符号，用它们表示任意的合式公式，而不是某个具体的公式，这与p, p∧q, (p∧q)→r等具体的公式是有所不同的。 A,B等符号被称作元语言符号。p,q等被称作对象语言符号。 所谓对象语言是指用来描述研究对象的语言，而元语言是指用来描述对象的语言，这两种语言是不同层次的语言。 例如中国人学习英语时，英语为对象语言，而用来学习英语的汉语则是元语言。 关于合式公式的说明 (┐A)、(A∧B)等公式单独出现时，外层括号可以省去，写成┐A、A∧B等。 公式中不影响运算次序的括号可以省去，如公式(p∨q)∨(┐r)可以写成p∨q∨┐r。 合式公式的例子：(p→q)∧(q ? r)(p∧q)∧┐rp∧(q∧┐r) 不是合式公式的例子pq→r(p→(r→q) 定义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＝B?C，其中B,C的层次及n同(b)。 (3)若公式A的层次为k，则称A是k层公式。 例如：(┐p∧q)→r，(┐(p→┐q))∧((r∨s)?┐p) 分别为3层和4层公式 公式的解释 在命题公式中，由于有命题符号的出现，因而真值是不确定的。当将公式中出现的全部命题符号都解释成具体的命题之后，公式就成了真值确定的命题了。 (p∨q)→r 若p：2是素数，q：3是偶数，r：π是无理数，则p与r被解释成真命题，q被解释成假命题，此时公式(p∨q)→r被解释成：若2是素数或3是偶数，则π是无理数。（真命题） r被解释为：π是有理数，则(p∨q)→r被解释成：若2是素数或3是偶数，则π是有理数。（假命题） 将命题变项p解释成真命题，相当于指定p的真值为1，解释成假命题，相当于指定p的真值为0。 定义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。 赋值举例 在公式(┐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个不同的赋值。 定义1.9 真值表 将命题公式A在所有赋值下取值情况列成表，称作A的真值表。 构造真值表的具体步骤如下： (1)找出公式中所含的全体命题变项p1,p2,…,pn (若无下角标就按字典顺序排列)，列出2n个赋值。本书规定，赋值从00…0开始，然后按二进制加法依次写出各赋值，直到11…1为止。 (2)按从低到高的顺序写出公式的各个层次。 (3)对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。 公式A与B具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考虑构造真值表的中间过程。 说明 例1.8 求下列公式的真值表，并求成真赋值和成假赋值。 (1)(┐p∧q)→┐r (2)(p∧┐p)?(q∧┐q) (3)┐(p→q)∧q∧r 定义1.10 重言式、永真式、可满足式 设A为任一命题公式 (1)若A在它的各种赋值下取值均为真,则称A是重言式(tautology)或永真式。 (2)若A在它的各种赋值下取值均为假,则称A是矛盾式(contradiction)或永假式。 (3)若A不是矛盾式,则称A是可满足式（satisfactable formula）。 定义1.10的进一步说明 A是可满足式的等价定义是：A至少存