真假条件与有限逻辑推理

把文字条件转成可以逐项检验的命题

有限逻辑问题由一组候选状态和若干限制条件组成。状态可以是奖品的位置、人物与职业的对应关系，也可以是各句话的真假。求解目标是找到满足全部条件的状态，而不是找到一组看起来合理的解释。

1. 列明对象与取值。 例如三个人对应三种职业，若每人恰有一种、每种恰有一人，就应把对应关系记成一个双射；没有“一一对应”条件时不能自行添加。
2. 把每句话记为命题。 “甲是医生或乙是教师”是一个复合命题；“只有一句是假话”应统计整句话的真值，不能把其中两个分句分别计数。通常“或”允许两者都真；“恰有一个”才排除同时为真。
3. 按完整状态分类。 将每个候选代入所有陈述，在对应表中标出真、假及是否满足额外约束。分类须覆盖全部可能，且同一状态不要重复计入。
4. 先用必然关系缩小范围。 $P$ 与 $\neg P$ 恰有一句真；两个命题不能同时为真，只能推出至多一个真，不能推出恰有一个真。
5. 回代与唯一性。 得到候选后仍须逐条回代。若有两个合法候选，结论就是不唯一；若没有合法候选，应检查条件是否矛盾或转译有误。

对应表中的一行表示一个人，一列表示一种身份，格中标记允许或排除。只有明确一一对应时，某行确定身份后才能排除同列其他位置。表格只是保存约束的工具，推理依据仍是题目条件。

逆向推理：先确定终局，再确定前一步

当过程只有有限阶段，而且后一阶段的选择会影响前一阶段时，可以从最后阶段逐层倒推。这与数列的数学归纳法用途不同：这里要确定在给定选择规则下，每个状态将产生什么结果。

先列出终局及其结果，再对倒数第二阶段的每个合法行动，写出它通向的终局；按照题目规定的偏好选择行动。随后把已确定的结果作为更早阶段的已知信息，逐层向前重复。

其正确性可以按“剩余阶段数”证明：剩余零步时结果已知；若所有剩余 $k$ 步的状态均已正确求出，则剩余 $k+1$ 步时，每个行动的后果都已知，依照规定的选择规则比较即可。有限次后覆盖初始状态。

必须保留的条件。 谁先行动、能看到哪些信息、投票门槛、是否允许弃权、同分时怎样选择以及生存与收益的优先级，都会改变倒推结果。若偏好没有规定同分选择，只能保留多个可能结果，不能擅自指定唯一行动。存在随机选择时还要比较题目指定的期望或成功概率，不能直接套用确定性倒推。

信息条件：知道一个事实与知道别人也知道

设 $P$ 是一个事实。“甲知道 $P$”表示在甲当前认为可能的所有状态中，$P$ 都成立；“甲知道乙知道 $P$”则还要求甲能排除那些乙无法判断 $P$ 的状态。这是两个不同层次的条件。

例如甲、乙各自收到私信，均得知同一事实 $P$，但不知道对方收到了什么。此时两人都知道 $P$，却未必知道对方也知道 $P$。若主持人在双方都能听见、且双方都知道彼此能听见的场合公开宣布 $P$，信息就更强：两人都知道 $P$，都知道对方知道，依次继续。把所有有限层次的相互知晓称为共同知识。

处理此类题，可先列所有与可见信息相符的状态。某人公开说“我不知道”时，排除那些会使此人当时能够唯一确定答案的状态；下一位必须在更新后的状态集合中推理。每次筛选都要使用发言当时的信息，不能把后来得到的结论提前使用。

公开宣布的事实即使每人已经各自看见，也可能通过增加“别人知道什么”的层次改变结论。因此信息题中的公开、私下、同步、先后顺序都是数学条件。

验证一个策略，需要覆盖每个允许的分支

策略是按当前可观察状态指定行动的规则。证明策略有效，应写清初始行动、对每一种允许回应的下一步、能够继续执行的理由，以及最终满足目标的理由。

一种常见结构是保持某个性质 $I$：先证明初始状态具有 $I$；再证明对手采取任一合法行动后，都能作出允许的回应使 $I$ 恢复；最后证明过程必然终止，且终局具有 $I$ 时满足目标。只证明某一条顺利的过程，不能说明策略对所有对手行动有效。

信息编码策略还须说明：发送者知道什么、能发送哪些信号、信号怎样由已知信息算出、接收者利用信号及自己的信息能恢复什么。若声称可区分所有情形，必须证明不同待区分情形不会产生无法辨别的同一观测；若只保证恢复一部分信息，应明确恢复目标。