Я создаю небольшую систему символьной логики в Python и пытаюсь понять, как реализовать правила перезаписи для логических выражений. Я не уверен, как должен выглядеть «правильный» дизайн, и я даже не уверен, должны ли эти правила иметь имена или как быть в случаях, когда существует несколько эквивалентных форм.
Вот некоторые из правил перезаписи, которые я хочу поддержать:
- A → ¬¬A
- ¬A ↔ ¬¬A
- ¬(A ∨ B) ↔ ¬A ∧ ¬B
- ¬(A ∧ B) ↔ (A → ¬B) ↔ (B → ¬A)
- ¬¬(A → B) ↔ (¬¬A → ¬¬B) ↔ (A → ¬¬B) ↔ ¬¬(¬A ∨ B)
- ¬(A → B) ↔ ¬(¬A ∨ B)
- (A → B) ↔ (¬B → ¬A)
Not(Or(A, B))
Я хочу иметь возможность превратить это в:
And(Not(A), Not(B))
когда я выбираю это правило. Но я не знаю, как должны быть представлены правила перезаписи или как работать с несколькими эквивалентными формами правил.
Вот код для моих классов выражений:
"""
The goal of this question is to learn how to implement the following
rewrite rules:
A → ¬¬A
¬A ↔ ¬¬¬A
¬(A ∨ B) ↔ ¬A ∧ ¬B
¬(A ∧ B) ↔ (A → ¬B) ↔ (B → ¬A)
¬¬(A → B) ↔ (¬¬A → ¬¬B) ↔ (A → ¬¬B) ↔ ¬¬(¬A ∨ B)
¬(A → B) ↔ ¬(¬A ∨ B)
(A → B) ↔ (¬B → ¬A)
I don't know if they should each be named,
or what to do when there are multiple equivalent forms.
"""
class Variable:
"""
A variable is a placeholder for an Expression.
"""
def __init__(self, name):
self.name = name
def __repr__(self):
return self.name
def substitute(self, target, replacement):
if self.name == target:
return replacement
return self
class LogicalSymbol:
"""
As logical symbols we use:
⊥, ¬, ∨, ∧, →, ↔, ∀, ∃, ∃!
In bracketing we adopt the usual convention that
¬, ∀, ∃ bind stronger than any of the binary
operators, AND that ∧, ∨ bind stronger than
→, ↔.
Unless stated otherwise, ¬, ↔, ∃! are regarded
as abbreviations defined by:
¬A ≔ A → ⊥ ;
A ↔ B ≔ (A → B) ∧ (B → A) ;
∃!x A ≔ ∃x(A ∧ ∀y(x=y ↔ A[x/y]))
Repeated equivalences can be written as
A ↔ B ↔ C ↔ ...
in place of
(A ↔ B) ∧ (B ↔ C) ∧ ...
For iterated quantifiers we use the abbreviations
∀x,y,... ≔ ∀x∀y;
∃x,y,... ≔ ∃x∀y
and for iterated restricted quantifiers:
∀x,y ∈ A ≔ ∀x ∈ A ∀y ∈ A ...
"""
class Contradiction(LogicalSymbol):
"""
The symbol ⊥ is used when a proof line
leads to a contradiction. It has zero
operands. It is equivalent to the ¬
of its antecedent.
"""
def __repr__(self):
return "⊥"
def decompose(self):
return self
def substitute(self, target, replacement):
return self
class Not(LogicalSymbol):
"""
This is the ¬ operation which flips the
truth value of a statement. It takes
one operand, and is defined as
meaning its operand implies a contradiction.
¬A ≔ A → ⊥
"""
def __init__(self, operand):
self.operand = operand.decompose()
def __repr__(self):
return f"¬{self.operand}"
def decompose(self):
return Implies(self.operand.decompose(), Contradiction())
def substitute(self, target, replacement):
return Not(self.operand.substitute(target, replacement))
class Or(LogicalSymbol):
"""
This is the ∨ operation.
It takes two operands, and is true if at least
one operand is true
"""
def __init__(self, LHS, RHS):
self.LHS = LHS.decompose()
self.RHS = RHS.decompose()
def __repr__(self):
return f"{self.LHS} ∨ {self.RHS}"
def decompose(self):
return Or(self.LHS.decompose(), self.RHS.decompose())
def substitute(self, target, replacement):
return Or(
self.LHS.substitute(target, replacement),
self.RHS.substitute(target, replacement)
)
class And(LogicalSymbol):
"""
This is the ∧ operation.
It takes two operands, and is true iff they both are true.
"""
def __init__(self, LHS, RHS):
self.LHS = LHS.decompose()
self.RHS = RHS.decompose()
def __repr__(self):
return f"{self.LHS} ∧ {self.RHS}"
def decompose(self):
return And(self.LHS.decompose(), self.RHS.decompose())
def substitute(self, target, replacement):
return And(
self.LHS.substitute(target, replacement),
self.RHS.substitute(target, replacement)
)
class Implies(LogicalSymbol):
"""
This is the → operation.
It takes two operands.
"""
def __init__(self, LHS, RHS):
self.LHS = LHS.decompose()
self.RHS = RHS.decompose()
def __repr__(self):
return f"{self.LHS} → {self.RHS}"
def decompose(self):
return Implies(self.LHS.decompose(), self.RHS.decompose())
def substitute(self, target, replacement):
return Implies(
self.LHS.substitute(target, replacement),
self.RHS.substitute(target, replacement)
)
class Iff(LogicalSymbol):
"""
This is the ↔ operation.
It has two operands.
It is true if both sides
are simultaneously true or dimultaneously false
"""
def __init__(self, LHS, RHS):
self.LHS = LHS.decompose()
self.RHS = RHS.decompose()
def __repr__(self):
return f"{self.LHS} ↔ {self.RHS}"
def decompose(self):
return And(Implies(self.LHS, self.RHS), Implies(self.RHS, self.LHS))
def substitute(self, target, replacement):
return Iff(
self.LHS.substitute(target, replacement),
self.RHS.substitute(target, replacement)
)
