搜索
写经验 领红包

一阶逻辑是什么(一阶逻辑的基本概念)

导语:一阶逻辑简介

话题:

小石头/编

(由于,在科普数学过程中,会经常用到 一阶谓词逻辑语言,所以 写一篇文章,对其进行简单的介绍。这里的目标是,数学中够用,所有并不会涉及《模型论》和《证明论》部分。)

我们在日常生活中经常需要做判断,例如:

老张是狐狸公司的CEO。⑴

称这些判断句为命题。

命题常常会被验证,逻辑学要求,验证有明确的结果,即:

要么命题是真实的,要么命题是虚假的;☆

命题的验证结果 被称为 命题的 逻辑值,显然,真(记为 T) 和 假(记为 F)是唯二的逻辑值。值为真的命题 称为 真命题,值为假的命题 称为 假命题。

注:☆ 含有两层意思,

排中律:命题值 只能 是 T 或 F;

矛盾律:命题值 不能 同时是 T 或 F;

有一些命题会包含其它命题,例如:

命题,

老张有钱并且会物理。⑵

就包括两个命题,

老张有钱;⑶老张会物理。⑷

我们称这类命题为 复合命题,而不是复合命题的命题则被称为 原子命题,如前面上面的 ⑴,⑶ 和 ⑷ 都是原子命题。

复合命题都是通过 联词 将其所包含的命题关联起来而构成的,例如,⑵ 是通过 “...并且...” 连接⑶和⑷而而成。自然语言中,有多个联词表示同一个关联关系,例如,⑵ 还可以写成:

老张既有钱又会物理。⑵‘

联词 ”既 ...又...“ 和 “...并且...” 都是并列关系,功能相同。为了表述的一致,我们用 逻辑符号 ∧ (称为和取) 来表示 “...与...”、 ”既 ...又...“ 、“...并且...” 等。若再令 ,

A = ⑶ , B = ⑷

则 复合命题 ⑵ 和 ⑵‘ 可统一写成:

A ∧ B

这样我们就得到了逻辑语言的一个公式。除了析取外,日常交流中常用的联词还有很多,我们也对它们接引入逻辑符号来表示:

析取 ∨,表示 “或”、”或者“、”要么...,要么..“ 等;否定 ¬,表示 “非” 、&39;

则显然有,

P(老张) = A,P(老马) = B

称 这样的 P(x) 为谓词。谓词 也可以是多元的,例如,对 ⑴ 引入参数,得到谓词:

Q(x, y) = x是y的CEO

就是一个二元 谓词。从元数来看,位引入参数化的原子命题,例如上面的 A、B,可以认为是 零元谓词。

注:一元谓词P(x) 参数两边的 括号 可以省略不写,记为 Px。

量词也在日常交流中常常被用到,例如:

所有人都会回死;⑸总有人是天才; ⑹

我们 用 ∀(称为 全称量词) 表示 ”所有...“、”任何...“、”任意...“ 等, 用 ∃(称为 存在量词) 表示 ”有...“、”总有...“、”存在...“ 等。

注:∀ 为 Any 的首字母 A 上下颠倒得到,∃ 为 Exist 的首字母 E 左右翻转得到。

于是令,

P(x) = x 是人,A(x) = x 会死,B(x)=x是天才

则 ⑸ 和 ⑹ 分别表示为:

∀x(P(x)∧A(x)) ⑸&39;

注:在数学中,∀x(P(x)∧A(x)) 也被写成 ∀x, P(x)∧A(x) ,这样可以省一层 括号,看着清爽。

最后,复合命题可能有多层嵌套,例如:

并非所有人都是天才

这时改写成 逻辑语言 时,需要使用 括号 进行分层,例如:

¬(∀x(P(x)∧B(x)))

至此,我们就得到了全部的 谓词逻辑 语言。

回头,再比较 ⑶ 和 ⑷,我们发现 它们的 主语 都是 老张,于是课将谓语参数化,得打:

老张 P

这样 谓词 P 就成了 变元。 这种情况,日常交流也经常遇到,例如:

老张有的,老马也有。

写成 逻辑公式就是:

∀P(P(老张) → P(老马))

这种将 谓词作为 变元的,称为 高阶逻辑,而 不将 谓词作为 变元的,就是本篇介绍的 一阶逻辑,也是被数学所使用的逻辑。

站在 数学的角度,联词 就是 集合 {T, F} 上的 逻辑运算,由于逻辑运算的操作数只有 T 和 F 两个,于是我们可以将 全运算 情况 罗列出来,得到如下的 真值表:

从真值表中可以看出,¬ 是一元运算,其它的都是 二元运算。逻辑运算可以是任意有限元的,特别是 零元运算,定义为:

恒真 ⊤ = T;恒假⊥= F;

注:有些书 会用 ⊤ 和 ⊥ 分别去记 真 和 假。

虽然,逻辑运算多种多样,但是它们可以 通过 有限 个 联词 的 组合来实现,能够实现所有逻辑运算 的 联词集,被称为 功能完全集。可以证明:

联词集 {¬, ∨, ∧, →, ↔} 是 功能完全的

这也是,为什么自然语言 仅凭借 它们,就可以表达所有 逻辑,的 原因。

观察,上面真值表 中 的 p, q 与 p → q 之间的逻辑关系,我们发现:

当 p=T 并且 q=F 时 p → q 为 F;其它情况p → q都是 T;

于是有:

¬(p → q) = p∧¬q ①

进而得到:

p → q = ¬(¬(p → q)) = ¬(p∧¬q)

这种方法 称为 写假法。再观察,还发现:

当 p=T 并且 q=T 时 p → q 为 T;当 p=F 时 p → q 为 T;其它情况 p → q 都是 F;

于是可得到:

p → q = (p∧q)∨¬p

这种方法 称为 写真法。

对于任意逻辑运算,我都可以通过,写假法 或 写真法,用{¬, ∨, ∧}去实现它,例如:

p↔q = ¬((¬p∧q)∨(p∧¬q)) 或 (¬p∧¬q)∨(p∧q)

故, {¬, ∨, ∧} 是功能完全集。

对于 p∨q 和 p∧q 使用写假法,可分别得到:

¬(p∨q) = ¬p∧¬q

¬(p∧q) = ¬p∨¬q

这就是 德摩根定律,进而分别有,

p∨q=¬ (¬p∧¬q)

p∧q = ¬(¬p∨¬q)

这说明,{¬, ∨} 和 {¬, ∧} 也都是功能完全集。另外,由 ① 式,有,

¬(p → ¬q) = p∧¬(¬q) = p∧q

所以,{¬, →} 也是功能完全集。

那么,有没有一个联词的功能完全集呢?有!我们定义:

皮尔士箭头: p↓q = ¬(p∨q)谢弗竖: p|q = ¬(p∧q)

则分别有,

p∨q = ¬¬(p∨q) = ¬( p↓q) , ¬p = ¬(p∨p) = p↓p;

p∧q = ¬¬(p∧q) = ¬(p|q), ¬p = ¬(p∧p) = p|p;

所以,{↓} 和 {|} 都是功能完全集,也是最小的功能完全集。

在数学上,将 F 和 T 分别看做 0 和 1,这样以来算术运算也就成了逻辑运算,例如:

p⋅q = p∧q

最后,结合数学运算,将 一元 和 二元 的所有逻辑运算汇总如下:

一元逻辑运算:

二元逻辑运算:

(好了,就写到这里了,以后想到了再补充!本篇力求简单,尽量不耗费各位的时间,希望大家有机会看到,希望看到的能喜欢!)

补充1:

大家看到 蕴含 p→q 的真值表:

F → T = T,F → F = T

可能会差异。诚然,这和我们日常言语中的感觉不同,实际上,自然语言中的,“如果 p 那么 q” 含有 逻辑推理的 意思,其相当于:

{p, p→q} ⇒ q

这与 p→q 的语义 并不相同。

本文内容由小春整理编辑!