|
In propositional logic, a tautology (from the Greek word ταυτολογία) is a sentence that is true in every valuation (also called interpretation) of its propositional variables, independent of the truth values assigned to these variables. For example,  is a tautology, because any valuation either makes A and B both true, or makes one or the other false. According to Kleene (1967, p. 12), the term was introduced by Ludwig Wittgenstein (1921). Propositional logic or sentential logic is the logic of propositions, sentences, or clauses. ...
In mathematical logic, a sentence is a formula with no free variables; therefore, a sentence is either true or false in a given structure. ...
Model Theory In logic and model theory, a valuation is a map from the set of variables of a first-order language to the universe of some interpretation of that language. ...
Stephen Cole Kleene (January 5, 1909 - January 25, 1994) was an American mathematician whose work at the University of Wisconsin-Madison helped lay the foundations for theoretical computer science. ...
Ludwig Josef Johann Wittgenstein (IPA: ) (April 26, 1889 in Vienna, Austria – April 29, 1951 in Cambridge, England) was an Austrian philosopher who contributed several ground-breaking ideas to philosophy, primarily in the foundations of logic, the philosophy of mathematics, the philosophy of language, and the philosophy of mind. ...
The negation of a tautology is a contradiction, a sentence that is false regardless of the truth values of its propositional variables, and the negation of a contradiction is a tautology. A sentence that is neither a tautology nor a contradiction is logically contingent. Such a sentence can be made either true or false by choosing an appropriate interpretation of its propositional variables. Broadly speaking, a contradiction is an incompatibility between two or more statements, ideas, or actions. ...
Modal logic, or (less commonly) intensional logic is the branch of logic that deals with sentences that are qualified by modalities such as can, could, might, may, must, possibly, and necessarily, and others. ...
Examples There are infinitely many tautologies. One example is  the law of the excluded middle. A truth valuation for this formula must, by definition, assign A one of the truth value true or false, and assign  the other truth value. Thus the disjunction in this law is satisfied by every valuation. The law of excluded middle (tertium non datur in Latin) states that for any proposition P, it is true that (P or ~P). ...
Another tautology is
 One method of verifying that every valuation causes this sentence to be true is to make a truth table that examines every possible valuation. There are 8 possible valuations for the propositional variables A, B, C, represented by the first three columns of the following table. The remaining columns show the truth of subsentences of the sentence above, culminating in a column showing the truth value of this sentence under each interpretation. Truth tables are a type of mathematical table used in logic to determine whether an expression is true or whether an argument is valid. ...
| A | B | C |  |  |  |  |  | | T | T | T | T | T | T | T | T | | T | T | F | T | F | F | F | T | | T | F | T | F | T | T | T | T | | T | F | F | F | T | T | T | T | | F | T | T | F | T | T | T | T | | F | T | F | F | T | F | T | T | | F | F | T | F | T | T | T | T | | F | F | F | F | T | T | T | T | Because each row of the final column shows T, the sentence in question is verified to be a tautology.
Notation The notation  is used to indicate that S is a tautology. The symbol  is sometimes used to denote an arbitrary tautology, with the dual symbol  (falsum) representing an arbitrary contradiction.
Tautological implication A sentence S is said to tautologically imply a sentence T if every truth valuation that causes S to be true also causes T to be true. This situation is denoted  . It is equivalent to the sentence  being a tautology (Kleene 1967 p. 27).
It follows from the definition that if S is a contradiction then S tautologically implies every sentence, because there is no truth valuation that causes S to be true and so the definition of tautological implication is trivially satisfied.
Substitution There is a general procedure, the substitution rule, that allows additional tautologies to be constructed from a given tautology (Kleene 1967 sec. 3). Suppose that S is a tautology and for each propositional variable A in S a fixed sentence SA is chosen. Then the sentence obtain by replacing each variable A in S with the corresponding sentence SA is also a tautology.
For example, let S be , a tautology. Let SA be  and let SB be  . It follows from the substitution rule that the sentence
 is a tautology.
Verifying tautologies The problem of constructing practical algorithms to determine whether sentences with large numbers of propositional variables are tautologies is an area of contemporary research in the area of automated theorem proving. Automated theorem proving (ATP) or automated deduction, currently the most well-developed subfield of automated reasoning (AR), is the proving of mathematical theorems by a computer program. ...
The method of truth tables illustrated above is provably correct – the truth table for a tautology will end in a column with only T, while the truth table for a sentence that is not a tautology will contain a row whose final column is F, and the valuation corresponding to that row is a valuation that does not satisfy the sentence being tested. This method for verifying tautologies is an effective procedure, which means that given unlimited computational resources it can always be used to mechanistically determine whether a sentence is a tautology. Truth tables are a type of mathematical table used in logic to determine whether an expression is true or whether an argument is valid. ...
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ...
As an efficient procedure, however, truth tables are constrained by the fact that the number of valuations that must be checked increases as 2k, where k is the number of variables in the formula. This exponential growth in the computation length renders the truth table method useless for formulas with thousands of propositional variables, as contemporary computing hardware cannot execute the algorithm in a feasible time period. In computer science, computational complexity theory is the branch of the theory of computation that studies the resources, or cost, of the computation required to solve a given computational problem. ...
The problem of determining whether there is any valuation that makes a formula true is the Boolean satisfiability problem; the problem of checking tautologies is equivalent to this problem, because verifying that a sentence S is a tautology is equivalent to verifying that there is no valuation satisfying  . It is known that the Boolean satisfiability problem is NP complete, and widely believed that there is no polynomial-time algorithm that can perform it. Current research focuses on finding algorithms that perform well on special classes of formulas, or terminate quickly on average even though some inputs may cause them to take much longer. To meet Wikipedias quality standards, this article or section may require cleanup. ...
In complexity theory, the NP-complete problems are the most difficult problems in NP (non-deterministic polynomial time) in the sense that they are the smallest subclass of NP that could conceivably remain outside of P, the class of deterministic polynomial-time problems. ...
Cubic time redirects here. ...
Tautologies versus validities in first-order logic The fundamental definition of a tautology is in the context of propositional logic. The definition can be extended, however, to sentences in first-order logic (see Enderton (2002, p. 114) and Kleene (1967 secs. 17–18)). These sentences may contain quantifiers, unlike sentences of propositional logic. In the context of first-order logic, a distinction is maintained between logical validities, sentences that are true in every model, and tautologies, which are a proper subset of the first-order logical validities. In the context of propositional logic, these two terms coincide. First-order logic (FOL) is a formal deductive system used by mathematicians, philosophers, linguists, and computer scientists. ...
A tautology in first-order logic is a sentence that can be obtain by taking a tautology of propositional logic and uniformly replacing each propositional variable by a first-order formula (one formula per propositional variable). For example, because  is a tautology of propositional logic,  is a tautology in first order logic. Similarly, in a first-order language with a unary relation symbols R,S,T, the following sentence is a tautology:
 It is obtained by replacing A with  , B with  , and C with  in the propositional tautology considered above.
Not all logical validities are tautologies in first-order logic. For example, the sentence
 is true in any first-order interpretation, but it corresponds to the propositional sentence  which is not a tautology of propositional logic.
Tautology and its application in Logic Synthesis In Logic Synthesis tautology plays an important role especially for Logic Optimization. Though the problem is intractable, whether or not a function is a tautology can be efficiently answered using the Recursive Paradigm. Any binary-valued function F is a tautology if and only if its cofactors with respect to any variable and its complement are both tautologies. Hence it can be easily concluded whether or not a function F is reducible to a tautology by recursive Shannon Expansion and the application of the above theorem. Logic synthesis is a process by which an abstract form of desired circuit behavior (typically register transfer level (RTL) or behavioral) is turned into a design implementation in terms of logic gates. ...
Logic Optimization a part of Logic Synthesis, is the process of finding an equivalent representation of the specificied Logic Circuit under one or more specified constraint. ...
Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ...
References - Enderton, H. B. (2002). A Mathematical Introduction to Logic. Harcourt/Academic Press. ISBN 0-12-238452-0
- Kleene, S. C. (1967). Mathematical Logic. Reprinted 2002, Dover. ISBN 0-486-42533-9
- Rechenbach, H. (1947). Elements of Symbolic Logic. Reprinted 1980, Dover. ISBN 0-486-24004-5
- Wittgenstein, L. (1921). "Logisch-philosophiche Abhandlung," Annalen der Naturphilosophie (Leipzig), v. 14, pp. 185–262. Reprinted in English translation as Tractatus logico-philosophicus, New York and London, 1922.
External links Dr. Eric W. Weisstein Encyclopedist Dr. Eric W. Weisstein (born March 18, 1969, in Bloomington, Indiana) is a noted encyclopedist in several technical areas of science and mathematics. ...
MathWorld is an online mathematics reference work, sponsored by Wolfram Research Inc. ...
See also
Normal forms In Boolean logic, Algebraic Normal Form (ANF) is a method of standardizing and normalizing logical formulas. ...
In boolean logic, a formula is in conjunctive normal form (CNF) if it is a conjunction of clauses, where a clause is a disjunction of literals. ...
In boolean logic, a disjunctive normal form (DNF) is a standardization (or normalization) of a logical formula which is a disjunction of conjunctive clauses. ...
Logic Optimization a part of Logic Synthesis, is the process of finding an equivalent representation of the specificied Logic Circuit under one or more specified constraint. ...
Related logical topics Boolean algebra is the finitary algebra of two values. ...
A boolean domain B is a generic 2-element set, say, B = {0, 1}, whose elements are interpreted as logical values, typically 0 = false and 1 = true. ...
A Boolean function describes how to determine a Boolean value output based on some logical calculation from Boolean inputs. ...
First-order logic (FOL) is a formal deductive system used by mathematicians, philosophers, linguists, and computer scientists. ...
Logical consequence is the relation that holds between a set of sentences and a sentence when the latter follows from the former. ...
A logical graph is a special type of graph-theoretic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic. ...
Propositional logic or sentential logic is the logic of propositions, sentences, or clauses. ...
In logic, a set of symbols is frequently used to express logical constructs. ...
Truth tables are a type of mathematical table used in logic to determine whether an expression is true or whether an argument is valid. ...
Vacuous truth is a special topic of first-order logic. ...
Zeroth-order logic is a term in popular use among practitioners for the subject matter otherwise known as boolean functions, monadic predicate logic, propositional calculus, or sentential calculus. ...
Related topics |
Feeds |
Contact