問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 164
作問者 : yusukeyusuke / テスター : cielciel
2 ProblemId : 2331 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-05-17 12:08:54

問題文


注: この問題の出力には非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$のみで真偽が決定しますが、簡略せずに出力します。

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