No.2121 帰属関係と充足可能性
タグ : / 解いたユーザー数 29
作問者 : 👑
p-adic
/ テスター :
遭難者
問題文
入力に $5$ 以下の非負整数 $N$ と $2$ 以下の非負整数 $A_0, A_1, A_2, A_3, A_4, A_5$ が与えられます。
ここでは $x$ に非負整数である添字を付けた記号で集合変数を表すことにします。
例えば $x_0$ や $x_3$ は集合変数ですが、 $x$ や $y$ や $y_0$ は集合変数ではありません。
まずは記法の確認です。各非負整数 $n$ に対し、有限集合 $V_n$ は以下のように再帰的に定義されます：
- $n = 0$ ならば、$V_n$ は空集合である。
- $n > 0$ ならば、$V_n$ は $V_{n-1}$ の冪集合、つまり $V_{n-1}$ の部分集合全体の集合である。
集合論の論理式
$\displaystyle ((((\forall x_3((x_3 \in x_{A_0}) \to (x_3 \in x_{A_1}))) \land (x_{A_1} \in x_{A_2})) \land (x_{A_3} \in x_{A_2})) \land (x_{A_4} \in x_{A_2})) \land (x_{A_5} \in x_{A_0}) $
が $V_N$ で充足可能か否か、つまり論理式
$\displaystyle ((((\forall x_3 \in V_N((x_3 \in m_{A_0}) \to (x_3 \in m_{A_1}))) \land (m_{A_1} \in m_{A_2})) \land (m_{A_3} \in m_{A_2})) \land (m_{A_4} \in m_{A_2})) \land (m_{A_5} \in m_{A_0}) $
が真であるような $V_N$ の要素 $m_0, m_1, m_2$ の組み合わせ $(m_0,m_1,m_2)$ が存在するか否かを判定してください。
ただし $m_3$ と $m_{A_3}$ を混同しないように気をつけてください。
以下、$\forall$ について詳しくない人向けの解説をします。（クリックで開く）
何らかの論理式 $P$ が与えられた時、論理式 $\forall x_3(P)$ は日本語では
- 任意の $x_3$ に対し、$P$ である。
- いかなる $x_3$ に対しても、$P$ である。
などのように読まれます。つまりどのように $x_3$ を選んだとしても $P$ が常に成り立つということですね。例えば $\forall x_3(x_3 = x_3)$ は
- 任意の $x_3$ に対し、$x_3 = x_3$ である。
- いかなる $x_3$ に対しても、$x_3 = x_3$ である。
などのように読まれます。
更に何らかの集合 $M$ が与えられた時、$x_3$ の動く範囲を $M$ に制限したい場合は、$\forall x_3 \in M(P)$ のように書きます。これは日本語だと
- $M$ の任意の要素 $x_3$ に対し、$P$ である。
- $M$ に属す任意の $x_3$ に対し、$P$ である。
- $M$ のいかなる要素 $x_3$ に対しても、$P$ である。
- $M$ に属すいかなる $x_3$ に対しても、$P$ である。
などのように読まれます。なお $\forall x_3 \in M(P)$ という表記は実際には $\forall x_3(x_3 \in M \to P)$ の糖衣構文ですので、その定義に則って
- 任意の要素 $x_3$ に対し、$x \in M$ ならば $P$ である。
- いかなる $x_3$ に対しても、$x \in M$ ならば $P$ である。
などのように読んでも構いません。今回は $M$ として $V_N$ を考えており、$\forall x_3 \in V_N(P)$ という形の論理式を扱っています。
入力
入力は次の形式で標準入力から与えられます：
$N$ $A_0$ $A_1$ $A_2$ $A_3$ $A_4$ $A_5$
$1$ 行目に $N$ が与えられ、$2$ 行目に $A_0, A_1, A_2, A_3, A_4, A_5$ が半角空白区切りで与えられます。
制約
入力 $N, A_0, A_1, A_2, A_3, A_4, A_5$ は以下の制約を満たします：
- $N$ は $5$ 以下の非負整数
- $A_0$ は $2$ 以下の非負整数
- $A_1$ は $2$ 以下の非負整数
- $A_2$ は $2$ 以下の非負整数
- $A_3$ は $2$ 以下の非負整数
- $A_4$ は $2$ 以下の非負整数
- $A_5$ は $2$ 以下の非負整数
出力
集合論の論理式
$\displaystyle ((((\forall x_3((x_3 \in x_{A_0}) \to (x_3 \in x_{A_1}))) \land (x_{A_1} \in x_{A_2})) \land (x_{A_3} \in x_{A_2})) \land (x_{A_4} \in x_{A_2})) \land (x_{A_5} \in x_{A_0}) $
が $V_N$ で充足可能であるならばYESを、充足可能でない場合はNOを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 0 0 0 0 0 0
出力
NO
今回は $x_{A_0},x_{A_1},x_{A_2},x_{A_3},x_{A_4},x_{A_5}$ が全て $x_0$ なので、充足可能性を判定すべき論理式は
$\displaystyle ((((\forall x_3((x_3 \in x_0) \to (x_3 \in x_0))) \land (x_0 \in x_0)) \land (x_0 \in x_0)) \land (x_0 \in x_0)) \land (x_0 \in x_0) $
です。そして $N = 1$ であるので、$V_1 = \{\{\}\}$ での充足可能性を考える必要があります。$V_1$ は $\{\}$ 以外に要素を持たないので、可能な $m_0,m_1,m_2$ 全てを $\{\}$ と定める以外の選び方がありません。しかしこの選び方に対応する論理式
$\displaystyle ((((\forall x_3 \in V_1((x_3 \in \{\}) \to (x_3 \in \{\}))) \land (\{\} \in \{\})) \land (\{\} \in \{\})) \land (\{\} \in \{\})) \land (\{\} \in \{\}) $
は $1$ つ目の $\land$ の右側の部分論理式 $\{\} \in \{\}$ が偽であるため、全体としても偽となります。従って与えられた論理式は $V_N$ で充足可能ではありません。
サンプル2
入力
3 0 0 1 0 0 2
出力
YES
今回は $x_{A_0},x_{A_1},x_{A_3},x_{A_4}$ が $x_0$ で $x_{A_2}$ が $x_1$ で $x_{A_5}$ が $x_2$ なので充足可能性を判定すべき論理式は
$\displaystyle ((((\forall x_3((x_3 \in x_0) \to (x_3 \in x_0))) \land (x_0 \in x_1)) \land (x_0 \in x_1)) \land (x_0 \in x_1)) \land (x_2 \in x_0) $
です。そして $N = 3$ であるので、$V_3$ での充足可能性を考える必要があります。そのためには $V_3$ にどのような要素が存在するかを考えなければなりません。
まず $V_2 = \{\{\},\{\{\}\}\}$ であったので、
$\displaystyle \begin{array}{rcl} \displaystyle \{\} &\displaystyle \subset &\displaystyle V_2 \\ \displaystyle \{\{\}\} &\displaystyle \subset &\displaystyle V_2 \\ \displaystyle \{\{\},\{\{\}\}\} &\displaystyle \subset &\displaystyle V_2 \\ \end{array} $
となります。従って $V_3$ の定義から $\{\}$ と $\{\{\}\}$ と $\{\{\},\{\{\}\}\}$ がいずれも $V_3$ の要素であることが分かりました。そこで例えば $m_0$ を $V_3$ の要素 $\{\{\}\}$ と定め、$m_1$ を $V_3$ の要素 $\{\{\},\{\{\}\}\}$ と定め、$m_2$ を $V_3$ の要素 $\{\}$ と定めると、対応する論理式
$\displaystyle ((((\forall x_3 \in V_3((x_3 \in \{\{\}\}) \to (x_3 \in \{\{\}\}))) \land (\{\{\}\} \in \{\{\},\{\{\}\}\})) \land (\{\{\}\} \in \{\{\},\{\{\}\}\})) \land (\{\{\}\} \in \{\{\},\{\{\}\}\})) \land (\{\} \in \{\{\}\}) $
は真となります。実際、$4$ つの $\land$ の右側にある論理式 $\{\} \in \{\{\}\}$ や $(\{\{\}\} \in \{\{\},\{\{\}\}\})$ は真ですので $1$ つ目の $\land$ の左側にある論理式
$\displaystyle \forall x_3 \in V_3((x_3 \in \{\{\}\}) \to (x_3 \in \{\{\}\})) $
が真であることを確認すれば良いです。$\forall x_3 \in V_3$ の適用範囲内の論理式
$\displaystyle (x_3 \in \{\{\}\}) \to (x_3 \in \{\{\}\}) $
は前件（「ならば」の左側の論理式）と後件（「ならば」の右側の論理式）が等しいので、$x_3$ をどう選んでも真となります。特にそれに $\forall x_3 \in V_N$ を適用した論理式も真であることが分かりました。従って与えられた論理式は $V_N$ で充足可能です。
サンプル3
入力
0 0 0 1 0 0 2
出力
NO
今回もサンプル2と同じく $x_{A_0},x_{A_1},x_{A_3},x_{A_4}$ が $x_0$ で $x_{A_2}$ が $x_1$ で $x_{A_5}$ が $x_2$ なので充足可能性を判定すべき論理式は
$\displaystyle ((((\forall x_3((x_3 \in x_0) \to (x_3 \in x_0))) \land (x_0 \in x_1)) \land (x_0 \in x_1)) \land (x_0 \in x_1)) \land (x_2 \in x_0) $
です。そして $N = 0$ であるので、$V_0 = \{\}$ での充足可能性を考える必要があります。しかし $\{\}$ は要素を持たないので、その要素 $3$ 個 $m_0,m_1,m_2$ の組み合わせ $(m_0,m_1,m_2)$ が存在しません。従って与えられた論理式は $V_N$ で充足可能ではありません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。