Propositional Logic

​

​

​

1

• This is the second and last formal system of logic that we will learn in this course.
• This system is important because it is more powerful than categorical logic and is the basis of computing language.

2

Language for Propositional Logic

• Simple propositions are the simplest propositions that do not contain any other proposition as a component part.
• E.g. Today is Monday.

​

• Simple propositions can be combined to give compound propositions using logical operators.
• E.g. Jane is married and she is pregnant.

It is not the case that Jacky is present.

I will die if I quit my job.

Either Mary is a liar or John misunderstood her.

3

Propositional Variables and Logical Operators

• We use propositional variables (e.g. P, Q, R, …) to represent simple propositions.

​

• Five logical operators:

1) ~ negation (not, it is not the case that)

2) • conjunction (and, but, also)

3) ∨ disjunction (or, unless)

4) ⊃ implication (if-then, only if)

5) ≡ equivalence (if and only if, just in case)

​

4

Logical Operators

• Logical operators join the propositional variables into a logically meaningful compound proposition.

​

Example

It is not the case that P ~P

Q and R (Q • R)

Either R or S (R ∨ S)

If P then Q (P ⊃ Q)

R if and only if S (R ≡ S)

​

5

Formation Rules

• A well-formed formula (wff) is a proposition that formed according to the formation rules of PC.

​

• We use P, Q, R,… to represent propositional variables and α, β, γ,… to represent wffs.

​

• The formation rules of PC aim to state what is, and what is not, grammatical in PC. Please make sure that every formula you write in PC is a wff.

6

Formation Rules

• Rule 1: Every propositional variable is a wff.
• Rule 2: If α is a wff, then ~α is a wff.
• Rule 3: If α and β are wff s, then (α • β) is a wff.
• Rule 4: If α and β are wff s, then (α ∨ β) is a wff.
• Rule 5: If α and β are wff s, then (α ⊃ β) is a wff.
• Rule 6: If α and β are wff s, then (α≡β) is a wff.
• Rule 7: No other expression is a wff.

​

• For the sake of simplicity, the outermost pair of parentheses is omitted.

7

Logical Operators

• “~” is an unary operator with exactly one wff input and is placed in front of a formula.

​

• “•”, “∨”, “⊃”, and “≡” are binary operators with exactly two wff inputs and are placed between formulas.

​

• “•”, “∨” and “≡” are commutative operators, but not “⊃”.
• (α • β) = (β • α)
• (α ∨ β) = (β ∨ α)
• (α≡ β) = (β ≡α)
• However, (α ⊃ β) ≠ (β ⊃ α).

8

Main Operator and Parenthesis

• The main operator of a wff is the last operator to calculate in determining the truth value of the wff .
• In mathematics, “×” is the main operator in 4 × (3 + 2).
• In logic, “•” is the main operator in P • (R ∨ S).

​

• Parentheses aim to avoid ambiguity.
• E.g. (P • Q ∨ R) is not a wff because it can be expressed as
• (P • Q) ∨ R, or
• P • (Q ∨ R)

which have different truth conditions.

9

Truth-functionality

• The 5 operators are truth-functional.
• A operator is truth functional =df given the same inputted truth value, the outputted truth value governed by the operator will remain the same.
• Motto: same value input, same value output.

​

• Many of the operators in our daily life are non-truth-functional.
• “Because”, “it is necessary that”, “causes” etc.

10

Example

α : Today is a schoolday (T)

β : Today is not Sunday (T)

γ : 1 + 1 = 2 (T)

​

• Given that α and β are true, (α • β) is true.
• Since β and γ have the same truth value, by substituting β with γ, the truth value of (α • γ) is true also.

​

• Suppose that “α because β” is true.
• Even though β and γ have the same truth value, by substituting β with γ, the truth value of “α because γ” is false.

11

Translation

• Theoretically speaking, all statements in natural language can be translated into formulas in PC without any significant loss in meaning.

​

• However, many pragmatic factors (e.g. moods and implicatures) are neglected in the translation process.

​

• Negation is probably the one closest to our daily use. Let’s skip the discussion of it.

12

Conjunction “•”

• Conjunction means the obtaining of truth for both conjuncts. “But” in English performs a similar function as a conjunction.

​

• “John left early but Mary stayed” means “John left early” and “Mary stayed” are true respectively.

​

• Conjunction in PC neglects any temporal order between the conjuncts.
• “Jane got pregnant and Jane got married.”
• “Jane got married and Jane got pregnant.”

13

Disjunction “∨”

• Disjunction is read as inclusive in PC. That is, there are 3 cases when affirming the formula (α ∨ β):

(1) affirming α but denying β,

(2) denying α but affirming β, and

(3) affirming both α and β.

​

• So, to deny the formula (α ∨ β) is to deny both α and β.

​

• “Unless” can be expressed as a disjunction.
• “Unless you work hard, you will fail”

= “You work hard, or you will fail”.

14

Material Implication “⊃”

• Material implication is similar, but not identical, to the English “if-then”. As noted by many logicians, there are various kinds of conditional statements in which some of them are non-truth-functional. Indeed, “⊃” is quite different from the one in our daily usage.

​

• However, in our course, we will merely consider the indicative kind of conditionals which is truth-functional.
• α is the antecedent of the conditional (α ⊃ β), and
• β is the consequent of the conditional (α ⊃ β).

​

• “α only if β” / “α implies β” = (α ⊃ β)
• “Only if α, β” / “α on condition that β” = (β ⊃ α)

15

Sufficient Condition

• (α ⊃ β) means that α is a sufficient condition for β.
• α is the one that leads to β’s occurrence.
• However, even if α does not occur, it does NOT mean that β fails to occur.

​

Example

• A good DSE result is a sufficient condition to get an offer.
• However, one could have earned an offer without having a good DSE result (e.g. a high GPA in SPACE).

16

Necessary Condition

• (α ⊃ β) means that β is a necessary condition for α.
• Without β, α will not occur.
• However, even if β occurs, it does NOT guarantee that α occurs.

​

Example

• Water is a necessary condition for our survival. Without it, we will all die.
• However, water itself cannot guarantee our survival (e.g. when you have no food).

​

17

Material Equivalence “≡”

• (α ≡ β) means that the truth conditions for α and β must be identical, and is understood as the combination of (α ⊃ β) and (β ⊃ α). In English, we use “… just in case…” to mean “… if and only if… ”.

​

• On top of that, (α ≡ β) also means that the truth values for α and β are the same.

18

Truth Tables

• The input-output relationship of the 5 logical operators are completely determined by their respective truth-table definitions.

​

• We can then compute the truth value of any wff once we have the truth value of its components.

19

Negation

20

Conjunction

21

Disjunction

22

Material Implication

23

Material Implication

• Note that when α is F, no matter whether β is T or F, α ⊃ β is T.

​

• It is common that you cannot understand why it should be defined in this particular way at first.
• However, the definition is actually provable. See Aside.

​

• For the time being, simply take it as a logicians’ tradition.

24

Material Equivalence

25

Applications

• We use the 5 definitions to compute the truth values of any compound proposition.

​

• Step 1: Assign propositional variables to simple propositions without duplication.

​

• Step 2: Translate by joining propositional variables with logical operators and insert parentheses if required.

​

• Step 3: Assign truth values to each propositional variable.

​

• Step 4: Compute the truth value from the innermost formula until the one under the main operator.

26

Example

• (P ∨ Q) ⊃ R
• Suppose that P is true, Q and R are false:

​

​

27

Complete Truth Table for wff s

• The previous method works because there is a value assignment to each propositional variable.

​

• On the contrary, if we want to know the truth value of a wff in each logical possibility, we need to exhaust all the different combinations of truth values of its constituting propositional variables.

28

Complete Truth Table for wff s

• One row = one logical possibility
• The number of rows are governed by the rule 2ⁿ. That is, if there are 2 propositional variables, there are 4 rows; 3 propositional variables, then 8 rows; and so on.

​

• The rule of truth assignment is to alternate at the right-most column of the propositional variables, then alternate pairs for the next column and so on. In this way, we need not worry about omission or repetition of truth assignment.

​

• After inputting the combination of truth assignment, we can compute the truth value of any wff.

29

Example

30

Procedures

1. Draw a cross that divides the space into four quadrants.
2. Put the wff to be solved in the upper right quadrant.
3. Extract the propositional variables and order them in alphabetical order in the left upper quadrant.
4. List out the truth assignments for the propositional variables line by line in the lower left quadrant.
5. Compute the truth values of the logical operators one by one in the right lower quadrant

31

Properties of Propositions

• α is a tautology

=df α is true in every logical possibility.

​

• α is a self-contradiction

=df α is false in every logical possibility.

​

• α is a contingent proposition

=df α is true in at least one logical possibility and

is false in at least one logical possibility.

​

​

32

Tautology

33

Self-Contradiction

34

Contingent Proposition

35

Relations of Propositions

• α and β are logically equivalent

=df α and β have the same truth value in every logical possibility.

​

• α and β are contradictory

=df α and β have different truth values in every logical possibility.

​

• α and β are consistent

=df there is at least one logical possibility that α and β are both true.

​

• α and β are inconsistent

=df there is no logical possibility that α and β are both true.

36

Equivalence

37

Contradiction

38

Consistency

39

Inconsistency

40

Truth Table for Arguments

• An argument is valid =df it is logically impossible that all premises are true but the conclusion is false.

​

• So the key question is:

​

​

41

Is there a row in which all premises are true and the conclusion is false in the complete truth table?

Invalid

Valid

YES

NO

Truth Table for Arguments

• The four quadrants are almost the same for determining the truth value of a formula in each logical possibility.

​

• The only difference is that, for the top right quadrant, we state every formula of the argument instead of a single formula.
• Use “ / ” to separate the premises
• Use “// ” to separate the last premise and the conclusion

42

Example – Valid Argument

43

Example – Invalid Argument

44

Indirect Truth Table

• If there are many propositional variables involved, the table will be large and time-consuming to construct. But all we want to know is whether there is at least one truth assignment showing the argument as invalid, that is, to find a counterexample.

​

• Indirect truth table is a shortcut method of spotting counterexample.

​

• **IMPORTANT** Assume that the argument is invalid.

​

• Next, we work backward to obtain truth values for each component.

​

• If there is a contradiction somewhere in the filling process, the argument is valid; and invalid if otherwise.

45

Example 1

~P ⊃ (Q ∨ R)

~Q

R ⊃ P

​

• Step 1: Assign the premises as true and the conclusion as false by assuming the argument as invalid.

​

​

46

Example 1

• Step 2: Fill in the blanks one by one.

​

​

​

​

• As there appears no contradiction, the argument is invalid due to the logical possibility {P:F, Q:F, R:T}.

47

Counterexample

Example 2

Q ≡ R

P ⊃ Q

~R ⊃ ~P

​

• Step 1: Assign the premises as true and the conclusion as false by assuming the argument as invalid.

​

​

48

Example 2

• Step 2: Fill in the blanks one by one.

​

​

​

​

• As there is a contradiction aroused in the filling process, the argument is valid.
• The contradiction you find can be different from mine.

49

Example 2

• An alternative filling order for the same argument:

​

​

​

​

50

Testing for Consistency

• We can also use indirect truth table to check whether a set of wffs are consistent.

​

• **IMPORTANT** Assume that the given wffs are consistent.

​

• If no contradiction is seen, they are consistent; if there is a contradiction somewhere in the filling process, they are inconsistent.

​

51

Example

• P ∨ Q
• Q ⊃ (R ∨ P)
• R ⊃ ~Q
• S ∙ ~P

​

• Step 1: We assign all wffs as true by assuming their consistency.

​

​

​

52

Example

• Step 2: Fill in the blanks one by one.

​

​

​

​

• As a contradiction arises, they are inconsistent.

53

Multiple Ways of Filling

• Sometimes, some boxes are difficult to be filled because we cannot determine whether they should be marked as T or F.

​

• Let say the value of P is what we cannot determine. We have to ASSUME arbitrarily that it is T (or F). If there is no contradiction shown, we satisfy the initial assumption (i.e. the argument is invalid / the wffs are consistent).

​

• If there is a contradiction shown, we CANNOT claim that we have falsified the initial assumption. We have to discharge the assumption that P is T (or F) and claim that P is F (or T) instead. If there is no contradiction shown this time, we satisfy the initial assumption. If there is a contradiction again, then the initial assumption fails.

54

Example

P ⊃ (Q ⊃ R)

R ⊃ S

~(P ∙ Q) ⊃ R

S ∙ P

​

• Step 1: Assign the premises as true and the conclusion as false by assuming that the argument is invalid.

​

​

​

55

Example

• However, for each premise and the conclusion, there are multiple ways of filling the remaining boxes.

​

• Step 2: We arbitrary assume that P is true.

56

Example

• Now we have to withdraw our last assumption that P is true. Therefore, P is false.

​

​

​

57

Example

​

​

​

​

• We can fill in many boxes this time. But for Q, we cannot tell whether it is a T or a F. Let say we start one more assumption that Q is T.

​

​

58

Example

​

​

​

​

• So now we come up with a completed indirect truth table without contradiction. So the argument is invalid and the counterexample is {P:F, Q:T, R:T, S:F}.
• You can also go back to the previous slide and see that assuming Q as F will lead to another counterexample.

​

​

59