CS285 · Chapter 1 · Annotated SlidesLogic and Proofs
Original
Overview

Logic and Proofs

Propositions and connectives, truth tables, implication and its converse / inverse / contrapositive, translating English, consistent specifications, logical equivalences and De Morgan, satisfiability, predicates and quantifiers (and negating them), nested quantifiers, and the rules of inference including resolution.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 132 slides
  1. 1 Slide 1
  2. 2 Chapter Summary
  3. 3 Propositional Logic Summary
  4. 4 Slide 4
  5. 5 Section Summary
  6. 6 Logic
  7. 7 C++ Example
  8. 8 Propositions
  9. 9 Propositional Logic
  10. 10 Conjunction
  11. 11 Disjunction
  12. 12 The Connective Or in English
  13. 13 Negation
  14. 14 Implication
  15. 15 Understanding Implication
  16. 16 Understanding Implication (cont)
  17. 17 Understanding Implication (cont)
  18. 18 Different Ways of Expressing p q
  19. 19 Converse, Contrapositive, and Inverse
  20. 20 Converse, Contrapositive, and Inverse
  21. 21 Biconditional
  22. 22 Biconditional vs Exclusive Or
  23. 23 Expressing the Biconditional
  24. 24 Truth Tables For Compound Propositions
  25. 25 Example Truth Table
  26. 26 Example Truth Table
  27. 27 Slide 27
  28. 28 Slide 28
  29. 29 Equivalent Propositions
  30. 30 Using a Truth Table to Show Non-Equivalence
  31. 31 Problem
  32. 32 Precedence of Logical Operators
  33. 33 Slide 33
  34. 34 Slide 34
  35. 35 Applications of Propositional Logic: Summary
  36. 36 Translating English Sentences
  37. 37 Example
  38. 38 System Specifications
  39. 39 Consistent System Specifications
  40. 40 Consistent System Specifications
  41. 41 Consistent System Specifications
  42. 42 Consistency and Inconsistency
  43. 43 Raymond Smullyan
  44. 44 Logic/digital Circuits
  45. 45 Slide 45
  46. 46 Section Summary
  47. 47 Tautologies, Contradictions, and Contingencies
  48. 48 Logically Equivalent
  49. 49 Logically Equivalent
  50. 50 Logically Equivalent
  51. 51 De Morgan’s Laws
  52. 52 Key Logical Equivalences
  53. 53 Key Logical Equivalences ( cont )
  54. 54 More Logical Equivalences
  55. 55 Constructing New Logical Equivalences
  56. 56 Equivalence Proofs
  57. 57 Equivalence Proofs
  58. 58 Equivalent Propositions
  59. 59 Slide 59
  60. 60 Slide 60
  61. 61 Derivational Proof Techniques
  62. 62 Slide 62
  63. 63 Solution
  64. 64 Propositional Satisfiability
  65. 65 Questions on Propositional Satisfiability
  66. 66 Slide 66
  67. 67 Section Summary
  68. 68 Propositional Logic Not Enough
  69. 69 Introducing Predicate Logic
  70. 70 Introducing Predicate Logic
  71. 71 Introducing Predicate Logic
  72. 72 Propositional Functions
  73. 73 Examples of Propositional Functions
  74. 74 Compound Expressions
  75. 75 Quantifiers
  76. 76 Universal Quantifier ( ) 
  77. 77 Existential Quantifier( ) 
  78. 78 Uniqueness Quantifier ( optional )
  79. 79 Thinking about Quantifiers
  80. 80 Properties of Quantifiers
  81. 81 Precedence of Quantifiers
  82. 82 Predicates & Quantifiers
  83. 83 Socrates Example
  84. 84 Translating from English to Logic
  85. 85 Translating from English to Logic
  86. 86 Equivalences in Predicate Logic
  87. 87 Thinking about Quantifiers as Conjunctions and Disjunctions
  88. 88 Negating Quantified Expressions
  89. 89 Negating Quantified Expressions ( continued )
  90. 90 De Morgan’s Laws for Quantifiers
  91. 91 Multiple Quantifiers
  92. 92 Multiple Quantifiers
  93. 93 Multiple Quantifiers
  94. 94 Translation from English to Logic
  95. 95 Some Fun with Translating from English into Logical Expressions
  96. 96 Translation (cont)
  97. 97 Translation (cont)
  98. 98 Translation (cont)
  99. 99 Translation (cont)
  100. 100 Translation
  101. 101 Solution:
  102. 102 Example
  103. 103 Slide 103
  104. 104 Rules of Inference
  105. 105 Valid Arguments in Propositional Logic
  106. 106 Valid Arguments in real life!
  107. 107 Valid Arguments in Propositional Logic
  108. 108 Valid Arguments in Propositional Logic
  109. 109 Valid Arguments in Propositional Logic
  110. 110 Valid Arguments in Propositional Logic
  111. 111 The 1
  112. 112 modus ponens
  113. 113 Rules of Inference for Propositional Logic
  114. 114 The rules of inference
  115. 115 Modus Ponens
  116. 116 Modus Tollens
  117. 117 Hypothetical Syllogism
  118. 118 Disjunctive Syllogism
  119. 119 Addition
  120. 120 Simplification
  121. 121 Conjunction
  122. 122 Resolution
  123. 123 Using the rules of inference to build arguments
  124. 124 An example
  125. 125 Using the rules of inference to build arguments An example
  126. 126 Using the resolution rule (an example)
  127. 127 Using the resolution rule (an example)
  128. 128 Example
  129. 129 Continue
  130. 130 Another view on what we are doing
  131. 131 Rule of inference Tautology Name p q  p [ p  ( p  q )]  q Modusponens
  132. 132 Example
Slide 1 / 132

Slide 1

Slide 1: Slide 1
Slide 2 / 132

Chapter Summary

Slide 2: Chapter Summary

Notes

  1. Tip p → q is FALSE only when p is true and q is false. Same as ¬p ∨ q, and as its contrapositive ¬q → ¬p.

Slide 3 / 132

Propositional Logic Summary

Slide 3: Propositional Logic Summary
Slide 4 / 132

Slide 4

Slide 4: Slide 4
Slide 5 / 132

Section Summary

Slide 5: Section Summary
Slide 6 / 132

Logic

Slide 6: Logic
Slide 7 / 132

C++ Example

Slide 7: C++ Example
Slide 8 / 132

Propositions

Slide 8: Propositions

Notes

  1. A proposition is a declarative sentence that is either true or false, not both. Questions, commands and "x + 1 = 2" (x unknown) are NOT propositions.

Exam angle

PredictionQ1

Which of these is a proposition?

Slide 9 / 132

Propositional Logic

Slide 9: Propositional Logic
Slide 10 / 132

Conjunction

Slide 10: Conjunction

Notes

  1. p ∧ q (and) is true only when both are true.

Slide 11 / 132

Disjunction

Slide 11: Disjunction

Notes

  1. p ∨ q (inclusive or) is false only when both are false.

Slide 12 / 132

The Connective Or in English

Slide 12: The Connective Or in English

Exam angle

PredictionQ1

p ⊕ q is true when:

Slide 13 / 132

Negation

Slide 13: Negation
Slide 14 / 132

Implication

Slide 14: Implication

Notes

  1. p → q is FALSE only when p is true and q is false. Same as ¬p ∨ q, and as its contrapositive ¬q → ¬p.

  2. Readings: "if p then q", "p only if q", "q whenever p", "q is necessary for p", "p is sufficient for q".

  3. Trap "p only if q" is p → q, NOT q → p.

Exam angle

PredictionQ1

When is p → q false?

PredictionQ2

If p is false, p → q is true no matter what q is.

Slide 15 / 132

Understanding Implication

Slide 15: Understanding Implication
Slide 16 / 132

Understanding Implication (cont)

Slide 16: Understanding Implication (cont)
Slide 17 / 132

Understanding Implication (cont)

Slide 17: Understanding Implication (cont)
Slide 18 / 132

Different Ways of Expressing p q

Slide 18: Different Ways of Expressing p q

Notes

  1. From p → q: converse q → p, inverse ¬p → ¬q, contrapositive ¬q → ¬p.

  2. Only the contrapositive is equivalent to the original; the converse and inverse are equivalent to each other.

  3. Memory trick CONtrapositive = CONverse + inverse together (swap AND negate).

Exam angle

PredictionQ1

The contrapositive of "If it rains, then I stay home" is:

PredictionQ2

An implication is logically equivalent to its converse.

Slide 19 / 132

Converse, Contrapositive, and Inverse

Slide 19: Converse, Contrapositive, and Inverse
Slide 20 / 132

Converse, Contrapositive, and Inverse

Slide 20: Converse, Contrapositive, and Inverse
Slide 21 / 132

Biconditional

Slide 21: Biconditional

Notes

  1. p ↔ q is true when p and q have the SAME truth value ("if and only if", "necessary and sufficient").

Exam angle

PredictionQ1

p ↔ q is equivalent to:

Slide 22 / 132

Biconditional vs Exclusive Or

Slide 22: Biconditional vs Exclusive Or

Notes

  1. p ↔ q is the negation of p ⊕ q.

Slide 23 / 132

Expressing the Biconditional

Slide 23: Expressing the Biconditional
Slide 24 / 132

Truth Tables For Compound Propositions

Slide 24: Truth Tables For Compound Propositions

Exam angle

PredictionQ1

How many rows does the truth table of a proposition with 4 variables have?

Slide 25 / 132

Example Truth Table

Slide 25: Example Truth Table
Slide 26 / 132

Example Truth Table

Slide 26: Example Truth Table
Slide 27 / 132

Slide 27

Slide 27: Slide 27
Slide 28 / 132

Slide 28

Slide 28: Slide 28
Slide 29 / 132

Equivalent Propositions

Slide 29: Equivalent Propositions
Slide 30 / 132

Using a Truth Table to Show Non-Equivalence

Slide 30: Using a Truth Table to Show Non-Equivalence
Slide 31 / 132

Problem

Slide 31: Problem
Slide 32 / 132

Precedence of Logical Operators

Slide 32: Precedence of Logical Operators

Notes

  1. Precedence: ¬ first, then ∧, then ∨, then →, then ↔. So p ∨ q → ¬r means (p ∨ q) → (¬r).

Exam angle

PredictionQ1

p ∧ q ∨ r is read as:

Slide 33 / 132

Slide 33

Slide 33: Slide 33
Slide 34 / 132

Slide 34

Slide 34: Slide 34
Slide 35 / 132

Applications of Propositional Logic: Summary

Slide 35: Applications of Propositional Logic: Summary
Slide 36 / 132

Translating English Sentences

Slide 36: Translating English Sentences

Notes

  1. Translate: pick atomic propositions, then join them with connectives. "You can access the Internet only if you are a CS major or not a freshman" → a → (c ∨ ¬f).

Slide 37 / 132

Example

Slide 37: Example
Slide 38 / 132

System Specifications

Slide 38: System Specifications
Slide 39 / 132

Consistent System Specifications

Slide 39: Consistent System Specifications

Notes

  1. A set of specifications is consistent if ONE assignment of truth values makes all of them true at the same time.

Exam angle

PredictionQ1

How do you check that a list of system specifications is consistent?

Compare with the model answer

Translate each into propositional logic and look for one truth assignment (a row of the truth table) that makes every specification true at once. If such a row exists the specs are consistent; if none exists they are inconsistent.

Slide 40 / 132

Consistent System Specifications

Slide 40: Consistent System Specifications
Slide 41 / 132

Consistent System Specifications

Slide 41: Consistent System Specifications
Slide 42 / 132

Consistency and Inconsistency

Slide 42: Consistency and Inconsistency
Slide 43 / 132

Raymond Smullyan

Slide 43: Raymond Smullyan
Slide 44 / 132

Logic/digital Circuits

Slide 44: Logic/digital Circuits

Notes

  1. Logic gates: inverter (¬), AND (∧), OR (∨); circuits compute compound propositions.

Slide 45 / 132

Slide 45

Slide 45: Slide 45
Slide 46 / 132

Section Summary

Slide 46: Section Summary
Slide 47 / 132

Tautologies, Contradictions, and Contingencies

Slide 47: Tautologies, Contradictions, and Contingencies

Exam angle

PredictionQ1

p ∨ ¬p is a:

PredictionQ2

(p → q) ∧ p ∧ ¬q is a:

Slide 48 / 132

Logically Equivalent

Slide 48: Logically Equivalent

Notes

  1. p ≡ q (logically equivalent) when p ↔ q is a tautology: same truth value in every row.

Slide 49 / 132

Logically Equivalent

Slide 49: Logically Equivalent
Slide 50 / 132

Logically Equivalent

Slide 50: Logically Equivalent
Slide 51 / 132

De Morgan’s Laws

Slide 51: De Morgan’s Laws

Notes

  1. De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q.

  2. Memory trick Negate each part and FLIP the operator.

Exam angle

PredictionQ1

¬(p ∨ q) is equivalent to:

Slide 52 / 132

Key Logical Equivalences

Slide 52: Key Logical Equivalences
Slide 53 / 132

Key Logical Equivalences ( cont )

Slide 53: Key Logical Equivalences ( cont )
Slide 54 / 132

More Logical Equivalences

Slide 54: More Logical Equivalences

Notes

  1. Implication laws: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p; p ↔ q ≡ (p → q) ∧ (q → p).

Slide 55 / 132

Constructing New Logical Equivalences

Slide 55: Constructing New Logical Equivalences
Slide 56 / 132

Equivalence Proofs

Slide 56: Equivalence Proofs

Notes

  1. Equivalence proof: rewrite step by step, naming the law used at each step (no truth table).

Exam angle

PredictionQ1

Show that ¬(p → q) ≡ p ∧ ¬q without a truth table.

Compare with the model answer

¬(p → q) ≡ ¬(¬p ∨ q) (implication law) ≡ ¬¬p ∧ ¬q (De Morgan) ≡ p ∧ ¬q (double negation).

Slide 57 / 132

Equivalence Proofs

Slide 57: Equivalence Proofs
Slide 58 / 132

Equivalent Propositions

Slide 58: Equivalent Propositions
Slide 59 / 132

Slide 59

Slide 59: Slide 59
Slide 60 / 132

Slide 60

Slide 60: Slide 60
Slide 61 / 132

Derivational Proof Techniques

Slide 61: Derivational Proof Techniques
Slide 62 / 132

Slide 62

Slide 62: Slide 62
Slide 63 / 132

Solution

Slide 63: Solution
Slide 64 / 132

Propositional Satisfiability

Slide 64: Propositional Satisfiability

Exam angle

PredictionQ1

A compound proposition is unsatisfiable exactly when its negation is a tautology.

Slide 65 / 132

Questions on Propositional Satisfiability

Slide 65: Questions on Propositional Satisfiability
Slide 66 / 132

Slide 66

Slide 66: Slide 66
Slide 67 / 132

Section Summary

Slide 67: Section Summary
Slide 68 / 132

Propositional Logic Not Enough

Slide 68: Propositional Logic Not Enough
Slide 69 / 132

Introducing Predicate Logic

Slide 69: Introducing Predicate Logic
Slide 70 / 132

Introducing Predicate Logic

Slide 70: Introducing Predicate Logic
Slide 71 / 132

Introducing Predicate Logic

Slide 71: Introducing Predicate Logic
Slide 72 / 132

Propositional Functions

Slide 72: Propositional Functions
Slide 73 / 132

Examples of Propositional Functions

Slide 73: Examples of Propositional Functions
Slide 74 / 132

Compound Expressions

Slide 74: Compound Expressions
Slide 75 / 132

Quantifiers

Slide 75: Quantifiers

Notes

  1. ∀x P(x): true when P(x) holds for EVERY x in the domain. ∃x P(x): true when it holds for AT LEAST ONE.

Slide 76 / 132

Universal Quantifier ( ) 

Slide 76: Universal Quantifier ( ) 

Notes

  1. One counterexample makes ∀x P(x) false.

Exam angle

PredictionQ1

Domain: all integers. ∀x (x² ≥ x) is:

Slide 77 / 132

Existential Quantifier( ) 

Slide 77: Existential Quantifier( ) 

Notes

  1. ∃x P(x) is false only when P(x) is false for every x. Over an empty domain ∃ is false and ∀ is true.

Slide 78 / 132

Uniqueness Quantifier ( optional )

Slide 78: Uniqueness Quantifier ( optional )
Slide 79 / 132

Thinking about Quantifiers

Slide 79: Thinking about Quantifiers
Slide 80 / 132

Properties of Quantifiers

Slide 80: Properties of Quantifiers
Slide 81 / 132

Precedence of Quantifiers

Slide 81: Precedence of Quantifiers

Notes

  1. ∀ and ∃ bind tighter than all connectives: ∀x P(x) ∨ Q(x) means (∀x P(x)) ∨ Q(x).

Slide 82 / 132

Predicates & Quantifiers

Slide 82: Predicates & Quantifiers
Slide 83 / 132

Socrates Example

Slide 83: Socrates Example
Slide 84 / 132

Translating from English to Logic

Slide 84: Translating from English to Logic

Notes

  1. Trap ∀ pairs with →, ∃ pairs with ∧. ∃x (S(x) → C(x)) is true as soon as one x is not a student.

Exam angle

PredictionQ1

Domain: all people. "Some students are lazy" is:

Slide 85 / 132

Translating from English to Logic

Slide 85: Translating from English to Logic
Slide 86 / 132

Equivalences in Predicate Logic

Slide 86: Equivalences in Predicate Logic
Slide 87 / 132

Thinking about Quantifiers as Conjunctions and Disjunctions

Slide 87: Thinking about Quantifiers as Conjunctions and Disjunctions
Slide 88 / 132

Negating Quantified Expressions

Slide 88: Negating Quantified Expressions

Notes

  1. ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x) (De Morgan for quantifiers).

  2. Memory trick Push ¬ inside and flip ∀ ↔ ∃.

Exam angle

PredictionQ1

¬∀x (x > 0) is equivalent to:

Slide 89 / 132

Negating Quantified Expressions ( continued )

Slide 89: Negating Quantified Expressions ( continued )
Slide 90 / 132

De Morgan’s Laws for Quantifiers

Slide 90: De Morgan’s Laws for Quantifiers
Slide 91 / 132

Multiple Quantifiers

Slide 91: Multiple Quantifiers

Notes

  1. Nested quantifiers: order matters when they differ. ∀x ∃y (x + y = 0) is true over the integers; ∃y ∀x (x + y = 0) is false.

Exam angle

PredictionQ1

Domain: integers. Which is TRUE?

Slide 92 / 132

Multiple Quantifiers

Slide 92: Multiple Quantifiers
Slide 93 / 132

Multiple Quantifiers

Slide 93: Multiple Quantifiers

Notes

  1. ∀x∀y and ∃x∃y can be swapped freely; ∀x∃y and ∃y∀x cannot.

Slide 94 / 132

Translation from English to Logic

Slide 94: Translation from English to Logic
Slide 95 / 132

Some Fun with Translating from English into Logical Expressions

Slide 95: Some Fun with Translating from English into Logical Expressions
Slide 96 / 132

Translation (cont)

Slide 96: Translation (cont)
Slide 97 / 132

Translation (cont)

Slide 97: Translation (cont)
Slide 98 / 132

Translation (cont)

Slide 98: Translation (cont)
Slide 99 / 132

Translation (cont)

Slide 99: Translation (cont)
Slide 100 / 132

Translation

Slide 100: Translation
Slide 101 / 132

Solution:

Slide 101: Solution:
Slide 102 / 132

Example

Slide 102: Example
Slide 103 / 132

Slide 103

Slide 103: Slide 103
Slide 104 / 132

Rules of Inference

Slide 104: Rules of Inference

Notes

  1. An argument is valid if the conclusion must be true whenever all premises are true (the conditional (p₁ ∧ … ∧ pₙ) → q is a tautology).

Slide 105 / 132

Valid Arguments in Propositional Logic

Slide 105: Valid Arguments in Propositional Logic
Slide 106 / 132

Valid Arguments in real life!

Slide 106: Valid Arguments in real life!
Slide 107 / 132

Valid Arguments in Propositional Logic

Slide 107: Valid Arguments in Propositional Logic
Slide 108 / 132

Valid Arguments in Propositional Logic

Slide 108: Valid Arguments in Propositional Logic
Slide 109 / 132

Valid Arguments in Propositional Logic

Slide 109: Valid Arguments in Propositional Logic
Slide 110 / 132

Valid Arguments in Propositional Logic

Slide 110: Valid Arguments in Propositional Logic
Slide 111 / 132

The 1

Slide 111: The 1
Slide 112 / 132

modus ponens

Slide 112: modus ponens
Slide 113 / 132

Rules of Inference for Propositional Logic

Slide 113: Rules of Inference for Propositional Logic
Slide 114 / 132

The rules of inference

Slide 114: The rules of inference
Slide 115 / 132

Modus Ponens

Slide 115: Modus Ponens

Exam angle

PredictionQ1

"If it snows, school closes. It snows. Therefore school closes." uses:

Slide 116 / 132

Modus Tollens

Slide 116: Modus Tollens

Notes

  1. Trap p → q, q ∴ p is the fallacy of affirming the conclusion; p → q, ¬p ∴ ¬q is denying the hypothesis. Neither is valid.

Exam angle

PredictionQ1

From p → q and ¬q we may conclude:

Slide 117 / 132

Hypothetical Syllogism

Slide 117: Hypothetical Syllogism
Slide 118 / 132

Disjunctive Syllogism

Slide 118: Disjunctive Syllogism

Exam angle

PredictionQ1

"Either the file is corrupt or the disk is full. The disk is not full. So the file is corrupt." uses:

Slide 119 / 132

Addition

Slide 119: Addition

Notes

  1. Addition: p ∴ p ∨ q.

Slide 120 / 132

Simplification

Slide 120: Simplification

Notes

  1. Simplification: p ∧ q ∴ p.

Slide 121 / 132

Conjunction

Slide 121: Conjunction

Notes

  1. Conjunction: p, q ∴ p ∧ q.

Slide 122 / 132

Resolution

Slide 122: Resolution

Notes

  1. Resolution: p ∨ q, ¬p ∨ r ∴ q ∨ r (the clashing literal p cancels).

Exam angle

PredictionQ1

From p ∨ q and ¬p ∨ r, resolution gives:

Slide 123 / 132

Using the rules of inference to build arguments

Slide 123: Using the rules of inference to build arguments

Notes

  1. Build an argument as a numbered list of steps, each a premise or a rule applied to earlier steps.

Exam angle

PredictionQ1

Premises: p → q, q → r, p. Show r with rules of inference.

Compare with the model answer

1. p → q (premise) 2. q → r (premise) 3. p → r (hypothetical syllogism 1, 2) 4. p (premise) 5. r (modus ponens 3, 4).

Slide 124 / 132

An example

Slide 124: An example
Slide 125 / 132

Using the rules of inference to build arguments An example

Slide 125: Using the rules of inference to build arguments An example
Slide 126 / 132

Using the resolution rule (an example)

Slide 126: Using the resolution rule (an example)
Slide 127 / 132

Using the resolution rule (an example)

Slide 127: Using the resolution rule (an example)
Slide 128 / 132

Example

Slide 128: Example
Slide 129 / 132

Continue

Slide 129: Continue
Slide 130 / 132

Another view on what we are doing

Slide 130: Another view on what we are doing
Slide 131 / 132

Rule of inference Tautology Name p q  p [ p  ( p  q )]  q Modusponens

Slide 131: Rule of inference Tautology Name p q  p [ p  ( p  q )]  q Modusponens
Slide 132 / 132

Example

Slide 132: Example