Logic

What is Logic?

Logic is the study of reasoning. It is concerned mainly with inference, but also with entailment, causality, consequence, induction, deduction, truth, falsity, belief, fallacies, paradoxes, probabilities, analysis, tense, modality, necessity, sufficiency, possibility, identity, vagueness, existence, description, justification, tolerance, obligation, permission, relevance, assertion, judgment, soundness, validity, contradiction, provability, and argumentation.

Logic is topic-neutral, meaning we don’t let our biases about subject matter influence the way we look at the structure of arguments. Logic focuses on the form of arguments rather than their content. Here’s an introductory video. In fact it is the first video in an amazing playlist of 83 videos on logic.

One of the central questions explored in the study of logic is:

Does the conclusion follow from the premises?

The phrase “follow from” can have different interpretations, depending on the inference mode you are working under:

Deduction is the one most often formally studied in philosophy, mathematics, and computer science. The others are still important, of course.

But hang on though! Each of these descriptions used the word truth. But what is truth? And how do we reason our way from premises to true conclusions? Answers to those questions depend on the system of logic we are using. We’ll see many systems of logic later in these notes.

A Pretest

Have some fun! Take this logic pre-test.

Basic Concepts

A rigorous study of any field benefits from an understanding of its basic concepts and terminology.

Sentences

Since logic requires a rigorous study of the forms of arguments, it helps to not get bogged down in long, confusing, and often ambiguous prose, so we want our statements, or sentences, to have a very compact form. We can achieve this by using single letters for our subjects, objects, and predicates, and fancy symbols for our conjunctions and prepositions and other grammatical words. Let’s jump right into some examples (with details to follow):

Now here’s a summary of common logical notation:

It takes an enormous amount of practice to translate sentences of English (or other natural language) into sentences of logic. Such translations are not unique, nor are they always even exact, as natural language is fluid and frequently imprecise.

Terms and Formulas

Most systems of logic distinguish between terms and formulas.

• Terms represent objects. They can be written directly like $r$ for Romeo, $j$ for Juliet, $k$ for the king, $2$ for the number two, or made by applying functions to other terms. For example, if $d$ is the function “daughter of” then $dk$ denotes the daughter of the king; if $t$ was the country Türkiye and $c$ was the function “capital of” then $ct$ is the capital of Türkiye. If $p$ were the plus function, then $p\,3\,5$ represents the sum of $3$ and $5$. Also, the binder $\iota$ and the probability operator $pr$ can create complex terms from formulas.
• Formulas are expressions that evaluate to truth values. The simplest formulas are propositions such as $T$ (truth), $F$ (falsity), $R$ (it’s raining). More complex formulas are made by applying predicates (e.g., $L$ for “likes” and $W$ for “is wet”) as in $Lrj$ (Romeo likes Juliet), and $Ws$ (the sidewalk is wet) to terms and formulas. The binders $\forall$ and $\exists$, as well as operators such as $\neg$, $\land$, $\lor$, $\supset$, $\equiv$, $=$, $\Box$, $\lozenge$, $\textbf{P}$, $\textbf{F}$, $\textbf{G}$, $\textbf{H}$, $\mathscr{K}$, $\mathscr{B}$, and so on also create formulas. See above for examples.

Parentheses

Be sure to use parentheses when needed. For example, $Pfb$ is an application of the two-argument predicate $P$ to $f$ and $b$, for instance “Farah pressed the button”; but in $P(fb)$, $P$ is a one-argument predicate and $f$ is a function, as in “The friend of Billie is popular.”

For operators, $\neg$ has the highest precedence, then $\land$, then $\lor$ then $\supset$ then $\equiv$. All operators associate to the right, so $P \supset Q \supset R$ means $P \supset (Q \supset R)$ and does not mean $(P \supset Q) \supset R$.

The . is sugar for a left parenthesis whose implicit made is as far to the right as possible. So $\exists x. Px \land Q$ means $\exists x. (Px \land Q)$ and does not mean $(\exists x. Px) \land Q$. .

You can also just use parentheses everywhere. No shame in that!

Be careful not to confuse terms and formulas. For example, note $\iota x. Px$ is a term, but $\exists x. Px$ is a formula.

Notation conventions

Note how we’ve always used lowercase letters in the term world (objects and functions) and uppercase letters in the formula world (predicates and propositions). This is the way.

If you were a minimalist, you might notice:

• An object is a just a function with zero arguments, so all terms are functions.
• A formula is just a term (and hence a function) with a truth value type.
• A predicate is just a function that returns a term with a truth value type.
• A proposition is a just a predicate with zero arguments, and is thus also a function.
• Logical operators are just predicates, which are functions.
• So everything is a function!

That’s cool from a foundational point of view, but as humans, we like to work with objects, functions, terms, propositions, predicates, and formulae as distinct concepts.

Variables

A variable stands for something unspecified.

Every variable occurrence is either bound or free. It’s bound if it is within the scope of a $\forall$, $\exists$, or $\iota$ that binds it or is the binding occurrence itself, and free otherwise. This requires examples! In the following, the free variable occurrences are underlined:

• $\underline{x} = \underline{y}$
• $\forall x. x = \underline{y}$
• $\forall y. \underline{x} = y$
• $\forall x. x = x$
• $\forall x. x > 3 \lor x < 5$
• ($\forall x. x > 3) \lor \underline{x} < 5$

The names of bound variables are rather arbitrary: $\forall x. x = x$ and $\forall y. y = y$ are meant to represent the same sentence.

A term or formula with a free variable is called an open term or open formula. A term or formula with no free variables is called closed. Open formulas are general statements and closed statements are specific statements. When useful to do so, we will indicate that a term or formula has certain free variables by writing $A[x]$ or $A[x,y]$ (read: “there are free occurrences of $x$ in $A$” and “there are free occurrences of $x$ and $y$ in $A$”, respectively).

To increase specificity, we may substitute for the free variables in a term or formula. The notation for substituting $t$ for free occurrences of $x$ in formula $A$ such that no free variable in $t$ becomes bound (i.e., is captured) is $A[x \mapsto t]$ or $A[t/x]$.

Capturing is explicitly disallowed because a capture changes the meaning of the formula. For example, in the formula $\exists x. x \neq y$, the substitution $[y \mapsto x]$ mustn’t replace $y$ with $x$, since you’d end up with $\exists x. x \neq x$, which means something completely different! To properly substitute in such cases, you must rename bound variable occurrences in $A$ to avoid capturing free variables in $t$, like so:

Where we can safely substitute $t$ for $x$ in $A$ (without any need for renaming), we say $t$ is free for $x$ in $A$.

Judgments

A formula is just a string of symbols: on its own it asserts nothing. To actually claim something, we need a judgment.

The first judgment we’ll see is that a formula is true. We write it:

which is read “$A$ is true.” This looks trivial, but the distinction matters: $A$ is just a formula; $A\;\textsf{true}$ is an assertion about that formula. It is easy to get confused.

A hypothetical judgment is one that asserts something relative to assumptions:

where each of the $J$s are simple judgments. We often use $\mathcal{H}$ for a list of hypotheses so:

is the assertion that “$A$ is true, given that every assertion in $\mathcal{H}$ holds.” The symbol $\vdash$ is called turnstile. Since $A\;\textsf{true}$ is (for now) our only judgment, people often shortcut the notation and abbreviate $A\;\textsf{true}$ as just $A$, so you will see entire judgments shortened to $\mathcal{H} \vdash A$ or $\vdash A$ or even (yikes) just $A$.

AMBIGUOUS NOTATION ALERT

Once we start dropping $\textsf{true}$, the symbol $A$ on its own becomes confusing: sometimes it’s the formula (pure syntax), and sometimes shorthand for the judgment $A\;\textsf{true}$.

If the context is such that you are dealing with judgments rather than formulas, you will have to mentally understand that the $\textsf{true}$ symbols are really present, just not visible. BE CAREFUL.

There is no shame at all, however, in being pedantic and never dropping the $\textsf{true}$s.

What other judgments are there?

In beginning logic, the truth assertion $A\;\textsf{true}$ is pretty much the only one we’ll see. But we’ll see more, especially in computer science. Examples:

$t\;\textsf{type}$

$t$ is a type

$e\!:t$

$e$ has type $t$

$e \Downarrow v$

$e$ evaluates to $v$

$e \Uparrow$

The evaluation of $e$ diverges

$e\;\to\;e'$

$e$ reduces in one step to $e'$

$s\;\mapsto\;s'$

State $s$ transitions in one step to $s'$

$p\;\textsf{halts}$

Program $p$ halts

When you are done reading these notes, you will be ready to return to the deeper philosophical questions about the difference between formulas and judgments, and will then enjoy reading the transcript of the three lectures by Per Martin-Löf.

Arguments

A logical argument is a sequence of judgments, each of which is either a hypothesis or follows from earlier judgments in the sequence via inference rules. The set of inference rules depends on the particular system of logic you are working in. In other words, a particular system will tell you which judgments you are allowed to state and how to infer from existing judgments to new judgments. An argument is valid if all of its judgments are derived by following the rules of the system.

Arguments are often written graphically, with premises above the line and conclusion below. Example:

If a particular logic system allows you to make a hypothetical judgment $J$ from no prior judgments, $J$ is called an axiom of that system. If a non-hypothetical judgment $J$ is an axiom or can be inferred from other judgments according to the rules of the system, then $J$ is said to be a theorem of that system. Because theorems are non-hypothetical judgments you will often see the notation:

to mean $A$ is a theorem, or equivalently, $A$ is provable, $A$ is derivable from the inference rules. etc.

Truth

A system of logic needs to do at least two things. It needs to define:

• The truth values for each formula
• The judgments you allowed to infer

The first part, truth, is a semantic notion, concerning the relationship between formulas and the world (or model) they describe. Truth values vary according to system: they can be exact (e.g., true, false, both, neither) or a “degree of belief,” or whether something is “justified,” or “achievable,” or “knowable.”

The second part, proof, is a syntactic notion. You blindly follow the rules, deriving new judgments as you go, without consulting the model. You have to hope that whoever designed the inference rules did so in a way that the rules line up with model, so you only derive truthy things as theorems.

Some of the truth values of a system are known as its designated values. These are the truthy ones. Formulas that always have a designated value in a model, no matter what their internal variables are assigned to, are valid. If $A$ is valid, we write;

The notations look similar, but they are different things.

Truth and proof are related, but absolutely not the same thing.

Kinds of Logic

How can there be many different kinds of logic? Well, there could be different ways to understand truth, as we saw above. There can also be different ways to reason, with some inferences acceptable in some contexts but not others. Some systems are deliberately small (in that they cannot capture all forms of reasoning), to simply serve as a stepping stone for more complex forms of reasoning.

Here are some kinds of logics. The list is incomplete. The kinds are also overlapping.

Bivalent Logic

A bivalent system has exactly two truth values, usually called true and false. Contrast this with a non-bivalent system has more than two truth values, perhaps three, four, eight, or an infinite number (e.g. a value $\in 0.0\ldots 1.0$).

Often a bivalent system will identify false with $0$ and true with $1$, as this will scale up nicely to three-valued logics where the third value gets $\frac{1}{2}$, and to infinitely-valued, or fuzzy, logics that admit any value between $0.0$ and $1.0$ inclusive. Bivalency is about complete certainty of truth or falsity with nothing in between.

Bivalent logics are super simple to work with, even if they don’t fully capture the nuances of the real world.

For example, bivalent logical negation is trivial: $\neg \textbf{true} = \textbf{false}$ and $\neg \textbf{false} = \textbf{true}$.

Also, bivalency gives rise to dualities with respect to negation that sometimes facilitate reasoning. The duals are related to each other as $\neg\square A \equiv \blacksquare\neg A$ or as $ \neg(A\circ B) = \neg A\bullet \neg B$.

Propositional Logic

Technically, a proposition is a predicate with no arguments, such as “It‘s raining”. (We saw this in the example above, where we represented this with $R$.)

There is a type of logic where we simplify things so much that we ignore subjects, predicates, and objects, where all information is rolled up into single, atomic, nondecomposable sentences. Then propositions can be things like “Pigs fly”, “I am late”, “The moon is square”, and “The baby wants to sleep”. Propositional Logic is a system of reasoning about these things without decomposing them. The traditional operators are:

Note: The $\land$ and $\lor$ operators are meant to be material, not causal. They cannot distinguish the sentence “I called her and found out about the problem” from “I found out about the problem and called her.”

Propositional logic is too weak to deal with everything we need to reason about. But the simplicity buys us so much! Besides being easy to learn and understand, a propositional logic system has many desirable technical properties, many of which we’ll see in these notes.

Syllogistic Logic

Systems of logic featuring syllogisms were studied thousands of years ago; they include reasoning about “all” and “some”, but do not allow general propositions nor connectives like “and” and “or”. Traditionally, only the following eight kinds of statements were considered (capital letters are classes, small letters are instances):

For historical use only

Syllogistic logic has been completely superseded by first-order predicate logic.

Predicate Logic

A predicate logic adds objects, functions on objects, predicates, descriptions, and quantifiers (such as $\exists$ and $\forall$) to propositional logic. A first-order logic allows quantification over objects only; In a second-order logic you can quantify over first-order predicates. You can go on forever with these orders. At $\omega$-order logic, you essentially have type theory.

For each of the eight examples of syllogistic forms above, we will write the corresponding formula in first-order logic. Then we’ll try to come up with formulae in first-order logic that cannot be expressed in syllogistic logic.

Here is an example of a second-order logic formula. Do you recognize it? It’s the principle of mathematical induction on natural numbers, where $s$ is the successor function (that is, $sn = n+1$):

$$\forall P.((P0 \land \forall n.(Pn \supset P(sn))) \supset \forall n.Pn)$$

Classical Logic

Classical Logic is probably the most widely used logic. It has several properties:

• Bivalency: Only truth values are true and false
• Excluded middle: $\frac{}{A \lor \neg A}$
• Non-contradiction: $\frac{}{\neg (A \land \neg A)}$
• Monotonicity: If $\frac{A}{B}$ then $\frac{A \quad C}{B}$ (you can always add assumptions!)
• Commutativity of conjunction: $A \land B \;\equiv\; B \land A$
• Dualities with respect to negation everywhere ($\land$-$\lor$, $\forall$-$\exists$)
• Explosiveness: $\frac{A \quad \neg A}{B}$ (from a contradiction, anything follows)

The term “classical” here does mean old or ancient. This was not the logic of the Ancient Greeks, the Ancient Chinese, or the Ancient anyone else. Classical Logic dates from the late 1800s. It’s relatively new. However, it is strongly influenced by the work of a few ancient philosophers.

Some classical logics are entirely truth-functional, which means we can give the meanings of the logical operators purely in terms of the meanings of their components. For example, in a bivalent, propositional, classical logic, we can give the following truth table:

Sometimes these are shortened to one table per operator.

Classical logic is quite useful, but there are quite a few things that folks can rightly quibble over, hence the interest in non-classical logics.

Intuitionistic Logic

In intuitionistic logic (often identified with constructive logic), we are not concerned with the truth of a statement as much as we are about its justification. Everything we assert in intuitionistic logic is something justifiable, constructively. So $A$ means “$A$ is provable” and $\neg A$ means “$A$ is refutable” (i.e., it is provable that no proof of $A$ exists—in other words, assuming $A$ allows you to derive falsity). Therefore:

• You can only prove $A \lor \neg A$ by proving $A$ or refuting $A$. The inability to do neither means you can’t say anything about $A$ at all!
• You can only prove $\exists x. P$ by demonstrating an object for which $P$ is true. You cannot prove it by saying “it just can’t be the case that $\neg P$ holds for every $x$.” Not good enough.
• You can derive $\neg \neg A$ from $A$, but you cannot derive $A$ from $\neg \neg A$. The former says “if I can prove $A$, then I can refute that $A$ is refutable” but the latter is saying “if there’s no proof that $A$ is not provable then $A$ must be provable.” That’s not good enough: you have to demonstrate a direct constructed proof of $A$.

Therefore:

Intuitionistic logic is not truth-functional.

Our familiar logical connectives are read quite differently:

• $A \land B$ means “I can construct a proof of $A$ and a proof of $B$”
• $A \lor B$ means “I can construct a proof of $A$ or a proof of $B$”
• $A \supset B$ means “From a proof of $A$, I can construct a proof of $B$”
• $\forall x.\, P$ means “for every $x$, I can construct a proof of $P$”
• $\exists x.\, P$ means “I can find an $x$ for which I can construct a proof of $P$”

Constructive logic codifies the principles of mathematical reasoning as it is actually practiced. In mathematics a proposition may be judged to be true exactly when it has a proof, and may be judged to be false exactly when it has a refutation. Because there are, and always will be, unsolved problems, we cannot expect in general that a proposition is either true or false, for in most cases we have neither a proof nor a refutation of it. Constructive logic may be described as logic as if people matter, as distinct from classical logic, which may be described as the logic of the mind of god. From a constructive viewpoint the judgment “φ true” means that “there is a proof of φ.” —Robert Harper, Practical Foundations of Programming Languages, Chapter 30.

Intuitionistic logic turns out to be ideal for computer science.

Learn more at Wikipedia and the SEP. And if you prefer a video introduction, here’s Attic Philosophy’s:

Many-Valued Logics

Sometimes bivalent systems are just too restrictive. We run into sentences like “This sentence is false” which appear to be both true and false, or sentences like “This sentence is true” which appear to be neither true nor false. Approaches to handling these seemingly self-contradictory or seemingly meaningless statements include adding to a bivalent system either (1) a third truth value for “other” or (2) two new truth values for “both true and false” and “neither true nor false”.

In general, a many-valued logic is one with three or more truth-values. Many such systems exist. We can have $3$, $4$, or even infinitely many truth values.

Don’t miss the Attic Philosophy videos on this topic

See the Logic playlist, videos 44–51, for Mark Jago’s presentations of many-valued logics, paradoxes, dialetheism, paraconsistent logics, and Curry’s Paradox.

In the case of a three-valued system, the third value is just “other” ($O$). Let’s construct the truth matrices for a truth-functional 3-valued logic. Using the laws from the section on propositional logic we can fill in almost everything:

We have two reasonable options:

• If we treat $A \supset B$ as $\neg A \lor B$, then $O \supset O = O$. (This is the Strong Kleene, or $K_3$ interpretation.)
• If we extend the law $x \supset x = T$, then $O \supset O = T$. (This is the Łukasiewicz, or $Ł_3$ interpretation.)

But now here’s something interesting with multi-valued logics. What does it mean for a sentence to be valid? Does it have to be (1) always true or (2) just never false? Look at these tautologies from classical logic:

Under the always-true interpretation of validity, none of those sentences are valid in $K_3$, and only self-implication is valid in $Ł_3$. Under the never-false interpretation, all are valid under all interpretations.

The Logic of Paradoxes ($LP$) is a three-valued logic that uses the $K_3$ truth matrices but the never-false interpretation of validity. (When folks talk about $K_3$ as a complete system they assume the always-true interpretation.) $LP$ is an example of a paraconsistent logic, which we’ll turn to now.

Resources on Many-Valued Logics

The SEP and Wikipedia have quite a few articles on this topic. Notable ones include Many-valued Logics, Four-valued logics, The Liar Paradox, and The Logic of Conditionals.

Paraconsistent Logic

Classical logic, and even several non-classical logics, are explosive, meaning that from a contradiction, anything and everything follows (in Latin: ex falso quodlibet, or ECQ), $ \frac{A \quad \neg A}{B}$. Here’s how it is shown in a classical logic:

A paraconsistent logic is any logic that is nonexplosive. That’s the definition. Contradictions do not collapse everything into triviality. The argument above is invalid in a paraconsistent logic. There are a few real-life situations where adopting paraconsistency is quite useful.

The big idea in paraconsistent logic is not to abolish contradictions but to contain them so the logic is not explosive. Approaches to doing so include (1) adding new truth values to essentially allow statements that are both true and false, (2) requiring premisses and conclusions to be somehow relevant to each other, and (3) keeping $A$ and $\neg A$ in separate contexts, much like two people arguing different sides of a sentence.

One well-known paraconsistent logic is $LP$ that we saw above. How is this not explosive? It’s because validity here is about falsity avoidance, so both $T$ and $O$ are its designated values (its “truthy values”). So $\frac{A\quad\neg A}{B}$ cannot be a valid argument: take $A$ to have the value $\textsf{other}$ and therefore $\neg A$ also has the value $\textsf{other}$. You cannot derive any $B$ whatsoever, since a false $B$ must never be come from designated premises!

The SEP article on Paraconsistent Logic has quite a few examples. Read the article for an in-depth look, or this video for a short introduction:

In a 3-valued logic, you get paraconsistency when the third value has “both true and false” vibes rather than “neither true nor false” vibes. So the natural next question we might ask: what if we had a logic with four values, embracing both and neither?

Catuṣkoṭi

The Catuṣkoṭi is also known as the “Four Corners.” Propositions take on four values :

• Being
• Not Being
• Being and Not Being
• Neither Being nor Not Being

Find out more at Wikipedia and the SEP.

This 16-minute by Graham Priest is really good:

The Catuṣkoṭi is sometimes pictured as follows in logic, with the left column being True and the bottom row being False:

Here’s a modern take on the Catuṣkoṭi. Consider these four possible responses to a person asking you what they think is a yes-no question:

Here’s why it works:

• While Yeah no has a variety of meanings, one common usage is as a hedge, or social deflection, indicating both agreement and disagreement, as in when told you did a great job, you reply “Yeah no, I had a lot of help”
• The term Mu(無) is used to indicate that the question itself is invalid or unanswerable, effectively unasking it or saying “neither yes nor no” as in: “Is your answer to this question ‘no’?”

And don’t miss this article by Graham Priest.

Relevance Logic

Sometimes the principle of explosion pops up because of irrelevant implications, as in these completely true statements of classical logic:

• If the moon is six inches in diameter, then $2 + 2 = 4$.
• If the moon is six inches in diameter, then $2 + 2 = 5$.
• If the moon is six inches in diameter, then the moon is seven inches in diameter.

A relevance logic is a paraconsistent logic that rejects the explosion by requires the antecedent and consequent to be related to each other, usually by requiring both to share some common content (like a variable or a predicate), though there are many different ways to encode relevance.

Read about Relevance Logic in the SEP.

Discussive Logic

A discussive logic is a paraconsistent logic that allows contradictions to exist in separate contexts. It is based on the idea that two people can discuss the same topic and have different opinions about it, and both can be right in their own context. You can consider it a third “family” of paraconsistent logics (the other two being many-valued logics with a “both true and false” option and relevance logics).

We’ll not say much here, but refer you to the SEP.

Non-monotonic Logic

A non-monotonic logic rejects monotonicity. If a logic is monotonic, then adding new information can change the set of known facts, causing previously known truths to become falsehoods. These kind of logics are good for cases where you have to retract previous knowledge when new facts are known, as in:

• default reasoning
• abductive reasoning (infer the most likely cause)
• reasoning about knowledge (I used to not know this, now I do)
• belief revision

See the SEP article on non-monotonic logic.

Free Logic

Descriptions can be tricky. What if no object satisfies the description?

Russell regarded $P(\iota x.Ax)$ as an abbreviation for $\exists x.((\forall y.(Ay \equiv y=x)) \land Px)$. But this means the statement is false unless there is a unique object satisfying the description $A$ and that has the property $P$.

A free logic allows the description of terms that do not denote anything. Read about Free Logic in the SEP.

Fuzzy Logic

A fuzzy logic is one in which facts have a numeric truth value between $0$ and $1$, inclusive. It is a generalization of many-valued logics to an infinite number of truth values. It is useful for statements like “$X$ is tall” or “$X$ is an adult” or “The bike is new.” where truth is thought of as a matter of degree.

Do not confuse fuzzy logic with paraconsistent logic.

Do not confuse fuzzy logic with probability theory.

Read about Fuzzy Logic in the SEP.

Modal Logic

Modal Logic deals with modalities, which qualify statements somehow. There are many different kinds of modalities, giving rise to different kinds of logics. Each can be based on classical or non-classical logics, and use numeric truth values, too.

See the SEP article on modal logic.

Alethic Logic (Necessity and Possibility)

The basic alethic modal operators are defined as:

In classical modal logic, the two operators are duals:

• $\Box A \equiv \neg \lozenge \neg A$
• $\lozenge A \equiv \neg \Box \neg A$
• $\neg \Box A \equiv \lozenge \neg A$
• $\neg \lozenge A \equiv \Box \neg A$

Deontic Logic (Obligation and Permission)

The basic deontic operators are defined as:

Epistemic Logic (Knowledge)

In epistemic logic we have:

Doxastic Logic (Belief)

In doxastic logic we have:

You may sometimes see the epistemic and the doxastic distinguished in the following context. Let $\Gamma = \exists g. G g$, i.e., there exists a $g$ such that $g$ is a god, or “(at least one) god exists.” Then:

• $\mathscr{K}_x\,\Gamma \land \mathscr{B}_x\,\Gamma$ means $x$ is a gnostic theist
• $\mathscr{K}_x\,\Gamma \land \neg \mathscr{B}_x\,\Gamma$ means $x$ is a gnostic atheist
• $\neg \mathscr{K}_x\,\Gamma \land \mathscr{B}_x\,\Gamma$ means $x$ is an agnostic theist
• $\neg \mathscr{K}_x\,\Gamma \land \neg \mathscr{B}_x\,\Gamma$ means $x$ is a agnostic atheist

Temporal Logic

Temporal logic deals with the modalities of time.

Dynamic Logic

Dynamic Logic brings events into the picture:

Temporal vs. Dynamic Logic

Temporal logic [is] the modal logic of choice for reasoning about concurrent systems with its aspects of synchronization, interference, independence, deadlock, livelock, fairness, etc. These concerns of concurrency would appear to be less central to linguistics, philosophy, and artificial intelligence, the areas in which dynamic logic is most often encountered nowadays. — Wikipedia

Formal Logic

In logic we are not so much concerned with the absolute truth or falsity of premises themselves, but rather with the form of arguments. We can deal with “forms” using a formal systems. Formal systems manipulate formulas.

A formal system (or calculus) is a purely syntactic mechanism used to mechanically generate formulas. It consists of a formal language (alphabet and grammar) and a set of inference rules, and operates entirely without regard to meaning or truth.

A logical system, sometimes called a formal logic, pairs a formal system with a semantics (or model). A logical system has both the syntactic machinery of proof ($\vdash$) and the semantic machinery of truth ($\vDash$), which we want to ultimately try to connect.

To define a logical system we need three parts:

In more detail: A syntax gives a rigorous, formal specification of exactly what is and what is not a formula. A semantics assigns truth values to each formula, usually via reference to a model of some sort. We need only describe the semantic mappings—we don’t show how to compute them step-by-step. The inference rules are what we apply algorithmically (i.e., mechanistically, typographically, symbolically) to judgments to derive new judgments. A formula $A$ for which the non-hypothetical judgment $\vdash A\;\textsf{true}$ is so derivable is called a theorem. Inference rule application is purely syntactic: it never consults the semantics!

That last statement is important.

Inference rules operate on judgments mechanistically, independent of their semantic interpretation.

Following are three examples of logical systems.

A Formalization of Classical Propositional Logic

We begin with the syntax:

This means that, for example:

    p
    (¬(p′′′ ∧ q) ∨ ¬¬p)
    (r ⊃ p′)

are formulas, but

    ¬≡pp∧))′∧¬q∨(F′′

is not. Neither, by the way is

    p ∧ q

since the syntax above requires parentheses around all formulae formed with binary operators. Look again, closely!

Wait, what? Parentheses are...required?

In this formal syntax, yes they are. That said, you are free to write another formal syntax to capture operator precedence if you like, or you can allow for an informal representation of formulas in which precedence is assumed. That’s what we’ll do from now on.

A semantics assigns truth values to each formula. Because variables are permitted, a semantics must to take into account the truth values of variables before computing the truth values of formulas. That is, while we may be able to assign a truth value of false to $p \land \neg p$, the truth value of $p \supset q$ depends on the previously assigned values of $p$ and $q$. We call a mapping of variables to truth values an interpretation and require semantic definitions to be relative to an interpretation. Here is a semantic definition for classical propositional logic:

Don’t mix syntax and semantics

In particular, note that $T$ is a syntactic element, a formula, just a symbol; while true is from the world of semantics.

There are quite a few different ways to represent inference rules. There are two styles of presenting them: (1) the Hilbert-style, which does not use any hypothetical judgments and separates axioms from inference rules, and (2) the Gentzen-style, which is all about hypothetical judgments. Gentzen-style is much easier for to understand and work with, and the only one we’ll be using here. Recall that hypothetical judgments are of the form:

$A_1\;\textsf{true}, ..., A_n\;\textsf{true} \vdash B\;\textsf{true}$

but, as mentioned above, since the only kind of judgment we have is that a formula is true, we can drop the $\textsf{true}$ and just write:

$A_1, ..., A_n \vdash B$

and keep in mind that is really a judgment meaning “$B$ given assumptions $A_1, ..., A_n$.” One set of inference rules for classical propositional logic is:

Latin Names

Let’s get classically educated! Impress your friends with these Latin terms:

• $T$ = Verum (sometimes written $\top$)
• $F$ = Falsum (sometimes written $\bot$)
• IMPL-ELIM = Modus Ponens (MP)
• NEG-INTRO = Reductio ad absurdum (RAA)
• FALSE-ELIM = Ex falso quodlibet (EFQ)

Also not Latin, but worth knowing: IMPL-INTRO is also called “Conditional Proof” (which kind of mirrors the funny name “Indirect Proof”)

If $\mathcal{H}$ is empty in $\mathcal{H} \vdash A$, we say $A$ is a theorem and write $\vdash A$. The sequence of inferences producing a theorem is a proof of that theorem. The goal is to get to something that does not rely on any assumptions. The theorems of a formal logic are exactly those formulas we can reach through the rules.

Finding proofs is a bit of an art form when humans do it themselves, but a very worthy endeavour to undertake to sharpen your logic skills! For complex tasks, computer programs called mechanical proof assistants or automatic theorem provers exist. These programs can systematically apply inference rules to derive theorems. The good ones are really efficient at finding the proofs, that is, they do much better than a brute-force search through all possible inferences. As with AI coding tools, you can run proofs with the human-in-charge, program helps mode; or give the prover full automation permission.

To find proofs on your own, a graphical technique, such as Fitch-style Natural Deduction is powerful. Watch Attic Philosophy’s video #11, video #12, and video #72 in the Logic playlist for a great tutorial on doing proofs with this technique. It works for propositional and first-order logic. Some automated theorem provers use this mechanism internally as well!

You can find additional information on this technique at Wikipedia and Stanford Encyclopedia of Philosophy. We’ll offer just a simple example, a proof of the theorem $\vdash p \land (p \supset q) \supset (p \land q)$:

Derived Rules

The set of inference rules defining a logical system can be extended with derived rules which are those that can be proven using the existing rules. These make things much more convenient for a human doing proofs (if you’re a programmer, think of writing new procedures and functions).

Examples of derived rules that you can prove for classical propositional logic include modus tollens (MT), disjunctive syllogism, the “law” of excluded middle (EM), and double negation elimination (DNE) and a few others:

$$ \frac{\mathcal{H} \vdash A \supset B \quad\;\; \mathcal{H} \vdash \neg B}{\mathcal{H} \vdash \neg A}\;{\tiny \textrm{MT}} $$ $$ \frac{\mathcal{H} \vdash \neg\neg A}{\mathcal{H} \vdash A}\;{\tiny \textrm{DNE}} $$ $$ \frac{}{\mathcal{H} \vdash A \lor \neg A}\;{\tiny \textrm{EM}} $$ $$ \frac{\mathcal{H} \vdash A \lor B \quad\;\; \mathcal{H} \vdash \neg A}{\mathcal{H} \vdash B}\;{\tiny \textrm{DISJ-SYLL}} $$ $$ \frac{\mathcal{H} \vdash A \supset B \quad\;\; \mathcal{H} \vdash B \supset C}{\mathcal{H} \vdash A \supset C}\;{\tiny \textrm{IMPL-TRANS}} $$ $$ \frac{\mathcal{H}\vdash A \land B \supset C}{\mathcal{H}\vdash A \supset (B \supset C)}\;{\tiny \textrm{CURRY}} $$ $$ \frac{\mathcal{H}\vdash A \supset (B \supset C)}{\mathcal{H}\vdash A \land B \supset C}\;{\tiny \textrm{UNCURRY}} $$

Here is how we derive modus tollens:

We are going to show exactly how to derive the other derived rules.

Yet another reminder: theoremhood is syntactic, not semantic

Theorems are statements that can be derived using the rules of inference, regardless of their truth in any particular model. Proving a theorem is mechanical and syntactic. Truth comes from the semantics. Proof and truth are distinct concepts. We will connect them in our section on metalogic, below.

Formalizing Intuitionistic Propositional Logic

Surprise: you get Intuitionistic Propositional Logic by taking Classical Propositional Logic and simply removing the inference rule INDIRECT-PROOF.

That’s it!

That one simple change is all you need. It makes it impossible to derive excluded middle and double negation elimination and other rules that intuitionists do not accept. It’s rather interesting to show that for most of the classical rules that don’t exist in intuitionistic logic (those that require indirect proof to show), there is a corresponding rule that is intuitionistically (and classically) valid:

Formalizing Classical First-Order Logic

Starting with the syntax:

Parentheses can be removed as long as precedence is respected.

The semantics for first-order logic is significantly more involved than for propositional logic (it requires a domain of discourse and an interpretation of constants and function symbols as objects/functions over that domain), so we’ll leave those details for later.

However, the inference rules are a modest, concise extension of what we’ve already seen.

For the history of how first-order logic came to be the workhorse of mathematics and semantics, see this really cool SEP article.

Formalizing Higher-Order Logic

There are many higher-order logics, each with different features and expressive power. In most of these systems, the core idea is that every term has a type, and so higher order logics are sometimes called type theories. We’ll therefore defer discussion of these logics to our notes on Type Theory.

Formalizing Modal Logics

For alethic modal logic, which add the operators $\Box$ and $\lozenge$ to predicate logic, there are quite a few versions, based on the axioms and inference rules they add to the underlying logic. Here are some examples:

• System K, the weakest form of modal logic, adds the following to an underlying logic:
  • From $\Box(A \supset B)$ infer $\Box A \supset \Box B$
  • If $A$ is a theorem of the underlying logic, infer $\Box A$
• System T is System K plus
  • From $\Box A$ infer $A$
• S4 is System T plus
  • From $\Box A$ infer $\Box \Box A$
• S5 is System T plus
  • From $\lozenge A$ infer $\Box \lozenge A$

Properties of Formulae

We’re interested ultimately in valid reasoning—what follows from what—so let’s define some terms:

Satisfiability

If formula $A$ is true under some interpretation $\varphi$ we write $\vDash_{\varphi}A$ and say $\varphi$ satisfies $A$, or that $A$ is satisfiable.

Validity

If formula $A$ is true under all allowable interpretations we write $\vDash A$ and say $A$ is a tautology, or that $A$ is valid.

Entailment

If formula $A$ is true under all allowable interpretations in which formula $B$ is true, we write $B \vDash A$ and say $B$ entails $A$. Entailment is central to reasoning; if our knowledge base contains $B$ and we know that $B$ entails $A$, we know, then, that $A$ is true. Entailment is a purely semantic relation; the syntactic, proof-theoretic analogue $B \vdash A$ is called derivability.

By allowable interpretations we mean the interpretations that are permitted by the rules and constraints of the logical system we are working within.

In practice, you might hear people use the term “valid” rather loosely, but try to keep in mind the exact definition of this term.

More terms! A formula is a:

• Tautology if always true (true under all interpretations, same as valid)
• Contingency if sometimes true (true under some but not all interpretations)
• Contradiction if never true (true under no interpretations, same as unsatisfiable)

Metalogic

The definition of truth in a system is generally just stated in precise natural language, or with semantic functions (as in our example above). The derivation of theorems, however, is a purely mechanical process. We would like to know how well, in a logistic system, theorem derivation (proof) correlates with truth (keeping in mind the notion of truth varies between systems).

Soundness

A system is sound iff every theorem is valid, e.g., if $\vdash A$ then $\vDash A$.

Completeness

A system is complete iff every valid formula is a theorem, e.g., if $\vDash A$ then $\vdash A$.

Consistency

A system is consistent iff not every formula is a theorem. (This is known as Post-consistency, named after the logician Emil Post. Another definition, known as semantic consistency, requires that there exists at least one allowable interpretation under which all theorems are simultaneously true. These notions coincide for many mainstream logical systems.)

Decidability

A system is decidable iff there exists an (always-terminating) algorithm to determine whether or not a given formula is a theorem.

The reasoning about logistic systems themselves is called metalogic.

Recall Practice

Here are some questions useful for your spaced repetition learning. Many of the answers are not found on this page. Some will have popped up in lecture. Others will require you to do your own research.

1. Logic is the study of ________________.
   reasoning
2. What is the difference between deduction and induction? In particular how are they in some sense opposites of each other?
   Deduction goes from the general to the specific (and hence always gives a valid conclusion when the premises are true); induction goes from the specific to the general (and is therefore not guaranteed to give you a valid conclusion).
3. What is abduction?
   Drawing conclusions from strong evidence.
4. What is the difference between $=$ and $\equiv$?
   $x = y$ means that $x$ and $y$ refer to the same object, while $A \equiv B$ means that the two formulas $A$ and $B$ have the same truth value.
5. What is an equivalent formula of $A \supset B$, in terms of $\lor$?
   $\neg A \lor B$
6. What is an equivalent formula of $A \supset B$, in terms of $\land$?
   $\neg (A \land \neg B)$
7. Describe two ways to represent the object “The president of Mexico” in common logic notation, one with the description operator and the other with a function.
   $\iota p. P m p$, where $m$ is Mexico and $Pxy$ means “the president of $x$ is $y$.”
   
   $pm$ where $p$ is the function “president of” and $m$ is Mexico.
8. How do you represent the formula “Juliet once believed that Romeo might someday forever live in Canada”?
   $\mathbf{P}(\mathscr{B}_j\lozenge\mathbf{F}\mathbf{G}(Lrc))$, where $j$ is Juliet, $r$ is Romeo, $c$ is Canada, and $Lxy$ means $x$ lives in $y$.
9. Give the formula $A \lor B \land C \equiv D \supset E$ in its fully-parenthesized form.
   $((A \lor (B \land C)) \equiv (D \supset E))$
10. Give the formula $A \land \forall x. Px \supset \neg Qxy$ in its fully-parenthesized form.
    $(A \land (\forall x. (Px \supset \neg Qxy)))$
11. How to we diagram the inference that judgment $C$ follows from $A$ and $B$?
    $\dfrac{A \;\;\;\; B}{C}$
12. What’s the difference between a formula and a judgment?
    A formula is a piece of syntax; it asserts nothing on its own. A judgment is an act of assertion — a claim about a formula (or other object), such as that it is true.
13. What is the primary judgment used in pure logic, and how is it written?
    $A\;\textsf{true}$, read “$A$ is true.”
14. What is the symbol $\vdash$ called?
    Turnstile.
15. What does it mean for an argument to be valid?
    Every judgment in the sequence is either a hypothesis or follows from earlier judgments by a rule of inference.
16. What is a bivalent logic?
    A logic in which every formula has one of two truth values (generally $T$ or $F$).
17. What is a proposition?
    A predicate of zero arguments. As such, it can be considered a formula on its own, and importantly, it is atomic (nondecomposable).
18. What is propositional logic good for, if anything?
    It is too weak to be useful for much really, but its simplicity (1) makes it a good introductory logic for learners, and (2) is an example of a system that is both sound and complete.
19. What is the study of syllogisms relegated to these days?
    The history of logic, since first-order predicate logic encompasses all syllogistic forms and much more.
20. The principle of mathematical induction is an formula of ________________-order predicate logic.
    Second
21. What characterizes classical logic? Try to list all six features.
    (1) Bivalence, (2) excluded middle, (3) non-contradiction, (4) monotonicity of entailment, (5) commutativity of conjunction, (6) dualities of conjunction/disjunction and of universal/existential quantification.
22. What is intuitionistic logic most concerned with?
    Proof, rather than truth.
23. What does paraconsistent logic study?
    Logics that can handle contradictions without collapsing into triviality.
24. What is the difference between paraconsistent logic and relevance logic?
    Relevance logic is a kind of paraconsistent logic that prevents explosion by ensuring that the premises are relevant to the conclusion.
25. Why is paraconsistent logic interesting?
    Humans seem to get by just fine with contradictions.
26. What are the four corners of the Catuṣkoṭi?
    Being, Not Being, Being and Not Being, Neither Being nor Not Being.
27. What is a free logic and why might a computer scientist care?
    A free logic is one that does not require that all terms refer to objects. Computer scientists may find ways to deal with that horrible null thing.
28. How is fuzzy logic different from probability theory?
    Fuzzy logic deals with degrees of truth, while probability theory deals with likelihoods.
29. What is an alethic logic concerned with and what are its basic operators?
    Alethic logic is concerned with necessity and possibility. Its basic operators are $\Box$ and $\lozenge$.
30. What is a deontic logic concerned with and what are its basic operators?
    Deontic logic is concerned with obligation and permission. Its basic operators are $\mathscr{O}$ and $\mathscr{P}$.
31. What is an epistemic logic concerned with and what are its basic operators?
    Epistemic logic is concerned with knowledge. Its basic operators are $\mathscr{K}$ and $\mathscr{K}_x$.
32. What is a doxastic logic concerned with and what are its basic operators?
    Doxastic logic is concerned with belief. Its basic operators are $\mathscr{B}$ and $\mathscr{B}_x$.
33. In dynamic logic, how do we denote that after event $e$ occurs, $A$ must be true? How do we denote that after $e$ occurs, $A$ might be true?
    We write $[e]A$ and $\langle e \rangle A$ respectively.
34. What are the three parts of a definition of a formal logical system?
    Syntax, semantics, inference rules.
35. What is an interpretation in formal logic, and why are they needed?
    An interpretation is a mapping of variables to truth values. They are needed because the truth value of a formula depends on the truth values of its variables.
36. What do we call a formula $A$ for which $\vdash A$ holds?
    A theorem.
37. What do we call a formula $A$ for which $\vDash A$ holds?
    A tautology (or a valid formula.)
38. How are validity and satisfiability related?
    If something is valid then it is satisfiable, but not the other way around. (Similarly, if something is unsatisfiable, then it is invalid, but not the other way around.)
39. Give an example of a valid statement of (classical) prepositional logic.
    $p \lor \neg p$
40. Give an example of a invalid statement of (classical) prepositional logic.
    $p \land \neg p$
41. Give an example of a satisfiable statement of (classical) prepositional logic that is neither valid nor invalid.
    $p \supset \neg p$
42. What is a tautology? A contingency? A contradiction?
    A tautology is a formula that is valid (true under all interpretations). A contingency is a formula that is true under some but not all interpretations. A contradiction is a formula that is unsatisfiable (true under no interpretations).
43. What is a theorem in formal logic?
    A formula that is an axiom or that is derived from axioms via inference rules.
44. What does it mean for a logical system to be sound?
    Every theorem is true.
45. What does it mean for a logical system to be complete?
    Every true formula is a theorem.
46. What does it mean for a logical system to be consistent?
    Post-consistency is: There exists a formula that is not a theorem. (There are other kinds of consistencies, but the high-level intent is that two theorems have contradictory truth values.)
47. What does it mean for a logical system to be decidable?
    There exists an algorithm (always-terminating effective procedure) to determine whether a given formula is a theorem.
48. What do we call the field that studies properties of logical systems, such as soundness, completeness, consistency, and decidability?
    Metalogic.

Summary