汎用論証支援システム

(1)

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

汎用論証支援システム

南, 俊朗

Graduate School of Information Science and Electrical Engineering, Kyushu University

https://doi.org/10.11501/3150887

出版情報：Kyushu University, 1998, 博士（理学）, 課程博士

バージョン：

(2)

7.1 Martin-Lof's Intuitionistic Type Theory

This example is a tiny subset of the intuitionistic type theory described in

[2]

and

[55].

Based on the formulas-as-types notation, a type is represented as a formula that gives a formal specification and its element represents a program that satisfies the specification. This principal expression is represented in an intuitionistic type theory as a judgment of the form "xEA", reads "x is a proof of a proposition A" in formulas-as-types interpretation, where "x" is an expression in .A.-calculus and "A"

is a first-order formula interpreted as a type. The judgment is naturally and well described in the EUODHILOS framework

[

78; 98;

100].

We present two description examples; one on EUODHILOS-I in the DCGo nota

tion and the other on EUODHILOS-II in the BNF-based notation.

Description and Proof Example in DCGo-based framework The language definition consists of four parts: an object language, a metalanguage, interface between the meta and object languages and the constructor declaration as follows. This is a typical classification of the descriptions in the DCGo notation.

Language:

'1. Meta_language

meta_term --> meta_term1;

meta_type --> "A" I "B";

meta_term1 --> "F" meta_const I meta_variable;

meta_const --> "a" I ''b";

meta_variable --> "X";

I. Object_language

judgement --> term, "E", type;

term --> bind_op, variable, term, ".", term I II (II ^> term, ")"

II II _term I

type --> type, ":J", type type, "v", type

"-", type I

II

(

II ^> type ^' II ) II

basic_type;

variable --> "x" "f";

constant --> "c" "d";

basic_type --> "P" I "l_";

bind_op --> "..\";

I. Interface between meta and object languages type --> meta_type;

variable --> meta_variable.

'1. Constructor declaration with_priority

"-"; "v":left; ":J":left; ".":left; "..\"; "E";

without_priority

"inl", "inr", meta_term1.

It is notable that the syntax definition for the metalanguage is provided for defin

ing inference rules schematically, and the operators have precedence in the indicated order as well as their associativity, and the functors or predicates, e.g., "inl" in the term "inl

(

x

)

", are listed simply by themselves or the non terminals by which they are denoted, under the heading "predicate". As has been described in Chapter 4, the constructor declaration tells the parser and the unparser that the terminal name de

clared to be an operator or the terminal name denoted by the nonterminal character string is entitled to become the principal operator of the internal structure for an expression generated by the grammar rules.

11-11 term I Inference Rule:

"inl", "(", term, ")" I "inr", "(", term, ")" I

variable I constant I

meta_term1, "

(

", term, ")" I meta_term;

The intuitionistic type theory is defined by a number of natural deduction style in

ference rules. For the purpose of illustration we consider just four rules and one

(3)

INFORMATION

new new

SOFT_KEYBOARD

** exit

SYNTAX ^1\Ei

INFERENCE_RULE

AE2

REWRITING_RULE

AI

AXIOM

VE

vii

PROVER _thea

VI2

DERIVED_RULE

::JE

THEOREM

::JI

PROOF ^ljE

** EXIT ** ^ljl 3E 31

fEA::JB aEA app(f,a)EB

** Side conditon

Define

bEB

exit **

---def +def

*def D1 D2

E

^::Jj_

l t--i �n�r�(� b�) E�A�V �B��:t::===�==�� ---( .... def (R) {})

** Si de conditon .... A Ay.app(y,inr(Ax.app(!:J1inl(x))))E ... (AV .... A)

Define

sheet_t

Figure 7.1: Intuitionistic Type Theory and Constructive Proof on EUODHILOS-I

rewriting rule. These are the rules for function introduction and elimination, the two rules for V-introduction, and the rewriting rule for the definition

rv A

⁼

A �

_l. As can be recognized in these example inference rule definitions, if we see only the right sides of the judgme1�ts the rule is exactly that of the natural deduction rules for the classical propositional logic.

�-I:

[yEA) f(yjx) E B Ax.f(x) E A� B

Side Condition:

y

is not free in

B

�-E:

inl-I:

inr-I:

Rewriting Rule:

def:

Proof Example:

fEA�B aEA app(f, a) E B

a E A inl(a) E A VB

bE B inr(b)EA VB

A�l_

rvA

Figure 7.1 displays the proof of the theorem''·""·"'

(AV rv A).

The theorem means that the law of the double negation of the excluded middle cannot be refuted. This is an instance of Glivenko's theorem that if A is any tautology of the classical propositional calculus then the proposition

rvrv A

is always constructively valid. For further de

tails about how the proof has been constructed using our various proof facilities and methods, refer to

[102].

Description and Proof Example in EUODHILOS-11

Also in the description framework of EUODHILOS-II, the intuitionistic type theory can be formulated in a similar way. We present the actual description example for the same example logical system in order to provide a comparison example between the two EUODHILOS frameworks.

(4)

Language:

The syntax definition is as follows:

%ROOT Judgement

%META_ VARIABLES

Meta_ Var = "[u-z] [0-9] * 11 Meta_ Term = 11 [a-kr-t] [0-9] *"

Meta_ Type = "[A-GO-T] [0-9] *'1 Meta_Judgement = "[IJ] [0-9]*" ; /.PRODUCTIONS

Judgement Judgement Judgement Judgement Judgement

Meta_Judgement

Meta_Judgement "(" Type ")11 Meta_Judgement "(" Term ")11 Term "E11 Type

Type 11 =11 Type Judgement Term

Op1 "inl";

Op1 Op1 ^- Op1 Op2 Dp2 Op2 Op3

"inr";

"car";

"cdr";

"ap" ;

"cons"

"Ell

"D"

"="

Variable Term Term

: : = Meta_ Var Variable ; Meta_Term ;

Term 11 E11 Type

Term Meta_Term "(11 List Of Term ")11 Term

Term Term Term Term Arg2

Op1 "(11 Op2 "(11 Op3 "("

Term "/11 Term Arg2 Arg3 Term II ).11 @Term 11. II II II , Term

")"

")II

")"

[ Term ] Arg3

Term

Term II II , Term 11," Term ; . ·= Term

L1st Of Term List_Of_Term

Type 11 j_" Term 11 " List_Of_Term Type

Type Type

Meta_ Type

Meta_Type "(11 List Of Term ")11

"(" Type ")11 ;

Type Type Type Type Type Type

"("

Type

"("

Axiom:

-

"'I/ II

-

"3"

"•" Type

Type "/"

Type "/\"

Type IIV"

Type II :J II

@Variable

@Variable Type

Type Type Type

liE II Type II) II [ Type J

liE" Type II) II [ Type J

There are two axioms,

a

⁼

a E A

and

A

⁼

A,

which give the identity properties for the elements and the types, respectively.

Inference Rule:

:JI:

[x E A]

fEB AX.j E A :J B

Side Condition: (NOT-FREE ("x" . Variable) ("B" ^. Type))

Note that the rule body looks the same to the previous example, whereas the side condition is specified in a different style of description. The other rules are omitted here.

Rewriting Rule:

cons:

A:Jl_

-.A

cons( car( t), cdr( t))

t

(5)

� EUODHJLOS-11: Proof Sheet 1- CTT

��

Name : ONEM

.Ab.a b inr .Aa.a b inl a 'E-,-, AV-,A -,def

.Ab.ap(b, inr(.Aa.ap(b, inl(a))))E-,(AV-,A):::Jl.. (=>I [1]) I ap(b, i nr( A a. ap(b, in I (a)))) E 1.. (=>E)

I I bEAV -,A:=>l.. ("�def)

I I I [bE-, (AV -,A)] (Discharged 1) I I inr(.Aa.ap(b, inl (a))) EAV-,A (VI2) I I I .Aa.ap(b,inl(a))E-,A ("�def) I I I I .A.a. ap(b, in I (a)) EA:::Jl.. (=>I [2]) I I I I I ap(b,inl(a))El.. (:::JE) I I I I I I bE AV -,A:::J 1.. ( .,def)

I I I I I I I [bE., (AV .,A)] (Discharged 1)

I I I I I I i n I (a) E AV -,A ( V I 1)

I I I I I I I [a E A] (0 i scharged 2)

-- E :--%*-EUODHILOS-II: Proof Sheet 1 - CTT EUODHILOS-II P

[bE •(A V •AJ]1 • [a E Af

& E A V •A ::J __L •dd ·inl(a) E A V •A Vl

�

ap(&,_·iul(a)) E __L

::JJ., ::J

Aa.ap(b,tnl(a)) E A ::J __L [bE •(A V •AJ]1 I ^. .\a.ap(b,·inl(a)) E •.4 '' c· 1-f J;)

I. 4 4 ^ofC'l . ( \ J. . {. . V ^_

v E.· V ,_. ::J __L m'f' /\a.ap(v, 't'lt (a))) E A V ^•A _I::

ap(b, inr(.\a.ap(b, ·inl(a)))) E __L ::J .\&.up(b, ·inr(.\u.ap(b. ·iul(a)))) E •(A V ^•A) ::J j_ ::JJ, ^.

.\b b ^. >. b . { ^.. . ( ·dd

.ap( ·, ·tnr( a.ap( , w (a)))) E •• A V •A)

Figure 7.2: A Proof of the Double Negation of the Excluded Middle Law in Intuition

istic Type Theory

Proof Example:

The screen image in Figure 7.2 shows the proof of the double negation of the excluded middle law. In the upper window, the proof is displayed in a full-tree representation, whereas in the lower window the same proof is displayed with a DVI previewer by using the Y.TEX macros for having a better view of the proof trees.

7.2 Modal Logic

Modal logic

[

³⁷

]

is a variety of classical logic extended by adding two modal expres

sions: DA and 0 A. These propositions assert that "it is necessary that proposition A holds" and "it is possible that proposition A holds," respectively.

In this section we present two formulation examples. The first example is a stan

dard one of propositional modal logic and the other one is a logic for program verifi

cation which is formulated by using modal operators, where for each program p, two modal operators

[p]

and < p > are introduced.

(A) Modal Logic

^T

Language:

Two modal operators, D

(

^necessity

)

^and⁰

(

possibility

)

, are add d to the language of classical propositional logic:

%ROOT Formula

%META_ VARIABLES

Identifier = "[A-Z] [A-Z0-9]*"

%PRODUCTIONS

AtomicFormula : := "j_" ;

AtomicFormula ::= Identifier Formula AtomicFormula Formula - "•" Formula Formula - "0" Formula _' Formula "0" Formula ;

Formula "

(

^" ^Formula ^"

)

^"

Formula - Formula "/\" Formula

Formula Formula "V" Formula Formula - Formula II:) II Formula Formula Formula "=" Formula

(6)

Axiom:

The first three axioms come from ordinary propositional logic, and the rest are specific to the modal logic T.

(1) _{A� (B �A)}

(2) (A� (B �C))� ((A� B)� (A� C))

(3) (-.A� -.B) � (B �A)

(4) _{DA �A}

(5) D(A �B) � (DA � DB)

Inference Rule:

A A� B

!liP

B AD

DA

B

1\

A

!\exchange

-.A:> B A VB Vdef

•(A

1\

B)

---- cle_jnorganl

-.Av-.B

AVE B V A V exchange

•(A VB)

---- clc.J11organ2

-.A

1\

-.B

Name :

A/\ 0 A::> B ::::> A/\ B *DEOUCT:t 1

OCA/\ B) C ---, ---,)

I ^---,---,0 (A/\ B) ( ---, def)

I ---,0 (A/\ B) ^{::) l_} (*DEDUCT:*= [2]) I l_ (MP)

I I OA (MP)

I I I [0AA0 (A::::>B)] (Discharged ₁₎

I I I OA/\ D (A::::> B) ::::>OA (Theorem ) I I OA=> l_ C -,def)

I I I -,OA (0def)

I I I -,-,D -,A ( ---, ---,)

I I I 0---,A CD)

I I I I -,A (MP)

I I I I I ^---,AV ---,A C V def) I I I I I I ---, ---,A::>---, A C ---, ---,) I I I I I I A=> -,A (=>TRANS)

I I I I I A::::>B (MP)

I I I I I I OCA=>B) (MP)

I I I I I I I [ OA/\ D (A::> B) J (D i «<f'r-,ra.:>rl I I I I I I OA/\ D (A::::>B) =>D (A=> B) I I I I I DCA=>B) ::::> (A::::>B) (Axiom)

I I I I B::::> -,A (---, ---,)

I I I I I -, -,B::::>-,A (Vdef)

I I I I I I -,Bv -,A (V exchange)

I I I I I I I -,Av -,B (de_morganl)

I I I I I I I I ---, (A/\ B) (MP)

I I I I I I I I I O--. (A/\8) (Odef$

I I I I I I I I I I --.0 ---,---, (A/\ B) C--.--.) I I I I I I I I I I I [ -,OCA/\ B)J $ I I I I I I I I I 0 ---, (A/\B) ::::> ---, (A/\B) $

1 1 -,Av -,A::> -.A cv _I)

I I I -,A:J -,A (Theorem)

I I I -,A::> -.A (Theorem )

-- E :--%*-EUODHILOS-II· Proof Sheet 1- T EUODHILOS-II Proof Edttor - (

To prove this proposition, we use propositional theorems. Without these theorems, the proof would be much larger and more difficult.

Proof Example in the DCGo Framework:

Figure

7.4

is an example in DCGo framework, where a proof example of "a strong correctness assertion is implied from a termination assertion and a weak correctness assertion" is displayed in the screen.

(7)

INFORMATION SOFT_KEYBOARD

SYNTAX INFERENCLRULE REWRITING_RULE

AXIOM PROVER DERIVEO_RULE

THEOREM PROOF

** EXIT **

formula -->

formula! -->

** exit IIEP IIEQ III VE VIP VIQ :JE :JI

"-E

"-l

formula2 --> formula2,and,fo formula2 --> formula3;

formula3 --> ''('',formula,'')";

formula3 --> not, formula3;

formula3 --> modall, lormula3;

formula3 --> modal2,formula3;

formula3 --> atomic_rormula;

imply --> ��;

or --> "V";

and --> "A";

not --> ''.-....'';

modal! --> "O";

modal2 --> "</";

**

[�pliO (p:Jq) J

-(IIEP{l})

�p

[OpAO(p:Jq) J

-(AEQ{l})

O(p-;jq) O{p:Jq)-;j(p:Jq)

---C:JE{l}) p:Jq

2 ["-¢ (pllq) J

<�0->0"-{2})

[]--(pllq) []--(p/\q)-:;)"' (pAq)

---(:JE {2})

"-(pllq)

-(dc_morgan{2})

"-PY"-q

--(change {2})

"-qv�p

--(Y->:J {2} )

---(san-dan {1, 2}) p:::l"-p

--(Y->-:;)(R) {1, 2})

"'PV"'P

--_(V{I,2})

"'P

-(DI {1, 2}) o--p

-{"-0->D--(R) {1, 2})

"'¢P

---("-E{l, 2})

** ncUJ **

** exit **

1\-:;)_tO_-:;):J y V->-:;) :J->Y

"""E []--->�¢

�¢->O�

change

j_

--("-1{1})

�o<pllq)

----<�E{i})

(/(pllq)

---(:JI {}) 0pAO(p:Jq):J0(pi\q)

REWRITING_RULE:mod;

INFERENCE_RULE:mod;

p

OP

(B) Dynamic Logic

Dynamic logic

[

33

]

is a kind of multi-modal logic which is an extension to classical logic.

The principal formulas in dynamic logic are the dynamic formulas of the form "

[

a

)

p"

and its dual "<a>p", read informally ''after executing the program a the proposition p holds", where "a" is a regular or context-free program and "p" is a first-order or dynamic formula. They can be easily dealt with in the DCGo framework of EUO

DHILOS-I.

Language:

dynamic_formula --> "<", regular_program, ">", formula3;

dynamic_formula --> "[", regular_program, "]", formula3;

formula -->

formulaO -->

formula! -->

formula2 -->

formula3 -->

formula, "=" ' formulaO;

formulaO;

formulaO, ^II^::)^II^> formula!;

formula!;

formula!, "V", formula2;

formula2;

formula2, "I\ II' _formula3;

formula3;

It

(

^{tl ,} _formula, II) II ;

11-11

formula3;

dynamic_formula;

"true";

term, term, term,

"="

">",

">" - '

term;

term --> variable I constant;

term --> term, "+", term I term, "-" term I term, ^"x^11, term I term ^' " I II I "

(

" ' t e rm ' " ) " ;

variable --> "x" "y" I "z" I "n";

constant --> "0" "1";

regular_program --> regular_program, ";", regular_program1;

regular_program --> regular_program, "I", regular_program1;

regular_program --> regular_program1;

regular_program1 --> regular_program2, "*";

regular_program1 --> regular_program2;

regular_program2 --> assignment_statement;

regular_program2 --> formula, ^11?";

regular_program2 --> "

(

^", regular_program, "

)

^"; assignment_statement --> variable, ":=", term;

regular_program2 --> meta_program;

formula3 --> meta_formula, "

(

", term, ")";

formula3 --> meta_formula;

term --> meta_term;

(8)

variable ^--> meta_variable;

meta_term ^--> meta_variable;

meta_program --> "A" I "B";

meta_variable --> "X";

meta_formula --> "P" I "Q" I "R" I "S".

with_priority

"!"; "x"; ("+", "-"); ("<", "["); ("^-", ''>", '':2:", "=");

"/\"; "V"; "�"; "="; ("?", ":="); "*"; (";", "I");

without_priority meta_formula.

Axiom:

(1) [Q?)P = (Q � P) (test)

(2) [X

:

= T]P(X) = P(T) (assignment axiom) (3) [A; B]P = [A][B]P (composition)

(4) <A; B > P =<A>< B > P (composition)

(5) [A!B]P = ([A]P 1\ [B]P) (nondeterministic selection) (6) P(X) 1\ X = T � P(T) (substitution)

(7) x = 0 � (x = 0 �true) (arith)

Inference Rule:

mod us ponens:

necessitation:

in variance:

convergence:

p

P�Q

Q

P�Q [A]P � [A]Q

n "2: 01\ P(n

+

1) �<A> P(n) n 2:: 01\ P(n) �<A*> P(O)

composition 1:

composition 2:

derived-rule1:

replacement 1:

replacement 2:

symmetricity:

Rewriting Rule:

def:

neg-elim:

double-neg-elim:

arithmetic:

true-elim:

P

�<A> Q Q �< B > R P �< A;B > R

P � [A]Q Q � [B]R P � [A;B]R

P �<A> Q R � [A)S PI\R�<A>(QAR)

P(Q) Q=R P(R)

P�Q Q=R P�R

P=::Q Q=P

[A]P

rvrv

P

p

n"2:01\x=n x"20 true

1\

P

p

(9)

d�namic_logic SYNTAX : dynamic_logic INFORMATION

SOFT_KEYBOARD

save make test structure print reshape exit

--> 1eft_diamond1regular_program1right_diamon!

--> Jeft_box,regular_program,right_box,formul!

AXIOM : dynamic_logic

IJimil��,l!m�

formula --> formula, equivalence, formulaO; formula --> formulaO;

t-r�---...j

save wff _editor reshape ^exit

--> formulaO, imply, formula!;

--> formu I at;

--> formula1,or,formula2;

--> formula2;

[Q?JP:(QJP) [X:=TJP(X):P(T) [A;BJP;;;[AJ[BJP

REWRITING_RULE:

- ----�--

zXx!=n!�[(x>O?)](zXx!=n!Ax>O) zXx!=n!Ax>O�[z:=xXz](zX(x-i)!=n!)

---(comp20) zXx! =n! � [ (x>O?; z: =xXz) J (zX (x-1)! =n!)

:)<(z:=1)>(n�0Ax=n)

1---(compl 0)

zXx!=n!�[((x>O?;z:=xXz);x:=x-1)

0) x=O�<(x=O?)>true

I---( c omp 1 {} )

zXx!=n!�[(((x>O?;z:=xXz);x:=x-1)*

);x:=x-1)*);x=O?)>true x=n�[(z:=1; ((

1 ---(ar i t h 0 ) x:=x-1)*);x=O?)>true

x<::Oi\x=n:x ( (z: ;;;1 j ( (x>O?; z: =xXz); x: ;;;x-1) *); x;;;O?)> (trueAz=n!)

---(trE{})

�OAx=n:x ( (z: =1; ( (x>O?; z: ;;;xXz); x: =x-1) *); x=O?)> (z:n!)

sheet_!

Figure 7.5: Total Correctness Theorem

m

Dynamic Logic

Lemma:

(1)

<

(

^{x =}

0)? >true= (

^{x =}

0

:J

+

1)

(4)

^{x = n}+

1

:J< x := x- 1

> (

^{x = n}

7.3 Intensional Logic

Intensional logic [ 25 ] is a higher-order modal logic based on the simple type theory, which requires context-sensitive constraints on terms. It includes a lot of complicated logical concepts which are all well described in the DCGo notation.

Language:

meta_formula --> pred_const, "(", term(_), ")";

meta_formula --> meta_formula, "=>", meta_formula;

pred_const --> "beweis";

meta_formula --> meta_term(_);

meta_ variable --> "X" I "Y";

meta_ term(_) --> "R" I "S" I "A" "B" I "P" I "F";

meta_term(_) --> meta_variable;

meta_term(_) --> meta_term(_), colon, type(_);

meta_type(_) --> "a" I "b" I "c" I "T" I "T1" I "T2" I "T3";

(10)

term(t) --> term(t), "=:J", term1(t);

term(T) --> term1(T);

term1(t) --> term1(t), "V", term2(t);

term1(T) --> term2(T);

term2(t) --> term2(t), "/\", term3(t);

term3(t) --> term3(T), "=", term7(T);

term7(T2) --> term7((s,(T1,T2))), "{", term(T1), "}";

term4(t) --> bind_op, variable(T), ".", term5(t);

bind_op --> "\/" I "::3";

term4((T1, T2)) --> bind_op, variable(T1), ".", term5(T2);

bind_op --> ",\";

term5(t) --> "

-

", term5(t);

term5(T2) --> term5((T1, T2)), "•", term6(T1);

term6((s,T)) --> "�", term6(T);

term6(T) --> "v", term6((s,T));

term6(t) --> "[]", term6(t);

term6(t) --> "<>", term6(t);

term6(T) --> "(", term(T), ")";

term6(T) --> variable(T) I constant(T);

term6(T) --> meta_term2(T), "(", term(_), ")";

meta_term2(T) --> meta_term(T);

term6(T) --> meta_term(T);

variable(T) constant(t) constant(T) truth_ value

-->

var_sym, ":", type(T) I meta_variable, truth_value, ":'', type(t);

const_sym, ":", type(T);

"true" I "false";

var _sym --> "x" I "y" I "p";

const_sym --> "fish" I "believe" I "walk" I "j";

type (e) --> ''e";

type(t) --> "t";

type(T) --> meta_type(_);

type((T1,T2)) --> "(", type(T1), " 11 type(T2), ")";

type((s,T)) --> "(s,", type(T), ")".

with_priority

II .II

. ' type(T);

(II : II 1 tt J If) ;

("�",

"v",

"[]", "<>");

( "•"' "- fl) ^;

"{";

bind_op;

11-11 . - '

"I\ _II;

"V";

without_priority

meta_term2, pred_const.

Axiom:

(1) G: (t,t) •true: t

1\

G: (t,t) • false: t = VX: t.G: (t,t) •X: t (2) X: a=

Y:

a� F: (a, t) • X: a= F: (a, t) •

Y:

a

(3) VX: a.(F: (a, b) • X: a= G: (a, b) • X: a)= (F: (a, b) = G: (a, b)) (4 ) (AX: a.A(X; a)) • B = A(B)

(5 ) [ ](v F: (s, a) =v G: (s, a)) = (F: (s, a)= G: (s, a)) (6)v�A:a=A:a

Inference Rule:

Reflection -1:

Reflection-2:

=>I:

Replace-1:

beweis(A) A

A beweis(A)

[A]

B A=>B

A(R) R=S

A(S)

(11)

Replace-2:

Symmetricity:

Rewriting Rule:

\1-Definition:

Brace convention:

Notational convention:

Lemma:

A(B) = A(R) R = S A(B) = A(S)

R=S S=R

..\X

: a.P : t

⁼ ..\X

: a.true : t

\IX:

a

^.

P

:

t

A{R}

CA). R

F•G F(G)

(1) (P

:

t =true : t) = P: t (

2

)

..\X :

a.Q : b =

..\X

: a.Q : b

Proof Example:

The following metatheorem 1s ingeniously proved usmg the idea of the reflection principle

[

l14

]

.

Generalization rule:

f-P : t =>f- \lx : a.P : t

Figure

7.6

illustrates a proof of this generalization rule.

In Montague's language theory, natural language sentences are first translated into expressions in intensional logic, which in turn are analyzed by using the possible world semantics. Under the defined intensional logic, the following complicated inte

n

sional formula:

A(R) R=S

A(S/R)

** Side condilon **

** Define **

SYNTAX ^: intensional_logic

save make test structure print reshape ex.

term4(t) --> bind_op,variable(T),".", term5(t);

term4((T1,T2)) --> lambda,variable(Ti),".",term5(T2);

1 ambda --> "A.";

bind_op --> "1:1";"3";

termS(t) --> not,term5(t);

not --> """";

term5(T2) --> term5((T11T2)),apply, term6(T1);

term5(T) --> lermG(T);

apply --> "0";

SYNTAX INFERENCE_RULE REWRITING_RULE

AXIOM PROVER DERIVED_RULE

THEOREM

PROOF ll...,r-:n-.,--,....-r-r7��--,-__,ll.,_dl terrn6 ( (s, T)) --> intension, t erm6 (T);

** EXIT **

A

** Side conditon

** Define **

R: (t, t)Otrue: tAR: (t, t)Ofalse: t=I:IX: t. R: <t, t)OX: t X: a=Y: a:::lF: (a, t )OX: a=F: (a, t )@Y: a

\:IX: a. (F; (a, b)OX: a=R: (a, b)OX: a)= (F: (a, b) =R: (a, b)) (AX:a.A(X:a))OB:A(B)

0 c�F: (s, a) =�R: (s, a))= (F: Cs, a) =R: (s, a)) V"'A:a=A:a

R=R

[beweis(P: t)]

--

(Refl {1}) P: l

7.6:

A Proof of the Generalization Rule in Intensional Logic

(..A.p: (s, (e, t)).3x: e.(fish: (e, t) • x: e

1\ p:

(s, (e, t)){x e} )) .�

..\y:

e.(believe: ((s, t), (e, t))

• � (walk : (

e,

t) •

y :

e) • ^j : _e)

which is a translation of a natural language sentence ((John believes that a fish walks", easily and precisely reduces to a simpler and legible one:

3x: e(fish: (e, t) • x e

1\

believe: ((s, t), (e, t)) • �(walk (e, t) • x: e) • j e).

This theorem also has been proved easily.

(12)

7.4 Hoare Logic

Hoare logic

[

35] is the most well known logic for the axiomatic semantics of a program

ming language and the verification of a program. The principal formula in Hoare logic is a form of "P{S}Q", reads "if the property P holds, then after executing the pro

gram S, the property Q holds", where P and Q are first-order formulas and S is a program in an ALGOL-like programming language. These syntactic objects are easily described in the DCGo framework, as well as the inference rules of Hoare logic which is a kind of Hilbert-type logical system.

Language:

h-formula -->formula, "{", program, "}", formula;

formula --> formula, ":J", formula1;

formula --> formula1;

formula1 --> formula1, "V", formula2;

formula1 --> formula2;

f ormula2 --> f ormula2, "I\" , f ormula3;

formula3 --> "(", formula, ")";

formula3 -- "-", formula3;

formula3 --> basic_formula;

basic_formula --> "true" I term, "=" term;

term --> variable I constant I "(", term, ")" I term, "+", term I term, "*", term I term, variable --> "x" "y" I "z";

constant --> "1" "0";

program --> program, ";", program1;

program--> program1;

program1 --> assignment_statement I

II I II _. ^•

'

"while", formula, "do", program, "od" I

"if", formula, "then", program, "else", program, "fi" I

"(", program, ")";

assignment_statement -->variable, ":=", term;

meta_program --> "A" "B";

meta_var --> "X" I "Y" I meta_var, "/", term;

meta_ term --> "T";

meta_formula --> "P" I "E" I "F" I "G";

basic_formula --> meta_var;

term --> meta_term;

variable --> meta_var;

program --> meta_program;

program1 --> meta_program.

with_priority II! II; 11*11; 11+11;

Axiom:

"--"· '

Conjunction-elimination:

Substitution:

''/\"; "V"; ":J";

EI\F� E

"·-.-"' ·

P( X)

1\

X

=

T � P(T)

Assignment axiom:

Arithmetic:

Inference rule:

Consequence rule 1:

Consequence rule 2:

Composition rule:

P(T){ X

:=

T} P(X) true�

1 = 0!

E � F F{A}G E{A}G

E{A}F F � G E{A}G

E{A}F F{B}G E{A;B}G

"while"; "if"; "{".

(13)

Hoare_logic SYNTAX : Hoare_logic AXIOI� : Hoare_logic save make test structu save wff_editor h_formula --> formula,Ieft_bra true::J1=0!

left_brace --> "{"; z=y!A�Cy=x)::Jz=y!

right_brace --> "}";

variable --> "a''l"b":"x":"y'':"

constant --> "1":"011;

reshape exit INFORMATION

SOFT_KEYBOARD SYNTAX INFERENCE_RULE REWRITING_RULE

AXIOM PROVER DERIVED_RULE

program --> program,semi_colon PAQ::JP INFERENCE_RULE:Hoai THEOREM

PROOF

program --> program!; P(T/X) {X:=T}P(X)

** EXIT **

gcd_prop1 name:repetilion

program! --> assignmenl_slalem (X>Y)::J(gcd(X,V)=gcd(X-Y,V)) f----'---i

program! --> while, formula, "do' gcd_prop2

FAG{A}F

00¢¢LJ{--il��·�·

F{whileGdoAod}FA�G

. . . . _.

Q Q LJ ;{21Dl� ^EJ

^•(>j.• ** Side conditon **

** Define **

naone:arith z=y!

=1}z=O!

seq10)

z=O! {!J:=O}z=y!

1---(comp {})

z=y! A� Cy=x) ::n=y!

---(ar i th {})

z=y!A�y=x::Jz*(y+l)=(y+i)! z* (y+i) = (y+ 1)! {y: =y+1} z*y=y!

---(conseqt 0)

Z*\J=\J! {Z: =Z*!J} z=y!

---(comp {}) z=y!A�y=x{y:=y+l;z:=z*y}z=y!

---(repe ti {}) z=y! {whi I e�y=xdoy: =y+1; z: =z*yod} z=y! A�y=x ---<�EO>

{z:=l;y:=O>z=y! z=y! {whi I e�y=xdoy: =y+l; z: =z*yod} z=y! Ay=x

1---Ccomp 0) true{z:=i;y:=O; (while�!J=xdo!J:=y+i;z:=z*yod)}z=x!

heet_t

Figure 7. 7: Partial Correctness Proof of a Factorial Program in Hoare Logic Conditional rule:

Repetition rule:

Rewriting rule:

Arithmetic rule:

E !\ F{A}G E!\

^r-.J

F{B}G E{ if F then A else B fi}G

F !\ G{A}F

F{while G do A od}F!\"' G

z

=

y!

Z X

(y

⁺^{1) =}

(y

⁺^1)!

z=

Proof Example:

The screen layout of the proof of the following partial correctness assertion of a factorial program is shown in Figure 7. 7:

true { z

:= 1;

y

^{:= 0;}

while

rv

(y

⁼

x)do _y

:=

y

⁺^1;

z

:= z *

y od}z

=

x!

with the precondition "true" and postcondition "z=x!". For such a proof, we have often used an external ATP system which was connected to EUODHILOS-I through the theorem prover interface, in order to search for arithmetical theorems from its theorem database.

7.5 Linear Logic

Linear logic was originated from J ^.-Y. Girard[26] and is usually described in the sequent style formalization. Unlike the classical logic LK, it lacks the two structural rules of

weakening

and

contraction,

so that it is suitable for handling the properti s of finite resources. From these differences the free creation and deletion of an arbitrary proposition are prohibited in Linear Logic.

Petri net[54] is a computation model of concurrent processes, and is used to analyze their properties. The behavior of Petri net can be represented naturally in linear logic[31], because the tokens in a Petri net has the property of resources. To be precise, the diagram:

A B

0--.f----.0

denotes that "if we have a token on condition A, then it IS possible to fire event t.

Firing

t

exhausts the token on

A

and provides a token on

B."

This can be translated into the linear logic sequent

A

f-

B.

The reachability problem, which is common 111 Petri net theory, can be replaced with the provability problem in linear logic.

Consider the following Petri net:

(14)

r B ^s D

A

u

The problem is to determine whether the proposition "if there are two tokens on A, a token can reach F" holds. In linear logic, this problem is expressed as A, A � F.

Language:

We specify a language system that can represent the above problem.

/.ROOT Sequent /.META_ VARIABLES

Meta_Formula ⁼ "[P-R] [0-9]*" ; Meta_Formula List ⁼ "[L-N] [0-9]*"

%PRODUCTIONS Sequent Sequent Sequent

Formula_List "f-" Formula List Formula_List "f-"

"f-" Formula List

Formula List Formula List Formula List Atomic Formula Atomic Formula

Meta_Formula_List Formula ;

Formula_List

"A"

"8"

Atomic Formula "C"

Atomic Formula Atomic Formula

"D"

"E"

Atomic Formula "F"

Formula - Meta Formula Atomic Formula

" " '

Formula Formula Formula

"(" Formula ")" ; Formula "®" Formula

Formula List

Axiom:

Name _: NETl

A.A F CUT

A, A f-D®E I A f-D I I A f-B I I B f-D I A f-E I I A f-C I I ^cf-E D®E f-F

I ^0,E f-F

(®R) (CUT) (Axiom Netl)

(Axiom Net2) •

(CUT) (Axiom Net3)

(Axiom Net4)

(®L) (Axiom Net5)

-- E :--%*-EUODHILOS-II. Proof Sheet 1- Petri EUOOHI

� CU031.A.IIJI�l:J�Jtrvf ""' - I .-]' _: - - ,,,.�!:::_..A ^1' ---�---�----·�---·-� -�··--. -

A f- B B f- D CUT A f- C C f- E CUT A f- D A f- E nR A,Af-D0E ^�

A,Af- F

D, E f- F D IS,1 E f- F 0L

Cl T

L�

� ... ,]

I·M•.oal E3 1""''""'1

Figure 7.8: Proof of the Reachability Problem.

Transitions of the above Petri net are expressed ^asfollows:

Inference Rule:

r: A� B t: A� C

s: B � D

u: C�E v: D, E�F

We will use only the following four inference rules in this example:

(1)

_CUT_:

(2)

_EXCHL:

L�P P�Q L�Q

P, Q�M Q , P�M

(15)

(3)

^@1:

(4) &R:

Proof Example:

P, Q f- M P&Qf-M

Ll f- P L2 f- Q Ll, L2 f- P

0

Q

The formula to be proved is A, A f-

F.

Its simplest proof is shown in Figure

7.8,

where the lower part is the same proof tree displayed by the DVI previewer.

7.6 First-Order Logic

In this section we present two description and proof examples for classical first-order logic.

^1\

^1\

O(v,b))))

(4) :=lv(C(y)/\Vy((C(y)/\H(y,y)

^�

H(v,y)/\O(v,g))/\(C(y)/\ "'H(y,y)

^�

H(v,y)/\

O(u, b))))

where the meaning of each predicate is as follows:

A (x): xis an algorithm ,

C (y): y is a computer program in some programming language ,

SYNTAX INFERENCE_RULE REWRITING_RULE

AXIOM PROVER

�ormula --> formula,equivalence,formulal;

formula --> formula!;

formula! --> formula1,imply,formula2;

formula! --> formula2;

formula2 --> formula2,or, formula3;

•

save wff_editor reshape exit r

3v(C(v)AHy((C(y)AH(y,y)::>H(v,y)A0(v,g))A(C(y)A�HCy,y)::>H(v,y)A0(v ))A(C(y)A�H(y,y)::>H(u,y)AO(u,b))))

p P::>Q

0

** Side condi

** Define **

�P

** Side conditon **

** De fine **

3w(C(w)AHyC(C(y)AH(y,y)::>HCw,y,y)A0(w,g))A(C(y)A�HCy,y)::>H(w,y,y)A0(w,b))))::>3v(C(v)AHy((C(y)AH(y,y)::>H(!

v,y)AQ(v,g))A(C(y)A�HCy,y)::>H(v,y)AO(v,b))))

0

g))A(C(y)A�HCy,y)::>HCv,y)AO(v,b))))

1---C::>E{i} l

heet_i

.l

---<�I 0)

�3xCA(x)AHy(C(y)::>HzOCx,y,z)))

Figure

7.9:

Unsolvability of the Halting Problem in First-Ord r Logic

D (x,y, z): xis able to decide whether y halts with given input z, H (x,y): x halts with given input y,

H (x,y,z): x halts with given inputs y and z, O (x,g ): x outputs g; i.e. x halts , and

O (x,b ) : x outputs b; i.e. x does not halt.

Proof Example:

Figure

7.9

shows part of a proof of the theorem that no algorithm to solve the halting problem [ lO ] exists:

f-"' :=Jx(A(x)

^1\

Vy(C(y)

^�

VzD(x,y,z)))

(16)

induct j ve_proot --- •

SYNTAX INFERENCE-RULE

REWRITING_RULE _theor�

** new **

** exit **

lnd inst subst substl S!Jm

[P(T/0)) P(O) P((XOT)/0)

tin. P(n/0)

** Side conditon **

** Define **

save make test structure print reshape exit

�ormula --> formula, equal, formulaO;

formula --> formulaO;

formulaO --> bind_op,varlable,".",formulai;

formulaO --> formula1;

formula! --> formula1,op, formula2;

formula! --> formula2;

formula2 --> append,"(", formula,",",formula,")";

formula2 --> term;

AXIOM : inductive_proof

term -->

constant;

save

variable;

"(",formula,">"; r term,op,term; x=x

wff_editor

constant --> ''0'' ;

variable --> "u":":x":"�11: append(O,T)=T

reshape

append(XOT,S)=XOappend(T,S) term --> meta_term;

x=x

exi i

---(in ,append(u,z))J append(xOv,append(u,z))=xOappend(!J,append(u,z)) append(append(O,u),z)=append(append <O,

--(subst (if) (s!Jm 0)

xOappend(!J,append(u1z))=append(xO!J,append(u,z)) append(append(O,u>,z>=app ---(trans(1})

nd(xOv,append(u,z)) append

tlx. (append(append(x,u),z)=append(x,append(u,z)))

shee L 1

Figure

7.10:

Structural Induction Proof in First-Order Logic

(B) Structural Induction on List Structure

As another example proof for first-order logic we take a recursive data structure which is popularly used for defining new data types.

Proof Example:

Figure

7.10

is a proof for the theorem:

�

Vx'Vy'Vz.append(append(x, y), z)

⁼

append(x, append(y, z))

which expresses the associativity of the append function.

The structural induction is a well-used method for proving useful properties for the data structures that are defined in terms of recursion.

·�-·=. .

.

^.^- ^{. .}

oooo'LJ�-(1��-·�·

(tiE(}) O:ii

-(VJP O ) O�j Vr (j)

-(:S-> () ) j<O:::>r(j)

2 ----(til{

[j:OJ tlj (j<O:::lr (j

.(chg {2})

O=j I

[tlp(p(O)Atln(p(n):::>p(n+l)):::ltlnp(n))] r (j)

(tiE (I}) ---(:>I{

p(O)stlj (j:.;O:::>r (j)) p(O)Atln(p(n):::>p(n+l)):::>tlnp(n) j=O:::>r(j)

(rep2 (1} ) <=

p(n)!!tlj (j�:::lr(j)) tlj (j�O:::lr (j) )Atln (p (n):::lp (n+l) ):::ltlnp (n) j �O:::lr (j)

Crep2(1}) (tl

+l:::lr(j)) tJ j C j .:SO:::lr C j)) A tin (tl j ( j .;Sn:::lr < j) ) :::lp (n+ 1)) :::ltlntl j ( j ,:Sn:::lr ( j ) ) tl j ( j :.;0 :::lr ( j ) ) (rep2{1})

j ::;;O:::lr < j)) A tin (tlj (j �:::lr C j)) :::ltlj { j .:sn+ 1 :::lr < j))) :::ltlntl j ( j .:snx ( j))

tlntlj {j�Dr (j))

(t:1E(11 3}) tJ j (j ,:Sn:::lr ( j))

(t1E(1, 3}) n.;Sn:::lr (n)

(::lEU, 3} >

r(n)

--(til {1, 3}) tlnr(n)

(:::ll ( 1} ) tin Ctlj (j<n:::lr(j) ):::lr (n)):::ltlnr (n)

(t:1l ( 1} ) tlr (tin (tlj (j<n:::lr (j) ):::lr (n)):::ltlnr (n))

(:::ll {} )

tlp(p(0)Atln(p(n)�p(n+1)):::lt:1np(n)):::ltlr(tln(tlj(j<n:::lr(j)):::>r(n)):::ltlnr(n))

heet_l

Figure

7.11:

Proof Examples of Second-Order Logic

7.7 Second-Order Logic

We present a proof of second-order logic ^asan example of higher-order logic.

Proof Example:

Figure

7.11

proves that the principle of the mathematical induction 1s equivalent to the principle of the complete induction:

汎用論証支援システム