No.792 真理関数をつくろう

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 88
作問者 : yusukeyusuke / テスター : cielciel
0 ProblemId : 2331 / 出題時の順位表

問題文


注: この問題の出力には非Ascii文字が含まれます。
含まれる非Ascii文字は次の通りです: ∧∨¬⊥⊤

$N$個の原子式$P_1, P_2, \cdots, P_N$について、次のような真理表を考える。

$ \large \begin{array}{cccc|c} P_1 & P_2 & \cdots & P_N & A \\ \hline Q_{1,1} & Q_{1,2} & \cdots & Q_{1,N} & R_1 \\ Q_{2,1} & Q_{2,2} & \cdots & Q_{2,N} & R_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ Q_{2^N,1} & Q_{2^N,2} & \cdots & Q_{2^N, N} & R_{2^N} \end{array} $

$Q_{i,j}$は$1$または$0$であり、1なら真、0なら偽を表す。
また、$R_i$は$1$または$0$であり、同様に真偽を表す。
このとき、この真理表で表される真理関数に対して妥当な論理式$A$を出力しなさい。

入力

$N$
$Q_{1,1} \, Q_{1,2} \, \cdots \, Q_{1,N} \, R_1$
$Q_{2,1} \, Q_{2,2} \, \cdots \, Q_{2,N} \, R_2$
$\vdots$
$Q_{2^n,1} \, Q_{2^n,2} \, \cdots \, Q_{2^n,N} \, R_{2^N}$

$1 \le N \le 12$
$Q_{i,j}, R_i(1 \le i \le 2^N,\, 1 \le j \le N)$はそれぞれ$0$か$1$

出力

入力された真理関数に対して妥当な論理式$A$を出力しなさい。なお、出力の形式は次に従うこと。

  • "A=" から始める。
  • $P_i$が真の場合、$P_i$、偽の場合は$\lnot P_i$と出力しなさい。
  • すべてのiについて$P_i$は出力上で"P_i"と表される。(iが何桁であろうが、例えばi=12のときP_12と表されます
  • $R_i$が真の場合、真理表のi行目に基づいて、論理式Aに"($Q_1$∧$Q_2$∧$\cdots$∧$Q_N$)"の形式で論理式を含めなさい。
    • ただし、$P_i$が真のとき$Q_i$ は "P_i"、そうでないとき$Q_i$ は "¬P_i"を示す。
    • ここで含めた論理式を$X_1, X_2, \cdots, X_N$とすると、論理式$A$は"A=$X_1$∨$X_2$∨$\cdots$∨$X_N$"の形で表す必要があります。
    • $i > j$のとき、$X_j$は$X_i$よりも先に論理式Aに表すこと。
    • $i > j$のとき、$Q_j$は$Q_i$よりも先に論理式$X_k$に表すこと。
  • すべての$i$について$R_i$が真の場合、論理式Aは"A=⊤"と表される。(Tではない。⊤はトップと読む。)
  • すべての$i$について$R_i$が偽の場合、論理式Aは"A=⊥"と表される。(⊥は矛盾式を表す。ボトムと読む。)

サンプル

サンプル1
入力
2
1 1 0
1 0 1
0 1 1
0 0 0
出力
A=(P_1∧¬P_2)∨(¬P_1∧P_2)

この場合、$R_2$と$R_3$が真です。真理表の2行目と3行目より、$P_1$かつ$P_2$でない場合、または$P_1$でないかつ$P_2$の場合にこの真理関数は真であることを示します。

サンプル2
入力
1
0 0
1 0
出力
A=⊥

どの$i$についても$R_i$が偽ですから、出力は上の通りになります。

サンプル3
入力
2
1 1 1
1 0 1
0 1 1
0 0 1
出力
A=⊤

どの$i$についても$R_i$が真ですから、出力は上の通りになります。

サンプル4
入力
4
1 1 1 1 0
1 1 1 0 1
1 1 0 1 0
1 1 0 0 1
1 0 1 1 0
1 0 1 0 1
1 0 0 1 0
1 0 0 0 1
0 1 1 1 0
0 1 1 0 1
0 1 0 1 0
0 1 0 0 1
0 0 1 1 0
0 0 1 0 1
0 0 0 1 0
0 0 0 0 1
出力
A=(P_1∧P_2∧P_3∧¬P_4)∨(P_1∧P_2∧¬P_3∧¬P_4)∨(P_1∧¬P_2∧P_3∧¬P_4)∨(P_1∧¬P_2∧¬P_3∧¬P_4)∨(¬P_1∧P_2∧P_3∧¬P_4)∨(¬P_1∧P_2∧¬P_3∧¬P_4)∨(¬P_1∧¬P_2∧P_3∧¬P_4)∨(¬P_1∧¬P_2∧¬P_3∧¬P_4)

サンプル5
入力
2 
1 1 1 
1 0 1 
0 1 0 
0 0 0
出力
A=(P_1∧P_2)∨(P_1∧¬P_2)

$P_2$の真偽にかかわらず、$P_1$のみで真偽が決定しますが、簡略せずに出力します。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。