命题公式分类及等值演算.ppt

命题公式及分类等值演算 福建师范大学数学与计算机科学学院 1.2 命题公式及其赋值 简单命题是真值唯一确定的命题逻辑中最基本的研究单位，所以也称简单命题为命题常项或命题常元。用p,q,r,…等小写字母表示命题常项。 称真值可以变化的陈述句为命题变项或命题变元 。也用p,q,r,…表示命题变项。 当p,q,r,…表示命题变项时，它们就成了取值0或1的变项，因而命题变项已不是命题。 这样一来，p,q,r,…既可以表示命题常项，也可以表示命题变项。在使用中，需要由上下文确定它们表示的是常项还是变项。 将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为合式公式或命题公式。 定义1.6 合式公式的递推定义 (1)单个命题变项是合式公式，并称为原子命题公式。 (2)若A是合式公式，则(┐A)也是合式公式。 (3)若A，B是合式公式，则(A∧B)，(A∨B)，(A→B)，(A?B)也是合式公式。 (4)只有有限次地应用(1)～(3)形式的符号串才是合式公式。 合式公式也称为命题公式或命题形式，并简称为公式。 设A为合式公式，B为A中一部分，若B也是合式公式，则称B为A的子公式。 关于合式公式的说明 (┐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是偶数，则π是有理数。（假命题） 定义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个不同的赋值。 真值表 将命题公式A在所有赋值下取值情况列成表，称作A的真值表。 例 求下列公式的真值表，并求成真赋值和成假赋值。 (1)(┐p∧q)→┐r (2)(p∧┐p)?(q∧┐q) (3)┐(p→q)∧q∧r 定义1.9 重言式、永真式、可满足式 设A为任一命题公式 (1)若A在它的各种赋值下取值均为真,则称A是重言式或永真式（Tautology）。 (2)若A在它的各种赋值下取值均为假,则称A是矛盾式或永假式(Contradiction)。 (3)若A不是矛盾式,则称A是可满足式。 定义1.9的进一步说明 A是可满足式的等价定义是：A至少存在一