blob: 61bc2adbb2a6ef58104a9306c014269d8d3558a9 [file]
/-
Copyright (c) 2022 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Leonardo de Moura
-/
module
prelude
public import Init.Data.RArray
import Init.LawfulBEqTactics
import Init.ByCases
import Init.Data.Prod
public section
@[expose] section
namespace Nat.Linear
/-!
Helper definitions and theorems for constructing linear arithmetic proofs.
-/
abbrev Var := Nat
abbrev Context := Lean.RArray Nat
/--
When encoding polynomials. We use `fixedVar` for encoding numerals.
The denotation of `fixedVar` is always `1`. -/
abbrev fixedVar := 100000000 -- Any big number should work here
noncomputable abbrev Var.denote (ctx : Context) (v : Var) : Nat :=
Bool.rec (ctx.get v) 1 (Nat.beq v fixedVar)
inductive Expr where
| num (v : Nat)
| var (i : Var)
| add (a b : Expr)
| mulL (k : Nat) (a : Expr)
| mulR (a : Expr) (k : Nat)
deriving Inhabited, BEq
noncomputable abbrev Expr.denote (ctx : Context) : Expr → Nat
| .add a b => Nat.add (denote ctx a) (denote ctx b)
| .num k => k
| .var v => v.denote ctx
| .mulL k e => Nat.mul k (denote ctx e)
| .mulR e k => Nat.mul (denote ctx e) k
abbrev Poly := List (Nat × Var)
noncomputable abbrev Poly.denote (ctx : Context) (p : Poly) : Nat :=
match p with
| [] => 0
| (k, v) :: p => Nat.add (Nat.mul k (v.denote ctx)) (denote ctx p)
def Poly.insert (k : Nat) (v : Var) (p : Poly) : Poly :=
match p with
| [] => [(k, v)]
| (k', v') :: p =>
bif Nat.blt v v' then
(k, v) :: (k', v') :: p
else bif Nat.beq v v' then
(k + k', v') :: p
else
(k', v') :: insert k v p
def Poly.norm (p : Poly) : Poly := go p []
where
go (p : Poly) (r : Poly) : Poly :=
match p with
| [] => r
| (k, v) :: p => go p (r.insert k v)
def Poly.cancelAux (fuel : Nat) (m₁ m₂ r₁ r₂ : Poly) : Poly × Poly :=
match fuel with
| 0 => (r₁.reverse ++ m₁, r₂.reverse ++ m₂)
| fuel + 1 =>
match m₁, m₂ with
| m₁, [] => (r₁.reverse ++ m₁, r₂.reverse)
| [], m₂ => (r₁.reverse, r₂.reverse ++ m₂)
| (k₁, v₁) :: m₁, (k₂, v₂) :: m₂ =>
bif Nat.blt v₁ v₂ then
cancelAux fuel m₁ ((k₂, v₂) :: m₂) ((k₁, v₁) :: r₁) r₂
else bif Nat.blt v₂ v₁ then
cancelAux fuel ((k₁, v₁) :: m₁) m₂ r₁ ((k₂, v₂) :: r₂)
else bif Nat.blt k₁ k₂ then
cancelAux fuel m₁ m₂ r₁ ((Nat.sub k₂ k₁, v₁) :: r₂)
else bif Nat.blt k₂ k₁ then
cancelAux fuel m₁ m₂ ((Nat.sub k₁ k₂, v₁) :: r₁) r₂
else
cancelAux fuel m₁ m₂ r₁ r₂
def hugeFuel := 1000000 -- any big number should work
def Poly.cancel (p₁ p₂ : Poly) : Poly × Poly :=
cancelAux hugeFuel p₁ p₂ [] []
def Poly.isNum? (p : Poly) : Option Nat :=
match p with
| [] => some 0
| [(k, v)] => bif v == fixedVar then some k else none
| _ => none
def Poly.isZero (p : Poly) : Bool :=
match p with
| [] => true
| _ => false
def Poly.isNonZero (p : Poly) : Bool :=
match p with
| [] => false
| (k, v) :: p => bif v == fixedVar then k > 0 else isNonZero p
abbrev Poly.denote_eq (ctx : Context) (mp : Poly × Poly) : Prop :=
mp.1.denote ctx = mp.2.denote ctx
abbrev Poly.denote_le (ctx : Context) (mp : Poly × Poly) : Prop :=
mp.1.denote ctx ≤ mp.2.denote ctx
set_option allowUnsafeReducibility true
attribute [semireducible] Poly.denote_eq Poly.denote_le
def Expr.toPoly (e : Expr) :=
go 1 e []
where
-- Implementation note: This assembles the result using difference lists
-- to avoid `++` on lists.
go (coeff : Nat) : Expr → (Poly → Poly)
| .num k => bif k == 0 then id else ((coeff * k, fixedVar) :: ·)
| .var i => ((coeff, i) :: ·)
| .add a b => go coeff a ∘ go coeff b
| .mulL k a
| .mulR a k => bif k == 0 then id else go (coeff * k) a
def Expr.toNormPoly (e : Expr) : Poly :=
e.toPoly.norm
def Expr.inc (e : Expr) : Expr :=
.add e (.num 1)
structure PolyCnstr where
eq : Bool
lhs : Poly
rhs : Poly
deriving BEq, ReflBEq, LawfulBEq
structure ExprCnstr where
eq : Bool
lhs : Expr
rhs : Expr
abbrev PolyCnstr.denote (ctx : Context) (c : PolyCnstr) : Prop :=
bif c.eq then
Poly.denote_eq ctx (c.lhs, c.rhs)
else
Poly.denote_le ctx (c.lhs, c.rhs)
def PolyCnstr.norm (c : PolyCnstr) : PolyCnstr :=
let (lhs, rhs) := Poly.cancel c.lhs.norm c.rhs.norm
{ eq := c.eq, lhs, rhs }
def PolyCnstr.isUnsat (c : PolyCnstr) : Bool :=
bif c.eq then
(c.lhs.isZero && c.rhs.isNonZero) || (c.lhs.isNonZero && c.rhs.isZero)
else
c.lhs.isNonZero && c.rhs.isZero
def PolyCnstr.isValid (c : PolyCnstr) : Bool :=
bif c.eq then
c.lhs.isZero && c.rhs.isZero
else
c.lhs.isZero
abbrev ExprCnstr.denote (ctx : Context) (c : ExprCnstr) : Prop :=
bif c.eq then
c.lhs.denote ctx = c.rhs.denote ctx
else
c.lhs.denote ctx ≤ c.rhs.denote ctx
def ExprCnstr.toPoly (c : ExprCnstr) : PolyCnstr :=
{ c with lhs := c.lhs.toPoly, rhs := c.rhs.toPoly }
def ExprCnstr.toNormPoly (c : ExprCnstr) : PolyCnstr :=
let (lhs, rhs) := Poly.cancel c.lhs.toNormPoly c.rhs.toNormPoly
{ c with lhs, rhs }
def monomialToExpr (k : Nat) (v : Var) : Expr :=
bif v == fixedVar then
.num k
else bif k == 1 then
.var v
else
.mulL k (.var v)
def Poly.toExpr (p : Poly) : Expr :=
match p with
| [] => .num 0
| (k, v) :: p => go (monomialToExpr k v) p
where
go (e : Expr) (p : Poly) : Expr :=
match p with
| [] => e
| (k, v) :: p => go (.add e (monomialToExpr k v)) p
def PolyCnstr.toExpr (c : PolyCnstr) : ExprCnstr :=
{ c with lhs := c.lhs.toExpr, rhs := c.rhs.toExpr }
attribute [local simp] Nat.add_comm Nat.add_assoc Nat.add_left_comm Nat.right_distrib Nat.left_distrib Nat.mul_assoc Nat.mul_comm
attribute [local simp] Poly.denote Expr.denote Poly.insert Poly.norm Poly.norm.go Poly.cancelAux
theorem Poly.denote_insert (ctx : Context) (k : Nat) (v : Var) (p : Poly) :
(p.insert k v).denote ctx = p.denote ctx + k * v.denote ctx := by
match p with
| [] => simp
| (k', v') :: p =>
by_cases h₁ : Nat.blt v v'
· simp [h₁]
· by_cases h₂ : Nat.beq v v'
· simp only [insert, h₁, h₂, cond_false, cond_true]
simp [Nat.eq_of_beq_eq_true h₂]
· simp only [insert, h₁, h₂, cond_false]
simp [denote_insert]
attribute [local simp] Poly.denote_insert
theorem Poly.denote_norm_go (ctx : Context) (p : Poly) (r : Poly) : (norm.go p r).denote ctx = p.denote ctx + r.denote ctx := by
match p with
| [] => simp
| (k, v):: p => simp [denote_norm_go]
attribute [local simp] Poly.denote_norm_go
theorem Poly.denote_sort (ctx : Context) (m : Poly) : m.norm.denote ctx = m.denote ctx := by
simp
attribute [local simp] Poly.denote_sort
theorem Poly.denote_append (ctx : Context) (p q : Poly) : (p ++ q).denote ctx = p.denote ctx + q.denote ctx := by
match p with
| [] => simp
| (k, v) :: p => simp [denote_append]
attribute [local simp] Poly.denote_append
theorem Poly.denote_cons (ctx : Context) (k : Nat) (v : Var) (p : Poly) : denote ctx ((k, v) :: p) = k * v.denote ctx + p.denote ctx := by
match p with
| [] => simp
| _ :: m => simp
attribute [local simp] Poly.denote_cons
theorem Poly.denote_reverse (ctx : Context) (p : Poly) : denote ctx (List.reverse p) = denote ctx p := by
induction p <;> simp [*]
attribute [local simp] Poly.denote_reverse
private theorem eq_of_not_blt_eq_true (h₁ : ¬ (Nat.blt x y = true)) (h₂ : ¬ (Nat.blt y x = true)) : x = y :=
have h₁ : ¬ x < y := fun h => h₁ (Nat.blt_eq.mpr h)
have h₂ : ¬ y < x := fun h => h₂ (Nat.blt_eq.mpr h)
Nat.le_antisymm (Nat.ge_of_not_lt h₂) (Nat.ge_of_not_lt h₁)
theorem Poly.denote_eq_cancelAux (ctx : Context) (fuel : Nat) (m₁ m₂ r₁ r₂ : Poly)
(h : denote_eq ctx (r₁.reverse ++ m₁, r₂.reverse ++ m₂)) : denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂) := by
induction fuel generalizing m₁ m₂ r₁ r₂ with
| zero => assumption
| succ fuel ih =>
simp
split <;> try (simp at h; try assumption)
rename_i k₁ v₁ m₁ k₂ v₂ m₂
by_cases hltv : Nat.blt v₁ v₂ <;> simp [hltv]
· apply ih; simp [denote_eq] at h |-; assumption
· by_cases hgtv : Nat.blt v₂ v₁ <;> simp [hgtv]
· apply ih; simp [denote_eq] at h |-; assumption
· have heqv : v₁ = v₂ := eq_of_not_blt_eq_true hltv hgtv; subst heqv
by_cases hltk : Nat.blt k₁ k₂ <;> simp [hltk]
· apply ih
simp [denote_eq] at h |-
have haux : k₁ * Var.denote ctx v₁ ≤ k₂ * Var.denote ctx v₁ := Nat.mul_le_mul_right _ (Nat.le_of_lt (Nat.blt_eq.mp hltk))
rw [Nat.mul_sub_right_distrib, ← Nat.add_assoc, ← Nat.add_sub_assoc haux]
apply Eq.symm
apply Nat.sub_eq_of_eq_add
simp [h]
· by_cases hgtk : Nat.blt k₂ k₁ <;> simp [hgtk]
· apply ih
simp [denote_eq] at h |-
have haux : k₂ * Var.denote ctx v₁ ≤ k₁ * Var.denote ctx v₁ := Nat.mul_le_mul_right _ (Nat.le_of_lt (Nat.blt_eq.mp hgtk))
rw [Nat.mul_sub_right_distrib, ← Nat.add_assoc, ← Nat.add_sub_assoc haux]
apply Nat.sub_eq_of_eq_add
simp [h]
· have heqk : k₁ = k₂ := eq_of_not_blt_eq_true hltk hgtk; subst heqk
apply ih
simp [denote_eq] at h |-
rw [← Nat.add_assoc, ← Nat.add_assoc] at h
exact Nat.add_right_cancel h
theorem Poly.of_denote_eq_cancelAux (ctx : Context) (fuel : Nat) (m₁ m₂ r₁ r₂ : Poly)
(h : denote_eq ctx (cancelAux fuel m₁ m₂ r₁ r₂)) : denote_eq ctx (r₁.reverse ++ m₁, r₂.reverse ++ m₂) := by
induction fuel generalizing m₁ m₂ r₁ r₂ with
| zero => assumption
| succ fuel ih =>
simp at h
split at h <;> (try simp; assumption)
rename_i k₁ v₁ m₁ k₂ v₂ m₂
by_cases hltv : Nat.blt v₁ v₂ <;> simp [hltv] at h
· have ih := ih (h := h); simp [denote_eq] at ih ⊢; assumption
· by_cases hgtv : Nat.blt v₂ v₁ <;> simp [hgtv] at h
· have ih := ih (h := h); simp [denote_eq] at ih ⊢; assumption
· have heqv : v₁ = v₂ := eq_of_not_blt_eq_true hltv hgtv; subst heqv
by_cases hltk : Nat.blt k₁ k₂ <;> simp [hltk] at h
· have ih := ih (h := h); simp [denote_eq] at ih ⊢
have haux : k₁ * Var.denote ctx v₁ ≤ k₂ * Var.denote ctx v₁ := Nat.mul_le_mul_right _ (Nat.le_of_lt (Nat.blt_eq.mp hltk))
rw [Nat.mul_sub_right_distrib, ← Nat.add_assoc, ← Nat.add_sub_assoc haux] at ih
have ih := Nat.eq_add_of_sub_eq (Nat.le_trans haux (Nat.le_add_left ..)) ih.symm
simp at ih
rw [ih]
· by_cases hgtk : Nat.blt k₂ k₁ <;> simp [hgtk] at h
· have ih := ih (h := h); simp [denote_eq] at ih ⊢
have haux : k₂ * Var.denote ctx v₁ ≤ k₁ * Var.denote ctx v₁ := Nat.mul_le_mul_right _ (Nat.le_of_lt (Nat.blt_eq.mp hgtk))
rw [Nat.mul_sub_right_distrib, ← Nat.add_assoc, ← Nat.add_sub_assoc haux] at ih
have ih := Nat.eq_add_of_sub_eq (Nat.le_trans haux (Nat.le_add_left ..)) ih
simp at ih
rw [ih]
· have heqk : k₁ = k₂ := eq_of_not_blt_eq_true hltk hgtk; subst heqk
have ih := ih (h := h); simp [denote_eq] at ih ⊢
rw [← Nat.add_assoc, ih, Nat.add_assoc]
theorem Poly.denote_eq_cancel {ctx : Context} {m₁ m₂ : Poly} (h : denote_eq ctx (m₁, m₂)) : denote_eq ctx (cancel m₁ m₂) := by
apply denote_eq_cancelAux; simp [h]
theorem Poly.of_denote_eq_cancel {ctx : Context} {m₁ m₂ : Poly} (h : denote_eq ctx (cancel m₁ m₂)) : denote_eq ctx (m₁, m₂) := by
have := Poly.of_denote_eq_cancelAux (h := h)
simp at this
assumption
theorem Poly.denote_eq_cancel_eq (ctx : Context) (m₁ m₂ : Poly) : denote_eq ctx (cancel m₁ m₂) = denote_eq ctx (m₁, m₂) :=
propext <| Iff.intro (fun h => of_denote_eq_cancel h) (fun h => denote_eq_cancel h)
attribute [local simp] Poly.denote_eq_cancel_eq
theorem Poly.denote_le_cancelAux (ctx : Context) (fuel : Nat) (m₁ m₂ r₁ r₂ : Poly)
(h : denote_le ctx (r₁.reverse ++ m₁, r₂.reverse ++ m₂)) : denote_le ctx (cancelAux fuel m₁ m₂ r₁ r₂) := by
induction fuel generalizing m₁ m₂ r₁ r₂ with
| zero => assumption
| succ fuel ih =>
simp
split <;> try (simp at h; assumption)
rename_i k₁ v₁ m₁ k₂ v₂ m₂
by_cases hltv : Nat.blt v₁ v₂ <;> simp [hltv]
· apply ih; simp [denote_le] at h |-; assumption
· by_cases hgtv : Nat.blt v₂ v₁ <;> simp [hgtv]
· apply ih; simp [denote_le] at h |-; assumption
· have heqv : v₁ = v₂ := eq_of_not_blt_eq_true hltv hgtv; subst heqv
by_cases hltk : Nat.blt k₁ k₂ <;> simp [hltk]
· apply ih
simp [denote_le] at h |-
have haux : k₁ * Var.denote ctx v₁ ≤ k₂ * Var.denote ctx v₁ := Nat.mul_le_mul_right _ (Nat.le_of_lt (Nat.blt_eq.mp hltk))
rw [Nat.mul_sub_right_distrib, ← Nat.add_assoc, ← Nat.add_sub_assoc haux]
apply Nat.le_sub_of_add_le
simp [h]
· by_cases hgtk : Nat.blt k₂ k₁ <;> simp [hgtk]
· apply ih
simp [denote_le] at h |-
have haux : k₂ * Var.denote ctx v₁ ≤ k₁ * Var.denote ctx v₁ := Nat.mul_le_mul_right _ (Nat.le_of_lt (Nat.blt_eq.mp hgtk))
rw [Nat.mul_sub_right_distrib, ← Nat.add_assoc, ← Nat.add_sub_assoc haux]
apply Nat.sub_le_of_le_add
simp [h]
· have heqk : k₁ = k₂ := eq_of_not_blt_eq_true hltk hgtk; subst heqk
apply ih
simp [denote_le] at h |-
rw [← Nat.add_assoc, ← Nat.add_assoc] at h
apply Nat.le_of_add_le_add_right h
done
theorem Poly.of_denote_le_cancelAux (ctx : Context) (fuel : Nat) (m₁ m₂ r₁ r₂ : Poly)
(h : denote_le ctx (cancelAux fuel m₁ m₂ r₁ r₂)) : denote_le ctx (r₁.reverse ++ m₁, r₂.reverse ++ m₂) := by
induction fuel generalizing m₁ m₂ r₁ r₂ with
| zero => assumption
| succ fuel ih =>
simp at h
split at h <;> try (simp; assumption)
rename_i k₁ v₁ m₁ k₂ v₂ m₂
by_cases hltv : Nat.blt v₁ v₂ <;> simp [hltv] at h
· have ih := ih (h := h); simp [denote_le] at ih ⊢; assumption
· by_cases hgtv : Nat.blt v₂ v₁ <;> simp [hgtv] at h
· have ih := ih (h := h); simp [denote_le] at ih ⊢; assumption
· have heqv : v₁ = v₂ := eq_of_not_blt_eq_true hltv hgtv; subst heqv
by_cases hltk : Nat.blt k₁ k₂ <;> simp [hltk] at h
· have ih := ih (h := h); simp [denote_le] at ih ⊢
have haux : k₁ * Var.denote ctx v₁ ≤ k₂ * Var.denote ctx v₁ := Nat.mul_le_mul_right _ (Nat.le_of_lt (Nat.blt_eq.mp hltk))
rw [Nat.mul_sub_right_distrib, ← Nat.add_assoc, ← Nat.add_sub_assoc haux] at ih
have := Nat.add_le_of_le_sub (Nat.le_trans haux (Nat.le_add_left ..)) ih
simp at this
exact this
· by_cases hgtk : Nat.blt k₂ k₁ <;> simp [hgtk] at h
· have ih := ih (h := h); simp [denote_le] at ih ⊢
have haux : k₂ * Var.denote ctx v₁ ≤ k₁ * Var.denote ctx v₁ := Nat.mul_le_mul_right _ (Nat.le_of_lt (Nat.blt_eq.mp hgtk))
rw [Nat.mul_sub_right_distrib, ← Nat.add_assoc, ← Nat.add_sub_assoc haux] at ih
have := Nat.le_add_of_sub_le ih
simp at this
exact this
· have heqk : k₁ = k₂ := eq_of_not_blt_eq_true hltk hgtk; subst heqk
have ih := ih (h := h); simp [denote_le] at ih ⊢
have := Nat.add_le_add_right ih (k₁ * Var.denote ctx v₁)
simp at this
exact this
theorem Poly.denote_le_cancel {ctx : Context} {m₁ m₂ : Poly} (h : denote_le ctx (m₁, m₂)) : denote_le ctx (cancel m₁ m₂) := by
apply denote_le_cancelAux; simp [h]
theorem Poly.of_denote_le_cancel {ctx : Context} {m₁ m₂ : Poly} (h : denote_le ctx (cancel m₁ m₂)) : denote_le ctx (m₁, m₂) := by
have := Poly.of_denote_le_cancelAux (h := h)
simp at this
assumption
theorem Poly.denote_le_cancel_eq (ctx : Context) (m₁ m₂ : Poly) : denote_le ctx (cancel m₁ m₂) = denote_le ctx (m₁, m₂) :=
propext <| Iff.intro (fun h => of_denote_le_cancel h) (fun h => denote_le_cancel h)
attribute [local simp] Poly.denote_le_cancel_eq
theorem Expr.denote_toPoly_go (ctx : Context) (e : Expr) :
(toPoly.go k e p).denote ctx = k * e.denote ctx + p.denote ctx := by
induction k, e using Expr.toPoly.go.induct generalizing p with
| case1 k k' h =>
simp [toPoly.go, eq_of_beq h]
| case2 k k' h =>
simp [toPoly.go, h, Var.denote]
| case3 k i => simp [toPoly.go]
| case4 k a b iha ihb => simp [toPoly.go, iha, ihb]
| case5 k k' a h => simp [toPoly.go, eq_of_beq h]
| case6 k a k' h ih =>
simp only [toPoly.go, denote, mul_eq]
simp [h, cond_false, ih, Nat.mul_assoc]
| case7 k a k' h =>
simp only [toPoly.go, denote, mul_eq]
simp [eq_of_beq h]
| case8 k a k' h ih =>
simp only [toPoly.go, denote, mul_eq]
simp [h, cond_false, ih, Nat.mul_assoc]
theorem Expr.denote_toPoly (ctx : Context) (e : Expr) : e.toPoly.denote ctx = e.denote ctx := by
simp [toPoly, Expr.denote_toPoly_go]
attribute [local simp] Expr.denote_toPoly
theorem Expr.eq_of_toNormPoly (ctx : Context) (a b : Expr) (h : a.toNormPoly = b.toNormPoly) : a.denote ctx = b.denote ctx := by
simp [toNormPoly, Poly.norm] at h
have h := congrArg (Poly.denote ctx) h
simp at h
assumption
theorem Expr.of_cancel_eq (ctx : Context) (a b c d : Expr) (h : Poly.cancel a.toNormPoly b.toNormPoly = (c.toPoly, d.toPoly)) : (a.denote ctx = b.denote ctx) = (c.denote ctx = d.denote ctx) := by
have := Poly.denote_eq_cancel_eq ctx a.toNormPoly b.toNormPoly
rw [h] at this
simp [toNormPoly, Poly.norm, Poly.denote_eq, -eq_iff_iff] at this
exact this.symm
theorem Expr.of_cancel_le (ctx : Context) (a b c d : Expr) (h : Poly.cancel a.toNormPoly b.toNormPoly = (c.toPoly, d.toPoly)) : (a.denote ctx ≤ b.denote ctx) = (c.denote ctx ≤ d.denote ctx) := by
have := Poly.denote_le_cancel_eq ctx a.toNormPoly b.toNormPoly
rw [h] at this
simp [toNormPoly, Poly.norm,Poly.denote_le, -eq_iff_iff] at this
exact this.symm
theorem Expr.of_cancel_lt (ctx : Context) (a b c d : Expr) (h : Poly.cancel a.inc.toNormPoly b.toNormPoly = (c.inc.toPoly, d.toPoly)) : (a.denote ctx < b.denote ctx) = (c.denote ctx < d.denote ctx) :=
of_cancel_le ctx a.inc b c.inc d h
theorem ExprCnstr.toPoly_norm_eq (c : ExprCnstr) : c.toPoly.norm = c.toNormPoly :=
rfl
theorem ExprCnstr.denote_toPoly (ctx : Context) (c : ExprCnstr) : c.toPoly.denote ctx = c.denote ctx := by
cases c; rename_i eq lhs rhs
simp [ExprCnstr.denote, PolyCnstr.denote, ExprCnstr.toPoly];
by_cases h : eq = true <;> simp [h]
· simp [Poly.denote_eq]
· simp [Poly.denote_le]
attribute [local simp] ExprCnstr.denote_toPoly
theorem ExprCnstr.denote_toNormPoly (ctx : Context) (c : ExprCnstr) : c.toNormPoly.denote ctx = c.denote ctx := by
cases c; rename_i eq lhs rhs
simp [ExprCnstr.denote, PolyCnstr.denote, ExprCnstr.toNormPoly]
by_cases h : eq = true <;> simp [h]
· rw [Poly.denote_eq_cancel_eq]; simp [Poly.denote_eq, Expr.toNormPoly, Poly.norm]
· rw [Poly.denote_le_cancel_eq]; simp [Poly.denote_le, Expr.toNormPoly, Poly.norm]
attribute [local simp] ExprCnstr.denote_toNormPoly
theorem Poly.of_isZero (ctx : Context) {p : Poly} (h : isZero p = true) : p.denote ctx = 0 := by
simp [isZero] at h
split at h
· simp
· contradiction
theorem Poly.of_isNonZero (ctx : Context) {p : Poly} (h : isNonZero p = true) : p.denote ctx > 0 := by
match p with
| [] => contradiction
| (k, v) :: p =>
by_cases he : v == fixedVar <;> simp [he, isNonZero] at h ⊢
· simp [eq_of_beq he, Var.denote]; apply Nat.lt_of_succ_le; exact Nat.le_trans h (Nat.le_add_right ..)
· have ih := of_isNonZero ctx h
exact Nat.le_trans ih (Nat.le_add_right ..)
theorem PolyCnstr.eq_false_of_isUnsat (ctx : Context) {c : PolyCnstr} : c.isUnsat → c.denote ctx = False := by
cases c; rename_i eq lhs rhs
simp [isUnsat]
by_cases he : eq = true <;> simp [he, denote, Poly.denote_eq, Poly.denote_le, -and_imp]
· intro
| Or.inl ⟨h₁, h₂⟩ => simp [Poly.of_isZero, h₁]; have := Nat.ne_zero_of_lt (Poly.of_isNonZero ctx h₂); simp [this.symm]
| Or.inr ⟨h₁, h₂⟩ => simp [Poly.of_isZero, h₂]; have := Nat.ne_zero_of_lt (Poly.of_isNonZero ctx h₁); simp [this]
· intro ⟨h₁, h₂⟩
simp [Poly.of_isZero, h₂]
exact Poly.of_isNonZero ctx h₁
theorem PolyCnstr.eq_true_of_isValid (ctx : Context) {c : PolyCnstr} : c.isValid → c.denote ctx = True := by
cases c; rename_i eq lhs rhs
simp [isValid]
by_cases he : eq = true <;> simp [he, denote, Poly.denote_eq, Poly.denote_le, -and_imp]
· intro ⟨h₁, h₂⟩
simp [Poly.of_isZero, h₁, h₂]
· intro h
simp [Poly.of_isZero, h]
theorem ExprCnstr.eq_false_of_isUnsat (ctx : Context) (c : ExprCnstr) (h : c.toNormPoly.isUnsat) : c.denote ctx = False := by
have := PolyCnstr.eq_false_of_isUnsat ctx h
simp [-eq_iff_iff] at this
assumption
theorem ExprCnstr.eq_true_of_isValid (ctx : Context) (c : ExprCnstr) (h : c.toNormPoly.isValid) : c.denote ctx = True := by
have := PolyCnstr.eq_true_of_isValid ctx h
simp [-eq_iff_iff] at this
assumption
theorem ExprCnstr.eq_of_toNormPoly_eq (ctx : Context) (c d : ExprCnstr) (h : c.toNormPoly == d.toPoly) : c.denote ctx = d.denote ctx := by
have h := congrArg (PolyCnstr.denote ctx) (eq_of_beq h)
simp [-eq_iff_iff] at h
assumption
theorem Expr.eq_of_toNormPoly_eq (ctx : Context) (e e' : Expr) (h : e.toNormPoly == e'.toPoly) : e.denote ctx = e'.denote ctx := by
have h := congrArg (Poly.denote ctx) (eq_of_beq h)
simp [Expr.toNormPoly, Poly.norm] at h
assumption
end Linear
def elimOffset {α : Sort u} (a b k : Nat) (h₁ : a + k = b + k) (h₂ : a = b → α) : α :=
h₂ (Nat.add_right_cancel h₁)
end Nat