Exam 1 Notes:

Reviewing everything we learned pre -exam 1

What is a statement/proposition?

A statement/propositions is a sentence that has one unambiguous truth value either: TRUE or False

ex: “3 is odd” “If x is even, then x² is even”

not p

it is not the case that p

p ^ q

p and q

p v q

p or q

Converse

The converse of an implication p→q is the implication q→p

Contrapositive

The contrapositive of an implication p→q is the prop not q→not p

Logically Equivalent

If two compound propositions have identical truth tables.

Logical Argument:

A collection of statements (premises) thar support a conclusion

ex: if it rains, the ground gets wet

Core Laws:

• Distribution

• DeMorgans’s Law

• Communitavity

• Associativity

Distributive Law

A law that distributes one operation over another

ex: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

DeMorgan’s Laws

Rules for negotiating AND/OR statements

ex:

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

Commutative Law

Changing the order does not change the result

ex:

p ∧ q ≡ q ∧ p
p ∨ q ≡ q ∨ p

Associative Law

Grouping does not change the result

ex:

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

When do you use the distributive law?

When you need to remove parentheses or factor expressions

Used when a term must be applied to a group:

p ∧ (q ∨ r) → distribute p across (q ∨ r)

When do you use De Morgan’s Laws?

When negating a compound statement (with AND/OR)

Especially when pushing a NOT inside parentheses

¬(p ∧ q), ¬(p ∨ q)

When do you use the commutative law?

When you want to reorder terms without changing meaning

Used to rearrange expressions for simplification or matching forms:

p ∧ q ↔ q ∧ p

When do you use the associative law?

When regrouping terms to simply or reorder logic

Used when parentheses are moved without changing meaning:
(p ∧ q) ∧ r ↔ p ∧ (q ∧ r)

ℕ

natural numbers

{0,1,2,…}

ℤ

integers: {…, -2,-1,0,1,2,…}

ℚ

rational numbers {n/m | n,m E ℤ, m =/ 0}

ℝ

real numbers (decimals)

Def: An integer n is even if

n = 2k for some integer k

What is the Division Algorithm?

• For any integer a,b, there exist positive integers q and r such that:

• a = bq + r, where 0 <_ r < b

• a = fivident

• b = divisor

• q = quotient

• r = remainder

When do you use the Division Algorithm?

• When dividing integers, and you want to express a number in the form

• Used in

  • modular arithmetic

  • proving properties about remainders

  • computer science proofs involving disability

Direct Proof (DP)

• a method where you prove a statement by:

• starting with known facts/assumptions

• logically step-by-step reaching the conclusion

• Steps:

  • Assumption: start with what you told is true, the hypothesis

  • Conclusion: What you want to prove, the statement to prove is true

• p → q

When to use a direct proof?

• When the statement can be proven by straightforward logical steps starting from the hypothesis

• best used when:

  • you can directly manipulate definitions

  • no “negation” or contradictions is needed

  • the conclusion follows naturally from the assumption

• ex:

  • proving properties of even/odd numbers, divisibility, algebraic statements

Pf by Contrapositive

• a proof method where instead of proving “If P then Q:”, you prove the logically equivalents statement:

• “If not Q, then not P

• not q → not p

When to use Pf by Contrapositive:

• When the contrapositive is easier to prove than the original statement

• Best used when:

  • the conclusion is hard to reach directly

  • negating the conclusion simplifies the problem

  • the statement involves “if P then Q” and switching it makes it clearer

Proof by Contradiction

• A proof method where you assume the opposite of what you want to prove and show that it leads to a contradiction, so the original statement must be true

When to use Pf by Contradiction:

• When assuming the opposite of the statement makes it easier to find a contradiction

• Best used when:

  • the statement involves impossibility

  • the conclusion is hard to prove directly

  • the problem includes “not”, “no,” or uniqueness

  • you can derive something impossible (like 0 = 1)

  • assume its false and break it

“All integers greater than 1 are divisible by a prime” Means what?

• Every integer n > 1 is either prime or can be divided by a prime number

What is a “Prime Number”?

• An integer greater than 1 that has exactly two positive divisors: 1 and itself

• Example:

  • An integer greater than 1 has exactly two positive divisors: 1 and itself

  • Example: 2,3,5,7

What is a “Composite Number”?

• An integer greater than 1 that has more than two positive divisor

What is the empty set (∅)?

• A set that contains no elements

• {} (another way to write empty set

What does ∈ mean?

• “Is an element of”

• Example: 3 ∈ {1,2,3}

What does ∉ mean?

• “Is not an element of”

• Example: 4 ∉ {1,2,3}

What does ⊆ mean?

• Subset (every element of A is in B)

• A ⊆ B means A is contained in B

What does ⊂ mean?

• Proper subset (A is contained in B and A ≠ B)

What does = mean for sets?

• Two sets are equal if they have exactly the same elements

What is the universal set (U)?

• The set containing all elements under consideration

What is set difference?

• Elements in A but not in B

• A − B

• Use when removing elements of one set from another

What is complement?

• Elements not in A (relative to universal set)

• Aᶜ

• Use when finding everything NOT in a set

What is the commutative law for sets?

• A ∪ B = B ∪ A

• A ∩ B = B ∩ A

What is the Associative Law for sets?

• (A ∪ B) ∪ C = A ∪ (B ∪ C)

• (A ∩ B) ∩ C = A ∩ (B ∩ C)

What is DeMorgan’s Law for sets?

• (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ

• (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

What does |A| mean?

• The number of elements in set A (cardinality)

What is a finite set?

• A set with a limited number of elements

What is an infinite set?

• A set with infinitely many elements

What does Curly braces mean? {, }

• set

What does ∈ mean?

• belongs to

• “… is an element of…”

what does “ | “ mean?

• such that

what does { x ∈ X | P(x) } mean?

• The set of all elements x in X such that P(x) is true

When are two sets equal?

• Two sets are equal if they contain exactly the same elements (i.e., each is a subset of the other)

• Two sets A and B are equal if:

• A ⊆ B and B ⊆ A

What does A⊕B mean?

• The set of elements in A or B but not in both

• (i.e., elements that are in exactly one of the sets)

What is “U”:

• The universal set is the set of ALL elements under discussion in a given problem

What is the Inclusion-Exclusion Principle for two sets?

• A way to find the size of a union of two sets without double-counting:

• ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

What is the Inclusion–Exclusion Principle for three sets A, B, and C?

• A formula to find the size of the union of three sets without double-counting:

• ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣

• Add all single sets

• Subtract pairwise overlaps (because they get counted twice)

• Add back the triple overlap (because it got subtracted too much)

• Use when counting elements in three overlapping sets and you want to avoid double-counting shared elements.

What is the Cartesian product?

• The Cartesian product of two sets A and B is the set of all ordered pairs (a,b) where Aa∈A and b∈Bb:

• A×B={(a,b)∣a∈A,b∈B}

• It pairs every element of A with every element of B.

• ex:

• A = {1,2}, B = {x,y}

• Then A × B = {(1,x), (1,y), (2,x), (2,y)}

When are two ordered pairs equal?

• (a,b)=(c,d) if and only if:

  • a=ca = ca=c AND

  • b=db = db=d

What is an m×n matrix of elements of a set A?

• A rectangular array with m rows and n columns, where each entry is an element of A.

• A grid of elements where:

  • m = number of rows

  • n = number of columns

  • each position contains an element from A

  • If A = {0,1} and we form a 2×3 matrix:

  • [1 0 1]

  • [0 1 0]

What does A* mean?

• The set of all possible strings (including the empty string) that can be formed using elements of A

• repeated any number of times (including 0 times).

• never stops

• (Kleene Star)

What is a language?

• Some set of strings

what is L^+=i=1⋃∞ ​Li

• Positive Closure of a Language (L^+)

• defined as the union of all concatenations of L with itself one or more times:

• At least 1 repetition

• No empty string included (in general

• If:

• L = {a, b}Then:

• L¹ = {a, b}

• L² = {aa, ab, ba, bb}

• L³ = {aaa, aab, …}

• So

• L⁺ = {a, b, aa, ab, ba, bb, aaa, …}

• Use when you want all strings formed by repeating elements of a language one or more times

L^+ vs. L*

• L* = zero or more repetitions (includes ε)

• L^+ = one or more repetitions (excludes ε unless ε is already in L)

What does it mean that “a language is closed”?

• A language is closed under an operation if applying that operation to languages in the set always produces a language that is also in the same set

• If you start with languages in a class (like regular languages) and apply an operation (like union or concatenation), you still stay inside that same class

What is a binary relation?

• A binary relation R from a set A to a set B is any subset of the Cartesian product A×B

• R⊆A×B

• ex: A = {1,2}, B = {x,y}

• Then a relation could be:

• R = {(1,x), (2,y)}

feb 13th