《数理逻辑 (2)》由会员分享，可在线阅读，更多相关《数理逻辑 (2)（32页珍藏版）》请在金锄头文库上搜索。
1、电子科技大学离散数学课程组国家精品课程离 散 数 学数学科学学院*任课教师:杨春电子科技大学离散数学课程组国家精品课程122-23.3 命题公式、解释与真值表定义（1）一个特定的命题是一个常值命题，其真 值已经确定；(2)一个任意的没有赋予具体内容的原子命题是一 个变量命题，常称它为命题变量(或命题变元)， 该命题变量无具体的真值，它的变域是集合T， F(或0，1)电子科技大学离散数学课程组国家精品课程122-33.3.1 命题公式定义3.3.2 (命题公式)命题变元本身是一个公式；如G是公式，则(G)也是公式；如G，H是公式，则(GH)、(GH)、(GH)、 (GH)也是公式；命题公式是仅由
2、有限步使用规则1-3后产生的结 果。该公式常用符号G、H、等表示。电子科技大学离散数学课程组国家精品课程122-4例3.3.1 符号串：(P(QR)(Q(SR)；(PQ)； (P(PQ)；(PQ)(RQ)(PR)。 等都是命题公式。例3.3.2 符号串：(PQ)Q)； (PQ；(PQ(R； PQ。等都不是合法的命题公式。例电子科技大学离散数学课程组国家精品课程122-5例3.3.3试用符号形式写出下列命题：n虽然今天天气晴朗，老陈还是不来；n除非你陪伴我或代我叫车子，否则我将不出 去；n停机的原因在于语法错误或者程序错误；n若a和b是偶数，则a+b是偶数；n我们要做到身体好、学习好、工作好，为
3、祖 国四化建设而奋斗。 P：今天天气晴朗，Q：老陈不来, 则有：PQP：你陪伴我； Q：你代我叫车子；R：我出去 。 则有：RPQ或PQRP：停机的原因在于语法错误， Q：停机的原因在于程序错误， 则有：PQP：a是偶数， Q：b是偶数， R：a+b是偶数， 则有：PQRP：我们要做到身体好 Q：我们要做到学习好 R：我们要做到工作好 S：我们要为祖国四化建设而奋斗 则有：PQR S电子科技大学离散数学课程组国家精品课程122-6公式(P(QR)(Q(SR)可表示如下：(P(QR)(Q(SR)P(QR) Q(SR)P QR Q SRQ R S RS例3.3.4电子科技大学离散数学课程组国家精品
4、课程122-73.3.2 公式的解释与真值表定义3.3.3 设P1、P2、Pn是出现在公式G中的 所有命题变元，指定P1、P2、Pn一组真值， 则这组真值称为G的一个解释,常记为。一般来说，若有个命题变元，则应有2n个 不同的解释。如果公式G在解释下是真的，则称满足G ；如果G在解释下是假的，则称弄假G。定义3.3.4 将公式G在其所有可能解释下的真值 情况列成的表，称为G的真值表。电子科技大学离散数学课程组国家精品课程122-8例3.3.5求下面公式的真值表：(P(PQ)R)Q其中，、是的所有命题变元。P Q R PPQ(PQ)RP(PQ)R)G 0 0 0 10 011 0 0 1 10
5、011 0 1 0 1 1 01 1 0 1 1 1 1 111 1 0 0 0 1 000 1 0 1 0 1 111 1 1 0 0 0 001 1 1 1 0 0 001电子科技大学离散数学课程组国家精品课程122-9例3.3.5（续）P Q R(P(PQ)R)Q 0 0 01 0 0 11 0 1 01 0 1 11 1 0 00 1 0 11 1 1 01 1 1 1 1进一步化简为：电子科技大学离散数学课程组国家精品课程122-10定义3.3.5公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。公式G称为
6、可满足的，如果它不是永假的。电子科技大学离散数学课程组国家精品课程122-11例3.3.7写出下列公式的真值表，并验证其公式是重言 式、矛盾式、可满足公式。（1）G1 = ()()；（2）G2 = (Q)(Q)(Q) ；（3）G3 = (P Q)Q。电子科技大学离散数学课程组国家精品课程122-12解：P Q() ()( Q) (Q)(Q )(P Q) Q0 01 0 1 0 11 0 1 1 0 1 0 1 1 11 0 0永真公式 可满足公式永假公式可满足公式三个公式的真值表如下：电子科技大学离散数学课程组国家精品课程122-13定义3.3.6 设G、H是公式，如果在任意解释下， G与H的
7、真值相同，则称公式G、H是等价的，记作G H。基本等价公式定理3.3.1公式G、H等价的充分必要条件是公式GH是永真公式。说明：GH的结果仍是一个命题公式。GH表示“命题公式G等价于命题公式H。电子科技大学离散数学课程组国家精品课程122-14证明:“”假定G，H等价，则G，H在其任意解 释下或同为真或同为假，于是由“”的意 义知，GH在其任何的解释下，其真值为“ 真”，即GH为永真公式。“”假定公式GH是永真公式，是它的任 意解释，在下，GH为真，因此，G、H或同 为真，或同为假，由于的任意性，故有GH 。电子科技大学离散数学课程组国家精品课程122-15例3.3.5 证明公式G1()与公式
8、G2 (PQ)(QP)之间是逻辑等价的。 解：根据定理3.3.1，只需判定公式G3( ) (PQ)(QP)为永真公式。P Q G3() (Q)(Q ) 0 0 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 1 1 1 1 1 1电子科技大学离散数学课程组国家精品课程122-16设G，H，S是任何的公式，则：基本等价公式1) 1：G(HS)(GH)S(结合律 )2: G(HS)(GH)S2) 3：GHHG (交换律 )4：GHHG3) 5：GGG (幂等律 )6：GGG3) 7：G(GH) G (吸收律 )8：G(GH) G电子科技大学离散数学课程组国家精品课程
9、122-179：G(HS)(GH)(GS)(分配律）10：G(HS)(GH)(GS)11：GG(同一律)12：GG 13：G(零律)14：G15：GG (排中律)16：GG (矛盾律)基本等价公式（续）电子科技大学离散数学课程组国家精品课程122-18基本等价公式（续）17：(G)G(双重否定律)18：(GH)GH(De MoRGan定律)19：(GH)GH20: (GH)(GH)(HG)(等 价式)21：(GH)(GH)(蕴涵式)E22：G G(假言易位 )E23：G G(等价否定等式)E24：(G ) (G)G(归谬论)电子科技大学离散数学课程组国家精品课程122-19设G(P1,P2,P
10、n)是一个命题公式，其中：P1、P2、Pn是命题变元，G1(P1,P2,Pn)、G2(P1,P2,Pn)、.、Gn(P1,P2,Pn)为任意的命题公式，分别用G1、G2、Gn取代G中的P1、P2、Pn后得到新的命题公式：G(G1,G2,Gn)G(P1,P2,Pn)若G是永真公式（或永假公式），则G也是一个永真公式（或永假公式）。定理3.3.2(代入定理)电子科技大学离散数学课程组国家精品课程122-20例3.3.6设(, )()，证明 公式G是一个永真公式。另有两个任意公式：(, )()；(, )()。进一步验证代入定理的正确性。 解 建立 公式G的真 值表如右 所示。可 见为永真 公式。P
11、Q() 0 01 0 11 1 01 1 11电子科技大学离散数学课程组国家精品课程122-21例3.3.6（续）将，代入到中分别取代G中的命题变元P、 Q，所得到的公式为：(P, Q) = G(H, S) = (H(HS)S = ()()()( ) 建立新公式(P, Q)的真值表，代入定理符合 。P Q()()()( ) 0 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 1 1 1 1电子科技大学离散数学课程组国家精品课程122-22定理3.3.3(替换定理)设G1是G的子公式(即
12、G1是公式G的一部分)，H1 是任意的命题公式，在G中凡出现G1处都以H1替 换后得到新的命题公式H，若G1H1，则GH。利用24个基本等价公式及代入定理和替换定理 ，可完成公式的转化和等价判定。电子科技大学离散数学课程组国家精品课程122-23例3.3.7利用基本的等价关系，完成如下工作：（1）判断公式的类型：证明 () ( )()()是一个永真公式 。（2）证明公式之间的等价关系：证明() = ()（3）化简公式：证明(P(R)(R)(PR) = R 电子科技大学离散数学课程组国家精品课程122-24证明（1）() () ()()= ()()()( )= ()() ()()()= ()()() ()()= ()()()()= T即:() ()() (
