笔记9-《程序员的数学》复杂命题与德摩根定律

目录

1. 建立复杂命题
2. 六个逻辑运算
3. 德摩根定律

建立复杂命题

• 逻辑的基本是两个分支

  • 逻辑只有真（true）和假（false）两种状态
  • 命题 = 一个能判断真假的陈述句
  • 把简单命题组合起来，就得到复杂命题

六个逻辑运算

• 逻辑非——不是 A

  • 记作 !A（读作「非 A」）
  • A 为真则结果为假，A 为假则结果为真

  A	!A
  true	false
  false	true

• 逻辑与——A 并且 B

  • 记作 A && B
  • 两个都为真时结果才为真

  A	B	A && B
  true	true	true
  true	false	false
  false	true	false
  false	false	false

• 逻辑或——A 或者 B

  • 记作 A || B
  • 至少一个为真时结果为真

  A	B	A || B
  true	true	true
  true	false	true
  false	true	true
  false	false	false

• 异或——A 或者 B（但不都满足）

  • 记作 A ^ B
  • 两个命题的真假不同则为真

  A	B	A ^ B
  true	true	false
  true	false	true
  false	true	true
  false	false	false

• 相等——A 和 B 相等

  • 记作 A == B
  • 两边真假一致时为真

  A	B	A == B
  true	true	true
  true	false	false
  false	true	false
  false	false	true

• 蕴涵——若 A 则 B

  • 记作 !A || B
  • A 为假时结论随便都为真（因为「若 A 则 B」的前提没成立）
  • A 为真时才检查 B

  A	B	!A || B
  true	true	true
  true	false	false
  false	true	true
  false	false	true

• 囊括所有了吗

  • 每写一个运算都要问一句：所有组合都覆盖了吗？

  • 六个运算的真值表每个都是 4 行（2 个命题 × 2 个取值），没有遗漏也没有重复

  • 用代码枚举一遍，防止手写真值表时抄错

    #ruby
    # 枚举 A、B 的所有 4 种组合，输出各运算的真值
    [true, false].each do |a|
      [true, false].each do |b|
        printf("A=%-5s B=%-5s !A=%-5s A&&B=%-5s A||B=%-5s A^B=%-5s A==B=%-5s !A||B=%-5s\n",
               a, b, !a, a && b, a || b, a ^ b, a == b, !a || b)
      end
    end
    # A=true  B=true  !A=false A&&B=true  A||B=true  A^B=false A==B=true  !A||B=true
    # A=true  B=false !A=false A&&B=false A||B=true  A^B=true  A==B=false !A||B=false
    # A=false B=true  !A=true  A&&B=false A||B=true  A^B=true  A==B=false !A||B=true
    # A=false B=false !A=true  A&&B=false A||B=false A^B=false A==B=true  !A||B=true

德摩根定律

• 德摩根定律是什么

  • (非A) 或 (非B) 等价于 非(A 与 B)

  • (非A) 与 (非B) 等价于 非(A 或 B)

  • 文字表述：「非A」或「非B」等价于非「A 与 B」

    A	B	(!A) || (!B)	!(A && B)	(!A) && (!B)	!(A || B)
    true	true	false	false	false	false
    true	false	true	true	false	true
    false	true	true	true	false	true
    false	false	true	true	true	true

  • 「德摩根」是人名，1900 年前后提出的这个定律

• 对偶性

  • 在逻辑表达式中把 && 和 || 互换、每个命题取否定，就能得到该逻辑表达式的否定式

  • 这称作逻辑表达式的对偶性

  • 以 A && B 为例

    A && B
    ↓ 换成对偶：&& → ||，A → !A，B → !B
    (!A) || (!B)

  • 换过来的 (!A) || (!B) 恰好等于原式的否定 !(A && B)

  • 这就是德摩根定律：否定落在两边，和 && 换 || 是同一件事

  • 记住对偶性，德摩根定律就不用背了

  • 代码验证

    #ruby
    # 验证德摩根定律：两个式子在所有组合下都相等
    ok1 = ok2 = true
    [true, false].each do |a|
      [true, false].each do |b|
        ok1 &&= ((!a) || (!b)) == !(a && b)     # (!A) || (!B) == !(A && B)
        ok2 &&= ((!a) && (!b)) == !(a || b)     # (!A) && (!B) == !(A || B)
      end
    end
    puts "德摩根 1: #{ok1}"    # 德摩根 1: true
    puts "德摩根 2: #{ok2}"    # 德摩根 2: true
    
    # 对偶性：&& 换 ||、每项取否定，得到的式子等于原式的否定
    dual = [true, false].all? { |a| [true, false].all? { |b| ((!a) || (!b)) == !(a && b) } }
    puts "对偶性成立: #{dual}"  # 对偶性成立: true