幽夜默示录解析
没有爱就看不见
P1
直接构造前件为真，后件为假的情况即可。比如可令\(P(x,y)\)永真、\(Q(x,y)\)永假。
P2
构造时满足「对于任意的\(y\)」存在「不同的\(x\)」满足\(P(x, y)\)即可。比如
\[P = \left(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}\right) \]P3
注意到如下等价转换
\[\neg \exists x(\neg P(x) \land \neg Q(x)) \rightarrow \neg (\exists x (\neg P(x)) \land \exists x (\neg Q(x))) \tag 3 \\ \Leftrightarrow \exists x (\neg P(x)) \land \exists x (\neg Q(x)) \rightarrow \exists x(\neg P(x) \land \neg Q(x)) \\ \Leftrightarrow \neg \forall x P(x) \land \neg \forall x Q(x) \rightarrow \neg \forall x (P(x) \lor Q(x)) \]于是，构造并非永真的谓词\(P(x), Q(x)\)，使得\(P(x) \lor Q(x)\)永真即可。不妨采用分割的办法，把一个永真谓词「拆」成\(P(x),Q(x)\)。比如
\[P = (1, 0, 0)\\ Q = (0, 1, 1) \]P4
“哦？想不到这异世的土地上也能诞生出这么有趣的游戏呢。虽然远比不上妾身的猫箱，却也称得上让人眼前一亮。“黄金的魔女、无限的魔女贝阿朵莉切此刻正慵懒地躺在六轩岛那气派的庄园客厅里柔软舒适的沙发上。
那是一个玫瑰盛开的午后，多亏嘉音的悉心打理，园中的花朵开得灿烂极了。屋内，战人和贝阿朵正饶有兴致地看着这道来自异世的谜题。
“两个小艾咪？哈哈，真不知道你是从哪弄来的题目，我的贝阿朵。”战人笑得像个孩子。
“别忘了，妾身可是可怕的魔女呢！“贝阿朵一脸的得意。
复杂的事物往往有着极其简单的核心，这道题也不例外。解决这道题最关键的一点在于，弄清\(R(x,w)\oplus R(z,y)\)有什么性质。即然这道题只涉及主对角线，那我们首先讨论\(R(x, y)\)在主对角线上具有的性质，然后再考虑如何构造式\((4.2)\)的反例。
关于\((4.1)\)式，首先考虑对于每个\(y\)，应满足何种约束。
考虑\(y=s\)时的退化形式，如下\((4.1')\)式意味着什么
\[\exists y\exists x \forall z \forall w \big( (R(x, z) \oplus R(w, y)) \lor y=z \big) \tag {4.1'} \]分别取定\(z/w\)，枚举\(w/z\)可知，除\((x,y)\)处以外，所有的\(R(x,z), z=0, 1, 2, \cdots\)和所有的\(R(w, y), y = 0, 1, 2, \cdots\)分别相等，而\(R(x, z)\)和\(R(w, y)\)的值分别相反。于是得到：
\[R = \left(\begin{matrix} & & 0 & & \\ & & 0 & & \\ 1 & 1 & 0 & 1 & 1 \\ & & 0 & & \\ & & 0 & & \\ \end{matrix}\right) \]另一种情况省略，下同。
“十字排布？也不过如此嘛。啧，比起你的环形密室还真是差得远呢！”战人一边谢过沙音端来的咖啡，一边吮着咖啡说道。
“这才刚开始呢，可不要轻敌啊我的战人君。“无限的魔女轻声劝诫着她的爱人。不过嘛，任谁都喜欢被夸，魔女也不例外，于是本该平淡的声音里出现了一丝笑意的波澜。
我们取定\(y=s, x=t\)，这时，\((x,y)\)处的约束变为
\[\forall z \forall w \big( (R(x, z) \oplus R(w, y)) \lor y=z \lor x=w \big) \tag {4.1''} \]这导致\(R\)在\((x, y)\)处的真值可以任意指定：
\[R = \left(\begin{matrix} & & 0 & & \\ & & 0 & & \\ 1 & 1 & ? & 1 & 1 \\ & & 0 & & \\ & & 0 & & \\ \end{matrix}\right) \](i). 考虑如果还有\(x_2 \neq x\)使得\(x_2, y\)也满足\((4.1')\)式，那么：
\[R = \left(\begin{matrix} & & 0 & & \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ & & 0 & & \\ & & 0 & & \\ \end{matrix}\right) \]此时，若继续构造，使\(R\)满足\((4.1)\)式，则出现如下情况：
\[R = \left(\begin{matrix} 1 & & 0 & & \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & & 0 & & \\ \end{matrix}\right) \]无法满足\((4.1)\)式。
(ii). 接着讨论不存在上述\(x_2\)满足条件的情况。考虑如果对于某个\(y_2 \neq y\)，也有\(x_2\)满足\((4.1')\)式，可能有哪些情况：如果\(x_2 = t\)，那么
\[R = \left(\begin{matrix} 0 & & 0 & & \\ 0 & & 0 & & \\ 1 & 1 & ? & 1 & 1 \\ 0 & & 0 & & \\ 0 & & 0 & & \\ \end{matrix}\right) \]如果\(x_2 \neq t\)那么
\[R = \left(\begin{matrix} & & 0 & & 1\\ 0 & 0 & 0 & 0 & 1\\ 1 & 1 & ? & 1 & 1 \\ & & 0 & & 1\\ & & 0 & & 1\\ \end{matrix}\right) \\ \]注意到此时如果还有\(y_3 \neq y \land y_3 \neq y_2\)以及对应的\(x_3\)满足\((4.1')\)式，则必有\(x_3 = t\)，因此\(R\)中至多有一列和一排\(1\)，其余位置全\(0\)（当然，或者反过来）。
“啊唷！原来还有第二个十字啊……“样貌俊朗的公子望着眼前的推理结果露出了惊讶的表情。
“哦我的小傻瓜，妾身刚刚说什么来着？“魔女的话音带着妩媚，听得战人君不好意思地摸着后脑勺附和地笑起来。
考虑\(R\)在主对角线上的性质，显然有：\(R\)在主对角线上可以有零或一或二个1，其余全0（或反之）。显然，即使有另外一组\(s,t\)使\((4.1)\)式为真，\(R\)也仍然满足上述条件。不过似乎s和t至多只能有一组
得到\(R(x,y)\)在对角线上的性质后，我们分析式\((4.2)\)。构造辅助谓词\(Q(x) = P(x, x) \oplus R(x, x)\)，注意到如下等价关系：
\[\begin{aligned} &\forall x \forall y \big( P(x, x) \oplus R(x, x) \oplus P(y, y) \oplus R(y, y) \oplus 1 \big)\\ \Leftrightarrow & \forall x \forall y \big( Q(x) \oplus Q(y) \oplus 1 \big) \\ \Leftrightarrow & \forall x \forall y \neg \big( Q(x) \oplus Q(y) \big)\\ \Leftrightarrow & \neg \exists x \exists y \big( Q(x) \oplus Q(y) \big) \end{aligned} \tag {4.2} \]因此，只需构造\(P(x, y)\)使其对任意\(R(x, y)\)均满足\(\exists x \exists y \big(Q(x) \oplus Q(y)\big)\)即可。
考虑\(\oplus R(x, y)\)对\(P(x, x)\)的影响，由\(R(x, y)\)在主对角线上的性质可知，\(\oplus R(x, y)\)这一操作会使\(P(x, y)\)中的零或一或二个主对角线元素发生翻转或留下零或一或二个主对角线元素不发生翻转。
而要使得\(\exists x \exists y \big(Q(x) \oplus Q(y)\big)\)，就要保证翻转后的主对角线上同时有\(0\)和\(1\)。显然，这要求\(P(x, y)\)的主对角线上，\(0\)和\(1\)各至少有三个，因此最低阶数为「六」。
标签：默示录,matrix,exists,幽夜,big,forall,neg,oplus,Turorial From： https://www.cnblogs.com/fallqs/p/18221603“将军！“贝阿朵莉切满意地放下端着的咖啡，靠在了战人的肩上。战人便轻轻将身旁这位魔女搂住，二人一起享受着这午后的宁静。
忽得，一阵“哈”“哈”的怪响隔着楼板传了过来，原来是嘉音和沙音又在和真理亚小姐玩装死游戏，弄得一旁的管家源次先生也不知怎样才好了呢。
夕阳斜照，海猫群飞，六轩岛上一片祥和。
--THE END--