关于扫雷小游戏的几个定理
我们用大写英文字母（A、B、C、…）表示扫雷区域中若干个（可以为1个或0个）小正方形组成的集合，并用|A|表示A中所含小正方形的个数（|∅|=0）。由含义可知该集合是可列且有限的。
我们接着用映射f(A)来表示集合A（即雷区A）中所包含的雷的个数。在扫雷过程
中，f(A)的值由小正方形内的数字直接给出或间接推出。下面给出f(A)的表达
式：
f(A)= 0, 当|A|=1且A中无雷时;
1, 当|A|=1且A中有雷时;
∑f(Pi)（其中{Pi}是A的一个划分且|Pi|=1）, 当|A|>1时;
0, 当A=∅时.
在上面的基础上我们不加证明的给出如下几个定理：
1.0≤f(A)≤|A|, f(A)ϵℤ.
2.若f(A)=0, 则∀P⊆A且|P|=1, f(P)=0.
该定理的另一种表述为：若f(A)=0, 则∀P⊆A, f(P)=0.
3.若f(A)=|A|, 则∀P⊆A且|P|=1, f(P)=1.
该定理的另一种表述为: 若f(A)=|A|, 则∀P⊆A, f(P)=|P|.
4.f(A∩B)=f(A)+f(B)-f(A∪B).
该定理的推广形式为：f(A1∩A2∩A3∩…∩An)=f(A1)+f(A2)+f(A3)+…+
f(An)-f(A1∪A2)-f((A1∩A2)∪A3)-f((A1∩A2∩A3)∪A4)-…-
f((A1∩A2∩…∩An-1)∪An).
5.f(AUB)=f(A)+f(B)-f(A∩B).
特别地，当A∩B=∅时, f(AUB)=f(A)+f(B).
该定理的推广形式为f(A1∪A2∪A3∪…∪An)=f(A1)+f(A2)+f(A3)+…+
f(An)-f(A1∩A2)-f((A1∪A2)∩A3)-f((A1∪A2∪A3)∩A4)-…-
f((A1∪A2∪…∪An-1)∩An).
特别地，当A1、A2、A3、…、An两两不相交时, f(A1∪A2∪A3∪…∪An)=
f(A1)+f(A2)+f(A3)+…+f(An).
6.f(A-B)=f(A)-f(A∩B).
特别地，当B⊆A时，f(A-B)=f(A)-f(B).
特别地，当B⊆A且f(A)=f(B)时，f(A-B)=0.
7.f(~A)=f(S)-f(A)（其中S是全集）.
8.若B⊆A，则max(f(A)-(|A|-|B|), 0)≤f(B)≤min(|B|, f(A) ).
PDF下载：https://pan.baidu.com/s/1ho150dQe5v7lTCOG44dVAw
|
|
