Tautology (logic) - Citizendia

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. This is a technical mathematical article about the area of mathematical logic variously known as "propositional calculus" or "propositional logic" Greek (el ελληνική γλώσσα or simply el ελληνικά — "Hellenic" is an Indo-European language, spoken today by 15-22 million people mainly In Propositional logic, a propositional formula is a type of syntactic formula which is well formed and has a Truth value. Valuation in mathematics may refer to Valuation (algebra Valuation (logic Valuation (measure theory In Logic an interpretation gives meaning to an artificial or Formal language or to a sentence of such a language by assigning a denotation (extension For example, the propositional formula $(A) \lor (\lnot A)$ ("A or not-A") is a tautology, because the statement is true for any valuation of A. Examples can be more complex such as $(A \land B) \lor (\lnot A) \lor (\lnot B)$ ("A and B; or not-A; or not-B"). The philosopher Ludwig Wittgenstein first applied the term to propositional logic in 1921. Philosophy is the study of general problems concerning matters such as existence knowledge truth beauty justice validity mind and language

A tautology's negation is a contradiction, a propositional formula that is false regardless of the truth values of its propositional variables. In Classical logic, a contradiction consists of a logical incompatibility between two or more Propositions It occurs when the propositions taken together yield 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). An effective method (also called an effective procedure) for a class of problems is a method for which each step in the method may be described as a mechanical operation and One such method uses truth tables. A truth table is a Mathematical table used in Logic — specifically in connection with Boolean algebra, Boolean functions and Propositional 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. In Computability theory and Computational complexity theory, a decision problem is a question in some Formal system with a yes-or-no answer depending on In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources

The notation $\vDash S$ is used to indicate that S is a tautology. The symbol $\top$ is sometimes used to denote an arbitrary tautology, with the dual symbol $\bot$ (falsum) representing an arbitrary contradiction.

1 History
2 Background
3 Definition and examples
4 Verifying tautologies
5 Tautological implication
6 Substitution
7 Efficient verification and the Boolean satisfiability problem
8 Tautologies versus validities in first-order logic
9 Tautology and its application in Logic Synthesis
10 References
11 External links
12 See also
- 12.1 Normal forms
- 12.2 Related logical topics

History

The word tautology was used by the ancient Greeks to describe a statement that was true merely by virtue of saying the same thing twice, a pejorative meaning that is still used for rhetorical tautologies. In Rhetoric, a tautology is an unnecessary (and usually unintentional repetition of meaning using different words that effectively say the same thing twice (often originally Between 1800 and 1940, the word gained new meaning in logic, and is currently used in mathematical logic to denote a certain type of proposition formula, without the pejorative connotations it originally enjoyed.

In 1800, Immanuel Kant wrote in his book Logic:

"The identity of concepts in analytical judgements can be either explict (explicita) or non-explicit (implicita). Immanuel Kant (ɪmanuəl kant 22 April 1724 12 February 1804 was an 18th-century German Philosopher from the Prussian city of Königsberg In the former case analytic propositions are tautological.

Here analytic proposition refers to an analytic truth, a statement in natural language that is true solely because of the terms involved. The analytic-synthetic distinction is a conceptual distinction used primarily in Philosophy to distinguish propositions into two types analytic propositions and

In 1884, Gottlob Frege proposed in his Grundlagen that a truth is analytic exactly if it can be derived using logic. Friedrich Ludwig Gottlob Frege ( 8 November 1848, Wismar, Grand Duchy of Mecklenburg-Schwerin &ndash 26 July 1925 But he maintained a distinction between analytic truths (those true based only on the meanings of their terms) and tautologies (statements devoid of content).

In 1921, in his Tractatus Logico-Philosophicus, Ludwig Wittgenstein proposed that statements that can be deduced by logical deduction are tautological (empty of meaning) as well as being analytic truths. Tractatus Logico-Philosophicus is the only book-length work published by Austrian Philosopher Ludwig Wittgenstein. Henri Poincaré had made similar remarks in Science and Hypothesis in 1905. Jules Henri Poincaré ( 29 April 1854 &ndash 17 July 1912) (ˈʒyl ɑ̃ˈʁi pwɛ̃kaˈʁe was a French Mathematician Although Bertrand Russell at first argued against these remarks by Wittgenstein and Poincaré, claiming that mathematical truths were not only non-tautologous but were synthetic, he later spoke in favor of them in 1918:

"Everything that is a proposition of logic has got to be in some sense or the other like a tautology. Bertrand Arthur William Russell 3rd Earl Russell, OM, FRS (18 May 1872 – 2 February 1970 was a British Philosopher, Historian The analytic-synthetic distinction is a conceptual distinction used primarily in Philosophy to distinguish propositions into two types analytic propositions and It has got to be something that has some peculiar quality, which I do not know how to define, that belongs to logical propositions but not to others. "

Here logical proposition refers to a proposition that is provable using the laws of logic.

During the 1930s, the formalization of the semantics of propositional logic in terms of truth assignments was developed. The term tautology began to be applied to those propositional formulas that are true regardless of the truth or falsity of their propositional variables. Some early books on logic (such as Symbolic Logic by Lewis and Langford, 1932) used the term for any proposition (in any formal logic) that is universally valid. It is common in presentations after this (such as Kleene 1967 and Enderton 2002) to use tautology to refer to a logically valid propositional formula, but to maintain a distinction between tautology and logically valid in the context of first-order logic (see below). In Propositional logic, a tautology (from the Greek word ταυτολογία is a Propositional formula that is true under any possible valuation

Background

Main article: propositional logic

Propositional logic begins with propositional variables, atomic units that represent concrete propositions. This is a technical mathematical article about the area of mathematical logic variously known as "propositional calculus" or "propositional logic" A formula consists of propositional variables connected by logical connectives in a meaningful way, so that the truth of the overall formula can be uniquely deduced from the truth or falsity of each variable. A valuation is a function that assigns each propositional variable either T (for truth) or F (for falsity). So, for example, using the propositional variables A and B, the binary connectives $\lor$ and $\land$ representing disjunction and conjunction, respectively, and the unary connective $\lnot$ representing negation, the following formula can be obtained:

$(A \land B) \lor (\lnot A) \lor (\lnot B)$ . In Logic and Mathematics, negation or not is an operation on Logical values for example the logical value of a Proposition

A valuation here must assign to each of A and B either T or F. But no matter how this assignment is made, the overall formula will come out true. For if the first disjunct $(A \land B)$ is not satisfied by a particular valuation, then one of A and B is assigned F, which will cause the corresponding later disjunct to be T.

Definition and examples

A formula of propositional logic is a tautology if the formula itself is always true regardless of which valuation is used for the propositional variables.

There are infinitely many tautologies. Examples include:

$P \lor \lnot P$ ("P or not-P"), the law of the excluded middle. This article uses forms of logical notation For a concise description of the symbols used in this notation see Table of logic symbols. This formula has only one propositional variable, P. Any valuation for this formula must, by definition, assign $P$ one of the truth values true or false, and assign $\lnot P$ the other truth value.
$(A \to B) \Leftrightarrow (\lnot B \to \lnot A)$ ("if A implies B then not-B implies not-A", and visa versa), which expresses the law of contraposition. For contraposition in the field of traditional logic see Contraposition (traditional logic.

Verifying tautologies

The problem of determining whether a formula is a tautology is fundamental in propositional logic. The definition suggests one method: proceed by cases and verify that every possible valuation does satisfy the formula. An algorithmic method of verifying that every valuation causes this sentence to be true is to make a truth table that includes every possible valuation. A truth table is a Mathematical table used in Logic — specifically in connection with Boolean algebra, Boolean functions and Propositional

For example, consider the formula

$((A \land B) \to C) \Leftrightarrow (A \to (B \to C)).$

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 subformulas of the formula above, culminating in a column showing the truth value of the original formula under each valuation.

A	B	C	$A \land B$	$(A \land B) \to C$	$B \to C$	$A \to (B \to C)$	$((A \land B) \to C) \Leftrightarrow (A \to (B \to 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.

It is also possible to define a deductive system (proof system) for propositional logic, as a simpler variant of the deductive systems employed for first-order logic (see Kleene 1957, Sec 1. A deductive system (also called a deductive apparatus of a Formal system) consists of the Axioms (or Axiom schemata and Rules of inference First-order logic (FOL is a formal Deductive system used in mathematics philosophy linguistics and computer science 9 for one such system). A proof of a tautology in an appropriate deduction system may be much shorter than a complete truth table (a formula with n propositional variables requires a truth table with 2ⁿlines, which quickly becomes infeasible as n increases). Proof systems are also required for the study of intuitionistic propositional logic, in which the method of truth tables cannot be employed because the law of the excluded middle is not assumed.

Tautological implication

A formula R is said to tautologically imply a formula S if every valuation that causes R to be true also causes S to be true. This situation is denoted $R \vDash S$ . It is equivalent to the formula $R \to S$ being a tautology (Kleene 1967 p. 27).

For example, let S be $A \land (B \lor \lnot B)$ . Then S is not a tautology, because any valuation that makes A false will make S false. But any valuation that makes A true will make S true, because $B \lor \lnot B$ is a tautology. Let R be the formula $A \land C$ . Then $R \models S$ , because any valuation satisfying R makes A true and thus makes S true

It follows from the definition that if a formula R is a contradiction then R tautologically implies every formula, because there is no truth valuation that causes R to be true and so the definition of tautological implication is trivially satisfied. Similarly, if S is a tautology then S is tautologically implied by every formula.

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 S_A is chosen. Then the sentence obtained by replacing each variable A in S with the corresponding sentence S_A is also a tautology.

For example, let S be $(A \land B) \lor (\lnot A) \lor (\lnot B)$ , a tautology. Let S_A be $C \lor D$ and let S_B be $C \to E$ . It follows from the substitution rule that the sentence

$((C \lor D) \land (C \to E)) \lor (\lnot (C \lor D) )\lor (\lnot (C \to E))$

is a tautology.

Efficient verification and the Boolean satisfiability problem

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

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. A truth table is a Mathematical table used in Logic — specifically in connection with Boolean algebra, Boolean functions and Propositional 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. An effective method (also called an effective procedure) for a class of problems is a method for which each step in the method may be described as a mechanical operation and

As an efficient procedure, however, truth tables are constrained by the fact that the number of valuations that must be checked increases as 2^k, where k is the number of variables in the formula. Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources 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.

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 $\lnot S$ . 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. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties 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.

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. First-order logic (FOL is a formal Deductive system used in mathematics philosophy linguistics and computer science 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.

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 $A \lor \lnot A$ is a tautology of propositional logic, $(\forall x ( x = x)) \lor (\lnot \forall x (x = x))$ 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:

$(((\exists x Rx) \land \lnot (\exists x Sx)) \to \forall x Tx) \Leftrightarrow ((\exists x Rx) \to ((\lnot \exists x Sx) \to \forall x Tx)).$

It is obtained by replacing A with $\exists x Rx$ , B with $\lnot \exists x Sx$ , and C with $\forall x Tx$ in the propositional tautology considered above.

Not all logical validities are tautologies in first-order logic. For example, the sentence

$(\forall x Rx) \to \lnot \exists x \lnot Rx$

is true in any first-order interpretation, but it corresponds to the propositional sentence $A \to B$ 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. 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 Logic optimization a part of Logic synthesis, is the process of finding an equivalent representation of the specified Logic circuit under one or more specified constraints Though the problem is intractable, whether or not a function is a tautology can be efficiently answered using the Recursive Paradigm. Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources 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.

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

Eric W. Weisstein, Tautology at MathWorld. Eric W Weisstein (born March 18, 1969, in Bloomington Indiana) is an Encyclopedist who created and maintains MathWorld MathWorld is an online Mathematics reference work created and largely written by Eric W

Contents