命題論理

メインページ > 論理学 > 命題論理

Wikipedia

ウィキペディアに命題論理の記事があります。

ここでは、論理学の基本である命題論理（propositional logic）について解説する。高校レベルの集合論・数学論理の理解を前提とする。数理論理学も併せて参照するとより理解が深まるだろう。

論理学とは

そもそも、論理学とはどのような学問だろうか？

論理学とは、演繹的論証の妥当性を研究する学問である。

論証（argument）とは、平たく言えば「ある前提から結論を導出して結論の正しさを示そうとする」ことである。類似した用語として推論（inference）があり厳密には区別されるが、本項では区別せず扱うことにする。

論証は前提（premises）・導出（resolution）・結論（conclusion）という三要素に分解することができる。

例えば、有名なソクラテスの三段論法（syllogism）「ソクラテスは人間である。人間はいつか死ぬ。故にソクラテスもいつかは死ぬ」は、「ソクラテスは人間である」「人間はいつか死ぬ」の2文が前提で「ソクラテスもいつかは死ぬ」が結論である。明示はされないが、前提と結論の間には導出するための思考過程が必ず介在する。

結論の正しさを担保するには、前提・導出ともに正しくなければならない。

例えば「魚は水中で呼吸できる。人間は魚である。なので人間は水中で呼吸できる。」という論証について、二つ目の前提「人間は魚である」が間違っているので結論は明らかに正しくない。

そも論証とは「正しいと判明している主張（前提）から問題にしている主張（結論）が導かれる」ことを示すものなので、正しくない前提を持ってくると論証を行う意味そのものがない。

「鳥類は嘴(くちばし)を持つ。カモノハシは嘴を持つ。なので、カモノハシは鳥類である。」という論証はどうであろうか？これは結論が明らかに間違いであるが、高校数学で習ったベン図（Venn's diagram）を書くことで示せる。

「鳥類」の集合と「カモノハシ」の集合は共に「嘴を持つ」という集合の部分集合であるが、ベン図を書くことでこの条件だけでは「カモノハシ」の集合が「鳥類」の集合に包含されるとはいえないことがわかる。そのため、この前提から「カモノハシならば鳥類」が必ず成り立つとは言えない。

これらのことから、「導出が正しい」とは『前提が正しければ100%結論が正しい』が成り立つことと言える。二重鍵括弧で示した性質を妥当性（validity）という。妥当性のある論証を「妥当な（valid）論証」という。

注意：妥当な論証は「前提が正しければ結論も必ず正しくなる」論証であり、妥当性の判定時に前提が実際に正しいかどうかは関係ない。妥当且つ前提の正しい論証を特に「健全な（sound）論証」という。このように、論理学は「前提と結論の関係」に焦点を当てる学問である。

なお、前提・結論ともに正しいが妥当でない（invalid）論証も存在する。例えば「スマホはSIMカードを使う。パソコンはスマホではない。なので、パソコンはSIMカードを使わない」という論証はそうである。これは一見正しそうに見えるが、ベン図を書くことで妥当ではないと判る。「スマホ」の集合は「SIMカードを使う」という集合の部分集合であり、「スマホ」の集合の補集合が「SIMカードを使う」という集合の補集合であるとは必ずしも言えない。そのため、「パソコン」の集合は「スマホ」の集合の補集合に包含されるが「SIMカードを使う」という集合の補集合に包含されると言い切れないため、妥当ではない。

妥当ではない論証は前提が変われば結論の真偽が変わるため、証明に用いることができない。

論証には幾つか種類が存在する。

演繹法（deduction）は、「前提に含まれている論理的な事柄を抽出する」論証である。「妥当な論証」が「前提が真ならば結論が必ず真」というのも、ここからきている。演繹法は最も厳密且つ確実な論証であるが、前提に含まれていない事柄には対応できない。現代の社会で用いられる論証は多くが「前提からは抽出されない結論」に関する論証なので、演繹法が必ずしも万能というわけではない。

帰納法（induction）は、「繰り返し観察されてきて得られた経験則を一般化する」論証である。例えば、今迄目撃した鳥は全て空を飛べたことから、「全ての鳥は飛べる」と判断することが帰納法の例である。この結論が実際には正しくない（ペンギン・ダチョウ・鶏 etc.）ように、帰納法による論証は反例が出現する可能性が常にあるので確実とは言えない。しかし、科学は帰納法により積み上げられた作業仮説の集合体であり、日常生活でよく用いられる論証も多くは帰納法である。帰納法は仮説形成や予測に役立っている。より良い帰納的な論証を行うには、標本の無作為抽出及び大数の法則が肝要となる。なお、「数学的帰納法」は実際には演繹法である（自然数が順に積み上がっていく形式的な連鎖を「帰納的」と呼んだ名残）。

逆行推論法（abduction）は、「説明が必要となるデータを前提としてそのデータの表す現象を合理的に説明する仮説を結論として導く」論証である。ケプラーの第三法則、ウェゲナーの大陸移動説、オームの法則などが好例である。科学は帰納法による法則の抽出、逆行推論法による仮説形成の積み重ね、観測・実験による仮説の補強を繰り返すことにより発展してきた。良い逆行推論とは、「データを最も良く説明する」仮説を導くことである。そのため、逆行推論は「最良の説明への推論（inference to the best explanation）」と形容される。なお、英語の「abduction」は「誘拐」という意味も持つため、「retroduction」と言い換える場合もある。

帰納法や逆行推論法では論証の妥当性を重視しないので、妥当でない論証が必ずしも悪い論証というわけではないことを註しておく。

論理学（特に記号論理学）の守備範囲は演繹法のみである。故に、以降登場する論証は全て演繹的論証である。

論理式

真偽を判定できる文を命題（proposition）という。

命題論理では真（truth）と偽（false）の意味を考えない。命題はあくまでも「真」「偽」という二つの真理値（truth value）のいずれか一方が割り当てられるものと考える（二値原理）。

二値原理を仮定しない論理学も存在する。詳しくは多値論理を参照。

命題が偽であることを証明するには、命題が成り立たない例である反例（counterexample）を一つでも見つければよい。

先述のように、論理学で議論されるのは論証の妥当性である。そのため、前提・結論の意味内容は議論に無関係となる。

意味内容に焦点が当たらないのであれば、文を簡単な記号に置換しても問題ない。

文を置換した記号（例えば $p,q,r,\cdots$ ）を命題変項（propositional variable）という。

命題として扱えない文（命令文、感嘆文、疑問文、挨拶文 etc.）は命題変項に置換されず、代入することもない。

単一の命題変項は命題の最小単位として機能するので、原子式（atomic formula）と呼ぶ。

命題変項は、論理結合子（logical connector）と呼ばれる記号群を用いて複雑な命題を構成する。これを複合式（compound formula）という。

論理結合子は、自然言語でいう接続詞に（ある程度）対応する。

論理結合子の一覧
記号	対応する接続詞（日本語）	名称
$\lnot$	～でない	否定（negation）
$\land$	～且つ…	連言（conjunction）
$\lor$	～又は…	選言（disjunction）
$\rightarrow$ ^※	～ならば…	条件法（conditional）
$\leftrightarrow$ ^※	～であるとき且つそのときに限って…	双条件法（biconditional）

※ $\rightarrow ,\leftrightarrow$ は、数理論理学ではそれぞれ $\implies ,\iff$ とも書かれる。

$p\leftrightarrow q$ は、「pならばq」も「qならばp」も成り立っていること、則ち $(p\rightarrow q)\land (q\rightarrow p)$ を表す。ベン図では $p,q$ を表す集合が一致する場合に対応し、英語では「 $p$ if and only if $q$ 」のように表す。この英語に直接対応する日本語の接続詞は存在しないので、「であるとき且つそのときに限って」とやや長い表現となっている。命題「 $p\leftrightarrow q$ 」が真であるとき、「 $p$ と $q$ は同値（equivalence, iff）である」という。

論理結合子 $\circledast$ を用いた命題「 $p\circledast q$ 」に於いて、 $p,q$ はそれぞれ以下のように呼ばれる。

$p$	$\circledast$	$q$
連言肢（conjunct）	$\land$	連言肢
選言肢(disjunct)	$\lor$	選言肢
前件（antecident）	$\rightarrow$	後件（conseqent）
左辺（left-hand side）	$\leftrightarrow$	右辺（right-hand side）

順態接続の接続詞「且つ」と逆態接続の接続助詞「が」は、通常コンテクストによって使い分けられる。しかし、どちらも「繫いでいる前後の内容は両立する」という点では全く同じ働きをしている。そのため、文の意味内容を切り捨てる論理学ではどちらも連言記号 $\land$ に置き換えられる。

このように、自然言語で書かれた文を複合式に置き換えるとき、複合式を自然言語で書かれた文に直すときは注意が必要である。

命題変項と論理結合子を組み合わせて構成される複雑な式を複合式と呼んだ。

では、どのように複合式を構成すれば命題として意味を成すのであろうか？

ここでは、自然言語に於ける文法と同様に、命題論理に於いて有意と認められる論理式（logical formula）を構成するための公理を定める。

論理式の公理

(1)命題変項は論理式である。
(2)論理式 $A$ の否定 $\lnot A$ は論理式である。
(3)2つの論理式 $A,B$ の連言 $A\land B$ 、選言 $A\lor B$ 、条件法 $A\rightarrow B$ は全て論理式である^※。
(4)上記の規則以外で構成された複合式は論理式ではない。

※双条件法は条件法と連言の組み合わせで表せるので省略している。

ここで $A,B$ は任意の論理式を代入することができ、図式文字（schematic letter）と呼ばれる。

この公理に従えば、(2)(3)の規則を繰り返し適用することでいくらでも複雑な論理式を構成できる。

この公理は論理式の定義であり、最も単純な論理式を明示してそこから複雑な論理式を形成するための規則を与えている。このような定義法を再帰的/帰納的な定義（inductive/recursive definition）という。

論理式を読み易くするため、括弧の使用法についても定めておく。

論理式に於ける括弧の使用規則

(1)論理式の最外部に位置する括弧は省略してよい。但し、省略は左右同時に行う。
(2)括弧の種類は必要に応じて使い分けてよい。但し、左右一組とする。
(3)否定式全体は括弧で括らなくてもよい。

例えば、 $A\land B\land C$ という論理式は、 $(A\land B)\land C$ であるのか $A\land (B\land C)$ であるのか区別がつかない。そのため、この論理式は（構文上は）成り立たない。このように、括弧の使用規則によっても論理式の構成が制限されうる。

連言記号・選言記号・条件記号は数学的には二項演算子である。そのため、左右には明確に一つづつの論理式が来なければならない。

ある論理式がどのような手順で構成されたものであるかは、形成の木（formation tree）と呼ばれる図を書くことで調べられる。

形成の木は、複合式から論理結合子を一つづつ外して構成要素へと分解し、原子式まで至る過程を図にしたものである。

形成の木の出発点となる複合式を木の根（root）、末端となる原子式または論理結合子を木の葉（node）という。

例えば、論理式「 $(\lnot p\land q)\rightarrow r$ 」の形成の木は以下のようになる。

[図]

ある複合式の形成の木を描いたとき、最初の分解プロセスで除かれる論理結合子を見ることにより、その複合式が全体として何式であるかを見て見て取れる。このような論理結合子を主要結合子（main connective）という。

ここまで、命題論理の構文論（syntax）を扱ってきた。次の節では、真理値分析を通して命題論理の意味論（semantics）をみていく。

真理値分析

ブール代数も参照。

命題に「真/偽」という二つの真理値が割り当てられることは先述の通りなので、まずは真理値を表す記号を導入する。

中学・高校・大学と、英語の授業では $\mathrm {T} /\mathrm {F}$ が用いられてきただろう。数学・情報・電気工学では $1/0$ を用いることが多い。

論理学では、一般的に $\top /\bot$ を用いる。それぞれ「アップタック」「ダウンタック」と呼ばれる記号である。

原子式の真理値に応じて複合式の真理値がどのようになるかを表した表を真理値表（truth table）という。

論理結合子は論証の妥当性に於いて重要となる。妥当性は論理式の真理値に密接に関係しているので、論理結合子の持つ「意味」は、論理結合子を加える前と加えた後の真理値の変化によって確定される。

否定の真理値表は以下のようになる。

$A$	$\lnot A$
$\top$	$\bot$
$\bot$	$\top$

真理値表は、「 $A$ が $\top$ のとき $\lnot A$ が $\bot$ 」「 $A$ が $\bot$ のとき $\lnot A$ が $\top$ 」のように行毎に左から見る。

この真理値表から、「 $\lnot$ は論理式の真理値を反転させる」という風に否定の意味を決定することができる。

否定はNOT演算とも呼ばれるほか、真理値の補集合を返すので補数（complete）とも呼ばれる。

論理式の全体の真理値が原子式の真理値のみに依存するとき、論理式に含まれる論理結合子は真理関数的（truth-functional）であるという。今迄登場した論理結合子は全て真理関数的である（逆に、古典論理では真理関数的でない論理結合子は扱わない）。

例えば「～であることは可能/必然である」という論理結合子は真理関数的でないので本項では扱わないが、様相論理で詳しく学ぶ。

以下、他の論理結合子も真理値表によって意味付けを行う。

連言の真理値表は以下のようになる。

$A$	$B$	$A\land B$
$\top$	$\top$	$\top$
$\top$	$\bot$	$\bot$
$\bot$	$\top$	$\bot$
$\bot$	$\top$	$\bot$

この真理値表から、連言は「連言肢は共に成り立つ」という意味を持つと判る。

連言は、掛け算のような振舞を見せるので論理積（AND演算）とも呼ばれる。

選言の真理値表は以下のようになる。

$A$	$B$	$A\lor B$
$\top$	$\top$	$\top$
$\top$	$\bot$	$\top$
$\bot$	$\top$	$\top$
$\bot$	$\top$	$\bot$

この真理値表から、選言は「選言肢の一方は成り立つ」という意味を持つと判る。

連言は、足し算のような振舞を見せるので論理和（OR演算）とも呼ばれる。

ここで一行目の真理値に違和感を覚えた人もいるだろうが、日本語の接続詞「か」「又は」等は「選言肢が両方成り立つ場合を含む/含まない」両方の意味で用いられる。含まない方の選言を排他的選言（排他的論理和、XOR演算）、含む方の選言を非排他的選言（非排他的論理和）と呼んで区別する。

ちなみに、排他的選言の真理値表は以下のようになる。

$A$	$B$	$A{\underline {\lor }}B$ ^※
$\top$	$\top$	$\bot$
$\top$	$\bot$	$\top$
$\bot$	$\top$	$\top$
$\bot$	$\top$	$\bot$

※排他的選言の記号として、他に $\oplus$ を用いる流儀もある。

条件法の真理値表は以下のようになる。

$A$	$B$	$A\rightarrow B$
$\top$	$\top$	$\top$
$\top$	$\bot$	$\bot$
$\bot$	$\top$	$\top$
$\bot$	$\top$	$\top$

これは日本語の「ならば」と全く対応しないように思える。一行目に関していうと、例えば「1×0=0ならばカラスは黒い」という文が正しいということになる。三行目に関していうと、例えば「田中がテストを受けるならば100点である」は田中がテストを休めば自動的に正しいということになる。実は、日本語の「ならば」は真理関数的ではないのである。このままでは「ならば」「とき」のような仮定を含む命題は真理関数的ではないので命題論理で扱えないことになってしまうが、「真理関数的な論理結合子を用いる」という制約の下で日本語の「ならば」に近づくように条件法の真理値を定義することによって辛うじて仮定を含む命題の真偽を判定できるようになっている（と理解してくれればよい）。なお、「前件が偽であるとき後件が真」であることは、ベン図と空集合の考え方を用いて説明できる。詳細は数学Ⅰ「集合と論理」のページを参照。

後述するが、 $A\rightarrow B$ は $\lnot (A\land \lnot B)$ （「Aであり且つBでない」ということはない）と同値である。

つまり、条件法は「前件が成り立つ且つ後件が成り立たないということはありえない」という意味を持つと判る。

複合式の真理値表を書く際は、形成の木を描いた手順と同様にして論理式を分解し、原子式から逆に辿って元の式に向かって真理値表を埋めていく。

例えば、双条件法の真理値表は「 $(A\rightarrow B)\land (B\rightarrow A)$ 」を用いると以下のようになる。

$A$	$B$	$A\rightarrow B$	$B\rightarrow A$	$A\leftrightarrow B$
$\top$	$\top$	$\top$	$\top$	$\top$
$\top$	$\bot$	$\bot$	$\top$	$\bot$
$\bot$	$\top$	$\top$	$\bot$	$\bot$
$\bot$	$\top$	$\top$	$\top$	$\top$

つまり、双条件法は「左辺と右辺が一致する」という意味を持つと判る。

これらの論理結合子の真理値表は、論理結合子の意味から考えるよりも丸暗記した方がとっつきやすいだろう。

真理値表を用いることで、どんな複雑な複合式であっても（それが論理式である限り）真偽を判定することができる。このように、真理値表を用いて命題の真理値を調べ、真偽を判定することを真理値分析（ truth-value analysis, truth table analysis）という。

真理値は二値原理より2通りの値をとるので、複合式に含まれる原子式がn個であれば真理値表の行数は重複順列 ${}_{2}\Pi _{n}=2^{n}$ に等しい。

真理値表を書く際のコツとして、以下のようなものを紹介する。

①最初に原子式の種数を数え、それに応じた原子式の真理値の組み合わせを全て最左列に記入する

②より短い複合式から右の列に埋めていく。

③連言式の真理値を書くとき、原子式のどちらかが偽であればその時点で偽だと確定する。

④選言式の真理値を書くとき、原子式のどちらかが真であればその時点で真だと確定する。

⑤条件式の真理値を書くとき、前件が偽または後件が真であればその時点で真だと確定する。

真理値表を書いたとき、全ての行が真となる式を恒真式（トートロジー、tautology）、全ての行が偽となる式を矛盾式（contradiction）、それ以外の式を事実式（contingency）という。真となる行がある式を充足可能式（satisfiable）、ない式を充足不可能式（unsatisfiable）という。

有名な恒真式には名前が付されている。

同一律（law of identity）：

{\begin{aligned}A\rightarrow A\\A\leftrightarrow A\end{aligned}}

排中律（law of the excluded middle）：

A\lor \lnot A

矛盾律（law of non-contradiction）：

\lnot (A\land \lnot A)

二重否定律（再帰則、対合、reflexive low）：

\lnot \lnot A\leftrightarrow A

交換律（commutative law）：

{\begin{aligned}(A\land B)\leftrightarrow (B\land A)\\(A\lor B)\leftrightarrow (B\lor A)\end{aligned}}

結合律（associative laws）：

{\begin{aligned}\{A\land (B\land C)\}\leftrightarrow \{(A\land B)\land C\}\\\{A\lor (B\lor C)\}\leftrightarrow \{(A\lor B)\lor C\}\end{aligned}}

分配律（distributive laws）：

{\begin{aligned}\{A\land (B\lor C)\}\leftrightarrow \{(A\land B)\lor (A\land C)\}\\\{A\lor (B\land C)\}\leftrightarrow \{(A\lor B)\land (A\lor C)\}\end{aligned}}

ド・モルガンの法則（de Morgan's law）：

{\begin{aligned}\lnot (A\land B)\leftrightarrow (\lnot A\lor \lnot B)\\\lnot (A\lor B)\leftrightarrow (\lnot A\land \lnot B)\end{aligned}}

対偶律（contraposition）：

(A\rightarrow B)\leftrightarrow (\lnot B\rightarrow \lnot A)

恒真式であることを明示するための記号も存在するが、一階述語論理の知識が必要なためそちらで紹介する。

$A\land B\land C,A\lor B\lor C$ という式は論理式の公理に従えば論理式たりえないが、結合律よりこの複合式の真理値は括弧の位置に依らないのでこのような書き方も認めることにする。但し、 $A\land B\lor C,A\lor B\land C,A\rightarrow B\rightarrow C$ のような式は依然認められない。

恒真式は遍く場合に於いて真となる式である。これは情報としての価値を一切有さない。そのため、真に形式的/論理的な真理（formal/logical truth）である。

ある二つの論理式の真理値表が全く同じであるとき、これらの論理式は論理的に同値/等価/等値（logically equivalent）であるという。論理的に同値であることは、それらを結んだ双条件式が恒真式であることと全く同じである。

論理的に同値な式は、互いに置き換えることができる。ある論理式を論理的に同値な別の式に置き換える操作を同値変形（logical equivalence transformation）という。

同値変形には、上で列挙した恒真式群を用いる。これらは覚えてしまった方が便利だろう。

条件式について、前件と後件を入れ替えた式（元の命題の逆）と元の式は必ずしも同値とは限らない。同様に、前件と後件の否定をとった式（元の命題の裏）と元の式も同値とは限らない。それに対し、前件と後件を入れ替えてそれぞれ否定をとった式（元の命題の裏の逆、則ち対偶）は必ず元の式と同値である。このことは、真理値分析によって確かめられる。

真理値分析を用いることで、論証の妥当性を判定することもできる。

論証が妥当であるとは「前提が全て真ならば結論は必ず真」であることだった。同値変形すれば、「前提が全て真のとき結論が偽であることは決してない」となる。則ち、真理値表を書いたときに「前提となる論理式が全て $\top$ のとき結論となる論理式が $\bot$ であるか」を調べればよいことになる。このとき、結論となる論理式が $\bot$ であれば、それはその論証の反例である。

妥当性を判定するとき、真理値表をばらばらに書いても意味がない。必ず、前提・結論となる論理式を全て含んだ一つの真理値表を書く必要がある。

そのため、真理値表の最左列には、論証全体に現れる全ての原子式の数に応じて真理値の組を全て列挙する必要がある。

なお、結論が $\bot$ となる行が少ない場合、 $\bot$ となる行の左を見て前提の真理値が全て $\top$ であるかを見た方が手っ取り早い。

妥当な論証の代表例
- 肯定式（modus ponens）： $A\rightarrow B,A.\quad$ 故に $B.$
- 否定式（modustollens）： $A\rightarrow B,\lnot B.\quad$ 故に $\lnot A.$
- 選言的三段論法（disjunctive syllogism）： $A\land B,\lnot A.\quad$ 故に $B.$
- 推移律（transive law）： $A\rightarrow B,B\rightarrow C.\quad$ 故に $A\rightarrow C.$

妥当でない論証の代表例
- 前件否定の誤謬（denying the antecedent）： $A\rightarrow B,\lnot A.\quad$ 故に $\lnot B.$
- 後件肯定の誤謬（afirming the conseqent）： $A\rightarrow B,B.\quad$ 故に $A.$

この二つは、命題とその逆・裏との区別ができていないことから起こる誤謬である。

ある論理式群が矛盾するとは、「その論理式群が揃って $\top$ となることはない」ということである。

妥当な論証は「前提が全て真のとき結論が偽となることはありえない」論証であった。矛盾する論理式群は全てが同時に真とは決してならないので、互いに矛盾した論理式を前提に持つ論証は結論に関係なく妥当である。

ここまで、論理結合子の真理値表を用いて論理式の真理値を分析する方法、その応用として論理式の種類や論証の妥当性を判定する方法を学んできた。

今迄意図的に触れなかったが、論理結合子は上で扱った5つ（排他的選言を含めて6つ）である必要はあるのであろうか？

論理結合子として定義できるのはこの5(6)つのみではない。

例えば、「～でも…でもない」に対応する論理結合子を $\downarrow$ で表すことにすると、その真理値表は以下のようになる。

$A$	$B$	$A\downarrow B$
$\top$	$\top$	$\bot$
$\top$	$\bot$	$\bot$
$\bot$	$\top$	$\bot$
$\bot$	$\top$	$\top$

このように、 $\downarrow$ は真理関数的である。

而し、 $(A\downarrow B)\leftrightarrow (\lnot A\land \lnot B)$ であるように、任意の（二項演算を行う）論理結合子（ ${}^{2}2=2^{2^{2}}=16$ 通り）は $\lnot ,\land ,\lor$ の組み合わせで表現することができる。これは、任意個の論理式を $\lnot ,\land ,\lor$ で繋いでいけば任意の真理値を持つ真理関数を生成できることに依る。

では、論理結合子として必要な最小種数は $\lnot ,\land ,\lor$ の三つなのであろうか？答えは否である。

$A\land B,A\lor B$ は、ド・モルガンの法則より自身を除く他の二つを用いて表すことができる。

実は、論理結合子として必要な最低種数は一つなのである。

その一つが、上で述べた $\downarrow$ である。

$\downarrow$ のみで全ての真理関数を表せることを証明するには、 $\lnot ,\lor$ （又は $\lnot \land$ ）を $\downarrow$ のみで表せることを証明すれば充分である。自力で見つけるのは大変なので、答えを記しておく。

真理値表を書くことにより、 $\lnot A\leftrightarrow (A\downarrow A),\quad (A\land B)\leftrightarrow \{(A\downarrow A)\downarrow (B\downarrow B)\},\quad (A\lor B)\leftrightarrow \{(A\downarrow B)\downarrow (A\downarrow B)\}$ を証明できる。

他に、それ一つのみで他の真理関数を表せる論理結合子としては、「～且つ…ということはない」に対応する $\uparrow (|)$ が存在する。

$A$	$B$	$A\uparrow B$
$\top$	$\top$	$\bot$
$\top$	$\bot$	$\top$
$\bot$	$\top$	$\top$
$\bot$	$\top$	$\top$

$\downarrow$ は否定論理和（NOR演算）、 $\uparrow$ は否定論理積（NAND演算）と呼ばれ、論理回路では非常に重宝されている。

$\lnot ,\land ,\lor ,\downarrow ,\uparrow$ のように、限られた種数で全ての真理関数を表せる論理結合子の組は関数として完全（functional complete）であるという。

否定論理和・否定論理積はそれ単体で関数として完全である。この二つを、発見者の名前に因んでシェッファー・ストローク（Sheffer's stroke）と呼ぶ。

シェッファー・ストロークは片方のみが存在すれば全ての真理関数を表現するのに充分であるが、実用上の観点からは非常に扱いづらい。日常で用いられる様々な命題を論理式に直す際に便利（且つ関数として完全）な論理結合子の組として、 $\lnot ,\lor ,\land ,\rightarrow ,\leftrightarrow (,\oplus )$ が採用されているのである。

タブロー法

真理値分析は、原子式が増えれば増えるほど真理値の組み合わせが指数関数的に増大するのであまり使い勝手の良いものではない。

ここでは、厳密且つ単純で実用的な方法としてタブロー法（tableau method）を紹介する。

タブロー（tableau）ないし真理の木（truth tree）とは、ある論理式の真理値を仮定したとき、その仮定が成り立つのはその式に含まれるより単純な式がどのような真理値を持つ場合化を示す図である。

真理値を表す符号を付した論理式を符号付き論理式（signed logical formula）という。ここでは、符号付き論理式を用いたタブローを扱う。

タブローを作る操作は、真理値表を右から左へ読むことに対応する。

タブローでは、問題となる複合式が特定の真理値を持つ場合のみを扱う。そのため、真理値分析とは違い全パターンを網羅する必要はなく、実用的である。

タブローは、「符号付き論理式」「展開経路を表す線（枝）」「矛盾した枝を閉鎖（close）する×印」を基本部分とする。補助記号として、「符号付き論理式の左に付す通し番号」「符号付き論理式の右に付し、その論理式の根拠となる論理式を示す式番号」「展開し終わった論理式の通し番号の左に付す作業済みマーク☑」「閉鎖された枝の下に付す、その枝で互いに矛盾する論理式の式番号」も書かれる。

タブローの展開規則を以下に示す。但し、数式ツールの都合により本来のタブローとは異なる表現をした。

${\begin{array}{|c|c|c|c|}\hline [\top \lnot ]&[\top \land ]&[\top \lor ]&[\top \Rightarrow ]\\\hline {\begin{array}{c}\top :\lnot A\\\Rightarrow \bot :A\end{array}}&{\begin{array}{c}\top :A\land B\\\Rightarrow \top :A,\;\top :B\end{array}}&{\begin{array}{c}\top :A\lor B\\\Rightarrow \left\{{\begin{array}{l}\top :A\\\top :B\end{array}}\right.\end{array}}&{\begin{array}{c}\top :A\Rightarrow B\\\Rightarrow \left\{{\begin{array}{l}\bot :A\\\top :B\end{array}}\right.\end{array}}\\\hline [\bot \lnot ]&[\bot \land ]&[\bot \lor ]&[\bot \Rightarrow ]\\\hline {\begin{array}{c}\bot :\lnot A\\\Rightarrow \top :A\end{array}}&{\begin{array}{c}\bot :A\land B\\\Rightarrow \left\{{\begin{array}{l}\bot :A\\\bot :B\end{array}}\right.\end{array}}&{\begin{array}{c}\bot :A\lor B\\\Rightarrow \bot :A,\;\bot :B\end{array}}&{\begin{array}{c}\bot :A\Rightarrow B\\\Rightarrow \top :A,\;\bot :B\end{array}}\\\hline \end{array}}$

本来は、条件連立で書いてある部分は枝によって分岐し（枝分かれタイプ）、「,」で区切られて書いてある部分は分岐しないので上下に並べて書いていく（直接帰結タイプ）。

直接帰結タイプは分岐が存在しないので、その上の符号付き論理式は全て成り立つ。それに対し、枝分かれタイプは同一の枝に属する符号付き論理式のみ同時に成り立つ。タブローに於ける「矛盾」とは、同時に成り立つ符号付き論理式群の中に同じ論理式が異なる符号で存在することである。これは、「ある命題が真であって且つ偽である」という状態がありえないことに対応する。なお、枝分かれが複数存在する場合は、先に分岐した（閉鎖していない）枝のそれぞれで次の枝を展開する。

直接帰結タイプと枝分かれタイプは、真理値表でその真理値となる行の個数で分かれる。

タブローによる論証の解析には、背理法/帰謬法（proof by contradiction, RAA）が用いられている。

具体的には、「ある論理式（群）が特定の真理値を持つ」という仮定からタブローを書いていき、その過程でタブローが矛盾すれば「その論理式（群）がその真理値になることはありえない」ということができる。

全ての枝が閉じたタブローを閉じたタブロー（closed tableau）、全ては閉じていないタブローを開いたタブロー（opened tableau）という。タブローが矛盾するとは、タブローが閉じたタブローであることといえる。開いたタブローは閉じていない枝を持ち、その枝は仮定が成り立つ場合を示す。

論証が妥当であることを証明するには、「前提となる論理式が全て真且つ結論となる論理式が偽」という仮定からタブローを書き、タブローが矛盾することを示せばよい。

論理式が恒真式であることを証明するには、「その論理式が偽」という仮定からタブローを書き、タブローが矛盾することを示せばよい。

論理式群が矛盾することを証明するには、「その論理式群が全て真」という仮定からタブローを書き、タブローが矛盾することを示せばよい。

タブローを書くとき、同値変形は形成規則に含まれていないので行ってはいけない。但し、双条件法に限っては展開規則を導入していないので同値変形により条件法・連言の組み合わせに直すことが許される。

また、タブローの展開規則は主要結合子の展開規則である。例えば、「 $\top :\lnot (A\rightarrow B)$ 」という式に条件法が含まれているからといって、「 $\top :\rightarrow$ 」の規則を適用することはできない。形成の木を描いた時と同じように、一つ一つの論理結合子の階層を把握する必要がある。

タブローを簡潔に書くコツは、以下である。

①直接帰結タイプの符号付き論理式を優先して展開する。

②枝分かれタイプは、枝が早く閉じると判っている方を優先して展開する。

タブローを用いた論理的同値性の判定方法を紹介する。

論理式A, Bが論理的に同値であるとは、 $\top :A\land \bot :B,\top :B\land \bot :A$ がありえない、則ち「 $A.\quad$ 故に $B.$ 」「 $B.\quad$ 故に $A.$ 」という論証がどちらも妥当であることと言い換えられる。よって、「 $\top :A,\bot :B$ 」「 $\bot :A,\top :B$ 」をそれぞれ仮定に持つ二つのタブローを書いて調べればよい。真理値分析の節で「トートロジーと双条件法」の関係について述べたが、それを利用してタブローを書いても、結局は今述べた方法に帰着する。

タブロー法は強力な武器だが、それが信頼できる且つ強力である理由は、タブロー法の健全性と完全性に依る。

タブロー法の健全性

タブロー法によって妥当な論証/恒真式/矛盾式と判定されたものは、全て真に妥当な論証/恒真式/矛盾式である。

タブロー法の完全性

妥当な論証は全て、タブロー法によって妥当な論証と判定することができる。

証明

自然演繹法

この節は書きかけです。この節を編集してくれる方を心からお待ちしています。

補：公理的方法

この節は書きかけです。この節を編集してくれる方を心からお待ちしています。

演習問題

この節は書きかけです。この節を編集してくれる方を心からお待ちしています。

元の命題の裏と逆が論理的に同値であることを真理値分析により確かめよ。

論理学とは

論理式

真理値分析

タブロー法

自然演繹法

補：公理的方法

演習問題

関連書