論理式の基本

Posted by

今更だけど基礎。（その理屈、証明できますか？より）

ド・モルガンの法則

\lnot(P\wedgeQ)=\lnot P \vee \lnot Q
\lnot(P\vee Q)=\lnot P \wedge \lnot Q

交換法則

P\wedge Q = Q\wedge P
P\vee Q=Q\vee P

結合則

P\wedge (Q\wedge R) = (P\wedge Q)\wedge R
P\vee (Q\vee R) = (P\vee Q)\vee R

冪等則

P\wedge P = P
P\vee P = P

分配則

P\wedge (Q\vee R) = (P\wedge Q)\vee (P\wedge R)
P\vee (Q\wedge R) = (P\vee Q)\wedge (P\vee R)

吸収則

P\vee (P\wedge Q) = P
P\wedge (P\vee Q) = P

二重否定の法則

\lnot\lnot P=P

状況に応じて複雑な式を変形できることが大事。

    \begin{eqnarray*} \lnot(Q　\wedge \lnot　P)\vee P&=&(\lnot Q \vee\lnot\lnot P)\vee P \\ &=& (\lnot Q　\vee P)\vee P \\ &=& \lnot Q　\vee (P\vee P) \\ &=& \lnot Q　\vee P \end{eqnarray*}