5. PROPOSITIONAL LOGIC

Outline

 

James Fieser, UT Martin

updated 6/1/2021

 

This chapter builds upon the principles of propositional logic first presented in the overview chapter. We (1) present five logical connectives (conjunction, disjunction, negation, conditional, biconditional), (2) show how truth tables are used for defining the meaning of individual propositions, (3) show how truth tables are used for determining the validity and invalidity of arguments, and (4) show how truth trees are used as an alternative way of determining the validity or invalidity of arguments.

 

A. LOGICAL CONNECTIVES

 

Logical connectives (also called “logical operators”) are symbols or words used to connect two or more sentences (of either a formal or a natural language) in a grammatically valid way, such that the value of the compound sentence produced depends only on that of the original sentences and on the meaning of the connective. There are five common logical connectives: and, or, not, if-then, if and only if. In formal logic, these five connectives are symbolized as follows:

 

and (conjunction): &

or (disjunction): v

not (negation): ~

if-then (conditional): →

if-and-only-if (biconditional): ↔

 

1. Conjunction (and)

P & Q

Sentence letters are called “conjuncts”; the two conjuncts can be reversed and retain the original meaning. In ordinary conversation, several words can express the conjunctive relation, such as "but", "although", "besides" (see the Logic Overview for a fuller list).

 

2. Disjunction (or)

P v Q

Sentences letters are called “disjuncts”; the two disjuncts can be reversed and retain the original meaning. The disjunction is always understood inclusively as an or/and; that is, P might obtain, Q might obtain, or both P and Q might obtain. Thus, the disjunction is never taken to be exclusive, where either P obtains or Q obtains but both cannot obtain.

 

3. Negation (not)

~P

For clarity, the negation symbol is often read as “it is not the case that”.

 

4. Conditional (if-then)

P → Q

The first sentence letter is called “antecedent” and second is called “consequent”. The antecedent and consequent cannot be reversed and still retain its original meaning. In ordinary conversation, several words can express the conditional relation, such as "implies", "entails", "since" (see the Logic Overview for a fuller list). In philosophical discourse, two common ways of designating conditional statements are "necessary/sufficient conditions", and "if/only if". Below is an explanation of each.

Necessary-sufficient conditions

P (sufficient condition) → Q (necessary condition)

Example: if it rains, then the sidewalk will get wet

P is a sufficient condition for Q

Raining is a sufficient condition for the sidewalk being wet

P is sufficient for bringing about Q, but is not the only thing that brings about Q. For example, the sidewalk could get wet from a garden hose.

Q is a necessary condition for P

The sidewalk being wet is a necessary condition of it raining

Q is a necessary result of P in every case in which P arises

If / only if

Consider the following conditional statement as worded in standard propositional form:

"If it rains then the sidewalk will get wet" (R → S)

In ordinary conversation, we may express this in the following two ways:

"The sidewalk will get wet IF it rains" (S if R)

"It is raining ONLY IF the sidewalk gets wet" (R only if S)

While the terms "if" and "only if" are both indicators of a conditional in ordinary conversation, the two do not mean the same thing, and they in fact designate opposite orders of the antecedent and consequent. When the term "if" appears by itself in a sentence (without the word "only"), we should just follow our normal intuition and interpret "if" as designating the antecedent, in this case "it rains" (R). However, when "only if" appears in a sentence, it designates the consequent, in this case, "the sidewalk gets wet" (S). Think of the term "only if" as stressing the necessity of the consequent "S". That is, when it rains, of necessity the sidewalk will get wet.

 

5. Biconditional (if and only if)

P ↔ Q

The biconditional combines a conditional relation between P and Q and its reverse. Sentence letters are called “biconditions”; the two biconditions can be reversed and retain the original meaning.

 (P→Q) and (Q→P)

P is a necessary and sufficient condition for Q

Example: Bob’s being a bachelor is both a necessary and sufficient condition for Bob being an unmarried man

P is a sufficient condition for Q (Q is a necessary condition for P)

P is a necessary condition for Q (Q is a sufficient condition for P)

P if and only if Q

Example: Bob is a bachelor if and only if Bob is an unmarried man

P if Q (if Q then P)

P only if Q (if P then Q)

 

B. TRUTH TABLES FOR LOGICAL CONNECTIVES

 

A truth table is a representation of the truth value of a wff, and in essence display the meaning of a wff. Truth tables follow the principle of bivalence, which is that true and false are the only truth values and in every possible situation each statement has one and only one of them. The following are the truth tables for wffs containing the five logical connectives.

 

1. Negation: ~p

Hint: the truth value of the negated proposition is opposite that of the original proposition.

Example: “it is not the case that Bob is here.”

p          | ~ p

T          | F

F          | T

 

2. Conjunction: p & q

Hint: for the conjunction to be true, both conjunts need to be true.

Example: “Bob is here and Joe is here.”

p          q          | p & q

T          T          | T

T          F          | F

F          T          | F

F          F          | F

 

3. Disjunction: p v q

Hint: for the disjunction to be true, either disjunct or both disjuncts need to be true (remember that “or” is inclusive).

Example: “I will eat an apple or I will eat a banana.”

p          q          | p v q

T          T          | T

T          F          | T

F          T          | T

F          F          | F

 

4. Conditional: p → q

Hint: there is no easy hint here, but remember that the consequent is the necessary condition in the conditional. Take the example below “If it rains then the sidewalk will be wet”. In line 4, when the necessary condition is false that "the sidewalk is wet", it is also false that "it is raining" and thus the whole conditional proposition is true. This is like an application of modus tollens. In line 2, when the necessary condition is false that "the sidewalk is wet", but in this case the it is true that "it is raining," this is like an application of fallacious modus tollens, in which case the whole conditional statement is false. Line 3 is the most difficult one to grasp. This suggests that if the necessary condition is true that "the sidewalk is wet" yet false that "it is raining" it is thereby true that "if it rains, the sidewalk will be wet". It is sort of like the falsity of the sufficient condition "it is raining" doesn't rule out the possibility that the sidewalk could be wet from other reasons.

Example: “If it rains then the sidewalk will be wet.”

p          q          | p → q

T          T          | T

T          F          | F

F          T          | T

F          F          | T

 

5. Biconditional: p ↔ q

Hint: for the biconditional to be true, both simple propositions need to have the same truth value.

Example: “Bob is a bachelor if and only if (iff) Bob is an unmarried man”

p          q          | p ↔ q

T          T          | T

T          F          | F

F          T          | F

F          F          | T

 

C. TRUTH TABLES FOR COMPLEX WFFS

 

1. Rules for truth tables of complex wffs

The column for any wff or subwff is always written under its main operator;

Circle the column under the main operator of the entire wff to show that the entries in it are the truth values for the whole formula.

Find the truth values for the smallest subwffs and then use the truth tables for the logical operators to calculate values for increasingly larger subffs, until you obtain the values for the whole wff.

 

2. Examples

 

Example: (p & q) v r

 

p          q          r           | p & q | (p & q) v r

T          T          T          | T        |            T

T          T          F          | T        |            T

T          F          T          | F        |            T

T          F          F          | F        |            F

F          T          T          | F        |            T

F          T          F          | F        |            F

F          F          T          | F        |            T

F          F          F          | F        |            F

 

Example: (p & q) v (p & r)

 

p          q          r           | p & q | p & r  | (p & q) v (p & r)

T          T          T          | T        | T        |            T

T          T          F          | T        | F        |            T

T          F          T          | F        | T        |            T

T          F          F          | F        | F        |            F

F          T          T          | F        | F        |            F

F          T          F          | F        | F        |            F

F          F          T          | F        | F        |            F

F          F          F          | F        | F        |            F

 

 

D. TAUTOLOGIES, INCONSISTENCIES, AND CONTINGENCIES

 

There are three possible configurations of T's and F's under the wff's main logical connective, and each has special names: tautology, inconsistency and contingency.

 

1. Tautology: each line is true under the main operator

Example: “Bob is here or it is not the case that Bob is here”

p          | ~ p     | p v ~p

T          | F        |    T

F          | T        |    T

 

2. Inconsistency: each line is false under the main operator

Example” “Bob is here and it is not the case that Bob is here”

p          | ~ p     | p & ~p

T          | F        |    F

F          | T        |    F

 

3. Contingency: some lines are true, others false, under the main operator

Example: “it is not the case that Bob is here”

p          | ~ p

T          | F

F          | T

 

E. DEMONSTRATING LOGICAL EQUIVALENCE OF WFFS

 

If two different wffs have the same truth value in their truth-tables, then they are logically equivalent

 

1. Example: logical equivalence of “p → q” and “~q → ~p”

 

“p → q” (“if it rains, then the sidewalk is wet”)

 

p          q          | p → q

T          T          |    T

T          F          |    F

F          T          |    T

F          F          |    T

 

“~q → ~p” (“if it is not the case that the sidewalk is wet then it is not the case that it is raining”)

 

p          q          | ~q      | ~p      | ~q → ~p

T          T          | F        | F        |       T

T          F          | T        | F        |       F

F          T          | F        | T        |       T

F          F          | T        | T        |       T

 

2. Example: logical equivalence of “~(p & ~q)” and “~p v q”

 

“~(p & ~q)” “It is not the case that (it is raining and it is not the case that the sidewalk is wet)”

 

p          q          | ~q      | p & ~q           | ~(p & ~q)

T          T          | F        | F                     |        T

T          F          | T        | T                     |        F

F          T          | F        | F                     |        T

F          F          | T        | F                     |        T

 

“~p v q” “it is not the case that it is raining or the sidewalk is wet”

 

p          q          | ~p      | ~p v q

T          T          | F        |     T

T          F          | F        |     F

F          T          | T        |     T

F          F          | T        |     T

 

3. Example: logical equivalence of “p ↔  q” and “(p →  q) & (q → p)” and “(p & q ) v (~p & ~q)”

 

“p ↔  q” “Bob is a bachelor iff Bob is an unmarried man”

p          q          | p ↔  q

T          T          |    T

T          F          |    F

F          T          |    F

F          F          |    T

 

“(p → q) & (q → p)” “(If Bob is a bachelor then Bob is an unmarried man) and (If Bob is an unmarried man then Bob is a bachelor)”

 

p          q          | p→q  | q→p  | (p→q)&(q→p)

T          T          | T        | T        |            T

T          F          | F        | T        |            F

F          T          | T        | F        |            F

F          F          | T        | T        |            T

 

“(p & q ) v (~p & ~q)” “(Bob is a bachelor and Bob is an unmarried man) or (it is not the case that Bob is a bachelor and it is not the case that Bob is an unmarried man)”

 

p          q          | ~p      | ~q      | p&q   | ~p&~q           | (p&q)v(~p&~q)

T          T          | F        | F        | T        | F                     |            T

T          F          | F        | T        | F        | F                     |            F

F          T          | T        | F        | F        | F                     |            F

F          F          | T        | T        | F        | T                     |            T

 

F. ARGUMENT FORMS

 

1. Terms

Informal logic: the study of particular arguments in natural language and the contexts in which they occur (argument diagrams, fallacies).

Formal logic: the study of argument forms, abstract patterns common to many different arguments.

Valid deductive argument: an argument whose conclusion cannot be false while the premises are all true.

Invalid deductive arguments are arguments which purport to be deductive but in fact are not.

Soundness: a valid deductive argument with all true premises.

Propositional logic: the study of the logical concept of validity insofar as this is due to the truth-functional operators (i.e., logical connectives such as “and”, “or”, “not”, “if-then” “if and only if” that have a consistent truth value.

Sentence letters: P, Q, R, place holders for declarative sentences.

 

2. Four common deductively valid argument forms

In formal propositional logic, the conclusion of an argument is typically designated by either the symbol “˫” or “:.”, which are read as “therefore". We will use the first of these here, which is called the "turnstile". The four valid argument forms below (and their corresponding fallacies) are presented in greater detail in the Logic Overview. They are presented here as a review in preparation for the discussion of truth tables for argument forms which follows.

Modus ponens

p → q

p

˫ q

Modus tollens

p → q

~q

˫ ~p

Disjunctive syllogism

p v q

~p

˫ Q

Hypothetical syllogism

p → q

q → r

:. p → r

 

3. Three common fallacies: deductively invalid argument forms

Fallacious modus ponens (fallacy of affirming the consequent)

p → q

q

:. p

Fallacious modus tollens (fallacy of denying the antecedent)

p → q

~p

:. ~q

Fallacious disjunctive syllogism (fallacy of asserting an alternative)

p v q

p

:. ~q

 

G. TRUTH TABLES FOR ARGUMENT FORMS

 

Rules:

Display each premise and conclusion as a separate wff on the top

The argument is valid when, for every row where all premises are true, the conclusion in all of those rows are also true. But if a conclusion in any one of those selected rows is false, the argument is invalid. This technique for validity follows the above definition of a valid deductive argument: "an argument whose conclusion cannot be false while the premises are all true."

 

1. Example: disjunctive syllogism

p          q          | p v q, ~p        ˫q

T          T          | T        F          T

T          F          | T        F          F

F          T          | T        T          T

F          F          | F        T          F

 

This is valid since only row 3 has true premises, and the conclusion of row 3 is also true.

 

2. Example: fallacious disjunctive syllogism

p          q          | p v q, p          ˫~q

T          T          | T        T          F

T          F          | T        T          T

F          T          | T        F          F

F          F          | F        F          T

 

This is invalid since both rows 1 and 2 have true premises, but the conclusion in row 1 is false. It does not matter that the conclusion in row 2 is true; this is an all or nothing situation where one defective row makes the entire argument form invalid.

 

H. REFUTATION TREES (bonus material, not included on test)

 

General

Refutation trees are alternatives to truth tables for demonstrating the validity of arguments; they are shorter but conceptionally more challenging

Main intuition: if an argument is valid, and you negate its conclusion, then contradictions should arise everywhere. Similarly, if an argument is invalid when you negate its conclusion, then you will find at least one non-contradictory option

Easy example: p v q, ~ p ˫ q  (valid DS)

“p v  q, ~ p ˫ ~ q” (negated conclusion)

p in premise 1 is contradicted by ~p in premise 2, and q in premise 1 is contradicted by ~q in the conclusion

All options in the premises are contradicted when negating the conclusion, thus the original argument is valid

Easy example: p v q, p ˫ ~q  (invalid DS)

“p v  q, p ˫ ~~ q” (negated conclusion)

p in premise 1 is not contradicted by p in premise 2, and q in premise 1 is not contradicted by ~~q in the conclusion

All options in the premises are un-contradicted when negating the conclusion, thus the original argument is invalid

Closed and open paths

Closed path: one which ends in a contradiction and is designated with an X

Open path: one that ends with a consistency and is designated with an !

Basic point: if all paths are closed (i.e., contradictory), then the original version is valid; if any path remains open (i.e., consistency), then the original version is invalid

Basic rules

Begin working on non-branching paths

All branching paths must be converted into either disjunctions or conjunctions, and each path must terminate in a contradiction for the argument to be valid

Conditional: convert to disjunction using “material implication” rule (p → q) ↔ (~p v q)

Biconditional: convert to two conjunction using the “material equivalence” rule (p ↔ q) ↔ [(p & q) v (~p & ~q)]

Negated conjunction: convert to disjunction using “De Morgan” rule ~(p & q) ↔ (~p v ~q)

Negated disjunct: convert to conjunction using “De Morgan” rule ~(p v q) ↔ (~p & ~q)

Negated conjunction: convert to conjunction using mystery rule ~(p → q) ↔ (p & ~q)

Negated biconditional: convert to two conjunctions using mystery rule ~(p ↔ q) ↔ [(p & ~q) v (~p & q)]

Explanation as appears in John Nolt's book Logic

Main description

Refutation trees provide a more efficient algorithm than truth tables for determining an argument’s validity

A refutation tree is an analysis in which a list of statements is broken down into sentence letters or their negations, which represent ways in which the members of the original list may be true. Since the ways in which a statement may be true depend on the logical operators it contains, formulas containing different logical operators are broken down differently.

All wffs containing logical operators fall into one of the following ten categories:

Negation — Negated negation

Conjunction  — Negated conjunction

Disjunction  — Negated disjunction

Conditional  — Negated conditional

Biconditional  — Negated biconditional

Steps

Construct a list consisting of its premises and the negation of its conclusion.

Break down the wffs on the list into sentence letters or their negations.

If we find any assignment of truth and falsity to sentence letters which makes all the wffs on the list true, then under that assignment the premises of the form are true while its conclusion is false. Thus we have refuted the argument form; it is invalid.

If the search turns up no assignment of truth and falsity to sentence letters which makes all the wffs on the list true, then our attempted refutation has failed; the form is valid.

Refutation Tree Rules

Negation (~): If an open path contains both a formula and its negation, place an “x” at the bottom of the path.

Negated Negation(~~): If an open path contains an unchecked wff of the form ~~p, check it and write p at the bottom of every open path that contains this newly checked wff.

Conjunction (&): If an open path contains an unchecked wff of the form p&q, check it and write p and q at the bottom of every open path that contains this newly checked wff.

Negated Conjunction (~&): If an open path contains an unchecked wff of the form ~(p&q), check it and split the bottom of each open path containing this newly checked wff into two branches, at the end of the first of which write ~p and at the end of the second of which write ~q.

Disjunction (v): If an open path contains an unchecked wff of the form pVq, check it and split the bottom of each open path containing this newly checked wff into two branches, at the end of the first of which write p and at the end of the second of which write q.

Negated Disjunction (~v): If an open path contains an unchecked wff of the form ~(p v q), check it and write both ~p and ~q at the bottom of every open path that contains this newly checked wff.

Conditional (→): If an open path contains an unchecked wff of the form p→q, check it and split the bottom of each open path containing this newly checked wff into two branches, at the end of the first of which write ~p and at the end of the second of which write q.

Negated Conditional ~(→): If an open path contains an unchecked wff of the form ~(p→q), check it and write both p and ~q at the bottom of every open path that contains this newly checked wff.

Biconditional (↔): If an open path contains an unchecked wff of the form p↔q, check it and split the bottom of each open path containing this newly checked wff into two branches, at the end of the first of which write both p and q, and at the end of the second of which write both ~p and ~q.

Negated Biconditional (~↔): If an open path contains an unchecked wff of the form ~(p↔q), check it and split the bottom of each open path containing this newly checked wff into two branches, at the end of the first of which write both p and ~q, and at the end of the second of which write both ~p and q.

 

Refutation Tree examples for conjunction

Instructions: Complete the refutation trees below for conjunction. At the end of each path, indicate that the path is closed with an X or open with an !,. Write “valid” or “invalid” in the final line. In brackets, explain your work for each step.

 

(1) Example

1. A & B / ˫ A

2. ~A [negated conclusion]

Path 1

3. A [from 1]

4. B [from 1]

x [2, 3 conflict]

Valid [path closed]

 

(2) Construct 1 path.

1. A & B

2. ~A / ˫ B

3. ~ B [negated conclusion]

Path 1

4. A [from 1]

5. B [from 1]

x [2, 4 conflict, 3, 5 conflict]

Valid [path closed]

 

(3) Construct 1 path.

1. A & B

2. A / ˫ ~B

3. B [negated conclusion]

Path 1

4. A [from 1]

5. B [from 1]

! [2, 4 consistency, 3, 5 consistency]

Invalid [path open]

 

Refutation Tree examples for disjunction

Instructions: Complete the refutation trees below for disjunction.

 

(1) Example

1. A v B

2. ~A / ˫ B

3. ~B [negated conclusion]

Path 1

4. A [from 1]

x [2, 4 conflict]

Path 2

5. B [from 1]

x [3, 5 conflict]

Valid [paths 1 and 2 closed]

 

(2) Construct two paths.

1. A v B

2. A / ˫ ~B

3. B [negated conclusion]

Path 1

4. A [from 1]

! [2, 4 consistency]

Path 2

5. B [from 1]

! [3, 5 consistency]

Invalid [paths 1 and 2 open]

 

Refutation Tree examples for conjunction

Instructions: Complete the refutation trees below for conditional.

 

(1) Example

1. A → B

2. A / ˫ B

3. ~B [negated conclusion]

4. ~A v B [1, MI]

Path 1

5. ~A [from 4]

x [2, 5 conflict]

Path 2

6. B [from 4]

x [3, 6 conflict]

Valid [paths 1 and 2 closed]

 

(2) Construct two paths.

1. A → B

2. ~B / ˫ ~A

3. ~A [negated conclusion]

4. ~A v B [1, MI]

Path 1

5. ~A [from 4]

! [3, 5 consistency]

Path 2

6. B [from 4]

! [2, 6 consistency]

Invalid [paths 1 and 2 open]

 

(3) Construct three paths.

1. A → B

2. B → C

3. A / ˫ C

3. ~C [negated conclusion]

4. ~A v B [1, MI]

5. ~B v C [2, MI]

Path 1

6. ~A [from 4]

x [3, 6 conflict]

Path 2

7. B [from 4]

x [5, 7 conflict]

Path 3

8. C [from 5]

X [3, 8 conflict]

Valid [paths 1, 2 and 3 closed]

 

(4) Construct three paths.

1. H → I

2. I → J

3. ~H / ˫ J

3. ~J [negated conclusion]

4. ~H v I [1, MI]

5. ~I v J [2, MI]

Path 1

6. ~H [from 4]

! [3, 6 consistency]

Path 2

7. I [from 4]

x [5, 7 conflict]

Path 3

8. J [from 5]

x [3, 8 conflict]

Invalid [path 1 open]