数理逻辑 (2).ppt

《数理逻辑 (2).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学数学科学学院09九月2021任课教师:杨春3.3命题公式、解释与真值表定义（1）一个特定的命题是一个常值命题，其真值已经确定；(2)一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元)，该命题变量无具体的真值，它的变域是集合{T，F}(或{0，1})3.3.1命题公式定义3.3.2(命题公式)命题变元本身是一个公式；如G是公式，则(┐G)也是公式；如G，H是公式，则(G∧H)、(G∨H)、(G→H)、(GH)也是公式；命题公式是仅由有限步使用规则1-3后产生的结果。该公式常用符号G、H、…等表示。例3.3.1符

2、号串：((P∧(Q∨R))→(Q∧(┐S∨R)))；(┐P∧Q)；(P→(┐(P∧Q)))；(((P→Q)∧(R→Q))(P→R))。等都是命题公式。例3.3.2符号串：(P→Q)∧┐Q)；(P→Q；(┐P∨Q∨(R；P∨Q∨。等都不是合法的命题公式。例例3.3.3试用符号形式写出下列命题：虽然今天天气晴朗，老陈还是不来；除非你陪伴我或代我叫车子，否则我将不出去；停机的原因在于语法错误或者程序错误；若a和b是偶数，则a+b是偶数；我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。P：今天天气晴朗，Q：老陈不来,则有：P∧QP：你陪伴我；Q：你

3、代我叫车子；R：我出去。则有：R→P∨Q或P∧Q→RP：停机的原因在于语法错误，Q：停机的原因在于程序错误，则有：P∧QP：a是偶数，Q：b是偶数，R：a+b是偶数，则有：P∧Q→RP：我们要做到身体好Q：我们要做到学习好R：我们要做到工作好S：我们要为祖国四化建设而奋斗则有：P∧Q∧RS公式(P∧(Q∨R))→(Q∧(┐S∨R))可表示如下：(P∧(Q∨R))→(Q∧(┐S∨R))P∧(Q∨R)Q∧(┐S∨R)PQ∨RQ┐S∨RQR┐SRS例3.3.43.3.2公式的解释与真值表定义3.3.3设P1、P2、…、Pn是出现在公式G中的所有命题变元，指

4、定P1、P2、…、Pn一组真值，则这组真值称为G的一个解释,常记为Ｉ。一般来说，若有ｎ个命题变元，则应有2n个不同的解释。如果公式G在解释Ｉ下是真的，则称Ｉ满足G；如果G在解释Ｉ下是假的，则称Ｉ弄假G。定义3.3.4将公式G在其所有可能解释下的真值情况列成的表，称为G的真值表。例3.3.5求下面公式的真值表：Ｇ＝(P→((PQ)∧R))∨Q其中，Ｐ、Ｑ、Ｒ是Ｇ的所有命题变元。PQRPPQ((PQ)∧RP→((PQ)∧R)G00010011001100110101101101111111100010001010111111000001

5、11100001例3.3.5（续）PQR(P→((PQ)∧R))∨Q00010011010101111000101111011111进一步化简为：定义3.3.5公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。公式G称为可满足的，如果它不是永假的。例3.3.7写出下列公式的真值表，并验证其公式是重言式、矛盾式、可满足公式。（1）G1=(Ｐ→Ｑ)(Ｐ∨Ｑ)；（2）G2=(ＰQ)((Ｐ→Q)∨(Q→Ｐ))；（3）G3=(P→Q)∨Q。解：PQ(Ｐ→Ｑ)(

6、Ｐ∨Ｑ)(ＰQ)((Ｐ→Q)∨(Q→Ｐ))(P→Q)∨Q00101011011010111100永真公式可满足公式永假公式可满足公式三个公式的真值表如下：定义3.3.6设G、H是公式，如果在任意解释Ｉ下，G与H的真值相同，则称公式G、H是等价的，记作G＝H。基本等价公式定理3.3.1公式G、H等价的充分必要条件是公式GH是永真公式。说明：GH的结果仍是一个命题公式。G＝H表示“命题公式G等价于命题公式H。证明:“”假定G，H等价，则G，H在其任意解释Ｉ下或同为真或同为假，于是由“”的意义知，GH在其任何的解释Ｉ下，其真值为“真”

7、，即GH为永真公式。“”假定公式GH是永真公式，Ｉ是它的任意解释，在Ｉ下，GH为真，因此，G、H或同为真，或同为假，由于Ｉ的任意性，故有G＝H。例3.3.5证明公式G1＝(ＰＱ)与公式G2＝(P→Q)∧(Q→P)之间是逻辑等价的。解：根据定理3.3.1，只需判定公式G3＝(ＰＱ)((P→Q)∧(Q→P))为永真公式。PQG3＝(ＰＱ)((Ｐ→Q)∧(Q→Ｐ))0011111010110010010011111111设G，H，S是任何的公式，则：基本等价公式Ｅ1：G∨(H∨S)＝(G∨H)∨S(结合律)Ｅ2:G∧(H∧S)＝(G∧H)

8、∧SＥ3：G∨H＝H∨G(交换律)Ｅ4：G∧H＝H∧GＥ5：G∨G＝G(幂等律)Ｅ6：G∧G＝GＥ7：G∨(