First-order equational logic consists of quantifier-free terms of ordinary first-order logic, with equality as the only predicate symbol. The model theory of this logic was developed into universal algebra by Birkhoff, Grätzer, and Cohn. It was later made into a branch of category theory by Lawvere ("algebraic theories").[1]
The terms of equational logic are built up from variables and constants using function symbols (or operations).
Syllogism
Here are the four inference rules of logic. denotes textual substitution of expression for variable in expression . Next, denotes equality, for and of the same type, while , or equivalence, is defined only for and of type boolean. For and of type boolean, and have the same meaning.
![{\textstyle P[x:=E]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39259cf5f0aa09389d66ca1fb1796820e753af2a)
| Substitution | If is a theorem, then so is . | |
|---|---|---|
| Leibniz | If is a theorem, then so is . | |
| Transitivity | If and are theorems, then so is . | |
| Equanimity | If and are theorems, then so is . |
![{\displaystyle \vdash P\qquad \rightarrow \qquad \vdash P[x:=E]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46de827bbda42d470325dac9da8b3abbf7c3d600)
![{\textstyle E[x:=P]=E[x:=Q]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/478f9de34f1265f7f0e982df59d4f147c23c6c1c)
![{\displaystyle \vdash P=Q\qquad \rightarrow \qquad \vdash E[x:=P]=E[x:=Q]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3ed8d176cd573c4efc119e916e5d0bd96262d18)
Proof
We explain how the four inference rules are used in proofs, using the proof of [clarify]. The logic symbols and indicate "true" and "false," respectively, and indicates "not." The theorem numbers refer to theorems of A Logical Approach to Discrete Math.[2]
First, lines – show a use of inference rule Leibniz:
is the conclusion of Leibniz, and its premise is given on line . In the same way, the equality on lines – are substantiated using Leibniz.
The "hint" on line is supposed to give a premise of Leibniz, showing what substitution of equals for equals is being used. This premise is theorem with the substitution , i.e.
![{\displaystyle (\lnot (p\equiv q)\equiv \lnot p\equiv q)[p:=q]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/976dcc76ffedb0362a9636f929beff0db3c6309a)
This shows how inference rule Substitution is used within hints.
From and , we conclude by inference rule Transitivity that . This shows how Transitivity is used.
Finally, note that line , , is a theorem, as indicated by the hint to its right. Hence, by inference rule Equanimity, we conclude that line is also a theorem. And is what we wanted to prove.[2]
See also
References
- ^ equational logic. (n.d.). The Free On-line Dictionary of Computing. Retrieved October 24, 2011, from Dictionary.com website: http://dictionary.reference.com/browse/equational+logic
- ^ a b c Gries, D. (2010). Introduction to equational logic . Retrieved from http://www.cs.cornell.edu/home/gries/Logic/Equational.html Archived 2019-09-23 at the Wayback Machine
You must be logged in to post a comment.