Logic

Premises and conclusions are the basic parts of inferences or arguments and therefore play a central role in logic. In the case of a valid inference or a correct argument, the conclusion follows from the premises, or in other words, the premises support the conclusion.[6][35] For instance, the premises "Mars is red" and "Mars is a planet" support the conclusion "Mars is a red planet". It is generally accepted that premises and conclusions have to be truth-bearers.[6][35][lower-roman 1] This means that they have a truth value: they are either true or false. Thus contemporary philosophy generally sees them either as propositions or as sentences.[6] Propositions are the denotations of sentences and are usually understood as abstract objects.[36]

Propositional theories of premises and conclusions are often criticized because of the difficulties involved in specifying the identity criteria of abstract objects or because of naturalist considerations.[6] These objections are avoided by seeing premises and conclusions not as propositions but as sentences, i.e. as concrete linguistic objects like the symbols displayed on a page of a book. But this approach comes with new problems of its own: sentences are often context-dependent and ambiguous, meaning an argument's validity would not only depend on its parts but also on its context and on how it is interpreted.[6][37]

In earlier work, premises and conclusions were understood in psychological terms as thoughts or judgments, in an approach known as "psychologism". This position was heavily criticized around the turn of the 20th century.[6][38][39]

Premises and conclusions have internal structure. As propositions or sentences, they can be either simple or complex.[40][41] A complex proposition has other propositions as its constituents, which are linked to each other through propositional connectives like "and" or "if...then". Simple propositions, on the other hand, do not have propositional parts. But they can also be conceived as having an internal structure: they are made up of subpropositional parts, like singular terms and predicates.[35][40][41] For example, the simple proposition "Mars is red" can be formed by applying the predicate "red" to the singular term "Mars".[35] In contrast, the complex proposition "Mars is red and Venus is white" is made up of two simple propositions connected by the propositional connective "and".[35]

Whether a proposition is true depends, at least in part, on its constituents.[41] For complex propositions formed using truth-functional propositional connectives, their truth only depends on the truth values of their parts.[35] But this relation is more complicated in the case of simple propositions and their subpropositional parts. These subpropositional parts have meanings of their own, like referring to objects or classes of objects.[35][42][43] Whether the simple proposition they form is true depends on their relation to reality, i.e. what the objects they refer to are like. This topic is studied by theories of reference.[43]

In some cases, a simple or a complex proposition is true independently of the substantive meanings of its parts.[3][44] For example, the complex proposition "if Mars is red, then Mars is red" is true independent of whether its parts, i.e. the simple proposition "Mars is red", are true or false. In such cases, the truth is called a logical truth: a proposition is logically true if its truth depends only on the logical vocabulary used in it.[16][44] This means that it is true under all interpretations of its non-logical terms. In some modal logics, this notion can be understood equivalently as truth at all possible worlds.[16] Logical truth plays an important role in logic and some theorists even define logic as the study of logical truths.[5]

Truth tables can be used to show how logical connectives work or how the truth of complex propositions depends on their parts. They have a column for each input variable. Each row corresponds to one possible combination of the truth values these variables can take. The final columns present the truth values of the corresponding expressions as determined by the input values. For example, the expression "${\displaystyle p\land q}$" uses the logical connective ${\displaystyle \land }$ (and). It could be used to express a sentence like "yesterday was Sunday and the weather was good". It is only true if both of its input variables, ${\displaystyle p}$ ("yesterday was Sunday") and ${\displaystyle q}$ ("the weather was good"), are true. In all other cases, the expression as a whole is false. Other important logical connectives are ${\displaystyle \lor }$ (or), ${\displaystyle \to }$ (if...then), and ${\displaystyle \lnot }$ (not).[45][46] Truth tables can also be defined for more complex expressions that use several propositional connectives. For example, given the conditional proposition ${\displaystyle p\to q}$, one can form truth tables of its inverse (${\displaystyle \lnot p\to \lnot q}$), and its contraposition (${\displaystyle \lnot q\to \lnot p}$).[47]

Logic is commonly defined in terms of arguments or inferences as the study of their correctness.[3][6] An argument is a set of premises together with a conclusion.[48] An inference is the process of reasoning from these premises to the conclusion.[6] But these terms are often used interchangeably in logic. Arguments are correct or incorrect depending on whether their premises support their conclusion. Premises and conclusions, on the other hand, are true or false depending on whether they are in accord with reality. In formal logic, a sound argument is an argument that is both correct and has only true premises.[49] Sometimes a distinction is made between simple and complex arguments.[6] A complex argument is made up of a chain of simple arguments. These simple arguments constitute a chain because the conclusions of the earlier arguments are used as premises in the later arguments. For a complex argument to be successful, each link of the chain has to be successful.[6]

Argument terminology used in logic

Arguments and inferences are either are correct or incorrect. If they are correct then their premises support their conclusion. In the incorrect case, this support is missing. It can take different forms corresponding to the different types of reasoning.[5][29][50] The strongest form of support corresponds to deductive reasoning. But even arguments that are not deductively valid may still constitute good arguments because their premises offer non-deductive support to their conclusions. For such cases, the term ampliative or inductive reasoning is used.[5][29][50] Deductive arguments are associated with formal logic in contrast to the relation between ampliative arguments and informal logic.[18][27]

A deductively valid argument is one whose premises guarantee the truth of its conclusion.[7][15] For instance, the argument "Victoria is tall; Victoria has brown hair; therefore Victoria is tall and has brown hair" is deductively valid. For deductive validity, it does not matter whether the premises or the conclusion are actually true. So the argument "trees can speak the English language; therefore trees can speak a language" is valid because, if the premise were true, the conclusion would be true as well.

Alfred Tarski holds that deductive arguments have three essential features: (1) they are formal, i.e. they depend only on the form of the premises and the conclusion; (2) they are a priori, i.e. no sense experience is needed to determine whether they obtain; (3) they are modal, i.e. that they hold by logical necessity for the given propositions, independent of any other circumstances.[7]

Because of the first feature, the focus on formality, deductive inference is usually identified with rules of inference.[5] Rules of inference specify how the premises and the conclusion have to be structured for the inference to be valid. Arguments that do not follow any rule of inference are deductively invalid.[5][51] The modus ponens is a prominent rule of inference. It has the form "p; if p, then q; therefore q".[51] Knowing that it has just rained (${\displaystyle p}$) and that after rain the streets are wet (${\displaystyle p\to q}$), one can use modus ponens to deduce that the streets are wet (${\displaystyle q}$).

The third feature can be expressed by stating that deductively valid inferences are truth-preserving: it is impossible for the premises to be true and the conclusion to be false.[5][29][52] Because of this feature, it is often asserted that deductive inferences are uninformative since the conclusion cannot arrive at new information not already present in the premises.[5][28] But this point is not always accepted since it would mean, for example, that most of mathematics is uninformative. A different characterization distinguishes between surface and depth information.[5][53][54] On this view, deductive inferences are uninformative on the depth level but can be highly informative on the surface level, as may be the case for various mathematical proofs.[5][53][54]

Ampliative inferences, on the other hand, are informative even on the depth level. They are more interesting in this sense since the thinker may acquire substantive information from them and thereby learn something genuinely new.[5][29][30] But this feature comes with a certain cost: the premises support the conclusion in the sense that they make its truth more likely but they do not ensure its truth.[5][29][30] This means that the conclusion of an ampliative argument may be false even though all its premises are true. This characteristic is closely related to non-monotonicity and defeasibility: it may be necessary to retract an earlier conclusion upon receiving new information or in the light of new inferences drawn.[3][5][52] Ampliative reasoning is of central importance since many arguments found in everyday discourse and the sciences are ampliative. Ampliative arguments are not automatically incorrect. Instead, they just follow different standards of correctness. An important aspect of most ampliative arguments is that the support they provide for their conclusion comes in degrees.[50][52][55] In this sense, the line between correct and incorrect arguments is blurry in some cases, as when the premises offer weak but non-negligible support. This contrasts with deductive arguments, which are either valid or invalid with nothing in-between.[50][52][55]

The terminology used to categorize ampliative arguments is inconsistent. Some authors use the term "induction" to cover all forms of non-deductive arguments.[50][55][56] But in a more narrow sense, induction is only one type of ampliative argument besides abductive arguments.[52] Some authors also allow conductive arguments as one more type.[18][57] In this narrow sense, induction is often defined as a form of statistical generalization.[58][59] In this case, the premises of an inductive argument are many individual observations that all show a certain pattern. The conclusion then is a general law that this pattern always obtains.[60] In this sense, one may infer that "all elephants are gray" based on one's past observations of the color of elephants.[52] A closely related form of inductive inference has as its conclusion not a general law but one more specific instance, as when it is inferred that an elephant one has not seen yet is also gray.[60] Some theorists stipulate that inductive inferences rest only on statistical considerations in order to distinguish them from abductive inference.[52]

Abductive inference may or may not take statistical observations into consideration. In either case, the premises offer support for the conclusion because the conclusion is the best explanation of why the premises are true.[52][61][lower-roman 2] In this sense, abduction is also called the inference to the best explanation.[62] For example, given the premise that there is a plate with breadcrumbs in the kitchen in the early morning, one may infer the conclusion that one's house-mate had a midnight snack and was too tired to clean the table. This conclusion is justified because it is the best explanation of the current state of the kitchen.[52] For abduction, it is not sufficient that the conclusion explains the premises. For example, the conclusion that a burglar broke into the house last night, got hungry on the job, and had a midnight snack, would also explain the state of the kitchen. But this conclusion is not justified because it is not the best or most likely explanation.[52][61][62]

Not all arguments live up to the standards of correct reasoning. When they do not, they are usually referred to as fallacies. Their central aspect is not that their conclusion is false but that there is some flaw with the reasoning leading to this conclusion.[63] So the argument "it is sunny today; therefore spiders have eight legs" is fallacious even though the conclusion is true. Some theorists give a more restrictive definition of fallacies by additionally requiring that they appear to be correct.[24][64] This way, genuine fallacies can be distinguished from mere mistakes of reasoning due to carelessness. This explains why people tend to commit fallacies: because they have an alluring element that seduces people into committing and accepting them.[64] However, this reference to appearances is controversial because it belongs to the field of psychology, not logic, and because appearances may be different for different people.[64][65]

Young America's dilemma: Shall I be wise and great, or rich and powerful? (poster from 1901) This is an example of a false Dilemma: an informal fallacy using a disjunctive premise that excludes viable alternatives.

Fallacies are usually divided into formal and informal fallacies.[31][32][33] For formal fallacies, the source of the error is found in the form of the argument. For example, denying the antecedent is one type of formal fallacy, as in "if Othello is a bachelor, then he is male; Othello is not a bachelor; therefore Othello is not male".[63][66] But most fallacies fall into the category of informal fallacies, of which a great variety is discussed in the academic literature. The source of their error is usually found in the content or the context of the argument.[24][32][64] Informal fallacies are sometimes categorized as fallacies of ambiguity, fallacies of presumption, or fallacies of relevance. For fallacies of ambiguity, the ambiguity and vagueness of natural language are responsible for their flaw, as in "feathers are light; what is light cannot be dark; therefore feathers cannot be dark".[25][34][33] Fallacies of presumption have a wrong or unjustified premise but may be valid otherwise.[33][67] In the case of fallacies of relevance, the premises do not support the conclusion because they are not relevant to it.[33][34]

The main focus of most logicians is to investigate the criteria according to which an argument is correct or incorrect. A fallacy is committed if these criteria are violated. In the case of formal logic, they are known as rules of inference.[5] They constitute definitory rules, which determine whether a certain inference is correct or which inferences are allowed. Definitory rules contrast with strategic rules.[5][68][69] Strategic rules specify which inferential moves are necessary in order to reach a given conclusion based on a certain set of premises.[5][68][69] This distinction does not just apply to logic but also to various games as well. In chess, for example, the definitory rules dictate that bishops may only move diagonally while the strategic rules describe how the allowed moves may be used to win a game, for example, by controlling the center and by defending one's king.[5][68][69] A third type of rules concerns empirical descriptive rules. They belong to the field of psychology and generalize how people actually draw inferences.[5] It has been argued that logicians should give more emphasis to strategic rules since they are highly relevant for effective reasoning.[5]

A formal system of logic consists of a language, a proof system, and a semantics.[70] The term "a logic" is often used a countable noun to refer to a particular formal system of logic.[4][5][17] Starting in the 20th century, many new formal systems have been proposed.[lower-roman 3][4][5][17]

A formal language consists of an alphabet and syntactic rules. The alphabet is the set of basic symbols used in expressions. The syntactic rules determine how these symbols may be arranged to result in well-formed formulas.[71][72][73] For instance, the syntactic rules of propositional logic determine that "${\displaystyle P\land Q}$" is a well-formed formula but "${\displaystyle PQ\land \land \land }$" is not.

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 ${\displaystyle P\land Q}$ follows from the premises ${\displaystyle P}$ and ${\displaystyle 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.[70][74][75] Proof systems are closely linked to philosophical work which characterizes logic as the study of valid inference.[4]

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 ${\displaystyle P\land Q}$ the denotation "true" whenever ${\displaystyle P}$ and ${\displaystyle Q}$ are true. Entailment is a semantic relation which holds between formulas when the first cannot be true without the second being true as well.[76][77] Semantics is closely tied to the philosophical characterization of logic as the study of logical truth.[5]

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.[78][79][80]

The study of properties of formal systems is called metalogic. Other important metalogical properties include consistency, decidability, and expressive power.[81]

Aristotelian logic encompasses a great variety of topics, including metaphysical theses about ontological categories and problems of scientific explanation.[82][83][92] But in a more narrow sense, it refers to term logic or syllogistics. A syllogism is a certain form of argument involving three propositions: two premises and a conclusion. Each proposition has three essential parts: a subject, a predicate, and a copula connecting the subject to the predicate.[82][83][92] For example, the proposition "Socrates is wise" is made up of the subject "Socrates", the predicate "wise", and the copula "is".[83] The subject and the predicate are the terms of the proposition. In this sense, Aristotelian logic does not contain complex propositions made up of various simple propositions.[82] It differs in this aspect from propositional logic, in which any two propositions can be linked using a logical connective like "and" to form a new complex proposition.[93]

The square of opposition is often used to visualize the relations between the four basic categorical propositions in Aristotelian logic. It shows, for example, that the propositions "All S are P" and "Some S are not P" are contradictory, meaning that one of them has to be true while the other is false.

Aristotelian logic differs from predicate logic in that the subject is either universal, particular, indefinite, or singular.[82][92][94] For example, the term "all humans" is a universal subject in the proposition "all humans are mortal". A similar proposition could be formed by replacing it with the particular term "some humans", the indefinite term "a human", or the singular term "Socrates".[82][92][94] In predicate logic, on the other hand, universal and particular propositions would be expressed by using a quantifier and two predicates.[82] Another important difference is that Aristotelian logic only includes predicates for simple properties of entities, but lacks predicates corresponding to relations between entities.[95] The predicate can be linked to the subject in two ways: either by affirming it or by denying it.[82][83] For example, the proposition "Socrates is not a cat" involves the denial of the predicate "cat" to the subject "Socrates". Using different combinations of subjects and predicates, a great variety of propositions and syllogisms can be formed. Syllogisms are characterized by the fact that the premises are linked to each other and to the conclusion by sharing one predicate in each case.[82][96][97] Thus, these three propositions contain three predicates, referred to as major term, minor term, and middle term.[83][96][97] The central aspect of Aristotelian logic involves classifying all possible syllogisms into valid and invalid arguments according to how the propositions are formed.[82][83][96] For example, the syllogism "all men are mortal; Socrates is a man; therefore Socrates is mortal" is valid. The syllogism "all cats are mortal; Socrates is mortal; therefore Socrates is a cat", on the other hand, is invalid.

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 ${\displaystyle P}$ and ${\displaystyle Q}$ as the complex formula ${\displaystyle P\land 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.[98] 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.[99]

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

First-order logic includes the same propositional connectives as propositional logic but differs from it because it articulates the internal structure of propositions. This happens through devices such as singular terms, which refer to particular objects, predicates, which refer to properties and relations, and quantifiers, which treat notions like "some" and "all".[35][40][43] For example, to express the proposition "this raven is black", one may use the predicate ${\displaystyle B}$ for the property "black" and the singular term ${\displaystyle r}$ referring to the raven to form the expression ${\displaystyle B(r)}$. To express that some objects are black, the existential quantifier ${\displaystyle \exists }$ is combined with the variable ${\displaystyle x}$ to form the proposition ${\displaystyle \exists xB(x)}$. First-order logic contains various rules of inference that determine how expressions articulated this way can form valid arguments, for example, that one may infer ${\displaystyle \exists xB(x)}$ from ${\displaystyle B(r)}$.[100][101]

Gottlob Frege developed the first fully axiomatic system of first-order logic.[102]

The development of first-order logic is usually attributed to Gottlob Frege, who is also credited as one of the founders of analytic philosophy. However, the formulation of first-order logic most often used today is found in Principles of Mathematical Logic by David Hilbert and Wilhelm Ackermann in 1928.[103] The analytical generality of first-order 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.[104]

Many extended logics take the form of modal logic by introducing modal operators. Modal logics were originally developed to represent statements about necessity and possibility. For instance the modal formula ${\displaystyle \Diamond P}$ can be read as "possibly ${\displaystyle P}$" while ${\displaystyle \Box P}$ can be read as "necessarily ${\displaystyle P}$". Modal logics can be used to represent different phenomena depending on what flavor of necessity and possibility is under consideration. When ${\displaystyle \Box }$ is used to represent epistemic necessity, ${\displaystyle \Box P}$ states that ${\displaystyle P}$ is known. When ${\displaystyle \Box }$ is used to represent deontic necessity, ${\displaystyle \Box P}$ states that ${\displaystyle 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.[105][106][107] Other fields such as computer science and set theory have applied the relational semantics for modal logic beyond its original conceptual motivation, using it to provide insight into patterns including the set-theoretic multiverse and transition systems in computation.[107][108]

Higher-order logics extend classical logic not by using modal operators but by introducing new forms of quantification.[6][109][110] Quantifiers correspond to terms like "all" or "some". In classical first-order logic, quantifiers are only applied to individuals. The formula "${\displaystyle \exists x(Apple(x)\land Sweet(x))}$" (some apples are sweet) is an example of the existential quantifier "${\displaystyle \exists }$" applied to the individual variable "${\displaystyle x}$". In higher-order logics, quantification is also allowed over predicates. This increases its expressive power. For example, to express the idea that Mary and John share some qualities, one could use the formula "${\displaystyle \exists Q(Q(mary)\land Q(john))}$". In this case, the existential quantifier is applied to the predicate variable "${\displaystyle Q}$".[6][109][111] The added expressive power is especially useful for mathematics since it allows for more succinct formulations of mathematical theories.[6] But it has various drawbacks in regard to its meta-logical properties and ontological implications, which is why first-order logic is still much more widely used.[6][110]

A great variety of deviant logics have been proposed. One major 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.[112][113][114]

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.[115][116][117] 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.[118]

Paraconsistent logics are logical systems that can deal with contradictions. They are formulated to avoid the principle of explosion: for them, it is not the case that anything follows from a contradiction.[88][119][120] They are often motivated by dialetheism, the view that contradictions are real or that reality itself is contradictory. Graham Priest is an important contemporary proponent of this position and similar views have been ascribed to Georg Wilhelm Friedrich Hegel.[119][120][121]

The pragmatic or dialogical approach to informal logic sees arguments as speech acts and not merely as a set of premises together with a conclusion.[64][90][91] As speech acts, they occur in a certain context, like a dialogue, which affects the standards of right and wrong arguments.[24][91] A prominent version by Douglas N. Walton understands a dialogue as a game between two players.[64] The initial position of each player is characterized by the propositions to which they are committed and the conclusion they intend to prove. Dialogues are games of persuasion: each player has the goal of convincing the opponent of their own conclusion.[24] This is achieved by making arguments: arguments are the moves of the game.[24][91] They affect to which propositions the players are committed. A winning move is a successful argument that takes the opponent's commitments as premises and shows how one's own conclusion follows from them.[24] This is usually not possible straight away. For this reason, it is normally necessary to formulate a sequence of arguments as intermediary steps, each of which brings the opponent a little closer to one's intended conclusion. Besides these positive arguments leading one closer to victory, there are also negative arguments preventing the opponent's victory by denying their conclusion.[24] Whether an argument is correct depends on whether it promotes the progress of the dialogue. Fallacies, on the other hand, are violations of the standards of proper argumentative rules.[64][65] These standards also depend on the type of dialogue. For example, the standards governing the scientific discourse differ from the standards in business negiotiations.[91]

The epistemic approach to informal logic, on the other hand, focuses on the epistemic role of arguments.[64][90] It is based on the idea that arguments aim to increase our knowledge. They achieve this by linking justified beliefs to beliefs that are not yet justified.[122] Correct arguments succeed at expanding knowledge while fallacies are epistemic failures: they do not justify the belief in their conclusion.[64][90] In this sense, logical normativity consists in epistemic success or rationality.[122] For example, the fallacy of begging the question is a fallacy because it fails to provide independent justification for its conclusion, even though it is deductively valid.[34][122] The Bayesian approach is one example of an epistemic approach.[64] Central to Bayesianism is not just whether the agent believes something but the degree to which they believe it, the so-called credence. Degrees of belief are understood as subjective probabilities in the believed proposition, i.e. as how certain the agent is that the proposition is true.[123][124][125] On this view, reasoning can be interpreted as a process of changing one's credences, often in reaction to new incoming information.[64] Correct reasoning, and the arguments it is based on, follows the laws of probability, for example, the principle of conditionalization. Bad or irrational reasoning, on the other hand, violates these laws.[90][124][126]

Philosophy of logic is the philosophical discipline studying the scope and nature of logic.[3][6] It investigates many presuppositions implicit in logic, like how to define its fundamental concepts or the metaphysical assumptions associated with them.[17] It is also concerned with how to classify the different logical systems and considers the ontological commitments they incur.[3] Philosophical logic is one important area within the philosophy of logic. It studies the application of logical methods to philosophical problems in fields like metaphysics, ethics, and epistemology.[17][87] This application usually happens in the form of extended or deviant logical systems.[5][89]

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

Bertrand Russell made various significant contributions to mathematical logic.[130]

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.[131] 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.[132] 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.[133]

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. They include Cantor's theorem, the status of the Axiom of Choice, the question of the independence of the continuum hypothesis, and the modern debate on large cardinal axioms.[134][135]

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.[136] Today recursion theory is mostly concerned with the more refined problem of complexity classes and the classification of degrees of unsolvability.[137]

Conjunction (AND) is one of the basic operations of boolean logic. It can be electronically implemented in several ways, for example, by using two transistors.

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.[138][139][140] Computer scientists also apply concepts from logic to problems in computing and vice versa. The works of Claude Shannon were influential in this regard. He showed how boolean logic can be used to understand and implement computer circuits.[141][142] The interaction between the two disciplines can be seen, for example, in how modern artificial intelligence builds on logicians' work in argumentation theory, while automated theorem proving can assist logicians in finding and checking proofs.[143] In logic programming languages such as Prolog, a program computes the consequences of logical axioms and rules to answer a query.[144]

Formal semantics, a subfield of both linguistics and philosophy, 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.[145][146][147]