述語論理における論理式の解釈
命題論理の基本単位は\(0\)または\(1\)を値としてとり得る命題変数\(P,Q,\cdots \)です。命題論理では命題変数に論理演算子を作用させることで論理式を得ますが、論理式の値を確定するためにはそこに含まれる個々の命題変数に\(1\)または\(0\)の値を代入する必要があります。論理式に含まれる命題変数の値の組み合わせをその論理式の解釈と呼びます。論理式の値を特定するためにはそれに対して何らかの解釈を与える必要があります。
一方、述語論理の基本単位は様々な値を取り得る変数\(x_{1},\cdots ,x_{n}\)に関する命題関数\(P\left( x_{1},\cdots ,x_{n}\right) \)です。命題関数もまた\(1\)または\(0\)を値としてとりますが、その値を特定するためには以下の3つの要素\begin{eqnarray*} &&\left( a\right) \ \text{議論領域}D \\
&&\left( b\right) \ \text{関数}P\text{が定める条件} \\
&&\left( c\right) \ \text{変数}x_{1},\cdots ,x_{n}\text{に代入する値}\overline{x}_{1},\cdots ,\overline{x}_{n}
\end{eqnarray*}を具体的に指定する必要があります。これが述語論理における命題関数の解釈です。
例（命題関数の解釈）
変数\(x\in X\)に関する命題関数\(P\left( x\right) \)が与えられているものとします。以下の解釈\begin{eqnarray*} &&\left( a\right) \ X\text{はすべての自然数からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x^{2}\geq 1 \\
&&\left( c\right) \ x=1
\end{eqnarray*}から以下の命題\begin{equation*}
P\left( 1\right) :1^{2}\geq 1
\end{equation*}が得られます。別の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての実数からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x^{2}\geq 1 \\
&&\left( c\right) \ x=\frac{1}{2}
\end{eqnarray*}から以下の命題\begin{equation*}
P\left( \frac{1}{2}\right) :\left( \frac{1}{2}\right) ^{2}\geq 1
\end{equation*}が得られます。これは偽です。さらに別の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての都道府県からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x\text{の人口は}800\text{万人以上} \\
&&\left( c\right) \ x=\text{東京}
\end{eqnarray*}から以下の命題\begin{equation*}
P\left( \text{東京}\right) :\text{東京の人口は}800\text{万人以上}
\end{equation*}が得られますが、これは真です。
&&\left( b\right) \ P\left( x\right) :x^{2}\geq 1 \\
&&\left( c\right) \ x=1
\end{eqnarray*}から以下の命題\begin{equation*}
P\left( 1\right) :1^{2}\geq 1
\end{equation*}が得られます。別の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての実数からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x^{2}\geq 1 \\
&&\left( c\right) \ x=\frac{1}{2}
\end{eqnarray*}から以下の命題\begin{equation*}
P\left( \frac{1}{2}\right) :\left( \frac{1}{2}\right) ^{2}\geq 1
\end{equation*}が得られます。これは偽です。さらに別の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての都道府県からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x\text{の人口は}800\text{万人以上} \\
&&\left( c\right) \ x=\text{東京}
\end{eqnarray*}から以下の命題\begin{equation*}
P\left( \text{東京}\right) :\text{東京の人口は}800\text{万人以上}
\end{equation*}が得られますが、これは真です。
述語論理では命題関数を含む原子論理式に論理演算子や量化記号を作用させることで論理式を得ます。論理式は変数の自由な現れを持つ開論理式と、変数の自由な現れを持たない閉論理式とに分類されます。論理式\(A\)が変数の自由な現れを持たない閉論理式である場合、その値を特定するためには以下の2つの要素\begin{eqnarray*} &&\left( a\right) \ \text{議論領域}D \\
&&\left( b\right) \ \text{論理式}A\text{を構成するすべての命題関数が定める条件}
\end{eqnarray*}を具体的に指定する必要があります。以上が述語論理における閉論理式の解釈です。
例（閉論理式の解釈）
変数\(x\in X\)に関する命題関数\(P\left( x\right) \)に関する以下の論理式\begin{equation*} \forall x\in X:P\left( x\right)
\end{equation*}は変数の自由な現れを持たないため、これは閉論理式です。以下の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての実数からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x^{2}\geq 0
\end{eqnarray*}から以下の命題\begin{equation*}
\text{任意の実数}x\text{について}x^{2}\geq 0\text{が成り立つ}
\end{equation*}が得られますが、これは真です。別の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての実数からなる集合} \\
&&\left( b\right) \ P\left( x\right) :\left\vert x\right\vert >0
\end{eqnarray*}から以下の命題\begin{equation*}
\text{任意の実数}x\text{について}\left\vert x\right\vert >0\text{が成り立つ}
\end{equation*}が得られますが、これは偽です。さらに別の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての都道府県からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x\text{の人口は}800\text{万人以上}
\end{eqnarray*}から以下の命題\begin{equation*}
\text{すべての都道府県の人口は}800\text{万人以上である}
\end{equation*}が得られますが、これは偽です。
\end{equation*}は変数の自由な現れを持たないため、これは閉論理式です。以下の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての実数からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x^{2}\geq 0
\end{eqnarray*}から以下の命題\begin{equation*}
\text{任意の実数}x\text{について}x^{2}\geq 0\text{が成り立つ}
\end{equation*}が得られますが、これは真です。別の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての実数からなる集合} \\
&&\left( b\right) \ P\left( x\right) :\left\vert x\right\vert >0
\end{eqnarray*}から以下の命題\begin{equation*}
\text{任意の実数}x\text{について}\left\vert x\right\vert >0\text{が成り立つ}
\end{equation*}が得られますが、これは偽です。さらに別の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての都道府県からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x\text{の人口は}800\text{万人以上}
\end{eqnarray*}から以下の命題\begin{equation*}
\text{すべての都道府県の人口は}800\text{万人以上である}
\end{equation*}が得られますが、これは偽です。
論理式\(A\)が変数\(x_{1},\cdots ,x_{n}\)の自由な現れを持つ開論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)である場合、その値を特定するためには以下の3つの要素\begin{eqnarray*} &&\left( a\right) \ \text{議論領域}D \\
&&\left( b\right) \ \text{論理式}A\text{を構成するすべての命題関数が定める条件} \\
&&\left( c\right) \ \text{変数の自由な現れに代入する値}\overline{x}_{1},\cdots ,\overline{x}_{n}
\end{eqnarray*}を具体的に指定する必要があります。以上が述語論理における開論理式の解釈です。
例（開論理式の解釈）
変数\(x\in X\)と\(y\in Y\)に関する命題関数\(P\left( x,y\right) \)に関する以下の論理式\begin{equation*} \exists x\in X:P\left( x,y\right)
\end{equation*}は変数\(y\)の自由な現れを持つため、これは開論理式です。以下の解釈\begin{eqnarray*} &&\left( a\right) \ X,Y\text{はすべての実数からなる集合} \\
&&\left( b\right) \ P\left( x,y\right) :x^{2}=y \\
&&\left( c\right) \ y=2
\end{eqnarray*}から以下の命題\begin{equation*}
x^{2}=2\text{を満たす実数}x\text{が存在する}
\end{equation*}が得られますが、これは真です。別の解釈\begin{eqnarray*}
&&\left( a\right) \ X,Y\text{はすべての実数からなる集合} \\
&&\left( b\right) \ P\left( x,y\right) :x^{2}=y \\
&&\left( c\right) \ y=-1
\end{eqnarray*}から以下の命題\begin{equation*}
x^{2}=-1\text{を満たす実数}x\text{が存在する}
\end{equation*}が得られますが、これは偽です。さらに別の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{は都道府県の集合、}Y\text{はすべての自然数の集合} \\
&&\left( b\right) \ P\left( x,y\right) :x\text{の人口は}y\text{以上} \\
&&\left( c\right) \ y=800\text{万}
\end{eqnarray*}から以下の命題\begin{equation*}
\text{人口が}800\text{万人以上の都道府県が存在する}
\end{equation*}が得られますが、これは真です。
\end{equation*}は変数\(y\)の自由な現れを持つため、これは開論理式です。以下の解釈\begin{eqnarray*} &&\left( a\right) \ X,Y\text{はすべての実数からなる集合} \\
&&\left( b\right) \ P\left( x,y\right) :x^{2}=y \\
&&\left( c\right) \ y=2
\end{eqnarray*}から以下の命題\begin{equation*}
x^{2}=2\text{を満たす実数}x\text{が存在する}
\end{equation*}が得られますが、これは真です。別の解釈\begin{eqnarray*}
&&\left( a\right) \ X,Y\text{はすべての実数からなる集合} \\
&&\left( b\right) \ P\left( x,y\right) :x^{2}=y \\
&&\left( c\right) \ y=-1
\end{eqnarray*}から以下の命題\begin{equation*}
x^{2}=-1\text{を満たす実数}x\text{が存在する}
\end{equation*}が得られますが、これは偽です。さらに別の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{は都道府県の集合、}Y\text{はすべての自然数の集合} \\
&&\left( b\right) \ P\left( x,y\right) :x\text{の人口は}y\text{以上} \\
&&\left( c\right) \ y=800\text{万}
\end{eqnarray*}から以下の命題\begin{equation*}
\text{人口が}800\text{万人以上の都道府県が存在する}
\end{equation*}が得られますが、これは真です。
論理式の解釈の応用
日常言語を使って表現された問題をあえて論理式に翻訳した上で、それを解釈すれば、もとの問題を解く助けになります。例を挙げます。
例（論理式の解釈の応用）
セールスマンが以下のように発言しました。「20代または30代でこの商品を購入した方々は全員、この商品を高く評価しています。残念ながら、この商品を高く評価していない方もいます。ただ、他の世代の方もこの商品を購入していることは確かです。」この発言には論理的な嘘が含まれている可能性がありますが、それはどのような嘘でしょうか。変数\(x\)の定義域\(X \)をすべての人からなる集合と定めた上で、以下の命題関数\begin{eqnarray*} P\left( x\right) &:&x\text{は20代である} \\
Q\left( x\right) &:&x\text{は30代である} \\
R\left( x\right) &:&x\text{は商品購入者である} \\
S\left( x\right) &:&x\text{は商品を高く評価している}
\end{eqnarray*}をそれぞれ導入します。このとき、「20代または30代でこの商品を購入した方々は全員、商品を高く評価している」という主張は以下の論理式\begin{equation}
\forall x\in X:\left( \left( \left( P\left( x\right) \vee Q\left( x\right)
\right) \wedge R\left( x\right) \right) \rightarrow S\left( x\right) \right)
\quad \cdots (1)
\end{equation}として定式化され、「この商品を高く評価していない方もいる」という主張は以下の論理式\begin{equation}
\exists x\in X:\lnot S\left( x\right) \quad \cdots (2)
\end{equation}として定式化され、「他の世代の方もこの商品を購入している」という主張は以下の論理式\begin{equation}
\exists x\in X:\left( \lnot P\left( x\right) \wedge \lnot Q\left( x\right)
\wedge R\left( x\right) \right) \quad \cdots (3)
\end{equation}として定式化されます。実態として、商品を購入しているのは20代または30代の人だけで、購入者はいずれも商品を高く評価しているものとします。ただ、20代または30代の中には商品を購入していない人がおり、その人は商品を高く評価しようがありません。このような解釈において、\(\left( 1\right) \)と\(\left( 2\right) \)は真である一方、\(\left( 3\right) \)は偽となります。
Q\left( x\right) &:&x\text{は30代である} \\
R\left( x\right) &:&x\text{は商品購入者である} \\
S\left( x\right) &:&x\text{は商品を高く評価している}
\end{eqnarray*}をそれぞれ導入します。このとき、「20代または30代でこの商品を購入した方々は全員、商品を高く評価している」という主張は以下の論理式\begin{equation}
\forall x\in X:\left( \left( \left( P\left( x\right) \vee Q\left( x\right)
\right) \wedge R\left( x\right) \right) \rightarrow S\left( x\right) \right)
\quad \cdots (1)
\end{equation}として定式化され、「この商品を高く評価していない方もいる」という主張は以下の論理式\begin{equation}
\exists x\in X:\lnot S\left( x\right) \quad \cdots (2)
\end{equation}として定式化され、「他の世代の方もこの商品を購入している」という主張は以下の論理式\begin{equation}
\exists x\in X:\left( \lnot P\left( x\right) \wedge \lnot Q\left( x\right)
\wedge R\left( x\right) \right) \quad \cdots (3)
\end{equation}として定式化されます。実態として、商品を購入しているのは20代または30代の人だけで、購入者はいずれも商品を高く評価しているものとします。ただ、20代または30代の中には商品を購入していない人がおり、その人は商品を高く評価しようがありません。このような解釈において、\(\left( 1\right) \)と\(\left( 2\right) \)は真である一方、\(\left( 3\right) \)は偽となります。
例（論理式の解釈の応用）
信号機の回路を設計します。時間\(t\)を変数とし、それを離散的\(0,1,2,3,\cdots \)なものとして扱います。その上で以下の命題関数\begin{eqnarray*} B\left( t\right) &:&\text{時点}t\text{において信号は青である} \\
Y\left( t\right) &:&\text{時点}t\text{において信号は黄色である} \\
R\left( t\right) &:&\text{時点}t\text{において信号は赤である}
\end{eqnarray*}を定義します。まず、それぞれの時点\(t\)において信号の色が青、黄色、赤のいずれかであることを論理式として定式化すると、\begin{equation*} \left( B\left( t\right) \Leftrightarrow \left( \lnot Y\left( t\right) \wedge
\lnot R\left( t\right) \right) \right) \wedge \left( Y\left( t\right)
\Leftrightarrow \left( \lnot B\left( t\right) \wedge \lnot R\left( t\right)
\right) \right) \wedge \left( R\left( t\right) \Leftrightarrow \left( \lnot
B\left( t\right) \wedge \lnot Y\left( t\right) \right) \right)
\end{equation*}となります。また、それぞれの時点\(t\)において、信号の色は変わるとは限らないが、変わる場合には青から黄色、黄色から赤、赤から青へ変わることを論理式として定式化すると、\begin{eqnarray*} B\left( t-1\right) &\Rightarrow &B\left( t\right) \vee Y\left( t\right) \\
Y\left( t-1\right) &\Rightarrow &Y\left( t\right) \vee R\left( t\right) \\
R\left( t-1\right) &\Rightarrow &R\left( t\right) \vee B\left( t\right)
\end{eqnarray*}となります。また、信号が青または赤であり続ける時間は最大\(2\)単位時間であり、信号が黄色であり続ける時間は最大\(1\)単位時間であることを論理式として表現すると、\begin{eqnarray*} B\left( t-2\right) \wedge B\left( t-1\right) &\Rightarrow &\lnot B\left(
t\right) \\
Y\left( t-1\right) &\Rightarrow &\lnot Y\left( t\right) \\
R\left( t-2\right) \wedge R\left( t-1\right) &\Rightarrow &\lnot R\left(
t\right)
\end{eqnarray*}となります。
Y\left( t\right) &:&\text{時点}t\text{において信号は黄色である} \\
R\left( t\right) &:&\text{時点}t\text{において信号は赤である}
\end{eqnarray*}を定義します。まず、それぞれの時点\(t\)において信号の色が青、黄色、赤のいずれかであることを論理式として定式化すると、\begin{equation*} \left( B\left( t\right) \Leftrightarrow \left( \lnot Y\left( t\right) \wedge
\lnot R\left( t\right) \right) \right) \wedge \left( Y\left( t\right)
\Leftrightarrow \left( \lnot B\left( t\right) \wedge \lnot R\left( t\right)
\right) \right) \wedge \left( R\left( t\right) \Leftrightarrow \left( \lnot
B\left( t\right) \wedge \lnot Y\left( t\right) \right) \right)
\end{equation*}となります。また、それぞれの時点\(t\)において、信号の色は変わるとは限らないが、変わる場合には青から黄色、黄色から赤、赤から青へ変わることを論理式として定式化すると、\begin{eqnarray*} B\left( t-1\right) &\Rightarrow &B\left( t\right) \vee Y\left( t\right) \\
Y\left( t-1\right) &\Rightarrow &Y\left( t\right) \vee R\left( t\right) \\
R\left( t-1\right) &\Rightarrow &R\left( t\right) \vee B\left( t\right)
\end{eqnarray*}となります。また、信号が青または赤であり続ける時間は最大\(2\)単位時間であり、信号が黄色であり続ける時間は最大\(1\)単位時間であることを論理式として表現すると、\begin{eqnarray*} B\left( t-2\right) \wedge B\left( t-1\right) &\Rightarrow &\lnot B\left(
t\right) \\
Y\left( t-1\right) &\Rightarrow &\lnot Y\left( t\right) \\
R\left( t-2\right) \wedge R\left( t-1\right) &\Rightarrow &\lnot R\left(
t\right)
\end{eqnarray*}となります。
演習問題
問題（論理式の解釈）
以下の論理式\begin{equation*}
P\left( x\right)
\end{equation*}に対して、以下の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての自然数からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x^{2}>x+3 \\
&&\left( c\right) \ x=2
\end{eqnarray*}を与えることにより得られる命題の真偽を判定してください。
P\left( x\right)
\end{equation*}に対して、以下の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての自然数からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x^{2}>x+3 \\
&&\left( c\right) \ x=2
\end{eqnarray*}を与えることにより得られる命題の真偽を判定してください。
問題（論理式の解釈）
以下の論理式\begin{equation*}
\forall x\in X:P\left( x\right)
\end{equation*}に対して、以下の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての実数からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x^{2}+1>0
\end{eqnarray*}を与えることにより得られる命題の真偽を判定してください。
\forall x\in X:P\left( x\right)
\end{equation*}に対して、以下の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての実数からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x^{2}+1>0
\end{eqnarray*}を与えることにより得られる命題の真偽を判定してください。
問題（論理式の解釈）
以下の論理式\begin{equation*}
\exists x\in X:P\left( x\right) \wedge Q\left( x\right)
\end{equation*}に対して、以下の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての整数からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x\leq 5 \\
&&\left( c\right) \ Q\left( x\right) :x\geq 8
\end{eqnarray*}を与えることにより得られる命題の真偽を判定してください。
\exists x\in X:P\left( x\right) \wedge Q\left( x\right)
\end{equation*}に対して、以下の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての整数からなる集合} \\
&&\left( b\right) \ P\left( x\right) :x\leq 5 \\
&&\left( c\right) \ Q\left( x\right) :x\geq 8
\end{eqnarray*}を与えることにより得られる命題の真偽を判定してください。
問題（論理式の解釈）
以下の論理式\begin{equation*}
\exists x\in X,\ \forall y\in X:P\left( x,y\right)
\end{equation*}に対して、以下の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての動物からなる集合} \\
&&\left( b\right) \ P\left( x,y\right) :x\text{は}y\text{を食べる}
\end{eqnarray*}を与えることにより得られる命題を日常語で表現してください。
\exists x\in X,\ \forall y\in X:P\left( x,y\right)
\end{equation*}に対して、以下の解釈\begin{eqnarray*}
&&\left( a\right) \ X\text{はすべての動物からなる集合} \\
&&\left( b\right) \ P\left( x,y\right) :x\text{は}y\text{を食べる}
\end{eqnarray*}を与えることにより得られる命題を日常語で表現してください。
問題（論理式の解釈）
以下の論理式
\begin{equation*}
\forall x\in X,\ \exists y\in X:x<y
\end{equation*}について、次の2つの解釈のもとで得られる命題の真偽をそれぞれ判定してください。
\begin{equation*}
\forall x\in X,\ \exists y\in X:x<y
\end{equation*}について、次の2つの解釈のもとで得られる命題の真偽をそれぞれ判定してください。
- \(X\)はすべての自然数からなる集合である。
- \(X=\left\{ 1,2,3,4\right\} \)である。
問題（開論理式の解釈）
変数\(x,y\)の定義域を、\begin{equation*} X=\left\{ 1,2,3,4,5,6\right\}
\end{equation*}とし、命題関数を、
\begin{equation*}
P\left( x,y\right) :x+y=7
\end{equation*}とします。以下の開論理式
\begin{equation*}
\exists x\in X:P\left( x,y\right)
\end{equation*}について、次の値を自由変数\(y\)に代入したときに得られる命題の真偽をそれぞれ判定してください。
\end{equation*}とし、命題関数を、
\begin{equation*}
P\left( x,y\right) :x+y=7
\end{equation*}とします。以下の開論理式
\begin{equation*}
\exists x\in X:P\left( x,y\right)
\end{equation*}について、次の値を自由変数\(y\)に代入したときに得られる命題の真偽をそれぞれ判定してください。
- \(y=2\)
- \(y=6\)
問題（量化記号の順序）
学生全体からなる集合を\(S\)、書籍全体からなる集合を\(B\)とし、命題関数 \begin{equation*}
P\left(x,y\right):\text{学生}x\text{は書籍}y\text{を読んだ}
\end{equation*}を定義します。以下の論理式をそれぞれ日常言語で表現した上で、両者の意味の違いを説明してください。
P\left(x,y\right):\text{学生}x\text{は書籍}y\text{を読んだ}
\end{equation*}を定義します。以下の論理式をそれぞれ日常言語で表現した上で、両者の意味の違いを説明してください。
- \(\forall x\in S,\ \exists y\in B:P\left( x,y\right) \)
- \(\exists y\in B,\ \forall x\in S:P\left( x,y\right) \)
問題（論理式の解釈の応用）
ある大学の学生全体からなる集合を\(X\)とし、以下の命題関数を定義します。 \begin{eqnarray*}
P\left(x\right) &:& x\text{は経済学を履修している} \\
Q\left(x\right) &:& x\text{は統計学を履修している}
\end{eqnarray*}次の主張を論理式として定式化してください。
P\left(x\right) &:& x\text{は経済学を履修している} \\
Q\left(x\right) &:& x\text{は統計学を履修している}
\end{eqnarray*}次の主張を論理式として定式化してください。
- 経済学を履修している学生は全員、統計学も履修している。
- 統計学を履修しているが、経済学を履修していない学生が少なくとも1人存在する。
- 1と2がともに成り立つとき、経済学を履修している学生全体と統計学を履修している学生全体は一致しないことを説明してください。
問題（論理式の解釈の応用）
3つの講義\(1,2,3\)を3つの教室\(a,b,c\)のいずれかに割り当てるものとします。講義の集合を、\begin{equation*} L=\left\{ 1,2,3\right\}
\end{equation*}とし、教室の集合を、\begin{equation*}
R=\left\{ a,b,c\right\}
\end{equation*}とします。また、命題関数
\begin{equation*}
P\left( l,r\right) :\text{講義}l\text{は教室}r\text{に割り当てられる}
\end{equation*}を定義します。以下の条件を論理式として定式化してください。
\end{equation*}とし、教室の集合を、\begin{equation*}
R=\left\{ a,b,c\right\}
\end{equation*}とします。また、命題関数
\begin{equation*}
P\left( l,r\right) :\text{講義}l\text{は教室}r\text{に割り当てられる}
\end{equation*}を定義します。以下の条件を論理式として定式化してください。
- それぞれの講義は少なくとも1つの教室に割り当てられる。
- それぞれの講義は高々1つの教室にしか割り当てられない。
- それぞれの講義はちょうど1つの教室に割り当てられる。
問題（論理式の解釈）
以下の集合
\begin{equation*}
X=\left\{ 1,2,3,4\right\}
\end{equation*}と命題関数
\begin{equation*}
P\left( x,y\right) :x+y=5
\end{equation*}を考えます。次の論理式の真偽をそれぞれ判定してください。
\begin{equation*}
X=\left\{ 1,2,3,4\right\}
\end{equation*}と命題関数
\begin{equation*}
P\left( x,y\right) :x+y=5
\end{equation*}を考えます。次の論理式の真偽をそれぞれ判定してください。
- \(\forall x\in X,\ \exists y\in X:P\left( x,y\right) \)
- \(\exists y\in X,\ \forall x\in X:P\left( x,y\right) \)
問題（論理式の解釈）
「数独（すうどく）」とは縦横9行ずつの合計81マスの枠内に1から9までの数字を1つずつ入れるパズルです。ゲームの開始時点において下図のようにいくつかのマスにはすでに数字が書かれており、空いているマスに1から9までの数字を1つずつ入れていくことが目標になります。ただし、全体は下図のように太線で囲まれた3\(\times \)3のブロックに区切られており、同じブロック内のマスに同じ数字を入れることはできません。また、同じ行内のマスや同じ列内のマスにも同じ数字を入れることはできません。
図：数独
以上を踏まえた上で以下の問いに答えてください。
- 「それぞれのマスに入るのは高々1つの数字」ことを論理式として定式化してください。
- 「それぞれの行内のマスには1から9までの数字が1回ずつ現れる」ことを論理式として定式化してください。
- 「それぞれの列内のマスには1から9までの数字が1回ずつ現れる」ことを論理式として定式化してください。
- 「それぞれのブロック内のマスには1から9までの数字が1回ずつ現れる」ことを論理式として定式化してください。
