Tautology

From Logic

(Difference between revisions)
m
Line 3: Line 3:
The negation of a tautology is clearly a [[Contradiction]], and the negation of a contradiction is clearly a tautology. A sentence that is neither a tautology (always true) nor a contradiction (always false) is logically [[Necessity and Contingency|contingent]], i.e., possible of being true or false .
The negation of a tautology is clearly a [[Contradiction]], and the negation of a contradiction is clearly a tautology. A sentence that is neither a tautology (always true) nor a contradiction (always false) is logically [[Necessity and Contingency|contingent]], i.e., possible of being true or false .
-
== Tautologies versus validities ==
 
-
 
-
The use of 'tautology', however, can be extended to [[first-order logic]] since it includes propositional logic. It can be further extended to include sentences that are quantified in the following sense. Call any statement that is not a truth-functional compound (i.e. not a conjunction, disjunction, conditional, etc.) a 'Boolean atom'. Then every [[atomic sentence]] is a Boolean atom, as is every quantified sentence&mdash;i.e. those of the form <math>\\forall x\\phi</math> or <math>\\exists x\\phi</math>. For example, <math>P(x)</math> and <math>\\forall x(P(x)\\land Q(y))</math> are Boolean atoms, while <math>\\forall xP(x)\\land Q(y)</math> is not. Then a statement of first-order logic is a tautology if the uniform relettering of each of its Boolean atoms yields a tautology in the propositional sense. Thus <math>\\forall x(P(x) \\lor\\lnot P(x))</math> is not a tautology, since its Boolean relettering yields <math>p</math>, while <math>\\forall xP(x)\\lor\\lnot\\forall xP(x)</math> is a tautology. One could further extend this notion by taking statements to be equivalence classes of statements, each of which is closed under the property of its elements being variants of each other (e.g. ''&forall;xP(x)'' is a variant of ''&forall;yP(y)'', and likewise upon substituting any other variable for ''x'' in the former). Then the Boolean relettering of <math>\\forall xP(x)\\lor\\lnot\\forall yP(y)</math> yields a tautology, since each disjunct falls under the same equivalence class.
 
==Discovering tautologies==
==Discovering tautologies==

Revision as of 22:48, 18 June 2007

In Popositional Logic, a tautology is a statement that is truth-functionally valid—i.e. it is universally true, or true in every interpretation). For example, the statement "If it rains, then it rains" is a tautology. Every theorem of propositional logic is a tautology, and so we can equivalently define 'tautology' as any theorem of propositional logic—i.e. any statement that is deducible from the empty set in some system of deduction of propositional logic, such as a natural deduction system. The term is often mistakenly applied to any validity (or theorem) of first-order logic, though it applies only to a proper subset of such validities. The term was originally introduced by Ludwig Wittgenstein.

The negation of a tautology is clearly a Contradiction, and the negation of a contradiction is clearly a tautology. A sentence that is neither a tautology (always true) nor a contradiction (always false) is logically contingent, i.e., possible of being true or false .


Discovering tautologies

An effective procedure for checking whether a propositional formula is a tautology or not is by means of a Truth Table


References

Retrieved from "http://editthis.info/logic/Tautology"
Personal tools