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

命題変数 $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$ を真にするものの個数を求めよ。

命題変数 $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$ の、同値関係による同値類の個数を求めよ。

自然数全体を $\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とし、$p_i$ を $i$ 番目の素数とする（$p_0=2,p_1=3,p_2=5,\dots$）。有限列 $(a_0,a_1,\dots ,a_{k-1})\in {\mathbb{N}}^k$ のゲーデル数を
$$⟨a_0,a_1,\dots ,a_{k-1}⟩=\prod _{i=0}^{k-1}{p}_i^{a_i+1}$$
で定める（空列のゲーデル数は $1$ とする）。

関数 $F:\mathbb{N}\to \mathbb{N}$ を
$$F(0)=1,F(1)=1,F(n+2)=F(n+1)+2F(n)(n\in \mathbb{N})$$
で定め、その累積値関数（course-of-values function）$\overline{F}:\mathbb{N}\to \mathbb{N}$ を
$$\overline{F}(n)=⟨F(0),F(1),\dots ,F(n-1)⟩$$
で定める。自然数 $\overline{F}(5)$ の正の約数の個数を求めよ。

命題変数 $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$ へのすべての真理値割り当てで同じ真理値をとるとき同値であるという。互いに同値でない論理式は最大で何個とれるか。すなわち、同値類の個数を求めよ。