論理的同値・論理的帰結と同値類の個数

命題変数 $x_1,x_2,x_3$ だけを使う命題論理の論理式を考え、論理的に同値な論理式どうしを同一視する。
$$(x_1\wedge x_2\wedge x_3)\to \psi \text{と}\psi \to (x_1\vee x_2)$$
がともにトートロジーとなる論理式 $\psi$ の同値類の個数を求めよ。

命題変数 $x_1,x_2,x_3$ と結合子 $\wedge ,\vee$ だけを用いて作られる命題論理の論理式を考える。すなわち、各 $x_i$ は論理式であり、$\phi ,\psi$ が論理式ならば $(\phi \wedge \psi )$ と $(\phi \vee \psi )$ も論理式であり、これらの規則で作られるものだけを論理式とする（否定 $\neg$、含意 $\to$、定数 $\top ,\perp$ は用いない）。2 つの論理式は、$x_1,x_2,x_3$ へのすべての真理値割り当てで同じ真理値をとるとき同値であるという。互いに同値でない論理式は最大で何個とれるか。すなわち、同値類の個数を求めよ。

命題変数 $x_1,x_2,x_3,x_4$ だけを用いた命題論理の論理式を考える（結合子は $\neg ,\wedge ,\vee ,\to$ を用いる）。2 つの論理式は、$x_1,\dots ,x_4$ へのすべての真理値割り当て（$2^4=16$ 通り）で同じ真理値をとるとき同値であるという。また、論理式 $\phi$ に現れる $x_3$ と $x_4$ を同時に入れ替えて得られる論理式を ${\phi }^{\sigma }$ と書く。

次の 4 つの条件をすべて満たす論理式 $\phi$ を考える。

(1) $(x_1\wedge x_2)\to \phi$ はトートロジーである。

(2) $\phi \to (x_1\vee x_2\vee x_3)$ はトートロジーである。

(3) $\phi$ と ${\phi }^{\sigma }$ は同値である。

(4) $\phi$ を真にする真理値割り当て（充足割り当て）はちょうど $8$ 個である。

このような論理式 $\phi$ は、同値なものを同一視すると何個あるか。

命題変数 $x_1,x_2,\dots ,x_6$ だけを用いた命題論理の論理式を考える（結合子は $\neg ,\wedge ,\vee ,\to$ を用いる）。2 つの論理式は、$x_1,\dots ,x_6$ へのすべての真理値割り当てで同じ真理値をとるとき同値であるという。次の 2 つの論理式を定める。
$$\phi =\underset{i=1}{\overset{5}{\bigwedge }}\left(x_i\vee x_{i+1}\right),\chi =\underset{i=1}{\overset{4}{\bigwedge }}\left(x_i\vee x_{i+1}\vee x_{i+2}\right).$$
$x_1,\dots ,x_6$ だけを用いた論理式 $\psi$ であって、$\phi \to \psi$ と $\psi \to \chi$ がともにトートロジー（恒真式）であるものを考える。このような $\psi$ の、同値関係による同値類の個数を求めよ。

命題変数 $x_1,x_2,x_3,x_4$ だけを用いた命題論理の論理式を考える（結合子は $\neg ,\wedge ,\vee ,\to$ とし、定数 $\top ,\perp$ は用いない）。2 つの論理式は、$x_1,\dots ,x_4$ へのすべての真理値割り当てで同じ真理値をとるとき同値であるという。

論理式 $\phi$ に対し、$\phi$ の中の $x_i$ をすべて $\neg x_i$（$i=1,2,3,4$）に同時に置き換えた論理式を ${\phi }^{\ast }$ とする。次の 2 条件をともに満たす論理式 $\phi$ を考える。

$(1)$ $\phi$ は、結合子 $\wedge ,\vee$ と命題変数 $x_1,\dots ,x_4$ だけを用いた（$\neg ,\to$ を用いない）ある論理式と同値である。

$(2)$ $\neg \phi$ と ${\phi }^{\ast }$ は同値である。

このような論理式 $\phi$ の同値類は何個あるか。

2 項関係記号 $E$ だけからなる一階の言語（等号を含む）を考える。台集合 $A$ が空でない有限集合で、$E^{\mathcal{A}}$ が $A$ 上の同値関係であるような構造 $\mathcal{A}=(A,E^{\mathcal{A}})$ を、以下「有限同値構造」とよぶ。

論理式の量化子の深さ $\mathrm{qr}$ を次で定める。
- 原子論理式 $\phi$ に対して $\mathrm{qr}(\phi )=0$
- $\mathrm{qr}(\neg \phi )=\mathrm{qr}(\phi )$
- $\mathrm{qr}(\phi \wedge \psi )=\mathrm{qr}(\phi \vee \psi )=\mathrm{qr}(\phi \to \psi )=\max (\mathrm{qr}(\phi ),\mathrm{qr}(\psi ))$
- $\mathrm{qr}(\exists x\phi )=\mathrm{qr}(\forall x\phi )=\mathrm{qr}(\phi )+1$

2 つの構造 $\mathcal{A},\mathcal{B}$ が、$\mathrm{qr}\le 3$ のすべての閉論理式について真偽が一致するとき、$\mathcal{A}{\equiv }_3\mathcal{B}$ と書く。

すべての有限同値構造（台集合の大きさは任意）を ${\equiv }_3$ で分類したときの同値類の個数を求めよ。