读《程序员数学》2-逻辑

2019-06-19 本文已影响0人 shine100

逻辑是消除歧义的工具。
1、能够判断对错的陈述句叫做命题（proposition）。
命题正确则为真，反之为假。
如：
明天会下雨吗？ -- 疑问句
明天可能下雨。 -- 猜测，无法判断
明天会下雨。 -- 命题，明天下雨就是真，明天不下雨就是假。

2、在考虑规则时，确认是否“遗漏”和“重复”是非常重要的
没有“遗漏”，即具备完整性。此明确该规则包含了所有情况。
没有“重复”，即具备排他性，此明确该规则不存在交叉之处。
在处理大问题时，将其分解问多个小问题，此时要注意的就是完整性和排他性。

3、逻辑非 $\overline A$

真值表是表征逻辑事件输入和输出之间全部可能状态的表格。真值表没有遗漏和重复，兼顾完整性和排他性。

文氏图是标识集合关系的图，外围矩形标识全集。

（1）真值表

image.png

（2）文氏图
命题A：电影院1.2米及以下不要钱

image.png

命题 $\overline A$ ：1.2米以上都需要购买电影票

image.png

4、逻辑与 $A \cap B$
（1）真值表

image.png

（2）文氏图

image.png

5、逻辑或 $A \cup B$
（1）真值表

image.png

（2）文氏图

image.png

6、异或 $A \oplus B$
命题A “我现在在武汉”
命题B “我现在在北京”
组合起来"我现在在武汉或者我现在在北京，但我只能在其中一处"。这就是异或： A或B 但不能同时满足。
（1）真值表

image.png

（2）文氏图

image.png

7、相等 A = B
（1）真值表

image.png

（2）文氏图
（并不是两个重叠起来的圆）

image.png

这种无论A和B的真假，恒等于true的命题称为恒真命题。

8、蕴含 A => B
命题A“今天下雨”
命题B“我不出门”
组合起来“如果今天下雨，我就不出门。”（不下雨的情况没有提，也就是说可能出门也可能不出门）
这就是蕴含：若A则B，A => B

组合起来的另一种情况 “如果今天下雨，我就不出门。不下雨，我就出门”
这就是A=B （注意和上面的区别）

（1）真值表

image.png

（2）文氏图

image.png

$\overline B => \overline A称为 A => B的逆否命题$
如果原命题为真，则逆否命题为真，若原命题为假，则逆否命题为假。

9、德.摩根定律
$\overline A \cup \overline B = \overline {A \cap B}$
$\overline A \cap \overline B = \overline {A \cup B}$
（可以根据对偶性记忆
$A 变为 \overline A ，B变为 \overline B，\cap 变为 \cup，\cup 变为 \cap$ ）

（1）真值表

image.png

（2）文氏图

image.png

10、卡诺图
卡诺图是将所有命题的真假组合以二维表的形式表示的图。
（1）卡罗图结构特点：
a、n个变量的卡诺图由2^n个小方格组成，每个小方格代表一个最小项。如 2个变量的卡诺图有4格。
b、在几何位置上相邻的最小项小方格在逻辑上也必定是相邻的，即相邻两项中有一个变量是互补的。如00横着相邻只能是01 不能是11，竖着相邻的只能是10也不能是11。

（2）卡诺图化简逻辑函数的基本原理，
(固定一个变量罗列出所有情况，则可以简化为此变量)
a. 依据关系式
$AB + A\overline B = A$
，即两个“与”项中，如果只有一个变量相反，其余变量均相同，则这两个“与”项可以合并成一项，消去其中互反的变量。

b. 相邻最小项用倒角矩形圈(或椭圆形圈)圈起来，称为卡诺圈。在合并项(卡诺圈)所处位置上，若某变量的代码有0也有1，则该变量被消去，否则该变量被保留，并按0为反变量，1为原变量的原则写成乘积项形式的合并项中。

卡诺圈：用框将相邻的标位1的网格围起来形成组合框，组合框为以下网格(x * y)：
1 * 1
1 * 2 或 2 * 1
2 * 2
1 * 4 或 4 * 1
4 * 4
相邻打钩网格形成的最大网络，组合框相互重叠没有关系。

（4）2个变量逻辑表达式简化
命题A：绿灯亮
命题B：黄灯亮

问题是，请在以下情况之一时按下按钮：
绿灯灭，黄灯亮；
绿灯、黄灯都灭；
绿灯、黄灯都亮；
即
$(\overline A \cap B) \cup (\overline A \cap \overline B) \cup (A \cap B)$
求化简表达式。

第一步写真值表，将为true的网格写为1或打钩，并画出卡诺圈。

image.png

第二步简化
横着的圈，可以观察为 $\overline A$ ，也可以用逻辑表达式计算得出：
$\overline A \overline B + \overline A B = \overline A$

竖着的圈，可以观察为B，也可以用逻辑表达式计算得出：
$\overline A B + A B = B$

最后简化为
$\overline A \cup B$

（5）3个变量逻辑表达式简化
命题A：绿灯亮
命题B：黄灯亮
命题C：红灯亮

问题是，请在以下情况之一时按下按钮：
绿灯、黄灯、红灯都灭；
黄灯灭、红灯亮；
绿灯灭、黄灯亮；
绿灯、黄灯、红灯都亮；
即
$\overline A \overline B \overline C + \overline B C + \overline A B + ABC$
求化简表达式

image.png

由卡诺图化简可得
$\overline A + C$

11、包含未定义的三值逻辑
（1）无法得出true 或者 false，则为未定义 undefined。
（2）带条件的逻辑，就是编程中的短路，应该根据条件A判断是否需要看B。
这里用1代表true，0代表false，X代表undefined，逻辑真值表如下：
a、带条件的逻辑与（&&）

image.png

b、带条件的逻辑与（||）

image.png

c、否定（!）

image.png

（3）三值逻辑符合德.摩根定律
编程中实际运用，如
if (! (x >= 0 && y >=0)) {
......
}

可以化简为
if(x<0 || y < 0) {
......
}

参考
https://baike.baidu.com/item/卡诺图化简法/18894817?fr=aladdin

读《程序员数学》2-逻辑

猜你喜欢

热点阅读