数理論理学・集合論の問題

命題変数 $x_1,x_2,\dots ,x_{10}$ に関する命題論理の論理式
$$\phi =\underset{i=1}{\overset{10}{\bigwedge }}\left(\neg x_i\vee \neg x_{i+1}\right)$$
を考える。ただし添字は巡回的に読み、$x_{11}$ は $x_1$ を表すものとする（したがって $\phi$ は $10$ 個の節 $\neg x_1\vee \neg x_2,\neg x_2\vee \neg x_3,\dots ,\neg x_9\vee \neg x_{10},\neg x_{10}\vee \neg x_1$ の連言である）。

$x_1,\dots ,x_{10}$ への真理値割り当て（全部で $2^{10}$ 通り）のうち、$\phi$ を真にするものの個数を求めよ。

命題変数 $x_1,x_2,x_3,x_4,x_5$ に関する命題論理の論理式
$$\phi =(x_1\vee x_2\vee x_3)\wedge \neg (x_1\wedge x_2)\wedge (x_4\to x_1)\wedge (x_5\to x_3)$$
を考える。$x_1,\dots ,x_5$ への真理値割り当て（全部で $2^5=32$ 通り）のうち、$\phi$ を真にするものの個数を求めよ。

2 項関係記号 $D$ だけからなる言語の構造 $\mathcal{M}$ を、台集合 $M=\{1,2,3,4,5,6,7,8,9,10\}$ とし、$D$ を「割り切る」と解釈したものとする。すなわち $a,b\in M$ に対して $\mathcal{M}\models D(a,b)$ となるのは、$a$ が $b$ を割り切る（ある整数 $k$ で $b=ka$ となる）ときであり、そのときに限る。

自由変数 $x$ をもつ論理式
$$\phi (x):\forall y(D(x,y)\to y=x)$$
について、$\mathcal{M}\models \phi (a)$ となる $a\in M$ の集合を求めよ。ただし $=$ は台集合の元の等しさと解釈する。

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