布尔代数 [计算机数学专题(8)]

标签：逻辑专题计算机布尔代数公式命题真值蕴含推理

简介

布尔代数又称逻辑代数，是与计算机最紧密的一个数学分支。

布尔代数建立于俩个逻辑值和三个运算符，是计算机二进制、开关逻辑元件、逻辑电路的设计基础。

俩个逻辑值：真、假，(1、0)。

三个运算符：与、或、非，(

$\wedge ~\vee$

$\lnot$

)。

历史

1847年，英国数学家乔治·布尔发表著作《The Mathematical Analysis of Logic》，建立布尔代数。

1815年，乔治出身家境贫寒(皮匠)，读书也是一件困难事。

20岁时，对数学产生浓厚的兴趣。

广泛涉猎了许许多多的数学家著作，并留下了大量的推导笔记。

后完成了前辈莱布尼茨的工作，设计一种用于逻辑推导的专用语言，使用这种语言可以只凭计算得到当下哪怕是最复杂的真理。

这门语言借助于符号和规定的语法来引导计算，每个符号代表一个简单的概念，通过组合各种符号表达复杂的思想或环境。

1855年，布尔与皇后学院一位希腊文教授的女儿新婚。

曾经编写的微积分方程、差分方程课本，一直流行于英国19世纪?️期。

1864年，因暴风雨坚持上课后死于肺炎。

命题

具有或必将具有确定真、假意义的陈述句。

真、假意义：0/1、真\假、True\False。

一个命题(满足条件的简单陈述句)被称为 "原子命题"。

e.g. 明天会下雨。

几个原子命题通过逻辑联词组合在一起的命题被称为 "复合命题"，或原子命题的否定。

举一些语句，判断是否是命题。

1+10=11。
宇宙中除了地球，还有生命存在。
我正在说谎。

1、2 是命题，3 是悖论。

1 ：在 2 进制中是真命题，其余进制是假命题，总之是命题。

2 ：虽然现在还不知道，但到未来的某个时间一定会弄清楚满足命题必将具有的性质所以也是命题。

命题非真即假的定义，所以A是悖论。

逻辑联词

构建复合命题。

计算机里面常用的3个，(一假必假)与、(一真必真)或、(取反)非，等同逻辑的合取

$\land$

、析取

$\lor$

、否定

$\lnot$

。以及条件

$\to$

，P

$\to$

Q，读：若 (命题)P 则 (命题)Q，P称前件，Q称后件；双条件

$\leftrightarrow$

，P

$\leftrightarrow$

Q，读：P 当且仅当 Q。若 P

$\leftrightarrow$

Q 取真，则 P 与 Q取相同的真值(真值：真或假)。

运算定律

凭计算得到当下哪怕是最复杂的真理。

运算定律，共 12 个，其组成的等式叫基本等价式。

对合律
$\lnot$
(
$\lnot$
p) = p
幂等律 p
$\land$
p = p 、 p p = p
结合律 (p
$\land$
q)
$\land$
r = p
$\land$
(q
$\land$
r) 、 (p q) r = p (q r)
交换律 p
$\land$
q = q
$\land$
p 、 p q = q p
分配律 p
$\land$
(q r) = (p
$\land$
q) (p
$\land$
r) 、p (q
$\land$
r) = (p q)
$\land$
(p r)
吸收律 p
$\land$
(p q) = p、p (p
$\land$
q) = p
反演律
$\lnot$
(p
$\land$
q) =
$\lnot$
p $\lnot$
q 、
$\lnot$
(p q) =
$\lnot$
p
$\land$
$\lnot$
q
壹律 p
$\land$
T = p、p F = p
零律 p
$\land$
F = F、p T = T
矛盾律
$\lnot$
(p
$\land$
$\lnot$
p) = T
排中律 p $\lnot$
p = T
联词转换律 p q =
$\lnot$
p q 、p q = (p q)
$\land$
(q p)

p.s. 一般书写形式 P、Q、R 为大写，但又觉得小写方便阅读所以采用小写。

对合律，如同负负得正，矛盾律说明了一个命题不能即是真又是假，排中律说明了一个命题要么为真要么为假。

基本蕴含式

基本蕴含式是继续逻辑推理，一个最基本的依据也是人们思维推理的一些常用方法。

化简式 P
$\land$
Q
$\Rightarrow$
P、P
$\land$
Q
$\Rightarrow$
Q
附加式 P
$\Rightarrow$
P Q、Q
$\Rightarrow$
P Q
假言推理 P
$\land$
(P
$\rightarrow$
Q)
$\Rightarrow$
Q
拒取式
$\lnot$
Q
$\land$
(P
$\rightarrow$
Q)
$\Rightarrow$

$\lnot$
P
析取三段论
$\lnot$
P
$\land$
(P Q)
$\Rightarrow$
Q
假言三段论 (P Q)
$\land$
(Q R)
$\Rightarrow$
P R
二难推论 (P Q)
$\land$
(P R)
$\land$
(Q S)
$\Rightarrow$
R S
等价三段论 (P
$\leftrightarrow$
Q)
$\land$
(Q
$\leftrightarrow$
R)
$\Rightarrow$
(P
$\leftrightarrow$
R)
合成式 P，Q
$\Rightarrow$
P
$\land$
Q（有前提P，Q 可得结论P
$\land$
Q）

$\Rightarrow$

读作 "蕴含"，命题中的永真公式称为 "重(第 2 声)言式"，永假公式称为 "矛盾式"，非"矛盾式"的命题公式称 "可满足式"。

$\to$

Q 是重言式，当且仅当 P

$\Rightarrow$

Q。

即当且仅当 P 取真值 "真" 时，Q 必取真值 "真"; 或即当且仅当 Q 取真值 "假" 时，P 必取真值 "假"。

所以，一个正确的逻辑推理(形式)由真的前提出发必能得到真的结论，其前提与结论间的逻辑形式正是 "蕴含式"。

前提蕴含结论。

如果推理(形式)是正确的，那么由推理的前提和结论构成的条件公式是一个 "重言式"。

因此。

检查一个推理的推理形式是否正确，只需写出相应于推理的条件命题公式，判断这个条件公式是否是重言式(蕴含式)。

命题演算推理

前提经过正确的推理得到结论，一旦推理成立，结论也是蕴含式是正确的。

构造一个推理的过程实际上也是一个演绎过程。

设

$S = [ H_{1}, H_{2}, ... ,H_{n} ]$

是作为前提的命题公式集合，C 为要证结论。从 S 推出 C 的一个演绎是命题公式的一个有限序列：

$[G_{1}, G_{2}, ... G_{k}]$

，其中

$G_{i}$

或者属于 S，或者是在 TA 之前的某些

$G_{j}(j<i)$

的逻辑结果并且

$G_{k} = C$

。

按照这一定义，任何推理步骤可以写为 P 规则，T 规则，CP 规则。

P 规则：前提。

T 规则：引用先前步骤中得出的某些命题公式的逻辑结果，对是否是逻辑结果的判定，特别要使用基本蕴含式和基本等价式，TA们是我们已经证明过的事实，是使用 T 规则的依据。

CP 规则：如果需要论证的结论是 P

$\rightarrow$

Q 的形式，则可将 P 作为附加前提使用。

标签：逻辑,专题,计算机,布尔代数,公式,命题,真值,蕴含,推理
From： https://blog.51cto.com/u_13937572/6417567

布尔代数 [计算机数学专题(8)]

简介

历史

命题

逻辑联词

运算定律

基本蕴含式

命题演算推理

相关文章

赞助商

阅读排行