命題論理とは

/論理・基礎論

命題論理とは、命題をいくつかの記号(論理記号)に置換えて単純化して表現したものです。尚、命題とは、真偽の判断の対象となる文章(論理式)です。

論理記号

以下に、命題論理で使われる論理記号について説明します。

含意($\to$)

命題 $A$、$B$ について、「$A$ であれば $B$ である」ことを以下のように表します。言い換えれば、$A$ であることが証明できれば、$B$ であることも証明できるという意味になります。

$$A\to B$$

定義より、次のことが分かります。

$$A\to A$$

否定($\neg$)

命題 $A$ について、「$A$ でない」ことを以下のように表します。

$$\neg A$$

定義より、次のことが分かります。

$$\neg\neg A\to A$$

同値($\equiv$)

2つの論理式 $A\to B$ と $B\to A$ が両方証明できることを「同値である」といい、以下のように表します。これは、「$A$ ならば $B$ であり、かつ、$B$ ならば $A$ である」と同じ意味であると考えます。

$$A\equiv B$$

定義より、次のことが分かります。

$A\equiv B$、$B\equiv C$ ならば、$A\equiv C$

論理和($\vee$)

命題 $A$、$B$ について、「$A$ または $B$」であることを以下のように表します。

$$A\vee B$$

また、この論理和は次のように表すことができます。

$$A\vee B\equiv\neg A\to B$$

論理積($\wedge$)

命題 $A$、$B$ について、「$A$ かつ $B$」であることを以下のように表します。

$$A\wedge B$$

また、この論理和は次のように表すことができます。

$$A\wedge B\equiv\neg(\neg A\vee\neg B)$$

公理と公式

命題論理では以下の公理系が採用されています。

  1. $A\to(B\to A)$
  2. $[A\to(B\to C)]\to[(A\to B)\to(A\to C)]$
  3. $(\neg B\to\neg A)\to(A\to B)$

また、推論規則として以下を仮定します。

  1. $(A\wedge(A\to B))\to B$
  2. $((A\to B)\wedge(B\to C))\to(A\to C)$

背理法

背理法とは、ある仮定が矛盾することを示すことで、その仮定が成り立たないことを証明する手法です。元の仮定{$C_1,\cdots,C_n$}に $C_{n+1}$ を追加して、仮定{$C_1,\cdots,C_n,C_{n+1}$}が矛盾すれば、元の仮定に対し $\neg C_{n+1}$ が証明できたことになります。

尚、矛盾とは、ある仮定の下で、論理式 $A$ とその否定 $\neg A$ の両方が証明できてしまうことを言います。

ド・モルガンの法則

ド・モルガンの法則は以下のように表されます。

$$\neg(A\vee B)\equiv\neg A\wedge\neg B$$$$\neg(A\wedge B)\equiv\neg A\vee\neg B$$

 

数学
解析学、代数学、幾何学、統計学、論理・基礎論、情報・暗号、機械学習、金融・ゲーム理論、高校数学
散策路TOP
数学、応用数学、古典物理、量子力学、物性論、電子工学、IT、力学、電磁気学、熱・統計力学、連続体力学、解析学、代数学、幾何学、統計学、論理・基礎論、プラズマ物理、量子コンピュータ、情報・暗号、機械学習、金融・ゲーム理論

 

タイトルとURLをコピーしました