Skip to content

5. Introduction to Logic

  • Proposition: A statement that is either true or false. e.g. “The sky is blue” is a proposition, but “What time is it?” is not.
  • Logical Operations:
    • Logical Conjunction (AND): \(p \land q\) is true if both \(p\) and \(q\) are true.
    • Logical Disjunction (OR): \(p \lor q\) is true if either \(p\) or \(q\) is true.
    • Logical Negation (NOT): \(\neg p\) is true if \(p\) is false.
    • Conditional Statement (IF-THEN): \(p \to q\) is false if \(p\) is true and \(q\) is false, otherwise it is true. The order condition => conclusion is important, the q => p is a different statement.
    • Converse Statement: The converse of \(p \to q\) is \(q \to p\).
    • Contrapositive Statement: The contrapositive of \(p \to q\) is \(\neg q \to \neg p\).
    • Logical inverse: The inverse of \(p \to q\) is \(\neg p \to \neg q\).
    • Biconditional Statement (IF AND ONLY IF): \(p \leftrightarrow q\) is true if \(p\) and \(q\) have the same truth value.
Operation Symbol Comments
Logical Conjunction (AND) \(p \land q\)
Logical Disjunction (OR) \(p \lor q\)
Logical Negation (NOT) \(\neg p\)
Conditional Statement \(p \to q\) false if \(p\) is true and \(q\) is false, otherwise it is true.
Converse Statement \(q \to p\)
Contrapositive Statement \(\neg q \to \neg p\) The inverse of the converse
Logical inverse \(\neg p \to \neg q\)
Biconditional Statement \(p \leftrightarrow q\) true if \(p\) and \(q\) have the same truth value (either T or F)
  • Number of possible truth value rows for a statement with \(n\) variables: \(2^n\)
  • If we have the number of possible rows, then we can find the number of variables: \(\log_2(n)\)

Equivalence and Implication

  • Equivalence: Two statements are equivalent if they have the same truth table, they must be a tautology and is denoted by \(p \ q\) . That is, they have the same truth value for each possible combination of truth values of their variables.
  • Tautology: A statement that is always true, regardless of the truth values of its variables. E.g. \(p \lor \neg p\) is always true. All tautologies are equivalent.
  • Contradiction: A statement that is always false, regardless of the truth values of its variables. E.g. \(p \land \neg p\) is always false. All contradictions are equivalent.
  • Implication:
    • \(p \implies q\) is true when \(p \rightarrow q\) is a tautology.
    • \(p \implies q\) is equivalent to \(\neg p \lor q\).

The laws of logic

Mathematical Systems and Proofs

  • Mathematical System: A collection of related:
    • A universe: a set of objects
    • Definitions: statements that describe the objects in the universe.
    • Axioms: assertions about the rules of the system.
    • Theorems: additional assertions that can be proved using the axioms and definitions.
  • Euclidean geometry: Is a system, where the universe is a set of points and lines. Definitions include the definition of parallel lines. Axioms include that two parallel lines never intersect. Theorems include that the sum of the angles of a triangle is 180 degrees…etc.
  • Theorem:
    • It is a true proposition derived from the axioms and definitions of a mathematical system.
    • Theorems start with premises (set of propositions) and end with a conclusion (one true proposition).
    • The premises imply the conclusion.
    • The previously proved theorems can be used as axioms to prove new theorems (assumed to be true).
    • Axioms are assumed to be true without proof.
    • The newly proved theorems can be used to prove other theorems.
  • Proof
    • is a sequence of logically valid steps that demonstrate that the premises imply the conclusion.
    • Characteristics:
      • Must end in a finite number of steps.
      • Each step is either a premise, or a proposition that is driven from previous steps using equivalence or implication.
      • For direct proofs, the last step must be the conclusion.
      • For indirect proofs, the last step must be a contradiction.
      • Justification comments are added to each step to explain why it is valid.
  • Direct Proof: A proof that starts with the premises and uses logical steps to arrive at the conclusion.
  • Indirect Proof: A proof that starts with the premises and uses logical steps to arrive at a contradiction. The contradiction proves that the conclusion is true.

Quantifiers

  • If \(p(n)\) is a proposition over a universe U, its truth set \(T_p\) is equal to a subset of \(U\).
  • In many cases, such as when \(p(n)\) is an equation, we are most concerned with whether \(T_p\) is empty or not.
  • In other cases, we might be interested in whether \(T_p = U\); that is, whether \(p(n)\) is a tautology.
  • Since the conditions \(T_p = ∅\) and \(T_p = U\) are so often an issue, we have a special system of notation for them.
  • Existential Quantifier: (reads there exist) \(\exists n \in U, p(n)\) is true if \(T_p \neq ∅\). That is, if the truth set is not empty, then there exists at least one element in the universe that makes \(p(n)\) true.
  • Universal Quantifier: (reads for all) \(\forall n \in U, p(n)\) is true if \(T_p = U\). That is, if the truth set is the entire universe, then \(p(n)\) is true for all elements in the universe.

References

  • Doerr, A., & Levasseur, K. (2022). Applied discrete structures (3rd ed.). licensed under CC BY-NC-SA. https://discretemath.org/ads/chapter_7.html.
  • Levin, O. (2021). Discrete mathematics: An open introduction (3rd ed.). licensed under CC 4.0.