## [Discrete Mathematics] Sets and Funtions

### 1. Sets

• A set is an unordered collection of objects, called elements or members of the set.
• A set is said to contain its elements
•  if a is element of A
•  if a is not element of A
• Ways to describe set
• List all the members of a set $Roster method$. E.g  $Roster method$
• Use set builder notation:
• A is a subset of B if and only if every element of A is also an element of B.
• Two sets are equal if and only if they have the same elements.
• The empty set
• Given a set , the power set of  is the set of all subsets of the set S. The power set of S is denoted by

### 2. Set operations

• The union of the sets A and B is the set that contains those elements that are either in A or in B, or in both.
• The intersection of the sets A and B is the set containing those elements in both A and B.
• The difference of A and B is the set containing those elements that are in A but not in B. The difference of A and B is also called the complement of B with respect to A.

Table set identies

### 3. Cartesian product

• The ordered n-tuple $a1, a2, . . . , an$ is the ordered collection that has a1 as its first element, a2 as its second element, . . . , and an an as its nth element.
• The Cartesian product of the sets A1, A2, . . . , An, denoted by A1 x A2 x · · · x An, is the set of ordered n-tuples $a1, a2, . . . , an$, where ai belongs to Ai for i = 1, 2, . . . , n.

### 4. Function

• Let X and Y be nonempty sets. A function f from X to Y is an assignment of exactly one element of X to each element of Y
• A function f is said to be one-to-one, or an injunction, if and only if f$a$ = f $b$ implies that a = b for all a and b in the domain of f $Injunctive$
• A function f from X to Y is called onto, or a surjection, if and only if for every element y ∈ Y there is an element x ∈ X with f$x$ = y $Surjective$
• A function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. $Bijective$
• Let f be a function from the set X to the set Y and let g be a function from the set y to the set C. The composition of the functions g and f, is defined by is defined by $f ◦ g$$a$ = f $g(a$).

### 5. Cardinality of Sets

##### Definition

The sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B. When A and B have the same cardinality, we write |A| = |B|.

### References

• Discrete Mathematics and Its Applications 7th Edition, Kenneth H. Rosen
• Đại số tuyến tính, Nguyễn Hữu Việt Hưng

## I. Logic and Proof

#### 1. Propositional Logic

A proposition is a declarative sentence $that is, a sentence that declares a fact$ that is either true or false, but not both.

Name Meaning Notation
negation not p
disjunction p or q
conjunction p and q
conditional if p, then q
biconditional p if and only if q

#### 2. Propositional Equivalences

A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology.

A compound proposition that is always false is called a contradiction.

A compound proposition that is neither a tautology nor a contradiction is called a contingency.

The compound propositions p and q are called logically equivalent if  is a tautology. 

Equivalence Name

Identity laws

Domination laws

Idempotent laws
Double negation law

Commutative laws

Associative laws

Distributive laws

De Morgan’s laws

Absorption laws

Negation laws
Table of common Logical equivalence

To be done

#### References

Discrete Mathematics and Its Applications 7th Edition, Kenneth H. Rosen