Propositional Logic

Propositional Logic, developed by the Greek Stoics in the 3rd century BCE (especially Chrysippus), is the system of logic that deals with compound sentences whose clauses are joined by words such as: and, or, it’s false that, if then, if and only if, unless, provided that, only if, neither nor, either or.

Symbols and Sentences

The language of Propositional Logic consists of:
- Capital letters
  - which stand for sentences and are called sentence letters,
- Parentheses,
- Connectives, the symbols: &, ~, v, →, ↔︎
  - which are read: and, not, or, if then, if and only if.
The sentences of Propositional Logic are built up from sentence letters using the connectives and parentheses so that:
- A capital letter by itself is a sentence;
- If α is a sentence, ~α is a sentence;
- If α and β are sentences, (α & β) is a sentence;
- If α and β are sentences, (α v β) is a sentence;
- If α and β are sentences, (α → β) is a sentence;
- If α and β are sentences, (α ↔︎ β) is a sentence.

The following are thus sentences of PL:
- (A→~B)
  - If A then it’s false that B;
- ~(AvB)
  - It’s false that A or B;
- ((A&B) v ~C)
  - Either A and B or it’s false that C;
- (~(A&B) ↔︎ ~Av~B)
  - It’s false that both A and B if and only if either A is false or B is false.

Connectives

Let α and β be any sentences of PL. Then:

A conjunction is a sentence of the form (α & β) and means “α and β”.
- α and β are its conjuncts.
A negation is a sentence of the form ~α and means “it’s false that α”.
- ~α is the negation of α.
A disjunction is a sentence of the form (α v β) and means “α or β (or both)”.
- α and β are its disjuncts.
A conditional is a sentence of the form (α → β) and means “if α then β”.
- α is its antecedent and β its consequent.
A biconditional is a sentence of the form (α ↔︎ β) and means “α if and only β”.
- α and β are its left and right conditions.

The truth values of conjunctions, negations, disjunctions, conditionals, and biconditionals are determined by the truth values of their components as follows:
- A conjunction is true if and only both its conjuncts are true.
- A negation is true if and only if it’s the negation of a false sentence.
- A disjunction is true if and only if either or both its disjuncts are true.
  - Disjunction thus uses the inclusive rather than the exclusive sense of “or.”
- A conditional is true if and only if its antecedent is false or its consequent true or both.
  - Or, equivalently, it’s not the case that its antecedent is true and consequent false.
- A biconditional is true if and only if its two conditions have the same truth value.

Truth Table Definition of the Connectives

The truth table definitions are straightforward except for the conditional. It makes sense that a conditional is true when the antecedent and consequent are both true. And it makes sense that a conditional is false when the antecedent is true and the consequent false. But the fact that a conditional is true when its antecedent is false leads to what are politely called the “paradoxes of material implication” but impolitely referred to as flaws. I take up this matter in Paradoxes of Material Implication.

Translating Natural Language into Propositional Logic

Here are the translations of words such as “only if” and “unless” into the language of Propositional Logic.

He’s morally responsible for Fido’s death only if he could have prevented it. (M: He’s morally responsible for Fido’s death, P: He could have prevented Fido’s death.)
- M only if P
- P is a necessary condition for M
- If not P, then not M
- ~P → ~M
- Equivalently, M → P.
He’s not morally responsible for Fido’s death unless he could have prevented it. (M: He’s morally responsible for Fido’s death, P: He could have prevented Fido’s death.)
- Not M unless P
- Not M if not P
- If not P, then not M
- ~P → ~M
- Equivalently, M → P.
To be eligible for the presidency a person must be a native-born citizen and at least 35 years of age. (E: Person is eligible to be president, N: Person is a native-born citizen, A: Person is at least 35 years of age)
- For E to be true, N and A must be the case
- N and A are necessary conditions of E
- E → (N & A)
- Equivalently, ~(N & A) → ~E
- Equivalently, (~Nv~A) → ~E
  - ~N&~A → ~E says a person is not eligible if they lack both qualifications
  - ~Nv~A → ~E says a person is not eligible if they lack either qualification (or both).
32539 is prime if and only if it is divisible only by itself and one. (P: 32539 is prime, D: 32539 is divisible only by itself and one)
- P if and only if D
- P ↔︎ D
- Equivalently, (P → D) & (D → P)
- Versus only one conditional:
  - From (P → D) alone, you can’t infer from the fact that 32539 is divisible only by itself and one that 32539 is prime.
  - From (D → P) alone, you can’t infer from the fact that 32539 is not divisible only by itself and one that 32539 is not prime.
- Equivalently, (D → P) & (~D → ~P)
  - So, from the fact that 32539 is divisible only by itself and one, you can infer it’s prime.
  - And from the fact that 32539 is not divisible only by itself and one, you can infer it’s not prime.
He’ll be fined up to $250,000, imprisoned up to 5 years, or both. (F: He’ll be fined up to $250,000, P: He’ll be imprisoned up to 5 years).
- F v P v (F&P)
- Equivalently, F v P
  - F v P and F v P v (F&P) are logically equivalent
He’ll be fined up to $250,000, imprisoned up to 5 years, but not both. (F: He’ll be fined up to $250,000, P: He’ll be imprisoned up to 5 years).
- (F v P) & ~(F&P)
  - (F v P) & ~(F&P) entails F v P
  - F v P does not entail (F v P) & ~(F&P).

Truth and Falsehood

A sentence of PL is true or false given an assignment of propositions to its sentence letters.

For Example

Let
- A = Thomas Jefferson signed the Declaration of Independence;
- B = George Washington signed the Declaration of Independence;
  - which is false since Washington was fighting the British in Boston when the Declaration was signed.
Then:
- A&B is false, since one of the conjuncts is false.
- A&~B is true, since both conjuncts are true.
- AvB is true, since at least one of the disjuncts is true.
- Av~B is true, since, both being true, at least one of the disjuncts is true.
- AvB &~(A&B) is true, since A or B is true but not both.
  - This is the exclusive sense of “or”.
- A→B is false, since the antecedent is true and the consequent false.
- A↔︎B is false, since A and B have different truth values.
- A↔︎~B is true, since A and ~B have the same truth value.
- (A&B)↔︎(AvB) is false, since A&B is false and AvB is true.

For a sentence to be true or false we don’t need to assign actual propositions to sentence letters. We just need truth-values.
So a sentence is true or false under an assignment of truth-values (T and F) to its sentence letters.

Logical Modalities

A sentence of PL is true or false under an assignment of truth-values to its sentence letters.
Using the notions of truth and falsehood under an assignment of truth-values, we can define the central notions of logic:
- logical truth,
- logical falsehood
- logical equivalence,
- logical consequence (validity),
- logical compatibility.

A sentence is logically true (or a tautology or logically necessary) if there is no assignment of truth values to its sentence letters under which it’s false. For example:
- A v ~A
- A&B → A
A sentence is logically false (or contradictory or logically impossible) if there is no assignment of truth values to its sentence letters under which it’s true. For example:
- A & ~A
- A ↔︎ ~A
Two sentences are logically equivalent if there is no assignment of truth values to their sentence letters under which one sentence is true and the other false. For example:
- ~(A&B) and ~Av~B
- ~(AvB) and ~A&~B
- More Logical Equivalences.
An argument is valid if there is no assignment of truth values to its sentence letters under which its premises true and its conclusion false. The conclusion of a valid argument is a logical consequence of its premises. The premises of a valid argument logically entail or logically imply its conclusion. Valid arguments:
- AvB, ~A, So B,
- A→B, ~B, So ~A,
- More Valid Arguments.
A set of sentences is logically compatible if there’s an assignment of truth values to its sentence letters under which they are all true; and logically incompatible otherwise. Logically compatible propositions:
- {A, A→B, A↔︎B, AvB, A&B}
- {A→B, A→~B}

Decision Procedures

A decision procedure is a step-by-step procedure that, after a finite number of steps, yields a YES or NO answer to a question. For propositional logic, there are decision procedures for the following questions:
- Is sentence σ logically true?
- Is sentence σ logically false?
- Are sentences σ and β logically equivalent?
- Is sentence σ a logical consequence of sentences Π?
- Are sentences Σ logically incompatible?
The three chief decision procedures for propositional logic are:
- Truth tables
- Truth trees (semantic tableau)
- Computer code using Boolean functions.

Truth Tables

A truth table is a table:
- whose columns are sentences and their sentence letters
- whose rows are Ts and Fs for every combination of truth-values for the sentence letters of the sentences.
  - For n sentence letters there are 2ⁿ rows.

Examples:

Is ~(A & ~A) logically true?
Yes, because the two possible truth-values for ~(A & ~A) are both T.

Is A → ~A logically false?
No, because A → ~A is T when A is F.

Are A ↔︎ B and (A&B) v (~A&~B) logically equivalent?
Yes, because A ↔︎ B and (A&B) v (~A&~B) have identical truth-values (the Ts and Fs) for the four combinations of truth-values for A and B.

Is the argument MvG, M →~A, A, so G valid? (Is G a logical consequence of MvG, M →~A, A?).
Yes, because there is no row on which the three premises are T and the conclusion F.

Truth Trees (Semantic Tableau)

Truth trees (semantic tableau) are a more efficient procedure than truth tables of determining logical truth, logical falsehood, logical equivalence, and logical consequence. Where truth tables use rows to depict the ways sentences can be true or false, truth trees use tree branches.

Basic Idea

Is this argument valid?
That is, can the premises be true and the conclusion false? In other words, can these three sentences all be true?
This is the trunk of the tree. Trees grow (downward) by applying rules to sentences and closing branches if they’re contradictory. The Disjunction Rule applied to A v B splits the tree into two branches. (The 1 indicates that a rule has been applied to A v B.)
Both A and ~A appear on the left branch, so the left branch is contradictory and is closed. And both B and ~B appear on the right branch, so the right branch is contradictory and is also closed.
All branches are closed; so argument is valid.
In a nutshell:
- The branches represent the two conceivable ways A v B, ~A, and ~B can all be true. But neither of the ways is possible. Hence there’s no possible way the three sentences are all true. So the argument A v B, ~A, so B is valid.

Overview

A tree is grown (downward) by alternating between (1) applying a rule and (2) closing branches.
1. A rule is applied to a sentence on an open branch.
  - Conjunctions, disjunctions, conditionals and their negations all have rules, as well as double negations. See the rules below.
2. A branch is closed, and marked with an X, if both a sentence and its negation appear on the branch.
A tree terminates when either:
- All branches are closed, in which case the argument is valid.
- No rules can be applied but some branches are open, in which case the argument is invalid.

Another Example

Is this argument valid?
- M v G
- M → ~A
- A
- So, G
The trunk of the tree consists of the premises and the negation of the conclusion:
We first apply the Disjunction Rule to M v G, which splits the tree into two branches, adding a green 1 to M v G. Both G and ~G appear on the right branch. So we close the branch by adding an X.
We next apply the Conditional Rule to M → ~A, which splits the tree again, adding a green 2 to M → ~A.. We then close both new branches, since M and ~M appear on the left branch and A and ~A appear on the right branch.
All branches are closed. So the argument is valid.

See, Truth Tree Algorithm, Rules, and Flowchart below.

Computer Code using Boolean Functions

The symbolic/numeric programming language Mathematica has commands that can be easily used to determine whether sentences are logically true, logically false, logically equivalent, or a logical consequence. The commands are TautologyQ and the Boolean functions Implies, And, Or, Not.

Here’s how it works.

Logical Truth

Is ~(A&B) → ~Av~B logically true.
We first translate ~(A&B) → ~Av~B into Mathematica. Working inside out:
- A&B ⇒ And[a,b]
- ~(A&B) ⇒ Not[And[a,b]]
- ~A ⇒ Not[a]
- ~B ⇒ Not[b]
- ~Av~B ⇒ Or[Not[a],Not[b]]
- Finally, ~(A&B) → ~Av~B ⇒ Implies[Not[And[a,b]], Or[Not[a],Not[b]]]
- Which in Mathematica looks like this:
  - ! (a && b) ⇒ ! a || ! b
- Then we use the TautologyQ command to determine whether the sentence is logically true.
  - TautologyQ[Implies[Not[And[a, b]], Or[Not[a], Not[b]]]]
- The command returns True. So the sentence is logically true.

Validity

To determine whether an argument is valid we represent the argument as a single sentence so that the argument P1, P2, .. Pn, so C is represented by (P1 & P2 & ..& Pn) → C. Then we translate the sentence into Mathematica and use the TautologyQ command to determine whether it’s logically true.
Consider the argument:
- ~(A v B)
- ~(B v C)
- So, ~(A v C)
The argument is represented by the sentence (~(A v B) & ~(B v C) ) → ~(A v C).
Which in Mathematica is:
- Implies[And[Not[Or[a, b]], Not[Or[b, c]]], Not[Or[a, c]]]
The TautologyQ command returns True, so the argument is valid.
An invalid argument:
- A v B
- B v C
- So, A v C
The argument is represented by (A v B) & (B v C) → (A v C).
Which in Mathematica is:
- Implies[And[Or[a, b], Or[b, c]], Or[a, c]]
The TautologyQ command returns False.
With a little code (see below) we can list the counterexamples, i.e., the truth-value combinations of a, b, c that make the premises true and conclusion false. Which in this case is:
- {a→False, b→True, c→False}.

Equivalence

To determine whether two sentences P and Q are logically equivalent we represent the equivalence as the conditionals P→Q and Q→P, translate them into Mathematica, and test each for logical truth.
Consider the sentences;
- (AvB)&~(A&B) and (A&~B) v (~A&B)
The left-to-right conditional is:
- ((AvB)&~(A&B)) → ((A&~B) v (~A&B))
Which is logically true per Mathematica instruction:
- TautologyQ[Implies[And[Or[a, b], Not[And[a, b]]], Or[And[a, Not[b]], And[Not[a], b]]]]
The right-to-left conditional is:
- ((A&~B) v (~A&B)) → ((AvB)&~(A&B))
Which is logically true per the code:
- TautologyQ[Implies[Or[And[a, Not[b]], And[Not[a], b]], And[Or[a, b], Not[And[a, b]]]]]
The sentences are thus logically equivalent.

Code That Lists Counterexamples

This piece of code takes “Implies[And[Or[a, b], Or[b, c]], Or[a, c]]” and
- prints out what it looks like
  - (a || b) && (b || c) ⇒ a || c
- says whether it’s logically true
  - False
- displays counterexamples
  - {a→False, b→True, c→False}.

sentence = Implies[And[Or[a, b], Or[b, c]], Or[a, c]]
letters = DeleteDuplicates@Cases[sentence, _Symbol, Infinity];
assignments = Tuples[{True, False}, Length[letters]];
value = Flatten[sentence /. Thread[letters → #] & /@ assignments];
And @@ Flatten[sentence /. Thread[letters → #] & /@ assignments]
Do[
If[value[[n]] == False, Print[Thread[letters → #] &@assignments[[n]]]],
{n, 1, 2^Length[letters]}]
- (a || b) && (b || c) ⇒ a || c
- False
- {a→False, b→True, c→False}.

Arguments

Real-life arguments can be translated into the language of Propositional Logic and evaluated to determine whether they’re valid.

You’re damned if you do and you’re damned if you don’t. Therefore, you’re damned. (D: You’re damned, Y: You do)
- (Y→D) & (~Y→D)
- So, D
  - Valid
If people have free will, then mental acts of will can bring about physical changes in the brain. But if mental acts can bring about changes in the brain, then telekinesis is real. But there is no such thing as “mind over matter” — telekinesis. So people don’t have free will. (F: People have free will, M: Mental acts of will can bring about physical changes in the brain, T: Telekinesis is real)
- F → M
- M → T
- ~T
- So, ~F
  - Valid
If capital punishment deterred capital crimes, it would be morally justified. But it doesn’t deter capital crimes. So, it’s not morally justified. (D: Capital punishment deters capital crimes, J: Capital punishment is morally justified)
- D → J
- ~D
- So ~J.
  - Invalid
    - Counterexample: D → False and J → True
    - Fallacy of Denying the Antecedent
The theory of evolution and Genesis are not both be true. If the Bible is the word of God, Genesis is true. Therefore, if the theory of evolution is true, the Bible is not the word of God. (B: The Bible is the word of God, E: The theory of evolution is true, G: Genesis is true)
- ~(E&G)
- B → G
- So, E → ~B
  - Valid
The universe consists either of the Milky Way Galaxy alone or of a vast number of galaxies (including the Milky Way). If the universe consists merely of the Milky Way Galaxy, the Andromeda Nebula would not be significantly further from Earth than the stars in the Milky Way. The Andromeda Nebula is in fact significantly further from Earth than the stars in the Milky Way (as discovered by Edwin Hubble in 1923). Therefore, the universe consists of numerous galaxies. (M: The universe consists of the Milky Way Galaxy alone, G: The universe consists of a vast number of galaxies. A: The Andromeda Nebula is significantly further from Earth than the stars in the Milky Way.)
- M v G
- M → ~A
- A
- So, G
  - Valid
The defendant’s statement and the plaintiff’s testimony aren’t both true. The defendant’s statement is true. Therefore the plaintiff’s testimony is false. (D: The defendant’s statement is true, P: The plaintiff’s testimony is true)
- ~(D & P)
- D
- So, ~P
  - Valid
The defendant’s statement and the plaintiff’s testimony aren’t both true. The defendant’s statement is false. Therefore the plaintiff’s testimony is true. (D: The defendant’s statement is true, P: The plaintiff’s testimony is true)
- ~(D & P)
- ~D
- So, P
  - Invalid
    - Counterexample: D → False, P → False
If Einstein’s General Theory is true, clocks at 30,000 feet run faster than clocks at sea level. Clocks at 30,000 feet do in fact run faster than clocks at sea level. Therefore, Einstein’s General Theory is true. (G: Einstein’s General Theory is true, C: Clocks at 30,000 feet run faster than clocks at sea level)
- G → C
- C
- So, G
  - Invalid
    - Counterexample: G → False, C → True
    - Fallacy of Affirming the Consequence

Basic Valid Arguments

An argument is valid if there is no assignment of truth values to its sentence letters under which its premises true and conclusion false.

Basic Logical Equivalences

Two sentences are logically equivalent if there is no assignment of truth values to their sentence letters under which one sentence true and the other false.

Paradoxes of Material Implication

The conditional in Propositional Logic is defined so that it’s true when its antecedent is false. This leads to what are called the “paradoxes of material implication,” valid arguments that are subject to counterexample:

Consider Argument #5, for example:
- Not knowing whether Anna went to school yesterday, her brother says that it’s false that if she rode her electric bike to school she went 500 mph. So it’s true that ~(A→B). Assume Anna didn’t go to school yesterday. Then A&~B is false. So argument #5 is invalid.
The problem is that the truth value of the indicative conditional of natural language is determined by circumstances beyond the truth values of its components when the antecedent is false. Consider the conditional:
- If Anna rode her bike to school yesterday she wore a helmet.
The statement is true if she rode her bike to school yesterday and wore a helmet. The statement is false if she rode her bike and didn’t wear a helmet. But if Anna didn’t ride her bike to school yesterday, the truth-value of the conditional depends on evidence beyond the truth-values of the antecedent and consequent. Suppose Anna always wears a helmet and there’s no reason why she would have not worn one yesterday. That’s evidence that the conditional is true. Suppose instead that Anna never wears a helmet and there’s no reason why she would have worn one yesterday. That’s evidence the conditional is false.
So the truth-value of the indicative conditional of natural language depends on the truth-value of its consequent when the antecedent is true but depends on evidence beyond the truth value of the consequent when the antecedent is false.

So why don’t logicians fix the problem. We’ll they have, pretty much. The fix is called Conditional Logic. The problem is that Conditional Logic is more complicated than Propositional Logic. Since the truth-value of the conditional can’t be defined simply in terms of the truth values of its antecedent and consequent, the conditional in Conditional Logic has to be defined in more complex terms, such as possible worlds or conditional probability. This makes evaluating validity, logical truth, and logical consequence more complicated.

Truth Tree Algorithm, Rules and Flowchart

Truth Tree Algorithm

List the premises and negation of the conclusion in a column, the trunk of the tree.
Check each open branch for the occurrence along the branch of both a sentence and its negation. Close each such “contradictory” branch by placing an X at the end of the branch.
Check to see if all branches are closed. If so, stop: the argument is valid. Otherwise, proceed to the next step.
Select an unnumbered nonbasic sentence, if there is one, and apply the appropriate rule.
- A numbered sentence is one with a number to its right.
- A nonbasic sentence is a sentence that is neither a sentence letter nor the negation of a sentence letter.
- The appropriate rule is determined by the form of the selected sentence (conjunction, negation of conjunction, disjunction, etc.).
- To apply a rule:
  - Place the number N to the right of the sentence
    - where N starts at one and increases by one with each application of of a rule
  - Write down the sentences and any branching lines, according to the rule, at the bottom of all open branches on which the selected sentence appears.
    - Suggestion: select those sentences first whose rules are nonbranching.
If a rule was applied in the previous step, return to step two. Otherwise stop: the argument is invalid.

Rules

Flowchart

More Examples

Argument 1
- A → (B & C)
- ~B v ~ C
- So, ~A

Argument 2
- A → B
- B → A
- So, A v B

Argument 3
- ~(A v B)
- ~(B v C)
- So, ~(A v C)

Argument 4
- (A v B) & (A v ~B)
- So, A

m

A Philosopher's View