Zulip Chat Archive
Stream: lean4
Topic: whats the lemma for (a = true) <-> a (classical logic)
Jared green (Feb 29 2024 at 18:48):
in this code:
import Init.Data.List
import Std.Data.List
import Mathlib.Data.List.Dedup
import Mathlib.Data.List.Pairwise
import Mathlib.Data.List.Join
import Mathlib.Data.List.Basic
import Mathlib.Data.List.Defs
import Mathlib.Data.List.Infix
import Mathlib.Data.List.Lattice
import Mathlib.Data.List.Lemmas
import Mathlib.Data.Bool.AllAny
import Mathlib.Data.Bool.Basic
open Classical
variable {α : Type}[h : DecidableEq α]
inductive normalizable α (pred : α -> Prop)
where
| atom : α -> (normalizable α pred)
| And : (normalizable α pred) -> (normalizable α pred) -> normalizable α pred
| Or : (normalizable α pred) -> (normalizable α pred) -> normalizable α pred
| Not : normalizable α pred -> normalizable α pred
deriving DecidableEq
namespace normalizable
@[reducible]
def toProp (n : normalizable α pred) : Prop :=
match n with
| atom a => pred a
| And a b => toProp a ∧ toProp b
| Or a b => (toProp a) ∨ toProp b
| Not i => ¬(toProp i)
@[simp]
theorem toProp_not : toProp (Not n₁) ↔ ¬ toProp n₁ := Iff.rfl
@[simp]
theorem toProp_and : toProp (And n₁ n₂) ↔ toProp n₁ ∧ toProp n₂ := Iff.rfl
@[simp]
theorem toProp_or : toProp (Or n₁ n₂) ↔ toProp n₁ ∨ toProp n₂ := Iff.rfl
@[simp]
theorem toProp_atom {a : α} : toProp (atom a : normalizable α pred) ↔ pred a := Iff.rfl
def subnormalize (n : (normalizable α pred)) : List (List (List (normalizable α pred))) :=
match n with
| Or a b => [[a,n],[b,n],[Not a,Not b, Not n]] :: (List.append (subnormalize a) (subnormalize b))
| And a b => [[a,b,n],[Not a,Not n],[Not b,Not n]] :: (List.append (subnormalize a) (subnormalize b))
| Not i => [[n,Not i],[Not n, i]] :: (subnormalize i)
| atom _ => [[[n],[Not n]]]
def normalize : normalizable α pred -> List (List (List (normalizable α pred))) := fun o =>
[[o]] :: (subnormalize o)
def nStrip (n : normalizable α pred) : Bool × normalizable α pred :=
match n with
| Not i => (false,i)
| i => (true,i)
def booleanize (n : List (List (List (normalizable α pred)))) : List (List (List (Bool × normalizable α pred))) :=
n.map (fun x => x.map (fun y => y.map (fun z => nStrip z)))
def normalizel (n : normalizable α pred) : List (List (List (Bool × normalizable α pred))) :=
booleanize (normalize n)
def wToProp (w : Bool × normalizable α pred) : Prop :=
if w.fst then toProp w.snd else ¬(toProp w.snd)
def sToProp (s : List (Bool × normalizable α pred)) : Prop :=
s.all (fun x => wToProp x)
def gToProp (g : List (List (Bool × normalizable α pred))) : Prop :=
g.any (fun x => sToProp x)
def nToProp (n : List (List (List (Bool × normalizable α pred)))) : Prop :=
n.all (fun x => gToProp x)
def fToProp (n : List (List (List (normalizable α pred)))) : Prop :=
n.all (fun x => x.any (fun y => y.all (fun z => toProp z)))
theorem nStrip_equiv : ∀ n : normalizable α pred, toProp n <-> wToProp (nStrip n) :=
by
intro n
unfold nStrip
induction n
simp
unfold wToProp
simp
simp
unfold wToProp
simp
unfold wToProp
simp
simp
unfold wToProp
simp
theorem booleanize_eqiv : ∀ n : List (List (List (normalizable α pred))), fToProp n <-> nToProp (booleanize n) :=
by
intro n
unfold nToProp
simp
unfold fToProp
simp
unfold booleanize
simp
unfold gToProp
simp
unfold sToProp
simp
simp [nStrip_equiv]
theorem andGateTaut : (a ∧ b ∧ (a ∧ b)) ∨ (¬ a ∧ ¬(a ∧ b)) ∨ (¬ b ∧ ¬(a ∧ b)) :=
by
cases Classical.em a
cases Classical.em b
left
constructor
assumption
constructor
assumption
constructor
assumption
assumption
right
right
constructor
assumption
push_neg
intro
assumption
right
left
constructor
assumption
rw [and_comm]
push_neg
intro
assumption
theorem orGateTaut : (a ∧ (a ∨ b)) ∨ (b ∧ (a ∨ b)) ∨ ((¬ a) ∧ (¬b) ∧ ¬(a ∨ b)) :=
by
cases Classical.em a
left
constructor
assumption
left
assumption
right
cases Classical.em b
left
constructor
assumption
right
assumption
right
constructor
assumption
constructor
assumption
push_neg
constructor
assumption
assumption
theorem all_and : List.all ( a ++ b) c <-> List.all a c ∧ List.all b c :=
by
simp
constructor
intro ha
constructor
intro b
intro hb
apply ha
left
exact hb
intro c
intro hc
apply ha
right
exact hc
intro ha
intro b
intro hb
cases hb
apply ha.left
assumption
apply ha.right
assumption
theorem subnormal : ∀ n : normalizable α pred, fToProp (subnormalize n) :=
by
intro n
induction' n with a b c d e f g i j k l
unfold subnormalize
unfold fToProp
simp
unfold toProp
apply Classical.em
unfold subnormalize
simp
unfold fToProp
rw [List.all_cons]
simp only [List.any_cons, List.all_cons, List.all_nil, Bool.and_true, List.any_nil,
Bool.or_false, Bool.and_eq_true, Bool.or_eq_true, decide_eq_true_eq,
List.mem_append, List.any_eq_true,toProp_not,toProp_and]
constructor
rw [toProp_not]
rw [toProp_and]
exact andGateTaut
rw [all_and]
constructor
assumption
assumption
unfold fToProp
unfold subnormalize
rw [List.all_cons]
simp only [List.any_cons, List.all_cons, toProp_or, List.all_nil, Bool.and_true, toProp_not,
List.any_nil, Bool.or_false, List.append_eq, Bool.and_eq_true, Bool.or_eq_true,
decide_eq_true_eq, List.mem_append, List.any_eq_true]
constructor
rw [toProp_not]
rw [toProp_or]
exact orGateTaut
rw [all_and]
constructor
assumption
assumption
unfold fToProp
unfold subnormalize
rw [List.all_cons]
simp only [List.any_cons, List.all_cons, toProp_not, List.all_nil, Bool.and_true, Bool.and_self,
not_not, List.any_nil, Bool.or_false, Bool.and_eq_true, Bool.or_eq_true, decide_eq_true_eq,
List.any_eq_true]
constructor
cases Classical.em (toProp k)
right
assumption
left
assumption
unfold fToProp at l
exact l
theorem normal : ∀ n : normalizable α pred, toProp n <-> nToProp (normalizel n) :=
by
intro n
unfold normalizel
unfold normalize
rw [← booleanize_eqiv]
unfold fToProp
simp only [List.all_cons, List.any_cons, List.all_nil, Bool.and_true, List.any_nil, Bool.or_false,
Bool.and_eq_true, decide_eq_true_eq, List.any_eq_true, iff_self_and]
intro
apply subnormal
def coherent (n : List (List (List (Bool × normalizable α pred)))) : Prop :=
∀ g : List (List (Bool × normalizable α pred)), g ∈ n ->
∀ s : List (Bool × normalizable α pred), s ∈ g ->
(∀ w : Bool × normalizable α pred,∀ x : Bool × normalizable α pred, w ∈ s ∧ x ∈ s ->
w.snd == x.snd -> w.fst == x.fst) ∧ s.Nodup
def makeCoherent (n : List (List (List (Bool × normalizable α pred)))) : List (List (List (Bool × normalizable α pred))) :=
n.map
(fun x => (x.filter
(fun y => y.Pairwise
(fun a b => a.snd == b.snd -> a.fst == b.fst))).map
(fun y => y.dedup))
theorem coherency : ∀ n : List (List (List (Bool × normalizable α pred))), coherent (makeCoherent n) :=
by
intro n g hg s hs
unfold makeCoherent at hg
obtain ⟨a, ha_in_n, ha_transformed_to_g⟩ := List.mem_map.mp hg
subst ha_transformed_to_g
constructor
intros w x hw heq
rw [List.mem_map] at hs
obtain ⟨b, hb_in_filtered_a, hb_eq_s⟩ := hs
subst hb_eq_s
rw [List.mem_filter] at hb_in_filtered_a
obtain ⟨hb_in_a, hb_pw⟩ := hb_in_filtered_a
have hb_pairwise : b.Pairwise (fun c d => c.snd = d.snd → c.fst = d.fst) :=
by {
rw [decide_eq_true_iff] at hb_pw
exact hb_pw
}
Matt Diamond (Feb 29 2024 at 20:47):
you can just use simpa
:
have hb_pairwise : b.Pairwise (fun c d => c.snd = d.snd → c.fst = d.fst) := by simpa using hb_pw
Jared green (Feb 29 2024 at 21:34):
similar problem:
theorem coherency : ∀ n : List (List (List (Bool × normalizable α pred))), coherent (makeCoherent n) :=
by
intro n g hg s hs
unfold makeCoherent at hg
obtain ⟨a, ha_in_n, ha_transformed_to_g⟩ := List.mem_map.mp hg
subst ha_transformed_to_g
constructor
intros w x hw heqw
rw [List.mem_map] at hs
obtain ⟨b, hb_in_filtered_a, hb_eq_s⟩ := hs
subst hb_eq_s
rw [List.mem_filter] at hb_in_filtered_a
obtain ⟨hb_in_a, hb_pw⟩ := hb_in_filtered_a
have hb_pairwise : b.Pairwise (fun c d => c.snd = d.snd → c.fst = d.fst) := by simpa using hb_pw
have snd_eq : w.snd = x.snd := by {
}
Jared green (Feb 29 2024 at 21:35):
(nevermind)
Chris Wong (Mar 03 2024 at 01:42):
Next time can you please post a #mwe. You'll get a faster answer if you clean up your code first.
Last updated: May 02 2025 at 03:31 UTC