[定義]
命題とは、「XはYである」という肯定文または「XはYではない」という否定文であり、正しいか間違っているかが決まっている文のことである。
つまり、命題は真と偽のうちどちらかひとつだけを持つ。これは、Pが命題のときは、Pは真であって偽ではないか、あるいはPは真ではなくて偽であるのどちらかになるということである。そこで、真であって偽ではない命題を真の命題と呼び、真ではなく偽である命題を偽の命題と呼ぶことにする。
[定義]
真の命題＝真であって偽ではない命題
偽の命題＝真ではなく偽である命題
数学の対象物は、命題と命題ではない対象物の2つに分かれる。
そこで、Pを数学の対象物とする。そして、次のようにA,Bを置いて、これらを命題と仮定する。
命題A：対象物Pは真である。
命題B：対象物Pは偽である。
すると、AとBの真偽の組み合わせは次の4通りになる。
| A | B | 意味 |
| 1 | 1 | Pは真かつ偽である |
| 1 | 0 | Pは真であって、偽ではない |
| 0 | 1 | Pは真ではなくて、偽である |
| 0 | 0 | Pは真でもなければ偽でもない |
そこで、例えば単にPは真であるというときは、次の2つのパターンが考えられる。
（1）Pは真である、かつ偽である
（2）Pは真である、かつ偽ではない
「Pは真である」といっても、「Pは偽ではない」とはいえないことになる。Pは対象物であり、命題ではないことに注意。
よって、一般的にはPは真であることを否定しても、Pは偽であることにはならない。
ところが、Pを命題とすると、このときPは真の命題、偽の命題であるかのどちらかである。そうすると、「Pは真の命題である」を否定すると、定義により「Pは真の命題ではない」といえるわけだ。
[定理]
（1）¬（Pが真）＝（Pが偽） （ただし、¬は否定を意味する）
（2）¬（Pが偽）＝（Pが真）
Pを数学の対象物とすると、「Pは命題である」と「Pは真の命題である」ということは違う。というのは、「Pは真である。しかし、Pは命題である」という命題に似たものが存在するからである。例えば、矛盾がそうである。矛盾（矛盾文）とは、正しい文でもあり、間違っている文でもあり、2つの性質を持っている。この矛盾が命題ではないというのは自明だけど、真というのはどういうことだろうか。これは、矛盾を含んだ理論が正しい理論として採用されている（世界中に思われている）可能性があるからである。
命題には真偽があるが、逆に真偽のあるものが命題であるという論理は成立しない。
ここで、命題ではない対象物の名称を定義しておく。
[定義]命題ではない対象物を非命題と呼ぶ。
こうして、数学の対象物は命題と非命題に分類されることになる。
誰も理解できない文は命題とはいえない。しかし、ある人は理解できて別の人が理解できない文は命題だろうか？ その明確なしきい値・区別は難しい。論理の性質を思い出すと、論理的とは誰でも理解できるものであった。つまり、文の意味も全員が理解できてこそ、命題といえて欲しい。しかしながら、言葉のわからない赤ちゃんが文の意味を理解できるわけがない。
このようにある文が命題か命題でないかを確実に分ける方法はない。しかし、ある対象物を命題と仮定したときに矛盾が出てくれば、その対象物は非命題といえる。これは背理法から導ける法則である。
論理記号や論理式を用いて議論の対象にしているのは主に命題である。だから数学が扱うものを単にPと書いたとき、これは「Pは命題である」、「Pは命題でない」（「Pは非命題である」）という場合に分けてそれぞれについて論理を進めなければならない。
ちなみに、ここで論理学では主に命題を対象とするといったが、場合によっては非命題も対象にできる。
Pを数学の対象物とする。もし、数学の対象物を、命題と非命題の2つに分類できれば、次の文Xは命題になる。
X：Pは命題である。
Pが命題であればXは真の命題になり、Pが非命題であればXは偽の問題になる。これにより、命題と非命題を真の命題と偽の命題に変換できる。わけだ。
2つの命題を「ならば」という語を使い結びつける演算で、「A⇒B」と記述される。命題Aが真で、命題Bが偽のときのみ「A⇒」が偽となる。
真理値を表の形式で表したものを真理値表という。
真理値表は、命題の真理値（真と偽）のすべての組み合わせについて、その演算結果の真理値を記述した表である。
| v(A) | v(￣A) |
| T | F |
| F | T |
ここではきちんと命題の真理値を明示するためにv( )で閉じているが、よく省略されて書かれていることもある。 また、真を「T」（True）、偽を「F」（False）と書いた。
| v(A) | v(B) | v(A∧B) |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
| v(A) | v(B) | v(A∨B) |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
| v(A) | v(B) | v(A⇒B) |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
次に示す命題の真理表を調べよ。なるべく自分の頭で考えること。
・[命題]A⇒B ・[命題]¬A∨B
上記2つの命題の結果を比較して、何か気付かないだろうか？
[定義]
元の命題の真偽に関わらず、常に真となるような命題を恒真命題（トートロジー）と呼ぶ。
逆に、常に偽となる命題を恒偽命題（矛盾命題）と呼ぶ。
恒真命題をI、恒偽命題をOと表記する。
例1：A∨￣Aは常に真となるから恒真命題である。
例2：A∧￣Aは常に偽となるから恒偽命題である。
[定理]
（1）¬I≡O
（2）¬O≡I
[証明]I、O、¬I、¬Oを真理表で表すと次のようになる。
| I | O | ¬I | ¬O |
| T | F | F | T |
[定義]
「A⇒B」に対して、「B⇒A」を逆といい、「¬A⇒¬B」を裏といい、「¬B⇒¬A」を対偶という。
[定理]
「A⇒B」とその対偶である「¬B⇒¬A」は同値である。
最初に導入されるべき導出規則は仮定の法則（rule of assumptions）である。これを略してAと呼ばれる。
この規則は、論証の任意の段階において、論証の仮定として選ばれた任意の命題を導出することを許す。次のように、新しい行の左側から順に「命題の番号」→「行番号」（括弧付き）→「仮定となっている命題」→「A」と記述する。
1 (1) P⇒Q A
これは命題「P⇒Q」を仮定の規則として使うことを意味する。
もちろん仮定はまったくないほうが数学的にはよい。しかし何らかの仮定を前提としなければ証明できない数学的事実なども多い。そこで仮定を用いるわけだが、仮定となるべき命題は広く信じられている結果でなければならない。例えば暗号の世界でいうなら、多くの暗号学者に広く認知されている「素因数分解は困難」「離散対数計算は困難」といった命題である。他にも広く認知されるまでには至っていないが、便利な仮定などもある。例えば「ランダムオラクル仮定」「CRS仮定」などである。現実性の度合いは前者の仮定のほうが強い。つまり、仮定に要求する強さでいうと、後者のほうが強い仮定ということになる。
一方、論理学者は仮定の正しさを研究するわけではない。仮定に基づくすべての結論が、正しく仮定に基づいていることを確かめるわけである。
2番目の導出規則は前件肯定式（MPP：Modus Ponendo Ponens）である。MPPは、前提として条件的命題とその条件的命題の前件とが与えられているならば、その条件的命題の後件を結論として導くことを許すというものである。つまり演算記号⇒に関するものである。MPPが主張される理由は次の通りである。
| A | B | A⇒B | A∧(A⇒B) | (A∧(A⇒B))⇒B |
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | F | T | F | T |
その結果、「(A∧(A⇒B))⇒B」はトートロジーとなるので、常に正しい。つまり、「Aが真∧「A⇒B」が真」⇒「Bが真」は必ず成立する。
この前件肯定式は公理から定理を証明するときに使うなど、論理学のおいてはもっとも基本的なものである。また、数学的帰納法も前件肯定式がなければ意味がない。
MPPを利用したときの例を示す。
例1：
1 (1) P⇒Q A 2 (2) P A 1,2 (3) Q 1,2 MPP
例2：
1 (1) ¬Q⇒(¬P⇒Q) A 2 (2) ¬Q A 1,2 (3) ¬P⇒Q 1,2 MPP
上記の例はどちらとも、1と2は仮定として与えられたときに、MPPを用いることでQが導かれるという意味である。
もう少し複雑な例を挙げる。
例3：
1 (1) P⇒Q A 2 (2) Q⇒R A 3 (3) P A 1,3 (4) Q 1,3 MPP 1,2,3 (5) R 2,4 MPP
最初の3行は必要な仮定を導入しているだけである。(1)行目は条件法「P⇒Q」を与えている。(3)行目でその前件Pが与えられると、MPPによって(4)行目で結論Qが導かれる。
| A | B | C | A⇒B | B⇒C | (A⇒B)∧(B⇒C) | A⇒C | ( (A⇒B)∧(B⇒C) )⇒(A⇒C) |
| T | T | T | T | T | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | F | T | T |
| T | F | F | F | F | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | F | F | T | T |
| F | F | T | F | T | F | T | T |
| F | F | F | F | F | F | T | T |
よって、「( (A⇒B)∧(B⇒C) )⇒(A⇒C)」は最終的にトートロジー、即ちいつでも成り立っている。これは「「もしA⇒Bが真であり、かつ、B⇒Cも真である」ならば、A⇒Cも真である」ということを意味する。
[定義]
この手続きを三段論法と呼ぶことにする。
矛盾とは、真と偽を同時に持つことであった。
ところで、Pが命題であるとき、Pは真か偽かのどちらかである。このとき、「Pは真であって偽ではない」か、あるいは「Pは偽であって真ではない」かのどちらかである。
したがって、Pは矛盾していない。
命題を定義した時点で、すでに命題は矛盾していないという特徴を有しているといえる。
したがって、これも命題論理の公理のひとつとして使えそうだ。
一般用語として「矛盾した命題」という言葉が使われることがある。これは命題の定義と矛盾の定義からありえないことだが、文の終わりに「命題」という言葉が付いているから、「矛盾した命題」とは命題（の一種）ではないか？ という反論があるかもしれない。
しかし、それは間違いである。というのも、命題はもともと矛盾していないのだから、それに「矛盾した」という修飾語をかぶせること自体がありえないということである。つまり、この「矛盾した命題」という用語は2つに切り離せないひとつの単語になっているのである。例えば、「ウミネコは海にいる猫ではない」ということからわかると思う。
矛盾が来たら、それに関連するものとして背理法がある。実はこれもいつでも成り立つ事実なのだ。
[定義]
背理法とは、ある命題Aが真であると仮定して正しい推論を続けたときに矛盾した結論が出てくるような場合、真と仮定したものの命題Aは本当は偽であると結論付ける証明方法である。
数学に慣れている人なら背理法の強力さは実感していると思われるが、知らない人であっても背理法がうまくいくということは実際に真理表を書いてみるとわかると思う。
| A | B | ¬A | ¬B | A⇒B | A⇒¬B | (A⇒B)∧(A⇒¬B) |
| T | T | F | F | T | F | F |
| T | F | F | T | F | T | F |
| F | T | T | F | T | T | T |
| F | F | T | T | T | T | T |
よって、¬Aと「(A⇒B)∧(A⇒¬B)」は同値になっている。
以上のことをまとめると、公理系が構成できる。これを公理系LPと呼ぶことにする。
[公理]命題論理の公理系LP
[規則1]（演繹規則DR（deduction rule））
Aを仮定してBを導出される時、Aという仮定なしにA⊃Bを導出してよい。
[規則2]（前件肯定式MP（ラテン語：modus poneus））
A,A⊃BからBを導出してよい。
[規則3]（背理法）
A⊃（D∧¬P）から¬Aを導出してよい。
[規則4]（二重否定）
¬¬AからAを導出してよい。~
[規則5]（結合）
A,BからA∧Bを導出してよい。
[規則6]（分離）
（１）A∧BからAを導出してよい。
（２）A∧BからBを導出してよい。
[規則7]（∨入れ）
（2）AからA∨Bを導出してよい。
（2）BからA∨Bを導出してよい。
[規則8]（∨取り）
A∨B,A⊃C,B⊃CからCを導出してよい。
定義：A≡Bは（A⊃B）∧（B⊃A）の略記である。
ここで、A,B,C,Dは任意の論理式を表す。
上記の公理をまとめると次のようになる。
| [規則1]・・・⊃の導入則 | [規則2]・・・⊃の除去則 |
| [規則3]・・・¬の導入則 | [規則4]・・・¬の除去則 |
| [規則5]・・・∧の導入則 | [規則6]・・・∧の除去則 |
| [規則7]・・・∨の導入則 | [規則8]・・・∨の除去則 |
[規則3']
Aを仮定して、D∧¬Dが導出される時、Aという仮定なしに¬Aを導出してよい。
[規則3' ']
¬Aを仮定して、D∧¬Dが導出される時、¬Aという仮定無しに、Aを導出してもよい。
[規則4']
Aから¬¬Aを導出してよい。
[規則3]、[3']、[3' ']をあわせて背理法と呼ぶ。また、[規則4]、[4']をあわせて二重否定と呼ぶ。
[定理]定理から派生規則への読み換え
（A1∧…∧An）⊃Bの形の定理と「A1,…,AnからBを導出してよい」という派生規則とは、基本的に同じものと見なしてよい。
それゆえ、（A1∧…∧An）⊃Bの形の定理が証明されたならば、直ちに派生規則「A1,…,AnからBを導出してよい」を証明されたものとみなすことにして、その派生規則もまた定理と同じ呼び名で呼び、以後の証明で用いることにする。
[定理]
（A∨B）⊃（B∨A）
[証明の方針]
A∨Bという分かれ道にいる。
目的地はB∨Aである。
そこで、Aの道を通ってB∨Aに着き、Bの道を通ってもB∨Aにつくことを証明する。
[証明]
（１）A∨B ←[1]仮定��
（２）A ←[2]仮定��
（３）B∨A ←[2]∨入れ
（４）A⊃（B∨A） ←（２）（３）とDR
（５）B ←[5]仮定��
（６）B∨A ←[5]∨入れ
（７）B⊃（B∨A） ←（５）（６）とDR
（８）B∨A ←[1]（１）（４）（７）と∨取り
（９）（A∨B）⊃（B∨A） ←（１）（８）とDR
