離散数学-命題論理

数理論理学の規則は、数学的ステートメントを推論する方法を指定します。ギリシャの哲学者、アリストテレスは論理的推論の先駆者でした。論理的推論は、数学、ひいてはコンピュータサイエンスの多くの分野の理論的基盤を提供します。コンピューティングマシンの設計、人工知能、プログラミング言語のデータ構造の定義など、コンピュータサイエンスで多くの実用的なアプリケーションがあります。

Propositional Logicは、真理値「true」および「false」を割り当てることができるステートメントに関係しています。目的は、これらのステートメントを個別に、または複合的に分析することです。

命題論理–定義

命題は、真理値「true」または真理値「false」のいずれかを持つ宣言型ステートメントのコレクションです。命題は、命題変数と結合要素で構成されます。命題変数は大文字（A、Bなど）で示されます。結合は命題変数を接続します。

命題のいくつかの例を以下に示します-

「ManisMortal」、真理値「TRUE」を返します
「12+ 9 = 3 – 2」、真理値「FALSE」を返します

以下は提案ではありません-

「Aは2未満です」。これは、Aの特定の値を指定しない限り、ステートメントが真であるか偽であるかを判断できないためです。

接続詞

命題論理では、一般に、次の5つの連結語を使用します。

または（$ \ lor $）
AND（$ \ land $）
否定/ NOT（$ \ lnot $）
含意/ if-then（$ \ rightarrow $）
（$ \ Leftrightarrow $）の場合のみ。

OR ($\lor$) −命題変数AまたはBの少なくともいずれかが真である場合、2つの命題AおよびB（$ A \ lor B $として記述）のOR演算は真です。

真理値表は次のとおりです-

A	B	A∨B
本当	本当	本当
本当	誤り	本当
誤り	本当	本当
誤り	誤り	誤り

AND ($\land$) −命題変数AとBの両方が真の場合、2つの命題AとB（$ A \ land B $として記述）のAND演算は真です。

真理値表は次のとおりです-

A	B	A∧B
本当	本当	本当
本当	誤り	誤り
誤り	本当	誤り
誤り	誤り	誤り

Negation ($\lnot$) −命題A（$ \ lnot A $として記述）の否定は、Aが真の場合は偽であり、Aが偽の場合は真です。

真理値表は次のとおりです-

A	¬A
本当	誤り
誤り	本当

Implication / if-then ($\rightarrow$)−含意$ A \ rightarrow B $は、「if A、thenB」という命題です。Aが真でBが偽の場合は偽です。残りのケースは本当です。

真理値表は次のとおりです-

A	B	A→B
本当	本当	本当
本当	誤り	誤り
誤り	本当	本当
誤り	誤り	本当

If and only if ($ \Leftrightarrow $) − $ A \ Leftrightarrow B $は双条件論理積であり、pとqが同じ場合、つまり両方が偽であるか、両方が真である場合に真になります。

真理値表は次のとおりです-

A	B	A⇔B
本当	本当	本当
本当	誤り	誤り
誤り	本当	誤り
誤り	誤り	本当

トートロジー

トートロジーは、命題変数のすべての値に常に当てはまる公式です。

Example − $ \ lbrack（A \ rightarrow B）\ land A \ rbrack \ rightarrow B $がトートロジーであることを証明する

真理値表は次のとおりです-

A	B	A→B	（A→B）∧A	[（A→B）∧A]→B
本当	本当	本当	本当	本当
本当	誤り	誤り	誤り	本当
誤り	本当	本当	誤り	本当
誤り	誤り	本当	誤り	本当

$ \ lbrack（A \ rightarrow B）\ land A \ rbrack \ rightarrow B $のすべての値が「真」であることがわかるので、これはトートロジーです。

矛盾

矛盾は、命題変数のすべての値に対して常に偽である式です。

Example − $（A \ lor B）\ land \ lbrack（\ lnot A）\ land（\ lnot B）\ rbrack $が矛盾していることを証明する

真理値表は次のとおりです-

A	B	A∨B	¬A	¬B	（¬A）∧（¬B）	（A∨B）∧[（¬A）∧（¬B）]
本当	本当	本当	誤り	誤り	誤り	誤り
本当	誤り	本当	誤り	本当	誤り	誤り
誤り	本当	本当	本当	誤り	誤り	誤り
誤り	誤り	誤り	本当	本当	本当	誤り

$（A \ lor B）\ land \ lbrack（\ lnot A）\ land（\ lnot B）\ rbrack $のすべての値が「偽」であることがわかるので、矛盾しています。

不測の事態

偶然性は、命題変数のすべての値に対していくつかの真の値といくつかの偽の値の両方を持つ式です。

Example − $（A \ lor B）\ land（\ lnot A）$の不測の事態を証明する

真理値表は次のとおりです-

A	B	A∨B	¬A	（A∨B）∧（¬A）
本当	本当	本当	誤り	誤り
本当	誤り	本当	誤り	誤り
誤り	本当	本当	本当	本当
誤り	誤り	誤り	本当	誤り

$（A \ lor B）\ land（\ lnot A）$のすべての値に「True」と「False」の両方があることがわかるので、これは不測の事態です。

提案的等価性

次の2つの条件のいずれかが当てはまる場合、2つのステートメントXとYは論理的に等価です。

各ステートメントの真理値表は同じ真理値を持っています。
双条件ステートメント$ X \ Leftrightarrow Y $はトートロジーです。

Example − $ \ lnot（A \ lor B）と\ lbrack（\ lnot A）\ land（\ lnot B）\ rbrack $が同等であることを証明する

1^番目の方法によるテスト（真理値表のマッチング）

A	B	A∨B	¬（A∨B）	¬A	¬B	[（¬A）∧（¬B）]
本当	本当	本当	誤り	誤り	誤り	誤り
本当	誤り	本当	誤り	誤り	本当	誤り
誤り	本当	本当	誤り	本当	誤り	誤り
誤り	誤り	誤り	本当	本当	本当	本当

ここで、$ \ lnot（A \ lor B）と\ lbrack（\ lnot A）\ land（\ lnot B）\ rbrack $の真理値が同じであることがわかります。したがって、ステートメントは同等です。

2^番目の方法によるテスト（Bi-conditionality）

A	B	¬（A∨B）	[（¬A）∧（¬B）]	[¬（A∨B）]⇔[（¬A）∧（¬B）]
本当	本当	誤り	誤り	本当
本当	誤り	誤り	誤り	本当
誤り	本当	誤り	誤り	本当
誤り	誤り	本当	本当	本当

$ \ lbrack \ lnot（A \ lor B）\ rbrack \ Leftrightarrow \ lbrack（\ lnot A）\ land（\ lnot B）\ rbrack $はトートロジーであるため、ステートメントは同等です。

インバース、コンバース、およびコントラポジティブ

含意/ if-then $（\ rightarrow）$は条件文とも呼ばれます。それは2つの部分に分かれています-

仮説、p
結論、q

前述のように、$ p \ rightarrow q $として表されます。

Example of Conditional Statement−「宿題をしても、罰せられることはありません。」ここで、「宿題をする」が仮説pであり、「罰せられない」が結論qです。

Inverse−条件文の逆は、仮説と結論の両方の否定です。ステートメントが「Ifp、then q」の場合、逆は「If not p、thennotq」になります。したがって、$ p \ rightarrow q $の逆数は$ \ lnot p \ rightarrow \ lnot q $です。

Example −「宿題をすれば罰せられない」の逆は「宿題をしなければ罰せられる」です。

Converse−条件文の逆は、仮説と結論を交換することによって計算されます。ステートメントが「Ifp、then q」の場合、逆は「If q、thenp」になります。$ p \ rightarrow q $の逆は$ q \ rightarrow p $です。

Example −「宿題をすれば罰せられない」の逆は「罰せられなければ宿題をする」です。

Contra-positive−条件の対偶論法は、仮説と逆ステートメントの結論を交換することによって計算されます。ステートメントが「Ifp、then q」の場合、対偶論法は「If not q、thennotp」になります。$ p \ rightarrow q $の対偶論法は$ \ lnot q \ rightarrow \ lnot p $です。

Example −「宿題をすれば罰せられない」の対偶論法は「罰せられれば宿題をしなかった」です。

双対原理

双対の原則は、真のステートメントの場合、ユニオンを共通部分に交換すること（およびその逆）とユニバーサルセットをヌルセットに交換すること（およびその逆）によって得られるデュアルステートメントも真であると述べています。いずれかのステートメントの双対がステートメント自体である場合、それは言われますself-dual ステートメント。

Example − $（A \ cap B）\ cup C $の双対は$（A \ cup B）\ cap C $です