:: Algebraic Approach to Algorithmic Logic :: by Grzegorz Bancerek :: :: Received September 15, 2014 :: Copyright (c) 2014-2021 Association of Mizar Users :: (Stowarzyszenie Uzytkownikow Mizara, Bialystok, Poland). :: This code can be distributed under the GNU General Public Licence :: version 3.0 or later, or the Creative Commons Attribution-ShareAlike :: License version 3.0 or later, subject to the binding interpretation :: detailed in file COPYING.interpretation. :: See COPYING.GPL and COPYING.CC-BY-SA for the full text of these :: licenses, or see http://www.gnu.org/licenses/gpl.html and :: http://creativecommons.org/licenses/by-sa/3.0/. environ vocabularies FUNCT_1, PBOOLE, UNIALG_1, MSUALG_1, FINSEQ_1, MSUALG_6, FINSET_1, FUNCT_7, ORDINAL2, ARYTM_3, RELAT_1, CATALG_1, XBOOLE_0, FOMODEL2, ZFMISC_1, ORDINAL1, STRUCT_0, SUBSET_1, TARSKI, CARD_3, MARGREL1, CARD_1, FUNCOP_1, FUNCT_3, NUMBERS, ARYTM_1, NAT_1, FACIRC_1, XXREAL_0, ORDINAL4, FUNCT_2, INCPROJ, FUNCT_4, COMPUT_1, PARTFUN1, WELLORD1, MSAFREE, UNIALG_2, AOFA_000, AOFA_L00, MCART_1, AOFA_A00, GRAPHSP, QC_LANG1, ZF_LANG, FOMODEL1, SETLIM_2, REAL_1, INSTALG1, PUA2MSS1, MATROID0, ALGSPEC1; notations TARSKI, XBOOLE_0, ZFMISC_1, SUBSET_1, RELAT_1, ENUMSET1, MCART_1, MATROID0, XTUPLE_0, FUNCT_1, RELSET_1, FUNCT_2, BINOP_1, FINSET_1, FINSEQ_1, FINSEQ_2, FUNCOP_1, NUMBERS, XREAL_0, NAT_1, NAT_D, FUNCT_3, FUNCT_4, MARGREL1, FUNCT_7, ORDINAL1, ORDINAL2, PBOOLE, CARD_1, CARD_3, FINSEQ_4, XXREAL_0, XCMPLX_0, STRUCT_0, FACIRC_1, COMPUT_1, INSTALG1, CATALG_1, UNIALG_1, MSUALG_1, MSAFREE, PUA2MSS1, UNIALG_2, FREEALG, CIRCCOMB, CLOSURE2, MSUALG_6, ALGSPEC1, MSAFREE3, MSAFREE4, PARTFUN1, AOFA_000, AOFA_A00, MSAFREE5; constructors RELAT_1, FUNCT_1, XXREAL_0, FINSEQ_1, FINSEQ_3, ENUMSET1, FUNCOP_1, NAT_1, FUNCT_4, BINOP_1, FUNCT_7, ORDINAL1, XCMPLX_0, CARD_1, CARD_3, FINSEQ_4, FACIRC_1, STRUCT_0, UNIALG_1, MSUALG_1, INSTALG1, MSUALG_6, PBOOLE, MARGREL1, FUNCT_2, REALSET2, RELSET_1, COMPUT_1, AOFA_000, PUA2MSS1, FREEALG, UNIALG_2, ZFMISC_1, SUBSET_1, NUMBERS, FINSEQ_2, MSAFREE, MSAFREE3, CATALG_1, CLOSURE2, MSAFREE4, AOFA_A00, XTUPLE_0, ARYTM_1, NAT_D, ORDINAL2, CIRCCOMB, ALGSPEC1, MSAFREE5, RELSET_2; registrations XBOOLE_0, SUBSET_1, FUNCT_1, ORDINAL1, RELSET_1, FUNCOP_1, FACIRC_1, NAT_1, FINSEQ_2, PBOOLE, STRUCT_0, FINSEQ_1, XXREAL_0, UNIALG_1, INSTALG1, CATALG_1, CARD_1, MSUALG_1, XREAL_0, RELAT_1, FUNCT_2, ZFMISC_1, FUNCT_4, XTUPLE_0, INDEX_1, MSAFREE4, AOFA_A00, MSUALG_9, CIRCCOMB, FOMODEL0, RAMSEY_1; requirements BOOLE, SUBSET, NUMERALS, ARITHM, REAL; begin :: Algorithmic language signature reserve X,Y for set, x,y,z for object, i,j,n for natural number; registration let f be non empty-yielding Function; cluster Union f -> non empty; end; definition let I be set; let f be ManySortedSet of I; let i be set; let x; redefine func f+*(i,x) -> ManySortedSet of I; end; registration let I be set; let f be non-empty ManySortedSet of I; let i be set; let x be non empty set; cluster f+*(i,x) -> non-empty; end; registration let S be non empty non void ManySortedSign; cluster non-empty for strict VarMSAlgebra over S; end; definition let f,g be Function; attr g is f-tolerating means :: AOFA_L00:def 1 f tolerates g; end; theorem :: AOFA_L00:1 for f,g being Function holds g is f-tolerating iff for x st x in dom f & x in dom g holds f.x = g.x; theorem :: AOFA_L00:2 for I,J being set for f being ManySortedSet of I for g being ManySortedSet of J holds g is f-tolerating iff for x st x in I & x in J holds f.x = g.x; theorem :: AOFA_L00:3 for f,g being Function holds f tolerates g+*f; registration let X,Y be Function; cluster Y+*X -> X-tolerating; end; registration let X be Function; let J be set; let Y be ManySortedSet of J; cluster Y+*(X|J) -> X-tolerating; end; registration let J be set; let X be Function; cluster X-tolerating for ManySortedSet of J; end; registration let J be set; let X be non-empty Function; cluster X-tolerating for non-empty ManySortedSet of J; end; registration let I be non empty set; let X be non empty-yielding ManySortedSet of I; cluster Union X -> non empty; end; theorem :: AOFA_L00:4 for S being non empty non void ManySortedSign for o being OperSymbol of S, r being SortSymbol of S, T being MSAlgebra over S holds o is_of_type {},r implies {} in Args(o,T); theorem :: AOFA_L00:5 for S being non empty non void ManySortedSign for o being OperSymbol of S, s,r being SortSymbol of S, T being MSAlgebra over S holds o is_of_type <*s*>,r & x in (the Sorts of T).s implies <*x*> in Args(o,T); theorem :: AOFA_L00:6 for S being non empty non void ManySortedSign for o being OperSymbol of S, s1,s2,r being SortSymbol of S, T being MSAlgebra over S holds o is_of_type <*s1,s2*>,r & x in (the Sorts of T).s1 & y in (the Sorts of T).s2 implies <*x,y*> in Args(o,T); theorem :: AOFA_L00:7 for S being non empty non void ManySortedSign for o being OperSymbol of S, s1,s2,s3,r being SortSymbol of S, T being MSAlgebra over S holds o is_of_type <*s1,s2,s3*>,r & x in (the Sorts of T).s1 & y in (the Sorts of T).s2 & z in (the Sorts of T).s3 implies <*x,y,z*> in Args(o,T); definition let S,E be Signature; attr E is S-extension means :: AOFA_L00:def 2 S is Subsignature of E; end; registration let S be Signature; cluster -> S-extension for Extension of S; end; theorem :: AOFA_L00:8 for S,E being non empty Signature st E is S-extension for a being SortSymbol of S holds a is SortSymbol of E; theorem :: AOFA_L00:9 for S,E being non void Signature st E is S-extension for o being OperSymbol of S for a being set for r being Element of S for r1 being Element of E st r = r1 & o is_of_type a,r holds o is_of_type a,r1; definition let X be Function; let J,Y be set; func X extended_by(Y,J) -> ManySortedSet of J equals :: AOFA_L00:def 3 (J-->Y)+*(X|J); end; registration let X be Function; let J,Y be set; cluster X extended_by(Y,J) -> X-tolerating; end; definition struct(ConnectivesSignature) PCLangSignature(# carrier -> set, carrier' -> set, Arity -> Function of the carrier', the carrier*, ResultSort -> Function of the carrier', the carrier, formula-sort -> (Element of the carrier), connectives -> (FinSequence of the carrier') :: <* not-op, and-op, or-op, imp-op, iff-op, true *> #); end; definition let X be set; :: set of variable symbols struct(PCLangSignature) QCLangSignature over X(# carrier -> set, carrier' -> set, Arity -> Function of the carrier', the carrier*, ResultSort -> Function of the carrier', the carrier, formula-sort -> (Element of the carrier), connectives -> (FinSequence of the carrier'), :: <* not-op, and-op, or-op, imp-op, iff-op, true *> quant-sort -> set, quantifiers -> Function of [:the quant-sort, X:], the carrier' #); end; definition let X be set; struct(QCLangSignature over X) AlgLangSignature over X(# carrier -> set, carrier' -> set, Arity -> Function of the carrier', the carrier*, ResultSort -> Function of the carrier', the carrier, formula-sort, program-sort -> (Element of the carrier), connectives -> (FinSequence of the carrier'), :: <* not-op, and-op, or-op, imp-op, iff-op, true, alg-imp *> quant-sort -> set, quantifiers -> Function of [:the quant-sort, X:], the carrier' #); end; definition let n be Nat; let L be PCLangSignature; attr L is n PC-correct means :: AOFA_L00:def 4 len the connectives of L >= n+5 & (the connectives of L)|{n,n+1,n+2,n+3,n+4,n+5} is one-to-one & (the connectives of L).n is_of_type <*the formula-sort of L*>, the formula-sort of L & (the connectives of L).(n+5) is_of_type {}, the formula-sort of L & ((the connectives of L).(n+1) is_of_type <*the formula-sort of L, the formula-sort of L*>, the formula-sort of L & ... & (the connectives of L).(n+4) is_of_type <*the formula-sort of L, the formula-sort of L*>, the formula-sort of L); end; definition let X; let L be QCLangSignature over X; attr L is QC-correct means :: AOFA_L00:def 5 :: (ex q1,q2 being set st q1 <> q2 & the quant-sort of L = {q1,q2}) & the quant-sort of L = {1,2} & :: { \for, \ex } the quantifiers of L is one-to-one & rng the quantifiers of L misses rng the connectives of L & for q,x being object st q in the quant-sort of L & x in X holds (the quantifiers of L).(q,x) is_of_type <*the formula-sort of L*>, the formula-sort of L; end; definition let n be Nat; let X be set; let L be AlgLangSignature over X; attr L is n AL-correct means :: AOFA_L00:def 6 the program-sort of L <> the formula-sort of L & len the connectives of L >= n+8 & ((the connectives of L).(n+6) is_of_type <*the program-sort of L,the formula-sort of L*>, the formula-sort of L & ... & (the connectives of L).(n+8) is_of_type <*the program-sort of L,the formula-sort of L*>, the formula-sort of L); end; registration let n; cluster n PC-correct -> non void for PCLangSignature; end; definition let X,Y be set such that Y c= X; func incl(Y,X) -> Function of Y,X equals :: AOFA_L00:def 7 id Y; end; registration let n be non empty natural number; let X be set; cluster non void non empty n PC-correct QC-correct for QCLangSignature over X; end; registration let n be non empty natural number; cluster non void non empty n PC-correct for PCLangSignature; end; registration let X be set; cluster non void non empty for strict AlgLangSignature over X; end; registration cluster ordinal -> non pair for set; end; theorem :: AOFA_L00:10 for a being ordinal number for n1,n2 being natural number st n1 <> n2 holds a+^n1 <> a+^n2; registration let R be non empty Relation; cluster -> pair for Element of R; end; theorem :: AOFA_L00:11 for n being non empty natural number for X being non empty set for J being Signature ex S being strict non void non empty AlgLangSignature over X st S is n PC-correct QC-correct n AL-correct J-extension & (for i st i = 0 or ... or i = 8 holds (the connectives of S).(n+i) = (sup the carrier' of J)+^i) & (for x being Element of X holds (the quantifiers of S).(1,x) = [the carrier' of J,1,x] & (the quantifiers of S).(2,x) = [the carrier' of J,2,x]) & the formula-sort of S = sup the carrier of J & the program-sort of S = (sup the carrier of J)+^1 & the carrier of S = (the carrier of J) \/ {the formula-sort of S, the program-sort of S} & for w being Ordinal st w = sup the carrier' of J holds the carrier' of S = (the carrier' of J) \/ {w+^0,w+^1,w+^2,w+^3,w+^4,w+^5,w+^6,w+^7,w+^8}\/ [:{the carrier' of J},{1,2},X:]; registration let n be non empty natural number; let X be non empty set; let J be Signature; cluster J-extension n PC-correct QC-correct n AL-correct for non void non empty strict AlgLangSignature over X; end; registration let X be non empty set; let n be non empty natural number; cluster n PC-correct QC-correct n AL-correct for non void non empty strict AlgLangSignature over X; end; begin :: Language definition let J be non empty non void Signature; let T be MSAlgebra over J; mode VariableSet of T -> set means :: AOFA_L00:def 8 ex G being GeneratorSet of T st it = Union G; end; definition let J be non empty non void Signature; let T be MSAlgebra over J; let X be GeneratorSet of T; redefine func Union X -> VariableSet of T; end; theorem :: AOFA_L00:12 for J being non empty non void Signature for T being MSAlgebra over J for X being VariableSet of T holds X c= Union the Sorts of T; definition let S be non empty non void Signature; let X be ManySortedSet of the carrier of S; let T be VarMSAlgebra over S; attr T is X-vf-yielding means :: AOFA_L00:def 9 the free-vars of T is ManySortedMSSet of the Sorts of T, X; end; definition let J be non empty set; let Q be ManySortedSet of J; let Y be set; let f be Function of [:Union Q, Y:], Union Q; attr f is sort-preserving means :: AOFA_L00:def 10 for j being Element of J holds f.:[:Q.j, Y:] c= Q.j; end; registration let J be non empty set; let Q be ManySortedSet of J; let Y be set; cluster sort-preserving for Function of [:Union Q, Y:], Union Q; end; definition let J be non empty non void Signature; let X be ManySortedSet of the carrier of J; struct (MSAlgebra over J) SubstMSAlgebra over J,X (# Sorts -> (ManySortedSet of the carrier of J), Charact -> (ManySortedFunction of (the Sorts)# * the Arity of J, the Sorts * the ResultSort of J), subst-op -> sort-preserving Function of [:Union the Sorts, Union [|X, the Sorts|]:], Union the Sorts #); end; theorem :: AOFA_L00:13 for I being set for X being ManySortedSet of I for S being ManySortedSubset of X for x holds S.x is Subset of X.x; definition let J be non empty non void Signature; let X be non empty-yielding ManySortedSet of the carrier of J; let Q be SubstMSAlgebra over J,X such that X is ManySortedSubset of the Sorts of Q; let x be Element of Union X; func @(x,Q) -> Element of Union the Sorts of Q equals :: AOFA_L00:def 11 x; end; definition let J be non empty non void Signature; let X be non empty-yielding ManySortedSet of the carrier of J; let Q be SubstMSAlgebra over J,X such that X is ManySortedSubset of the Sorts of Q; let j be SortSymbol of J such that (the Sorts of Q).j <> {}; let A be Element of Q,j; let x be Element of Union X; let y be Element of Union X; given a being SortSymbol of J such that x in X.a & y in X.a; func A/(x,y) -> Element of Q,j equals :: AOFA_L00:def 12 (the subst-op of Q).[A,[x,y]]; end; definition let J be non empty non void Signature; let X be non empty-yielding ManySortedSet of the carrier of J; let Q be SubstMSAlgebra over J,X; let j be SortSymbol of J; let A be Element of Q,j such that (the Sorts of Q).j <> {}; let x be Element of Union X; let t be Element of Union the Sorts of Q; given a be SortSymbol of J such that x in X.a & t in (the Sorts of Q).a; func A/(x,t) -> Element of Q,j equals :: AOFA_L00:def 13 (the subst-op of Q).[A,[x,t]]; end; registration let J be non empty non void ManySortedSign; let X be ManySortedSet of the carrier of J; cluster non-empty for SubstMSAlgebra over J,X; end; definition let J be non empty non void Signature; let X be non empty-yielding ManySortedSet of the carrier of J; let Q be non-empty SubstMSAlgebra over J,X; let o be OperSymbol of J; let p be Element of Args(o,Q); let x be Element of Union X; let y be Element of Union the Sorts of Q; func p/(x,y) -> Element of Args(o,Q) means :: AOFA_L00:def 14 for i being Nat st i in dom the_arity_of o ex j being SortSymbol of J st j = (the_arity_of o).i & ex A being Element of Q,j st A = p.i & it.i = A/(x,y); end; definition let I be non empty set; let X be non-empty ManySortedSet of I; let S be non-empty ManySortedSubset of X; let x be Element of I; let z be Element of S.x; func @z -> Element of X.x equals :: AOFA_L00:def 15 z; end; definition let J be non empty non void Signature; let X be non empty-yielding ManySortedSet of the carrier of J; let Q be non-empty SubstMSAlgebra over J,X; attr Q is subst-correct means :: AOFA_L00:def 16 for x being Element of Union X for a being SortSymbol of J st x in X.a holds (for j being SortSymbol of J for A being Element of Q,j holds A/(x,x) = A) & for y being Element of Union the Sorts of Q st y in (the Sorts of Q).a for o being OperSymbol of J for p being Element of Args(o,Q) for A being Element of Q, the_result_sort_of o st A = Den(o,Q).p holds not (ex S being QCLangSignature over Union X st J = S & ex z being (Element of Union X), q being Element of {1,2} st o = (the quantifiers of S).(q,z)) implies A/(x,y) = Den(o,Q).(p/(x,y)); attr Q is subst-correct2 means :: AOFA_L00:def 17 for j being SortSymbol of J for q being Element of Q,j, t being Element of Q,j for x being Element of Union X st t = x in X.j holds t/(x,q) = q; end; theorem :: AOFA_L00:14 for J being non empty non void Signature for X being non empty-yielding ManySortedSet of the carrier of J for Q being SubstMSAlgebra over J,X st X is ManySortedSubset of the Sorts of Q for a being SortSymbol of J st (the Sorts of Q).a <> {} for A being Element of Q,a for x,y being Element of Union X for t being Element of Union the Sorts of Q st y = t for j being SortSymbol of J st x in X.j & y in X.j holds A/(x,y) = A/(x,t); registration let J be non void Signature; cluster J-extension -> non void non empty for Signature; end; registration let J be Signature; cluster J-extension for non empty non void Signature; let X be non empty set; cluster J-extension for non empty non void QCLangSignature over X; let n be non empty natural number; cluster J-extension for non empty non void n PC-correct QC-correct QCLangSignature over X; end; definition let J be Signature; let X be non empty set; let n be non empty Nat; let S be J-extension n PC-correct feasible AlgLangSignature over X; attr S is essential means :: AOFA_L00:def 18 (the connectives of S).:(n+9 \ n) misses the carrier' of J & rng the quantifiers of S misses the carrier' of J & {the formula-sort of S, the program-sort of S} misses the carrier of J; end; registration let n be non empty natural number; let X be non empty set; let J be Signature; cluster essential for J-extension n PC-correct QC-correct n AL-correct non void non empty strict AlgLangSignature over X; end; registration let J be non empty Signature; let S be J-extension non empty Signature; let X be non empty-yielding ManySortedSet of the carrier of J; cluster X-tolerating for non empty-yielding ManySortedSet of the carrier of S; end; definition let J be non empty Signature; let S be non empty Signature; let T be MSAlgebra over J; let Q be MSAlgebra over S; attr Q is T-extension means :: AOFA_L00:def 19 Q|J = the MSAlgebra of T; end; theorem :: AOFA_L00:15 for J being non empty non void Signature for S being J-extension Signature for T being MSAlgebra over J for Q1,Q2 being MSAlgebra over S st the MSAlgebra of Q1 = the MSAlgebra of Q2 holds Q1 is T-extension implies Q2 is T-extension; theorem :: AOFA_L00:16 for J being non empty non void Signature for S being J-extension Signature for T being MSAlgebra over J for Q being MSAlgebra over S st Q is T-extension for x st x in the carrier of J holds (the Sorts of T).x = (the Sorts of Q).x; theorem :: AOFA_L00:17 for J being non empty non void Signature for S being J-extension Signature for T being MSAlgebra over J for I being set st I c= (the carrier of S)\the carrier of J for X being ManySortedSet of I ex Q being MSAlgebra over S st Q is T-extension & (the Sorts of Q)|I = X; theorem :: AOFA_L00:18 for J being non empty non void Signature for S being J-extension Signature for T being non-empty MSAlgebra over J for I being set st I c= (the carrier of S)\the carrier of J for X being non-empty ManySortedSet of I ex Q being non-empty MSAlgebra over S st Q is T-extension & (the Sorts of Q)|I = X; registration let J be non empty non void Signature; let S be J-extension Signature; let T be MSAlgebra over J; cluster T-extension for MSAlgebra over S; end; registration let J be non empty non void Signature; let S be J-extension Signature; let T be non-empty MSAlgebra over J; cluster T-extension for non-empty MSAlgebra over S; end; theorem :: AOFA_L00:19 for I being set, a being object holds pr1(I,{a}) is one-to-one; theorem :: AOFA_L00:20 for S1,S2,E1,E2 being Signature st the ManySortedSign of S1 = the ManySortedSign of S2 & the ManySortedSign of E1 = the ManySortedSign of E2 & E1 is Extension of S1 holds E2 is Extension of S2; registration let I be set; let a be object; cluster pr1(I,{a}) -> one-to-one; end; definition let a,b,c be non empty set; let g be Function of a,b; let f be Function of b,c; redefine func f*g -> Function of a,c; end; theorem :: AOFA_L00:21 for f being one-to-one Function st X misses Y holds f.:X misses f.:Y; theorem :: AOFA_L00:22 for n being non empty natural number, X being set for J being non empty Signature ex Q being non empty non void n PC-correct QC-correct QCLangSignature over X st the carrier of Q misses the carrier of J & the carrier' of Q misses the carrier' of J; registration let J be non empty Signature; cluster J-extension for non empty non void Signature; let X be set; cluster J-extension for non empty non void QCLangSignature over X; let n be non empty natural number; cluster J-extension for non empty non void n PC-correct QC-correct QCLangSignature over X; end; definition let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non empty non void QCLangSignature over Union X; let Y be X-tolerating ManySortedSet of the carrier of S; struct (VarMSAlgebra over S,SubstMSAlgebra over S,Y) LanguageStr over T,Y,S (# Sorts -> ManySortedSet of the carrier of S, Charact -> (ManySortedFunction of (the Sorts)# * the Arity of S, the Sorts * the ResultSort of S), free-vars -> ManySortedMSSet of the Sorts, the Sorts, :: Function of (the Sorts).the formula-sort of S, Bool X, subst-op -> sort-preserving Function of [:Union the Sorts, Union [|Y, the Sorts|]:], Union the Sorts, equality -> Function of Union [|the Sorts of T, the Sorts of T|], (the Sorts).the formula-sort of S #); end; definition let S be non empty PCLangSignature; let L be MSAlgebra over S; attr L is language means :: AOFA_L00:def 20 (the Sorts of L).the formula-sort of S is not empty; end; registration let S be non empty PCLangSignature; cluster non-empty -> language for MSAlgebra over S; cluster language for MSAlgebra over S; end; theorem :: AOFA_L00:23 for J being non void Signature for S being J-extension non void Signature for A1,A2 being MSAlgebra over S st the MSAlgebra of A1 = the MSAlgebra of A2 holds A1|J = A2|J; registration let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non empty non void QCLangSignature over Union X; cluster X-tolerating for non empty-yielding ManySortedSet of the carrier of S; end; registration let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non empty non void QCLangSignature over Union X; let Y be X-tolerating non empty-yielding ManySortedSet of the carrier of S; cluster non-empty language T-extension for LanguageStr over T,Y,S; end; definition let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non empty non void QCLangSignature over Union X; let Y be X-tolerating non empty-yielding ManySortedSet of the carrier of S; let L be non-empty LanguageStr over T,Y,S; attr L is subst-correct3 means :: AOFA_L00:def 21 for s,s1 being SortSymbol of S for t being Element of L,s for t1 being Element of L,s1 for y being Element of Union Y st y in Y.s holds y nin (vf t1).s & (y nin (vf t1).s implies t1/(y,t) = t1) & (t1 = y in Y.s1 implies t1/(y,t) = t) & for x being Element of Union Y st x in Y.s holds t1/(x,y)/(y,x) = t1; end; registration let J be non empty Signature; let S be J-extension non empty Signature; let X be non empty-yielding ManySortedSet of the carrier of J; let Y be set; cluster X extended_by(Y,the carrier of S) -> non empty-yielding; end; registration let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non empty non void QCLangSignature over Union X; cluster X extended_by({},the carrier of S)-vf-yielding non-empty language T-extension for LanguageStr over T,X extended_by({},the carrier of S),S; end; registration let X be set; let S be non empty QCLangSignature over X; let L be language MSAlgebra over S; cluster (the Sorts of L).the formula-sort of S -> non empty; end; definition let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non empty non void QCLangSignature over Union X; let Y be X-tolerating non empty-yielding ManySortedSet of the carrier of S; mode Language of Y,S is language T-extension LanguageStr over T,Y,S; end; definition let S be non empty PCLangSignature; let L be language MSAlgebra over S; mode Formula of L is Element of (the Sorts of L).the formula-sort of S; end; definition let n be non empty natural number; let S be non void non empty n PC-correct PCLangSignature; let L be language MSAlgebra over S; func \true_L -> Formula of L equals :: AOFA_L00:def 22 Den(In((the connectives of S).(n+5), the carrier' of S), L).{}; let A be Formula of L; func \notA -> Formula of L equals :: AOFA_L00:def 23 Den(In((the connectives of S).n, the carrier' of S), L).<*A*>; let B be Formula of L; func A\andB -> Formula of L equals :: AOFA_L00:def 24 Den(In((the connectives of S).(n+1), the carrier' of S), L).<*A,B*>; func A\orB -> Formula of L equals :: AOFA_L00:def 25 Den(In((the connectives of S).(n+2), the carrier' of S), L).<*A,B*>; func A\impB -> Formula of L equals :: AOFA_L00:def 26 Den(In((the connectives of S).(n+3), the carrier' of S), L).<*A,B*>; func A\iffB -> Formula of L equals :: AOFA_L00:def 27 Den(In((the connectives of S).(n+4), the carrier' of S), L).<*A,B*>; end; registration let J be non empty non void Signature; let T be non-empty MSAlgebra over J; cluster non empty for VariableSet of T; end; definition let n be non empty natural number; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non void non empty n PC-correct QC-correct QCLangSignature over Union X; let Y be X-tolerating non empty-yielding ManySortedSet of the carrier of S; let L be Language of Y,S; let A be Formula of L; let x be Element of Union X; func \for(x,A) -> Formula of L equals :: AOFA_L00:def 28 Den(In((the quantifiers of S).(1,x), the carrier' of S), L).<*A*>; func \ex(x,A) -> Formula of L equals :: AOFA_L00:def 29 Den(In((the quantifiers of S).(2,x), the carrier' of S), L).<*A*>; end; definition let n be non empty natural number; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non void non empty n PC-correct QC-correct QCLangSignature over Union X; let Y be X-tolerating non empty-yielding ManySortedSet of the carrier of S; let L be Language of Y,S; let A be Formula of L; let x,y be Element of Union X; func \for(x,y,A) -> Formula of L equals :: AOFA_L00:def 30 \for(x,\for(y,A)); func \ex(x,y,A) -> Formula of L equals :: AOFA_L00:def 31 \ex(x,\ex(y,A)); end; definition let n be non empty natural number; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non void non empty n PC-correct QC-correct QCLangSignature over Union X; let Y be X-tolerating non empty-yielding ManySortedSet of the carrier of S; let L be Language of Y,S; let A be Formula of L; let x,y,z be Element of Union X; func \for(x,y,z,A) -> Formula of L equals :: AOFA_L00:def 32 \for(x,y,\for(z,A)); func \ex(x,y,z,A) -> Formula of L equals :: AOFA_L00:def 33 \ex(x,y,\ex(z,A)); end; definition let n be non empty natural number; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non void non empty n PC-correct QC-correct QCLangSignature over Union X; let Y be X-tolerating non empty-yielding ManySortedSet of the carrier of S; let L be Language of Y,S; let t1,t2 be object; given a being SortSymbol of J such that t1 in (the Sorts of T).a & t2 in (the Sorts of T).a; func t1 '=' (t2,L) -> Formula of L equals :: AOFA_L00:def 34 (the equality of L).(t1,t2); end; definition let n be non empty natural number; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non void non empty n PC-correct QC-correct QCLangSignature over Union X; let Y be X-tolerating non empty-yielding ManySortedSet of the carrier of S; let L be non-empty Language of Y,S; attr L is vf-qc-correct means :: AOFA_L00:def 35 for A,B being Formula of L holds vf \notA = vf A & vf(A\andB) = (vf A) (\/) (vf B) & vf(A\orB) = (vf A) (\/) (vf B) & vf(A\impB) = (vf A) (\/) (vf B) & vf(A\iffB) = (vf A) (\/) (vf B) & vf \true_L = EmptyMS the carrier of S & for x being Element of Union X for a being SortSymbol of S st x in X.a holds vf \for(x,A) = (vf A) (\) a-singleton(x) & vf \ex(x,A) = (vf A) (\) a-singleton(x); end; definition let n be non empty natural number; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non void non empty n PC-correct QC-correct QCLangSignature over Union X; let Y be X-tolerating non empty-yielding ManySortedSet of the carrier of S; let L be non-empty T-extension Language of Y,S; attr L is vf-finite means :: AOFA_L00:def 36 for s being SortSymbol of S, t being Element of L,s holds vf t is finite-yielding; end; definition let n be non empty natural number; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non void non empty n PC-correct QC-correct QCLangSignature over Union X; let Y be X-tolerating non empty-yielding ManySortedSet of the carrier of S; let L be non-empty T-extension Language of Y,S; attr L is subst-forex means :: AOFA_L00:def 37 for A being Formula of L for x being Element of Union X for s,s1 being SortSymbol of S for t being Element of L,s st x in X.s1 for y being Element of Union Y st y in Y.s holds (x = y implies \for(x,A)/(y,t) = \for(x,A) & \ex(x,A)/(y,t) = \ex(x,A)) & (x <> y & x in (vf t).s1 implies ex z being (Element of Union X), x0,z0 being Element of Union Y st x = x0 & z0 = z = the Element of X.s1\(vf t).s1\(vf A).s1 & \for(x,A)/(y,t) = \for(z,A/(x0,z0)/(y,t)) & \ex(x,A)/(y,t) = \ex(z,A/(x0,z0)/(y,t))) & (x <> y & x nin (vf t).s implies \for(x,A)/(y,t) = \for(x,A/(y,t)) & \ex(x,A)/(y,t) = \ex(x,A/(y,t))); end; theorem :: AOFA_L00:24 for J being non void Signature for T being MSAlgebra over J for X being ManySortedSubset of the Sorts of T for S being J-extension non void Signature for Q being T-extension MSAlgebra over S holds X extended_by ({}, the carrier of S) is ManySortedSubset of the Sorts of Q; theorem :: AOFA_L00:25 for J being non void Signature for T being MSAlgebra over J for X being ManySortedSubset of the Sorts of T for S being J-extension non void Signature holds Union (X extended_by ({},the carrier of S)) = Union X; theorem :: AOFA_L00:26 for n being non empty natural number for X being non empty set for S being non empty non void n PC-correct QC-correct QCLangSignature over X for Q being language MSAlgebra over S holds {} in Args(In((the connectives of S).(n+5), the carrier' of S),Q) & for A being Formula of Q holds <*A*> in Args(In((the connectives of S).n, the carrier' of S),Q) & for B being Formula of Q holds (<*A,B*> in Args(In((the connectives of S).(n+1), the carrier' of S),Q) & ... & <*A,B*> in Args(In((the connectives of S).(n+4), the carrier' of S),Q)) & for x being Element of X holds <*A*> in Args(In((the quantifiers of S).(1,x), the carrier' of S),Q) & <*A*> in Args(In((the quantifiers of S).(2,x), the carrier' of S),Q); theorem :: AOFA_L00:27 for n being non empty natural number for J being non empty non void Signature for T being non-empty MSAlgebra over J for X being non empty-yielding GeneratorSet of T for S being J-extension non void non empty n PC-correct QC-correct QCLangSignature over Union X for Y being X-tolerating non empty-yielding ManySortedSet of the carrier of S for L being non-empty Language of Y,S for x being Element of Union Y for t being Element of Union the Sorts of L for s being SortSymbol of S st x in Y.s & t in (the Sorts of L).s holds (for a being Element of Args(In((the connectives of S).(n+5), the carrier' of S),L) st a = {} holds a/(x,t) = {}) & for A being Formula of L holds (for a being Element of Args(In((the connectives of S).n, the carrier' of S),L) st <*A*> = a holds a/(x,t) = <*A/(x,t)*>) & for B being Formula of L holds ((for a being Element of Args(In((the connectives of S).(n+1), the carrier' of S),L) st <*A,B*> = a holds a/(x,t) = <*A/(x,t),B/(x,t)*>) & ... & (for a being Element of Args(In((the connectives of S).(n+4), the carrier' of S),L) st <*A,B*> = a holds a/(x,t) = <*A/(x,t),B/(x,t)*>)) & for z being Element of Union X holds (for a being Element of Args(In((the quantifiers of S).(1,z), the carrier' of S),L) st <*A*> = a holds a/(x,t) = <*A/(x,t)*>) & (for a being Element of Args(In((the quantifiers of S).(2,z), the carrier' of S),L) st <*A*> = a holds a/(x,t) = <*A/(x,t)*>); theorem :: AOFA_L00:28 for n being non empty natural number for J being non empty non void Signature for T being non-empty MSAlgebra over J for X being non empty-yielding GeneratorSet of T for S being J-extension non empty non void n PC-correct QC-correct QCLangSignature over Union X for Y being X-tolerating non empty-yielding ManySortedSet of the carrier of S for L being non-empty Language of Y,S st L is subst-correct & Y is ManySortedSubset of the Sorts of L for x,y being Element of Union Y for a being SortSymbol of S st x in Y.a & y in Y.a for A being Formula of L holds (\notA)/(x,y) = \not(A/(x,y)) & for B being Formula of L holds (A\andB)/(x,y) = (A/(x,y))\and(B/(x,y)) & (A\orB)/(x,y) = (A/(x,y))\or(B/(x,y)) & (A\impB)/(x,y) = (A/(x,y))\imp(B/(x,y)) & (A\iffB)/(x,y) = (A/(x,y))\iff(B/(x,y)) & \true_L/(x,y) = \true_L; begin :: Algorithmic Theory definition let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non void non empty QCLangSignature over Union X; let Y be X-tolerating ManySortedSet of the carrier of S; struct (LanguageStr over T,Y,S,ProgramAlgStr over J,T,X) BialgebraStr over S,Y (# Sorts -> ManySortedSet of the carrier of S, Charact -> (ManySortedFunction of (the Sorts)# * the Arity of S, the Sorts * the ResultSort of S), free-vars -> ManySortedMSSet of the Sorts, the Sorts, subst-op -> sort-preserving Function of [:Union the Sorts, Union [|Y, the Sorts|]:], Union the Sorts, equality -> Function of Union [|the Sorts of T, the Sorts of T|], (the Sorts).the formula-sort of S, carrier -> set, charact -> PFuncFinSequence of the carrier, assignments -> (Function of Union [|X, the Sorts of T|], the carrier) #); end; registration let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; cluster J-extension for non void non empty AlgLangSignature over Union X; end; definition let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non void non empty AlgLangSignature over Union X; let Y be X-tolerating ManySortedSet of the carrier of S; let L be BialgebraStr over S,Y; attr L is AL-correct means :: AOFA_L00:def 38 the carrier of L = (the Sorts of L).the program-sort of S; end; notation let S be 1-sorted; synonym S is 1s-empty for S is empty; end; notation let S be UAStr; synonym S is ua-non-empty for S is non-empty; end; registration let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non void non empty AlgLangSignature over Union X; let Y be X-tolerating ManySortedSet of the carrier of S; cluster non 1s-empty for strict BialgebraStr over S,Y; end; registration let n be non empty Nat; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be essential J-extension n PC-correct non void non empty feasible AlgLangSignature over Union X; let Y be X-tolerating ManySortedSet of the carrier of S; cluster non-empty language AL-correct quasi_total partial ua-non-empty with_empty-instruction with_catenation with_if-instruction with_while-instruction T-extension for non 1s-empty strict BialgebraStr over S,Y; end; theorem :: AOFA_L00:29 for U1,U2 be preIfWhileAlgebra st the UAStr of U1 = the UAStr of U2 holds EmptyIns U1 = EmptyIns U2 & for I1,J1 being Element of U1 for I2,J2 being Element of U2 st I1 = I2 & J1 = J2 holds I1\;J1 = I2\;J2 & while(I1,J1) = while(I2,J2) & for C1 being Element of U1 for C2 being Element of U2 st C1 = C2 holds if-then-else(C1,I1,J1) = if-then-else(C2,I2,J2); theorem :: AOFA_L00:30 for U1,U2 be preIfWhileAlgebra st the UAStr of U1 = the UAStr of U2 holds ElementaryInstructions U1 = ElementaryInstructions U2; theorem :: AOFA_L00:31 for U1,U2 being Universal_Algebra st the UAStr of U1 = the UAStr of U2 for S1 being Subset of U1, S2 being Subset of U2 st S1 = S2 for o1 being operation of U1, o2 being operation of U2 st o1 = o2 holds S1 is_closed_on o1 implies S2 is_closed_on o2; theorem :: AOFA_L00:32 for U1,U2 being Universal_Algebra st the UAStr of U1 = the UAStr of U2 for S1 being Subset of U1, S2 being Subset of U2 st S1 = S2 holds S1 is opers_closed implies S2 is opers_closed; theorem :: AOFA_L00:33 for U1,U2 being Universal_Algebra st the UAStr of U1 = the UAStr of U2 for G being GeneratorSet of U1 holds G is GeneratorSet of U2; theorem :: AOFA_L00:34 for U1,U2 be Universal_Algebra st the UAStr of U1 = the UAStr of U2 holds signature U1 = signature U2; registration let n be non empty natural number; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be essential J-extension non void non empty n PC-correct QC-correct AlgLangSignature over Union X; cluster AL-correct vf-qc-correct vf-correct vf-finite subst-correct subst-forex non degenerated well_founded ECIW-strict for non-empty quasi_total partial ua-non-empty with_empty-instruction with_catenation with_if-instruction with_while-instruction language non 1s-empty T-extension BialgebraStr over S, X extended_by ({}, the carrier of S); end; definition let n be non empty natural number; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be essential J-extension non empty non void n PC-correct QC-correct n AL-correct AlgLangSignature over Union X; mode IfWhileAlgebra of X,S is AL-correct vf-qc-correct vf-correct subst-correct subst-forex non degenerated well_founded ECIW-strict non-empty quasi_total partial ua-non-empty with_empty-instruction with_catenation with_if-instruction with_while-instruction language non 1s-empty T-extension BialgebraStr over S, X extended_by ({}, the carrier of S); end; definition let n be non empty Nat; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be essential J-extension non empty non void n PC-correct QC-correct n AL-correct AlgLangSignature over Union X; let L be IfWhileAlgebra of X,S; let K be Formula of L; let P be Algorithm of L; func P*K -> Formula of L equals :: AOFA_L00:def 39 Den(In((the connectives of S).(n+6), the carrier' of S), L).<*P,K*>; func \Cup(P,K) -> Formula of L equals :: AOFA_L00:def 40 Den(In((the connectives of S).(n+7), the carrier' of S), L).<*P,K*>; func \Cap(P,K) -> Formula of L equals :: AOFA_L00:def 41 Den(In((the connectives of S).(n+8), the carrier' of S), L).<*P,K*>; end; definition let n be non empty Nat; let S be non empty non void n PC-correct PCLangSignature; let L be language MSAlgebra over S; let F be Subset of (the Sorts of L).the formula-sort of S; attr F is PC-closed means :: AOFA_L00:def 42 for A,B,C being Formula of L holds A\imp(B\impA) in F & (A\imp(B\impC))\imp((A\impB)\imp(A\impC)) in F & (\notA\imp\notB)\imp(B\impA) in F & A\imp(A\orB) in F & A\imp(B\orA) in F & (A\impC)\imp((B\impC)\imp((A\orB)\impC)) in F & A\andB\impA in F & A\andB\impB in F & A\imp(B\impA\andB) in F & A\and\notA\impB in F & (A\impB)\imp((A\imp\notB)\imp\notA) in F & A\or\notA in F & (A\iffB)\imp(A\impB) in F & (A\iffB)\imp(B\impA) in F & (A\impB)\and(B\impA)\imp(A\iffB) in F & \true_L in F & (\true_L)\andA\iffA in F & (\true_L)\orA\iff\true_L in F & (A in F & A\impB in F implies B in F); end; definition let n be non empty Nat; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non empty non void n PC-correct QC-correct QCLangSignature over Union X; let L be non-empty Language of X extended_by ({},the carrier of S), S; let F be Subset of (the Sorts of L).the formula-sort of S; attr F is QC-closed means :: AOFA_L00:def 43 for A,B being Element of (the Sorts of L).the formula-sort of S for x being Element of Union X holds (for a being SortSymbol of J holds (for t being Element of Union the Sorts of L st x in (X extended_by ({}, the carrier of S)).a & t in (the Sorts of L).a holds for y being Element of Union (X extended_by ({}, the carrier of S)) st x = y holds \for(x,A)\imp(A/(y,t)) in F) & (x in X.a & x nin (vf A).a implies \for(x,A\impB)\imp(A\imp\for(x,B)) in F)) & \not\ex(x,A)\iff\for(x,\notA) in F & \ex(x,\notA)\iff\not\for(x,A) in F & (A in F implies \for(x,A) in F); end; definition let n be non empty Nat; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non empty non void n PC-correct QC-correct QCLangSignature over Union X; let L be non-empty T-extension Language of X extended_by ({},the carrier of S), S; attr L is subst-eq-correct means :: AOFA_L00:def 44 for x0 being Element of Union (X extended_by({},the carrier of S)) for s,s1 being SortSymbol of S st x0 in X.s for t being Element of L,s, t1,t2 being Element of L,s1 holds (t1 '=' (t2,L))/(x0,t) = (t1/(x0,t)) '=' (t2/(x0,t),L); attr L is vf-eq-correct means :: AOFA_L00:def 45 for s being SortSymbol of S holds (for t1,t2 being Element of L,s holds vf(t1 '=' (t2,L)) = (vf t1) (\/) (vf t2)) & for s being SortSymbol of S for t being Element of L,s st t in X.s holds vf t = s-singleton t; let F be Subset of (the Sorts of L).the formula-sort of S; attr F is with_equality means :: AOFA_L00:def 46 (for t being Element of T holds t '=' (t,L) in F) & for b being SortSymbol of S for t1,t2 being Element of L,b for x being Element of Union (X extended_by ({},the carrier of S)) st x in X.b holds (for c being SortSymbol of S st c in the carrier of J for t being Element of L,c holds (t1 '=' (t2,L))\imp(t/(x,t1) '=' (t/(x,t2),L)) in F) & for A being Formula of L holds (t1 '=' (t2,L))\imp(A/(x,t1)\imp(A/(x,t2))) in F; end; definition let n be non empty natural number; let J be non empty non void Signature; let T be non-empty VarMSAlgebra over J; let X be non-empty GeneratorSet of T; let S be essential J-extension non empty non void n PC-correct QC-correct n AL-correct AlgLangSignature over Union X; let L be non 1s-empty IfWhileAlgebra of X,S; let V be Formula of L; :: true state test let F be Subset of (the Sorts of L).the formula-sort of S; attr F is V AL-closed means :: AOFA_L00:def 47 for A,B being Formula of L holds (for M being Algorithm of L holds (M*(A\andB)) \iff (M*A)\and(M*B) in F & (M*(A\orB)) \iff (M*A)\or(M*B) in F & \Cup(M,A) \iff A\or\Cup(M, M*A) in F & \Cap(M,A) \iff A\and\Cap(M, M*A) in F & (A\impB in F implies \Cup(M,A)\imp\Cup(M,B) in F & \Cap(M,A)\imp\Cap(M,B) in F)) & (for a being SortSymbol of J for x being Element of X.a for x0 being Element of Union (X extended_by ({},the carrier of S)) st x = x0 holds for t being Element of (the Sorts of T).a for t1 being Element of Union the Sorts of L st t1 = t holds ((x:=(t,L))*A) \iff (A/(x0,t1)) in F & (for y being Element of X.a st y nin (vf t).a holds for y0 being Element of Union (X extended_by ({},the carrier of S)) st y = y0 holds ((x:=(t,L))*\ex(x,A)) \iff \ex(y, (x:=(t,L))*((y:=(@x,L))*(A/(x0,y0)))) in F) & ((x:=(t,L))*A) \imp \ex(x,A) in F) & for M,M1,M2 being Algorithm of L holds ((M\;M1)*A) \iff (M*(M1*A)) in F & (if-then-else(M,M1,M2)*A) \iff ((M*V)\and(M*(M1*A)))\or((M*\notV)\and(M*(M2*A))) in F & (while(M,M1)*A) \iff ((M*\notV)\andA)\or((M*V)\and(M*(M1*(while(M,M1)*A)))) in F; end; registration let n be non empty Nat; let S be non empty non void n PC-correct PCLangSignature; let L be language MSAlgebra over S; cluster [#]((the Sorts of L).the formula-sort of S) -> PC-closed; cluster PC-closed -> non empty for Subset of (the Sorts of L).the formula-sort of S; cluster PC-closed for Subset of (the Sorts of L).the formula-sort of S; end; registration let n be non empty Nat; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non empty non void n PC-correct QC-correct QCLangSignature over Union X; let L be non-empty Language of X extended_by ({}, the carrier of S),S; cluster [#]((the Sorts of L).the formula-sort of S) -> QC-closed; cluster QC-closed PC-closed for Subset of (the Sorts of L).the formula-sort of S; end; registration let n be non empty Nat; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S be J-extension non empty non void n PC-correct QC-correct QCLangSignature over Union X; let L be non-empty T-extension Language of X extended_by ({}, the carrier of S),S; cluster [#]((the Sorts of L).the formula-sort of S) -> with_equality; cluster QC-closed PC-closed with_equality for Subset of (the Sorts of L).the formula-sort of S; end; definition let n be non empty Nat; let S being non empty non void n PC-correct PCLangSignature; let L be language MSAlgebra over S; mode PC-theory of L is PC-closed Subset of (the Sorts of L).the formula-sort of S; end; definition let n be non empty Nat; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S being J-extension non empty non void n PC-correct QC-correct QCLangSignature over Union X; let L be non-empty Language of X extended_by ({}, the carrier of S), S; mode QC-theory of L is QC-closed PC-closed Subset of (the Sorts of L).the formula-sort of S; end; definition let n be non empty Nat; let J be non empty non void Signature; let T be non-empty MSAlgebra over J; let X be non empty-yielding GeneratorSet of T; let S being J-extension non empty non void n PC-correct QC-correct QCLangSignature over Union X; let L be non-empty T-extension Language of X extended_by ({}, the carrier of S), S; mode QC-theory_with_equality of L is QC-closed PC-closed with_equality Subset of (the Sorts of L).the formula-sort of S; end; registration let n be non empty natural number; let J be non empty non void Signature; let T be non-empty VarMSAlgebra over J; let X be non-empty GeneratorSet of T; let S be essential J-extension non empty non void n PC-correct QC-correct n AL-correct AlgLangSignature over Union X; let L be non 1s-empty IfWhileAlgebra of X,S; let V be Formula of L; cluster V AL-closed for PC-closed QC-closed with_equality Subset of (the Sorts of L).the formula-sort of S; end; definition let n be non empty natural number; let J be non empty non void Signature; let T be non-empty VarMSAlgebra over J; let X be non-empty GeneratorSet of T; let S be essential J-extension non empty non void n PC-correct QC-correct n AL-correct AlgLangSignature over Union X; let L be non empty IfWhileAlgebra of X,S; let V be Formula of L; mode AL-theory of V,L is PC-closed QC-closed with_equality V AL-closed Subset of (the Sorts of L).the formula-sort of S; end; begin :: Propositional Calculus reserve n for non empty Nat, S for non empty non void n PC-correct PCLangSignature, L for language MSAlgebra over S, F for PC-theory of L, A,B,C,D for Formula of L; theorem :: AOFA_L00:35 A\impA in F; theorem :: AOFA_L00:36 A\andB in F iff A in F & B in F; theorem :: AOFA_L00:37 A\orB\impB\orA in F; theorem :: AOFA_L00:38 (B\impC)\imp((A\impB)\imp(A\impC)) in F; theorem :: AOFA_L00:39 A\imp(B\impC) in F implies B\imp(A\impC) in F; theorem :: AOFA_L00:40 :: Hypothetical syllogism (A\impB)\imp((B\impC)\imp(A\impC)) in F; theorem :: AOFA_L00:41 A\imp(B\imp(A\impB)) in F; theorem :: AOFA_L00:42 :: Contraposition (A\imp(B\impC))\imp(B\imp(A\impC)) in F; theorem :: AOFA_L00:43 :: Modus ponendo ponens B\imp((B\impA)\impA) in F; theorem :: AOFA_L00:44 A\iffB in F iff A\impB in F & B\impA in F; theorem :: AOFA_L00:45 B in F implies A\impB in F; theorem :: AOFA_L00:46 A\impB in F & B\impC in F implies A\impC in F; theorem :: AOFA_L00:47 C\imp(B\impA) in F & B in F implies C\impA in F; theorem :: AOFA_L00:48 (( A\andB )\impC )\imp( A\imp( B\impC )) in F; theorem :: AOFA_L00:49 ( A\imp( B\impC ))\imp(( A\andB )\impC ) in F; theorem :: AOFA_L00:50 ( C\impA )\imp(( C\impB )\imp( C\imp( A\andB ))) in F; theorem :: AOFA_L00:51 A\andB\impB\andA in F; theorem :: AOFA_L00:52 (A\iffB)\imp(B\iffA) in F; theorem :: AOFA_L00:53 A\orA\impA in F; theorem :: AOFA_L00:54 A\impA\andA in F; theorem :: AOFA_L00:55 A\impB in F & A\impC in F implies A\imp(B\andC) in F; theorem :: AOFA_L00:56 (A\andB)\or(A\andC) \imp A\and(B\orC) in F; theorem :: AOFA_L00:57 A\or(B\andC) \imp (A\orB)\and(A\orC) in F; theorem :: AOFA_L00:58 A\imp(\notA\impB) in F; theorem :: AOFA_L00:59 A\impB\imp(\notB\imp\notA) in F; theorem :: AOFA_L00:60 A\impB in F iff \notB\imp\notA in F; theorem :: AOFA_L00:61 A\impB in F & C\impD in F implies A\orC\impB\orD in F; theorem :: AOFA_L00:62 A\impB\imp(C\orA\impC\orB) in F; theorem :: AOFA_L00:63 A\impB in F & C\impD in F & \notB\or\notD in F implies \notA\or\notC in F; theorem :: AOFA_L00:64 A\orB\imp(\notA\impB) in F; theorem :: AOFA_L00:65 A\orB\imp(\notB\impA) in F; theorem :: AOFA_L00:66 A\imp\not\notA in F; theorem :: AOFA_L00:67 \not\notA\impA in F; theorem :: AOFA_L00:68 A\iff\not\notA in F; theorem :: AOFA_L00:69 A\imp\notB in F iff B\imp\notA in F; theorem :: AOFA_L00:70 \notA\impB in F iff \notB\impA in F; theorem :: AOFA_L00:71 A\imp(B\impC) in F & C\impD in F implies A\imp(B\impD) in F; theorem :: AOFA_L00:72 \not(A\andB)\imp\notA\or\notB in F; theorem :: AOFA_L00:73 \not(A\orB)\imp\notA\and\notB in F; theorem :: AOFA_L00:74 A\impB in F & C\impD in F implies A\andC\impB\andD in F; theorem :: AOFA_L00:75 \notA\or\notB\imp\not(A\andB) in F; theorem :: AOFA_L00:76 \notA\and\notB\imp\not(A\orB) in F; theorem :: AOFA_L00:77 A\or(B\orC)\imp(A\orB)\orC in F; theorem :: AOFA_L00:78 (A\orB)\orC\iffA\or(B\orC) in F; theorem :: AOFA_L00:79 A\and(B\andC)\imp(A\andB)\andC in F; theorem :: AOFA_L00:80 (A\andB)\andC\iffA\and(B\andC) in F; theorem :: AOFA_L00:81 C\or(A\impB)\imp(C\orA\impC\orB) in F; theorem :: AOFA_L00:82 (A\orB)\and(A\orC) \imp A\or(B\andC) in F; theorem :: AOFA_L00:83 A\and(B\orC) \imp (A\andB)\or(A\andC) in F; theorem :: AOFA_L00:84 A\impB\imp\notA\orB in F; theorem :: AOFA_L00:85 A\impB\imp\not(A\and\notB) in F; theorem :: AOFA_L00:86 B\or\notC\andC\impB in F; theorem :: AOFA_L00:87 B\orC\and\notC\impB in F; theorem :: AOFA_L00:88 A\iffB\impA\andB\or\notA\and\notB in F; theorem :: AOFA_L00:89 A\iffB\imp(A\or\notB)\and(\notA\orB) in F; theorem :: AOFA_L00:90 \not(A\and\notA) in F; theorem :: AOFA_L00:91 A\iffA in F; theorem :: AOFA_L00:92 A\iffB in F implies B\iffA in F; theorem :: AOFA_L00:93 A\iffB in F & B\iffC in F implies A\iffC in F; theorem :: AOFA_L00:94 A\iffB in F & B\impC in F implies A\impC in F; theorem :: AOFA_L00:95 A\impB in F & B\iffC in F implies A\impC in F; theorem :: AOFA_L00:96 A\iffB in F iff \notA\iff\notB in F; theorem :: AOFA_L00:97 A\iffB in F iff \not\notA\iffB in F; theorem :: AOFA_L00:98 A\imp(B\impC) in F & D\impB in F implies A\imp(D\impC) in F; theorem :: AOFA_L00:99 A\iffB\andC in F & C\iffD in F implies A\iffB\andD in F; theorem :: AOFA_L00:100 A\iffB\andC in F & B\iffD in F implies A\iffD\andC in F; theorem :: AOFA_L00:101 A\iffB\orC in F & C\iffD in F implies A\iffB\orD in F; theorem :: AOFA_L00:102 A\iffB\orC in F & B\iffD in F implies A\iffD\orC in F; theorem :: AOFA_L00:103 A\impB in F implies B\impC\imp(A\impC) in F; theorem :: AOFA_L00:104 A\impB in F implies C\impA\imp(C\impB) in F; theorem :: AOFA_L00:105 A\impB in F & C\impD in F implies B\impC\imp(A\impD) in F; begin :: Quantifier calculus reserve J for non empty non void Signature, T for non-empty MSAlgebra over J, X for non empty-yielding GeneratorSet of T, S1 for J-extension non empty non void n PC-correct QC-correct QCLangSignature over Union X, L for non-empty Language of X extended_by ({},the carrier of S1), S1, G for QC-theory of L, A,B,C,D for Formula of L; reserve x,y,z for Element of Union X; reserve x0,y0,z0 for Element of Union (X extended_by ({},the carrier of S1)); theorem :: AOFA_L00:106 L is subst-correct implies \for(x,A)\impA in G; theorem :: AOFA_L00:107 \ex(x,A)\iff\not\for(x,\notA) in G; theorem :: AOFA_L00:108 \for(x,A)\iff\not\ex(x,\notA) in G; theorem :: AOFA_L00:109 L is subst-correct implies \for(x,A\impB)\imp(\for(x,A)\impB) in G; theorem :: AOFA_L00:110 for a being SortSymbol of J st x in X.a & x nin (vf A).a & \for(x,A\impB) in G holds A\imp\for(x,B) in G; :: x nin (vf A).a implies \for(x,A\impB)\imp(A\imp\for(x,B)) in G by AX2; theorem :: AOFA_L00:111 L is subst-correct vf-qc-correct implies \for(x,A\impB)\imp(\for(x,A)\imp\for(x,B)) in G; theorem :: AOFA_L00:112 L is subst-correct implies for a being SortSymbol of J st x in X.a & y in X.a & x0 = x & y0 = y holds A/(x0,y0)\imp\ex(x,A) in G; theorem :: AOFA_L00:113 L is subst-correct vf-qc-correct implies \ex(x,y,A)\iff\not\for(x,y,\notA) in G; theorem :: AOFA_L00:114 L is subst-correct implies A\imp\ex(x,A) in G; theorem :: AOFA_L00:115 L is vf-qc-correct implies for a being SortSymbol of S1 st x in X.a holds x nin (vf \for(x,A)).a; theorem :: AOFA_L00:116 L is vf-qc-correct implies for a being SortSymbol of S1 st x in X.a holds x nin (vf \ex(x,A)).a; theorem :: AOFA_L00:117 L is subst-correct vf-qc-correct & A\impB in G implies (\for(x,A)\imp\for(x,B)) in G; theorem :: AOFA_L00:118 L is subst-correct vf-qc-correct implies \for(x,\notA\imp\notB)\imp(\for(x,B)\imp\for(x,A)) in G; theorem :: AOFA_L00:119 L is subst-correct vf-qc-correct implies \for(x,A\impB)\imp(\for(x,\notB)\imp\for(x,\notA)) in G; theorem :: AOFA_L00:120 L is subst-correct vf-qc-correct & A\iffB in G implies \for(x,A)\iff\for(x,B) in G; theorem :: AOFA_L00:121 \ex(x,\notA)\iff\not\for(x,A) in G; theorem :: AOFA_L00:122 L is subst-correct vf-qc-correct implies for a being SortSymbol of J st x in X.a & x nin (vf B).a holds \for(x,A\impB)\imp(\ex(x,A)\impB) in G; theorem :: AOFA_L00:123 L is subst-correct vf-qc-correct implies \for(x,A\impB)\imp(\ex(x,A)\imp\ex(x,B)) in G; theorem :: AOFA_L00:124 L is subst-correct vf-qc-correct implies \for(x,\notA)\iff\not\ex(x,A) in G; theorem :: AOFA_L00:125 L is subst-correct vf-qc-correct implies \for(x,y,A)\iff\not\ex(x,y,\notA) in G; theorem :: AOFA_L00:126 L is subst-correct vf-qc-correct implies \for(x,A)\iff\for(x,\not\notA) in G; theorem :: AOFA_L00:127 L is subst-correct vf-qc-correct implies \for(x,A\andB)\imp(\for(x,A)\and\for(x,B)) in G; theorem :: AOFA_L00:128 L is vf-qc-correct subst-correct implies (\for(x,A)\and\for(x,B))\imp\for(x,A\andB) in G; theorem :: AOFA_L00:129 L is subst-correct vf-qc-correct implies (\for(x,A)\or\for(x,B))\imp\for(x,A\orB) in G; theorem :: AOFA_L00:130 L is subst-correct vf-qc-correct & A\impB in G implies \ex(x,A)\imp\ex(x,B) in G; theorem :: AOFA_L00:131 L is subst-correct vf-qc-correct & A\iffB in G implies \ex(x,A)\iff\ex(x,B) in G; theorem :: AOFA_L00:132 L is subst-correct vf-qc-correct implies \ex(x,A)\iff\ex(x,\not\notA) in G; theorem :: AOFA_L00:133 L is subst-correct vf-qc-correct implies \ex(x,A)\or\ex(x,B)\iff\ex(x,A\orB) in G; theorem :: AOFA_L00:134 L is subst-correct implies for a being SortSymbol of J st x in X.a & x nin (vf A).a holds A\iff\for(x,A) in G; reserve a for SortSymbol of J; theorem :: AOFA_L00:135 L is subst-correct vf-qc-correct & x in X.a & x nin (vf A).a implies \for(x,A\orB)\imp(A\or\for(x,B)) in G; theorem :: AOFA_L00:136 L is subst-correct vf-qc-correct & x in X.a & x nin (vf A).a implies \ex(x,A\andB)\impA\and\ex(x,B) in G; theorem :: AOFA_L00:137 L is subst-correct vf-qc-correct & x in X.a & x nin (vf A).a implies \ex(x,A\andB)\iffA\and\ex(x,B) in G; theorem :: AOFA_L00:138 L is subst-correct vf-qc-correct & x in X.a & x nin (vf A).a implies \ex(x,A\impB)\imp(A\imp\ex(x,B)) in G; theorem :: AOFA_L00:139 L is vf-qc-correct implies \for(x,A)\imp\for(x,x,A) in G; theorem :: AOFA_L00:140 L is vf-qc-correct subst-correct implies \for(x,y,A)\imp\for(y,x,A) in G; theorem :: AOFA_L00:141 L is vf-qc-correct subst-correct implies \ex(x,y,A)\imp\ex(y,x,A) in G; theorem :: AOFA_L00:142 L is vf-qc-correct subst-correct implies \ex(x,\for(y,A))\imp\for(y,\ex(x,A)) in G; theorem :: AOFA_L00:143 L is subst-correct vf-qc-correct implies \for(x,A\andA)\iff\for(x,A) in G; theorem :: AOFA_L00:144 L is subst-correct vf-qc-correct implies \for(x,A\orA)\iff\for(x,A) in G; theorem :: AOFA_L00:145 L is subst-correct vf-qc-correct implies \ex(x,A\orA)\iff\ex(x,A) in G; reserve L for non-empty T-extension Language of X extended_by ({},the carrier of S1), S1, G1 for QC-theory_with_equality of L, A,B,C,D for Formula of L, s,s1 for SortSymbol of S1, t,t9 for Element of L,s, t1,t2,t3 for Element of L,s1; theorem :: AOFA_L00:146 L is subst-eq-correct & x0 in X.s & t1 '=' (t2,L) in G1 implies (t1/(x0,t) '=' (t2/(x0,t),L)) in G1; theorem :: AOFA_L00:147 L is subst-eq-correct vf-finite subst-correct2 subst-correct3 & s1 in the carrier of J & X.s1 is infinite implies t1 '=' (t2,L)\imp(t2 '=' (t1,L)) in G1; theorem :: AOFA_L00:148 L is subst-eq-correct vf-finite subst-correct2 subst-correct3 & s1 in the carrier of J & X.s1 is infinite implies t1 '=' (t2,L)\and(t2 '=' (t3,L))\imp(t1 '=' (t3,L)) in G1; theorem :: AOFA_L00:149 L is subst-correct3 vf-finite subst-correct2 subst-correct subst-eq-correct vf-qc-correct vf-eq-correct & x = x0 in X.s & y = y0 in X.s & x <> y nin (vf A).s & X.s is infinite implies \for(x,A\iff\ex(y, x '=' (y,L)\and(A/(x0,y0)))) in G1; theorem :: AOFA_L00:150 L is subst-correct3 vf-finite subst-correct2 subst-correct subst-eq-correct vf-qc-correct vf-eq-correct & x = x0 in X.s & y = y0 in X.s & x <> y nin (vf A).s & X.s is infinite implies \for(x,A\iff\for(y, x '=' (y,L)\imp(A/(x0,y0)))) in G1; theorem :: AOFA_L00:151 L is subst-correct subst-eq-correct subst-correct3 vf-eq-correct & x in X.s & y in X.s & x <> y implies \for(x,\ex(y,x '=' (y,L))) in G1; theorem :: AOFA_L00:152 L is subst-correct & x = x0 in X.s & y = y0 in X.s implies A\and (x '=' (y,L))\imp(A/(x0,y0)) in G1; theorem :: AOFA_L00:153 L is subst-correct & x = x0 in X.s & y = y0 in X.s implies A\and\not(A/(x0,y0))\imp\not(x '=' (y,L)) in G1; begin :: Algorithmic logic reserve n for non empty natural number, J for non empty non void Signature, T for non-empty VarMSAlgebra over J, X for non-empty GeneratorSet of T, S for essential J-extension non empty non void n PC-correct QC-correct n AL-correct AlgLangSignature over Union X, L for non empty IfWhileAlgebra of X,S, M,M1,M2 for Algorithm of L, A,B,C,V for Formula of L, H for AL-theory of V,L, a for SortSymbol of J, x,y for (Element of X.a), t for Element of T,a; theorem :: AOFA_L00:154 (M*(A\andB\andC))\iff(M*A)\and(M*B)\and(M*C) in H; theorem :: AOFA_L00:155 (M*(A\orB\orC))\iff(M*A)\or(M*B)\or(M*C) in H; theorem :: AOFA_L00:156 A\iffB in H implies \Cup(M,A)\iff\Cup(M,B) in H; theorem :: AOFA_L00:157 A\iffB in H implies \Cap(M,A)\iff\Cap(M,B) in H; theorem :: AOFA_L00:158 \Cup(M,A) \iff A\or(M*A)\or\Cup(M, (M\;M)*A) in H; theorem :: AOFA_L00:159 \Cap(M,A) \iff A\and(M*A)\and\Cap(M, (M\;M)*A) in H; theorem :: AOFA_L00:160 for x0,y0 being Element of Union (X extended_by ({},the carrier of S)) st x = x0 & y = y0 holds ((x:=(@y,L))*A) \iff (A/(x0,y0)) in H; theorem :: AOFA_L00:161 M*V in H & M*(M1*A) in H or M*\notV in H & M*(M2*A) in H implies if-then-else(M,M1,M2)*A in H; theorem :: AOFA_L00:162 M*\notV in H & A in H or M*V in H & M*(M1*(while(M,M1)*A)) in H implies while(M,M1)*A in H;