# Logic

Logic, from Classical Greek λόγος (logos), originally meaning the word, or what is spoken, (but coming to mean thought or reason or an explanation or a justification or key) is most often said to be the study of criteria for the evaluation of arguments, although the exact definition of logic is a matter of controversy among philosophers. However the subject is grounded, the task of the logician is the same: to advance an account of valid and fallacious inference, in order to allow one to distinguish good from bad arguments.

Traditionally, logic is studied as a branch of philosophy. Since the mid-1800s logic has also been commonly studied in mathematics, and, more recently, in set theory and computer science. As a science, logic investigates and classifies the structure of statements and arguments, both through the study of formal systems of inference, often expressed in symbolic or formal language, and through the study of arguments in natural language (a spoken language such as English, Italian, or Japanese). The scope of logic can therefore be very large, ranging from core topics such as the study of fallacies and paradoxes, to specialist analyses of reasoning such as probability, correct reasoning, and arguments involving causality.

## Nature of logic

Because of its fundamental role in philosophy, the nature of logic has been the object of intense dispute; it is not possible clearly to delineate the bounds of logic in terms acceptable to all rival viewpoints. Despite that controversy, the study of logic has been very coherent and technically grounded. In this article, we first characterize logic by introducing fundamental ideas about form, then by outlining some schools of thought, as well as by giving a brief overview of logic's history, an account of its relationship to other sciences, and finally, an exposition of some of logic's essential concepts.

### Informal, formal and symbolic logic

The crucial concept of form is central to discussions of the nature of logic, and it complicates exposition that the term 'formal' in "formal logic" is commonly used in an ambiguous manner. We shall start by giving definitions that we shall adhere to in the rest of this article:

• Informal logic is the study of arguments expressed in natural language. The study of fallacies—often known as informal fallacies—is an especially important branch of informal logic.
• An inference possesses a purely formal content if it can be expressed as a particular application of a wholly abstract rule, that is a rule that is not about any particular thing or property. (For example: The argument "If John was strangled he died. John was strangled. Therefore John died." is an example, in English, of the argument form or rule, "If P then Q. P is true. Therefore Q is true." Moreover, this is a valid argument form, known since the Middle Ages as Modus Ponens.) We will see later that on many definitions of logic, logical inference and inference with purely formal content are the same thing. This does not render the notion of informal logic vacuous, since one may wish to investigate logic without committing to a particular formal analysis.
• Formal logic is the field of study in which we are concerned with the form or structure of the inferences rather than the content.
• Symbolic logic is the study of abstractions, expressed in symbols, that capture the formal features of logical inference.

The ambiguity is that "formal logic" is very often used with the alternate meaning of symbolic logic as we have defined it, with informal logic meaning any logical investigation that does not involve symbolic abstraction; it is this sense of 'formal' that is parallel to the received usages coming from "formal languages" or "formal theory."

While formal logic is old, on the above analysis, dating back more than two millennia to the work of Aristotle, symbolic logic is comparatively new, and arises with the application of insights from mathematics to problems in logic. The passage from informal logic through formal logic to symbolic logic can be seen as a passage of increasing theoretical sophistication; of necessity, appreciating symbolic logic requires internalizing certain conventions that have become prevalent in the symbolic analysis of logic. Generally, logic is captured by a formal system, comprising a formal language, which describes a set of formulas and a set of rules of derivation. The formulas will normally be intended to represent claims that we may be interested in, and likewise the rules of derivation represent inferences; such systems usually have an intended interpretation.

Within this formal system, the rules of derivation of the system and its axioms (see the article Axiomatic Systems) then specify a set of theorems, which are formulas that are derivable from the system using the rules of derivation. The most essential property of a logical formal system is soundness, which is the property that under interpretation, all of the rules of derivation are valid inferences. The theorems of a sound formal system are then truths of that system. A minimal condition which a sound system should satisfy is consistency, meaning that no theorem contradicts another; another way of saying this is that no statement or formula and its negation are both derivable from the system. Also important for a formal system is completeness, meaning that everything true is also provable in the system. However, when the language of logic reaches a certain degree of expressiveness (say, second-order logic), completeness becomes impossible to achieve in principle.

In the case of formal logical systems, the theorems are often interpretable as expressing logical truths (tautologies, or statements that are always true), and it is in this way that such systems can be said to capture at least a part of logical truth and inference.

Formal logic encompasses a wide variety of logical systems. Various systems of logic we will discuss later can be captured in this framework, such as term logic, predicate logic and modal logic, and formal systems are indispensable in all branches of mathematical logic. The table of logic symbols describes various widely used notations in symbolic logic.

### Rival conceptions of logic

Logic arose (see below) from a concern with correctness of argumentation. The conception of logic as the study of argument is historically fundamental, and was how the founders of distinct traditions of logic, namely Aristotle, Mozi and Aksapada Gautama, conceived of logic. Modern logicians usually wish to ensure that logic studies just those arguments that arise from appropriately general forms of inference; so for example the Stanford Encyclopedia of Philosophy says of logic that it "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" (Hofweber 2004).

By contrast Immanuel Kant introduced an alternative idea as to what logic is. He argued that logic should be conceived as the science of judgment, an idea taken up in Gottlob Frege's logical and philosophical work, where thought (German: Gedanke) is substituted for judgment (German: Urteil). On this conception, the valid inferences of logic follow from the structural features of judgments or thoughts.

A third view of logic arises from the idea that logic is more fundamental than reason, and so that logic is the science of states of affairs (German: Sachverhalt) in general. Barry Smith locates Franz Brentano as the source for this idea, an idea he claims reaches its fullest development in the work of Adolf Reinach (Smith 1989). This view of logic appears radically distinct from the first; on this conception logic has no essential connection with argument, and the study of fallacies and paradoxes no longer appears essential to the discipline.

Occasionally one encounters a fourth view as to what logic is about: it is a purely formal manipulation of symbols according to some prescribed rules. This conception can be criticized on the grounds that the manipulation of just any formal system is usually not regarded as logic. Such accounts normally omit an explanation of what it is about certain formal systems that makes them systems of logic.

### History of logic

(see History of Logic)

While many cultures have employed intricate systems of reasoning, logic as an explicit analysis of the methods of reasoning received sustained development originally in three places: China in the fifth century B.C.E., Greece in the fourth century B.C.E., and India between the second century B.C.E. and the first century B.C.E..

The formally sophisticated treatment of modern logic apparently descends from the Greek tradition, although it is suggested that the pioneers of Boolean logic were likely aware of Indian logic. (Ganeri 2001) The Greek tradition itself comes from the transmission of Aristotelian logic and commentary upon it by Islamic philosophers to Medieval logicians. The traditions outside Europe did not survive into the modern era; in China, the tradition of scholarly investigation into logic was repressed by the Qin dynasty following the legalist philosophy of Han Feizi, in the Islamic world the rise of the Asharite school suppressed original work on logic.

However in India, innovations in the scholastic school, called Nyaya, continued into the early eighteenth century. It did not survive long into the colonial period. In the twentieth century, western philosophers like Stanislaw Schayer and Klaus Glashoff have tried to explore certain aspects of the Indian tradition of logic.

During the medieval period a greater emphasis was placed upon Aristotle's logic. During the later period of the medieval ages, logic became a main focus of philosophers, who would engage in critical logical analyses of philosophical arguments, and who developed sophisticated logical analyses and logical methods.

### Relation to other sciences

Logic is related to rationality and the structure of concepts, and so has a degree of overlap with psychology. Logic is generally understood to describe reasoning in a prescriptive manner (i.e. it describes how reasoning ought to take place), whereas psychology is descriptive, so the overlap is not so marked. Gottlob Frege, however, was adamant about anti-psychologism: that logic should be understood in a manner independent of the idiosyncrasies of how particular people might reason.

### Deductive and inductive reasoning

Originally, logic consisted only of deductive reasoning which concerns what follows universally from given premises. However, it is important to note that inductive reasoning has sometimes been included in the study of logic. Correspondingly, although some people have used the term "inductive validity," we must distinguish between deductive validity and inductive strength—from the point of view of deductive logic, all inductive inferences are, strictly speaking, invalid, so some term other than "validity" should be used for good or strong inductive inferences. An inference is deductively valid if and only if there is no possible situation in which all the premises are true and the conclusion false. The notion of deductive validity can be rigorously stated for systems of formal logic in terms of the well-understood notions of semantics. But for all inductive arguments, no matter how strong, it is possible for all the premises to be true and the conclusion nevertheless false. So inductive strength requires us to define a reliable generalization of some set of observations, or some criteria for drawing an inductive conclusion (e. g. "In the sample we examined, 40 percent had characteristic A and 60 percent had characteristic B, so we conclude that 40 percent of the entire population has characteristic A and 60 percent has characteristic B."). The task of providing this definition may be approached in various ways, some less formal than others; some of these definitions may use mathematical models of probability.

For the most part our discussion of logic here deals only with deductive logic.

## Topics in logic

Throughout history, there has been interest in distinguishing good from bad arguments, and so logic has been studied in some more or less familiar form. Aristotelian logic has principally been concerned with teaching good argument, and is still taught with that end today, while in mathematical logic and analytical philosophy much greater emphasis is placed on logic as an object of study in its own right, and so logic is studied at a more abstract level.

Consideration of the different types of logic explains that logic is not studied in a vacuum. While logic often seems to provide its own motivations, the subject usually develops best when the reason for the investigator's interest is made clear.

### Syllogistic logic

The Organon was Aristotle's body of work on logic, with the Prior Analytics constituting the first explicit work in formal logic, introducing the syllogistic. The parts of syllogistic, also known by the name term logic, were the analysis of the judgments into propositions consisting of two terms that are related by one of a fixed number of relations, and the expression of inferences by means of syllogisms that consisted of two propositions sharing a common term as premise, and a conclusion which was a proposition involving the two unrelated terms from the premises.

Aristotle's work was regarded in classical times and from medieval times in Europe and the Middle East as the very picture of a fully worked out system. It was not alone; the Stoics proposed a system of propositional logic that was studied by medieval logicians. Nor was the perfection of Aristotle's system undisputed; for example the problem of multiple generality was recognized in medieval times. Nonetheless, problems with syllogistic logic were not seen as being in need of revolutionary solutions.

Today, Aristotle's system is mostly seen as of historical value (though there is some current interest in extending term logics), regarded as made obsolete by the advent of sentential logic and the predicate calculus.

### Predicate logic

Logic as it is studied today is a very different subject to that studied before, and the principal difference is the innovation of predicate logic. Whereas Aristotelian syllogistic logic specified the forms that the relevant parts of the involved judgments took, predicate logic allows sentences to be analyzed into subject and argument in several different ways, thus allowing predicate logic to solve the problem of multiple generality that had perplexed medieval logicians. With predicate logic, for the first time, logicians were able to give an account of quantifiers (expressions such as all, some, and none) general enough to express all arguments occurring in natural language.

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

Frege's original system of predicate logic was not first-, but second-order. Second-order logic is most prominently defended (against the criticism of Willard Van Orman Quine and others) by George Boolos and Stewart Shapiro.

### Modal logic

In language, modality deals with the phenomenon that subparts of a sentence may have their semantics modified by special verbs or modal particles. For example, "We go to the games" can be modified to give "We should go to the games," and "We can go to the games" and perhaps "We will go to the games." More abstractly, we might say that modality affects the circumstances in which we take an assertion to be satisfied.

The logical study of modality dates back to Aristotle, who was concerned with the alethic modalities of necessity and possibility, which he observed to be dual in the sense of De Morgan duality. While the study of necessity and possibility remained important to philosophers, little logical innovation happened until the landmark investigations of Clarence Irving 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 discovered (contemporaneously with rivals) his theory of frame semantics which revolutionized the formal technology available to modal logicians and gave a new graph-theoretic way of looking at modality that has driven many applications in computational linguistics and computer science, such as dynamic logic.

### Deduction and reasoning

(see Deductive reasoning)

The motivation for the study of logic in ancient times was clear, as we have described: it is so that we may learn to distinguish good from bad arguments, and so become more effective in argument and oratory, and perhaps also, to become a better person.

This motivation is still alive, although it no longer necessarily takes center stage in the picture of logic; typically dialectical or inductive logic, along with an investigation of informal fallacies, will form much of a course in critical thinking, a course now given at many universities.

### Mathematical logic

(see Mathematical logic)

Mathematical logic really refers to two distinct areas of research: the first is the application of the techniques of formal logic to mathematics and mathematical reasoning, and the second, in the other direction, the application of mathematical techniques to the representation and analysis of formal logic.

The boldest attempt to apply logic to mathematics was undoubtedly the logicism pioneered by philosopher-logicians such as Gottlob Frege and Bertrand Russell with his colleague Alfred North Whitehead: the idea was that—contra Kant's assertion that mathematics is synthetic a priori—mathematical theories were logical tautologies and hence analytic, and the program was to show this by means to a reduction of mathematics to logic. The various attempts to carry this out met with a series of failures, 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.

Both the statement of Hilbert's Program and its refutation by Gödel depended upon their work establishing the second area of mathematical logic, the application of mathematics to logic in the form of proof theory. Despite the negative nature of the incompleteness theorems, Gödel's completeness theorem, a result in model theory and another application of mathematics to logic, can be understood as showing how close logicism came to being true: every rigorously defined mathematical theory can be exactly captured by a first-order logical theory; Frege's proof calculus is enough to describe the whole of mathematics, though not equivalent to it. Thus we see how complementary the two areas of mathematical logic have been.

If proof theory and model theory have been the foundation of mathematical logic, they have been but two of the four pillars of the subject. 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.

### Philosophical logic

(see Philosophical logic)

Philosophical logic deals with formal descriptions of natural language. Most philosophers assume that the bulk of "normal" proper reasoning can be captured by logic, if one can find the right method for translating ordinary language into that logic. Philosophical logic is essentially a continuation of the traditional discipline that was called "Logic" before it was supplanted by the invention of mathematical logic. Philosophical logic has a much greater concern with the connection between natural language and logic. As a result, philosophical logicians have contributed a great deal to the development of non-standard logics (e.g., free logics, tense logics) as well as various extensions of classical logic (e.g., modal logics), and non-standard semantics for such logics (e.g., Kripke's technique of supervaluations in the semantics of logic).

### Logic and computation

Logic cut to the heart of computer science as it emerged as a discipline: Alan Turing's work on the Entscheidungsproblem followed from Kurt Gödel's work on the incompleteness theorems, and the notion of a general purpose computer that came from this work was of fundamental importance to the designers of the computer machinery in the 1940s.

In the 1950s and 1960s, researchers predicted that when human knowledge could be expressed using logic with mathematical notation, it would be possible to create a machine that reasons, or artificial intelligence. This turned out to be more difficult than expected because of the complexity of human reasoning. In logic programming, a program consists of a set of axioms and rules. Logic programming systems such as Prolog compute the consequences of the axioms and rules in order to answer a query.

Today, logic is extensively applied in the fields of artificial intelligence, and computer science, and these fields provide a rich source of problems in formal logic. The ACM Computing Classification System in particular regards:

• Section F.3 on Logics and meanings of programs and F. 4 on Mathematical logic and formal languages as part of the theory of computer science: this work covers formal semantics of programming languages, as well as work of formal methods such as Hoare logic;
• Boolean logic as fundamental to computer hardware: particularly, the system's section B.2 on Arithmetic and logic structures;
• Many fundamental logical formalisms are essential to section I.2 on artificial intelligence, for example modal logic and default logic in Knowledge representation formalisms and methods, and Horn clauses in logic programming.

Furthermore, computers can be used as tools for logicians. For example, in symbolic logic and mathematical logic, proofs by humans can be computer-assisted. Using automated theorem proving the machines can find and check proofs, as well as work with proofs too lengthy to be written out by hand.

## Controversies in logic

Just as we have seen there is disagreement over what logic is about, so there is disagreement about what logical truths there are.

### Bivalence and the law of the excluded middle

The logics discussed above are all "bivalent" or "two-valued"; that is, they are to be understood as dividing all propositions into just two groups: those that are true and those that are false. Systems which reject bivalence are known as non-classical logics.

The law of the excluded middle states that every proposition is either true or false—there is no third or middle possibility. In addition, this view holds that no statement can be both true and false at the same time and in the same manner.

In the early twentieth century Jan Łukasiewicz investigated the extension of the traditional true/false values to include a third value, "possible," so inventing ternary logic, the first multi-valued logic.

Intuitionistic logic was proposed by L. E. J. Brouwer as the correct logic for reasoning about mathematics, based upon his rejection of the law of the excluded middle as part of his intuitionism. Brouwer rejected formalization in mathematics, but his student Arend Heyting studied intuitionistic logic formally, as did Gerhard Gentzen. Intuitionistic logic has come to be of great interest to computer scientists, as it is a constructive logic, and is hence a logic of what computers can do.

Modal logic is not truth conditional, and so it has often been proposed as a non-classical logic. However, modal logic is normally formalized with the principle of the excluded middle, and its relational semantics is bivalent, so this inclusion is disputable. On the other hand, modal logic can be used to encode non-classical logics, such as intuitionistic logic.

Logics such as fuzzy logic have since been devised with an infinite number of "degrees of truth," represented by a real number between 0 and 1. Bayesian probability can be interpreted as a system of logic where probability is the subjective truth value.

### Implication: strict or material?

It is easy to observe that the notion of implication formalized in classical logic does not comfortably translate into natural language by means of "if___ then...," due to a number of problems called the paradoxes of material implication.

Material implication holds that in any statement of the form "If P then Q ," the entire statement is false only if P (known as the antecedent)is true and Q (the consequent) is false. This means that if P is false, or Q is true, then the statement "If P then Q" is necessarily true. The paradoxes of material implication arise from this.

One class of paradoxes includes those that involve counterfactuals, such as "If the moon is made of green cheese, then 2+2=5"—a statement that is true by material implication since the antecedent is false. But many people find this to be puzzling or even false because natural language does not support the principle of explosion. Eliminating these classes of paradox led to David Lewis's formulation of strict implication, and to a more radically revisionist logics such as relevance logic and dialetheism.

A second class of paradoxes are those that involve redundant premises, falsely suggesting that we know the consequent because of the antecedent: thus "if that man gets elected, granny will die" is materially true if granny happens to be in the last stages of a terminal illness, regardless of the man's election prospects. Such sentences violate the Gricean maxim of relevance, and can be modeled by logics that reject the principle of monotonicity of entailment, such as relevance logic.

### Tolerating the impossible

Closely related to questions arising from the paradoxes of implication comes the radical suggestion that logic ought to tolerate inconsistency. Again, relevance logic and dialetheism are the most important approaches here, though the concerns are different; the key issue that classical logic and some of its rivals, such as intuitionistic logic have 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 proponent of dialetheism, has argued for paraconsistency on the striking grounds that there are in fact, true contradictions (Priest 2004).

### Is logic empirical?

What is the epistemological status of the laws of logic? What sort of arguments are appropriate for criticizing purported principles of logic? In an influential paper entitled Is logic empirical? Hilary Putnam, building on a suggestion of W.V.O. 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 by the same name by Sir 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.