提供: Internet Web School

2020年11月30日 (月) 15:25時点における版

演繹推論

演繹的推論は論理的思考の根幹である.

簡単な例を挙げる。

• (1)人間の髪の毛の本数は100万本以下である.
• (2)東京都民の人口は1200万人である.

これらの命題が正しければ

• (3)東京都民のうち少なくとも2人は髪の毛の本数は同じである.

この命題の正しさを示すには背理法による.

命題(3)の否定が成り立つものとする。

命題(3)は厳密に書くと

　「東京都民A,Bがいて,A,Bは同一人物でなくかつA,Bの髪の毛の本数は同じ」

である．

このこの命題の否定は

• (4)任意の東京都民A,Bについて,A,Bが同一人物でなければ　A,Bの髪の毛の本数は等しくない．

である.

ここでは(4)が正しいと仮定している．

東京都民一人一人にその人自身の髪の毛の本数によって背番号を振ることを考える. 例え ば毛の本数が0本の人には背番号0を，1000本の人には背番号1000を振る。

都民全員に付与した背番号は(4)の仮定により誰一人として同じものはなく, 一人一人に唯一の背番号が振られる.

「(1)人間の髪の毛の本数は100万本以下である.」が正しいとしているから 振られる番号は0番から100万まででの100万+1通りである.

都民全員に付与した背番号はそれぞれに唯一であるから 都民全員の数は100万人+１人である.

しかしこれは「(2)東京都民の人口は1200万人である.」に矛盾する.

この矛盾は 命題「東京都民のうち少なくとも2人は髪の毛の本数は同じである.」

の否定が成り立つとしたことによっている.

従って「東京都民のうち少なくとも2人は髪の毛の本数は同じである.」が正しい.

上記の　命題(1),(2)が正しければ命題(3)が正しいことを論証した過程は 論理の連鎖に依っている.命題(3)を否定した命題が正しいとして論理の連鎖を つくり,矛盾を導くことによって命題(3)の正しさを証明した.

演繹推論はこのように,正しいもとして与えられた命題から厳密な論理を 繰り返し適用することによって新たな命題を結論として導き出す.

この過程(証明)は,その論証の過程に出てくる命題やそれに施す論理的な推論を計算機によって処理できる形式化された記述で書けば,計算機によってその正しさを検証できる.それを形式化を行うかどうかは別として計算機による検証で正しさが認められるものでなければ完全な演繹推論とは言えない.

実際,以下は定理証明支援系のMizarによって上記の推論を記述したものである. Mizarのような定理証明支援系あるいは形式化証明検証システムでは,命題は全て記号列であり,三段論法その他の推論規則はそれらの複数の記号列を操作して 別の新たな記号列を構成する規則に過ぎない.証明は,前提となる命題(記号列)から出発して,目的の命題(記号列)に至る,推論規則により 生成された記号列の列にに過ぎない.

特に,A.I.　や　ICTの進歩など数学を含む科学技術の進歩の激流の中にある,科学工学の技術者はMizarのようなシステムの操作にも慣れ親しむことが必要になってくる.

environ

 vocabularies NUMBERS, REAL_1, FINSEQ_1, VALUED_0, XBOOLE_0, NEWTON, ARYTM_3,
      RELAT_1, NAT_1, XXREAL_0, ARYTM_1, SUBSET_1, CARD_1, CARD_3, ORDINAL4,
      TARSKI, INT_2, FUNCT_1, FINSEQ_2, PRE_POLY, PBOOLE, FINSET_1, XCMPLX_0,
      UPROOTS, FUNCT_2, BINOP_2, SETWISEO, INT_1, FUNCOP_1, NAT_3, XREAL_0;
 notations TARSKI, XBOOLE_0, SUBSET_1, FINSET_1, ORDINAL1, CARD_1, NUMBERS,
      XCMPLX_0, XXREAL_0, XREAL_0, REAL_1, NAT_D, INT_2, RELAT_1, FUNCT_1,
      FUNCT_2, FINSEQ_1, FINSEQ_2, VALUED_0, PBOOLE, RVSUM_1, NEWTON, WSIERP_1,
      TREES_4, BINOP_2, FUNCOP_1, XXREAL_2, SETWOP_2, PRE_POLY;
 constructors BINOP_1, SETWISEO, NAT_D, FINSEQOP, FINSOP_1, NEWTON, WSIERP_1,
      BINOP_2, XXREAL_2, RELSET_1, PRE_POLY, REAL_1,CARD_1;
 registrations XBOOLE_0, RELAT_1, FUNCT_1, FINSET_1, NUMBERS, XCMPLX_0,
      XXREAL_0, NAT_1, INT_1, BINOP_2, MEMBERED, NEWTON, VALUED_0, FINSEQ_1,
      XXREAL_2, CARD_1, FUNCT_2, RELSET_1, ZFMISC_1, FINSEQ_2, PRE_POLY,
      XREAL_0, RVSUM_1;
 requirements NUMERALS, SUBSET, ARITHM, REAL, BOOLE;
 definitions TARSKI, XBOOLE_0, INT_2, NAT_D, FINSEQ_1, VALUED_0, 
    PRE_POLY,FINSET_1,CARD_1;
 theorems ORDINAL1, NEWTON, NAT_1, XCMPLX_1, INT_1, CARD_4, XREAL_0, RVSUM_1,
      INT_2, PEPIN, FUNCT_1, CARD_2, PREPOWER, FINSEQ_1, TARSKI, XBOOLE_1,
      FUNCOP_1, WSIERP_1, XBOOLE_0, FINSEQ_2, FINSEQ_3, FINSEQ_4, RELAT_1,
      FINSOP_1, FUNCT_2, XREAL_1, XXREAL_0, NAT_D, VALUED_0, XXREAL_2,
      FINSET_1,PARTFUN1, PRE_POLY, CARD_1;
 schemes NAT_1, PRE_CIRC, FINSEQ_1, FINSEQ_2, PBOOLE, CLASSES1;

begin


now 
 let 
  Humankind be finite set, 
  Tokyoite be Subset of  Humankind,
  Numberofhair be  Function of Tokyoite,NAT ;


assume  LM1:
  card (Tokyoite) = 12*10|^6;
assume  LM2:
  for x be object 
     st x in Tokyoite 
  holds Numberofhair.x <= 10|^6;


LM0:
  10|^6 + 1 < 12*10|^6
proof
0 < 10|^6 by PREPOWER:6;
then
P2: 1*10|^6 < 11* 10|^6 by XREAL_1:68;
P3: 1 <  10 & 2 <= 6;
then
10 < 10 |^6 by PREPOWER:13;
then
1 < 10 |^6 by XXREAL_0:2,P3;
then
1 < 11*10|^6 by P2,XXREAL_0:2;
then
P4: 1*10|^6 + 1 < 1*10|^6 + 11*10|^6 by XREAL_1:8;
1*10|^6 + 11*10|^6 = (1+11)*10|^6  ;
hence thesis by P4;
end;


LM3:
  card (rng Numberofhair) <= 10|^6+1 
proof
 now let y be  object ;
   assume
   y in  rng Numberofhair;
   then
   consider  x be object 
     such that 
    A1: x in Tokyoite & y=Numberofhair.x   by FUNCT_2:11;
   Numberofhair.x <= 10|^6 by A1,LM2;
   then 
   Numberofhair.x < 10|^6+1 by NAT_1:16,XXREAL_0:2;
   then
   Numberofhair.x  in Segm (10|^6+1) by NAT_1:44,A1;
   hence 
   y in Segm (10|^6+1) by A1;
end;
then
A2: rng Numberofhair
   c= Segm (10|^6+1) by TARSKI:def 3;
 then
 card rng Numberofhair <= card Segm (10|^6+1) by NAT_1:43;
 then
 card rng Numberofhair <= card (10|^6+1) by ORDINAL1:def 17;
 hence 
 card rng Numberofhair <= (10|^6+1)  ;
end;

LM4:
card (rng (Numberofhair)) 
 < card  (Tokyoite) 
proof
reconsider N1= card (rng (Numberofhair)) 
 as Element of NAT ;
reconsider N2= card (Tokyoite) 
 as Element of NAT ;
A1: N1<=(10|^6+1) & N2=12*10|^6 by LM1,LM3;
then  
N1 < N2 by A1,XXREAL_0:2,LM0;
hence thesis ;
end;


EX:
  ex x,y be object  
    st x in Tokyoite 
       & y in Tokyoite 
       & x <> y   
       & Numberofhair.x = Numberofhair.y 

proof
assume 
A1: 
  not 
    (  ex x,y be object 
    st x in Tokyoite 
       & y in Tokyoite 
       & x <> y   
       & Numberofhair.x = Numberofhair.y ) ;

 then
A2:  for x,y be object 
    st x in Tokyoite 
       & y in Tokyoite 
       & x <> y   
     holds  
       Numberofhair.x <> Numberofhair.y  ;

A3: dom Numberofhair = Tokyoite by FUNCT_2:def 1;
then
for x,y be object st x in dom Numberofhair 
             & y in dom Numberofhair 
             & Numberofhair.x = Numberofhair.y 
      holds x = y by A2;
then
Numberofhair is one-to-one by FUNCT_1:def 4;
then
card  (dom Numberofhair) = card (rng Numberofhair) 
  by CARD_1:70;
then
card  (Tokyoite) = card (rng (Numberofhair)) 
  by A3;
hence contradiction by LM4;
end;
end;
   

公理系と推論

論理式

真」とする複数の命題から論理的操作をして,「真」である 命題を導き出す演繹推論は代数的演算のような扱いができる.

「真」　「偽」 「～でない」　「かつ」　「または」　「ならば」 をそれぞれ$\top$ および $\bot$　$\neg, \land, \lor, \Rightarrow$で表し, 命題と命題との「演算」とみなす.それらの「演算」の結果得られる ものを論理式と呼ぶがこれを以下のように以下のように 再帰的に定義される.

• $\top$ および $\bot$ は命題論理における論理式である。

• 個々の命題変数は命題論理における論理式である。

• $\cal A$ が論理命題における論理式ならば、$\neg\cal A$ は命題論

理における論理式である。

• $\cal A,B$ が命題論理における論理式ならば、

$\cal A \land B, A \lor B, A \Rightarrow B$ は、いずれも命題論理における論理式である。

• 以上によって定まるもののみが命題論理における論理式である。

命題論理における論理式の全体を $\bf L$ と書くことにしよう。

$\bf L$ の要素である論理式は、いずれもその論理式を表現としてもつ真理 関数と考えられる。任意の真理関数は、その独立変数がとり得る値のとり方 ($n$ 変数ならば $2^n$ 通り)の各々の場合について、有限回の操作でその 値(関数値)を決定できる。

$\bf L$ の論理式の値(真理関数とみなした場合の関数値)が、(命題変数の 値のとり方のすべてに対して)つねに $\top$ であるとき、そのような論理 式を{\gt 恒真論理式}(tautology)という。

命題計算

公理系と呼ばれる $\bf L$ の部分集合 $\bf A$ と推論規則が適当に定めら れ、恒真論理式が $\bf A$ から推論規則によって導けるような体系を、 {\gt 命題論理の公理的体系}、あるいは{\gt 命題計算の体系}という。

いろいろな公理的体系が知られているが、ここではヒルベルト(D. Hilbert) 流のものを挙げておこう。

以下、$\cal A,B,C$ は任意の $\bf L$ の要素とする。 {\gt 公理系 A} として、次の $(1) \sim (15)$ をとる。

• $\cal A \Rightarrow A$
• $\cal (A \Rightarrow B) \Rightarrow [(B \Rightarrow C) \Rightarrow (A \Rightarrow C)]$
• $\cal A \Rightarrow (A \lor B)$
• $\cal B \Rightarrow (A \lor B)$
• $\cal (A \Rightarrow C) \Rightarrow \{ (B \Rightarrow C) \Rightarrow [(A \lor B) \Rightarrow C]\}$
• $\cal (A \land B) \Rightarrow A$
• $\cal (A \land B) \Rightarrow B$
• $\cal (C \Rightarrow A) \Rightarrow \{ (C \Rightarrow B) \Rightarrow [C \Rightarrow (A \land B)]\}$
• $\cal [A \land (A \Rightarrow B)] \Rightarrow B$
• $\cal [(A \land C) \Rightarrow B] \Rightarrow [C \Rightarrow (A \Rightarrow B)]$
• $\cal (A \land \neg A) \Rightarrow \bot$
• $\cal [(A \land B) \Rightarrow \bot ] \Rightarrow (B \Rightarrow \neg A)$
• $\cal A \Rightarrow \top$
• $\cal \bot \Rightarrow A$
• $\cal A \lor \neg A$

{\gt 推論規則}は、次の三段論法(modus ponens)のみである。横線の上の論 理式から下の論理式が導かれることを表わす。 $\frac{\cal A \quad A \Rightarrow B}{\cal B}$

証明可能性を定義する。すなわち、$\bf L$ の要素である論理式のうち、 {\gt 証明可能な論理式}(provable formula)を次のように定める:

• 公理系の各公理の形の論理式は証明可能である。
• 論理式 $\cal A$ と論理式 $\cal A \Rightarrow B$ が証明可能なら

ば、(推論規則によって、)論理式 $\cal B$ は証明可能である。

• 以上によって定まるものだけが、証明可能な論理式である。

演繹定理

証明可能な論理式の列を「証明」という。「証明可能性」の定義に従えば

${\cal A}_1,{\cal A}_2, \cdots,{\cal A}_n$

が「証明」のとき。各${\cal A}_i$は

• 公理系の各公理の形の論理式である。
• 論理式${\cal A}_i$

の前に

論理式${\cal A}_j$

と

\({\cal A}_k (j,k 6 \Rightarrow 2>6 \\ ( 1=2 \land 2>6 \Rightarrow 2>6) \Rightarrow (2>6 \Rightarrow (1=2 \Rightarrow 2>6)) \\ 2>6 \Rightarrow ( 1=2 \Rightarrow 2>6) $は証明である。（証明可能な論理式を「定理」とか「命題」と呼ぶこともある。） 「証明」の中で推論規則と公理を何回か適用する共通した手順を「推論法則」 と呼ぶ。（これ自身は公理系を定義するのに必須ではないが、それを操作する 上で便利な手続きをまとめたもの。） **[例]$ \frac{\cal A }{\cal B \Rightarrow A} \qquad (推論法則：添加) \cal A$が証明可能な論理式ならば$\cal B \Rightarrow A$も 証明可能な論理式であることを表す。 (上の「証明」の例に現れている。)$ \frac{\cal A,B }{\cal A \land B} \qquad (推論法則：論理積) $任意の論理式$\cal C$を用いて「添加」により$ \cal (C \lor \lnot C ) \Rightarrow A,(C \lor \lnot C ) \Rightarrow B $が得られる。また$(8)$であるから$ \cal \{ (C \lor \lnot C) \Rightarrow A \} \Rightarrow [ \{ (C \lor \lnot C) \Rightarrow B \} \Rightarrow \{ (C \lor \lnot C) \Rightarrow (A \land B ) \} ] $推論規則により、$ \cal (C \lor \lnot C) \Rightarrow (A \land B ) $が得られる。ところで$(15)$により$ \cal C \lor \lnot C $は公理（当然証明可能な論理式であるから） 結局$ \cal A \land B $は証明可能な論理式である。$\Box$またこれから直ちに$ \frac{\cal A \land B }{\cal B \land A} \qquad (推論法則：交換) $が得られる。 同様に$ \frac{\cal A \lor B }{\cal B \lor A} \qquad (推論法則：交換) $も得られる。さらに$ \cal A \Rightarrow \lnot \lnot A,\lnot \lnot A \Rightarrow A 「２重否定」 $も得られる。$ \frac{ \cal A \Rightarrow B ,B \Rightarrow C } {\cal A \Rightarrow C}(推論法則：推移) $これは$(2)$より$ \cal (A \Rightarrow B) \Rightarrow [(B \Rightarrow C ) \Rightarrow (A \Rightarrow C) ] $が得られ、これと$ \cal A \Rightarrow B $から推論規則により、$ \cal (B \Rightarrow C ) \Rightarrow (A \Rightarrow C) $を得る。さらにこれと$ \cal B \Rightarrow C $とから$ \cal A \Rightarrow C $が得られることで示される。$\Box$%% %% 同様に$ \frac{ \cal A \Rightarrow (B \Rightarrow C) ,A \Rightarrow B } {\cal A \Rightarrow C}　(推論法則：復推移) $が得られる。これはまず、$(8)$から$ \cal (A \Rightarrow B) \Rightarrow [ \{ A \Rightarrow (B \Rightarrow C) \} \Rightarrow \{A \Rightarrow B \land (B \Rightarrow C) \} ] $これと$ {\cal A \Rightarrow (B \Rightarrow C) , A \Rightarrow B} $から$ {\cal A \Rightarrow \{ B \land (B \Rightarrow C) \} } $が得られ さらに$(9)$の$ {\cal \{B \land (B \Rightarrow C)\} \Rightarrow C } $と前述の「推移」により$ \cal A \Rightarrow C $が得られることで示される。$\Box$上述の体系を$H$と呼ぶことにしよう。（$H = 公理系 ${\bf A}$ + 「推論規則」$）$\bf L$の論理式$\cal A$が証明 可能であるとは、$H$において、公理系$\bf A$から$\cal A$が推論規 則によって導けることであるから、これを$ \vdash_H \cal A $と書く。推論規則$ \frac{\cal A \quad A \Rightarrow B}{\cal B} $はこの表記法を用いると、$ \frac{\vdash_H \cal A \quad \vdash_H A \Rightarrow B}{\vdash_H \cal B} $と書くべきである。しかし、どの系で証明可能なのか明らかな場合は$\vdash_H$は省略することにする。 =演繹定理= 上の体系$H$についてその公理系${\bf A}$に論理式$ {\cal A}_1,{\cal A}_2,\cdots,{\cal A}_n $を追加してできる新たな系で 論理式$\cal B$が証明可能であるとき、このことを$ {\cal A}_1,{\cal A}_2,\cdots,{\cal A}_n \vdash_H \cal B $で表す。さらにこのとき：$ {\cal A}_1,{\cal A}_2,\cdots,{\cal A} _{n-1} \vdash_H {\cal A}_n \Rightarrow {\cal B} $が成り立つ。 また、これを繰り返せば$ {\cal A}_1,{\cal A}_2,\cdots,{\cal A} _{n-2}

 \vdash_H {\cal A} _{n-1} \Rightarrow ({\cal A}_n \Rightarrow  {\cal B})

   \frac{\cal A }{\cal B \Rightarrow  A}

     \cal \lnot B　\land \lnot C$を得る。$\cal \lnot B \land \lnot C$は$\cal \lnot A(=\lnot (B \lor C))$に他ならない。


 *$\cal A$が$\cal B \land C$である場合$\cal A$の値が$\top$のとき$\cal B,C$の値はともに$\top$でなければならない。
このとき$ \delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H  \cal  B \delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H  \cal  C$これに推論法則の「論理積」$

     \cal  B　\land  C$を得る。$\cal B \land  C$は$\cal  A$に他ならない。$\cal A$の値が$\bot$のとき$\cal B,C$の少なくともどちらか一方の値は$\bot$であるから、$\cal B$の値が$\bot$としても一般性を失わない。このとき$ \delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H  \cal \lnot B$が成り立っている。これと公理の$(3)\cal P \Rightarrow P \lor Q$により$ \delta X_1,\delta X_2,\cdots,\delta X_n \vdash_H  \cal \lnot B \lor \lnot C\cal \lnot B \lor \lnot C$は$\cal \lnot A=\lnot(B \land C)$に他ならない。$\Box$