关于逻辑

逻辑学家的笑话

有一个流传甚广的笑话： 三个逻辑学家走进了一个小酒馆， 酒保问：“你们是不是都要啤酒？” 逻辑学家A回答：“我不知道。” 逻辑学家B回答：“我不知道。” 逻辑学家C回答：“是。”

通常人们不仔细想想无法理解其中的笑点。 其中的趣味是逻辑学家们把酒保的问题当作了一个逻辑命题： 只有三人都要啤酒，才应该回答“是”（真命题）； 只要有其中一人不要啤酒，就应该回答“不是”（假命题）。

当A回答时，如果他不想要啤酒，酒保的问题就是一个假命题，A应该回答“不是”。 但A并没有回答“不是”而回答了“不知道”，因为他想要啤酒，但又不知道其余两人是否需要，所以他无法判断这个命题的真假。 同理，B也回答了“不知道”，因为B也想要啤酒，但又不知道C是否想要。 当C回答时，因为他从之前二人的答案中推测出A和B都想要啤酒，而自己也想要，所以他可以确定酒保的问题是真命题，所以回答了“是”。

之所以说这个笑话的原因是，尽管很多时候我们自认为“很有逻辑”，但逻辑往往不是那么显然，有些简单的逻辑问题可能会让自认为有逻辑的我们挠破头皮。

男性是否比女性滥情

联想到MIT 6.042J上介绍了一个关于图论的问题也有类似的欺骗性： 男性和女性比较，平均来说谁有更多异性的性伴侣？

从社会科学角度来说，这可能是一个很有意思的课题。 人们可能会希望通过研究此类问题来讨论性开放程度和性别之间的关联：男性和女性相比，谁更“滥情”？ 通常人们可能会猜测男性是性关系中比较主动的一方，自古以来也是一夫多妻制比较多，所以男性的平均性伴侣数会比较多。 芝加哥大学甚至就此采访调查了不少人还出版了书籍，他们声称：美国男性的平均异性性伴侣数比女性多74%。 ABC新闻也做了类似的社会调查，得出的结论是：男性一生平均有20个性伴侣而女性只有6个。（多233%）

从图论角度看，他们的结论都是站不住脚的。 如果我们把人当作节点（vertex），把异性性伴侣关系当作边（edge），那我们可以得到一个无向图（undirected graph）。 那么，男性的平均性伴侣数就是男性节点的平均度数（记作\(A_m\)，the average degree of man vertices）， 女性的平均性伴侣数就是女性节点的平均度数（记作\(A_w\)，the average degree of woman vertices）。 即：

每一条edge必然一头是男性另一头是女性， 所以我们知道，总边数等于男性节点的度数之和，也等于女性节点的度数之和，即：

我们可以得到：

所以，根据简单的图论知识我们证明得到的结论是，男女平均异性性伴侣数之比是社会中男女人口比例的反比。 从这个例子我只是想说，人们的常识不一定靠得住，一些问题的答案可能是反直觉的。

一些不一定显然的逻辑基础

如果···那么···

作为习惯了布尔运算的程序员，我们能很自如地写出与（and，\(\land\)）、或（or，\(\lor\)）、非（not，\(\neg\)）的真值表。 我们用字母P、Q代表任意两个命题，可以写出如下真值表。

形如“如果P那么Q”的命题，我们记作\(P \implies Q\)。 对“如果那么”关系（implication）我们并不陌生，因为我们在数学证明中一直在用这个符号，但如果叫我们写出真值表，不见得所有人都写对。

注意真值表上的最后两行，为什么P为假时，\(P \implies Q\)恒为真呢？ 这可能是反直觉的，至少我第一次看到它时想了很久没有想通。 我们通过一个例子来看一个相对直观的解释： 我和朋友打赌：“如果明天下雨，那么我就给你100元。” 结果第二天没有下雨，所以无论我是否给我朋友100元，我都没有食言。

起初可能一些人会凭直觉认为，如果P为假，Q为真，那么\(P \implies Q\)应该为假。 他们给出的解释是：假命题怎么可以推出真命题呢？ 这是因为人们说“如果···那么···”这样的句式的时候，他们的思维往往并不是逻辑学意义上的implication，而是“等价关系”。

为了理解这一点，我们同样还是看那个打赌的例子：如果第二天没有下雨，结果我却把100元钱给朋友了，那朋友很可能会觉得奇怪问我：“你不是说下雨才给我100元的吗？这不没有下雨么，你给我钱干嘛？” 我会告诉他：“我只说了‘如果下雨的时候’我会给你钱，我并没有说‘如果没有下雨’我会干什么呀！所以现在我给不给你钱都行。” 产生这样分歧的原因是，朋友听到“如果···那么···”句式的时候，他脑子里做了“自动补全”：下雨就给钱，不下雨就没钱。 然而字面上我其实只说了前半句，后半句是朋友脑补的。 朋友脑中其实是等价关系的概念，而逻辑学上说这句话只是implication。 我们在后面的讨论中会进一步的看到，implication和等价关系的联系。

在逻辑学上implication是有严格定义的，\(P \implies Q\)等价于\(\neg P \lor Q\)，通过下表你可以简单的验证它们的等价关系。

等价关系

等价关系(equivalence)，记作\(P \equiv Q\)，即P和Q同真同假，满足下面真值表（前三列）。

等价关系，也就是我们在数学证明中常说的“充分必要”。 我们常说：“如果我们知道\(P \implies Q\)和\(Q \implies P\)，那么可以得到\(P \equiv Q\)。” 然而这种说法同样在逻辑上是不严谨的，这种说法听起来似乎在说\((P \implies Q) \land (Q \implies P)\)与\(P \equiv Q\)之间只是“如果那么”（implication）的逻辑关系，也就是说\(((P \implies Q) \land (Q \implies P)) \implies (P \equiv Q)\)。 然而众所周知他们之间是等价关系，即\(((P \implies Q) \land (Q \implies P)) \equiv (P \equiv Q)\)，这一结论也可以通过上面真值表的后三列看出。

顺便值得注意的是，从上表可以看出，\(P \implies Q\)和\(Q \implies P\)不可能同时为假。

如果···那么···否则···

还有一种“条件关系“(IF-THEN-ELSE)：形如“如果P那么Q否则R”，我们记作\(if\ P\ then\ Q\ else\ R\)。 \(if\ True\ then\ \alpha\ else\ \beta\)等价于\(\alpha\)， \(if\ False\ then\ \alpha\ else\ \beta\)等价于\(\beta\)。 这对于习惯写程序的我们是很容易理解的。 有趣的是“条件关系”是一种很强的逻辑关系， 我们可以用它表示上诉所有的基本逻辑关系， 下面是基本的逻辑关系和条件关系之间的等价表。

从上表我们可以更好地看出，我们日常说“如果\(P\)那么\(Q\)”时，其实是在说“如果\(P\)那么\(Q\)否则\(\neg Q\)”，只是懒惰的我们在日常会话中省略了“否则”的部分。

最后还有一个重要的等价性质：任意\(if\ P\ then\ Q\ else\ R\)，等价于\((P \implies Q) \land (\neg P \implies R)\)，即\((\neg P \lor Q) \land (P \lor R)\)。

编程中的逻辑分析

一些逻辑学知识，可以帮助你写出更清晰简短的代码。 这里举个例子：学校需要排课，已知课程的开始和结束时间，我们想判断两门课是否不冲突，也就是说没有时间上的重叠。 假设课程1的开始和结束时间分别为s1和e1（s1 < e1）， 课程2的开始和结束时间分别为s2和e2（s2 < e2）， 写一个函数is_compatible(s1, e1, s2, e2)， 如果两门课程不冲突返回True，否则返回False。

作为一个编程新手，我很自然地想到了应该先判断两门课程哪一门先开始，分三种情况讨论。 于是就有了第一个版本。

def is_compatible(s1, e1, s2, e2):
    if s1 < s2:
        # If class 1 starts before class 2,
        # then class 1 must end before class 2 starts.
        return e1 <= s2
    elif s1 > s2:
        # If class 1 starts after class 2,
        # then class 2 must end before class 1 starts
        return e2 <= s1
    else:
        # If class 1 starts at the same time as class 2,
        # then they must be incompatible.
        return False 

这是一个正确的实现，但却比较冗长， 我们可以通过逻辑学知识简化代码。 但为了套用逻辑学知识，我们先将程序稍加变形。

def is_compatible(s1, e1, s2, e2):
    if s1 < s2:
        return e1 <= s2
    else:
        if s1 > s2:
            return e2 <= s1
        else:
            return False 

这样我们就可以套用IF-THEN-ELSE的逻辑规则优化代码，首先观察到对嵌套在最里面的if else，我们可以套用\(P \land Q\)和\(if\ P\ then\ Q\ else\ False\)的等价关系。

def is_compatible(s1, e1, s2, e2):
    if s1 < s2:
        return e1 <= s2
    else:
        return (s1 > s2) and (e2 <= s1) # replace `if else` block with `and`

因为已知输入中e2 > s2，所以e2 <= s1时s1 > s2必然成立(always true)，所以s1 > s2是多余条件（\(True \land P\)等价于\(P\)）。 代码可以进一步简化为：

def is_compatible(s1, e1, s2, e2):
    if s1 < s2:
        return e1 <= s2
    else:
        return e2 <= s1 # remove redundant condition

看似已经十分简化了，我们还可以更近一步。 我们很容易观察到s1 < s2 and e1 <= s2为真时，函数必然为真。 因为已知输入中s1 < e1，所以e1 <= s2时s1 < s2必然成立， 所以e1 <= s2为真时，函数必然为真。 我们得到下面这个等价的程序。

def is_compatible(s1, e1, s2, e2):
    if e1 <= s2:
        return True # Since `s1 < s2` must be true, we can return True early.
    else:
        # below is the same as the code before
        if s1 < s2:
            return e1 <= s2
        else:
            return e2 <= s1

注意到上面程序中第7行的e1 <= s2因为在外层if的else中，所以恒为False。

def is_compatible(s1, e1, s2, e2):
    if e1 <= s2:
        return True
    else:
        if s1 < s2:
            return False # replace `e1 <= s2` with False
        else:
            return e2 <= s1

根据\(if\ P\ then\ Q\ else\ R\)和\(if\ \neg P\ then\ R\ else\ Q\)的等价关系，继续改写：

def is_compatible(s1, e1, s2, e2):
    if e1 <= s2:
        return True
    else:
        # negate the condition and flip the if-else block
        if s1 >= s2:
            return e2 <= s1
        else:
            return False

对嵌套在里面的if else继续套用\(P \land Q\)和\(if\ P\ then\ Q\ else\ False\)的等价关系。

def is_compatible(s1, e1, s2, e2):
    if e1 <= s2:
        return True
    else:
        return (s1 >= s2) and (e2 <= s1) # replace `if else` with `and`

根据之前的推论（已知s2 < e2，e2 <= s1时s1 > s2必然成立），所以s1 >= s2恒为真，是多余的条件。我们得到：

def is_compatible(s1, e1, s2, e2):
    if e1 <= s2:
        return True
    else:
        return e2 <= s1 # remove redundant condition

根据\(P \lor Q\)和\(if\ P\ then\ True\ else\ Q\)的等价关系，最后我们得到：

def is_compatible(s1, e1, s2, e2):
    return (e1 <= s2) or (e2 <= s1) # replace `if else` with `or`

简单地说，我们只需要判断一门课开始前，另外一门课已经结束了，我们就可以断定两门课不冲突。 是的，我绕了个大圈子，得到了一个对聪明的程序员来说似乎显而易见的结论。 我是不是特别笨呢？