离散数学 心得和好题 '离散数学及其应用笔记'

具体数学

ch1 逻辑与证明

好题

• 一个叫做chomp的游戏，这里每个矩形格中都放有一个曲奇饼，其中左上角那个曲奇是毒曲奇，两个玩家可以随意移动，但是每次移动过后必需吃掉他位置那个格子里的曲奇，如果哪个玩家移动后没曲奇吃或者吃了毒曲奇，那么就输了。请问两个玩家之一是否有必胜策略，是谁咧？
  

  解：这里用到的是非构造性证明，即不是通过举出一个列子来证明存在。
  首先，这个游戏不能是平局，而且在有限步内会分出胜负。假设，第一个玩家走了第一步，这里有两种情况，这是玩家一的获胜策略第一步，或者这是玩家二获胜策略第一步，如果是第二种情况，第一个玩家可以采用第二个玩家获胜策略相同的第一步，并继续循环这个策略，这将保证，第一个玩家获胜。
  这里我们只证明了获胜策略的存在性，但是并没有指明这个策略。

• 不用唯一量词表示唯一性逻辑，即，P(y)成立当且仅当x=y。
  解：$\exists x(P(x)\bigwedge \forall y(P(y)\rightarrow x=y))$
• 证明：假设“陆陆很笨”，“陆陆不帅”，结论：“彩虹尽头能找到金子” 是有效论证。那么结论能证明是真的嘛？
  解：因为前提条件为假，所以无法确定结论真假。

心得