Textbook notes for the course on Discrete Structures based on the book "Discrete Mathematics with Applications" by Susanna S. Epp 5th Edition

CS 1303

Set Symbols

Section 1

Remainder Theorem

• A condition statement

if 86 % 4 = 0 then 86 is even.

• A universal statement

All dogs have fleas.
( Even tho it might not be true, its a statement. )
For all elements in a set, a statement is true.
( A property of the elements in the set. )

• An existential statement

There is a prime number that is even.
There is no R such that x^2 = -1

• Universal conditional statement

( Talks about contents of the set.
if a in set or not ) For all integers n, if n is divisible by 10, then n is divisible by 5.
[ If _ then all. - this is not a part of this. ]

• Universal Existential statement

eg: Every real number has an additive inverse
=> For all real numbers is, there is an additive inverse for r.

• Existential universal statement

eg: There is a positive integer that is less than or equal to ever positive integer.

• A complex mathematical example
  "The limit of a_n as n approaches infinity is L" means that For all positive real numbers E, there is an integer N such that for all integer n, such that n >= N then
  -E < a_n - L < E

Language of Sets

X is an integer => x is an element in the integer set.

• Define Z: the set of integers

• Set: a collection of objects.

• Set-roster notation: writing all of a set's elements between braces.

• The order in a set is not important.

• An element listed more than once does not change the set. Symbols:

• Set-builder notation to describe sets

Subsets

A is a subset of B if and only if every element of A is also an element of B.
There exists an x such that x belongs A and x belongs to B

Property: A is a subset of itself.

A is not a subset of B => in set A there is at least one element which is not present in B.

Proper subset

A is called a proper subset if and only if A is a subset of B and there is at least one element of B that is not in A.

Cartesian Product

If A and B are two sets, then the Cartesian product of A and B, written as A X B, is the set:

(a,b) is called an ordered pair. Unlike with sets, order matters. (a,b) != (b,a)

Section 2

Statements

(aka proposition) is a sentence that declares something and is either true or false.

Non-Statements

Does not satisfy the definition of a statement

• It is the capital of Canada. ( Could be true or could be false; depends on what "it" represents. We need context. )
• a + b = 10
• This sentence is false. (paradox)

Logical connectives

Statement forms:

An expression made up of statement variables and logical connectives that becomes a statement when actual statements are substituted for statement variables.

Order of operations: ~; ^, v

Exclusive Or And Exclusive Nor:

Ways to represent XOR:

The above statements are logically equivalent. Represented by 3 line equals. A is equivalent to B then:

DeMorgan's Laws

Tautologies

A tautology is a statement form that is always true regardless of the truth of the individual statements for its statement variables.
eg: We either won the game or we didn't.
It's in the form: P V ~ P -> Always true.

Contradictions

A statement from that is always false regardless of the truth of the individual statements for its statement variables.
eg: We won the game and we lost the game.
P ^ ~P -> always false

Tautologies and Contradictions

• Let p be any statement, let t be a tautology , and c be a contradiction.
• P ^ t == P and that P ^ C == C
• P V t == t and P V C == P (Using == to represent logical equivalence.)

if p then q is represented as:

p implies q.

Laws of Equivalence

Contrapositives:

Given a condition p -> q
the contrapositive of the statement is
~q -> ~p
(Note that p and q positions are switched)

Fact: A conditional statement is logically equivalent to its contrapositive.

Example:

Negation of if

p -> q can be written as: ~p V q

That implies that the negation of the if statement is:
~(p -> q) == p ^ ~q

Only If

Only if does not mean that this is the only condition.
example: You can receive a BCS degree only if you complete cs1083
but this is not the only condition to completing BCS.

Logically equivalent to p -> q

If and only if

Order of operations:

~ | V ^ | -> <->

Sufficient condition

r is sufficient condition for s =>
if r is true this guarentees that s is true.
r -> s

Note: there may be other things that lead to s being true. Eg: p -> s

Necessary condition

r is a necessary condition for s =>
if r is not true then s can't be true.
~r -> ~s == s -> r

Here, even if there are other things that lead to s being true, r has to be true for s to be true.

Eg: (r ^ p) -> s (Here both r is a necessary condition)

Necessary and Sufficient conditions

If a condition is sufficient then, it means if that is true then s is true. If a condition is necessary then it means s can't be true without r being true.

r -> s (r sufficient condition for s)
s -> r (r necessary condition for s)

Together:
r <-> s
"r if and only if s"

Arguments

An Argument is a sequence of statements called premises, followed by a final statement called the conclusion.

A valid argument

To test if an argument is valid:

• construct a truth table showing values.
• Find the critical rows (Rows where all premises are true).
• In each critical row check if the conclusion is also true.

Forms of valid Arguments

• Modus Ponens

p -> q p => q

• Modus Tollens

p -> q ~p => ~q

• Generalization

p => p v q

• Specialization

p ^ q => p

• Elimination

p V q ~ q => p

• Transitivity

p -> q q -> r => p -> r

• Conjunction

p q => p ^ q

Proofs of Arguments

• Proof by contradiction

• To show p is true.

• Assume p is false.
• Now show that this leads to a contradiction.
• This implies that our assumption had to have been wrong.

~p -> c (Where c is a contradiction) => p

Section 3

Predicate

Statement: Alice is a student at UNB. Predicate: P(x): x is a student at UNB.

statements can be judged as true or false but predicated cannot be.

New Symbols:

All students know java.
S: The set of all students.
Java(x): x knows Java.
For all x belongs to S, Java(x)

Funcitons

a function is something that takes an input and returns an output. ( For a given input there is only one correct output. )

Square(5) = 25

Truth Set

Definition: If P(x) is a predicate and x has domain D, the truth set of P(x) is the set of all elements of D that make P(x) true when substituted for x. The truth set P(x) is denoted.

which is read "the set of all x in D such that P(x)."

Quantifiers

• The universal quantifier: For all -

• Universal statements

  The universal statement is true if and only if the predicate P(x) is true for every element in D, the domain of x.

An element x for which P(x) is false is called a counterexample.

• The Existential quantifier

  There exists

• Existential statements

is true if and only if the predicate P(x) is true for at least one element x in D, the domain of x.

• Universal Conditional statements

  Q(x) is true for all x if P(x) is true.

Negation of quantified statements

Negating universal condition

Variants of Universal Conditional Statements

Vacuous truth of universal statements

A statement is called vacuously true ( or true by default ) when P(x) is false for every x in D.

For all x belongs to D P(x) -> Q(x)

• Universal Instantiation

If some property is true of everything in a domain, then it is true of any particular thing in the domain.

• Universal Modus Ponens

• Universal Modus Tollens

• Universal Transitivity

• Universal version of Elimination

  

Section 4

Direct Proof and Counterexample I and II

Integers

• The set of all integers is closed under addition, subtraction and multiplication.

• Parity Property: Every integer is either even or odd.

Even and Odd Definition

An integer n is even if, and only if, n = 2k for some integer k.
An integer n is odd if, and only if, n = 2p + 1 for some integer p.

Prime and Composite Definition

An integer n is prime if, and only if, n > 1 and for all positive integers r and s, if n =r.s, then r=1 or s=1.

An integer n is composite if, and only if, n > 1 and n = r.s for some positive integers r and s with r != 1 and s != 1.

Proving by using examples or counterexamples

Methods of proving universal statements

• Proof by exhaustion

Proving a universal statement by proving that it holds for every single item in the set it's defined over.

• Direct Proof

(Universal conditional statement):

1. Let x be a particular but arbitrarily chosen element of D for which P(x) is true.
2. Use definitions, previously established results, and rules of logic to conclude that Q(x) is true.
3. Because your choice of x was entirely arbitrary, the conclusion holds for all x in D.

Example:

Proving a universal statement OR disproving an existential statement uses the direct proof or proof by exhaustion methods.

Rational Numbers

Definition: A real number r is rational if and only if there exists integers a and b such that r = a/b and b!= 0.

A real number that is not rational is irrational.

Zero product property a.b where a=0 V b=0 a.b =0

Corollaries

Definition: A corollary is a statement whose truth can almost immediately be deduced from a theorem that has already been proved.

r^2 is rational since r is rational is a corollary from a.b is rational is a and b are rational.

Quotient-Reminder Theorem

61/8 gives a reminder of 5 and a quotient of 7.
The Quotient-Reminder theorem says: Given any integer n and a positive integer d, there exist unique integers q and r such that n = dq + r and 0 <= r < d

Division into cases

You prove that P(x) is true for all the cases of x then it's true for all x. Example: If you prove that p(x) is true for even numbers and for odd numbers then it's true for all integers.

example:

Indirect Argument: Contradiction and Contraposition

Proof by contraposition

Statement: p -> q
Contraposition: ~q -> ~p

If the contraposition is true then the original statement is also true.

Proof by contradiction

Assume p
p -> c
Therefore ~p

Example: There is no greatest integer.
Assume there is a greatest integer, x
x+1 > x which is a contradiction.
Therefore there is no greatest integer.

Section 5

Sequences

Definition: A sequence is a function whose domain is either all the Integers (infinite sequence) or the integers greater than or equal to a given integer and less than or equal to another (finite sequence).

Each integer represents the position of the element in the sequence.

In a finite sequence:

• Each element ak is called a term.
• am is the initial term, an is the final term.
• m can be anything but usually, a sequence will start at 1 or 0.

Formulae Arithmetic Progression (AP) and Geometric Progression (GP)

Sum and product notation

Proof By Induction

• Prove P(x) is true for a base case.
• Prove given that P(k) is true, P(k+1) is true.
  ( P(k+1) just represents the next element in the series. )

Example:

Note: Proof by induction is based on the fact that you can define something recursively. Fn = Fn-1 + n. This is needed when assuming that n=k is true part of the induction.

Strong vs Weak induction

• In strong induction:
• In the inductive step, we prove that a statement is true for k+1 if it is true for all values from a (the base value) up to and including k.
• In the basic step, we sometimes have to prove the statement for more than one value n = 1 and n = 1 instead of just n = 1.
• Then assume n <= k and not n = k.

Strong induction is needed whenever the definition of the term recursively is based on more the one element of the prev set. Example: Fibonacci numbers. You can't prove anything about the sequence using induction if just considering n=1 and n=k (you'll need 2 base cases.)

The main difference is:

• n=k is the assumption. (Weak)
• n<= k is the assumption. (Strong)

Another Strong mathematical induction example:

Induction in inequalities

Well Ordering principle

Let S be a set containing one or more integers, all of which are greater than some fixed integer. Then S has a least element.

Section 6

Sets

Set: a collection of objects.
Element: one of the objects in a set.

Subset

A is called a subset of B, written A ⊆ B, if and only if every element of A is also an element of B.

Note: 2 sets are equal if and only if they are subsets of each other.

Proper subset

A is called a proper subset of B if and only if A ⊆ B, but there is at least one element of B that is not in A.

Notation: A ⊂ B

Universal Set

A larger set from which all sets being discussed is formed.

An example could be: {1,2,3,4} has a universal set of Z.

Set operations

Let A and B be subsets of a universal set U.

• Union

C = A ∪ B
⇒ ∀ x ∈ U, (x ∈ A ∨ x ∈ B ) → x ∈ C

• Intersection

C = A ∩ B
⇒ ∀ x ∈ U, (x ∈ A ∧ x ∈ B ) → x ∈ C

• Difference

C = A - B ⇒ ∀ x ∈ U, (x ∈ A ∧ x ∉ B ) → x ∈ C

• Compliment

C = A'
⇒ ∀ x ∈ U, (x ∉ A ) → x ∈ C

Partitions

A = {1,2,3,4,5}

A1 = {1,2} A2 = {3,4} A3 = {5}

A1 ∪ A2 ∪ A3 = A

AND

Ai ∩ Aj = ∅ for all i != j

Then A1, A2, A3 together is called a partition of A.

Sets notations

• |A| - Number of elements in A.
• P(A) - The power set, The set of all subsets of A.

Cartesian Product of sets

A x B = {(a,b) | a ∈ A and b ∈ B}.

(a,b) is called an ordered pair.

Number of elements in a cartesian product is
|A1| x |A2| x ... |An|

Properties of Sets

• A ⊆ B ∧ B ⊆ C → A ⊆ C

To formally prove a set is a subset of another we can use the element argument.

• Suppose x is an arbitrary element of X.
• Prove that x must be an element of Y.

Set Identities

![](ixVzbTzc.png