恒真式

どのような解釈をしようとも常に真である論理式のことを恒真式もしくはトートロジー(tautology)といいます.

$A,B,C$ を任意の論理式としたとき,以下の有名な恒真式として次のものがあります.

ド・モルガンの法則 De Morgan's law

\[\lnot (A \land B) \leftrightarrow \lnot A \lor \lnot B\]\[\lnot(A \lor B)\leftrightarrow \lnot A \land \lnot B\]この恒真式は,ド・モルガンの双対性(de Morgan's Duality law)ともいわれます.

また,ド・モルガンの法則は集合の概念を用いて次のようにも表現できます.\[\overline{A \cap B}=\overline{A} \cup \overline{B}\]\[\overline{A \cup B}=\overline{A} \cap \overline{B}\]

結合律 associative law

\[A \land(B \land C) \leftrightarrow (A \land B)\land C\]\[A \lor (B \lor C) \leftrightarrow (A \lor B) \lor C\]

交換律 commutative law

\[A \land B \leftrightarrow B \land A\]\[A \lor B \leftrightarrow B \lor A\]

Vita brevis, ars longa. Omnia vincit Amor.





















確率測度の拡張 文脈自由文法 同値関係と商集合 正規文法 形式文法と有限オートマトン 文と言語と文法