意味論からの論理式-2【論理学をつくる #4】
読んでいるテキストはこちら。
前回の内容を簡単に復習しておく。
〇トートロジー：論理式自体の性質
〇論理的同値 ：論理式どうしの関係性
具体的には、
〇論理式Pがトートロジー
⇔ Pは、これに含まれる原子式の真理値の組み合わせに依らず恒に真理値が1になる論理式である
〇論理式PとQが論理的同値
⇔ PとQを構成する原子式のいかなる構成に対しても、PとQは恒に同じ真理値を取る
【定理5】
2つの論理式A, Bが論理的同値であるならば, 論理式A↔Bはトートロジーであるし, A↔Bがトートロジーであるならば, A, Bは論理的同値である。
定理5から、
〇論理式A, Bが論理的同値 ⇔ 論理式A↔Bはトートロジー
といえる。
§3.2 semanticsからの論証の妥当性
§3.2.1 論証の妥当性
さて。当初からの目的(の一つ)であった論証の妥当性validityとは、意味論semanticsの立場からすればどう解釈できるだろうか。
論証の結論がその前提から従う(Conclusion is followed by premise)というのは、当時の説明としてはひどく直感に訴えるものであった。
とはいえ、既にformという形でsemanticsへの橋渡しはできていて、それを以下見ていく。
復習がてら、以前に論証の「正しさ」の意味を考えるときに出した例を再掲。
例１．(正しくない論証)
A：空は青い
B：海は青い
*****************************
C：北半球では月は東から昇る
例２．(正しい論証)
D：人間は変温動物である
E：変温動物は体温が大きく変わる
*************************************
F：人間は体温が大きく変わる
semanticsの観点、即ちA, B, …, Fのformulaの真偽によってこれら2つの論証を分類すると、例１では前提も結論も正しいがそれは「たまたま」(誤謬推論)だと解釈した。例２では前提も結論も正しく、論証としても正しいとした。
では、例１に倣って次のようにしたものはどうだろう。
例１´．(正しくない論証)
A：空は青色だ
B：海は緑色だ
*****************************
C：北半球では月は東から昇る
これは、結論だけ見れば正しいことを言っている。
しかし、前提の中に偽の論理式(真理値が0になるようなformulaをこのように云うことにしよう)が入っていることに拠って、これを論証として正しいというのには抵抗がある。
これを排除するためには、次のようなformを与えてやればよいのではないか。
即ち、
【定義】
前提A_1, …, A_nから結論Cを導く論証が妥当である
⇔ A_1, …, A_n, Cを構成している原子式への真理値割り当てのうち, A_1, …, A_nを同時に1とし, Cを0とするようなものが存在しない。
ここで、A_1, …, A_nを同時に1とし, Cを0とするような真理値割り当てを、反例 counterexampleと呼ぶ。
即ち、妥当な論証(のform)とは反例の存在しないような論証である、とするのである。
こうすると、例１’の論証は妥当でなくなる。従って、「結論が正しい」ということは何ら論理学的に(日常的にも)意味を為さない。
一方で、例２の論証は妥当である。この場合、「結論が正しくない」というのは大きな意味を持っている。何故ならば、この論証が成功しなかった(失敗した)からである。その理由は、p.10のsucceedの定義から明らかなように、(1)の条件は満たしているが(2)が満たされていないことに拠る。このように、前提となるformulaの真理値が0になってしまうようなことを、事実誤認と呼ぶことがある。
つまり、妥当な論証と同じformを持っている論証に対して、その結論が正しくないときには、前提のどこかで間違った解釈をしてしまっているということである。これは、背理法にも繋がる大事な"発見"だろう。
結論が間違っていた場合に、もしそれが妥当な形式の論証であれば、前提としていた命題が間違っていたことが分かるではないか。
〇構成的両刀論法 constructive dilemma
A：P→R
B：Q→R
C：P∨Q
*********
D：R
のような形式の推論/論証を構成的両刀論法と呼ぶ。
また、これは数学的な証明では場合分けによる証明 proof by casesと呼ぶ。これに明らかなように、選言肢に連なる論理式はいくつであっても構わない。
〇Ex Falso Quodibet
タイトルの意味は、「偽からは何でもかんでも(出てくる)」。我々がここまでに整備した人工言語ℒで云えば、「矛盾した前提からは何でも出てくる」である。
何でも、というのは、結論に当たる論理式の真理値が0, 1の両方を取りうる、ということである。
前提の全ての論理式の真理値が1となるような割り当てが存在しないので、そもそも反例を探すことができないのである。
従ってこのように、矛盾した前提を持つ論証は妥当な論証となる。
§3.3 論理学の3つの顔（semanticsの観点）
【定理9】（論証の妥当性とトートロジー）
前提A_1, …, A_nから結論Cを導く論証が妥当である
⇔ 論理式(A_1∧…∧A_n)→Cがトートロジーである
(証明)
前提A_1, …, A_nから結論Cを導く論証が妥当である
⇔ 前提A_1, …, A_nから結論Cを導く論証が、反例を持たない
⇔ A_1, …, A_nの真理値が全て1で、Cの真理値が0となる真理値割り当ては存在しない
⇔ A_1∧ … ∧A_nの真理値が1で、Cの真理値が0となる真理値割り当ては存在しない
⇔ A_1∧ … ∧A_nの真理値が1ならば、Cの真理値は1である
⇔ (A_1∧…∧A_n)→Cは、如何なる真理値割り当てに対しても真理値は1
⇔ (A_1∧…∧A_n)→Cはトートロジーである□
尚、以下「前提A_1, …, A_nから結論Cを導く論証」を「A_1, …, A_n/C」と記すことにする。
【定理10】（論証の妥当性と論理的同値）
AとBが論理的に同値
⇔ 論証A/Bと論証B/Aがともに妥当
(証明)
AとBが論理的に同値
⇔ AとBを構成する原子式のいかなる構成に対しても、AとBは恒に同じ真理値を取る
⇔ A↔Bがトートロジーである (∵定理5)
⇔ (A→B)∧(B→A)がトートロジーである (∵同値変形)
⇔ (A→B)がトートロジーかつ、(B→A)がトートロジーである (∵∧の真理値表)
⇔ 論証A/Bが妥当かつ、論証B/Aが妥当である (∵定理9)□
【定理11】
前提A_1, …, A_nから結論Cを導く論証が妥当である
⇔ A_1, …, A_n, ¬Cは矛盾している
(証明)
前提A_1, …, A_nから結論Cを導く論証が妥当である
⇔ 前提A_1, …, A_nから結論Cを導く論証が、反例を持たない
⇔ A_1, …, A_nの真理値が全て1で、Cの真理値が0となる真理値割り当ては存在しない
⇔ A_1∧ … ∧A_nの真理値が1で、¬Cの真理値が1となる真理値割り当ては存在しない
⇔ A_1∧ … ∧A_n, ¬Cの真理値を同時に1とする真理値割り当ては存在しない
⇔ A_1∧ … ∧A_n, ¬Cは矛盾している□
【定理12】
論理式Aがトートロジー
⇔ ¬Aは矛盾
(証明)
論理式Aがトートロジー
⇔ Aを構成する原子式の任意の真理値割り当てで、Aの真理値は恒に1
⇔ Aを構成する原子式の任意の真理値割り当てで、¬Aの真理値は恒に0
⇔ ¬Aの真理値を1にするような真理値割り当てが存在しない
⇔ ¬Aは矛盾□
【定理13】
前提A_1, …, A_nから結論⊥を導く論証が妥当である
⇔ A_1, …, A_nは矛盾している
(証明)
前提A_1, …, A_nから結論⊥を導く論証が妥当である
⇔ 前提A_1, …, A_nから結論⊥を導く論証が、反例を持たない
⇔ A_1, …, A_nの真理値が全て1で、⊥の真理値が0となる真理値割り当ては存在しない
⇔ A_1, …, A_nの真理値が全て1となるような真理値割り当ては存在しない。 (∵⊥の真理値は恒に0)
⇔ A_1, …, A_nは矛盾している□
§3.4 2重ターンスタイル
前提A_1, A_2, …, A_nから結論Cが論理的に出てくる(logically follow)とは、前提A_1, A_2, …, A_nと結論Cを持つ論証が妥当であることをいうのだった。そして、論証が妥当であるとは反例が存在しないことだった。
この「論理的に出てくる」を「⊨」(2重ターンスタイル)で表して、「A_1, A_2, …, A_n ⊨ C」と書くことにしよう。
テキストでは、CがA_1, A_2, …, A_nの論理的帰結であることを表す、として導入されている。
【定義2】
Γ |= C ⇔ Γに含まれている式とCとを構成しているすべての原子式(これを簡単に「ΓとCに含まれる原子式」と言うことにする)への真理値割り当てのうち、Γに含まれるすべての式を同時に1とし、なおかつCを0とするような真理値割り当ては存在しない。
(注)
考える集合が空集合である場合を、以下に特別に定義しておく。
⊨ C ⇔ Cはトートロジーである
Γ ⊨ ⇔ Γは矛盾している
§3.5 真理関数
§3.5.1 1変数真理関数／2変数真理関数
ここでいう「変数 variable」とは、論理式 formulaのことを指す。
さて。1変数―つまり論理式が1つ―のときに、真理値がどのような値を取りうるかを考えよう。
関数とは、ある入力に対して特有の出力があるようなものをいう(お気持ち)ので、先ずは入力を考え、次いで出力を考えよう。
この場合の入力とは、与えられた論理式の真理値の集合だろう。
1変数の場合には、{0,1}という集合が定義域に対応し、この元が入力値となる。
そして、この入力に対して、出力として新しい真理値(論理式)を与えるような写像のことを真理関数 truth functionという。
具体的に、真理関数によって与えられる出力(真理値)を持つ論理式を見つけたとき、真理関数はこの論理式によって実現される(realise)／表現される(express)という。
(注)
1変数{1,0}→{1,0}の場合には、4通り(2×2=4)の真理関数をつくることができる。また2変数{1,0}^2→{1,0}の場合には、16通り(2×2×2×2)の真理関数をつくることができる。
例．
P, Qを論理式とする。これらへの真理値割り当てには、4パターンある。
P Q
1 1
1 0
0 1
0 0
結合子▲を用いて、これらから作られる論理式の真理値を考える。
それぞれの場合において、この対応を実現する論理式はテキストに詳しい。
(注)
それぞれに対して、真理関数を表現する論理式はuniqueに定まるとは限らない。しかし、1, 2変数の場合には、既に用意した結合子を用いて表現できることは注目に値する。このことを、それらの結合子は十全 adequateであるという。
§3.5.2 n変数真理関数
【定義】
{1,0}^nから{1,0}への関数をn変数の真理関数と言う。
数学的には、bool関数(Boolean function)という名前が付いている。全部で、2^n通りの真理関数が考えられる。
これらの真理関数を表すための結合子は一体いくつ必要なのだろうか。
これについて、以下の重要な定理がある。
【定理17】(表現定理, または関数的完全性の定理とも言う)
¬, ∧, ∨のみを結合子として含む論理式によって, n変数の真理関数はすべて表せる。
上の{¬, ∧, ∨}の集まりは、十全である adequateとか、関数的に完全functionally completeという。
では、どれだけの結合子があれば十全なのだろうか。その必要最小限の個数はどのくらいなのか。
それに対する答えが、次の節で説明される。
§3.5.3 Sheffer関数
〇Shefferの棒
Shefferの棒とは、先に§3.5.1で載せた表の②に対応する論理結合子である。
記号としては、「|」(縦棒)を用いて「nand」と呼ぶ。
十全な{¬, ∧}のいずれであってもShefferの棒｜を用いることで表すことができるので、Shefferの棒それ自体だけで十全になるのである！
(練習問題19)
(1) 「|」だけを用いて、P∨QとP→Qに論理的同値でなるべく簡単な式をそれぞれつくれ。
☞既存の論理式とShefferの棒を繋ぐ同値変形は、P|Q |==| ¬(P ∧ Q)
これを用いたい。
また注意すべきことは、¬P |==| ¬P ∨ ¬P |==| ¬(P∧P) |==| (P|P)のように変形できることである。
(解答例)
P∨Q |==| ¬(¬P ∧ ¬Q) |==| ¬P | ¬Q |==| (P|P) | (Q|Q) □
P→Q |==| ¬P∨Q |==| ¬(P ∧ ¬Q) |==| P | ¬Q |==| P | (Q|Q) □
〇Sheffer関数
一般に, 1つで十全であるような真理関数, つまりその真理関数だけを繰り返し使って他のすべての真理関数を生み出すことのできるような真理関数をシェーファー関数と言う。
【定理19】
2変数のシェーファー関数は, ｜と↓だけである。
「↓」は、先に§3.5.1で載せた表の⑫に対応する論理結合子である。「nor」と読む。
証明は、次回に譲ることにしよう。
今回は、ここまでとする。これで、テキストの第3章の３．１０あたりの内容までカバーしたことになる■