Unit 1 | DSTL Notes |Discrete Structure and Theory of Logic Notes | Aktu Notes

Unit 1 | DSTL Notes |Discrete Structure and Theory of Logic Notes | Aktu Notes

Sets

Sets: Collections of well-defined objects.  

Elements: Can be numbers, letters, points, etc.  

Notation: Sets denoted by capital letters, elements by lowercase.  

Membership: x∈A means "x belongs to A."

 

Types of Sets

Finite Set: Contains a finite or countable number of elements. 

Ex. {1, 2, 3, 4}  

Infinite Set: Contains an infinite number of elements.

Ex. {1, 2, 3, ...}  

Null Set: Contains no elements; denoted by ∅ or {}.  

Singleton Set: Contains only one element. Ex. {5}  

Subset: A set where all elements belong to another set. {1, 2} is a subset of {1, 2, 3}  

Superset: A set that contains all elements of another set.

{1, 2, 3} is a superset of {1, 2}  

Proper Subset: A subset that is not equal to the original set.

{1, 2} is a proper subset of {1, 2, 3}  

Universal Set: A set that contains all sets under consideration.

The set of all integers, denoted by ℤ

 

Equal Set: Two sets with identical elements.

{1, 2, 3} = {3, 2, 1}  

Disjoint Set: Sets with no common elements.

{1, 2, 3} and {4, 5, 6} are disjoint sets.

Operations on Sets

Union: Combines elements from two or more sets, removing duplicates.

Ex: If A = {1, 2, 3}, B = {3, 4, 5} then A U B ={1,2,3,4,5}  

Intersection: Finds elements common to two or more sets.

Ex: If A = {1, 2, 3} ,B = {3, 4, 5} then A∩B={3}  

Set Difference: Subtracts elements of one set from another.

Ex: If A = {1, 2, 3} B = {3, 4, 5} then A−B={1,2}  

Complement: Finds elements not in a specified set.

Ex: If U is the universal set and A = {1, 2, 3},

then A′ (complement of A) would be the set of all elements in U that are not in A.  

Cartesian Product: Creates pairs of elements from two sets.

Ex: If A = {a, b} B = {1, 2}, then A×B={(a,1),(a,2),(b,1),(b,2)}.  

Power Set: Generates the set of all subsets of a given set.

Ex: If A = {1, 2}, then the power set P(A)={{},{1},{2},{1,2}}.

Relation

- A relation R from set A to set B is a collection of ordered pairs (a,b), where a is from A and b is from B.

- If (a,b) is in R, we say a is related to b by R;  

- otherwise, a is not related to b by R

Ex : Let A = {1, 2, 3, 4}, B = {1, 2} and aRb

iff a × b = even number Then R = {(1, 2), (2, 1), (2, 2), (3, 2), (4,1), (4, 2)}

Types of relations

Universal Relation: Contains all possible ordered pairs from sets A and B.

Ex: For A={a,b} and B={1,2}, U(R)={(a,1),(a,2),(b,1),(b,2)}.  

Identity Relation: Consists of pairs where both elements are identical.

Ex: For set C={x,y,z}, IC or ΔC ={(x,x),(y,y),(z,z)}.  

Void Relation: Contains no pairs; it's an empty set

ex : If A = {1, 2, 3} and as R = {(a + b) |a + b > 5}, a, b  A then R = NULL.  

Inverse Relation: Consists of pairs reversed from the original relation.

Ex: If T={(1,2),(2,3),(4,5)}, then T-1 ={(2,1),(3,2),(5,4)}.  

Complement of a Relation: Contains pairs not present in the original relation.

Ex: For E={m,n,o} and F={6,7},

if G={(m,6),(o,7)}, then Gc={(m,7),(n,6),(n,7),(o,6)}.

Properties of relation

Reflexive: Every element is related to itself.

Ex: If R is relation on set A, then (a,a) is in R for every a in A.  

Symmetric: If a is related to b, then b is related to a. Ex: If R is a relation on set A, and ((a,b) is in R, then (b,a) is also in R.  

Transitive: If a is related to b, and b is related to c, then a is related to c.

Ex: If R is a relation on set A, and (a,b) and (b,c) are in R, then (a,c) is also in R.  

Antisymmetric: If a is related to b and b is related to a, then a equals b.

Ex: Let A={1,2,3} and consider the relation

R={(1,1),(2,2),(3,3),(1,2),(2,3)}  

Irreflexive: No element is related to itself.

Ex: If R is a relation on set A, then (a,a) is not in R for any a in A.

Asymmetric: If a is related to b, then b is not related to a.

Ex: If R is a relation on set A, and (a,b) is in R, then (b,a) is not in R.

Question: Consider the following five relations on the set A = {1, 2, 3); R = {(1, 1), (1, 2), (1, 3), (3, 3)} Ø = empty relation AXA = universal relation S = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)

T = ((1, 1), (1, 2), (2, 2), (2, 3))

Determine: (a) reflexive; (b) symmetric, (c) transitive; (d) antisymmetric (e) draw directed graph

Solution: 

(a) R is not reflexive since 2 ∈ R but (2, 2) & R.

T is not reflexive since (3, 3) ∈T and,

similarly, Ø is not reflexive. S and A × A are reflexive.

(b) R is not symmetric since (1, 2) ∈ R but (2, 1) & R, similarly T is not symmetric except R and T all sets are symmetric.

(c) T is not transitive since (1, 2) and (2, 3) belong to T, but (1, 3) does not belong to T. The other four relations are transitive.

(d) S is not antisymmetric since 1≠2, and (1, 2) and (2, 1) both belong to S. Similarly, AXA is not antisymmetric. The other three relations are antisymmetric.

Operations on relation with example

Let R={(1,2),(3,4)} and S={(2,3),(4,5)}.  

Union: R∪S={(1,2),(2,3),(3,4),(4,5)}.  Intersection: R∩S=∅,  

Composition: R∘S={(1,4),(2,5)}.

Inverse: If R={(1,2),(2,3)}, then the inverse of is R^(−1)={(2,1),(3,2)}

Equivalence of relations

- Equivalence of relations refers to a specific property that relations can possess.  

- An equivalence relation on a set satisfies three important properties:

1.Reflexivity: For every element a in A, a is related to itself. 

(a,a)∈R

2.Symmetry: If a is related to b, then b is related to a.

(a,b)∈R⟹(b,a)∈R

3.Transitivity: If a is related to b and b is related to c, then a is related to c. 

(a,b)∈R ∧ (b,c)∈R ⟹ (a,c)∈R

Question: To prove that the relation R={(a,b)∣a−b is divisible by 4} is an equivalence relation on the set of integers Z

 

- we need to demonstrate three properties: reflexivity, symmetry, and transitivity.  

Reflexivity:  

- For every integer a in Z, we must show that a−a is divisible by 4.  

- Since a−a=0, which is divisible by any integer, including 4, reflexivity holds. 

Symmetry:  

- If a−b is divisible by 4, we need to show that b−a is also divisible by 4.  

- Since a−b=−(b−a), if a−b is divisible by 4, then b−a is also divisible by 4. Hence, symmetry holds.

Transitivity:  

- If a−b and b−c are both divisible by 4, we must show that a−c is also divisible by 4. 

- Since a−c=(a−b)+(b−c), if a−b and b−c are divisible by 4, then a−c is also divisible by 4. Thus, transitivity holds.

Since R satisfies reflexivity, symmetry, and transitivity, it is an equivalence relation on Z

Question: Show that R = {(a, b)|a = b (mod m)} is an equivalence relation on Z.  

- We must show that the relation is reflexive, symmetric, and transitive.  

- For any x in Z we have x = x (mod m) because x - x = 0 is divisible by m.

Hence the relation is reflexive.

- Suppose x =y (mod m), so x - y is divisible by m. Then - (x - y) = y -x is also divisible by m, so y = x (mod m). Thus the relation is symmetric.  

- Now suppose x = y (mod m) and y = z (mod m), so x -y and y - z are each divisible by m. Then the sum (xy)+(y-z) = x-z is

also divisible by m;  

- hence x = z (mod m).

Thus the relation is transitive.

Accordingly, the relation of congruence modulo m on Z in an equivalence relation.

Partial Order Set or Poset

- A binary relation R defined on set A is called Partial Order Relation (POR) if R satisfies following properties :  

- Reflexive: (a, a) belongs to R where all a belongs to A

- Antisymmetric: If (a, b) belongs to R and (b, a) belongs to R, then a = b

- Transitive: If (a, b) belongs to R and (b, c) belongs to R => (a, c) belongs to R where a, b, c belongs to A

A set A together with a partial order relation R is called partial order set or poset.

Question: Show that the inclusion relation ⊆ is a partial ordering on the power set of a set S

 

Reflexivity : A ⊆ A whenever A is a subset of S.

Antisymmetry : If A and B are positive integers with A ⊆ B and B ⊆ A, then A = B.

Transitivity : If A ⊆ B and B ⊆ C, then A ⊆ C.

Hasse Diagram

- It is a graphical representation of poset)  

- It captures ordering relations among the elements without redundancies.

Properties:  

- Elements of the poset are represented as nodes or points.  

- If element a is directly below or less than element b in the poset (i.e., a≤b), there is a line connecting a and b in the diagram.  

- A Hasse diagram only includes lines between elements directly related in the poset, avoiding redundant lines.

Question: Consider the set A = {4, 5, 6, 7}. Let R be the relation ≤ on A. Draw the directed graph and the Hasse diagram of R.

Question: Draw the Hasse diagram for the set P(S), where S = {a, b, c, d}.

- Minimal Element:

An element with no predecessors (no elements are directly below it) in a Hasse diagram.  

- Maximal Element:

An element with no successors (no elements are directly above it) in a Hasse diagram.  

- Minimum Element:

The lowest element in a Hasse diagram, if it exists, with no edges leading downward from it.  

- Maximum Element:

The highest element in a Hasse diagram, if it exists, with no edges leading upward from it.

- Lower Bound (lb):

A common ancestor of elements in a subset, located at a level below all elements in the subset.  

- Upper Bound (ub):

A common descendant of elements in a subset, located at a level above all elements in the subset.

- Greatest Lower Bound (lub) or infimum: 

The lowest common ancestor of elements in a subset.

- Least Upper Bound (lub) or supremum:

The highest common descendant of elements in a subset.

- Join Semilattice:

A Hasse diagram forms a join semilattice if it provides a least upper bound (lub) for every pair of elements.

- Meet Semilattice:

A Hasse diagram forms a meet semilattice if it provides a greatest lower bound (glb) for every pair of elements.

Lattice

- A lattice is a partially ordered set where every pair of elements has a least upper bound and a greatest lower bound, denoted by ∨ and ∧ respectively.  

- It's represented as (L,∨,∧).

Question : Consider the set L={1,2,3,4,6,12} partially ordered by divisibility. Determine whether L forms a lattice or not. If it does, find the join and meet operations for each pair of elements.

First, we need to verify that the poset on the set L.

Step 1:

- Reflexivity: Every element divides itself, so a∣a for all a in L.  

- Antisymmetry: If a|b and b|a, then a=b.  

- Transitivity: If a|b and b|c, then a|c.

Since it follows three property then it is poset on L.

Step 2:

Step 3: Conclusion

Since for every pair of elements in L, both the join and meet operations exist, and they satisfy the lattice properties, L forms a lattice under the divisibility relation.

Properties of Lattice

1. Idempotent property : 

i) a v a = a  ii) a v a = a

2. Commutative property : 

i) a v b = b v a  ii) a v b = b v a

3. Associative property :

i) a v (b v c) = (a v b) v c  ii) a v (b v c) = (a v b) v c

4. Absorption property : 

i) a v (a Λ b) = a  ii) a Λ (a v b) = a

5. Distributive Inequality :

i) a Λ (b v c) >= (a Λ b) v (a Λ c)

ii) a v (b Λ c) <= (a v b) Λ (a v c)

Types of Lattice

1. Bounded Lattice:

- A lattice L is said to be bounded if it has the greatest element I and a least element 0.

2. Complement Lattice:

- for any element a in L, its complement a is another element such that when combined with a,

- it produces the greatest element 1, and their meet results in the least element 0.

3. Distributive Lattice:

- A lattice L is said to be distributive if for any element a, b and c of L following properties are satisfied :

i) a v (b Λ c) = (a v b) Λ (a v c)

ii) a Λ (b v c) = (a Λ b) v (a Λ c)

otherwise L is non-distributive lattice

4. Modular Lattice:

A lattice (L, <=) is called modular lattice if, a v (b Λ c) = (a v b) Λ c whenever a <= c for all a, b, c belongs to L.

5. Complete Lattice:

- A lattice L is called complete if each of its nonempty subsets has a least upper bound and greatest lower bound.

Example:

1. (Z, <=) is not a complete lattice

2. It is a complete lattice