This article was written as the 21st day of ISer Advent Calendar 2019.
In this article, we will implement an automated proof using sequent calculus of classical propositional logic called G3C. However, I will focus on the implementation without going too far into the rigorous theory. What you make in this article is, for example,
Sequent is simply a proposition. For example
For example, the following sequence can be said to be a tautology.
In the previous proposition, $ \ lnot $ and $ \ to $ came out as logical symbols. There are only four types of logical symbols in propositional logic. They are in line with the intuitive meaning.
symbol | Example | meaning |
---|---|---|
Not A | ||
A and B | ||
A or B | ||
If A, then B |
You must be able to infer to make a proof. Inference is expressed in the following form.
The following eight types of inference rules are defined in the G3C proof system. The proof will be constructed using these eight types of inference rules. In addition, the order of logical expressions shall be arbitrarily changed on each side of the sequence.
(i) If $ \ Delta $ can be derived from $ \ Gamma $, then of course $ \ lnot A, \ Gamma \ Rightarrow \ Delta $ is tautological. (ii) If $ A $ can be derived from $ \ Gamma $, then $ \ lnot A and \ Gamma $ will never be true, so $ \ lnot A, \ Gamma \ Rightarrow \ Delta $ is tautological regardless of the right side. It's true.
I won't write about other inference rules, but I think you can be convinced by thinking this way.
Now, we will prove by combining the above inference rules, but for that purpose we need a sequence that is an axiom located at the top of the proof diagram. This is called the ** start sequence **. This should be a sequence that is self-evidently true to everyone. The sequence that can be derived from the tautological sequence is also tautological.
The starting sequence in the proof system dealt with here is only the one in the following form.
Given a sequence to prove, if the inference rule is repeatedly applied from the start sequence and the final sequence is matched, the proof is complete.
As an example, the first sequence I gave
Before introducing the proof search algorithm, let us introduce the concept of the ** size ** of the sequence. The size is the total number of logical symbols $ \ lnot, \ land, \ lor, \ to $ included in the sequence.
For example
Now, let's look at the inference rules again, focusing on size. You can see that in any inference rule the size of the sequence below the line is one larger than the size of the sequence above. This is the point of proof search.
Since proof basically draws conclusions from axioms, it is natural to draw a proof diagram from top to bottom. However, in the proof search, when a sequence to be proved is given, the search is performed from bottom to top with that as the bottom. If you follow the proof diagram one step up, the size will be reduced by 1, so no matter what sequence you have to prove, if you apply the inference rule repeatedly, you will eventually end up with a set of sequences of size 0. To do. A zero-sized sequence can't be transformed anymore, so you can tell if it's taut by just looking at whether it's a start sequence.
The proof search algorithm is also called the "Wang algorithm". It's a nice name, but the idea is quite natural. There is nothing new. The given sequence is reduced to a sequence of size 0, and if they are all start sequences, the original sequence can be proved, and if any one is not the start sequence, it cannot be proved. I will write in detail below. Basically, it is an algorithm that determines whether a given sequence is tautology, but with a little ingenuity, you can also draw a proof diagram.
Now suppose you are given the sequence $ \ Gamma \ Rightarrow \ Delta $. First, check if the size of this sequence is 0. If it is 0, it can be determined whether it is a tautology by determining whether it is an initial sequence.
If the size is greater than or equal to 1, $ \ Gamma \ Rightarrow \ Delta $ always contains the logical symbols $ \ lnot, \ land, \ lor, \ to $. If you search it from the left and find a logical symbol, you can follow the inference rules from bottom to top to get one or two sequences that are one smaller in size. Similarly, determine if those sequences are tautologies. Repeating this operation will eventually result in a sequence of size 0, and you can recursively determine if $ \ Gamma \ Rightarrow \ Delta $ is a tautology.
It's been a long time, but the basic idea is simple. We will implement this algorithm from now on.
Here, it is implemented in Python3. I'll put the whole code at the end of this article, but I'll write only the important parts here.
Consider defining three classes.
Atomic Formula
Formula
Sequent
AtomicFormula Propositions such as $ P, Q $ that cannot be further divided.
class AtomicFormula:
def __init__(self, name):
self.name = name
def is_atomic(self):
return True
Has only a name. ʻIs_atomic` will be used in the future, so define it.
There are various logical expressions such as $ P \ to Q, \ quad \ lnot (S \ land T), \ quad P \ to ((P \ land Q) \ lor (S \ land T)) $. , Focusing on its hierarchical structure, on the outermost side
class Formula:
def __init__(self, relation, form1, form2=None):
self.relation = relation
self.form1 = form1
self.form2 = form2
def is_atomic(self):
return False
We will define self.relation
as 1,2,3,4 for $ \ lnot, \ land, \ lor, \ to $, respectively. Also, let's define ʻis_atomic with $ A $ as
form1and $ B $ as
form2`.
The sequence has columns of formulas to the left and right of $ \ Rightarrow $. The proof diagram search is defined as a method of this class.
class Sequent:
def __init__(self, Left, Right):
self.Left = Left
self.Right = Right #Left,Right is Formula,List of Atomic Formula
#Start sequence judgment
def is_initial(self):
for l in self.Left:
if l in self.Right: return True
return False
#Sequent judgment of size 0
def is_atomic(self):
for l in self.Left:
if not l.is_atomic(): return False
for r in self.Right:
if not r.is_atomic(): return False
return True
#Tautology judgment
def is_tautology(self):
if self.is_atomic():
return self.is_initial()
for l in range(len(self.Left)):
if not self.Left[l].is_atomic():
self.Left[0],self.Left[l]=self.Left[l],self.Left[0]
form = self.Left[0]
if form.relation==1:
return Sequent(self.Left[1:], self.Right+[form.form1]).is_tautology()
if form.relation==2:
return Sequent(self.Left[1:]+[form.form1,form.form2], self.Right).is_tautology()
if form.relation==3:
return Sequent(self.Left[1:]+[form.form1], self.Right).is_tautology() and Sequent(self.Left[1:]+[form.form2], self.Right).is_tautology()
if form.relation==4:
return Sequent(self.Left[1:], self.Right+[form.form1]).is_tautology() and Sequent(self.Left[1:]+[form.form2], self.Right).is_tautology()
for r in range(len(self.Right)):
if not self.Right[r].is_atomic():
self.Right[0],self.Right[r]=self.Right[r],self.Right[0]
form=self.Right[0]
if form.relation==1:
return Sequent(self.Left+[form.form1], self.Right[1:]).is_tautology()
if form.relation==2:
return Sequent(self.Left, self.Right[1:]+[form.form1]).is_tautology() and Sequent(self.Left, self.Right[1:]+[form.form2]).is_tautology()
if form.relation==3:
return Sequent(self.Left, self.Right[1:]+[form.form1,form.form2]).is_tautology()
if form.relation==4:
return Sequent(self.Left+[form.form1], self.Right[1:]+[form.form2]).is_tautology()
def prooftree(self):
#I will write later
ʻIs_tautologyimplements Wang's algorithm and inference rules as they are. If the first element of
Left,
Right` is atomic, it is replaced with a non-atomic element, and the inference rule is applied to the first element.
Now you can determine if it can be proved by calling the ʻis_tautology` method for any sequence. By the way, in this definition, for example
Sequent([Formula(4, AtomicFormula('A'), AtomicFormula('B'))], [Formula(1, AtomicFormula('A')), AtomicFormula('B')])
Please note that it is represented as. The code that does this conversion will be postponed.
Now let's get down to prooftree
, the method of drawing a proof diagram, but we'll use LaTeX's prooftree environment to write the proof diagram. It's easy to use, so you should look at this site. The prooftree
method is created to return the code to pass to this environment.
In this environment, write as much as you can write one branch of the proof diagram, and if you can not write it, go to another branch and integrate it. What I want to say is that I write the proof diagram in the exact reverse order of the proof search. This fact makes it very easy to draw a proof diagram. You just have to add more and more in the process of exploration. The following is the definition of proof tree
, which is almost the same as ʻis_tautology`.
def prooftree(self):
if self.is_atomic(): return '\\AxiomC'+str(self)
string = str(self)
for l in range(len(self.Left)):
if not self.Left[l].is_atomic():
self.Left[0],self.Left[l]=self.Left[l],self.Left[0]
form = self.Left[0]
if form.relation==1:
return Sequent(self.Left[1:], self.Right+[form.form1]).prooftree()+'\n'+'\\UnaryInfC'+string
if form.relation==2:
return Sequent(self.Left[1:]+[form.form1,form.form2], self.Right).prooftree()+'\n'+'\\UnaryInfC'+string
if form.relation==3:
return Sequent(self.Left[1:]+[form.form1], self.Right).prooftree() + Sequent(self.Left[1:]+[form.form2], self.Right).prooftree() +'\n'+'\\BinaryInfC'+string
if form.relation==4:
return Sequent(self.Left[1:], self.Right+[form.form1]).prooftree() + Sequent(self.Left[1:]+[form.form2], self.Right).prooftree() + '\n'+'\\BinaryInfC'+string
for r in range(len(self.Right)):
if not self.Right[r].is_atomic():
self.Right[0],self.Right[r]=self.Right[r],self.Right[0]
form=self.Right[0]
if form.relation==1:
return Sequent(self.Left+[form.form1], self.Right[1:]).prooftree()+'\n'+'\\UnaryInfC'+string
if form.relation==2:
return Sequent(self.Left, self.Right[1:]+[form.form1]).prooftree() + Sequent(self.Left, self.Right[1:]+[form.form2]).prooftree()+'\n'+'\\BinaryInfC'+string
if form.relation==3:
return Sequent(self.Left, self.Right[1:]+[form.form1,form.form2]).prooftree()+'\n'+'\\UnaryInfC'+string
if form.relation==4:
return Sequent(self.Left+[form.form1], self.Right[1:]+[form.form2]).prooftree()+'\n'+'\\UnaryInfC'+string
Finally, define a function that converts a logical expression (not a sequence) written using $ \ lnot, \ land, \ lor, \ to $ into nested classes. It is easy to divide the sequence into logical expressions, so I will omit it. It is assumed that $ \ lnot $ has the highest priority for logical symbols, and that everything else is equivalent. The implementation is trying to find the logical symbols of the outermost hierarchy somehow.
def read(exp):
if '¬' in exp or '∧' in exp or '∨' in exp or '→' in exp:
#()Find the logical symbol outside of
i=len(exp)-1
if exp[i]==')':
c=1
while c:
i-=1
if exp[i]=='(': c-=1
elif exp[i]==')': c+=1
if i==0:
return read(exp[1:-1])
while exp[i] not in ['∧' , '∨' , '→']:
if i==0 and exp[i]=='¬':
return Formula(1, read(exp[1:]))
i-=1
if exp[i]=='∧': return Formula(2, read(exp[:i]), read(exp[i+1:]))
elif exp[i]=='∨': return Formula(3, read(exp[:i]), read(exp[i+1:]))
elif exp[i]=='→': return Formula(4, read(exp[:i]), read(exp[i+1:]))
return AtomicFormula(exp)
It's been a long time, but the implementation is over. The whole code is posted at the end, so please enter various sequences and try it out.
Thank you for reading this far. I think there was a part of the explanation that was unfriendly in the first article. The description may be inaccurate in some places. I would appreciate it if you could point out various things. The code I wrote this time is less than 200 lines in total, so I think you can see that you can easily create an automated proof by using sequent calculus. Of course, it can be automated by other methods, so it may be interesting to try natural deduction. Then, I will put all the codes at the end.
# -*- coding: utf-8 -*-
import sys
class AtomicFormula:
def __init__(self, name):
self.name = name
def is_atomic(self):
return True
def __eq__(self, other):
if type(other) != AtomicFormula: return False
return self.name == other.name
def __str__(self):
return self.name
class Formula:
def __init__(self, relation, form1, form2=None):
self.relation = relation
# 1:not
# 2:and
# 3:or
# 4:->
self.form1 = form1
self.form2 = form2
def is_atomic(self):
return False
def __eq__(self, other):
if type(other) != Formula: return False
return self.relation==other.relation and self.form1==other.form1 and self.form2==other.form2
def __str__(self):
if self.relation==1: return '\\lnot '+str(self.form1)
if self.relation==2: return '('+str(self.form1)+'\\land '+str(self.form2)+')'
if self.relation==3: return '('+str(self.form1)+'\\lor '+str(self.form2)+')'
if self.relation==4: return '('+str(self.form1)+'\\to '+str(self.form2)+')'
class Sequent:
def __init__(self, Left, Right):
self.Left = Left
self.Right = Right
def is_initial(self):
for l in self.Left:
if l in self.Right: return True
return False
def is_atomic(self):
for l in self.Left:
if not l.is_atomic(): return False
for r in self.Right:
if not r.is_atomic(): return False
return True
def is_tautology(self):
if self.is_atomic():
return self.is_initial()
for l in range(len(self.Left)):
if not self.Left[l].is_atomic():
self.Left[0],self.Left[l]=self.Left[l],self.Left[0]
form = self.Left[0]
if form.relation==1:
return Sequent(self.Left[1:], self.Right+[form.form1]).is_tautology()
if form.relation==2:
return Sequent(self.Left[1:]+[form.form1,form.form2], self.Right).is_tautology()
if form.relation==3:
return Sequent(self.Left[1:]+[form.form1], self.Right).is_tautology() and Sequent(self.Left[1:]+[form.form2], self.Right).is_tautology()
if form.relation==4:
return Sequent(self.Left[1:], self.Right+[form.form1]).is_tautology() and Sequent(self.Left[1:]+[form.form2], self.Right).is_tautology()
for r in range(len(self.Right)):
if not self.Right[r].is_atomic():
self.Right[0],self.Right[r]=self.Right[r],self.Right[0]
form=self.Right[0]
if form.relation==1:
return Sequent(self.Left+[form.form1], self.Right[1:]).is_tautology()
if form.relation==2:
return Sequent(self.Left, self.Right[1:]+[form.form1]).is_tautology() and Sequent(self.Left, self.Right[1:]+[form.form2]).is_tautology()
if form.relation==3:
return Sequent(self.Left, self.Right[1:]+[form.form1,form.form2]).is_tautology()
if form.relation==4:
return Sequent(self.Left+[form.form1], self.Right[1:]+[form.form2]).is_tautology()
def prooftree(self):
if self.is_atomic(): return '\\AxiomC'+str(self)
string = str(self)
for l in range(len(self.Left)):
if not self.Left[l].is_atomic():
self.Left[0],self.Left[l]=self.Left[l],self.Left[0]
form = self.Left[0]
if form.relation==1:
return Sequent(self.Left[1:], self.Right+[form.form1]).prooftree()+'\n'+'\\UnaryInfC'+string
if form.relation==2:
return Sequent(self.Left[1:]+[form.form1,form.form2], self.Right).prooftree()+'\n'+'\\UnaryInfC'+string
if form.relation==3:
return Sequent(self.Left[1:]+[form.form1], self.Right).prooftree() + Sequent(self.Left[1:]+[form.form2], self.Right).prooftree() +'\n'+'\\BinaryInfC'+string
if form.relation==4:
return Sequent(self.Left[1:], self.Right+[form.form1]).prooftree() + Sequent(self.Left[1:]+[form.form2], self.Right).prooftree() + '\n'+'\\BinaryInfC'+string
for r in range(len(self.Right)):
if not self.Right[r].is_atomic():
self.Right[0],self.Right[r]=self.Right[r],self.Right[0]
form=self.Right[0]
if form.relation==1:
return Sequent(self.Left+[form.form1], self.Right[1:]).prooftree()+'\n'+'\\UnaryInfC'+string
if form.relation==2:
return Sequent(self.Left, self.Right[1:]+[form.form1]).prooftree() + Sequent(self.Left, self.Right[1:]+[form.form2]).prooftree()+'\n'+'\\BinaryInfC'+string
if form.relation==3:
return Sequent(self.Left, self.Right[1:]+[form.form1,form.form2]).prooftree()+'\n'+'\\UnaryInfC'+string
if form.relation==4:
return Sequent(self.Left+[form.form1], self.Right[1:]+[form.form2]).prooftree()+'\n'+'\\UnaryInfC'+string
def __str__(self):
return '{$'+','.join(map(str,self.Left))+'\Rightarrow '+','.join(map(str,self.Right))+'$}'
def read(exp):
if '¬' in exp or '∧' in exp or '∨' in exp or '→' in exp:
#()Find the logical symbol outside of
i=len(exp)-1
if exp[i]==')':
c=1
while c:
i-=1
if exp[i]=='(': c-=1
elif exp[i]==')': c+=1
if i==0:
return read(exp[1:-1])
while exp[i] not in ['∧' , '∨' , '→']:
if i==0 and exp[i]=='¬':
return Formula(1, read(exp[1:]))
i-=1
if exp[i]=='∧': return Formula(2, read(exp[:i]), read(exp[i+1:]))
elif exp[i]=='∨': return Formula(3, read(exp[:i]), read(exp[i+1:]))
elif exp[i]=='→': return Formula(4, read(exp[:i]), read(exp[i+1:]))
return AtomicFormula(exp)
while True:
try:
exp = input("Sequent> ").replace(' ','')
if exp=="exit": sys.exit()
left , right = exp.split('⇒')
seq = Sequent(list(map(read, left.split(','))), (list(map(read, right.split(',')))))
if seq.is_tautology():
print(seq.prooftree())
else:
print("Not Provable")
except EOFError:
sys.exit()
except (AttributeError, ValueError):
print("Error: Invalid Input")
Recommended Posts