Logic

Definition

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.

Topics

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:

Deduction: There is no possible situation in which the premises are (all) true but the conclusion false.
Induction: The premises give really strong evidence for the truth of the conclusion.

Logistic Systems

Often, logicians are concerned not with the absolute truth or falsity of the premises themselves, but rather with the form of arguments. This makes them inclined to use formal systems. A logistic system is a formal system in which formulas are assigned truth values and a particular class of formulas, called theorems, are generated with inference rules.

Syntax

The syntax defines the legal strings of the system, which are called its formulas.

Example: Here is the syntax for one particular logistic system, the one known as "classical propositional logic":

    Var     ::= 'p' | 'q' | 'r' | Var '′'
    Formula ::= 'T' | 'F' | Var
              | '~' Forumula
              | '(' 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.

Semantics

The semantics is given by a semantic valuation function which maps each formula to a "truth value." The mapping is necessarily relative to some interpretation φ which gives meanings to the variables in the system.

Example: The semantics of classical propositional logic is defined as follows:

   type Interpretation = Var → {true, false}

   E : Formula → Interpretation → {true, false}
   E T φ = true
   E F φ = false
   E p φ = φ(p)
   E ~A φ = true, if E A φ = false; and false otherwise
   E (A ∧ B) φ = true, if both E A φ = true and E B φ = true; and false otherwise
   E (A ∨ B) φ = true, if at least one of E A φ = true and E B φ = true; and false otherwise
   E (A ⇒ B) φ = false, if E A φ = true and E B φ = false; and true otherwise
   E (A ≡ B) φ = true, if E A φ = E B φ; and false otherwise

Satisfiability: If formula A is true under some interpretation φ we write ⊨_φA and say φ satisfies A, or that A is satisfiable.
Validity: If formula A is true under all interpretations we write ⊨A and say A is a tautology, or that A is valid.
Entailment: If formula A is true under all interpretations in which formula B is true, we write B ⊨ 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.

Exercise: Prove the following:

If a formula is valid, then it is satisfiable
If a formula is unsatisfiable, then it is invalid
In classical propositional logic, A is valid iff ~A is unsatisifiable
In classical propositional logic, A is invalid iff ~A is satisifiable

Inference Rules

In some logistic systems, the semantic truth functions may be too expensive or impossible to compute. So inference rules are defined to algorithmically (mechanistically, typographically) generate a set of formulas in such a way as to mimic a reasoning process. Define

{A₁, ..., A_n} ⊢ B

to mean "B given assumptions A₁, ..., A_n." The inference rules of a logistic system produce these kinds of statements.

Example: The inference rules of classical propositional logic are these:

If ∅ ⊢ A, we say A is a theorem and write ⊢ A. The sequence of inferences producing a theorem is a proof of that theorem.

Example: The following is a proof of the theorem ((p ∧ (p ⇒ q)) ⇒ (p ∧ q))

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)

Exercise: Give proofs of the following theorems:

~F
(p ⇒ (q ⇒ p))
(p ∨ ~p)
((p ⇒ q) ≡ (~p ∨ q))
((p ≡ q) ⇒ ((p ∧ q) ∨ (~p ∧ ~q)))
((p ∧ ~p) ⇒ q)
((p ∨ (q ∧ r)) ⇒ (p ∨ q))

Properties of Logistic Systems

The definition of "truth" in a system is generally just stated in precise natural language. The derivation of theorems, however, is a purely mechanical process. We would like to know how well, in a logistic system, does "theorem derivation" (proof) correlate with truth.

Soundness: A system is sound iff every theorem is true.
Completeness: A system is complete iff every true formula is a theorem.
Consistency: A system is consistent iff no two theorems have contradictory truth values (where "contradictory" depends on the type of logic being considered).
Decidability: A system is decidable iff there exists an (always-terminating) algorithm to determine whether or not a given formula is a theorem.

Exercise: What are the ramifications of a logistic system that is unsound? That is incomplete? That is inconsistent? That is undecidable?

Kinds of Logic

There are many different kinds of logic. These types might vary on what they take to be "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.

Bivalent Logic

A system with exactly two truth values, usually called true and false. This is as opposed to having a third value called unknown, or instead having truth be a degree of certainty or belief (e.g. a value ∈ 0.0..1.0).

Classical Logic

The most widely used. It is characterized by five properties (so say one of the authors of the Wikipedia article on the subject):

Excluded middle: A ∨ ~A
Non contradiction: ~(A ∧ ~A)
Monotonicity of entailment: If B follows from A, then it follows from A and C (in other words, go ahead and add assumptions!)
Commutativity of conjunction: A ∧ B has the same truth value as B ∧ A
DeMorgan dualities for all operators: ~P(A1,...,An) = Q(~A1,...,~An), where P and Q are duals of each other. Examples: ∧ and ∨, ∀ and ∃ etc.

Exercise: Show that, in a bivalent, classical logic, the following definition of consistency is in line with the general definition above: "A bivalent, classical logic is consistent iff there exists a formula that is not a theorem." Also comment on the usefulness of a system in which everything you could possibly utter were a theorem?)

Intuitionistic (Constructive) Logic

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 ~A means "A is refutable" (i.e. it is provable that no proof of A exists — in other words, assuming A leads to the the constant False). Therefore

You can only prove A ∨ ~A by proving A or refuting A. (The inability to do neither means you can't say anything, so shut up.)
You can only prove ∃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 ~P holds for every x.
You can derive ~~A from A, but you cannot derive A from ~~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 the proof of A in order for A to be a theorem!

Relevance Logics

Classical logic has the principle of explosion: "false implies everything", or "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.

A proof of (A ∧ ~A) ⇒ B:

    A                (assume)
    ~A               (assume)
    A ∨ B            (disj intro (1))
    B                (disj elim (2,3))

This means the following statements are true in 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.

Exercise: Ugh. That last one looks awful. Go discuss it with a mathematician or logician.

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.

Exercise: Write a research paper on relevance logics.

Non-monotonic Logics

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

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

Paraconsistent Logics

A paraconsistent logic is one that allows contradictions, by throwing out the principle of explosion. This means throwing out disjunctive introduction, disjunctive elimination or the transitivity of entailment. At least you can reason about contradictions without throwing out the whole system.

These logics are alternatives to belief revision in non-monotonic logics.

Syllogistic Logic

A rather ancient kind of logic that includes reasoning about "all" and "some", but does not allow general propositions nor connectives like and and or. There are only eight kinds of statements that are considered (capital letters are classes, small letters are instances):

x is A
x is not A
x is y
x is not y
All A is B
No A is B
Some A is B
Some A is not B

Quantificational Logic

A modern way to reason about "all" and "some" — strictly more powerful than syllogistic logic. Just add quantifiers (∃ and ∀) and predicates to propositional logic.

Usually these systems allow objects, functions on objects, and ways to represent identity. Sometimes you have ways to write descriptions ("the x such that ...").

Orders of logic:

Zero-Order Logic (Propositional Logic): Propositions only
First-Order Logic (Predicate Logic): Zero-Order Logic + objects + functions on those objects + predicates which take as arguments only those objects + quantification on those objects.
Second-Order Logic: First-Order Logic + quantification over first-order predicates
Third-Order Logic: Second-Order Logic + predicates whose arguments are first-order predicates
Fourth-Order Logic: Third-Order Logic + quantification over third-order predicates
Fifth-Order Logic: Fourth-Order Logic predicates whose arguments are third-order predicates

Exercise: Define "nth order logic" (inductively).

Modal Logics

Modal Logics deal with modalities. The basic modalities are the alethic ones: necessity and possibility. Modal logics can be based on classical or non-classical logics. Other kinds of logics feature modalities, e.g.

temporal
dynamic
deontic ("ought to", "permissible that")
doxastic (belief)
epistemic (degree of knowledge / ignorance)

Fuzzy Logic

A fuzzy logic is one in which facts have a degree of truth between 0 and 1. DO NOT CONFUSE FUZZY LOGIC WITH PROBABILITY THEORY.