卡诺图与三值逻辑
卡诺图
- 卡诺图（Karnaugh map） 是将所有命题的真假组合以二维表的形式表示的图
- 作用：简化复杂逻辑表达式
- 格子数 = 2^(命题个数)
二灯游戏
游戏规则
- 屏幕上一绿一黄两个灯泡，不断忽闪忽灭
- 需要在下列情况按下按钮：
- 绿灯灭，黄灯亮
- 绿灯、黄灯都灭
- 绿灯、黄灯都亮
首先借助逻辑表达式进行思考
两个基本命题：A = 绿灯亮，B = 黄灯亮
三条规则对应的逻辑表达式
(!A) && B 绿灯灭，黄灯亮
(!A) && (!B) 绿灯、黄灯都灭
A && B 绿灯、黄灯都亮需要按下按钮 = 三者的逻辑或
((!A) && B) || ((!A) && (!B)) || (A && B)
这完全没有简化，要一边观察灯的亮灭一边判断表达式真假，实在难以做到
学习使用卡诺图
把 A、B 的所有真假组合做成二维表，在「应该按下按钮」的格中打钩
A \ B false true false ✓ ✓ true ✓ 用框把相邻的打钩格围起形成组合框
组合框取以下网格中相邻打钩格所形成的最大网格：
- 1 × 1
- 1 × 2
- 2 × 2
- 1 × 4
- 4 × 4
组合框相互重叠也没关系
每个组合框对应一个逻辑表达式
- 横向的组合框 = A 为 false 的区域，用
!A表示 - 纵向的组合框 = B 为 true 的区域，用
B表示
- 横向的组合框 = A 为 false 的区域，用
所有打钩格所在区域 =
(!A) || B也就是说：绿灯灭或者黄灯亮的时候按下按钮
原来的
((!A) && B) || ((!A) && (!B)) || (A && B)和(!A) || B是相等的用代码验证这个简化
#ruby
# 二灯游戏：原始表达式 vs 卡诺图简化后的 (!A) || B
a = b = nil
[true, false].each do |a|
[true, false].each do |b|
# 规则：绿灯灭黄灯亮 / 都灭 / 都亮
raw = ((!a) && b) || ((!a) && (!b)) || (a && b)
karnaugh = (!a) || b
printf("A=%-5s B=%-5s 原始=%-5s 卡诺图=%-5s 相等=%s\n",
a, b, raw, karnaugh, raw == karnaugh)
end
end
# A=true B=true 原始=true 卡诺图=true 相等=true
# A=true B=false 原始=false 卡诺图=false 相等=true
# A=false B=true 原始=true 卡诺图=true 相等=true
# A=false B=false 原始=true 卡诺图=true 相等=true
三灯游戏
游戏规则
- 三个灯泡：绿、黄、红
- 需要在下列情况按下按钮：
- 绿灯、黄灯、红灯都灭
- 黄灯灭，红灯亮
- 绿灯灭，黄灯亮
- 绿灯、黄灯、红灯都亮
用卡诺图表示
三个命题：A = 绿灯亮，B = 黄灯亮，C = 红灯亮
网格数变为 2³ = 8 个
B 和 C 的 false/true 分界是错位的。正是这个「错位」，使得用 8 个网格就能表示所有情况
A \ BC 00 01 11 10 false ✓ ✓ ✓ ✓ true ✓ ✓ 同样地尽可能用大的框分组
- 横向的组合框 = A 为 false 的区域，用
!A表示 - 正中间的组合框 = C 为 true 的区域，用
C表示
- 横向的组合框 = A 为 false 的区域，用
打钩区域用
!A和C的逻辑或表示：(!A) || C规则看起来相当复杂，通过卡诺图却能大幅简化
包含未定义的逻辑
未定义的第三种状态
有些命题既不是真也不是假，而是「未定义」
例如：红绿灯在闪烁时，红灯是什么状态？
命题 A 命题 B A && B true true true true false false true undefined undefined false true false false false false false undefined false undefined true undefined undefined false false undefined undefined undefined
带条件的逻辑与（&&）
- 逻辑与要求两边都为真才为真
- 只要有一边是 false，结果就是 false —— 不管另一边是什么
- 所以未定义的那一边不影响结果
带条件的逻辑或（||）
- 逻辑或要求至少一边为真才为真
- 只要有一边是 true，结果就是 true —— 不管另一边是什么
- 未定义的那一边同样不影响结果
三值逻辑中的否定（!）
未定义的否定还是未定义
A !A true false false true undefined undefined
三值逻辑的德摩根定律
!(A && B) == (!A) || (!B)在三值逻辑里依然成立也就是说：逻辑与的否定，等于两边否定的逻辑或
代码验证
#ruby
# 三值逻辑：true / false / nil(未定义)
def band(a, b)
return true if a == true && b == true
return false if a == false || b == false
nil
end
def bor(a, b)
return true if a == true || b == true
return false if a == false && b == false
nil
end
def bnot(a)
a.nil? ? nil : !a
end
vals = [true, false, nil]
ok = true
vals.each do |a|
vals.each do |b|
ok &&= (bnot(band(a, b)) == bor(bnot(a), bnot(b)))
end
end
puts "三值德摩根成立: #{ok}" # 三值德摩根成立: true
# 未定义参与逻辑与：只要有一边 false，结果就是 false
puts "false && nil = #{band(false, nil).inspect}" # false && nil = false
puts "nil && true = #{band(nil, true).inspect}" # nil && true = nil
puts "!nil = #{bnot(nil).inspect}" # !nil = nil