资源描述：
《§3命题形式和真值表》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、§3命题形式和真值表°上节介绍了将命题表示为符号串。°是否每个符号串都是命题呢？pq→°什么样的符号串才能表示命题呢？如下命题形式定义的符号串表示的才是命题。命题形式的定义定义6命题形式是由命题变元和联结词按以下规则组成的符号串:(1)任何命题变元都是命题形式---此时称为原子命题形式;(2)如果α是命题形式,则(¬α)也是命题形式;(3)如果α、β是命题形式,则(α∨β)、(α∧β)、(α→β)和(α↔β)都是命题形式;(4)只有有限次地应用(1)—(3)构成的符号串才是命题形式.下列符号串都是命题形式：(¬p)(
2、p∧(¬q))(p∨(¬p))(p↔(¬p))(p∧(¬p))((p∧p)→(¬(p∨r)))下列符号串是否为命题形式？（1）pq→（2）(p¬q)（3）(p∧(¬q))（4）p∧(¬q)（5）((¬q))（6）¬p一些注记1.定义6是归纳定义，而不是循环定义。(1)是奠基，(2)、(3)是归纳步骤。2.如果在(2)和(3)中将括号去掉，结果如何？p→q→r与P→q→r、P→q→r3.如仅去掉(2)和(3)中某类公式的括号呢？例如，仅去掉(2)中括号。(p∧¬q)——¬的优先级高于其它的。4.如果规定省略命题形式最外
3、层括号，与2的差别。约定¢¬的优先级高于其它的¢省略命题形式最外层括号命题形式的简单性质¢任一个命题形式必为下列形式之一：命题变元、(¬α)、(α∨β)、(α∧β)、(α→β)或(α↔β)¢命题形式的BNF(BacusNormalForm):α::=p
4、(¬α)
5、(α∨β)
6、(α∧β)
7、(α→β)
8、(α↔β)¢每个命题形式都是有限符号串。指派¢命题形式的真假由它中命题变元的值完全确定。¢定义7设α为一个命题形式,α中出现的所有命题变元都在pp，…，p中,对序列pp，…，p1，2n1，2n指定的的任一真假值序列t，t，
9、…，t称为α的关12n于pp，…，p的一个指派(asignment)，其中t1，2ni=0或1,i∈N,1N≤i≤n.即指派是从{pp，…，p}到{0，1}的一个函数。1，2n成真指派¢若p1，p2，…，pn的一个指派使α为真，则称此指派为α的一个成真指派¢若p1，p2，…，pn的一个指派使α为假，则称此指派为α的一个成假指派。¢由定义可知：¾¬p关于p的成真指派为0,成假指派为1.¾p∧q关于p、q的成真派为<1,1>,成假指派为<1,0>,<0,1>,<0,0>.¾p∨q关于p、q的成真指派为<1,1>,<0,1
10、>,<1,0>,成假指派为<0,0>.¾不难给出p→q、p↔q的成真和成假指派.(§2.1).例5求(p∧q)→(¬(q∨r))的成真和成假指派。解：令(p∧q)→(¬(q∨r))为α。要使α为假，必须p∧q为真且¬(q∨r)为假。从而p∧q必须为真，且q∨r也必须为真。故α的成假指派为(1，1，1)和(1，1，0).α的成真指派为(0，0，0)、(1，0，0)、(0，1，0)、(0，0，1)、(0，1，1)、(1，0，1)。定义8命题形式在所有可能的指派下所取值列成的表称为真值表.(p∧q)→(¬(q∨r))的真值
11、表Pqr(p∧q)¬(q∨r)α000011100011010001001001110100101001011001111100p∧(¬p)、p∨(¬p)的真值表解：Pp∧(¬p)p∨(¬p)001101(¬p)∨q、p→q的真值表解：pq(¬p)∨qp→q0011011110001111p→(q→r)、(p→q)→r的真值表pqrp→(q→r)(p→q)→r0001010011010100011111000101110111111111命题形式的类型定义9¢命题形式α称为重言式(或永真式)，如果α关于其中出现的命题
12、变元的所有指派均为成真指派.¢命题形式α称为矛盾式(永假式)，如果α对于其中出现的命题变元的所有指派均为成假指派.¢一个命题形式α称为可满足式,如果α对于其中出现的命题变元的某个指派为成真指派.例如：p∧(¬p)为矛盾式，p∨(¬p)为重言式。(¬p)∨q为可满足式。例7证明下列各式都是重言式(1)p→(q→(p∧q))证明：pqp∧qq→(p∧q)p→(q→(p∧q))00011100110100111111例7(续）(2)((p↔p)∧(q↔q))→((p∧q)↔(p∧q))1111ppqqα1101**110*
13、*1**011**10100001001111100111111与哑元的无关性定理1设命题形式α中出现的命题变元都在p,p,…,p中,p,…,p是另外m个不在α中12nn+1n+m出现的命题变元.对于p,p,…,p,p,…,p12nn+1n+m的任意两个指派:和12nn+1n+m，12
