数理逻辑入门：命题逻辑与原子命题解析

需积分: 33 136 浏览量更新于2024-08-02 收藏 969KB PDF 举报

"这篇资料主要介绍了数理逻辑中的命题逻辑，包括命题的定义、原子命题与复合命题的概念，以及命题公式的真值表、等值演算和不同类型的命题范式。" 在数理逻辑中，命题逻辑是基础研究领域之一，主要探讨命题的结构、性质及其相互关系。首先，我们要理解什么是命题。一个命题是能够被判断为真或假的陈述句，它必须是完整的，不能是疑问句、祈使句或感叹句。例如，“√3是有理数”、“8小于10”这样的陈述是命题，因为它们可以被证实为真或假。原子命题是最基本的命题，不包含其他命题作为组成部分，如“乌鸦是黑色的”。复合命题则由一个或多个原子命题通过联结词组合而成，如“如果乌鸦是黑色的，那么它不是白色的”，这样的命题的真假取决于其组成部分的真假。命题公式的构造通常涉及命题联结词，如“与”（AND）、“或”（OR）、“非”（NOT）、“蕴含”（IMPLICATION）和“等价”（EQUIVALENCE）。这些联结词用于构造更复杂的命题结构，并且可以通过等值演算来简化这些结构。等值演算是一组规则，如德摩根定律、分配律等，用于推导出两个命题公式在所有可能的真值分配下都具有相同真值的事实。等值演算帮助我们找到命题公式的等值形式，例如析取范式（Disjunctive Normal Form, DNF）和合取范式（Conjunctive Normal Form, CNF）。析取范式是所有可能的原子命题或其否定的析取（OR）组合，而合取范式则是所有可能原子命题或其否定的合取（AND）组合。这些范式在逻辑推理和证明中具有重要作用。在讨论命题逻辑时，我们还要注意命题的真值。每个命题都有真或假两种可能的真值，原子命题的真值是基于其自身的事实，而复合命题的真值由其支命题的真值决定。例如，蕴含命题“如果A，则B”只有在A为真且B为假时才为假，其他情况下都是真的。此外，经典命题逻辑不考虑命题的真假随时间变化的情况，这在时态逻辑中才会被处理。同样，它也不区分在理论上可以判断真假但实际上无法判断的情况，这是直觉逻辑关注的问题。数理逻辑中的命题逻辑是理解和处理逻辑关系的基础，它提供了分析和构建复杂论证的工具，是数学、计算机科学和哲学等领域的重要理论基础。通过学习和掌握这些概念，我们可以更好地理解和评估各种论证的有效性和正确性。

[10]. 排中律： (A∨(¬A)) ⇔ 1

[11]. 矛盾律： (A∧(¬A)) ⇔ 0

[12]. 蕴涵等值式： (A→B) ⇔ ((¬A)∨B)

[13]. 等价等值式： (A↔B) ⇔ ((A→B)∧(B→A))

[14]. 假言易位： (A→B) ⇔ ((¬B)→(¬A))

[15]. 等价否定等值式： (A↔B) ⇔ ((¬A)↔(¬B))

[16]. 归谬论： ((A→B)∧(A→(¬B))) ⇔ (¬A) □

【讨论 1.18】由于命题联结符号∧和∨都满足结合律，因此可有如下的简写：

∧A

∧…∧A

∨A

∨…∨A

根据以上简写，可推广定理 1.13

为以下定理 1.15：

【定理 1.15】

[1]. A

, A

, …, A

╞A 当且仅当╞((A

∧A

∧…∧A

)→A)。

[2]. A

, A

, …, A

╞A 当且仅当╞((A

→(A

→(…(A

→A)…))。 □

【引理 1.16】设有 A⇔A'和 B⇔B'，则有：

[1]. (¬A)⇔(¬A')

[2]. (A∧B)⇔(A'∧B')

[3]. (A∨B)⇔(A'∨B')

[4]. (A→B)⇔(A'→B')

[5]. (A↔B)⇔(A'↔B') □

根据引理 1.16，不难证明下面的等值置换规则：

【定理 1.17】设有 B⇔C，而 A'是命题公式 A 通过使用 C 替换 A 中出现的某些 B（不

需要替换所有的 B）而得到的命题公式，则有 A⇔A'。

【证明】对命题公式 A 的结构进行归纳。首先如果 B = A，则有 C = A'，从而有 A⇔A'。

归纳基：如果 A 是命题变量 p，则必有 B = p，因此定理成立。

归纳步：根据定理 1.6，命题公式 A 必为如下 5 种形式之一：¬A

, A

∧A

, A

∨A

, A

→A

, A

↔A

。设

A 的形式为¬A

，如果 B = A 则定理成立，否则必有 B 出现在 A

中，将 A

中的 B 用 C 替换后得到的为 A

'，

按归纳假设有 A

= A

'，再根据引理 1.16 有¬A

= ¬A

'。定理成立。若 A 的形式为 A

* A

，则如果 B = A

则定理成立，否则必有 B 出现在 A

或 A

中，或同时出现在这两者中。设将 A

中的 B 用 C 替换后得到的

为 A

'，而将 A

中的 B 用 C 替换后得到的为 A

'，按归纳假设有 A

⇔A

'和 A

⇔A

'，再根据引理 1.16 有

⇔A

，即定理成立。

□

【例子 1.5】验证下列等值式

(1). ((p→q)→r) ⇔ ((¬q∧p)∨r)

(2). (p→(q→r)) ⇔ ((p∧q)→r)

(3). ((p∨q)→r) ⇔ ((p→r)∧(q→r))

(4). ((p∧q)→r) ⇔ ((p→r)∨(q→r))

(5). (p→(q∨r)) ⇔ ((p→q)∨(p→r))

(6). (p→(q∧r)) ⇔ ((p→q)∧(p→r))

【证明】证明的思路有两种，第一种思路是通过列真值表，可看到上述等值式⇔的两边在任何真值

赋值下都有相同的真值，从而完成上述等值式的验证。读者不妨自己按照这种思路进行证明。第二种思路

是利用定理 1.14

中的基本等值式来证明。可以看到上述等值式主要是关于蕴涵的等值式，证明关于蕴涵的

等值式的方法是利用定理 1.14 中的[12]将蕴涵化成只出现与、或、非的公式，再来验证它们的相等。

(1). ((p→q)→r) ⇔ ((¬p∨q)→r) // 定理 1.14 中的[12]：蕴涵等值式

⇔ (¬(¬p∨q))∨r // 定理 1.14 中的[12]：蕴涵等值式

⇔ (p∧(¬q))∨r // 德摩尔根律

⇔ ((¬q∧p)∨r) // ∧的交换律

(2). (p→(q→r)) ⇔ (¬p∨(q→r)) // 蕴涵等值式

⇔ (¬p∨(¬q∨r)) // 蕴涵等值式

⇔ ((¬p∨¬q)∨r) // ∨的结合律

⇔ (¬(p∧q)∨r) // 德摩尔根律，反向运用

⇔ ((p∧q)→r) // 蕴涵等值式，反向运用

(3). ((p∨q)→r) ⇔ (¬(p∨q)∨r) // 蕴涵等值式

⇔ ((¬p∧¬q)∨r) // 德摩尔根律

⇔ ((¬p∨r)∧(¬q∨r)) // 分配律与交换律

⇔ ((p→r)∧(q→r)) // 蕴涵等值式

(5). (p→(q∨r)) ⇔ (¬p)∨(q∨r) // 蕴涵等值式

⇔ (¬p)∨(¬p)∨(q∨r) // ∨的幂等律

⇔ (¬p∨q)∨(¬p∨r) // ∨的交换律和结合律

⇔ (p→q)∨(p→r) // 蕴涵等值式

(4)(6)留作练习

□

【例子 1.6】德摩尔根律的推广：

(1). ¬(A

∨A

∨…∨A

) ⇔ (¬A

)∧(¬A

)∧…∧(¬A

)

(2). ¬(A

∧A

∧…∧A

) ⇔ (¬A

)∨(¬A

)∨…∨(¬A

)

【证明】对 n 实施数学归纳法。 □

5. 联结词的完全集

【定义 1.18】{0, 1}上的 n 元函数 f : {0, 1}

→{0, 1}就称为一个 n 元真值函数。

【讨论 1.19】真值联结词与真值函数：

1. ¬实际上一个一元真值函数：f¬(0) = 1, f¬(1) = 0。

2. 而真值联结词∧、∨、→和↔则都是二元真值函数：

f∧(0, 0) = 0, f∧(0, 1) = 0, f∧(1, 0) = 0, f∧(1, 1) = 1

f∨(0, 0) = 0, f∨(0, 1) = 1, f∨(1, 0) = 1, f∨(1, 1) = 1

f→(0, 0) = 1, f→(0, 1) = 1, f→(1, 0) = 0, f→(1, 1) = 1

f↔(0, 0) = 1, f↔(0, 1) = 0, f↔(1, 0) = 0, f↔(1, 1) = 1

3. 反过来，一个真值函数就可看成一个真值联结词。设 f : {0, 1}

→{0, 1}是一个 n 元真值函数，则

可定义一个 n 元真值联结词 N

为，对于 n 个命题变元 p

, p

, …, p

，命题公式 N

, p

, …, p

)在真值赋值

函数<t

, t

, …, t

>下的真值为 f(t

, t

, …, t

)。

4. 显然互不相同的 n 元真值函数的个数为

，因此可定义

个 n 元真值联结词，例如 1 元真值

函数有四个：f

: 0→0, 1→0、f

: 0→0, 1→1、f

: 0→1, 1→0 和 f

: 0→1, 1→1 而 2 元真值函数有 16 个，可定

义 16 个真值联结词，但常用的只不过是其中的 5 个。

5. 现在的问题是，是否所有的真值函数都可使用常用的 5 个真值联结词来表示呢？

【定义 1.19】设Ω是真值联结词的一个集合，称Ω为真值联结词的一个完全集，如果任

意真值函数 f 都可用仅含Ω中真值联结词的命题公式 A 表示，即对 A 中命题变元的任意一个

真值赋值<t

, t

, …, t

>，A 在<t

, t

, …, t

>下的真值为 f(t

, t

, …, t

)。

【定理 1.20】{¬, ∧, ∨, →}是联结词的一个完全集。

【证明】根据定义 1.18 和定义 1.19，只要证明对任意 n 元真值函数都可由只含¬、∧、

∨和→的 n 元命题公式来表示即可。对真值函数的元数 n 进行归纳证明。

归纳基：当 n = 1 时，一元真值函数只有 4 个，可分别用 p∧(¬p)、p、¬p 和 p∨(¬p)表示。

归纳步：假设当 n = k 时定理成立，要证 n = k + 1 定理也成立。设 f(x

, x

, …, x

, x

k+1

)是一个 k+1 元真

值函数，定义如下两个 k 元真值函数：

, x

, …, x

) = f(x

, x

, …, x

, 0) f

, x

, …, x

) = f(x

, x

, …, x

, 1)

由归纳假设知 f

和 f

都可由只含¬、∧、∨和→的 k 元命题公式来表示，设它们分别可由 A

和 A

表示，

且假定 A

和 A

中的 k 个命题变元为 p

, p

, …, p

。下面证 f 可由 A = ((¬p

k+1

)→A

)∧(p

k+1

→A

)表示，其中 p

k+1

是不同于p

, p

, …, p

的一个命题变元。即要证对命题变元p

, p

, …, p

, p

k+1

的一个真值赋值<t

, t

, …, t

, t

k+1

时，A 的真值是 f(t

, t

, …, t

, t

k+1

)。当 t

k+1

= 0 时，即 p

k+1

被赋值为 0，这时((¬p

k+1

)→A

)与 A

等值，而(p

k+1

→A

)

的真值为 1，所以 A 与 A

等值，而按归纳假设有 A

的真值为 f

, t

, …, t

)，即为 f(x

, x

, …, x

, 0)。同理

可证当 t

k+1

= 1 时 A 的真值是 f(x

, x

, …, x

, 1)，从而 A 的真值确实是 f(t

, t

, …, t

, t

k+1

)。

□

【推论 1.21】{¬, →}, {¬, ∧}和{¬, ∨}都是联结词的完全集。

【证明】

1. 要证{¬, →}是联结词的一个完全集，只要证任一命题公式可与一个只含¬和→的命题公式等值，事

实上有：(A∨B)⇔((¬A)→B)和 (A∧B)⇔(¬((¬A)∨(¬B)))。

2. {¬, ∧}是联结词的一个完全集，因为：(A∨B)⇔(¬((¬A)∧(¬B))) 和(A→B)⇔((¬A)∨B)

3. {¬, ∨}是联结词的一个完全集，因为：(A∧B)⇔(¬((¬A)∨(¬B))) 和(A→B)⇔((¬A)∨B)

事实上，上述每个集合都是极小完全集，即不能再从集合中去掉任意一个联结词还能保持是完全集。

□

剩余32页未读，继续阅读

heiyeah09

粉丝: 3
资源: 2

数理逻辑入门：命题逻辑与原子命题解析

math_exp_MATLAB智能算法代码.zip

PMS_Motor_level3eZDSPF2812.zip_BLDC_The New Math_bldc fuzzy cont

math_ptx:为各种 CUDA 数学函数自动生成 PTX 文件

citation.js-master_logic_capacitor_

ead.rar_logic

Programming_Logic:使用JavaScript和HTML进行编程逻辑练习

The Haskell Road to Logic, Math and Programming

Doets K.The Haskell road to logic,math and programming.2004.pdf

离散数学，逻辑和可计算性的Prolog实验Prolog Experiments in Discrete Math, Logic, and Computability

Propositional logic

最新资源