問題一覧 > 教育的問題

No.2090 否定論理積と充足可能性

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 105
作問者 : 👑 p-adic / テスター : taiga0629kyopro
1 ProblemId : 8441 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-30 21:04:28

問題文

入力に非負整数 A0,A1,A2,A3,A4,A5A_0,A_1,A_2,A_3,A_4,A_5 が与えられます。

　

まず記法を説明します。

ここでは PP に非負整数である添字を付けた記号で命題変数を表します。例えば P0P_0 や P3P_3 は命題変数ですが、PP や QQ や Q0Q_0 は命題変数ではありません。

(∣)(\mid) はシェファーの棒記号であり、否定論理積（NAND）を表します。

　

命題論理の論理式

(((PA0∣PA1)∣PA2)∣((PA3∣PA4)∣PA5))\displaystyle (((P_{A_0} \mid P_{A_1}) \mid P_{A_2}) \mid ((P_{A_3} \mid P_{A_4}) \mid P_{A_5}))

が充足可能か否かを判定してください。

　

以下、命題論理について詳しくない人に向けた用語の補足説明をします。（クリックで開く）

　

命題変数の真理値割り当てとは、大雑把には各非負整数 ii に対し PiP_i が真であるか偽であるかを決める対応のことです。

より形式的には非負整数全体の集合 N\mathbb{N} から{0,1}\{0,1\} への写像のことですが、その定式化に納得できる人はこの補足が不要なので大雑把な説明に留めます。

　

命題論理の論理式 FF が充足可能であるとは、FF が真になるような命題変数の真理値割り当てが存在するということです。例えば論理式

P0∧(P1∨P0)\displaystyle P_0 \land (P_1 \lor P_0)

は全ての命題変数（といっても P2P_2 以降は関係ありませんが）を真とすると論理式全体が真となるので、充足可能です。一方で論理式

P0∧(¬P0)\displaystyle P_0 \land (\neg P_0)

は充足可能ではありません。実際、P0P_0 が真である場合は ∧\land の右側にある部分論理式 ¬P0\neg P_0 が偽となってしまうため論理式全体が偽となり、P0P_0 が偽である場合も ∧\land の左側にある部分論理式 P0P_0 が偽となってしまうので論理式全体が偽となり、どう命題変数の真理値割り当てを取っても論理式全体が偽となってしまいます。

入力

入力は次の形式で標準入力から与えられます： 

A0A_0 A1A_1 A2A_2 A3A_3 A4A_4 A5A_5

11 行に A0,A1,A2,A3,A4,A5A_0,A_1,A_2,A_3,A_4,A_5 が半角空白区切りで与えられます。

制約

入力 A0,A1,A2,A3,A4,A5A_0, A_1, A_2, A_3, A_4, A_5 は以下の制約を満たします：

  • A0A_0 は 1010010^{100} 以下の非負整数
  • A1A_1 は 1010010^{100} 以下の非負整数
  • A2A_2 は 1010010^{100} 以下の非負整数
  • A3A_3 は 1010010^{100} 以下の非負整数
  • A4A_4 は 1010010^{100} 以下の非負整数
  • A5A_5 は 1010010^{100} 以下の非負整数

出力

命題論理の論理式

(((PA0∣PA1)∣PA2)∣((PA3∣PA4)∣PA5))\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

充足可能性を判定すべき論理式は

(((P0∣P1)∣P2)∣((P3∣P4)∣P5))\displaystyle (((P_0 \mid P_1) \mid P_2) \mid ((P_3 \mid P_4) \mid P_5))

です。P2P_2 を真とし残り全ての命題変数（といっても P6P_6 以降は関係ありませんが）を偽とする命題変数の真理値割り当てにおいてこの論理式全体は真となるので、この論理式は充足可能です。

サンプル2
入力
0 0 1 1 2 2
このように入力で得られる非負整数が重複することもあります。
出力
YES

充足可能性を判定すべき論理式は

(((P0∣P0)∣P1)∣((P1∣P2)∣P2))\displaystyle (((P_0 \mid P_0) \mid P_1) \mid ((P_1 \mid P_2) \mid P_2))

です。P0,P1P_0, P_1 を偽とし残り全ての命題変数（といっても P3P_3 以降は関係ありませんが）を真とする命題変数の真理値割り当てにおいてこの論理式全体は真となるので、この論理式は充足可能です。

サンプル3
入力
0 0 0 0 0 10
このように 55 より大きい値が入力されることもあります。
出力
YES

充足可能性を判定すべき論理式は

(((P0∣P0)∣P0)∣((P0∣P0)∣P10))\displaystyle (((P_0 \mid P_0) \mid P_0) \mid ((P_0 \mid P_0) \mid P_{10}))

です。P0P_0 を偽とし残り全ての命題変数（といっても P10P_{10} 以外は関係ありませんが）を真とする命題変数の真理値割り当てにおいてこの論理式全体は真となるので、この論理式は充足可能です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。