# Logic

Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents statements and argument patterns symbolically, using formal systems such as first order logic. Within formal logic, mathematical logic studies the mathematical characteristics of logical systems, while philosophical logic applies them to philosophical problems such as the nature of meaning, knowledge, and existence. Systems of formal logic are also applied in other fields including linguistics, cognitive science, and computer science.

Logic has been studied since Antiquity, early approaches including Aristotelian logic, stoic logic, Anviksiki, and the mohists. Modern formal logic has its roots in the work of late 19th century mathematicians such as Gottlob Frege.

## Formal and informal logic

Logic can be studied formally or informally. A formal approach is one that abstracts away from content, looking for patterns that arise from form alone. For instance, the formal rule of conjunction introduction states that any two statements $P$  and $Q$  together imply their conjunction $P\&Q$ . This rule is formal since the symbols $P$  and $Q$  can stand in for any two statements, regardless of their content.

On an informal approach, inferences of this sort would have to be characterized using particular statements. Informal logic is often part of courses in critical thinking, while informal approaches such as dialectical logic and argumentation theory continue as areas of research.

## Subfields

### Philosophical logic

Philosophical logic is the study of logic within philosophy. It includes applications to problems in epistemology, ethics, philosophy of mathematics, and natural language semantics.

### Mathematical logic

Mathematical logic is the study of logic within mathematics. Major subareas include model theory, proof theory, set theory, and computability theory.

Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic. However, it can also include attempts to use logic to analyze mathematical reasoning or to establish logic-based foundations of mathematics. The latter was a major concern in early 20th century mathematical logic, which pursued the program of logicism pioneered by philosopher-logicians such as Gottlob Frege and Bertrand Russell. Mathematical theories were supposed to be logical tautologies, and the programme was to show this by means of a reduction of mathematics to logic. The various attempts to carry this out met with failure, from the crippling of Frege's project in his Grundgesetze by Russell's paradox, to the defeat of Hilbert's program by Gödel's incompleteness theorems.

Set theory originated in the study of the infinite by Georg Cantor, and it has been the source of many of the most challenging and important issues in mathematical logic, from Cantor's theorem, through the status of the Axiom of Choice and the question of the independence of the continuum hypothesis, to the modern debate on large cardinal axioms.

Recursion theory captures the idea of computation in logical and arithmetic terms; its most classical achievements are the undecidability of the Entscheidungsproblem by Alan Turing, and his presentation of the Church–Turing thesis. Today recursion theory is mostly concerned with the more refined problem of complexity classes—when is a problem efficiently solvable?—and the classification of degrees of unsolvability.

### Computational logic

In computer science, logic is studied as part of the theory of computation. Key areas of logic that are relevant to computing include computability theory, modal logic, and category theory. Early computer machinery was based on ideas from logic such as the lambda calculus. Computer scientists also apply concepts from logic to problems in computing and vice versa. For instance, modern artificial intelligence builds on logicians' work in argumentation theory, while automated theorem proving can assist logicians in finding and checking proofs. In logic programming languages such as Prolog, a program computes the consequences of logical axioms and rules to answer a query.

### Formal semantics of natural language

Formal semantics is a subfield of both linguistics and philosophy which uses logic to analyze meaning in natural language. It is an empirical field which seeks to characterize the denotations of linguistic expressions and explain how those denotations are composed from the meanings of their parts. The field was developed by Richard Montague and Barbara Partee in the 1970s, and remains an active area of research. Central questions include scope, binding, and linguistic modality.

## Concepts

### Varieties of reasoning

Arguments are often divided into those that are deductive, inductive, and abductive. In the most prominent conception of logic, only deductive reasoning counts as logic in the strict sense.[i]

A deductive argument is one whose premises are intended to guarantee the truth of its conclusion. In other words, a deductive argument seeks to reach its conclusion by logical necessity. For instance, the following argument is deductive.

• Deductive argument:
1. Victoria is tall.
2. Victoria has brown hair.
3. Therefore, Victoria is tall and has brown hair.

Inductive arguments are those in which the premises are merely evidence for the conclusion.

• Inductive argument:
1. Victoria is tall.
2. Tall people are generally good at basketball.
3. Therefore, Victoria is good at basketball.

Abductive reasoning involves reasoning to the most likely explanation.

• Abductive argument:
1. Victoria is tall.
2. Victoria has brown hair.
3. Therefore, Victoria must have a tall or brown-haired ancestor .

### Valid and sound arguments

A deductive argument is valid if it is impossible for its premises to be true while its conclusion is false. For example, the example of a deductive argument in the previous section is valid since it would be logically impossible for Victoria to be tall, to have brown hair, but not be tall and have brown hair. The other arguments in that section would not be valid if understood as deductive, since their conclusions could conceivably be false even if the premises are true.

A deductive argument is sound if it is valid and all of its premises are true. For instance, the first argument given above would be sound if Victoria is indeed tall and indeed has brown hair. The validity of an argument is determined solely by its logical form, while its soundness additionally depends on its content.

### Formal system

A formal system of logic consists of a language, a proof system, and a semantics.  A system's language and proof system are sometimes grouped together as the system's syntax_(logic), since they both concern the form rather than the content of the system's expressions.

#### Formal language

A language is a set of well formed formulas. For instance, in propositional logic, $P\&Q$  is a formula but $PQ\&\&\&$  is not. Languages are typically defined by providing an alphabet of basic expressions and recursive syntactic rules which build them into formulas.

#### Proof system

A proof system is a collection of formal rules which define when a conclusion follows from given premises. For instance, the classical rule of conjunction introduction states that $P\&Q$  follows from the premises $P$  and $Q$ . Rules in a proof systems are always defined in terms of formulas' syntactic form, never in terms of their meanings. Such rules can be applied sequentially, giving a mechanical procedure for generating conclusions from premises. There are a number of different types of proof systems including natural deduction and sequent calculi.

#### Semantics

A semantics is a system for mapping expressions of a formal language to their denotations. In many systems of logic, denotations are truth values. For instance, the semantics for classical propositional logic assigns the formula $P\&Q$  the denotation "true" whenever $P$  is true and $Q$  is too. Entailment is a semantic relation which holds between formulas when the first cannot be true without the second being true as well.

#### Metalogic

Metalogic is the study of properties of formal systems. Two central metalogical properties are soundness and completeness. A system of logic is sound when its proof system cannot derive a conclusion from a set of premises unless it is semantically entailed by them. In other words, its proof system cannot lead to false conclusions, as defined by the semantics. A system is complete when its proof system can derive every conclusion that is semantically entailed by its premises. In other words, its proof system can lead to any true conclusion, as defined by the semantics. Thus, soundness and completeness together describe a system whose notions of validity and entailment line up perfectly.

Other important metalogical properties include consistency, decidability, and expressive power[disambiguation needed].

## .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}Systems of formal logic

### Propositional logic

Propositional logic comprises formal systems in which formulae are built from atomic propositions using logical connectives. For instance, propositional logic represents the conjunction of two atomic propositions $P$  and $Q$  as the complex formula $P\&Q$ . Unlike predicate logic where terms and predicates are the smallest units, propositional logic takes full propositions with truth values as its most basic component. Thus, propositional logics can only represent logical relationships that arise from the way complex propositions are built from simpler ones; it cannot represent inferences that results from the inner structure of a proposition.

### Predicate logic

Gottlob Frege's Begriffschrift introduced the notion of quantifier in a graphical notation, which here represents the judgement that $\forall x.F(x)$  is true.

Predicate logic is the generic term for symbolic formal systems such as first-order logic, second-order logic, many-sorted logic, and infinitary logic. It provides an account of quantifiers general enough to express a wide set of arguments occurring in natural language. For example, Bertrand Russell's famous barber paradox, "there is a man who shaves all and only men who do not shave themselves" can be formalised by the sentence $(\exists x)({\text{man}}(x)\wedge (\forall y)({\text{man}}(y)\rightarrow ({\text{shaves}}(x,y)\leftrightarrow \neg {\text{shaves}}(y,y))))$ , using the non-logical predicate ${\text{man}}(x)$  to indicate that x is a man, and the non-logical relation ${\text{shaves}}(x,y)$  to indicate that x shaves y; all other symbols of the formulae are logical, expressing the universal and existential quantifiers, conjunction, implication, negation and biconditional.

The development of predicate logic is usually attributed to Gottlob Frege, who is also credited as one of the founders of analytic philosophy, but the formulation of predicate logic most often used today is the first-order logic presented in Principles of Mathematical Logic by David Hilbert and Wilhelm Ackermann in 1928. The analytical generality of predicate logic allowed the formalization of mathematics, drove the investigation of set theory, and allowed the development of Alfred Tarski's approach to model theory. It provides the foundation of modern mathematical logic.

### Modal logic

Modal logic is the study of formal systems originally developed to represent statements about necessity and possibility. For instance the modal formula $\Diamond P$  can be read as "possibly $P$ " while $\Box P$  can be read as "necessarily $P$ ". Modal logics can be used to represent different phenomena depending on what flavor of necessity and possibility is under consideration. When $\Box$  is used to represent epistemic necessity, $\Box P$  states that $P$  is known. When $\Box$  is used to represent deontic necessity, $\Box P$  states that $P$  is a moral or legal obligation. Within philosophy, modal logics are widely used in formal epistemology, formal ethics, and metaphysics. Within linguistic semantics, systems based on modal logic are used to analyze linguistic modality in natural languages.

The earliest formal system of modal logic was developed by Avicenna, who ultimately developed a theory of "temporally modalized" syllogistic. While the study of necessity and possibility remained important to philosophers, little logical innovation happened until the landmark investigations of C. I. Lewis in 1918, who formulated a family of rival axiomatizations of the alethic modalities. His work unleashed a torrent of new work on the topic, expanding the kinds of modality treated to include deontic logic and epistemic logic. The seminal work of Arthur Prior applied the same formal language to treat temporal logic and paved the way for the marriage of the two subjects. Saul Kripke and Jaakko Hintikka built on this work to develop the frame semantics, which is now the standard semantics for modal logic. This graph-theoretic way of looking at modality has driven many applications in computational linguistics and computer science, such as dynamic logic.

### Non-classical logic

Non-classical logics are systems that reject various rules of classical logic. They are motivated by the view that classical logic does not accurately represent the nature of truth and reasoning.

One major non-classical paradigm is intuitionistic logic, which rejects the law of the excluded middle. Intuitionism was developed by the Dutch mathematicians L.E.J. Brouwer and Arend Heyting to underpin their constructive approach to mathematics, in which the existence of a mathematical object can only be proven by constructing it. Intuitionism was further pursued by Gerhard Gentzen, Kurt Gödel, Michael Dummett, among others. Intuitionistic logic is of great interest to computer scientists, as it is a constructive logic and sees many applications, such as extracting verified programs from proofs and influencing the design of programming languages through the formulae-as-types correspondence. It is closely related to nonclassical systems such as Gödel–Dummett logic and inquisitive logic.

Multi-valued logics depart from classicality by rejecting the principle of bivalence which requires all propositions to be either true or false. For instance, Jan Łukasiewicz and Stephen Cole Kleene both proposed ternary logics which have a third truth value representing that a statement's truth value is indeterminate. These logics have seen applications including to presupposition in linguistics. Fuzzy logics are multivalued logics that have an infinite number of "degrees of truth", represented by a real number between 0 and 1.

## Controversies

### "Is Logic Empirical?"

What is the epistemological status of the laws of logic? What sort of argument is appropriate for criticizing purported principles of logic? In an influential paper entitled "Is Logic Empirical?" Hilary Putnam, building on a suggestion of W. V. Quine, argued that in general the facts of propositional logic have a similar epistemological status as facts about the physical universe, for example as the laws of mechanics or of general relativity, and in particular that what physicists have learned about quantum mechanics provides a compelling case for abandoning certain familiar principles of classical logic: if we want to be realists about the physical phenomena described by quantum theory, then we should abandon the principle of distributivity, substituting for classical logic the quantum logic proposed by Garrett Birkhoff and John von Neumann.

Another paper of the same name by Michael Dummett argues that Putnam's desire for realism mandates the law of distributivity. Distributivity of logic is essential for the realist's understanding of how propositions are true of the world in just the same way as he has argued the principle of bivalence is. In this way, the question, "Is Logic Empirical?" can be seen to lead naturally into the fundamental controversy in metaphysics on realism versus anti-realism.

### Tolerating the impossible

Georg Wilhelm Friedrich Hegel was deeply critical of any simplified notion of the law of non-contradiction. It was based on Gottfried Wilhelm Leibniz's idea that this law of logic also requires a sufficient ground to specify from what point of view (or time) one says that something cannot contradict itself. A building, for example, both moves and does not move; the ground for the first is our solar system and for the second the earth. In Hegelian dialectic, the law of non-contradiction, of identity, itself relies upon difference and so is not independently assertable.

Closely related to questions arising from the paradoxes of implication comes the suggestion that logic ought to tolerate inconsistency. Relevance logic and paraconsistent logic are the most important approaches here, though the concerns are different: a key consequence of classical logic and some of its rivals, such as intuitionistic logic, is that they respect the principle of explosion, which means that the logic collapses if it is capable of deriving a contradiction. Graham Priest, the main proponent of dialetheism, has argued for paraconsistency on the grounds that there are in fact, true contradictions.[clarification needed]

### Conceptions of logic

Logic arose from a concern with correctness of argumentation. Modern logicians usually wish to ensure that logic studies just those arguments that arise from appropriately general forms of inference. For example, Thomas Hofweber writes in the Stanford Encyclopedia of Philosophy that logic "does not, however, cover good reasoning as a whole. That is the job of the theory of rationality. Rather it deals with inferences whose validity can be traced back to the formal features of the representations that are involved in that inference, be they linguistic, mental, or other representations."

The idea that logic treats special forms of argument, deductive argument, rather than argument in general, has a history in logic that dates back at least to logicism in mathematics (19th and 20th centuries) and the advent of the influence of mathematical logic on philosophy. A consequence of taking logic to treat special kinds of argument is that it leads to identification of special kinds of truth, the logical truths (with logic equivalently being the study of logical truth), and excludes many of the original objects of study of logic that are treated as informal logic. Robert Brandom has argued against the idea that logic is the study of a special kind of logical truth, arguing that instead one can talk of the logic of material inference (in the terminology of Wilfred Sellars), with logic making explicit the commitments that were originally implicit in informal inference.[page needed]

### Rejection of logical truth

The philosophical vein of various kinds of skepticism contains many kinds of doubt and rejection of the various bases on which logic rests, such as the idea of logical form, correct inference, or meaning, sometimes leading to the conclusion that there are no logical truths. This is in contrast with the usual views in philosophical skepticism, where logic directs skeptical enquiry to doubt received wisdoms, as in the work of Sextus Empiricus.

Friedrich Nietzsche provides a strong example of the rejection of the usual basis of logic: his radical rejection of idealization led him to reject truth as a "... mobile army of metaphors, metonyms, and anthropomorphisms—in short ... metaphors which are worn out and without sensuous power; coins which have lost their pictures and now matter only as metal, no longer as coins". His rejection of truth did not lead him to reject the idea of either inference or logic completely but rather suggested that "logic [came] into existence in man's head [out] of illogic, whose realm originally must have been immense. Innumerable beings who made inferences in a way different from ours perished". Thus there is the idea that logical inference has a use as a tool for human survival, but that its existence does not support the existence of truth, nor does it have a reality beyond the instrumental: "Logic, too, also rests on assumptions that do not correspond to anything in the real world".

This position held by Nietzsche however, has come under extreme scrutiny for several reasons. Some philosophers, such as Jürgen Habermas, claim his position is self-refuting—and accuse Nietzsche of not even having a coherent perspective, let alone a theory of knowledge. Georg Lukács, in his book The Destruction of Reason, asserts that, "Were we to study Nietzsche's statements in this area from a logico-philosophical angle, we would be confronted by a dizzy chaos of the most lurid assertions, arbitrary and violently incompatible." Bertrand Russell described Nietzsche's irrational claims with "He is fond of expressing himself paradoxically and with a view to shocking conventional readers" in his book A History of Western Philosophy.

## History

Logic was developed independently in several cultures during antiquity. One major early contributor was Aristotle, who developed term logic in his Organon and Prior Analytics. In this approach, judgements are broken down into propositions consisting of two terms that are related by one of a fixed number of relation. Inferences are expressed by means of syllogisms that consist of two propositions sharing a common term as premise, and a conclusion that is a proposition involving the two unrelated terms from the premises. Aristotle's monumental insight was the notion that arguments can be characterized in terms of their form. The later logician Łukasiewicz described this insight as "one of Aristotle's greatest inventions". Aristotle's system of logic was also responsible for the introduction of hypothetical syllogism, temporal modal logic, and inductive logic, as well as influential vocabulary such as terms, predicables, syllogisms and propositions. Aristotelian logic was highly regarded in classical and medieval times, both in Europe and the Middle East. It remained in wide use in the West until the early 19th century. It has now been superseded by later work, though many of its key insights live on in modern systems of logic.

Ibn Sina (Avicenna) (980–1037 CE) was the founder of Avicennian logic, which replaced Aristotelian logic as the dominant system of logic in the Islamic world, and also had an important influence on Western medieval writers such as Albertus Magnus and William of Ockham. Avicenna wrote on the hypothetical syllogism and on the propositional calculus. He developed an original "temporally modalized" syllogistic theory, involving temporal logic and modal logic. He also made use of inductive logic, such as the methods of agreement, difference, and concomitant variation which are critical to the scientific method. Fakhr al-Din al-Razi (b. 1149) criticised Aristotle's "first figure" and formulated an early system of inductive logic, foreshadowing the system of inductive logic developed by John Stuart Mill (1806–1873).

In Europe during the later medieval period, major efforts were made to show that Aristotle's ideas were compatible with Christian faith. During the High Middle Ages, logic became a main focus of philosophers, who would engage in critical logical analyses of philosophical arguments, often using variations of the methodology of scholasticism. Initially, medieval Christian scholars drew on the classics that had been preserved in Latin through commentaries by such figures such as Boethius, later the work of Islamic philosophers such as Avicenna and Averroes were drawn on, which expanded the range of ancient works available to medieval Christian scholars since more Greek work was available to Muslim scholars that had been preserved in Latin commentaries. In 1323, William of Ockham's influential Summa Logicae was released. By the 18th century, the structured approach to arguments had degenerated and fallen out of favour, as depicted in Holberg's satirical play Erasmus Montanus. The Chinese logical philosopher Gongsun Long (c. 325–250 BCE) proposed the paradox "One and one cannot become two, since neither becomes two."[ii] In China, the tradition of scholarly investigation into logic, however, was repressed by the Qin dynasty following the legalist philosophy of Han Feizi.

In India, the Anviksiki school of logic was founded by Medhātithi (c. 6th century BCE). Innovations in the scholastic school, called Nyaya, continued from ancient times into the early 18th century with the Navya-Nyāya school. By the 16th century, it developed theories resembling modern logic, such as Gottlob Frege's "distinction between sense and reference of proper names" and his "definition of number", as well as the theory of "restrictive conditions for universals" anticipating some of the developments in modern set theory.[iii] Since 1824, Indian logic attracted the attention of many Western scholars, and has had an influence on important 19th-century logicians such as Charles Babbage, Augustus De Morgan, and George Boole. In the 20th century, Western philosophers like Stanislaw Schayer and Klaus Glashoff have explored Indian logic more extensively.

The syllogistic logic developed by Aristotle predominated in the West until the mid-19th century, when interest in the foundations of mathematics stimulated the development of symbolic logic (now called mathematical logic). In 1854, George Boole published The Laws of Thought, introducing symbolic logic and the principles of what is now known as Boolean logic. In 1879, Gottlob Frege published Begriffsschrift, which inaugurated modern logic with the invention of quantifier notation, reconciling the Aristotelian and Stoic logics in a broader system, and solving such problems for which Aristotelian logic was impotent, such as the problem of multiple generality. From 1910 to 1913, Alfred North Whitehead and Bertrand Russell published Principia Mathematica on the foundations of mathematics, attempting to derive mathematical truths from axioms and inference rules in symbolic logic. In 1931, Gödel raised serious problems with the foundationalist program and logic ceased to focus on such issues.

The development of logic since Frege, Russell, and Wittgenstein had a profound influence on the practice of philosophy and the perceived nature of philosophical problems (see analytic philosophy) and philosophy of mathematics. Logic, especially sentential logic, is implemented in computer logic circuits and is fundamental to computer science. Logic is commonly taught by university philosophy, sociology, advertising and literature departments, often as a compulsory discipline.