2.1 Logic

2.1.1 Propositional Logic

Adapted from Schuller (2015Schuller, Dr. Frederic P. 2015. “Introduction/Logic of Propositions and Predicates- 01 - Frederic Schuller.” Lectures on the Geometric Anatomy of Theoretical Physics. 2015. https://youtu.be/V49i_LM8B0E.).

Definition 1.1 (Proposition) A proposition is a variable that can only take the value true or false.

We can build propositions using logical operators. We will start by looking at the unary operators, which take one proposition and return one proposition. We can enumerate the 4 unary operators:

  • A negation operator that inverts its input
  • An identity operator that leaves the input unchanged
  • A logical true operator that returns true regardless of the input
  • A logical false operator that returns false regardless of the input

As a concrete example, a truth table will help us organize the various operators:

\(p\) \(\text{id }p\) (identity) \(\neg p\) (negate) T (true) F (false)
true true false true false
false false true true false

Next we have the binary operators.1 There are \(4\times 4 = 16\) total binary operators given that there are 4 unary operators. Three basic ones are listed in the truth table below.

  • The AND operator returns true if both of its inputs are true
  • The OR operator returns true if any of its inputs are true
  • The XOR (exclusive or) operator returns true if only one of its inputs is true
\((p,q)\) \(p \land q\) (AND) \(p \lor q\) (OR) \(p \veebar q\) (XOR)
(true, true) true true false
(true, false) false true true
(false, true) false true true
(false, false) false false false

Next, we have a special binary operation, which we shall call “implication.” Here is its truth table.

\((p,q)\) \(p \implies q\)
(true, true) true
(true, false) false
(false, true) true
(false, false) true

An implication allows us to take one proposition and use it as a stepping stone to another proposition. So why should an implication be true if its premise \(p\) is false? We refer to the idea from the Latin phrase ex falso quodlibet (from falsehood anything follows). If you use a false proposition to start, you can claim anything.

Alright, one last important binary operation: equivalency. If \(p\) and \(q\) have the same value, equivalency returns true, otherwise false.

\((p,q)\) \(p \iff q\)
(true, true) true
(true, false) false
(false, true) false
(false, false) true

Theorem 1.1 \[ (p \implies q) \iff (\neg q \implies \neg p) \]

If \(p\) implies \(q\), then if \(q\) is false that implies \(p\) is false

Proof. We construct a truth table.

\((p,q)\) \(\neg p\) \(\neg q\) \(p \implies q\) \(\neg q \implies \neg p\)
(true, true) false false true true
(true, false) false true false false
(false, true) true false true true
(false, false) true true true true

The last two columns are equivalent, so Q.E.D.

Corollary 1.1 This theorem enables us to use proof by contradiction.

  1. Goal is to show that if \(p\) is true, \(q\) is true.
  2. Assume that \(q\) is not true.
  3. Show that this leads to a contradiction.
  4. Therefore, \(q\) was actually true.

Remark (Order of Operations). From highest to lowest precedence:

  1. \(\neg\)
  2. \(\land\)
  3. \(\lor\)
  4. \(\implies\)
  5. \(\iff\)

Remark (Functional Completeness). All higher order operators can be constructed using a NAND2 Negation of the AND operator gate.

2.1.2 Predicate Logic

Definition 1.2 (Predicate) A predicate is a proposition-valued function of some variable(s).

A predicate of one variable can be converted into a proposition.

Definition 1.3 (Universal Quantification) The proposition \(\forall x : P(x)\) (which may be read “for all \(x\), \(P(x)\) is true”) is defined to be true if \(P(x)\) is true independently of \(x\).

Definition 1.4 (Existential Quantification) The quantifier \(\exists\) can be used in the context \(\exists x : P(x)\) (which may be read “there exists an3 by which we mean "at least one" \(x\) such that \(P(x)\) is true”). Building this definition from the tools we have,

\[ \exists x : P(x) \iff \neg \left(\forall x : \neg P(x) \right) \]

The existence of an \(x\) such that \(P(x)\) is true means that it is not true that that \(P(x)\) is false for all \(x\) .

Corollary 1.2 \[ \forall x : \neg P(x) \iff \neg \left( \exists x: P(x) \right) \]

If \(P(x)\) is false for all \(x\), then there does not exist an \(x\) such that \(P(x)\) is true."

Example 1.1 (Quantification for Predicates of More than One Variable) Such a quantification looks like

\[ Q(\overbrace{y}^{\text{free variable}}) \iff \forall \underbrace{x}_{\text{bound variable}} : P(x,y) \]

The term \(x\) is bound to the expression in the sense that it simply stands as an index while \(y\) is a free variable since we can choose what to input for it.

Remark (Order of Quantification Matters). The proposition \(\forall x : \exists y: P(x,y)\) is generically different from \(\forall y : \exists x: P(x,y)\).