 ## Online Encylopedia and Dictionary Research Site Online Encyclopedia Search    Online Encyclopedia Browse # Logic

(Redirected from Formal logic)

In ordinary language, logic (ancient Greek logice=sense/think) is the reasoning used to reach a conclusion from a set of assumptions. More formally, logic is the study of inference—the process whereby new assertions are produced from already established ones. As such, of particular concern in logic is the structure of inference—the formal relations between the newly produced assertions and the previously established ones, where "formal" means that the relations are independent of the assertions themselves. Just as important is the investigation of validity of inference, including various possible definitions of validity and practical conditions for its determination. It is thus seen that logic plays an important role in epistemology in that it provides a mechanism for extension of knowledge.

As a byproduct, logic provides prescriptions for reasoning, that is, how people—as well as other intelligent beings, machines, and systems—ought to reason. However, such prescriptions are not essential to logic itself; rather, they are an application. How people actually reason is usually studied in other fields, including cognitive psychology.

Traditionally, logic is studied as a branch of philosophy. Since the mid-1800s logic has been commonly studied in mathematics, and, even more recently, in computer science. As a science, logic investigates and classifies the structure of statements and arguments and devises schemata by which these are codified. The scope of logic can therefore be very large, including reasoning about probability and causality. Also studied in logic are the structure of fallacious arguments and paradoxes. The ancient Greeks divided dialectic into logic and rhetoric. Rhetoric, concerned with persuasive arguments, would currently be seen as contrasted with logic, in some sense; as is dialectic in most of its acquired meanings.

 Contents

## Scope of logic

As it has developed, many distinctions have been introduced into logic. These distinctions serve to help formalize different forms of logic as a science. Here are some of the more important distinctions.

### 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—the study of deriving a reliable generalization from observations—has sometimes been included in the study of logic. Correspondingly, we must distinguish between deductive validity and inductive validity. 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 well-understood notions of semantics. Inductive validity on the other hand requires us to define a reliable generalization of some set of observations. 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 deals only with deductive logic.

### Formal and informal logic

The study of logic is divided into formal and informal logic.

Formal logic (sometimes called "symbolic logic") attempts to capture the nature of logical truth and inference in formal systems, which consist of a formal language, a set of rules of derivation (often called "rules of inference"), and sometimes a set of axioms. The formal language consists of a (often small) set of discrete symbols, a syntax, and (often) a semantics, and expressions in this language are often called "formulas". The rules of derivation and potential axioms then operate with the language to specify a set of theorems, which are formulas that are either axioms or are derivable using the rules of derivation. In the case of formal logical systems, the theorems are often interpretable as expressing logical truths (tautologies), and in this way can such systems be said to capture at least a part of logical truth and inference. Formal logic encompasses a wide variety of logical systems. For instance, propositional logic and predicate logic are a kind of formal logic, as well as temporal logic, modal logic, Hoare logic, the calculus of constructions, etc. Higher-order logics are logical systems based on a hierarchy of types.

Informal logic is the study of logic as used in natural language arguments. Informal logic is complicated by the fact that it may be very hard to tease out the formal logical structure embedded in an argument. Informal logic is also more difficult because the semantics of natural language assertions is much more complicated than the semantics of formal logical systems, due to the presence of such phenomena as defeasibility.

Following are more specific discussions of some systems of logic. See also: list of 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 develops most healthily when the reason for our interest is made clear.

### Aristotelian logic

Main article:Aristotelian 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 judgements 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 recognised in medieval times. Nonetheless, problems with syllogistic 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 the predicate calculus.

### Predicate logic

Main article:Predicate logic

### Modal logic

Main article:Modal logic

### Dialectical logic

Main article:Dialectical logic

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 takes centre stage in the picture of logic; typically dialectical logic will form the heart of a course in critical thinking, a compulsory course at many universities, especially those that follow the American model.

### Mathematical logic

Main article: 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: the idea was that mathematical theories were logical tautologies, and the programme 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

Main article 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., supervaluation semantics).

### Logic and computation

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.

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.

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.

In computer science, Boolean algebra is the basis of hardware design, as well as much software design.

There are also various systems for reasoning about computer programs. Hoare logic is one of the earliest of such systems. Other systems are CSP, CCS, pi-calculus for reasoning about concurrent processes or mobile processes. There is interest in the idea of finding a logical calculus that naturally captures computability; the computability logic of Japaridze is an example of a recently embarked research programme in this direction.

## Controversies in Logic

It is by no means the case that logicians agree on what the principles of logic are

### Bivalence and the law of the excluded middle

The logics discussed above are all "bivalent" or "two-valued"; that is, the semantics for each of these languages will assign to every sentence either the value "True" or the value "False." Systems which do not always make this distinction are known as non-classical logics or non-Aristotelian logics.

In the early 20th 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 formalisation 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 formalised with the principle of the excluded middle, and its relational semantics is bivalent, so this inclusion is disputable. However, 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 formalised 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.

The first class of paradoxes are those that involve counterfactuals, such as "If the moon is made of green cheese, then 2+2=4", puzzling 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.

The second class of paradox are those that involve redundant premises, falsely suggesting that we know the succedent 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 modelled by logics that reject the principle of monotonicity , such as relevance logic.

### Is logic empirical?

Main article: Is logic empirical?

What is the epistemological status of the laws of logic? What sort of arguments are appropriate for criticising 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 that 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 the relationship between bivalence and realism .

Concepts of logic

Techniques and rules

Related Topics

## References

• G. Birkhoff and J. von Neumann, The Logic of Quantum Mechanics, vol 37, 1936.
• D. Finkelstein, Matter, Space and Logic, Boston Studies in the Philosophy of Science vol V, 1969
• W. Hodges: Logic. An introduction to elementary logic, Penguin Books, 2001
• W. Kneale and M. Kneale, The Development of Logic, Oxford University Press, 1988 (originally 1962)
• H. Putnam, Is Logic Empirical, Boston Studies in the Philosophy of Science vol V, 1969