Lecture

命题逻辑

学习逻辑的动机：获得模拟现实生活情景的能力，使我们能够正式地对其进行推理。

例1：如果火车晚点，而且车站没有出租车，那么约翰开会就迟到了。约翰开会没有迟到。火车确实晚点了。因此，车站有出租车。

例2：如果下雨，简没有带雨伞，她就会淋湿。简没有淋湿。下雨了。因此，简随身带着雨伞。

我们能正式验证这些论点的有效性吗？

• 我们需要把英语句子转换成公式（建模）。

• 然后，我们可以将数学推理应用到公式中

造型

编码：

模式： If p and not q, then r. Not r. p. Therefore q.

我们将研究推理模式。

陈述句

陈述句（我们可以考虑它们是否正确）：

• 数字3和5之和等于8。

• 简对杰克的指控反应激烈。

• 每个偶数自然数都是两个素数的和。

• 所有的火星人都喜欢在比萨饼上加佩佩罗尼。

非陈述句（不知道是否正确）：

• 请把盐递给我好吗。

• 准备好，稳定，开始。

• 祝你好运。

我们想把陈述句转换成公式，并创建一种形式主义来操作这些公式。

把英语短语变成公式

原子句：

p:我上周中了彩票。

q:我买了一张彩票。

r:我赢了上周的抽奖。

连接词：

:我没有中彩票。

:我上星期中了彩票，或者我赢了上星期的抽奖。

:我上星期中了彩票和抽奖。

:如果我上周中了彩票，那么我就买了一张彩票。

复合公式：;连接优先级，,根据此约定，我们可以删除括号：。

自然演绎

• 证明规则的集合，允许从现有公式推断新公式。

• 给出公式，我们打算推断出一个结论ψ。我们用

这种构造称为序列。

• 例子：

• 没有一套“完美”的证明规则。你可以创造你自己的（你甚至可以发明你自己的逻辑）。这种练习类似于计算机编程。

自然演绎规则-连词

例子：

证明

Solution

备选证明方式：

自然演绎规则-双重否定与蕴涵消除

论证

例子

Solution

Solution

自然演绎规则-含义介绍

为了证明Φ→ψ，我们做了Φ的临时假设，然后证明了ψ。假设的范围用方框表示。

备注：我们可以将的任何证明转换为的证明

例子

Solution

Solution

Solution

自然演绎规则-析取

例子

Solution

Solution

自然演绎规则-否定

矛盾：形式的公式-所有此类公式应以（底部）表示。

例子

Solution

Solution

自然演绎规则

理由：如果我是中国人，那么我就是亚洲人。我不是亚洲人。因此，我不是中国人。

自然演绎总结

基本规则：

有用的派生规则：

Assignment

演绎规则

用自然演绎法证明下列定理

(1) ¬(p∧q) ⊣⊢ ¬q ∨ ¬p

Solution

(2) p → q ⊣⊢ ¬q → ¬p

Solution

(3) p ∧ q → p ⊣⊢ r ∨ ¬r

Solution