Logic and Proof

• Propositional logic

  • Twelve ways to say: p ⇒ q.

    • If p, then q.

    • If p, q.

    • q if p.

    • q when p.

    • p is sufficient for q.

    • q is necessary for p.

    • A sufficient condition for q is p.

    • A necessary condition for p is q.

    • p implies q.

    • p only if q.

    • q whenever p.

    • q follows from p.

  • Related Conditional statements

    • Contrapositive: ¬ q -> ¬ p

    • Inverse ¬ p: -> ¬ q

    • Converse: q -> p

  • Biconditionals

    • “p is necessary and sufficient for q”

    • “If p then q, and conversely”

    • “p iff q”

  • Precedence

    • Neg

    • And, or

    • Implies or biconditional

• Propositional equivalences

  • Tautology is always true while contradictions are always false

  • Distributive laws

    • p ∨ (q ∧ r) ≡ (p v q) ∧ (p v r)

    • p ∧ (q v r) ≡ (p ∧ q) v (p ∧ r)

  • De Morgan's Laws

    • ¬(p ∧ q) ≡ ¬p v ¬q

    • ¬(p ∨ q) ≡ ¬p ∧ ¬q

• Predicate Calculus

  • Predicate logic

    • Let P(x) denote …

  • Quantifiers

    • Universal

      • P(x1) ^ P(x2) ^ (Px3)

    • Existentia

      • P(x1) or P(x2) or (Px3)

    • Uniqueness (May be unnecessary)

      • ∃!X

      • There is exactly one…

  • De Morgan's Laws

    • ¬∃x P(x) ≡ ∀x ¬P(x)

    • ¬∀x P(x) ≡ ∃x ¬P(x)

• Nested Quantifiers

  • Nested quantifiers

    • ∀x ∃x Q(x) ≡ ∀x (∃x Q(x))

    • Read from the left quantifier to the right quantifier for ordering

  • Quantifying two variables

    • ∀x∀yP(x, y) ≡ ∀y∀xP(x, y) = true when P(x, y) is true for every x and y

    • ∀x∃yP(x, y) = true when for every x, there is a y for which P(x, y) is true

    • ∃x∀yP(x, y) = true when there is an x for which P(x, y) is true for every y

    • ∃x∃yP(x, y) ≡ ∃y∃xP(x, y) = true when a pair (x,y) for P(x, y) is true

  • Negating nested Quantifiers

    • ¬∃x∀yP(x, y) = ∀x¬∀yP(x, y) = ∀x∃y ¬P(x, y)

• Rules of Inference

  • Look to Table 1 on rules

  • Quantifiers: Look at Table 2

  • Fallacies

    • Denying the hypothesis

• Introduction to proofs

  • TERMS

    • Theorem is a statement that can be proven true

    • Proposition are less important theorems

    • Use proofs to justify theorems

      • Include axioms(or postulates): Statements assumed to be true

    • Lemma is a less important theorem that is helpful in the proof

    • Corollary is a statement that can be established directly from a theorem

    • A conjecture is a statement that is being proposed to be a true statement

  • Direct approach or p -> q:

    • Assume that p is true and with rules of inference prove that q is true

  • Proof by contraposition:

    • Assume that ¬q is true and try to prove that ¬p

  • Proof by contradiction

    • Give an example where the theorem fails

  • Proof by exhaustion: try everything (only works with a finite number of possibilities)

  • Proof by cases: you can break things into groups and show that certain groups work

  • Proof by implication

    • Assume P is true

      • Assume P, P then Q, therefore Q

      • Holds because if P is true you get Q and if P is false then Q is automatically implied

      • After you prove Q it is no longer safe to assume P still holds

    • Prove the contrapositive

      • Assume Not Q show that it implies Not P

  • Proving Biconditional

    • Prove each implies the other

      • P implies Q and Q implies P

    • Construct a chain of iffs

      • Show P iff R iff Q so P iff Q

  • Existence proof:

    • Constructive:

      • Find an x that satisfies ∃xP(x)

    • Non-Constructive:

    • Proof by contradiction  and show that the negations of the existential quantification  implies a contradiction

  • Proof Strategies:

    • If statement is a conditional statement: (1) direct proof, (2) indirect proof, (3) Proof by Contradiction

Sets, functions, Sequences and Sums

• Sets

  • A set is an unordered collection of objects

    • Objects in a set are called the elements/members

  • Number sets

    • N = Natural numbers

    • Z = Integers

    • Q = rational numbers

    • R = real numbers

    • = the empty set = {}

  • Sets are equal iff they have the same elements

    • Repetition and order don’t matter

  • S⊆T

    • T and S⊆T

  • Proper Subset

    • ST: ST

  • Cardinality(|S|): distinct elements in S

  • Power set (P(S)): The set of all subsets of the S

  • Cartesian Products

    • Ordered n-tuple: is the ordered collection that has a1 as its first element… and as its nth element

    • Two ordered n-tuples are equal iff each corresponding pair of their elements is equal

    • A x B ={(a,b)| aA bB}

      • A x B= {(1,a),(2,a),(1,b),(2,b)}

  • Truth sets of Quantifiers

    • P(x) = |x| = 1 where {xZ | |x| = 1} = {1,-1}

      • ∀xP(x) over domain U true iff U is the truth set of P

      • ∃xP(x) over domain U true iff U is nonempty

• Set Operations

  • Unioning (∪) two sets combines all the elements of two sets (additive)

  • Intersection (∩) creates a set containing all elements contained by both sets

    • Disjoint: if intersection of intersection is an empty set

  • Subtraction (–) creates a set containing only elements of either on or the other set but not both

    • Complement of B with respect to A = A-B

  • U is the universal set

• Functions

  • f(a) -> b

    • b is the image of a

    • a is the preimage of b’

    • f maps A to B

  • If f1 and f2 are functions from A to R

    • f1 + f2 = A to R

    • f1 * f2 = A to R

  • Injection: One to One

    • Horizontal line test: every mapping to Y has exactly one value in X

    • f(a) = f(b) implies that a = b for all a and b in domain of f

  • Surjective

    • A function f from A to B surjective iff every element b in B and there is an element A with f(a) = b

  • Bijection is Surjective and Injective

  • f^-1 (b) = a

• Sequences and Summations

  • A sequence is a function from a subset of the set of integers

    • Use a_n to denote term

    • Arithmetic and Geometric sequences

• Modular Arithmetic and Division

  • Division

    • a|b  denotes that such that b = ac

    • a is a multiple of b

  • Modular arithmetic

    • Amod m = b mod m