Tautology (logic)
From The Art and Popular Culture Encyclopedia
Revision as of 22:47, 15 August 2008 Jahsonic (Talk | contribs) ← Previous diff |
Current revision Jahsonic (Talk | contribs) |
||
Line 6: | Line 6: | ||
A key property of tautologies is that an [[effective method]] exists for testing whether a given formula is always satisfied (or, equivalently, whether its complement is unsatisfiable). One such method uses [[truth table]]s. The [[decision problem]] of determining whether a formula is satisfiable is the [[Boolean satisfiability problem]], an important example of an [[NP-complete]] problem in [[computational complexity theory]]. | A key property of tautologies is that an [[effective method]] exists for testing whether a given formula is always satisfied (or, equivalently, whether its complement is unsatisfiable). One such method uses [[truth table]]s. The [[decision problem]] of determining whether a formula is satisfiable is the [[Boolean satisfiability problem]], an important example of an [[NP-complete]] problem in [[computational complexity theory]]. | ||
+ | ==See also== | ||
+ | * [[Genre theory, corpus and tautology]] | ||
+ | * [[Logical consequence]] | ||
+ | * [[Tautology]] | ||
+ | * [[Vacuous truth]] | ||
{{GFDL}} | {{GFDL}} |
Current revision
Related e |
Featured: |
In propositional logic, a tautology (from the Greek word ταυτολογία) is a propositional formula that is true under any possible valuation (also called a truth assignment or an interpretation) of its propositional variables. The philosopher Ludwig Wittgenstein first applied the term to propositional logic in 1921.
A tautology's negation is a contradiction, a propositional formula that is false regardless of the truth values of its propositional variables. Such propositions are called unsatisfiable. Conversely, a contradiction's negation is a tautology. A formula that is neither a tautology nor a contradiction is said to be logically contingent. Such a formula can be made either true or false based on the values assigned to its propositional variables.
A key property of tautologies is that an effective method exists for testing whether a given formula is always satisfied (or, equivalently, whether its complement is unsatisfiable). One such method uses truth tables. The decision problem of determining whether a formula is satisfiable is the Boolean satisfiability problem, an important example of an NP-complete problem in computational complexity theory.
See also