Definition:Tautology/Formal Semantics/Boolean Interpretations
< Definition:Tautology | Formal Semantics(Redirected from Definition:Propositional Tautology)
Jump to navigation
Jump to search
Definition
Let $\mathbf A$ be a WFF of propositional logic.
Then $\mathbf A$ is called a tautology (for boolean interpretations) if and only if:
- $\map v {\mathbf A} = \T$
for every boolean interpretation $v$ of $\mathbf A$.
That $\mathbf A$ is a tautology may be denoted as:
- $\models_{\mathrm {BI} } \mathbf A$
Also known as
A tautology in this context may also be described as valid (for boolean interpretations).
On $\mathsf{Pr} \infty \mathsf{fWiki}$, we have chosen to only use validity in the context of a single boolean interpretation.
Also denoted as
If only boolean interpretations are under discussion, $\models \mathbf A$ is also often encountered.
Examples
Excluded Middle
- $p \lor \lnot p$
is an example of a tautology.
Arbitrary Example $1$
The WFF of propositional logic:
- $\paren {\paren {\paren {\lnot p} \implies q} \implies \paren {\paren {\paren {\lnot p} \implies \paren {\lnot q} } \implies p} }$
is a tautology.
Arbitrary Example $2$
The WFF of propositional logic:
- $\paren {\paren {\lnot p} \implies \paren {q \lor r} } \iff \paren {\paren {\lnot q} \implies \paren {\paren {\lnot r} \implies p} }$
is a tautology.
Also see
- Definition:Contradiction (Boolean Interpretations)
- Definition:Valid (Boolean Interpretation)
- Definition:Satisfiable (Boolean Interpretations)
- Results about tautology can be found here.
Sources
- 1959: A.H. Basson and D.J. O'Connor: Introduction to Symbolic Logic (3rd ed.) ... (previous) ... (next): $\S 3.5$: The Classification of Propositions
- 1964: Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning ... (previous) ... (next): $\text{II}$: 'AND', 'OR', 'IF AND ONLY IF': $\S 6$
- 1965: E.J. Lemmon: Beginning Logic ... (previous) ... (next): Chapter $2$: The Propositional Calculus $2$: $3$ Truth-Tables
- 1971: Robert H. Kasriel: Undergraduate Topology ... (previous) ... (next): $\S1.2$: Some Remarks on the Use of the Connectives and, or, implies
- 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic
- 1988: Alan G. Hamilton: Logic for Mathematicians (2nd ed.) ... (previous) ... (next): $\S 1$: Informal statement calculus: $\S 1.2$: Truth functions and truth tables: Definition $1.5 \ \text{(a)}$
- 2000: Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems ... (previous) ... (next): $\S 1.4.1$: The meaning of logical connectives: Exercise $1.8: \ 5$
- 2009: Kenneth Kunen: The Foundations of Mathematics ... (previous) ... (next): $\text{II}.9$ Tautologies (informal definition)
- 2009: Kenneth Kunen: The Foundations of Mathematics ... (previous) ... (next): $\text{II}.9$ Tautologies: Definition $\text{II}.9.2$ (formal definition)
- 2012: M. Ben-Ari: Mathematical Logic for Computer Science (3rd ed.) ... (previous) ... (next): $\S 2.5$: Definition $2.38$