上节讨论了简单命题(原子命题)和复合命题以及它们的符号化形式简单命题是命题逻辑中最基本的研究单位,其真值是确定的,又称作命题常项或命题常元,命题常项相当于初中的常数。初等数学中还有变量,对应地这里有命题变项。取值1(真)或0(假)的变元称作命题变项或命题变元可以用命题变项表示真值可以变化的陈述句.命题变项不是命题,命题变项与命题常项的关系如同初等数学中变量与常量的关系今后也用p,q,r,…表示命题变项这样来,P,q,r,…既可以表示命题常项,又可以表示命题变项,通常可以由上下文确定。
将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为合式公式,当使用联结词集{┓,A,V,→,<->}时,合式公式定义如下.
定义1.6 (1)单个命题变项和命题常项是合式公式,并称为原子命题公式.
若A是合式公式,则(┓A)是合式公式若A,B是合式公式,则(A∧B),(AVB),(A→B),(A<->B)是合式公式有限次地应用(1)~(3)形成的符号串是合式公式合式公式也称为命题公式或命题形式,简称为公式.
设A为合式公式,B为A中一部分,若B也是合式公式,则称B为A的子公式.
对于定义1.6,要做以下说明:
定义1.6给出的合式公式的定义方式称为归纳定义或递归定义方式,下文中还将多次出现这种定义方式定义中引进了A,B等符号,用它们表示任意的合式公式,称作元语言符号.而某个具体的公式,如p,P∧q,(P∧q)→r等称作对象语言符号.所谓对象语言是指用来描述研究对象的语言，而元语言是指用来描述对象语言的语言,这两种语言是不同层次的语言.做一个不完全恰当的类比，中国人学英语,常用汉语描述英语,英语是对象语言,而汉语就成了元语言。为方便起见,(┓A),(A∧B)等公式单独出现时,外层括号可以省去,写成┓A,A∧B等，另外,公式中不影响运算次序的括号也可以省去,如公式(pVq)V(┓r)可以写成pVgV┓r由定义可知,(p→q)∧(q<->r),(P∧q)∧┓r,p∧(q∧┓r)等都是合式公式，而pq->r,p->(r->q等不是合式公式。
下面给出公式层次的定义
定义1.7(1)若公式A是单个的命题变项,则称A为0层公式
称是n+1(n≥0)层公式是指下面情况之一：A=┓B,B是n层公式A=BAC,其中B,C分别为i层和j层公式,且n=max(i,j)A=BVC,其中B,C的层次及n同(b)A=B→C,其中B,C的层次及n同(b)A=B<->C,其中B,C的层次及n同(b)若公式A的层次为k.则称A是k层公式例如,(┓p∧q)→r,((p→┓q))∧((rVs)<->┓p)分别为3层和4层公式
在命题公式中.由于有命题变项的出现,因而真值是不确定的,用命题常项替换公式中的命题变项称作解释.当将公式中出现的全部命题变项都解释成具体的命题常项之后,公式就成了真值确定的命题.例如,在公式(pVq)→r中,若将p解释成:2是素数,q解释成:3是偶数,r解释成:√2是无理数,则公式(pVq)→r被解释成:若2是素数或3是偶数,则2是无理数.这是一个真命题.若p,q的解释不变,r被解释为:2是有理数,则(pVq)→r被解释成:若2是素数或3是偶数,则√2是有理数.这是一个假命题,还可以给出这个公式各种不同的解释,其结果不是得到真命题就是得到假命题.其实,将命题变项p解释dfdfj命题,相当于指定p的真值为1,解释成假命题,相当于指定p的真值为0
定义1.8设p1,P2,…,Pn是出现在公式A中的全部命题变项,给p1,P2,…,Pn各指定一个真值,称为对A的一个赋值或解释.若指定的一组值使A为1,则称这组值为A的dfdfj赋值;若使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)V(P1∧P2)中,000(P1=0,P2=0,P3=0),110(P1=1,P1=1,P3=0)都是dfdfj赋值,而001(P1=0,P2=0,P3=1),011(P1=0,P2=1,p3=1)都是成假赋值.在(pA┓q)→r中,011(p=0,q=1,r=1)为dfdfj赋值,100(p=1,q=0,r=0)为成假赋值.
不难看出,含n(n≥1)个命题变项的公式共有2"个不同的赋值
定义1.9将命题公式A在所有赋值下取值情况列成表,称作A的真值表
构造真值表的具体步骤如下
找出公式中所含的全体命题变项P1,P2,...,pn(若无下角标就按字母顺序排列),列出2n个赋值.赋值从00…0开始,然后按二进制加法依次写出每个赋值,直到11…1为止按从低到高的顺序写出公式的各个层次对应各个斌值计算出各层次的真值,直到最后计算出公式的真值如果两个公式A与B的真值表对所有赋值最后一列都相同,即最后结果都相同,则称这两个真值表相同,而不考虑构造真值表的中间过程
例1.8写出下列公式的真值表,并求它们的dfdfj赋值和成假赋值:
(┓p∧q)-->┓r(p^┓q)<->(q^┓q)┓(p->p)^q^r解：公式（1）是含3个命题变项的3层合式公式。它的真值表如表1.2所示：
从表1.2可知公式(1)的成假赋值为011,其余7个赋值都是dfdfj赋值
公式(2)是含2个命题变项的3层合式公式,它的真值表如表1.3所示.从表1.3看出该公式的4个赋值全是dfdfj赋值,即无成假赋值。
公式（3）是含3个命题变项的4层合式公式，它的真值表如表1.4所示。不难看出，该公式的8个赋值全是成假赋值，无dfdfj赋值。
表1.2~表1.4都是按构造真值表的步骤一步一步地构造出来的,这样构造真值表不易出错.如果构造的思路比较淸楚,有些层次可以省略
根据公式在各种赋值下的取值情况,可按下述定义将命题公式进行分类
定义1.10设A为任一命题公式
若A在它的各种赋值下取值均为真,则称A是重言式或永真式若A在它的各种赋值下取值均为假,则称A是矛盾式或永假式若A不是矛盾式A是可满足式从定义不难看出以下几点
A是可满足式的等价定义是:A至少存在一个dfdfj赋值重言式一定是可满足式,但反之不真.若公式A是可满足式,且它至少存在一个成假赋值则称A为非重言式的可满足式真值表可用来判断公式的类型若真值表最后一列全为1,则公式为重言式若真值表最后一列全为0,则公式为矛盾式若真值表最后一列中至少有一个1,则公式为可满足式从表1.2~表1.4可知,例1.8中,公式(1)(┓p^g)→┓r为非重言式的可满足式,公式(2)(p^┓p)<->(q^┓q)为重言式,而公式(3)┓(P->q)^q^r为矛盾式
从以上的讨论可知,真值表不但能准确地给出公式的dfdfj赋值和成假赋值,而且能判断公式的类型
给定n个命题变项,按合式公式的形成规则,自然可以形成无穷多种形式各异的公式,现在要问:这些公式的真值表是否也有无穷多种不同的情况呢?答案是否定的.n个命题变项共产生2“个不同的赋值,而任何公式在每种赋值下只能取两个值,0或1,于是含n个命题变项的公式的真值表只有2种不同的情况,因而必有无穷多个公式具有相同的真值表
例1.9下列各公式均含两个命题变项p与q,它们中哪些具有相同的真值表?
(p→q)P<->q┓(p^┓q)(p->q)^(q->p)┓qvp解 构造过程略去不写,表1.5给出了5个公式的真值表,从表中可看出,(1),(3)具有相同的真值表,(2),(4)具有相同的真值表
设公式A,B中共含有命题变项P1,P2,...,pn而A或B不全含这些命题变项,比如A中不含pi,pi+1,...,pn,i>=2,称这些命题变项为A的哑元,A的取值与哑元无关,因而在讨论A与B是有相同的真值表时,可将A,B都看成含P1,P2,…,Pn的命题公式
例1.10 下列公式中,哪些具有相同的真值表
(1) p->q
(2) ┓qvr
(3) (┓pvq)^((p^r)->p)
(4) (q->r)^(p->p)
解 本例中给出的4个公式,总共有3个命题变项P,q和r,r是公式(1)的哑元,P是公式(2)的哑元,讨论它们是否有相同的真值表时,均按3个命题变项写出它们的真值表.表1.6列出4个公式的真值表,中间过程省略了.从表中看出,(1)与(3)有相同的真值表,(2)与(4)有相同的真值表.