真理値表と充足割り当ての個数

命題変数 $p,q,r$ に真（$\mathrm{T}$）または偽（$\mathrm{F}$）を割り当てる $2^3=8$ 通りの割り当てのうち、論理式
$$(p\vee q)\to (q\leftrightarrow r)$$
を真にするものは何通りあるか。ただし、結合子 $\vee ,\to ,\leftrightarrow$ は通常の真理値表で解釈する（$A\to B$ は $A$ が真で $B$ が偽のときだけ偽、$A\leftrightarrow B$ は $A$ と $B$ の真理値が等しいときだけ真）。

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

$n\ge 2$ を整数とし、命題変数 $p_1,p_2,\dots ,p_n$ に対して論理式
$${\psi }_n=\underset{i=1}{\overset{n-1}{\bigwedge }}\neg (p_i\wedge p_{i+1})=\neg (p_1\wedge p_2)\wedge \neg (p_2\wedge p_3)\wedge \cdots \wedge \neg (p_{n-1}\wedge p_n)$$
を考える。真理値割り当て $v:\{p_1,\dots ,p_n\}\to \{\mathrm{T},\mathrm{F}\}$（全部で $2^n$ 個）のうち ${\psi }_n$ を真にするものの個数を $s_n$ とする。

フィボナッチ数を $F_1=F_2=1$, $F_{m+2}=F_{m+1}+F_m$ $(m\ge 1)$ で定めるとき、すべての整数 $n\ge 2$ について $s_n=F_{n+2}$ であることを証明せよ。

命題変数 $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$ の同値類は何個あるか。