下载文档原格式
命题逻辑基本推理公式(1) P∧Q⇒P .(2)¬( P→Q)⇒P .(3)¬(P→Q)⇒¬Q.(4) P⇒P ∨Q.(5)¬P⇒P →Q.(6) Q⇒P →Q.(7) ¬P∧(P∨Q) ⇒Q.选言推理否定式(8) P∧(P→Q) ⇒Q. 假言推理肯定前件式(9) ¬Q∧(P→Q) ⇒¬P .假言推理否定后件式(10) (P→Q)∧(Q→R) ⇒P→R. 三段论(11) (P↔ Q)∧(Q↔R) ⇒P↔R. 双条件三段论(12) (P→R)∧(Q→R)∧( P ∨Q) ⇒R. 二难推理(13) (P→Q)∧(R→S) ∧(P ∨R)⇒Q∨S. 二难推理(14) (P→Q)∧(R→S) ∧¬(Q∨¬S)⇒¬P ∨¬R. 破坏二难推理(15) (Q→R) ⇒(( P∨Q)→(P ∨R)) .(16) (Q→R) ⇒(( P→Q)→(P→R)) .使用真值表法证明这些推理公式是容易的。
若从语义上给予直观说明也是不难的. 如公式(2), ¬(P →Q) ⇒P . 公式( 3), ¬(P →Q)⇒Q. 意思是说, 若P →Q 不成立( 取假), 必有 P 为真, 还有 Q 为假. 这从P →Q 的定义可知, 因只有当 P = T 而 Q = F 时, P →Q = F. 又如公式( 7), ¬P ∧(P ∨Q)⇒Q. 意思是说, P 不对, 而P ∨Q 又对, 必然有 Q 对.公式( 8) , P ∧(P →Q) ⇒Q 常称作假言推理, 或称作分离规则, 是最常使用的推理公式。
公式(10) , (P →Q) ∧(Q→R)⇒P →R 常称作三段论。
日常语言运用：(1) 此人既呆又笨为真，则此人笨为真。
(2)(3)并非“犯错蕴涵失败“，即是说，”如果犯错，那么失败“为假命题,则必有犯错且不失败的例子。
第三章命题逻辑重点：掌握数理逻辑中命题的翻译及命题公式的定义；利用真值表技术和公式转换方式求公式的主析取范式和主合取范式；利用规则、基本等价和蕴涵公式、三种不同的推理方法完成命题逻辑推理；难点：如何正确地掌握对语言的翻译，如何利用推理方法正确的完成命题推理。
数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其他分支、计算机学科、人工智能、语言学等学科均有十分密切的联系，并且益显示出它的重要作用和更加广泛的应用前景。
要很好地使用计算机，就必须学习逻辑。
数理逻辑分五大部分。
在离散数学中仅介绍命题逻辑和谓词逻辑。
命题逻辑是谓词逻辑的基础，只有掌握了命题逻辑，才能学好谓词逻辑。
对于命题逻辑，下面从六个知识点来加以阐述。
3.1 命题符号化及联系结词1 命题有确切真值的陈述句称为命题。
所谓确切真值是指在具体的环境，具体的时间，具体的对象，具体的位置等情况下能唯一确定真值的。
命题分为两种：(1) 简单命题：不能分解为更为简单的句子的命题。
(2)复合命题：能够分解为更为简单的命题。
2 命题联结词关于联结词，有如下几点要注意：（1）此联结词是联结的句子与句子之间的联结，而非单纯的名记号、形容词、数词等的联结；（2）此联结词是两个句子真值之间的联结词，而非句子的具体含义的联结，两句子之间可以无任何的内在联系；（3）联结词与自然语言之间的对应并非一一对应，如合取联结词“∧”对应了自然语言中的“既……又……”、“不仅……而且……”、“虽然……但是……”、“并且”、“和”、“与”等。
如蕴涵联结词“→”，P →Q 对应了自然语言中的“加P 则Q ”，“只要P 就Q ”，“P 仅当Q ”，“只有Q 才P ”，“除非Q 否则乛P ”等。
如等价联结词“←→ ”对应了自然语言中的“等价”、“并且仅当”、“充分必 ”等。
如析取联结词∨是对应相容的或(中兼的或)。
3.2 命题公式及分类一般称具有确切真值的简单命题叫命题常量，用P ，Q ，R ，…等表示。
离散数学结构第1章命题逻辑基本概念第1章命题逻辑基本概念主要内容1. 命题与真值（或真假值）。
2. 简单命题与复合命题。
3. 联结词：否定联结词┐，合取联结词∧，析取联结词∨，蕴涵联结词→，等价联结词。
4. 命题公式（简称公式）。
5. 命题公式的层次和公式的赋值。
6. 真值表。
7. 公式的类型（重⾔式（或永真式），⽭盾式（或永假式），可满⾜式）。
学习要求1. 在5种联结词中，要特别注意蕴涵联结的应⽤，要弄清三个问题：① p→q的逻辑关系② p→q的真值③ p→q的灵活的叙述⽅法2. 写真值表要特别仔细认真，否则会出错误。
3. 深刻理解各联结词的逻辑含义。
4. 熟练地将复合命题符号化。
6. 会⽤真值表求公式的成真赋值和成假赋值。
1.1 命题与联结词 (2)⼀、命题的概念 (2)⼆、复合命题与联结词 (2)三、复合命题真假值 (5)1.2 命题公式及其赋值 (6)⼀、命题公式的定义 (6)⼆、公式的层次 (6)三、公式的赋值 (6)四、真值表 (7)五、公式的真假值分类 (8)1.1 命题与联结词⼀、命题的概念引⾔中的例⼦就是要对“我戴的是⿊帽⼦”进⾏判断。
这样的陈述句称为命题。
作为命题的陈述句所表达的判断结果称为命题的真值，真值只取两个值：真或假。
真值为真的命题称为真命题，真值为假的命题称为假命题。
真命题表达的判断正确，假命题表达的判断错误。
任何命题的真值都是唯⼀的。
判断给定句⼦是否为命题，应该分两步：⾸先判定它是否为陈述句，其次判断它是否有唯⼀的真值。
例1.1 判断下列句⼦是否为命题。
(1) 4是素数。
(2) 是⽆理数。
(3) x⼤于y。
(4) ⽉球上有冰。
(5) 2100年元旦是晴天。
(6) π⼤于吗？(7) 请不要吸烟！(8) 这朵花真美丽啊！(9) 我正在说假话。
解:本题的(9)个句⼦中，(6)是疑问句，(7)是祈使句，(8)是感叹句，因⽽这3个句⼦都不是命题。
剩下的6个句⼦都是陈述句，但(3)⽆确定的真值，根据x,y的不同取值情况它可真可假，即⽆唯⼀的真值，因⽽不是命题。
第1章命题逻辑1．1命题与连接词1．1．1命题的概念1．命题：具有真假意义的陈述句。
（只有能够确定或能够分辨其真假的陈述句）。
2．真值：命题总是具有一个“值”。
3．命题：原子命题：一种是不能够分解为更简单的陈述句的命题。
复合命题：是由原子命题和连接词复合而成的命题。
例：判断下列句子哪些是命题。
（1）地球外的星球上边也有生物。
（2）101+010=111。
（3）邓书记的头发有一万根。
（4）我正在说假话。
（5）离散数学真有趣啊！（6）雪是黑色的。
解：（1）、（3）、（6）是命题。
（2）、（4）、（5）不是命题。
（3）虽然不能马上知道其语句的真假，但只要仔细数一数，还是可以确定真假的。
（1）目前虽然无法确定真假，但从事物的本质而论，该语句具有真假意义。
（2）因为需要根据上下文确定其真假，该命题在十进制中为假，但在二进制中为真。
（4）这个句子是逻辑学中的悖论，因而不是命题。
当它为假时，它变为真；当它为真时，它变为假。
（5）是感叹句，不是命题。
4．命题常项（命题常元）：一个命题标识符（如果表示确定真值的命题）（如上面的p、q）5．命题变项（命题变元）：对于一个没有赋予任何意义的命题，因命题变项的真值不确定，故命题变项不是命题。
6．条件连接词（蕴涵连接词）：设p和q是两个命题，由连接词“→”将p、q 连接成复合命题，记做p→q，读作“如果p，那么q”或“若p则q”或“p蕴涵q”。
在p→q中，p为前件，q为后件。
也就是说p是q的充分条件，或者q 是p的必要条件。
当且仅当p的真值为1，q的真值为0时，p→q的真值为0，否则p→q的真值为1。
例：设p表示“猫是哺乳动物”；q表示“猫必胎生”。
复合命题“如果猫是哺乳动物，则猫必胎生”可以表示为p→q，由于p、q均为真，所以p→q的真值为1。
注：在自然语言中，“如果…，则…。
”常常表示一种因果关系，否则无意义。
但对于数理逻辑中的条件命题p→q来说，只要p、q能够分别确定真值，p→q即成为命题。
7.双条件连接词（等价连接词）：设p和q是两个命题，由连接词“↔”将p、q 连接成复合命题，记做“p↔q”，读作“p当且仅当q”或“p等价于q”。
例：2+2=4当且仅当太阳系由八大行星构成的天体系统。
解：设p表示“2+2=4”；q表示“太阳系由八大行星构成的天体系统”。
该命题可表示为“p↔q”。
总结：1.∧、∨、∧∨⌝具有可交换性，而⌝、→不具有交换性。
2.五个基本连接词的优先次序，优先级由高到低的次序为⌝、∧、∨、→、↔。
1.1.2逻辑连接词1.否定连接词：设p是一个命题，p的否定是一个新的命题，记做“⌝p”。
读作“非p”。
连接词“⌝”表示命题的否定。
（连接词“⌝”是一元运算符）。
例：设p表示“离散数学是计算机专业的一门主干课程”。
则⌝p表示“离散数学不是计算机专业的一门主干课程”。
2.合取连接词：设p和q是两个命题，由连接词“∧”将p、q连成复合命题，记做“p∧q”，读作“p合取q”或“p与q”。
（连接词“∧”是二元运算符。
）例：设p表示“小周是一名学习成绩优异的学生”。
q表示“小周是一名爱好运动的学生”。
p∧q表示“小周是一名学习成绩优异而且爱好运动的学生”。
此命题只有p和q同时为真，p∧q才为真。
3.析取连接词：设p和q是两个命题，由连接词“∨”将p、q连接成复合命题，记做“p∨q”，读作“p或q”或“p析取q”。
（连接词“∨”是二元运算符。
）例：a.菲尔普斯是100米或200米自由泳冠军。
b.今天晚上我再家上网或出门看电影。
解：a中的“或”是一个“可兼或”或“相溶或”。
复合命题可用析取连接词“∨”表示。
P表示“菲尔普斯是100米自由泳冠军”。
q表示“菲尔普斯是200米自由泳冠军”。
复合命题表示为p∨q。
b中的“或”是一个“排斥或”。
P表示“今天晚上我在家上网”。
q表示“今天晚上我出门看电影”。
因为p和q的真值不能同时为真，所以复合命题不能表示为p∨q。
“排斥或”也是一种连接词，其连接词“∨”的真值表如表所示。
复合命题b1.2命题公式及命题公式的翻译1.2.1命题公式1.命题公式是由下列规则形成的字符串：a.命题变元或常元本身是一个命题公式。
b.是命题公式，则（A）也是命题公式。
c.是命题公式，则（A∧B），（A∨B），（A→B）和（A↔B）都是命题公式。
d.过有限次地使用a、b、c所得到的结果，都是命题公式。
以上定义中，a为基础，b、c称为归纳，d成为界限或结论。
以下两点需要注意：（1）命题公式是没有真值的，只有对其变元进行真值指派后，才具有真值。
（2）命题公式无限多。
例：p→（q∧r），（q∨r）∧（q∨w）是命题公式，但pq→r，（p→q）→（∧q）不是命题公式。
1.2.2命题的翻译（命题的符号化）1.命题的翻译（符号化）：把一个文字叙述的命题相应地写成由命题标识符、连接词和圆括号表示的命题公式。
2.符号化的步骤：a.确定给定的句子是否为命题。
若是，分解出原子命题，分别用不同的符号表示不同的原子命题。
b.判断句子的连接词是否为命题连接词。
若是，分解出连接词，将其用相应逻辑连接词符号表示。
c.将表示各原子命题的符号，连接词符号及圆括号组成符号串，正确的表示命题。
例1：a.他既聪明又勤奋。
b.他虽聪明但不勤奋。
解：若设p表示“他聪明”；q表示“他勤奋”。
a中的连接词“既…又…”，可用合取连接词“∧”，符号化为p∧q。
b中的连接词“虽…但…”，其实际意义可表示为“他聪明而且不勤奋”，符号化为“p∧⌝q”。
例2：a.除非你努力学习，否则你将失败。
b.除非天气好，我才骑自行车上班。
c.小周晚上要回学校，除非下大雨。
解：a中设p表示“你努力”，q表示“你失败”。
该句的含义为“如果你不努力，则你将要失败”。
符号化为“⌝p→q”。
b中设p表示为“天气好”，q表示“我骑自行车上班”。
该句的含义为“如果我骑自行车上班，则天气好”。
符号化为q→p。
c中设p为“如果不下大雨，则小周晚上要回学校”。
符号化为“⌝p→q”。
例3：只有经常锻炼身体才能有强健的体魄。
解：设p表示“经常锻炼身体”；q表示“有强健的体魄”。
该句符号化为“q→p”。
一般地，“只有A，才B”句型才翻译为“⌝A→⌝B”或“B→A”。
例4：周五的离散数学课是10点或10点半上课。
解：该例中的“或”是“排斥或”。
可用连接词表示。
设p表示“周五的离散数学课时10点上课”；q表示“周五的离散数学课时10点半上课”。
符号化为p∨q或（p∧⌝q）∨（⌝p∧q）。
例5：三角形是正三角形当且仅当它的每个角为060。
解：该例题中的“…当且仅当…”可用“↔”连接词表示。
设p表示“三角形是正三角形”；q表示“三角形的每个角为060。
符号化为p↔q。
1.2.3命题公式的解释（命题公式的赋值）1.命题公式的解释：给命题公式A中的每个命题变项拟定一组真值。
2.成真赋值：拟定的一组赋值使命题公式A的真值为真。
3.成假赋值：拟定的一组赋值使命题公式A的真值为假。
例：设公式A为（⌝p∨q）→r。
若将p、q、r分别用（0、0、0）替换，得到公式A一种赋值。
这种赋值下，A的真值为假。
同理还可用（0、0、1），（0、1、0），（0、1、1），（1、0、0），（1、0、1），（1、1、0），（1、1、1）这7种指派。
由此可知：若公式A中有n个不同的命题变元，则公式A具有2n种不同的真值指派。
4.真值表：在命题公式A中，对其中出现的命题变元做所有可能的真值指派和由它们所确定的命题公式A的取真值情况所列的一个表。
5.列真值表的具体步骤：a.命题变元按英文字母字典顺序进行排列；带下标的命题变元，则由小到大按下标由小到大的顺序排列。
b.对公式的每种赋值，以二进制从小到大的顺序列出。
c.若公式较为复杂，遵循由简到复杂，由括号里到外的原则。
注意：含有2个命题变元的公式具有4种不同的真值指派，在每种指派下，公式的真值只能取真、假两种情况。
因此，2个命题变元不构成42个不等价的命题公式。
1.3等价公式（等值演算）与公式分类1.3.1等价公式的定义和性质1.等价公式（逻辑等值公式）：设A和B是两个公式，设P，2P，…，n P为所有1出现于A和B中的命题变元。
若组P，2P，…，n P拟定任意一组赋值，A、B1的真值都相同，记做“A⇔B”。
2.性质：a.自反性：对任意公式，都有A⇔A。
b.对称型：对任意公式A和B，若A⇔B，则B⇔A。
c.传递性：对任意公式A、B和C，若A⇔B且B⇔C，则A⇔C。
1.3.3置换规则1.子公式：若x是公式A的一部分，且x本身也是一个公式，则称x为公式A 的子公式。
例：若公式A为q→（p∨r），则q、p、r、pr的为公式A的子公式。
而q→，p∨，∨r均不为公式A的子公式。
2.置换规则：设x是合式公式（命题公式）A的子公式。
若x⇔y，如果将A中的x用y来置换，所得到的公式与原公式A等价，即A⇔B。
证明：因为x⇔y，所以在相同变元的任一种指派下x与y真值相同。
以y 取代x后，公式B与公式A在相应的指派情况下，其真值必相同，故A⇔B。
1.3.4命题公式的分类1.公式的分类：设A是一个公式，对A做所有可能解释I。
对于这些解释I：a.若所有的I（A）皆为真，则A为永真式（或重言式）。
b.若所有的I（A）皆为假，则A为永假式（或矛盾式）。
c.若至少存在一个I（A）为真，则A为可满足式。
2.利用等价推导可判断公式A的类型，现如下：a.若A⇔T，则A是永真式。
b.若A⇔F，则A是永假式。
c.若A⇔B，B是可满足式，则A是可满足式。
3.利用真值表也可判断公式A的类型:a.若公式A真值表中最后一列都是1，则A是永真式。
b.若公式A真值表中最后一列都是0，则A是永假式。
c.若公式A真值表中最后一列至少有一个1，则A是可满足式。
例：判断下列公式的类型：a.（p∧(p→q)）→qb.（p∨⌝p）→（（q∧⌝q）∧r）c.（p∨q）∧（p→q）解：a.（p∧（p→q））→q⇔（p∧ (⌝p∨q)) →q⇔（⌝p∧（p∨⌝q））∨q⇔（p∨（p∧q））∨q⇔（（⌝p∨p）∧（⌝p∨⌝q））∨q⇔（T∧（⌝p∨⌝q））∨q⇔p∨⌝q∨q⇔T（p∧（p→q））→q是永真式。
b．（p∨⌝p）→（（q∧⌝q）∧r）. ⇔T→((q∧⌝q)∧r)⇔T→（F∧r）⇔T→F⇔F（p∨⌝p）→（（q∧⌝q）∧r）是永假式。
c. （p∨q）∧（p→q）⇔（p∨q）∧（⌝p∨q）⇔（p∧⌝q）∨q⇔F∨q⇔q因为q是可满足式，因此（p∨q）∧（p→q）是可满足式。
由上可知：任何两个永真式的合取或析取，仍是一个永真式。
4.代入规则：一个永真式A，在任何一个原子命题变元R出现的每一处，用另一个公式代入，所得公式B仍为永真式。
证明：公式A是永真式，不论R做任何真值指派，A的真值永远是T。
