离散数学：命题逻辑推理理论

推理：若H1∧H2∧…∧Hn→C为永真式，则称H1，H2，…，Hn推结论C的推理正确，C是H1，H2，…，Hn的有效结论，记为H1，H2，…，Hn├C或H1，H2，…，Hn⇒C.

推理规则：

（1）P规则：在推导过程中，在任何地方都可引用前提.

（2）T规则：在推导过程中，前面导出的有效结论都可作为后续推导的前提.

（3）CP规则：要证H1，…，Hn├H→C，只需证明H1，H2，…，Hn，H├C.

（4）代入规则：在推理过程中，对重言式中的命题变元可使用代入规则.

（5）置换规则：在推理过程中，命题公式中的任何子公式都可以用与之等价的命题公式来置换.

（6）分离规则：如果已知命题公式A→B和A，则有命题公式B.

推理定理：

（1）化简律：P∧Q├P

（2）附加律：P├P∨Q

（3）析取三段论：¬P，P∨Q├Q

（4）假言推理（肯定律）：P，P→Q├Q

（5）拒取式（否定律）：¬Q，P→Q├¬P

（6）假言三段论：P→Q，Q→R├P→R

（7）合取引入：P，Q├P∧Q

使用推理规则进行推理演算：直接证明法，间接证明法，反证法.

重点

1.命题和联结词，5个联结词的真值表，命题符号化.

2.命题公式的类型，永真式.

3.两个命题公式等价的定义，基本等价式，用真值表法和等价式演算的方法证明两个公式等价.

4.蕴涵式的定义，基本蕴涵式，蕴涵式的证明方法：真值表法、前件真推出后件也真法、后件假推出前件也假法、利用等价和蕴涵的传递性证明一个公式蕴涵另一个公式.

5.析（合）取范式和主析（合）取范式的定义，用真值表法和等价式演算的方法求主析（合）取范式；主范式的3种应用.

6.命题逻辑推理的定义，常用推理规则和推理定理，构造推理的证明方法：真值表法、直接证明法、间接证明法、反证法.

难点

1.正确进行命题符号化，其关键在于对自然语言中语句之间的逻辑关系以及命题联结词的含义要有正确的理解，使用适当的联结词.尤其是条件式和日常生活用语中的条件联结词的区别和共同点.

2.判断命题公式的类型，判断等价式、蕴涵式是否成立.

3.求命题公式的主析（合）取范式.

4.构造推理过程.

例题解析

例1.1　试将下列命题符号化：

（1）张三与王五是兄弟.

（2）李四既聪明又用功.

（3）除非你努力，否则你将失败.

（4）除非天气好，我才骑自行车上班.

（5）小王晚上要回家，除非天下大雨.

（6）只有睡觉才能消除疲劳.

【分析】对一个命题进行符号化，其关键在于对自然语言中语句之间的逻辑关系以及命题联结词的含义要有正确的理解，确定原子命题并使用适当的联结词.如（1）是一个原子命题，因为兄弟表示的是两个人之间的一种关系.而（2）中表示了李四是聪明的和李四是用功的两个含义，所以是两个原子命题的并列.在符号化命题（3）（4）（5）时大家都知道要引入条件联结词，但很容易搞错哪个原子命题是条件式的前件，哪个是后件.应该认真细致地分析每个命题的确切含义.如命题（3）的本义是你不努力则必将失败（但即使你努力了也不保证你一定成功）.命题（4）的本义是我骑自行车上班一定是天气好的时候（天气不好则一定不骑自行车，天气好的话则可能骑也可能不骑）.命题（5）的本义是天不下大雨，小王晚上一定要回家（而天下大雨的话则不一定了）.命题（6）的本义是睡觉是消除疲劳的唯一途径，如果已经消除疲劳，则一定是睡觉了（但睡觉不一定能消除疲劳）.这时，哪个原子命题应该是前件就很清楚了.

解：

（1）设P：张三与王五是兄弟.则原命题符号化为：P.

（2）设P：李四聪明.Q：李四用功.则原命题符号化为：P∧Q.

（3）设P：你努力.Q：你将失败.则原命题符号化为：¬P→Q.

（4）设P：天气好.Q：我骑自行车上班.则原命题符号化为：¬P→¬Q或Q→P.

（5）设P：小王晚上要回家.Q：天下大雨.则原命题符号化为：¬Q→P或¬P→Q.

（6）设P：你睡觉.Q：你消除疲劳.则原命题符号化为：Q→P或¬P→¬Q.

例1.2　判断下列公式的类型：¬（Q→P）∧P.

【分析】判断一个公式的类型可用三种方法：真值表法、等价式演算的方法和主范式法.

真值表法：若真值表的最后一列都是T（F），则该公式是永真（假）式.若真值表的最后一列既有T又有F，则该公式是非永真的可满足式.

公式等价推演法：若该公式等价于T（F），则该公式是永真（假）式.若该公式等价于一个可满足式，则该公式是非永真的可满足式.

主范式法：设该公式有n个命题变元，则若该公式的主析（合）取范式中包含了所有的2n小（大）项，则该公式是永真（假）式.

解：

真值表法：

由于真值表的最后一列都是F，因此该公式是永假式.

等价式演算的方法：¬（Q→P）∧P⇔¬（¬Q∨P）∧P

⇔¬（¬Q）∧¬P∧P⇔Q∧（¬P∧P）⇔Q∧F⇔F，因此该公式是永假式.

主范式法：¬（Q→P）∧P⇔¬（¬Q∨P）∧P

⇔（¬P∧Q）∧P⇔（¬P∨（¬Q∧Q））∧（（¬P∧P）∨¬Q）∧（P∨（¬Q∧Q））

⇔（¬P∨¬Q）∧（¬P∨Q）∧（¬P∨¬Q）∧（P∨¬Q）∧（P∨¬Q）∧（P∨Q）(www.xing528.com)

⇔（¬P∨¬Q）∧（¬P∨Q）∧（P∨¬Q）∧（P∨Q），

它包含了所有的4个二元大项，因此该公式是永假式.

例1.3　求下列公式的主析取范式和主合取范式：（P∧Q）∨R.

【分析】求一个公式的主范式时，可先判断它便于求主析取范式还是主合取范式，然后再用主析取范式和主合取范式的关系求出另一种主范式.

如本命题公式当R为T时，其对应真值指派都是成真指派，因此先列出它对应的真值表，然后相应地得到主析取范式和主合取范式.

另外由于该公式本身已是一个析取范式，因此先用等价式演算的方法求出它的主析取范式更便捷，然后再求出它的主合取范式.

解：

（P∧Q）∨R的真值表如下表所示：

从真值表可知，该公式有成真指派FFT，FTT，TFT，TTF，TTT.所以，（P∧Q）∨R⇔m1∨m3∨m5∨m6∨m7⇔（¬P∧¬Q∧R）∨（¬P∧Q∧R）∨（P∧¬Q∧R）∨（P∧Q∧¬R）∨

（P∧Q∧R）（主析取范式）.

该公式有成假指派TFF，FTF，FFF.所以，（P∧Q）∨R⇔M3∧M5∧M7⇔（¬P∨Q∨R）∧（P∨¬Q∨R）∧（P∨Q∨R）（主合取范式）.

（P∧Q）∨R⇔（P∧Q∧（¬R∨R））∨（（¬P∨P）∧（¬Q∨Q）∧R）

⇔（P∧Q∧¬R）∨（P∧Q∧R）∨（¬P∧¬Q∧R）∨（¬P∧Q∧R）∨（P∧¬Q∧R）∨（P∧Q∧R）

⇔（¬P∧¬Q∧R）∨（¬P∧Q∧R）∨（P∧¬Q∧R）∨（P∧Q∧¬R）∨（P∧Q∧R）（主析取范式）.

公式否定的主析取范式是¬（P∧Q）∨R⇔（¬P∧¬Q∧¬R）∨（¬P∧Q∧¬R）∨（P∧¬Q∧¬R）.从而公式的主合取范式是（P∧Q）∨R⇔¬（（¬P∧¬Q∧¬R）∨（¬P∧Q∧¬R）∨（P∧¬Q∧¬R））⇔（¬P∨Q∨R）∧（P∨¬Q∨R）∧（P∨Q∨R）.

例1.4　甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛.关于谁参加竞赛，下列4种判断都是正确的：（1）甲和乙只有一人参加；（2）丙参加，丁必参加；（3）乙或丁至多参加一人；（4）若丁不参加，甲也不会参加.请推出哪两个人参加了围棋比赛.

【分析】对于这种类型的题目，先要进行命题符号化，然后把所有前提条件组成一个合取范式，将其化为主析取范式.删去不合题意的小项，剩下的小项就是一个符合要求的结果.

解：

设A：甲参加了比赛；B：乙参加了比赛；C：丙参加了比赛；D：丁参加了比赛.依题意有，则条件（1）符号化为（¬A∧B）∨（A∧¬B）；（2）符号化为C→D；（3）符号化为¬（B∧D）；（4）符号化为¬D→¬A.

所以由本题的4个判断可形成一个合取范式：

（（¬A∧B）∨（A∧¬B））∧（C→D）∧¬（B∧D）∧（¬D→¬A）

由于（（¬A∧B）∨（A∧¬B））∧（C→D）∧¬（B∧D）∧（¬D→¬A）

⇔（（¬A∧B）∨（A∧¬B））∧（¬C∨D）∧（¬B∨¬D）∧（D∨¬A）

⇔（（¬A∧B∧¬C）∨（A∧¬B∧¬C）∨（¬A∧B∧D）∨（A∧¬B∧D））∧（（¬B∧D）∨（¬B∧¬A）∨（¬D∧¬A））

⇔（A∧¬B∧¬C∧D）∨（A∧¬B∧D）∨（¬A∧B∧¬C∧¬D）

⇔T

但依据题意条件，有且仅有两人参加竞赛，故¬A∧B∧¬C∧¬D为F.所以只有（A∧¬B∧¬C∧D）∨（A∧¬B∧D）⇔T，即甲、丁参加了围棋比赛.

例1.5　证明：（U∨V）→（M∧N），U∨P，P→（Q∨S），¬Q∧¬S├M.

【分析】对于这种类型的题目，可能可以采用多种方法证明.首先要确定是用直接证明法还是间接证明法或是反证法.如果结论是一个条件式，则可采用CP规则.如果结论是一个析取式或一个更复杂的公式，则采用反证法更好.然后从结论开始分析，先看看结论与哪个前提有关，为了和该前提一起得出结论，需要用到什么推理定理，还要准备什么中间结论.然后为了得出该中间结论，它又与哪个前提有关，需要用到什么推理定理，还要准备什么中间结论……这样一直分析下去，直到恰好使用完所有的前提.

在本题中，可采用直接证明法，则结论M与第一个前提（U∨V）→（M∧N）中的后件M∧N有关.为了得到中间结论M∧N，需要利用假言推理和中间结论U∨V.中间结论U∨V中的V没有在任何其他前提中出现，故只能依靠U并利用附加律推出U∨V.与U相关的前提U∨P又与P有关，从而需要利用析取三段论及中间结论¬P得到所需的结论U.为了得到结论¬P，需要中间结论¬（Q∨S）和拒取式.而¬（Q∨S）与最后一个前提¬Q∧¬S等价.至此按相反的顺序就可以构造出有效的推理过程.

如果采用反证法，则除了原有的前提外，还多了个附加前提¬M.我们只要利用这些前提推出两个结论A与¬A，就可推出矛盾.其分析过程类似于直接证明法.

证明：

直接证明法

（1）¬Q∧¬S　前提引入

（2）¬（Q∨S）　置换，（1）

（3）P→（Q∨S）　前提引入

（4）¬P　拒取式，（2），（3）

（5）U∨P　前提引入

（6）U　析取三段论，（4），（5）

（7）U∨V　附加，（6）

（8）（U∨V）→（M∧N）　前提引入

（9）M∧N　假言推理，（7），（8）

（10）M　化简，（9）

反证法

（1）¬M　附加前提引入

（2）¬M∨¬N　附加，（1）

（3）（U∨V）→（M∧N）　前提引入

（4）¬（U∨V）　拒取式，（2），（3）

（5）¬U∧¬V　等价替换，（4）

（6）¬U　化简，（5）

（7）U∨P　前提引入

（8）P　析取三段论，（6），（7）

（9）P→（Q∨S）　前提引入

（10）Q∨S　假言推理，（8），（9）

（11）¬Q∧¬S　前提引入

（12）（¬Q∧¬S）∧（Q∨S）　合取引入，（10），（11）

（13）M