論理学
どの前提からどの結論が本当に導かれるかを研究する学問。
論理学は推論の中身ではなく形を扱う。形式論理は文を記号に置き換えるので、結論が導かれるかどうかは議論の形だけで決まり、機械的に検証できる。
論理学用語集
電卓・ガイド・練習問題で使われるすべての用語を、ひとところで定義しています。
用語を引き、記号を確かめ、例を電卓で開いて動きを見てください。ここで定義した用語は、ガイド本文に最初に現れたところで強調されます。
全62語
基礎
命題
真か偽のいずれかであり、両方ではない主張。
命題はちょうど一つの真理値をもつ平叙文である。「雨が降っている」は命題だが、疑問文や命令文は命題ではない。真偽を問える内容がないからである。
真理値
⊤ / ⊥命題が取りうる二つの値のいずれか、真または偽。
古典論理は各命題にちょうど一つの真理値を与える。記号では ⊤ と ⊥（あるいは 1 と 0）。真理値表の各行は変項への割り当てと、そこで式が取る値である。
原子命題
内部に結合子を一つも含まない命題。
原子命題はより小さい命題に分解できない。否定も連言もその他の結合子も含まない。それ以外はすべて複合命題であり、原子から組み立てられ、真理値は原子の真理値で決まる。
命題変項
任意の命題を表す p や A のような文字。
命題変項は任意の命題の置き場所である。電卓は一文字を変項として受け取り、各変項に真理値表の一列を与え、取りうる値の組み合わせごとに一行を作る。
電卓で試すp → q整式
その言語の文法が実際に許す記号列。
整式は規則に従って作られる。変項は整式であり、より小さい式を結合子でつないだものも整式である。「p ∧ ∨ q」はそうではないので、電卓は推測せずエラーを返す。
解釈
式に現れるすべての変項への真理値の割り当て。
解釈は各変項の値を定め、それによって式全体の値を決める。n個の変項をもつ式には 2ⁿ 個の解釈があり、それがちょうど真理値表の行である。
論証
結論を支持するために示された前提の集まり。
論証は、結論が前提から導かれると主張する。電卓では帰結記号を使って書く。前提を前、結論を後に置くと、前提が真で結論が偽になる行がないか各行が確かめられる。
電卓で試すp → q, p ⊨ q前提
結論に至るために論証が仮定する言明。
前提は論証の出発点である。妥当性が問うのは、すべての前提が成り立つところで結論も成り立つかどうかだけで、前提が実際に真かどうかは別問題であり、健全性が加える点である。
電卓で試すp → q, p ⊨ q結論
論証が確立しようとする言明。
結論は前提が支えようとするものである。電卓では帰結記号の後ろの式であり、前提を真にして結論を偽にする解釈が一つもないとき、その論証は妥当である。
電卓で試すp → q, p ⊨ q結合子
論理結合子
より単純な命題から複合命題を作る記号。
¬、∧、∨、→、↔ のような結合子は、命題どうしをつないでより大きな命題を作る。その真理値は部分の真理値だけで決まる。真理値表が記録するのはまさにこの依存関係で、入力の組ごとに一行になる。
否定
¬真理値を反転する。¬p は p が偽のときちょうど真。
否定は命題論理で唯一の一項結合子である。¬p、~p、!p と書かれ、真を偽に、偽を真に変える。したがって二度否定すればもとの命題に戻る。
電卓で試す¬p連言
∧両方の部分が真のときだけ真：p ∧ q。
連言は二つの部分（連言肢）をともに主張する。真理値表でちょうど一行だけ真になる。両方の連言肢が真である行であり、その意味で二項結合子のうち最も厳しい。
電卓で試すp ∧ q選言
∨少なくとも一方が真なら真：p ∨ q。
論理学の選言は包含的である。p が真のときも、q が真のときも、両方真のときも p ∨ q は真になる。両者が異なるときだけ真になる排他的な「または」は別の結合子である。
電卓で試すp ∨ q排他的選言
⊕二つの命題のうちちょうど一方が真のとき真。
排他的選言は ⊕ または XOR と書かれ、両者が異なるとき成り立ち、一致するとき成り立たない。双条件の否定であり、(p ∨ q) ∧ ¬(p ∧ q) とも書ける。
電卓で試す(p ∨ q) ∧ ¬(p ∧ q)条件法
→p → q。p が真で q が偽のときだけ偽。
実質条件法は「前件が真で後件が偽ではない」と言うだけなので、前件が偽ならば自動的に成り立つ。p → q が ¬p ∨ q と同値なのはそのためである。
電卓で試すp → q双条件法
↔p ↔ q。両方の部分の真理値が同じとき真。
双条件法は互いを条件として両辺を主張する。両方が真のときと両方が偽のときに真になる。恒真式である双条件法は、まさに論理的同値を述べたものである。
電卓で試すp ↔ q前件
条件法の「もし」の部分、p → q の p。
前件は条件法が依存する条件である。前件が偽であれば後件が何であれ条件法全体は真になり、→ の真理値表で意外に思える点のほとんどはここから来る。
電卓で試すp → q後件
条件法の「ならば」の部分、p → q の q。
後件は、前件が成り立つならば従うと条件法が述べているものである。後件が真なら条件法は真になるが、前件が真になるわけではない。そう推論するのは形式的誤謬である。
電卓で試すp → q逆
二つの部分を入れ替えた条件法：q → p。
p → q の逆は q → p であり、両者は同値ではない。電卓は一方が成り立ち他方が成り立たない行を見つける。両者を交換可能とみなすのは後件肯定である。
電卓で試すq → p対偶
¬q → ¬p。常に p → q と同じ真理値をもつ。
対偶は条件法の両方の部分を否定して入れ替える。逆とは違って原式と本当に同値であり、だからこそ数学で対偶による証明が正当なのである。
電卓で試す(p → q) ≡ (¬q → ¬p)否定論理積
↑連言の否定。両方の入力が真のときを除いて真。
否定論理積は ↑ と書かれ、¬(p ∧ q) である。関数的に完全で、他のどの結合子もこれだけで組み立てられるため、デジタル回路設計の主役になっている。
電卓で試す¬(p ∧ q)否定論理和
↓選言の否定。両方の入力が偽のときだけ真。
否定論理和は ↓ と書かれ、¬(p ∨ q) である。NAND と同じくそれ自体で関数的に完全なので、回路を NOR ゲートだけで組み上げることもできる。
電卓で試す¬(p ∨ q)演算子の優先順位
括弧が省かれたとき、どの結合子が先に効くか。
最も強く結びつくのは否定、次いで連言、選言、条件法、最後に双条件法である。したがって ¬p ∧ q ∨ r は ((¬p) ∧ q) ∨ r と読む。意図した読みが違うときは括弧で順序を変える。
電卓で試す¬p ∧ q ∨ r真理と帰結
真理値表
割り当てごとに一行を取り、そこでの式の値を示す表。
真理値表は式のn個の変項に対する 2ⁿ 通りの解釈をすべて並べ、それぞれで式の値を計算する。網羅的であるがゆえに、同値・妥当性・充足可能性など命題論理の意味論的な問いをすべて決着させる。
電卓で試すp → q恒真式
⊤どの解釈のもとでも真になる式。
恒真式は真理値表のどの行でも真になるので、世界について何も語らない。p が何であれ p ∨ ¬p は真である。二つの式が同値であるのは、その双条件法が恒真式であるときちょうどである。
電卓で試すp ∨ ¬p矛盾式
⊥どの解釈のもとでも偽になる式。
p ∧ ¬p のような矛盾式は真理値表のどの行でも偽である。仮定の集まりから矛盾を導けば、それらがすべて同時には成り立たないと示せる。背理法の原動力である。
電卓で試すp ∧ ¬p偶然式
ある解釈では真、別の解釈では偽になる式。
偶然式は恒真式でも矛盾式でもない。真理値表に真の行と偽の行が少なくとも一つずつある。人が書く式のほとんどは偶然式であり、だからこそ情報をもつ。
電卓で試すp ∧ q充足可能性
式を真にする解釈が存在するかどうか。
真理値表の行が少なくとも一つ真であれば、その式は充足可能であり、その行はモデルである。充足可能性の判定は SAT ソルバーの中心問題であり、ひいては自動推論の多くを支えている。
電卓で試すp ∧ (p → q)論理的同値
≡真理値表が完全に一致する二つの式。
同値な式はどの解釈でも一致するので、意味を変えずにどこでも置き換えられる。二つの式のあいだに等号を書けば、電卓が列を行ごとに比べてくれる。
電卓で試す(p → q) ≡ (¬p ∨ q)論理的帰結
⊨前提が成り立つどの解釈でも結論が成り立つこと。
Γ ⊨ φ と書かれる論理的帰結は、妥当な論証が主張していることそのものである。確かめ方は反例探し、すなわちすべての前提を真にし結論を偽にする解釈を探すことで、それが無ければ帰結は成り立つ。
電卓で試すp → q, p ⊨ q妥当性
前提を真にし結論を偽にする解釈が一つもないこと。
妥当性は事実ではなく論証の形の性質である。妥当な論証が偽の前提と偽の結論をもつことはありうる。ありえないのは、真の前提と偽の結論が並ぶことである。
電卓で試すp → q, p ⊨ q健全性
前提も実際に真である妥当な論証。
健全性は形式的な主張に事実の主張を加える。論証は妥当であり、かつその前提が成り立つ。前半は論理だけで決まるが、後半は論証が扱う事柄に属する。
反例モデル
前提を真にし結論を偽にする解釈。
反例モデルは論証が非妥当であることの証拠であり、一行あれば足りる。電卓は見つけた行を示すので、「それは導かれない」という指摘が手で確かめられる具体的な割り当てになる。
電卓で試すp → q ⊨ q → p無矛盾性
集合内のすべての言明を同時に真にする解釈があること。
前提の集合は、それらがすべて同時に成り立ちうるとき無矛盾である。矛盾した前提からは何でも導かれるので、その上に立つ論証は形式的には妥当でも何の値打ちもない。
電卓で試すp → q, ¬q ⊨ ¬p標準形
リテラル
変項またはその否定。p や ¬p など。
リテラルは標準形の原子である。節はリテラルの選言、最小項はリテラルの連言である。変項がそのまま現れるリテラルは正、否定されているものは負と呼ばれる。
電卓で試す¬p節
リテラルの選言。たとえば p ∨ ¬q ∨ r。
節は連言標準形を構成する括弧のまとまりの一つである。連言はすべての部分が真のときだけ真なので、CNF の式は各節が成り立つときちょうど成り立つ。
電卓で試すp ∨ ¬q ∨ r選言標準形
AND の OR、すなわちリテラルの連言の選言。
どの式にも選言標準形があり、真理値表からそのまま読み取れる。真になる行ごとに連言を作り、∨ でつなげばよい。電卓は最小化した DNF も示し、より少ないリテラルで同じことを述べる。
電卓で試す(p ∧ q) ∨ (¬p ∧ r)連言標準形
OR の AND、すなわち節の連言。
連言標準形は真理値表の偽の行から、行ごとに一つの節として読み取る。SAT ソルバーが前提とする入力形式であり、そのため CNF への変換は自動推論の定石になっている。
電卓で試す(p ∨ q) ∧ (¬p ∨ r)最小項
真理値表のちょうど一行を指定する連言。
最小項は各変項を否定つきか否定なしで一度ずつ含むので、ちょうど一つの解釈だけがそれを満たす。真の行の最小項を集めて ∨ でつなげば、その式の選言標準形になる。
電卓で試すp ∧ ¬q ∧ r最大項
真理値表のちょうど一行を排除する選言。
最大項は各変項を一度ずつ含み、ただ一つの解釈でのみ偽になる。偽の行ごとに最大項をとり ∧ でつなげば、その式の連言標準形になる。
電卓で試すp ∨ ¬q ∨ rド・モルガンの法則
否定は ∧ を ∨ に、∨ を ∧ に変える：¬(p ∧ q) ≡ ¬p ∨ ¬q。
ド・モルガンの法則は否定を連言や選言の内側へ押し込み、その途中で結合子を入れ替える。式を標準形へ近づける手立てであり、コードや回路で否定を簡単にする手立てでもある。
電卓で試す¬(p ∧ q) ≡ ¬p ∨ ¬q二重否定
二度否定するともとに戻る：¬¬p ≡ p。
古典論理では二重否定が両方向に成り立つので、¬¬p と p はいつでも置き換えられる。直観主義論理は p から ¬¬p への向きだけを残し、そこで両者は袂を分かつ。
電卓で試す¬¬p ≡ pブール代数と回路
ブール代数
二つの値の代数で、演算は ∧、∨、¬。
ブール代数は命題論理を 0 と 1 の算術として書いたものである。交換法則、分配法則、吸収法則、ド・モルガンの法則によって式を書き換え簡単にできる。デジタル回路はこの数学で設計される。
電卓で試す(p ∧ q) ∨ (p ∧ ¬q) ≡ pカルノー図
簡単化が目で見える形に並べ替えた真理値表の格子。
カルノー図は隣り合うマスが一つの変項だけ異なるように行を並べ、端は反対側とつながる。K図、K-map、kmap とも書かれる。大きさ 1、2、4、8 の隣接する 1 の長方形が、最簡の式の項としてそのまま読み取れる。
電卓で試す(p ∧ q) ∨ (p ∧ ¬r)主項
図の上でこれ以上大きくできないまとまり。
含意項は式を真にするリテラルの連言であり、どのリテラルを外してもそうでなくなるとき主項と呼ばれる。カルノー図では、主項は 1 からなる極大の長方形である。
必須主項
ある 1 を覆う唯一の主項。
図のある 1 が極大のまとまり一つにしか属さないなら、そのまとまりはどの最小被覆にも入らねばならないので先に取る。残った部分こそ、本当に探索すべき被覆である。
論理ゲート
入力に対して一つの結合子を計算する回路素子。
AND、OR、NOT、NAND、NOR、XOR の各ゲートは結合子のハードウェア版である。式と回路は同じものを二通りに描いたものなので、電卓は式をゲート図として表示できる。
電卓で試す(p ∧ q) ∨ ¬r証明と推論
推論規則
すでに得た式から新しい式へ進む、許された一歩。
推論規則は前件肯定のような型であり、適切な形の式が手元にあればいつでも適用できる。証明体系はそうした規則をわずかに選んで組み立てられ、帰結する結論しか導けないようになっている。
前件肯定
p → q と p から q を導く。
前件肯定は条件法の基本規則である。条件法とその前件があれば後件が従う。妥当性は真理値表で見て取れる。両方の前提が真である唯一の行では、結論も真になっている。
電卓で試すp → q, p ⊨ q後件否定
p → q と ¬q から ¬p を導く。
後件否定は条件法を逆向きにたどる。後件が成り立たないなら前件も成り立ちえない。対偶が働いているのであり、予測を試して仮説を退けるあらゆる議論の形でもある。
電卓で試すp → q, ¬q ⊨ ¬p仮言三段論法
p → q と q → r から p → r を導く。
仮言三段論法は条件法どうしをつなぐ。長い導出が可能になるのはこれのおかげで、鎖の一つひとつが前提を主張することなく議論を一歩ずつ先へ運ぶ。
電卓で試すp → q, q → r ⊨ p → r選言三段論法
p ∨ q と ¬p から q を導く。
選言三段論法は消えた選択肢を取り除く。二つのうち一方が成り立ち、最初の方が成り立たないなら、残りが成り立たねばならない。消去法による推論を支える規則である。
電卓で試すp ∨ q, ¬p ⊨ q自然演繹
推論規則を一歩ずつ適用して結論を証明すること。
自然演繹は各結合子の導入規則と除去規則によって前提から結論を導き、一時的な仮定を置いて後で解消することを許す。真理値表が確かめることを、全行を並べずに証明する。
背理法
反対を仮定し、矛盾を導き、もとの主張を結論する。
φ を証明するには ¬φ を仮定し、ψ ∧ ¬ψ の形のものを導く。矛盾を真にする解釈は存在しないので仮定は成り立たず、φ が従う。無理数性や無限性の証明はたいていこの形をとる。
電卓で試すp ∧ ¬p後件肯定
p → q と q から p へ進む非妥当な一歩。
後件が真でも前件が確立されるわけではない。別の何かがそれを引き起こしたかもしれない。電卓は反例モデル（p が偽、q が真）を示す。これが前件肯定と分かれる行である。
電卓で試すp → q, q ⊨ p前件否定
p → q と ¬p から ¬q へ進む非妥当な一歩。
条件法は前件が成り立たない場合について何も述べていないので、前件を退けても後件は未定のままである。反例モデルは p が偽で q が真である行である。
電卓で試すp → q, ¬p ⊨ ¬q命題論理の先へ
述語論理
命題の内側、対象とその性質まで見る論理。
述語論理は述語・項・量化子を加えるので、「2 より大きい素数はすべて奇数である」が一文字ではなく一つの式になる。命題論理より厳密に表現力が高く、真理値表では決定できない。
量化子
∀ / ∃述語が何個の対象に成り立つかを述べる記号。
古典的な量化子は ∀（すべて）と ∃（少なくとも一つ）で、いずれも中身を否定したもう一方の否定である。量化子が束縛する変項こそ、述語論理を命題論理から分ける点である。
全称量化子
∀∀x φ：領域のどの対象についても φ が成り立つ。
全称的な主張は反例が一つあれば覆り、空の領域では空虚に成り立つ。∀x φ は ¬∃x ¬φ と同値であり、これは量化子におけるド・モルガンの法則にあたる。
存在量化子
∃∃x φ：領域の少なくとも一つの対象について φ が成り立つ。
存在の主張は証人を一つ示せば確立できる。∃x φ は ¬∀x ¬φ と同値なので、どちらの量化子ももう一方と否定から定義できる。
様相論理
□ / ◇「必然的に」（□）と「可能的に」（◇）を加えた論理。
様相論理は式を単一の解釈ではなく可能世界で評価する。到達可能なすべての世界で φ が成り立てば □φ、いずれかの世界で成り立てば ◇φ が成り立つ。「到達可能」の意味を変えると異なる様相体系が得られる。