SG和的证明(Proof of SG and)

SG和的证明

原证明方法存在缺陷,这里使用另一种更完全的证明方法。
简介:主要利用SG函数和mex函数的定义和推论进行证明。

原定义有关SG和的定义不完全,这里进一步进行如下定义:
SG和的基本定义1:当对任意子游戏操作时,不对其他任意子游戏状态产生影响,即称为相互独立的子游戏。
SG和的基本定义2:整体状态\(G=<g_{k_1},g_{k_2},…,g_{k_n}>\)。
SG和的基本定义3:当子游戏\(k_i\)状态为\(g_{k_i}\)时,操作集合为\(f_{k_i}\),其后继状态集合为\(h_{k_i}\)。
SG和的基本定义4:当整体状态为\(G\)时,操作集合\(F=\cup_{i=1}^{n}{f_{k_i}}\),其后继状态集合\(H=\{h|h=<g_{k_1},g_{k_2},…,g_{k_{i-1}},h_{{k_i}j},g_{k_{i+1}},…,g_{k_n}>,h_{{k_i}j}\in h_{k_i},1\le i\le n\}\)

使用数学归纳法证明:\(SG(G)=\oplus_{i=1}^{n}{SG(g_{k_i})}\)。
显然\(\forall i,SG(g_{k_i})=0\)时\(SG(G)=\oplus_{i=1}^{n}{SG(g_{k_i})}=0\)。
假设\(SG(h)=(\oplus_{i=1}^{n}{SG(g_{k_i})})\oplus g_{k_i}\oplus h_{{k_i}j},h\in H\)。
证明\(SG(G)=\oplus_{i=1}^{n}{SG(g_{k_i})}\)成立。
1)由SG函数定义得\(SG(G)=mex(SG(H))=mex({SG(h)|h\in H})=mex({(\oplus_{i=1}^{n}{SG(g_{k_i})})\oplus g_{k_i}\oplus h_{{k_i}j}|h\in H})\)
2)由SG推论1得\((\oplus_{i=1}^{n}{SG(g_{k_i})})\oplus g_{k_i}\oplus h_{{k_i}j}\neq (\oplus_{i=1}^{n}{SG(g_{k_i})})\)
即证:\(\forall m,m<(\oplus_{i=1}^{n}{SG(g_{k_i})}),m\in N^0\),一定\(\exists i,j\),使得\((\oplus_{i=1}^{n}{SG(g_{k_i})})\oplus g_{k_i}\oplus h_{{k_i}j}=m\)。
1)由异或变换引理2得\(\exists b\in N^+\),使得\(m=(\oplus_{i=1}^{n}{SG(g_{k_i})})\oplus b\),并且\((\oplus_{i=1}^{n}{SG(g_{k_i})})\)二进制第\(u\)位一定为1。其中\(u\)为\(b\)二进制最高位所在位数。
2)可得\(\exists i,g_{k_i}\)第\(u\)位为1。\(g_{k_i}\oplus b<g_{k_i}\)。
3)由SG推论1得\(\exists j,h_{{k_i}j}=g_{k_i}\oplus b\)
4)综上得证。

————————

Proof of SG and

The original proof method has defects. Here we use another more complete proof method.
Introduction: it is mainly proved by the definition and inference of SG function and mex function.

The definition of SG and in the original definition is incomplete, and the following definitions are further defined here:
Basic definition of SG and 1: when operating any sub game, it will not affect the state of any other sub game, that is, it is called mutually independent sub game.
Basic definition 2 of SG and: overall state \ (g = & lt; G {k_1}, G {k_2},…, G {k_n} & gt; \).
Basic definition 3 of SG and: when the sub game \ (k_i \) state is \ (g_ {k_i} \), the operation set is \ (f_ {k_i} \), and its subsequent state set is \ (h_ {k_i} \).
The basic definition of SG and the basic definition 4: the basic definition 4: the basic definition 4: the basic definition 4: the basic definition 4: the basic definition 4: when the overall state is \ (g \), the operation set (F = \ cup {{{{uu{{{{{{{{i = I = 1}, the basic definition of SG and the basic definition 4: the basic definition 4: the basic definition 4: the basic definition 4: the basic definition 4: when the overall state is \ (g \ \), the operation set \ (F = \ {{{u{{i = 1}}}} {, when the overall state is \ (g \ \), the operation set (F = \ cup {{i = 1} {} {{{} {{{{{{{{{{{{\\\\\\\1 \ le I \ Le n \} \)

Use mathematical induction to prove that: \ (SG (g) = \ oplus_ {i=1}^{n}{SG(g_{k_i})}\)。
Obviously \ (\ forall I, SG (g_{k_i}) = 0 \) when \ (SG (g) = \ oplus_ {i=1}^{n}{SG(g_{k_i})}=0\)。
Suppose \ (SG (H) = (\ oplus_{I = 1} ^ {n} {SG (g_{k_i})}) \ oplus G_ {k_i}\oplus h_ {{k_i}j},h\in H\)。
Proof \ (SG (g) = \ oplus_ {I = 1} ^ {n} {SG (g_ {k_i})} \) is established.
1) Defined by SG function \ (SG (g) = mex (SG (H)) = mex ({SG (H) |h \ in H}) = mex ({(\ oplus_{I = 1} ^ {n} {SG (g_{k_i})}) \ oplus G_ {k_i}\oplus h_ {{k_i}j}|h\in H})\)
2) \ (\ oplus_{I = 1} ^ {n} {SG (g_{k_i})}) \ oplus G_ {k_i}\oplus h_ {{k_i}j}\neq (\oplus_{i=1}^{n}{SG(g_{k_i})})\)
Namely: \ (\ forall m, M & lt; (\ oplus {I = 1} ^ {n} {SG (g {K})}), m \ in n ^ 0 \), must be \ (\ exists I, J \), so that \ (\ oplus {I = 1} ^ {n} {SG (g {K})}) \ oplus G_ {k_i}\oplus h_ {{k_i}j}=m\)。
1) From XOR transformation lemma 2, \ (\ exists B \ in n ^ + \), so that \ (M = (\ oplus_{I = 1} ^ {n} {SG (g_{k_i})}) \ oplus B \), and \ ((\ oplus_{I = 1} ^ {n} {SG (g_{k_i})}) \) binary bit \ (U \) must be 1. Where \ (U \) is the digit of the highest binary bit of \ (B \).
2) The \ (U \) bit of \ (\ exists I, g_{k_i} \) is 1\ (g_{k_i}\oplus b<g_{k_i}\)。
3) Inferred from SG 1 \ (\ exists J, h_{{k_i} J} = g_{k_i} \ oplus B \)
4) To sum up, it is proved.