section ‹Clausal Logic›
theory Clausal_Logic
imports Nested_Multisets_Ordinals.Multiset_More
begin
text ‹
Resolution operates of clauses, which are disjunctions of literals. The material formalized here
corresponds roughly to Sections 2.1 (``Formulas and Clauses'') of Bachmair and Ganzinger, excluding
the formula and term syntax.
›
subsection ‹Literals›
text ‹
Literals consist of a polarity (positive or negative) and an atom, of type @{typ 'a}.
›
datatype 'a literal =
is_pos: Pos (atm_of: 'a)
| Neg (atm_of: 'a)
abbreviation is_neg :: "'a literal ⇒ bool" where
"is_neg L ≡ ¬ is_pos L"
lemma Pos_atm_of_iff[simp]: "Pos (atm_of L) = L ⟷ is_pos L"
by (cases L) simp+
lemma Neg_atm_of_iff[simp]: "Neg (atm_of L) = L ⟷ is_neg L"
by (cases L) simp+
lemma set_literal_atm_of: "set_literal L = {atm_of L}"
by (cases L) simp+
lemma ex_lit_cases: "(∃L. P L) ⟷ (∃A. P (Pos A) ∨ P (Neg A))"
by (metis literal.exhaust)
instantiation literal :: (type) uminus
begin
definition uminus_literal :: "'a literal ⇒ 'a literal" where
"uminus L = (if is_pos L then Neg else Pos) (atm_of L)"
instance ..
end
lemma
uminus_Pos[simp]: "- Pos A = Neg A" and
uminus_Neg[simp]: "- Neg A = Pos A"
unfolding uminus_literal_def by simp_all
lemma atm_of_uminus[simp]: "atm_of (-L) = atm_of L"
by (case_tac L, auto)
lemma uminus_of_uminus_id[simp]: "- (- (x :: 'v literal)) = x"
by (simp add: uminus_literal_def)
lemma uminus_not_id[simp]: "x ≠ - (x:: 'v literal)"
by (case_tac x) auto
lemma uminus_not_id'[simp]: "- x ≠ (x:: 'v literal)"
by (case_tac x, auto)
lemma uminus_eq_inj[iff]: "- (a::'v literal) = - b ⟷ a = b"
by (case_tac a; case_tac b) auto+
lemma uminus_lit_swap: "(a::'a literal) = - b ⟷ - a = b"
by auto
lemma is_pos_neg_not_is_pos: "is_pos (- L) ⟷ ¬ is_pos L"
by (cases L) auto
instantiation literal :: (preorder) preorder
begin
definition less_literal :: "'a literal ⇒ 'a literal ⇒ bool" where
"less_literal L M ⟷ atm_of L < atm_of M ∨ atm_of L ≤ atm_of M ∧ is_neg L < is_neg M"
definition less_eq_literal :: "'a literal ⇒ 'a literal ⇒ bool" where
"less_eq_literal L M ⟷ atm_of L < atm_of M ∨ atm_of L ≤ atm_of M ∧ is_neg L ≤ is_neg M"
instance
apply intro_classes
unfolding less_literal_def less_eq_literal_def by (auto intro: order_trans simp: less_le_not_le)
end
instantiation literal :: (order) order
begin
instance
by intro_classes (auto simp: less_eq_literal_def intro: literal.expand)
end
lemma pos_less_neg[simp]: "Pos A < Neg A"
unfolding less_literal_def by simp
lemma pos_less_pos_iff[simp]: "Pos A < Pos B ⟷ A < B"
unfolding less_literal_def by simp
lemma pos_less_neg_iff[simp]: "Pos A < Neg B ⟷ A ≤ B"
unfolding less_literal_def by (auto simp: less_le_not_le)
lemma neg_less_pos_iff[simp]: "Neg A < Pos B ⟷ A < B"
unfolding less_literal_def by simp
lemma neg_less_neg_iff[simp]: "Neg A < Neg B ⟷ A < B"
unfolding less_literal_def by simp
lemma pos_le_neg[simp]: "Pos A ≤ Neg A"
unfolding less_eq_literal_def by simp
lemma pos_le_pos_iff[simp]: "Pos A ≤ Pos B ⟷ A ≤ B"
unfolding less_eq_literal_def by (auto simp: less_le_not_le)
lemma pos_le_neg_iff[simp]: "Pos A ≤ Neg B ⟷ A ≤ B"
unfolding less_eq_literal_def by (auto simp: less_imp_le)
lemma neg_le_pos_iff[simp]: "Neg A ≤ Pos B ⟷ A < B"
unfolding less_eq_literal_def by simp
lemma neg_le_neg_iff[simp]: "Neg A ≤ Neg B ⟷ A ≤ B"
unfolding less_eq_literal_def by (auto simp: less_imp_le)
lemma leq_imp_less_eq_atm_of: "L ≤ M ⟹ atm_of L ≤ atm_of M"
unfolding less_eq_literal_def using less_imp_le by blast
instantiation literal :: (linorder) linorder
begin
instance
apply intro_classes
unfolding less_eq_literal_def less_literal_def by auto
end
instantiation literal :: (wellorder) wellorder
begin
instance
proof intro_classes
fix P :: "'a literal ⇒ bool" and L :: "'a literal"
assume ih: "⋀L. (⋀M. M < L ⟹ P M) ⟹ P L"
have "⋀x. (⋀y. y < x ⟹ P (Pos y) ∧ P (Neg y)) ⟹ P (Pos x) ∧ P (Neg x)"
by (rule conjI[OF ih ih])
(auto simp: less_literal_def atm_of_def split: literal.splits intro: ih)
then have "⋀A. P (Pos A) ∧ P (Neg A)"
by (rule less_induct) blast
then show "P L"
by (cases L) simp+
qed
end
subsection ‹Clauses›
text ‹
Clauses are (finite) multisets of literals.
›
type_synonym 'a clause = "'a literal multiset"
abbreviation map_clause :: "('a ⇒ 'b) ⇒ 'a clause ⇒ 'b clause" where
"map_clause f ≡ image_mset (map_literal f)"
abbreviation rel_clause :: "('a ⇒ 'b ⇒ bool) ⇒ 'a clause ⇒ 'b clause ⇒ bool" where
"rel_clause R ≡ rel_mset (rel_literal R)"
abbreviation poss :: "'a multiset ⇒ 'a clause" where "poss AA ≡ {#Pos A. A ∈# AA#}"
abbreviation negs :: "'a multiset ⇒ 'a clause" where "negs AA ≡ {#Neg A. A ∈# AA#}"
lemma Max_in_lits: "C ≠ {#} ⟹ Max_mset C ∈# C"
by simp
lemma Max_atm_of_set_mset_commute: "C ≠ {#} ⟹ Max (atm_of ` set_mset C) = atm_of (Max_mset C)"
by (rule mono_Max_commute[symmetric]) (auto simp: mono_def less_eq_literal_def)
lemma Max_pos_neg_less_multiset:
assumes max: "Max_mset C = Pos A" and neg: "Neg A ∈# D"
shows "C < D"
proof -
have "Max_mset C < Neg A"
using max by simp
then show ?thesis
using neg by (metis (no_types) Max_less_iff empty_iff ex_gt_imp_less_multiset finite_set_mset)
qed
lemma pos_Max_imp_neg_notin: "Max_mset C = Pos A ⟹ Neg A ∉# C"
using Max_pos_neg_less_multiset by blast
lemma less_eq_Max_lit: "C ≠ {#} ⟹ C ≤ D ⟹ Max_mset C ≤ Max_mset D"
proof (unfold less_eq_multiset⇩H⇩O)
assume
ne: "C ≠ {#}" and
ex_gt: "∀x. count D x < count C x ⟶ (∃y > x. count C y < count D y)"
from ne have "Max_mset C ∈# C"
by (fast intro: Max_in_lits)
then have "∃l. l ∈# D ∧ ¬ l < Max_mset C"
using ex_gt by (metis count_greater_zero_iff count_inI less_not_sym)
then have "¬ Max_mset D < Max_mset C"
by (metis Max.coboundedI[OF finite_set_mset] le_less_trans)
then show ?thesis
by simp
qed
definition atms_of :: "'a clause ⇒ 'a set" where
"atms_of C = atm_of ` set_mset C"
lemma atms_of_empty[simp]: "atms_of {#} = {}"
unfolding atms_of_def by simp
lemma atms_of_singleton[simp]: "atms_of {#L#} = {atm_of L}"
unfolding atms_of_def by auto
lemma atms_of_add_mset[simp]: "atms_of (add_mset a A) = insert (atm_of a) (atms_of A)"
unfolding atms_of_def by auto
lemma atms_of_union_mset[simp]: "atms_of (A ∪# B) = atms_of A ∪ atms_of B"
unfolding atms_of_def by auto
lemma finite_atms_of[iff]: "finite (atms_of C)"
by (simp add: atms_of_def)
lemma atm_of_lit_in_atms_of: "L ∈# C ⟹ atm_of L ∈ atms_of C"
by (simp add: atms_of_def)
lemma atms_of_plus[simp]: "atms_of (C + D) = atms_of C ∪ atms_of D"
unfolding atms_of_def by auto
lemma in_atms_of_minusD: "x ∈ atms_of (A - B) ⟹ x ∈ atms_of A"
by (auto simp: atms_of_def dest: in_diffD)
lemma pos_lit_in_atms_of: "Pos A ∈# C ⟹ A ∈ atms_of C"
unfolding atms_of_def by force
lemma neg_lit_in_atms_of: "Neg A ∈# C ⟹ A ∈ atms_of C"
unfolding atms_of_def by force
lemma atm_imp_pos_or_neg_lit: "A ∈ atms_of C ⟹ Pos A ∈# C ∨ Neg A ∈# C"
unfolding atms_of_def image_def mem_Collect_eq by (metis Neg_atm_of_iff Pos_atm_of_iff)
lemma atm_iff_pos_or_neg_lit: "A ∈ atms_of L ⟷ Pos A ∈# L ∨ Neg A ∈# L"
by (auto intro: pos_lit_in_atms_of neg_lit_in_atms_of dest: atm_imp_pos_or_neg_lit)
lemma atm_of_eq_atm_of: "atm_of L = atm_of L' ⟷ (L = L' ∨ L = -L')"
by (cases L; cases L') auto
lemma atm_of_in_atm_of_set_iff_in_set_or_uminus_in_set: "atm_of L ∈ atm_of ` I ⟷ (L ∈ I ∨ -L ∈ I)"
by (auto intro: rev_image_eqI simp: atm_of_eq_atm_of)
lemma lits_subseteq_imp_atms_subseteq: "set_mset C ⊆ set_mset D ⟹ atms_of C ⊆ atms_of D"
unfolding atms_of_def by blast
lemma atms_empty_iff_empty[iff]: "atms_of C = {} ⟷ C = {#}"
unfolding atms_of_def image_def Collect_empty_eq by auto
lemma
atms_of_poss[simp]: "atms_of (poss AA) = set_mset AA" and
atms_of_negs[simp]: "atms_of (negs AA) = set_mset AA"
unfolding atms_of_def image_def by auto
lemma less_eq_Max_atms_of: "C ≠ {#} ⟹ C ≤ D ⟹ Max (atms_of C) ≤ Max (atms_of D)"
unfolding atms_of_def
by (metis Max_atm_of_set_mset_commute leq_imp_less_eq_atm_of less_eq_Max_lit
less_eq_multiset_empty_right)
lemma le_multiset_Max_in_imp_Max:
"Max (atms_of D) = A ⟹ C ≤ D ⟹ A ∈ atms_of C ⟹ Max (atms_of C) = A"
by (metis Max.coboundedI[OF finite_atms_of] atms_of_def empty_iff eq_iff image_subsetI
less_eq_Max_atms_of set_mset_empty subset_Compl_self_eq)
lemma atm_of_Max_lit[simp]: "C ≠ {#} ⟹ atm_of (Max_mset C) = Max (atms_of C)"
unfolding atms_of_def Max_atm_of_set_mset_commute ..
lemma Max_lit_eq_pos_or_neg_Max_atm:
"C ≠ {#} ⟹ Max_mset C = Pos (Max (atms_of C)) ∨ Max_mset C = Neg (Max (atms_of C))"
by (metis Neg_atm_of_iff Pos_atm_of_iff atm_of_Max_lit)
lemma atms_less_imp_lit_less_pos: "(⋀B. B ∈ atms_of C ⟹ B < A) ⟹ L ∈# C ⟹ L < Pos A"
unfolding atms_of_def less_literal_def by force
lemma atms_less_eq_imp_lit_less_eq_neg: "(⋀B. B ∈ atms_of C ⟹ B ≤ A) ⟹ L ∈# C ⟹ L ≤ Neg A"
unfolding less_eq_literal_def by (simp add: atm_of_lit_in_atms_of)
end