Sets and logic

Logic is the study of reasoning: statements that are true or false and how they combine. Sets are collections of objects. Both are the language of all of mathematics and computing.

Key facts

  • AND (∧) is true only if both are true; OR (∨) if at least one is.
  • NOT (¬) flips true and false.
  • P ⇒ Q is false only when P is true and Q is false.
  • A set with n elements has 2ⁿ subsets.
  • De Morgan: ¬(P ∧ Q) = ¬P ∨ ¬Q.

Worked examples

Example 1

When is “If it rains, the ground is wet” false?

  1. P ⇒ Q is only false when P is true and Q is false.
  2. So it’s false only if it rains and the ground stays dry.

Answer: When it rains and the ground is not wet

Example 2

List the subsets of {a, b}.

  1. Each element is either in or out: 2² = 4 subsets.
  2. ∅, {a}, {b}, {a, b}

Answer: ∅, {a}, {b}, {a, b}