Tautology (logic)
From The Art and Popular Culture Encyclopedia
|
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
