Discrete Mathematics — Summer 2022

Determine whether each of these statements is true or false. 1)0 ∈ ∅ 2)∅ ⊂ {0} 3){0} ∈ {0} 4) ∅ ∈ {∅} 5){∅} ∈ {{∅}} 6) {{∅}} ⊂ {∅,{∅}}

Determine whether f is a function from the set of all bit strings to the set of integers if 1) f(s) is the position of a 0 bit in S. 2) f(s) is the number of a 1 bits in S. Find the range of each of the following functions that assigns: 3) to a bit string the number of one bits in the string 4) to each bit string twice the number of zeros in that string.

1) Find the bitwise OR, and bitwise XOR of the bit string 1111 0000, 2) Show that the function f:R → R+ ∪{0} defined by f(x) = |x| is not invertible. Modify the domain or codomain of f so that it becomes invertible. 3) Let Sbe subset of a universal set ∪. The characteristic function f S : ∪→ {0,1} , f (x) = 1,if x ∈ Sand 0 is x ∉ S. S Let Aand Bbe sets. Then show that f (x) = f (x).f (x) A∩B A B

Let P(x) be the statement “x = x2 “. If the domain consists of the integers, what are the truth values of the following? 1) ∃x P(x) 2) ∀x ¬P(x) 3) ∃x ¬P(x)

Identify the error or errors in this argument that supposedly shows that if ∃x P(x)∧∃x Q(x) is true then ∃x (P(x)∧Q(x)) is true. 1. ∃x P(x)∧∃x Q(x) Premise 2. ∃x P(x) Simplification from (1) 3. P(c) Existential instantiation from (2) 4. ∃x Q(x) Simplification from (1) 5. Q(c) Existential instantiation from (2) 6. P(c)∧Q(c) Conjunction from (3) and (5) 7. ∃x (P(x)∧Q(x)) Existential generalization

1) Use a truth table to verify the De Morgan’s law ¬(p∨q) ≡ ¬p∧¬q 2) Show that (p → q)∧(q → r) → (p → r) is a tautology. OR1

1) Suppose that the domain of Q(x, y, z) consists of triples x, y, z, where x = 0, 1, or 2, y = 0 or 1, and z = 0 or 1. Write out following propositions using disjunctions and conjunctions.

∃z¬Q(0,0,z) ii). ∀yQ(0,y,0) 2)

Show that ∃x P(x) ∧∃x Q(x) and ∃x(P(x)∧Q(x)) are not logically equivalent. ii) Show that ∃x(P(x)∨Q(x)) and ∃x P(x) ∨∃x Q(x) are logically equivalent.

For the relation {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} on the set {1,2,3,4}, decide whether it is reflexive, whether it is symmetric, whether it is antisymmetric, and whether it is transitive..(Justify your answer if the property is not satisfied)

For the following relations on the set of real numbers, R = {(a,b) ∈ R2|a ≥ b}, R = {(a,b) ∈ R2|a ≤ b}12 R = {(a,b) ∈ R2|a ≠ b} find3 1) R ⨁R 2) Ro R

1) Draw the Hasse diagram for the poset ({2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72}, |). Hence find glb({60,72}) and all maximal elements. 2) Determine whether the relation with the directed graph shown is an equivalence relation.

Suppose that the relations Rand Ron a set Aare represented by the matrices M = [1 0 0] and M = [0 1 1] R1 R2 What are the matrices representing R ∪Rand R ∩R ?

Use Warshall’s algorithm to find the transitive closures of the relation R = {(1,4),(2,1),(2,3),(3,1),(3,4),(4,3)} on {1,2,3,4}

1) Draw the Hasse diagram for the poset({2, 4, 5, 10, 12, 20, 25}, |). Hence, find the are maximal and minimal elements. 2) Which of these collections of subsets are partitions of {1, 2, 3, 4, 5, 6}? Justify your answer if it is not a partition.

Explain Path and Circuit of a graph.

1) Define Isomorphic Graphs 2) Verify the following graphs are Isomorphic or not (Justify). Graph -1 Graph-2

1) Define Subtree and Degree of a Node 2) Determine degree of the each node for the following tree.

1) Define: i) Isolated vertex ii) Null graph 2) Identify Isolated vertex/vertices from the following graph

1) Define incidence Matrix of a Graph 2) Find incidence matrix for the following graph

1) Define: M-ary Tree and Binary Tree. 2) Represent the following directed tree as Binary tree3

1) Define: SemiGroups. 2) Let S = {a, b, c, d}. The following multiplication table, define operations ∙ on S. Is 〈S, ∙〉semigroup? Justify

Let H = {1,–1} and G = {1,–1,i,–i} . (H,×) is a sub-group (G,×). Then find all left cosets and right cosets of Hin G.

1) Define:Ring. 2) Write elements of the ring 〈z , + , × 〉. And find −3,−8 ,3−1,4−1

Consider the set Qof a rational numbers. Let ∗ be the operation on Q defined by a∗b = a+b −ab. Find 1) 3 ∗ 4 2) the identity element for ∗.

Write the equivalence classes for congruence modulo 4 i.e.. z4 Let the subset H={[0],[2]} is a subgroup of G = 〈z ,+ 〉. Then determine44 all left cosets of Hin G.

We are given the ring 〈{a,b,c,d},+,∙〉 the operations + and ∙ on Rare as shown in the following table. + a b c d ∙ a b c d a a b c d a a a a a b b c d a b a c a c c c d a b c a a a a d d a b c d a c a a 1 ) Does it have an identity? 2) What is the zero of this ring? 3) Find the additive inverse of each of its elements