対偶 (論理学)
命題「AならばB」の対偶は「BでないならばAでない」である。 論理記号として「ならば ( ⇒ {\displaystyle \Rightarrow } )」および否定 ( ¬ {\displaystyle \neg } ) を用いると、命題 A ⇒ B {\displaystyle A\Rightarrow B} の対偶は ¬ B ⇒ ¬ A {\displaystyle \neg B\Rightarrow \neg A} である。
なお、 ¬ B ⇒ ¬ A {\displaystyle \neg B\Rightarrow \neg A} の対偶は厳密には A ⇒ B {\displaystyle A\Rightarrow B} ではなく、 ¬ ¬ A ⇒ ¬ ¬ B {\displaystyle \neg \neg A\Rightarrow \neg \neg B} である。
通常の数学では古典論理を用いるため、命題「AならばB」とその対偶「BでないならばAでない」の真偽および証明可能性は必ず一致する (すなわち真理値が等しい)。
数学では、元の命題「AならばB」の証明が難しくても、その対偶「BでないならばAでない」の証明は比較的易しい場合がある。両者の証明可能性は一致するので、対偶「BでないならばAでない」を示すことにより「AならばB」を証明できる。これを対偶論法とよぶ。同様に、「BならばAである」を示すことにより「AでないならばBでない」を証明することもできる。
対偶論法の正当性を示すためには「 ¬ B ⇒ ¬ A {\displaystyle \neg B\Rightarrow \neg A} が証明可能ならば A ⇒ B {\displaystyle A\Rightarrow B} が証明できること」が必要である。 古典論理におけるこれの証明は、自然演繹を用いると以下のようになる。
¬ B ⇒ ¬ A [ ¬ B ] 1 ¬ A [ A ] 2 ⊥ ¬ ¬ B ( 1 ) B A ⇒ B ( 2 ) {\displaystyle {\dfrac {\dfrac {{\dfrac {\dfrac {{\dfrac {\neg B\Rightarrow \neg A\quad [\neg B]^{1}}{\neg A}}\quad \displaystyle {{} \atop {[A]^{2}}}}{\bot }}{\neg \neg B}}(1)}{B}}{A\Rightarrow B}}(2)}
逆向きについても同様に証明できることから、元の命題と対偶命題の証明可能性が等しいことがわかる。