Logic is the study of reasoning. It deals primarily with inference, but also 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, validity, contradiction, provability, and argumentation.
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, including, but not limited to:
Have some fun! Take this logic pre-test.
In order to understand the form of arguments and not get bogged down in long, confusing, and often ambiguous text, we usually write statements in a very compact form. We often use common abbreviations such as the following:
Form | Meaning | Technical Term |
---|---|---|
$T$ | True | Truth |
$F$ | False | Falsity |
$\neg A$ | Not $A$ | Negation |
$A \wedge B$ | $A$ and $B$ | Conjunction |
$A \vee B$ | $A$ or $B$, or both | Disjunction |
$A \supset B$ | It is not the case that $A$ is true and $B$ is false (i.e., whenever $A$ is true, $B$ is true) | Material Implication |
$A \equiv B$ | $A$ and $B$ are either both true or both false | Material Equivalence |
$A \rightarrow B$ | If $A$, then $B$ (non-truth-functional) | Conditional |
$\forall x. A$ | For every $x$, $A$ | Universal quantification |
$\exists x. A$ | There exists an $x$ such that $A$ | Existential quantification |
$\iota x. A$ | The $x$ such that $A$ | Description |
$x = y$ | $x$ and $y$ are the same object | Equality |
$\Box A$ | In all possible worlds, $A$ | Necessity |
$\lozenge A$ | In some possible world, $A$ | Possibility |
$\mathbf{P} A$ | It was (at least once) the case that $A$ | Past |
$\mathbf{F} A$ | It will (at least at some point) be the case that $A$ | Future |
$\mathbf{H} A$ | It was always the case that $A$ | Always has been |
$\mathbf{G} A$ | It will forever be the case that $A$ | Always going to be |
$\mathscr{O} A$ | $A$ must (morally) be done | Obligation |
$\mathscr{P} A$ | $A$ may (morally) be done | Permission |
$\mathscr{K}_x A$ | Agent $x$ knows $A$ | Knowledge |
$\mathscr{B}_x A$ | Agent $x$ believes $A$ | Belief |
$|A|$ | Truth value of $A$ (in 0.0 ... 1.0) | Numerical Truth Value |
$pr(A)$ | Probability of $A$ being true | Probability |
$pr(A|B)$ | Probability of $A$ being true given that $B$ is true | Conditional Probability |
$E(\sigma)$ | The expected value of doing $\sigma$ | Expectation |
It takes quite a bit of practice to translate English (or other natural language) sentences into logical notation. In fact, the translation might not always be exact; natural language is pretty fluid (see, for example, The SEP article on Conditionals for the many readings of “if...then”). We’ll just give examples, rather than rules.
Engilsh | Logic | Breakdown |
---|---|---|
Juliet is Italian | $\mathit{Italian(Juliet)}$ | — |
$Ij$ | ||
Romeo likes Juliet | $\mathit{Likes(Romeo,Juliet)}$ | |
$Lrj$ | ||
Romeo likes himself | $Lrr$ | Romeo likes Romeo |
Romeo likes the King’s daughter | $Lr(\iota x.Dkx)$ | Romeo likes
the person x such that
the daughter of the king is x |
All apples are fruits | $\forall x.(Ax \supset Fx)$ | For every x
if x is an apple
x is a fruit |
Some apples are green | $\exists x.(Ax \wedge Gx)$ | There exists an x such that
x is an apple AND x is green |
All snakes are animals | $\forall x.(Sx \supset Ax)$ | For every thing x
if x is a snake
x is an animal |
$\neg \exists x.(Sx \wedge \neg Ax)$ | It is NOT the case that
there exists an x such that
x is a snake AND x is not an animal |
|
Some snakes are poisonous | $\exists x.(Sx \wedge Px)$ | There exists an x such that
x is a snake AND x is poisonous |
$\neg \forall x.(Sx \supset \neg Px)$ | It is NOT the case that
for every x
if x is a snake
then x is non-poisonous |
|
Alice sees everybody | $\forall p. Sap$ | For every (person) p
Alice sees p |
$\neg \exists p.\neg Sap$ | It is NOT the case that
there exists a (person) p such that
Alice does not see p |
|
Alice sees somebody | $\exists p.Sap$ | There exists a (person) p such that
Alice sees p |
$\neg \forall p. \neg Sap$ | It is NOT the case that
for every (person) p
Alice does not see p |
|
Alice sees nobody | $\neg \exists p.Sap$ | It is NOT the case that
there exists a (person) p such that
Alice sees p |
$\forall p. \neg Sap$ | For every (person) p
it is NOT the case that
Alice sees p |
|
Juliet doesn’t like French people | $ \neg\exists p.(Fp \wedge Ljp)$ | It is NOT the case that
there exists a (person) p such that
p is French AND Juliet likes p |
$\forall p.(Fp \supset \neg Ljp)$ | For every (person) p
if p is French
It is NOT the case that
Juliet likes p |
|
Juliet likes all Italians | $\forall p.(Ip \supset Ljp)$ | For every (person) p
if p is Italian
Juliet likes p |
Juliet likes all Italians except Romeo | $\forall p.(Ip \supset (Ljp \equiv \neg (p=r)))$ | For every (person) p
if p is Italian
Juliet likes p IF AND ONLY IF p is not Romeo |
Every Italian likes someone | $\forall p. (Ip \supset \exists q.Lpq)$ | For every (person) p
if p is Italian
there exists (a person) q such that
p likes q |
Everyone likes an Italian | $\forall p. \exists q.(Iq \wedge Lpq)$ | For every (person) p
there exists some q such that
q is Italian AND p likes q |
Everyone likes this one particular Italian | $\exists q.(Iq \wedge \forall p.Lpq)$ | There exists a particular q such that
q is Italian
AND
for every (person) p
p likes this one particular q |
Pablo shaves all and only those who do not shave themselves | $\forall q.(Spq \equiv \neg Sqq)$ | For every (person) q
Pablo shaves q
IF AND ONLY IF
it is not that case that
q shaves q |
Not everyone is libertarian or progressive | $\neg \forall p.(Lp \vee Pp)$ | It is NOT the case that
there exists a (person) p such that
p is Libertarian OR p is progressive |
$\exists p.(\neg Lp \wedge \neg Pp)$ | There exists a (person) p such that
p is NOT libertarian
AND
p is NOT progressive |
|
Either the queen is rich or some pigs fly | $Rq \vee \exists p.(Pp \wedge Fp)$ | The queen is rich
OR
there exists a p such that
p is a pig AND p flies |
Everything has a cause | $\forall x. \exists y.Cyx$ | For every (thing) x
there exists some y such that
y caused x |
Everything has the same cause | $\exists y. \forall x.Cyx$ | There exists this one (uber thing) y such that
for every thing x
y caused x |
Nothing caused itself | $\forall x. \neg Cxx$ | For every (thing) x
it is NOT the case that
x caused x |
$\neg \exists x. Cxx$ | It is NOT the case that
there exists an x such that
x caused x |
|
Everybody loves somebody, but someone is unloved | $(\forall x. \exists y.Lxy) \wedge (\exists x.\neg \exists y.Lyx)$ | For every (person) x
there is some (person) y such that
x loves y
AND ALSO
there exists some (person) x such that
it is NOT the case that
there exists some (person) y such that
y loves x |
Some number less than 5 is a perfect square | $\exists x. (x<5 \wedge \exists y.(x=y^2))$ | There exists an x such that
x < 5
AND
the exists a y such that
x is y squared |
Juliet might like Romeo | $\lozenge Ljr$ | It is possible that
Juliet likes Romeo |
Two is necessarily equal to two | $\Box (2=2)$ | It is necessary that
2 equals 2 |
The Olympic thunder-god was worshiped by some Athenians | $\exists p.(Ap \wedge Wp(\iota g.Gtg))$ | There exists a (person) p such that
p is an Athenian
AND
p worships
the g such that the god of thunder is g |
It is possible that at some point, the sun-god became forever awesome | $\lozenge \mathbf{FG}A(\iota g.Gsg)$ | It is possible that
at some point in the future
it will always be the case that
the g such that the god of sun is g
is awesome |
Juliet believes that Romeo doesn’t believe that Juliet likes him | $\mathscr{B}_j(\neg \mathscr{B}_r Ljr)$ | Juliet believes that
it is not the case that Romeo believes that
Juliet likes Romeo |
We were pretty liberal with parentheses, but you don’t have to be. $\neg$ has the highest precedence, then $\wedge$, then $\vee$ then $\supset$ then $\equiv$.
A logical argument is written as a sequence of formulas. We check the validity of the argument by checking whether each formula is either (1) a premise or (2) follows from previous formulas. Arguments can also be given graphically, with premises above the line and conclusions below. Example:
$q$ | |
$q \vee p$ | $\neg q$ |
$p$ |
The meaning of “follows from” depends on the particular system of logic you are working under.
So let’s look at different kinds of logic.
How can there be many different kinds of logic? Well, for one there could be different ways to understand “truth.” Sometimes we aren’t concerned with exact truth, but rather “degree of belief,” or whether something is “justified,” or “achievable,” or “knowable.”
Here are some types of logics. The list is incomplete. The types are also overlapping.
A bivalent system has exactly two truth values, usually called true and false. What kinds of systems are not bivalent? Those with a third value (sometimes called “unknown”), and those where a truth value is represented as a degree of certainty or belief (e.g. a value ∈ 0.0..1.0).
Propositional Logic deals only with atomic sentences, known as prepositions, such as “Pigs fly”, “I am late”, “The moon is square”, and “The baby wants to sleep”. By “atomic” we mean variables can only refer to complete sentences, never to the actors or the actions within the sentences. In other words, prepositions are never decomposed. Sentences can be combined with truth operators to form larger sentences. The traditional operators are:
Form | Meaning |
---|---|
$p \wedge q$ | $p$ and $q$ |
$p \vee q$ | $p$ or $q$ (or both) |
$\neg p$ | not $p$ |
$p \supset q$ | $p$ materially implies $q$; e.g., $\neg(p \wedge \neg q)$, or equivalently, $\neg p \vee q$ |
$p \equiv q$ | $p$ and $q$ have the same truth value |
$p \wedge q$ | means “Pigs fly and the queen is rich” |
$\neg q \vee p$ | means “The queen is not rich or pigs fly” |
$(p \vee q) \wedge (\neg p \wedge \neg q)$ | means “Pigs fly or the queen is rich, but not both” |
Note: The $\wedge$ and $\vee$ 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.”
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 are considered (capital letters are classes, small letters are instances):
Form | Example |
---|---|
$x$ is $A$ | Socrates is human |
$x$ is not $A$ | Fido is not human |
$x$ is $y$ | Obama is the 44th U.S. President |
$x$ is not $y$ | Italy is not the 2016 Olympic champion in Women’s Water Polo |
All $A$ are $B$ | All dogs are mammals |
No $A$ is $B$ | No dogs are fish |
Some $A$ are $B$ | Some birds are flyers |
Some $A$ are not $B$ | Some markers are not green |
Syllogistic logic has been completely superseded by first-order 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.
Classical Logic is probably the most widely used logic. It is characterized by five properties (so say one of the authors of the Wikipedia article on the subject):
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.
In intuitionistic logic we are not concerned with the truth of a statement as much as we are about its justification. Every theorem 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 False). Therefore:
Classical logic has the principle of explosion: false implies everything. Or in other words, “from a contradiction, everything follows.” The rationale is: if things are only true or false, and you assume false is true, then everything is true because true is already true and now you say that false is true also.
Let’s demonstrate with a proof of $(A \wedge \neg A) \supset B$:
1. $A$ | Assumption |
2. $\neg A$ | Assumption |
3. $A \vee B$ | Disj Intro (1) |
4. $B$ | Conj Elim (2, 3) |
This means the following statements are true in classical logic:
Relevance logic rejects explosion, and requires the antecedent and consequent to be related to each other. There must be some real causality. We say in classical logic, implication is material but in relevance logic it is strict. There are many different ways to encode relevance.
Read about Relevance Logic in the SEP.
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)) \wedge 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.
A non-monotonic logic rejects the monotonicity of entailment. 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
See the SEP article on non-monotonic logic.
A paraconsistent logic is one that allows contradictions, by throwing out the principle of explosion.
See the SEP article on Paraconsistent Logic.
A many-valued logic has, you got it, many truth-values. Many such systems exist. What’s useful about them is they get rid of the those principles of excluded middle and non-contradiction.
You might be interested in four-valued logics.
The Catuṣkoṭi is also known as the “Four Corners.” Propositions take on four values :
Find out more at Wikpedia and the SEP and this lecture by Graham Priest.
A fuzzy logic is one in which facts have a degree of truth between 0 and 1. It is useful for statements like “$X$ is tall” or “$X$ is an adult” or “The bike is new.”
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 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.
The basic alethic modal operators are defined as:
Form | Meaning |
---|---|
$\Box A$ | It is necessary that A |
$\lozenge A$ | It is possible that A |
In classical modal logic, the two operators are duals:
$$\begin{eqnarray} \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 \\ \end{eqnarray}$$Various systems of modal logic are characterized by the axioms and inference rules they add to the underlying logic.
The basic deontic operators are defined as:
Form | Meaning |
---|---|
$\mathscr{O}A$ | It is obligatory that $A$, or $A$ ought to be (MUST) |
$\mathscr{P}A$ | It is permissible that $A$, or $A$ is allowed (MAY) |
In epistemic logic we have:
Form | Meaning |
---|---|
$\mathscr{K}_x A$ | Agent x knows A |
$\mathscr{K} A$ | A is known (by some agent whose identity we assume from context) |
In doxastic logic we have:
Form | Meaning |
---|---|
$\mathscr{B}_x A$ | Agent x believes A |
$\mathscr{B} A$ | A is believed (by some agent whose identity we assume from context) |
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:
Temporal logic deals with the modalities of time.
Form | Meaning |
---|---|
$\mathbf{P}A$ | $A$ was true (at some point) in the Past |
$\mathbf{F}A$ | $A$ will be true (at some point) in the Future |
$\mathbf{H}A$ | $A$ Has always been true |
$\mathbf{G}A$ | $A$ is always Going to be true |
Dynamic Logic brings events into the picture:
Form | Meaning |
---|---|
$[e]A$ | “After event $e$, $A$ is necessarily true” |
$\langle e \rangle A$ | “After event e, A is possibly true” |
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
In logic we are not so much concerned with the absolute truth or falsity of individual premises themselves, but rather with the form of arguments. We can make this idea precise with formal systems.
A Formal System is a mechanism for symbolically generating a set of formulas (called theorems) via inference rules.
A logistic system (a.k.a. a system of formal logic) is a formal system in which formulas are assigned truth values.
We need examples.
So first, what is a formula? It’s a statement, written as a string of symbols from a finite alphabet, that is formed according to formation rules which we call a grammar. The grammar defines the syntax of the formal system.
For example, here is a grammar for classical propositional logic:
var → "p" | "q" | "r" | var "′" formula → "T" | "F" | var | "¬" formula | "(" formula "∧" formula ")" | "(" formula "∨" formula ")" | "(" formula "⊃" formula ")" | "(" formula "≡" formula ")"
which means that
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!
The semantics is given by a defining a function that maps each formula to a truth value. The mapping is necessarily relative to some interpretation (or situation) φ which gives meanings to the variables in the system.
For example, the semantics of classical propositional logic is defined as follows:
$(\neg p \wedge (r \supset \neg q)) \vee p)$
under an interpretation in which $p$ is mapped to true, $q$ to false, and $r$ to true.We’re interested ultimately in valid reasoning—what follows from what—so let’s define some terms:
In a logistic system, we don’t necessarily compute semantic functions for the fun of it. Instead, we apply inference rules to algorithmically, (or mechanistically, typographically, symbolically) generate a formulas in such a way as to mimic a reasoning process. Define
$\{A_1, ..., A_n\} \vdash B$
to mean “$B$ given assumptions $A_1, ..., A_n$.” The inference rules of a logistic system produce these kinds of statements.
If $\varnothing \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.
1. (p ∧ (p ⊃ q)) ⊢ (p ∧ (p ⊃ q)) | Assumption |
2. (p ∧ (p ⊃ q)) ⊢ p | Conj Elim (1) |
3. (p ∧ (p ⊃ q)) ⊢ (p ⊃ q) | Conj Elim (1) |
4. (p ∧ (p ⊃ q)) ⊢ q | MP (2, 3) |
5. (p ∧ (p ⊃ q)) ⊢ (p ∧ q) | Conj Intro (2, 4) |
6. ((p ∧ (p ⊃ q)) ⊃ (p ∧ q)) | Impl Intro (5) |
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.
The reasoning about logistic systems themselves is called metalogic.
We’ve covered: