Propositional Logic

Proposition

A proposition is a Declarative Sentence that is either true or false, but not both.

Link to original

Declarative Sentence

A declarative sentence is a sentence that declares something falsifiable.

Link to original

Examples:

7 - 4 = 3 prop

Odin is on our side prop

What is a Viking’s favorite food? not prop

Every Saxon is under attack. prop

x+y=3 not prop, because x and y vary

Propositional Variables are variables used to denote propositions.

• Typically: p, q, r, s, …
• never use capitals as they are reserved for propositional functions

Negation

Negation of $p$ denoted by $\neg p$

• *You must use $\neg$ to mean “not”
• same as !

Examples:

1. Ronnie likes Taco Bell $r$: “Ronnie likes Taco Bell” $\neg r$: “It is not the case that Ronnie likes Taco Bell”, “Ronnie does not like Taco Bell”

2. Thor’s hammer is not named Mjölnir always define prop vars as positive as below m: “Thor’s hammer is named Mjolnir” Negate original: $\neg (\neg m)⟹m$ “Double negation rule”

Truth Values and Truth Tables

1. Suppose we have a proposition $p$. Create a truth table for $p$ and $\neg p$

$p$	$\neg p$
T	F
F	T

Conjunction

A conjunction of $p$ and $q$ is the statement “p and q”

• it is denoted as $p\wedge q$
• same as &&
• Both p and q must be true for $p\wedge q$ to be true

Disjunction

A disjunction of p and q is the statement “p or q”

• it is denoted as $p\vee q$
• it is same as ||
• $p\vee q$ is true whenever p is true, q is true, or both p, q are true

Examples:

$p$: “Ronnie has 3 cats” $q$: “Ronnie does CrossFit”

1. Find $p\vee q$ Ronnie has 3 cats or Ronnie does CrossFit
2. Find $\neg p\wedge q$ Ronnie does not have 3 cats and Ronnie does CrossFit

XOR

The exclusive or of p and q is the statement p XOR q

• $p\oplus q$
• Same as ^
• In order to eval to true, p can be true or q can be true, but not both
• $p\oplus q=(p\vee q)\wedge \neg (p\wedge q)$

Conditionals & More!

Implication

Let p and q be propositions

• A statement in the form “if p, then q” is called a conditional statement / implication
• written as $p⟹q$
• False when p is true and q is false, otherwise true
• p is called the hypothesis, sufficient condition
• q is called the conclusion or the necessary condition
• if sufficient condition happens, then the necessary condition must happen

$p⟹q$

• if p, then q
• if p, q
• p is sufficient for q
• q if p
• q when p
• a necessary condition for p is q
• q unless ￢p
• p implies q
• p only if q (follows)
• a sufficient condition for q is p
• q whenever p
• q is necessary for p
• q follows from p
• q provided that p

Truth Tables: $p\wedge q,p\vee q,p\oplus q,p⟹q$

• List all possible combinations of truth values
• If $n$ is the # of unique prop vars, then there are $2^n$ rows in the truth table

p	q	$p\wedge q$	$p\vee q$	$p\oplus q$	$p⟹q$
T	T	T	T	F	T
T	F	F	T	T	F
F	T	F	T	T	T
F	F	F	F	F	T

Converses, Inverses, Contrapositives

Given $p⟹q$

1. Converse: $q⟹p$
2. Inverse: $\neg p⟹\neg q$
3. Contrapositive: $\neg q⟹\neg p$

• $q⟹p=\neg p⟹\neg q$
• $\neg q⟹\neg p=p⟹q$

Biconditional

• p iff q
• p $⟺$ q $\equiv$ (p $⟹$ q) $\wedge$ (q $⟹$ p)
• $p⟺q$

Precedence of Logical Operators

1. $\neg$
2. $\wedge$
3. $\vee$
4. $⟹$
5. $⟺$

Logic Puzzles

In the Vikings age, there lived 2 types of people

• Vikings, who are honorable and always tell the truth
• Saxons, who are not honorable so they never tell the truth Determine who is a Viking or Saxon between Ragnar and Egbert who say the following: Ragnar: I am a Viking only when Egbert is not ^[only if] Egbert: I am not a Saxon and Ragnar is a Saxon p: Ragnar is a viking, $\neg p$: Ragnar is a saxon q: Egbert is a viking, $\neg q$: Egbert is a saxon Ragnar says: $p⟹\neg q$ Egbert sats: $q\wedge \neg p$

p	q	$\neg p$	$\neg q$	$p⟹\neg q$	$p⟺p⟹\neg q$Whether Ragnar statement and identity align	$q⟺q\wedge \neg p$ Whether Egbert statement and identity align	$(p⟺p⟹\neg q)\wedge (q⟺q\wedge \neg p)$ Ragnar aligned && Egbert Aligned, i.e. do they go together
T	T	F	F	F	F	F	F
T	F	F	T	T	T	T	T
F	T	T	F	T	F	T	F
F	F	T	T	T	F	T	F
Based on the truth table, $p\equiv T,q\equiv F$

Now same situation, but different statements Ragnar says: We are both Saxons Egbert says: We are both Vikings p: Ragnar is a viking, $\neg p$: Ragnar is a saxon q: Egbert is a viking, $\neg q$: Egbert is a saxon Ragnar says: $\neg p\wedge \neg q$ Egbert says: $p\wedge q$

p	q	$\neg p$	$\neg q$	$\neg p\wedge \neg q$	$p⟺(\neg p\wedge \neg q)$	$p\wedge q$	$q⟺(p\wedge q)$	$[p⟺(\neg p\wedge \neg q)]\wedge [q⟺(p\wedge q)]$
T	T	F	F	F	F	T	T	F
T	F	F	T	F	F	F	T	F
F	T	T	F	F	T	F	F	F
F	F	T	T	T	F	F	T	F
No solution

If $>=1$ solution, “unable to determine”

Loki has heard of your exploits and wishes to honor you with a prize. However, being the deceiver that he is, he requires that you earn your prize by correctly determining which of three Chests actually holds the treasure. Only one Chest holds any treasure but the others are empty. You begin looking at the Chests and notice that Chests 1 and 2 are each inscribed with the message, “This Chest is empty.” The third Chest is inscribed with the message, “The treasure is in Chest 2.” Forseti, an honorable fellow, tells you that only one of these inscriptions are true. Which Chest do you select?

p: Treasure is in chest one q: Treasure is in chest two r: Treasure is in chest two 1: I’m empty ($\neg p$) 2: I’m empty ($\neg q$) 3: Treasure in 2 ($q$)

1 is true: $(\neg p\wedge \neg q\wedge q)\equiv F$ 2 is true: $(p\wedge \neg q\wedge \neg q)\equiv p\wedge \neg q\equiv T$ 3 is true: $(p\wedge q\wedge q)\equiv p\wedge q\equiv F$

Treasure in one

Definitions

Compound proposition: any expression formed from propositional variables using logical operators Tautology: always true compound prop. Contradiction: a compound prop. that is always false Contingency: everything else

Laws

Conditional Disjunction Equivalence

$p⟹q\equiv \neg p\vee q$

Absorption

$p\vee (p\wedge q)\equiv p$ $p\wedge (p\vee q)\equiv p$

Prove Equivalence

p \equiv q \text{ iff: }$$$$ p \iff q \equiv T

A Proof for DeMorgan’s First Law

Law: $\neg (p\wedge q)\equiv \neg p\vee q$

p	q	$\neg p$	$\neg q$	$p\wedge q$	$\neg (p\wedge q)$	$\neg p\wedge \neg q$
T	T	F	F	T	F	F
T	F	F	T	F	T	T
F	T	T	F	F	T	T
F	F	T	T	F	T	T

Prove logical equivalences without truth tables by using logical equivalences

Show that $(p\wedge q)⟹(p\vee q)$ is a tautology

$(p\wedge q)⟹(p\vee q)$	Given
$\neg (p\wedge q)\vee (p\vee q)$	Cond. Disj. Equiv.
$(\neg p\vee \neg q)\vee (p\vee q)$	DeMorgan’s
$(\neg p\vee p)\vee (\neg q\vee q)$	Asoc. & Comm.
$T\vee (\neg q\vee q)$	Negation law
$T$	Domination Law

Satisfiability

A compound proposition is satisfiable if there is an assignment of truth vaues to its variables that make it true (when it is a tautology or contingency) A compound proposition will be unsatisfiable if and only if it is a contradiction

Predicates and Quantifiers

Propositional Logic vs Predicate Logic

Example:

• x > 3
• x is the subject
• “less than 3” is the predicate
  • a property of x
• “x < 3” can be represented by $P(x)$
  • P denotes the predicate, x is the variable
  • $P(77)=77<3$
• Let $Q(x,y)$ denote $x=3-y$

Universal Quantifier

• The universal quantification of P(x) is the statement “P(x) for all values of x in the domain”
• $\forall xP(x)$ “for all x in P(x)”
• $\forall$ is the universal quantifier

Must include domain in statements

Existential Quantifier

• The existential quantification of P(x) is the proposition: “There exists an element x in the domain such that P(x).”
• “For some”, at least one / it exists
• $\exists xP(x)$

Uniqueness Quantifier

• “There exists a unique”, i.e. only one
• $\exists !xP(x)$
• e.g. $\exists !x(x^2=9)\equiv F$, due to -3, 3
• $\exists !xP(x)\equiv \exists x(P(x)\wedge \forall y(y\ne x⟹\neg P(y))$

$\forall ,\exists$ takes precedent over all logical operators

Quantifiers over Finite Domains

If the domain of a quantifier is finite, then you can convert quantified statements to propositional logic e.g. if domain = {$x_1,x_2$} $\forall xP(x)\equiv P(x_1)\wedge P(x_2)$ $\exists xP(x)\equiv P(x_1)\vee P(x_2)$

Domain Shorthand example

$\forall x<0(x^2<0)$ “for all x less than 0, $x^2<0$“

De Morgan’s Laws for Quantifiers

Negation	Equivalent Statement	Negation is true when…	Negation is false when…
$\neg \exists xP(x)$	$\forall x\neg P(x)$	P(x) is false for every x	There is an x that makes P(x) true
$\neg \forall xP(x)$	$\exists x\neg P(x)$	There is an x that makes P(x) false	P(x) is true for every x.

Double quant: DeMorgan allows to move neg inside if swap quant. Only have to be same x and y if in same scope. (Like programming)  

Statement	The statement is true when…	The statement is false when…
∀x∀yP(x,y)	P(x,y) is true for all pairs x,y	There is a pair x,y that makes P(x,y) false
∀x∃yP(x,y)	For each x, you can find a y that makes P(x,y) true	There is a value for x such that no value for y can make P(x,y) true
∃x∀yP(x,y)	There is an x that makes P(x,y) true for every y	There is not a single x that makes P(x,y) true for every y
∃x∃yP(x,y)	There is a pair x,y that makes P(x,y) true	There are no pairs x,y that make P(x,y) true

End

Argument

Argument: a set of initial statements, called premises, followed by a conclusion. An argument is valid if and only if in every case where all the premises are true, the conclusion is true. Otherwise, the argument is invalid.

• An argument can be valid even if the conclusion is false. This can occur if one of the premises is false. The requirement here for “valid” is that the conclusion is true when all premises are true.
• To prove a valid argument, show that the conjunction of the premises, leading to the conclusion is a tautology

Argument Name	Logical Representation
Modus Ponens	$p$ $p⟹q$ $\therefore q$
Modus tollens	$\neg q$ $p⟹q$ $\therefore \neg p$
Addition	$p$ $\therefore p\vee q$
Simplification	$p\wedge q$ $\therefore p$
Conjunction	$p$ $q$ $\therefore p\wedge q$
Hypothetical syllogism	$p⟹q$ $q⟹r$ $\therefore p⟹r$
Disjunctive syllogism	$p\vee q$ $\neg p$ $\therefore q$
Resolution	$p\vee q$ $\neg p\vee r$ $\therefore q\vee r$

Example

Want conclusion to be $b$ $\neg d\wedge e$ $c\vee d$ $\neg a⟹\neg c$ $\neg a\vee b$

Statements	Reasons
$\neg d\wedge e$	Given
$c\vee d$	Given
$\neg a⟹\neg c$	Given
$\neg a\vee b$	Given
$\neg d$	Simplification on $\neg d\wedge e$
$c$	Disjunctive Syllogism on $c\vee d$ and $\neg d$
$a$	Modus Tollens $c$ and $\neg a⟹\neg c$
$b$	Disjunctive Syllogism on $\neg a\vee b$ and $a$
$\therefore b$

Fallacy

Intro to Proofs: Direct Proof

Theorem a statement that can be shown to be true. Proof a valid argument that establishes the truth of a theorem Lemma less important theorems usually used to prove complicated theorems Corollary a theorem that is established directly from a theorem that has been proved Conjecture a statment that is being proposed as true

• Proving one makes it a theorem

Useful definitions and axioms

1. The integer n is even if there exists an integer k such that n = 2k, and 
2. n is odd if there exists an integer k such that n = 2k + 1. 
3. Closure of multiplication in integers:  The product of two integers is an integer.  
4. Closure of addition in integers: The sum of two integers is an integer
5. Closure of subtraction in integers:  The difference of any two integers is an integer
6. There is no closure of division (because of zero)

7. 3-5 above also work for real numbers.  replace all instances of the word integer with real number

8. The real number r is rational if there exist integers p and q with q ≠ 0 such that r = p∕q.
9. A real number that is not rational is called irrational.
10. A number m is a perfect square iff there exists some integer k such that $m=k^2$

Proof Format Introduction: Specify the type of proof technique you are using. E.g. I proceed with a direct proof. If proving a theorem in the form of conditional. State “Assume the hyp. Is true” where hyp. Is the hypothesis of the conditional. Outline any other things you may need to use to build this proof. Body: Write your argument for your proof. This step may typically contain multiple parts depending on both the proof technique and the theorem you are proving. Always define the domains of new variables you introduce See each proof technique for specifics. All simplification can be done in a single step. Any argument given should have a reason to go along with it. e.g. Let n be odd. By definition of odd, there’s an integer k such that n = 2k+1. Conclusion. State “Therefore by (insert proof technique)…is proven.” where … was the thing you were proving. Be careful to specify the entire theorem and not just the conclusion.

Direct Proof is a type of proof that directly leads to a conclusion, i.e. $p⟹q$. The assumption is that p is true, and we prove that q must follow.

Two Column Proof a proof with statements and reasons.

$\mathbb{Z}$ set of int $\mathbb{R}$ set of real $\mathbb{Q}$ set of rational $\mathbb{C}$ set of complex

Example: Give a direct proof of “If n is an even integer then $n^2$ is an even integer”

Pf: I proceed directly and assume $n$ is even.

Statement	Reasons
n is even	Premise
Let n = 2k, where $k\in \mathbb{Z}$	Definition of even
$n^2=4k^2$	Square both sides of the equation
$n^2=2(2k^2)$	Factoring out a 2
Let $j=2k^2$ for some $j\in \mathbb{Z}$	Closure of multiplication in $\mathbb{Z}$
$n^2=2j$	Substitution
$n^2$ is even	Definition of even
We see that if $n$ is even, then $n^2$ is also even is proven. Have proved $p⟹q$

Paragraph proof do your proof in a paragraph.

You write a box at the end or smth.

Proof by Contraposition

$p⟹q$ goes to $\neg q⟹\neg p$

Example 1:

Prove that if $n^2$ is an even and n is an integer, then n is even This proof is probably easier using the contrapositive

n is odd $⟹$ $n^2$ is odd This is the contrapositive

$n=2k+1$ $n^2=4k^2+4k+1$ $n^2=2(2k^2+2k)+1$ $z=2k^2+2k$ $n^2=2z+1$ $n^2$ is odd

Not all full proof btw, just showing how you can use the contrapositive

Example 2

Actual proof Prove that if n = ab, where a and b are positive integers, then a ≤ √n or b ≤ √n.

We will be using a contrapositive n = ab $\sqrt{n}=\sqrt{a}\sqrt{b}$ dead end, so use cp

Scratch !( a ≤ √n or b ≤ √n) $⟹$ !(n = ab) (a $>$ √n and b $>$ √n) $⟹$ n != ab (ab $>$ b√n and b$\sqrt{n}$ $>$ $\surd n^2$ ) $⟹$ n != ab (ab $>$ b√n and b$\sqrt{n}$ > n ) $⟹$ n != ab

Pf: I proceed by proving the contrapositive which states if a > $\sqrt{n}$ and $b>\sqrt{n}$, then n != ab, for all a, b, $\in \mathbb{Z}$

1	$a>\sqrt{n}$	Premise
2	$b>\sqrt{n}$	Premise
3	$ab>b\sqrt{n}$	mult 1 by b
4	$b\sqrt{n}>{\sqrt{n}}^2$	mult 2 by $sqrtn$
5	$b\sqrt{n}>n$	simplify 4
6	ab > n	Transitivity on 3 & 5
7	$ab\ne n$	def of >
Therefore, our proof by contrapositive suceeded, and thus, the equivalent “For all a, b $\in \mathbb{Z}$, if n = ab then $a$\leq\sqrt{n}$		b $\le$ $\sqrt{n}$” is true.
$\square$

Proof by Contradiction

All props are either true or false When trying to prove p is true, assume that p is false. Given this, break some equality or property of mathematics. Thus, p is true.

We’d assume if p then q is false Giving us: $\neg (p⟹q)$ Leading to $p\wedge \neg q$ (with simplification) is true

Example 1

Give a proof by contradiction of the theorem “If 5n + 2 is odd, then n is odd.”

In a proof by contradiction, assume $p\wedge \neg q$ is true, and find a contradiction.

Pf: I proceed using a proof by contradiction, where I assume 5n + 2 is odd, and n is even.

1	5n+2 is odd	premise
2	n is even	premise
3	n = 2k, for some k	def of even
4	5n = 10k	multi (3) by value of 5
5	5n + 2 = 10k + 2	add 2 to (4)
6	5n + 2 = 2(5k + 1)	factor (5)
7	5k + 1 = z, for z in $\mathbb{Z}$	closure mult + add in z, meaning that multiplication and addition with integers, gives an integer
8	5n + 2 = 2z	sub (7) into (6)
9	5n + 2 is even	def. even
By (9) and (1), 5n+2 is both even and odd, which is a contradiction. Therefore, the original assumption that n is even is false, and “if 5n + 2 is odd, then n is odd” is proven.
$\square$

Example 2

Show that at least four of any 22 days must fall on the same day of the week.

Scratch: Assume not p. At most, 3 of any 22 days must fall on the same day of the week. 3 * 7 = 21 Contradiction

Pf: Using proof by contradiction, I assume “At most, 3 of any 22 days must fall on the same day of the week”. Since there are 7 named days, and at most 3 fall on the same day, we have used at most 3x7=21 days, which contradicts that we have 22 days. Thus, our assumption was wrong, and at least 4 of any 22 days must feel on the same day of the week” $\square$

Example 3

Prove that √2 is irrational by giving a proof by contradiction Pf: I proceed using contradiction and assume $\sqrt{2}\in \mathbb{Q}$ We also note that a rational number can be written in simplest form. Thus, we have $\sqrt{2}=\frac{p}{q}$ where $p,q\in \mathbb{Z}$, $q\ne 0$, and $p,q$ have no common factors $2=\frac{p^2}{q^2}$, by squaring $2q^2=p^2$ Thus $p^2$ is even, by closue prop. and def of even Since $p^2$ is even, p is also even. And p = 2k for some $k\in \mathbb{Z}$ Then through sub, we have $2q^2=(2k{)}^2$ $2q^2=4k^2$ $2q^2=2(2k^2)$ $q^2=2k^2$ and thus, $q^2$ is even Thus q is even, and so q = 2m for some $m\in \mathbb{Z}$ We see p and q both have a common factor of 2, which contradicts the premise that they had no common factors. Thus, our assumption that $\sqrt{2}$ is ration is false, and we are left with $\sqrt{2}$ as irrational.

Example 6

Let a and b be positive integers with the property that ab+1 divides a^2+b^2. Show that (a^2+b^2)/ (ab+1) is a perfect square.

Pf: Just watch the lecture, view the notes later $\square$

When to use direct vs indirect proofs

Simple suggestion: Just try it. Start with a direct proof and see what happens. Do scratch work. Never try to write a proof before doing scratch work. Longer suggestion: Hypotheses that can’t be easily reasoned from might suggest that you use an indirect proof. Look back to example 3.

Vacuous Proof, with $p⟹q$, if $p\equiv F$, then the original statement must be true, regardless of q.

Trivial Proof with $p⟹q$, whenever $q\equiv T$, then the original statement must be true, regardless of q.

Backwards Reasoning (Strategy) This is a strategy that you can use in your scratch work. 

• Suppose you’re proving that q is true from a list of givens.
• However, you’re unable to figure out where to start based on those givens.
• In this case, you might start with q and work backwards to something that you can prove using your givens.
• Then when you write up your formal proof, you can do all the steps backwards.

Example: Prove that (x+y)/2 > √(xy) for all distinct positive real numbers x,y

$x\ne y,x\ge 0,y\ge 0$ Scratch: Start assuming conclusion is true. $\frac{x+y}{2}>\sqrt{xy}$ $x+y>2\sqrt{xy}$ $(x+y{)}^2>4xy$ $x^2+y^2+2xy>4xy$ $x^2+y^2-2xy>0$ $(x-y{)}^2>0$ Not equal, thus LHS will be gt0 Now for the Pf, just go backwards

Pf: Let $x,y\in \mathbb{R}$, be arb. where $x\ne y$. Then $x-y\ne 0$. Thus, $(x-y{)}^2>0$ * since the square of a nonzero real number is postive.

S	R
1) $(x-y{)}^2>0$	By *
2) $x^2+y^2-2xy>0$	Distr.
3) $x^2+y^2+2xy>4xy$	Add 4xy
4) $(x+y{)}^2>4xy$	Factor LHS
5) $xy>2\sqrt{xy}$	sqrt 4)
6) $\frac{x+y}{2}>\sqrt{xy}$	div by 2
We see that whenever x, y are distinct real # s, then $\frac{x+y}{2}>\sqrt{xy}$
$\square$

Exhaustive Proofs

In an exhaustive proof we try every possibility of the proposition. If all cases are true, then the proposition is proven.

e.g. Prove that $(n+1{)}^3\ge 4^n$ if n is a positive integer with n ≤ 3.

Pf: I proceed by exhaustion Let $P(n)\equiv (n+1{)}^3\ge 4^n$ Case: P(1) $P(1)\equiv (1+1{)}^3\ge 4^1\equiv 8\ge 4\equiv T$

Case: P(2) $P(2)\equiv (2+1{)}^3\ge 4^2\equiv 27\ge 16\equiv T$

Case: P(3) $P(3)\equiv (3+1{)}^3\ge 4^3\equiv 64\ge 64\equiv T$

$\therefore$ By exhaustion, $P(n)$ is true for all pos. int. where $n\le 3$ $\square$

Proof By Cases

A proof by cases is used when you must break your proof up into different cases due to a single argument not being enough to prove all cases. e.g. Prove that if n is an integer, then $n^2\ge n$. $n=0⟹n^2=0=n⟹n^2=n$ $n<0⟹n\le -1⟹n^2\ge 0⟹n^2>01\ge n⟹n^2\ge n$ $n>1⟹n^2>n$

Pf: Assume $n\in \mathbb{Z}$ is arbitrary. We have 3 cases: $n=0,n\le -1,n\ge 1$ Case: $n=0$ Since $n=0$, $n^2=0=n⟹n^2=n⟹n^2\ge n$ Case: $n\le -1$ $n^2\ge 0$ since the square of an int is nonnegative. We know $0\ge -1\ge n$ by transitivity, we have $n^2\ge n$ Case: $n\ge 1$ Mult ineq by $n$ gives $n^2\ge n$ Since we have proven all cases, then the original statement is true. $\square$

Without Loss of Generality

Sometimes we can eliminate cases inproof when the cases are very similar. e.g. $x>0,y<0$ vs $y>0,x<0$ You can say WLOG because the proofs for these cases with be exactly the same, except the x’s and y’s with be flipped.

Induction

Let P(n) be a proposition. To prove P(n) for all integers k.

1. Basis step where we show P(1)
2. Inductive step where we show that if P(k) then P(k+1)

Ex: Prove that ${\sum }_{j=1}^{n}j\frac{n(n+1)}{2},n\in {\mathbb{Z}}^{+}$

Pf: Let P(n) be ${\sum }_{j=1}^{n}j\frac{n(n+1)}{2}$. I use inductionto show P(n) is true for all int. n >= 1.

Basis: P(1) is true bc $1=\frac{1\cdot 2}{2}=\frac{1(1+1)}{2}$

Inductive Hypothesis: Assume that $P(k)=1+2+...+k=\frac{k(k+1)}{2}$ is true for a fixed arbitrary integer $k\ge 1$

Inductive Step:

1 + 2 + … k	$\frac{k(k+1)}{2}$
1 + 2 + … k + (k + 1)	$\frac{k(k+1)}{2}+(k+1)$
""""	$\frac{k^2+k+2k+2}{2}$
""""	$\frac{k^2+3k+2}{2}$
""""	$\frac{(k+1)(k+2)}{2}$
""""	$\frac{(k+1)((k+1)+1)}{2}$
We see that $P(k)⟹P(k+1)$ is true, completing the inductive step.
By math induction, P(n) is true for all int n >= 1
$\square$

Make sure to add the $(k+1{)}^{\text{th}}$ term, not just k + 1

Let a be constant and r be a common ratio ${\sum }_{j=0}^{n}a{r}^j=a+ar+a{r}^2+...+a{r}^n=\frac{a{r}^{n+1}-a}{r-1},r\ne 1$

Pf: Let P(n) be ${\sum }_{j=0}^{n}a{r}^j=a+ar+a{r}^2+...+a{r}^n=\frac{a{r}^{n+1}-a}{r-1},r\ne 1$. We us math. ind. to prove P(n) for all in $n\ge 0$

Basis Step: P(0) is true because ${\sum }_{j=0}^{0}a{r}^0=a{r}^0=\frac{ar-a}{r-1},r\ne 1$

Inductive Hypothesis: Assume ${\sum }_{j=0}^{k}a{r}^j=a+ar+a{r}^2+...+a{r}^k=\frac{a{r}^{k+1}-a}{r-1},r\ne 1,k\ge 0$

Inductive Step:

${\sum }_{j=0}^{k}a{r}^j=a+ar+a{r}^2+...+a{r}^k=\frac{a{r}^{k+1}-a}{r-1},r\ne 1,k\ge 0$	IH
$""""=a+ar+a{r}^2+...+a{r}^k+a{r}^{k+1}=\frac{a{r}^{k+1}-a}{r-1}+a{r}^{k+1}$	add $a{r}^{k+1}$
${\sum }_{j=0}^{k+1}a{r}^j=\frac{a{r}^{k+1}-a}{r-1}+a{r}^{k+1}$	Summation def
$""""=\frac{a{r}^{k+1}-a+a{r}^{k+1}(r-1)}{r-1}$	Simplify
$""""=\frac{a{r}^{k+1}-a+a{r}^{k+1+1}-a{r}^{k+1}}{r-1}$	Distributive
$""""=\frac{-a+a{r}^{k+1+1}}{r-1}$	Simplify
$""""=\frac{a{r}^{(k+1)+1}-a}{r-1}$	Commutative

Thus $P(k)⟹P(k+1)$ is proven, completing the inductive step. By induction, P(n) is true for all int. $n\ge 0$

Induction with Inequalities and Division

Use backwards reasoning in induction proofs in the SW to get the answer

~ Prove that $n$ people can divide the cake fairly.

n = 1 → whole cake n = 2 → 1/2 of whole cake n = 3 → 1/3 of each 1/2 n = 4 → 1/4 of each 1/3

Pf: Let $P(n)$ be that $n$ people can divide a cake fairly, so that each person has $\frac{1}{n}$ of the cake. I use induction to prov $P(n)$ is true for all integers $n\ge 1$

Basis: $P(1)$ is true because one person would get the entire cake. 1/1

Inductive Hypothesis: Assume $k$ people can divide the cake equally into $\frac{1}{k}$ pieces where $k\in {\mathbb{Z}}^{+}$

Inductive Step: Consider $k$ people, by the inductive hypothesis, they split the cake such that each person has $\frac{1}{k}$ of the cake. Let another person join, now we have $k+1$ people. We will take $\frac{1}{k+1}$ of each existing person’s slice. In order words, they take $\frac{1}{k+1}\cdot \frac{1}{k}$ of the original cake, from each of the original $k$ people. Since this occurred k times, they now have $k\frac{1}{k+1}\cdot \frac{1}{k}=\frac{1}{k+1}$. Each of the original $k$, originally had $\frac{1}{k}$ from which we took away $\frac{1}{1+k}$. Meaning $\frac{1}{k}-(\frac{1}{k+1}\cdot \frac{1}{k})=\frac{1}{k+1}$ each other person also has $\frac{1}{k+1}$ of the original cake. Thus by math ind, $P(k)⟹P(k+1)$; $\forall n\in {\mathbb{Z}}^{+}P(n)$ $\square$

Strong Induction

Induction but you do $(P(1)\wedge P(2)\wedge ...P(k))⟹P(k+1)$ You can also be like $P(j)$ for $j\in$ domain such that $b<=j<=k$

Set Theory

The study of Sets, which are collections of distinct objects.

Fundamentals

Set

An unordered collection of elements

Notation

Let $A,B$ be sets.

Symbol Name	Notation
Cardinality	$|A|$
Cartesian Product	$A\times B$
Complement	$A^{\prime }$ or $A^C$
Empty Set	$\{\}$ or $\varnothing$
	$A=B$
	$A\cap B$
	$x\in A$
Power Set	$\mathcal{P}(A)$
Subset	$A\subset B$
Superset	$A\supset B$
	$B-A$ or $B\text{textbackslash}A$
Set	$\{\dots \}$
Subset	$A\subseteq B$
Superset	$A\supseteq B$
Symmetric Difference	$A\oplus B$ or $A\Delta B$
	$A\cup B$
Universe	$\mathbb{U}$ or U

Operators

Binary

Equality

Let $A,B$ be sets

$$\begin{array}{c}A=B\\ ⟺\\ \forall x(x\in A⟺x\in B)\\ ⟺\\ A\subseteq B\wedge B\subseteq A\end{array}$$

Intersection

$$A\cap B=\{x|x\in A\vee x\in B\}$$

Union

$$A\cup B=\{x|x\in A\wedge x\in B\}$$

Relative Complement

$$A-B=\{x|x\in A\wedge x\notin B\}$$

Symmetric Difference

Symmetric Difference

$$\begin{array}{rl}A\oplus B& \\ & =(A\cup B)-(A\cap B)\\ & =(A-B)\cup (B-A)\\ & =\{x|(x\in A\vee x\in B)\wedge x\ne (A\cap B)\}\end{array}$$Link to original

Cartesian Product

Cartesian Product

$$A\times B=\{(a,b)|a\in A\wedge b\in B\}$$Link to original

Membership

Object $x$ is an element of the set of $A$

$$x\in A$$

Unary

Cardinality

Cardinality

The quantity of unique elements in a Set.

$$|A|=\text{\# unique elements in }A$$Link to original

Complement

Complement

$$A^{\prime }=\mathbb{U}-A=\{x\in \mathbb{U}|x\notin A\}$$Link to original

Power Set

Power Set

The powerset of the Set $A$, $\mathcal{P}(A)$, is the set of all subsets of $A$

$$\mathcal{P}(A)=\{S|S\subseteq A\}$$Link to original

Link to original

Subset

A part of a Set; Set A is a subset of B.

Definition

A set $A$ is a subset of $B$ if all elements of A are also elements of B.

$$A\subseteq B⟺\forall x(x\in A⟹x\in B)$$

Proper Subset

$$A\subset B\equiv A\subseteq B\wedge A\ne B$$Link to original

Superset

A Set encompassing/extending another set; Set B is a subset of A.

• A superset is the converse of a Subset. They are defined the same way, but the operands are swapped.
• Exclusively using subsets is favored

Definition

$$B\supseteq A⟺\forall x(x\in A⟹x\in B)$$

Proper Superset

$$B\supset A\equiv B\subseteq A\wedge B\ne A$$Link to original

Set Builder Notation

$$S=\{O|A\wedge B\wedge \dots \}$$

A set with some Object such that $A,B$ etc are true. e.g.

$$\{(x,y)|y=x^2\wedge x\in 2\mathbb{N}\wedge y\in \mathbb{N}\}$$Link to original

Composition

The act of combining the application of multiple Functions into one function.

• Age is a function that maps People to Integers
• GreaterThan18 is a function that maps Integers to Booleans
• GreaterThan18 $\circ$ Age is the Composition of the above functions that maps People to Booleans
  • It is equivalent to applying Age, then applying GreaterThan18
  • It can be thought of as: GreaterThan18 follows Age
  • GreaterThan18 $\circ$ Age = Age(GreaterThan18(…))
• id is the Identity Morphism, which is depicted above to map People to People
  • It exists for all sets, but is omitted for the others

Link to original

Universe

The Universe, Universal Set, or Universe of Discourse, denoted by $\mathbb{U}$ is the Set that contains all the entities one wishes to consider in a given situation.

• denoted mainly by $\mathbb{U}$ but also sometimes by $U,\mathcal{U}$
• ${\mathbb{U}}^{\prime }=\varnothing \wedge {\varnothing }^{\prime }=\mathbb{U}$

Link to original

Venn Diagram

In Set Theory, a Venn Diagram is a diagram that visually demonstrates the relationship between Sets, their overlap, and their relation to the Universe of Discourse

Link to original

Principle of Inclusion-Exclusion

$$\begin{array}{rl}|A_1\cup A_2\cup \cdots \cup A_n|& =\\ \sum _{i=1}^n|A_i|& -\\ \sum _{1\le i<j\le n}|A_i\cap A_j|& +\\ \sum _{1\le i<j<k\le n}|A_i\cap A_j\cap A_k|& -\\ \dots & \\ & \\ +(-1{)}^{n+1}|A_1\cap A_2\cap \cdots \cap A_n|& \end{array}$$

For 2 sets, for example $|A\cup B|=|A|+|B|-|A\cap B|$

For 3 sets, for example $\mid A\cup B\cup C\mid =\mid A\mid +\mid B\mid +\mid C\mid -\mid A\cap B\mid -\mid B\cap C\mid -\mid C\cap A\mid +\mid A\cap B\cap C\mid$ Note that we add $|A\cap B\cap C|$

Link to original

Numbers

Number

An element of a Division Ring, used for measuring, counting, quantifying, etc.

Set Name	Symbol	Description	Examples
Natural Number	$\mathbb{N}$	Counting numbers	$1,2,3,42$
Whole Number	$\mathbb{W}$ or ${\mathbb{N}}_0$	Nonzero Integers	$0,1,2,3,42$
Integer	$\mathbb{Z}$	Natural numbers, their negatives, and zero.	$-5,0,12$
Rational Number	$\mathbb{Q}$	Any number expressible as a fraction $\frac{p}{q}$.	$0.75,\frac{1}{3},-4$
Irrational Number	${\mathbb{Q}}^{\prime }$	Numbers that cannot be fractions (non-repeating decimals).	$\pi ,e,\sqrt{2}$
Real Number	$\mathbb{R}$	All points on the continuous number line ($\mathbb{Q}\cup {\mathbb{Q}}^{\prime }$).	$1.5,\pi ,-22$
Imaginary Number	$\mathbb{I}$	$\mathbb{R}\cdot i$	$1.5i,\pi i,-22i$
Complex Number	$\mathbb{C}$	$a+bi,a,b\in \mathbb{R}$	$2+3i,5,-i$
Quaternion	$\mathbb{H}$	$a+bi+cj+dk,a,b,c,d\in \mathbb{R}$	$1+5i+2j+3k$
Octonion	$\mathbb{O}$	$a+bi+cj+dk+el$ + fm+gn+ho$$a,b,c,d,e,f,g,h \in \mathbb{R}	Takes up too much space

Link to original

Functions

Function

A Mathematical Object that takes a set as an input, and outputs a set

• A mapping between sets
• Maps a Domain to a Codomain
• $f:A\to B$ is the function from $A$ to $B$ where $A$ and $B$ are Sets.
  • $f:A\to B⟺f\subseteq A\times B\wedge \{(a,b)|\forall a\in A,\exists !b\in B((a,b)\in f)\}$

Link to original

Domain

The Set of all inputs to a Function

Link to original

Codomain

The Set of all outputs of a Function

Link to original

Injective

If there is at most one location in the Codomain for every location in the Domain

Link to original

Surjective

If there is a location in the Codomain for every location in the Domain

Link to original

Bijective

If there is exactly one location in the Codomain for every location in the Domain for the Transformation

Link to original

Link to original

Functions

• Definition 1: Let A and B be nonempty sets. A function f from A to B is an assignment of exactly one element of B to each element of A. We write f (a) = b if b is the unique element of B assigned by the function f to the element a of A. If f is a function from A to B, we write f : A → B.
• Definition 2: If f is a function from A to B, we say that A is the domain of f and B is the codomain of f. If f (a) = b, we say that b is the image of a and a is a preimage of b. The range, or image, of f is the set of all images of elements of A. Also, if f is a function from A to B, we say that f maps A to B.
• You must specify the domain, codomain and the mapping of elements of the domain to elements in the codomain when defining a function. The range does not need to be explicitly specified
• Two functions are equal when they have the same domain, codomain, and map each element of their common domain to the same element in their common domain.
  • Changing the domain, codomain or mapping creates a new function

Ex:

1. What is the domain, codomain, and range of a function that assigns the last two bits of a bit string of length 2 or greater to that string.  (E.g. f(11010) = 10)

• Domain
  • The set of all bit strings $\ge$ 2
• Codomain
  • {11, 01, 10, 00}
• Range
  • {11, 01, 10, 00} Range and Codomain here happen to be equal

2. Let f : R→ R assign the square of a real number to this real number. Then, f (x) = $x^2$ .. What is the domain, codomain, and range of f.

• Domain
  • $\mathbb{R}$
• Codomain
  • $\mathbb{R}$
• Range
  • $\mathbb{R}-{\mathbb{R}}^{-}$ set operators have to order of precedence, except with union, intersect, and remove

1. ()
2. ~ complement
3. Everything else left to right

Real-valued and Integer-Valued

• A function is called real-valued if its codomain is the set of real numbers
• it is called integer-valued if its codomain is the set of integers.
• You can add and multiply both real-valued and integer-valued functions

A not necessarily a set of numbers

Ex

Let f1 and f2 be functions from R to R such that f1 (x) = x2 and f2 (x) = x − x2 . What are the functions f1 + f2 and f1 f2 ?

$(f_1+f_2)(x)=f_1(x)+f_2(x)=x^2+x-x^2=x$ $(f_1-f_2)(x)=f_1(x)-f_2(x)=x^2-x+x^2=2x^2-x$

One-to-One Functions

Some functions never assign the same value to two different domain elements. These functions are said to be one-to-one.

• At most one mapping from the domain for every element of the codomain
• Note that a function f is one-to-one if and only if f (a) ≠ f (b) whenever a ≠ b, and vice versa.
• Note 2 in the codomain below

Example: Determine whether the function f (x) = x2 from the set of integers to the set of integers is one-to-one.

• False, every value square is also hit by its opposite squared
• Assume domain if not given, to be the most reasonable real numbered domain or something similar.

Example: Prove that the function f (x) = x + 1 from the set of real numbers to itself is one-to-one.

• You need to show that if f(a) = f(b), then a = b By inspection it is 1-1 because it just shifts any value in the domain up by one. f: R→R Pf: Let a,b $\in \mathbb{R}$ be arbitrary and assume f(a) $\ne$ f(b). Then by def of f(x): a + 1 = b+1 a=b Since f(a)=f(b) → a=b f(x) is 1-1, by definition

A function has to map all element in the domain to something in the codomain. Let the domain be R, the codomain be R. then f(x) = 1/x is not a function.

Increasing and Decreasing

Given $x<y$, and x, y are in the proper domains, f is called:

• increasing if f (x) ≤ f (y)
• strictly increasing if f (x) < f (y)
• decreasing if f (x) ≥ f (y)
• strictly decreasing if    f (x) > f (y)

Its defined exactly as what you’d think it would mean. Not all function match. Horizontal line would be both. Vertical line would be neither.

Example: show that  $f(x)=x^2$  from R+ to R+ is strictly increasing. let x, y be positive reals and $x<y$ $x<y$ $x^2<xy$ $xy<y^2$ $x^2<y^2$ $f(x)<f(y)$ $\therefore x<y⟹f(x)<f(y)$

Onto Functions

A function f from A to B is called onto, or a surjection, if and only if for every element b ∈ B there is an element a ∈ A with f (a) = b. A function f is called surjective if it is onto.

• The range of the function equals the codomain. (every element in codomain is used.)
• All elements of codomain are hit at least once
• range = codomain

Let f be the function from {a, b, c, d} to {1, 2, 3} defined by f (a) = 3, f (b) = 2, f (c) = 1, and f (d) = 3. Is f an onto function? Yes.

Is the function f (x) = $x^2$ from the set of integers to the set of integers onto? No. Not onto. All non square integers will be missed from the codomain. For example: 2,${\mathbb{Z}}^{-}$

Is f (x) = x + 1 from the set of integers to the set of integers onto?

• Consider an arbitrary element y ∈ B and find an element x ∈ A such that f (x) = y. Let y in Z (codomain). Try to find x in the domain that makes x+1=y. x = y-1 ← Guaranteed to be in domain? (Yes for this case bc closure).

Bijections

The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. We also say that such a function is bijective. Exactly one domain element for every codomain element.

• Bijections have special properties
• All bijections have an inverse function

Inverse

Let f be a one-to-one correspondence from the set A to the set B. The inverse function of f is the function that assigns to an element b belonging to B the unique element a in A such that f (a) = b. The inverse function of f is denoted by f −1 . Hence, f −1(b) = a when f (a) = b.

Let f : Z → Z be such that f (x) = x + 1. Is f invertible, and if it is, what is its inverse? f(x) is a bijection $⟹$ f(x) is invertible

Get inverse. Replace f(x) with x. Replace x with $f(x{)}^{-1}$

Let f be the function from R to R with f (x) = $x^2$. Is f invertible? f(x) not a bijection

Composition of Functions

Let g be a function from the set A to the set B and let f be a function from the set B to the set C. The composition of the functions f and g, denoted for all a ∈ A by f ◦g, is the function from A to C defined by (f ◦ g)(a) = f (g(a)).

Let g be the function from the set {a, b, c} to itself such that g(a) = b, g(b) = c, and g(c) = a. Let f be the function from the set {a, b, c} to the set {1, 2, 3} such that   f (a) = 3, f (b) = 2, and f (c) = 1.  What is the composition of f and g, and what is the composition of g and f ? a → 3, c→1,b→2 a→undefined; g(f(x)) undefined, so the composition does not exist

Let f and g be the functions from the set of integers to the set of integers defined by f (x) = 2x + 3 and g(x) = 3x + 2. What is the composition of f and g? $f(g(x))=2(3x+2)+3=6x+4+3=6x+7$ What is the composition of g and f ? $g(f(x))=3(2x+3)+2=6x+9+2=6x+11$

$f(g(x))\ne g(f(x))$, but it is possible, just in general

Floor and Ceiling Functions

Floor

largest integer less than or equal to $x$ $\lfloor x\rfloor$

Ceiling

smallest number greater than or equal to $x$ $\lceil x\rceil$

Big-O Notation

Definition

Memorize: C and k are called witnesses to the relationship f(x) is O(g(x)).

• Trying to find an upper bound estimate of our function, i.e. if $f(x)$ is a quadratic, its big O is $O(x^2)$
  • In this class, not trying to find smallest upper bound, unlike in computing
  • We are just finding an upper bound
  • $p(x^n)=O(x^n)$
• k for when g(x) is growing faster than f(x) and is $\ge$ than f(x)
  • k doesn’t need to be the first x where this occurs, just one of them
• What C means is that we only care about the parent function, i.e. we consider if $f(x)=3x^2$ then $C=3$ where $g(x)=x^2$, so that the functions are comparable.

Pf: show that $f(x)=x^2+2x+1$ is $O(x^2)$ I proceed directly. (This proof only works for polynomials) Prove each term is $O(x^2)$ $x^2\le \_x^2$ $2x\le \_x^2$ $1\le \_x^2$

$|x^2|\le |1x^2|,\forall x>0$ $|2x|\le |2x^2|,\forall x>1$ Did not have to pick this value, its just easier $|1|\le |1x^2|,\forall x>1$ $x^2+2x+1\le 4x^2,\forall x>1$ Thus C=4, k=1 as witnesses: $f(x)$ is $O(x^2)$ $\square$

Big-O Complexity

1. $O(n^n)$
2. $O(n!)$
3. $O(2^n)$
4. $O(n^2)$
5. $O(nlogn)$
6. $O(n)$
7. $O(logn)$
8. $O(1)$

Have to memorize the theorem numbers.

Cardinality of Sets

Equal sets

Two sets A and B have the same cardinality if and only if you can find a bijection from A to B. When A and B have the same cardinality, we write |A| = |B|

Different Sets

If there is only a one-to-one function from A to B, the cardinality of A is less than or the same as the cardinality of B and we write |A| ≤ |B|. Furthermore, if there is a one-to-one function from A to B but there is no bijection, then |A| < |B|

Countable

• Finite sets are countable
• The set of positive integers is countable
• Any infinite set that has the same cardinality as the set of of positive integers is countable.
• When an infinite set S is countable, we denote cardinality of S by ${\aleph }_0$ (read as aleph null). |S| = ${\aleph }_0$

Hilbert’s Grand Hotel

Consider a hotel with a finite number of rooms.  Suppose all rooms are occupied. A new guest arrives.  Then there is no way to accommodate this guest without evicting a current guest.

Hilbert’s Grand Hotel: Consider a hotel with an infinitely countable number of rooms.  Assume all rooms are occupied. Suppose a new guest arrives.  Show that this guest can always be accommodated. In other words, show that we can always find a room for this guest without evicting a current guest.

Cantor’s Diagonalization Technique

The one that proves $\mathbb{Q}$ is countable with the diagonals

Uncountable Sets

Show that the set of real numbers is uncountable. Hint: Show that (0,1) as a subset of R is uncountable which would show R is also uncountable

Division

Modular Arithmetic

Integer Representation

Base Conversion

Note: on exam, must use base conversion algorithm, not guess and check.

Prime