真理表の限界

【問】条件式が２つ（Ｐ, Ｑとする）あるとき、その真偽の組み合わせは全部で4通りあります。だから、ある論理式の真偽を判定するための表を作ると（タイトル行を除いて）4行必要です。また、その２つの原子式から作られる論理式の真偽の組み合わせは、次表のように全部で16通りあります。

　　Ｐ　Ｑ　｜　ア　イ　　　Ｐ　ウ　Ｑ　　　エ　　　　　　　　　オ　　　　　カ
　　ー　ー　┼　ー　ー　ー　ー　ー　ー　ー　ー　ー　ー　ー　ー　ー　ー　ー　ー
　　１　１　｜　１　１　１　１　１　１　１　１　０　０　０　０　０　０　０　０
　　１　０　｜　１　１　１　１　０　０　０　０　１　１　１　１　０　０　０　０
　　０　１　｜　１　１　０　０　１　１　０　０　１　１　０　０　１　１　０　０
　　０　０　｜　１　０　１　０　１　０　１　０　１　０　１　０　１　０　１　０

(1)　表中の ア , カ にあたる論理式を何というか。その名称を答えなさい。

(2)　イ , ウ , エ , オ にあたる論理式を１つずつ、Ｐ , Ｑ の両方または片方を用いて書きなさい。

(3)　授業で扱った真偽判定法は、頭からっぽで 0 と 1 を書き込むだけでいいので簡単で便利だが、弱点もある。それは原子式が多くなると、表がとても大きくなることだ。
　たとえば原子式が P , Q , R の３つある場合は行の数は（タイトル行を除いて）全部で（ ① ）行必要になり、３つの原子式から作られる論理式の真偽の組み合わせは全部で（ ② ）通りになる。
　また、原子式が P , Q , R , S , T の５つある場合は行の数は（タイトル行を除いて）全部で（ ③ ）行必要になり、５つの原子式から作られる論理式の真偽の組み合わせは全部で約（ ④ ）億通りになる。
　こうなると、とても書ききれない。ましてや「すべての x において」のようなものを扱うことはまったく不可能だ。
　ではそれらを扱うにはどうすればいいかというと、やり方をまるで変えなければならなくなる。続きは大学で、もしくは自学自習でやってください。

---

《正解例》は、次の通りです。

(1)　ア：トートロジー（恒真式）　　カ：矛盾式（恒偽式）
　　　　※ トートロジーの否定は矛盾式に、矛盾式の否定はトートロジーになる。
(2)　イ：Ｐ∨Ｑ　　ウ：Ｐ⇒Ｑ　　エ：Ｐ∧Ｑ　　オ：Ｐ（Ｐでない、Ｐの上にバーをつけて表す）
　　　　※ 複雑なものを作ろうとすれば他にも答えは無限にあるが、重要かつ頻出かつシンプルなものは上の通り。
　　　　　 表中 イ , ウ , エ , オ の値（１か０か）が「∧ , ∨ , ⇒ , バー」の定義にあたります。

(3)　①　2³ ＝ 8 　　　②　2⁸ ＝ 256 　　　③　2⁵ ＝ 32 　　　④　2³² ＝ 40 億　
　　　※　２のｎ乗の簡易計算法は こちら をどうぞ。