No.2090 否定論理積と充足可能性
タグ : / 解いたユーザー数 102
作問者 : 👑
p-adic
/ テスター :
taiga0629kyopro
問題文
入力に非負整数 $A_0,A_1,A_2,A_3,A_4,A_5$ が与えられます。
まず記法を説明します。
ここでは $P$ に非負整数である添字を付けた記号で命題変数を表します。例えば $P_0$ や $P_3$ は命題変数ですが、$P$ や $Q$ や $Q_0$ は命題変数ではありません。
$(\mid)$ はシェファーの棒記号であり、否定論理積（NAND）を表します。
命題論理の論理式
$\displaystyle (((P_{A_0} \mid P_{A_1}) \mid P_{A_2}) \mid ((P_{A_3} \mid P_{A_4}) \mid P_{A_5})) $
が充足可能か否かを判定してください。
以下、命題論理について詳しくない人に向けた用語の補足説明をします。（クリックで開く）
命題変数の真理値割り当てとは、大雑把には各非負整数 $i$ に対し $P_i$ が真であるか偽であるかを決める対応のことです。
より形式的には非負整数全体の集合 $\mathbb{N}$ から$\{0,1\}$ への写像のことですが、その定式化に納得できる人はこの補足が不要なので大雑把な説明に留めます。
命題論理の論理式 $F$ が充足可能であるとは、$F$ が真になるような命題変数の真理値割り当てが存在するということです。例えば論理式
$\displaystyle P_0 \land (P_1 \lor P_0) $
は全ての命題変数（といっても $P_2$ 以降は関係ありませんが）を真とすると論理式全体が真となるので、充足可能です。一方で論理式
$\displaystyle P_0 \land (\neg P_0) $
は充足可能ではありません。実際、$P_0$ が真である場合は $\land$ の右側にある部分論理式 $\neg P_0$ が偽となってしまうため論理式全体が偽となり、$P_0$ が偽である場合も $\land$ の左側にある部分論理式 $P_0$ が偽となってしまうので論理式全体が偽となり、どう命題変数の真理値割り当てを取っても論理式全体が偽となってしまいます。
入力
入力は次の形式で標準入力から与えられます：
$A_0$ $A_1$ $A_2$ $A_3$ $A_4$ $A_5$
$1$ 行に $A_0,A_1,A_2,A_3,A_4,A_5$ が半角空白区切りで与えられます。
制約
入力 $A_0, A_1, A_2, A_3, A_4, A_5$ は以下の制約を満たします：
- $A_0$ は $10^{100}$ 以下の非負整数
- $A_1$ は $10^{100}$ 以下の非負整数
- $A_2$ は $10^{100}$ 以下の非負整数
- $A_3$ は $10^{100}$ 以下の非負整数
- $A_4$ は $10^{100}$ 以下の非負整数
- $A_5$ は $10^{100}$ 以下の非負整数
出力
命題論理の論理式
$\displaystyle (((P_{A_0} \mid P_{A_1}) \mid P_{A_2}) \mid ((P_{A_3} \mid P_{A_4}) \mid P_{A_5})) $
が充足可能ならばYES、充足可能でないならばNOと出力してください。
最後に改行してください。
サンプル
サンプル1
入力
0 1 2 3 4 5
出力
YES
充足可能性を判定すべき論理式は
$\displaystyle (((P_0 \mid P_1) \mid P_2) \mid ((P_3 \mid P_4) \mid P_5)) $
です。$P_2$ を真とし残り全ての命題変数（といっても $P_6$ 以降は関係ありませんが）を偽とする命題変数の真理値割り当てにおいてこの論理式全体は真となるので、この論理式は充足可能です。
サンプル2
入力
0 0 1 1 2 2このように入力で得られる非負整数が重複することもあります。
出力
YES
充足可能性を判定すべき論理式は
$\displaystyle (((P_0 \mid P_0) \mid P_1) \mid ((P_1 \mid P_2) \mid P_2)) $
です。$P_0, P_1$ を偽とし残り全ての命題変数（といっても $P_3$ 以降は関係ありませんが）を真とする命題変数の真理値割り当てにおいてこの論理式全体は真となるので、この論理式は充足可能です。
サンプル3
入力
0 0 0 0 0 10このように $5$ より大きい値が入力されることもあります。
出力
YES
充足可能性を判定すべき論理式は
$\displaystyle (((P_0 \mid P_0) \mid P_0) \mid ((P_0 \mid P_0) \mid P_{10})) $
です。$P_0$ を偽とし残り全ての命題変数（といっても $P_{10}$ 以外は関係ありませんが）を真とする命題変数の真理値割り当てにおいてこの論理式全体は真となるので、この論理式は充足可能です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。