[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
  • $ a \in A $ if a is element of A
  • $ a \notin A $ if a is not element of A
  • Ways to describe set
    • List all the members of a set (Roster method). E.g $ A = \{a, b, c, d\} $ (Roster method)
    • Use set builder notation: $ X = \{ x \mid P(x) \} $$$ E.g \ \ O=\{x \mid x \ is \ odd\} $$
  • A is a subset of B if and only if every element of A is also an element of B.$$ A \subseteq B \Leftrightarrow \forall x (x \in A \rightarrow x \in B) $$
  • Two sets are equal if and only if they have the same elements.$$ A = B \Leftrightarrow \forall x (x \in A \leftrightarrow x \in B) $$$$ A = B \Leftrightarrow A \subseteq B \land B \subseteq A $$
  • The empty set$\emptyset$$$ For \ every \ set \ \emptyset \subseteq S, S \subseteq S $$
  • Given a set $S$, the power set of $S$ is the set of all subsets of the set S. The power set of S is denoted by $\mathcal{P}(S)$

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.$$ A \cup B = \{x \mid x \in A \lor x \in B \} $$
  • The intersection of the sets A and B is the set containing those elements in both A and B.$$ A \cap B = \{x \mid x \in A \land x \in 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.$$ A \setminus B = \{ x \mid x \in A \land x \notin B \} $$

Table set identies

To be done

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.$$A_1 × A_2 × · · · × A_n = \{ \ (a_1, a_2, . . . , a_n) \mid a_i ∈ A_i, 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$$ f : X \to 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)$$ \forall a \forall b (a \neq b \rightarrow f(a) \neq f(b)) $$
  • 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)$$ \forall y \in Y, \exists x \in X : f(x) = y $$
  • A function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. (Bijective)$$ \forall y \in Y, \exists ! x \in X : f(x) = y $$
  • 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|.

To be done

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

[Discrete Mathematics] Logic and Proof

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 $\lnot p$
disjunction p or q $p \lor q$
conjunction p and q $p \land q$
conditional if p, then q $p \rightarrow q$
biconditional p if and only if q $p \leftrightarrow 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 $p \leftrightarrow q $ is a tautology. ($p \equiv q$)

Equivalence Name
$$ p \lor F \equiv p $$

$$ p \land T \equiv p $$

Identity laws
$$ p \lor T \equiv T $$

$$ p \land F \equiv F $$

Domination laws
$$ p \lor p \equiv p $$

$$ p \land p \equiv p $$

Idempotent laws
$$ \lnot(\lnot p)) \equiv p $$ Double negation law
$$ p \lor q \equiv q \lor p $$

$$ p \land q \equiv q \land p $$

Commutative laws
$$ (p \lor q) \lor r \equiv p\lor(q\lor r) $$

$$ (p \land q) \land r \equiv p \land (q \land r) $$

Associative laws
$$ p \lor (q \land r) \equiv (p \lor q) \land (p \lor r) $$

$$ p \land (q \lor r) \equiv (p \land q) \lor (p \land r) $$

Distributive laws
$$ \lnot (p \land q) \equiv \lnot p \lor \lnot q $$

$$ \lnot (p \lor q) \equiv \lnot p \land \lnot q $$

De Morgan’s laws
$$ p \lor (p \land q) \equiv p $$

$$ p \land (p \lor q) \equiv p $$

Absorption laws
$$ p \lor \lnot p \equiv T $$

$$ p \land \lnot p \equiv F $$

Negation laws
Table of common Logical equivalence

3. Predicates and Quantifiers

To be done

References

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