Top 22 Discrete Mathematics Interview Questions You Must Prepare 19.Mar.2024

A Contradiction is a formula which is always false for every value of its propositional variables.

Example − Prove (A∨B)∧[(¬A)∧(¬B)] is a contradiction

Whenever sets are being discussed, the relationship between the elements of the sets is the next thing that comes up. Relations may exist between objects of the same set or between objects of two or more sets.

Discrete Mathematics is a branch of mathematics involving discrete elements that uses algebra and arithmetic. It is increasingly being applied in the practical fields of mathematics and computer science. It is a very good tool for improving reasoning and problem-solving capabilities. 

Power set of a set S is the set of all subsets of S including the empty set. The cardinality of a power set of a set S of cardinality n is 2n. Power set is denoted as P(S).

Example −For a set S={a,b,c,d} let us calculate the subsets −

  • Subsets with 0 elements − {∅} (the empty set)
  • Subsets with 1 element − {a},{b},{c},{d}
  • Subsets with 2 elements − {a,b},{a,c},{a,d},{b,c},{b,d},{c,d}
  • Subsets with 3 elements − {a,b,c},{a,b,d},{a,c,d},{b,c,d}
  • Subsets with 4 elements − {a,b,c,d}

Sets can be represented in two ways −

Roster or Tabular Form: The set is represented by listing all the elements comprising it. The elements are enclosed within braces and separated by commas.

Example 1 − Set of vowels in English alphabet, A={a,e,i,o,u}A={a,e,i,o,u}

Example 2 − Set of odd numbers less than 10, B={1,3,5,7,9}

Set Builder Notation: The set is defined by specifying a property that elements of the set have in common. The set is described as A={x:p(x)}A={x:p(x)}

Example 1 − The set {a,e,i,o,u}{a,e,i,o,u} is written as- A={x:x is a vowel in English alphabet}A={x:x is a vowel in English alphabet}

Example 2 − The set {1,3,5,7,9}{1,3,5,7,9} is written as -B={x:1≤x<10 and (x%2)≠0}

A predicate is an expression of one or more variables defined on some specific domain. A predicate with variables can be made a proposition by either assigning a value to the variable or by quantifying the variable.

The following are some examples of predicates −

  • Let E(x, y) denote "x = y"
  • Let X(a, b, c) denote "a + b + c = 0"
  • Let M(x, y) denote "x is married to y"

A Tautology is a formula which is always true for every value of its propositional variables.

Example − Prove [(A→B)∧A]→B is a tautology

A Function assigns to each element of a set, exactly one element of a related set. Functions find their application in various fields like representation of the computational complexity of algorithms, counting objects, study of sequences and strings, to name a few. The third and final chapter of this part highlights the important aspects of functions.

Sets can be classified into many types. Some of which are finite, infinite, subset, universal, proper, singleton set, etc.

Finite Set: A set which contains a definite number of elements is called a finite set.

Infinite Set: A set which contains infinite number of elements is called an infinite set.

Subset: A set X is a subset of set Y (Written as X⊆Y) if every element of X is an element of set Y.

Proper Subset: The term “proper subset” can be defined as “subset of but not equal to”. A Set X is a proper subset of set Y (Written as X⊂YX⊂Y) if every element of X is an element of set Y and |X|<|Y|.

Universal Set: It is a collection of all elements in a particular context or application. All the sets in that context or application are essentially subsets of this universal set. Universal sets are represented as UU.

Empty Set or Null Set: An empty set contains no elements. It is denoted by ∅. As the number of elements in an empty set is finite, empty set is a finite set. The cardinality of empty set or null set is zero.

Singleton Set or Unit Set: Singleton set or unit set contains only one element. A singleton set is denoted by {s}.

Equal Set: If two sets contain the same elements they are said to be equal.

Equivalent Set: If the cardinalities of two sets are same, they are called equivalent sets.

Overlapping Set: Two sets that have at least one common element are called overlapping sets.

In case of overlapping sets −

  • n(A∪B)=n(A)+n(B)−n(A∩B)
  • n(A∪B)=n(A−B)+n(B−A)+n(A∩B)
  • n(A)=n(A−B)+n(A∩B)
  • n(B)=n(B−A)+n(A∩B)

Disjoint Set: Two sets A and B are called disjoint sets if they do not have even one element in common. Therefore, disjoint sets have the following properties −

  • n(A∩B)=∅
  • n(A∪B)=n(A)+n(B)

A set is an unordered collection of different elements. A set can be written explicitly by listing its elements using set bracket. If the order of the elements is changed or any element of a set is repeated, it does not make any changes in the set.

Some Example of Sets

  • A set of all positive integers
  • A set of all the planets in the solar system
  • A set of all the states in India
  • A set of all the lowercase letters of the alphabet

We can convert any proposition in two normal forms −

 Conjunctive Normal Form: A compound statement is in conjunctive normal form if it is obtained by operating AND among variables (negation of variables included) connected with ORs. In terms of set operations, it is a compound statement obtained by Intersection among variables connected with Unions.

Disjunctive Normal Form: A compound statement is in conjunctive normal form if it is obtained by operating OR among variables (negation of variables included) connected with ANDs. In terms of set operations, it is a compound statement obtained by Union among variables connected with Intersections.

Two statements X and Y are logically equivalent if any of the following two conditions hold −

  • The truth tables of each statement have the same truth values.
  • The bi-conditional statement X⇔Y is a tautology.

Example − Prove ¬(A∨B)and[(¬A)∧(¬B)] are equivalent

A Contingency is a formula which has both some true and some false values for every value of its propositional variables.

Example − Prove (A∨B)∧(¬A) a contingency

  • N − the set of all natural numbers = {1,2,3,4,.....}
  • Z − the set of all integers = {.....,−3,−2,−1,0,1,2,3,.....}
  • Z+ − the set of all positive integers
  • Q − the set of all rational numbers
  • R − the set of all real numbers
  • W − the set of all whole numbers

Two functions f:A→Bf:A→B and g:B→Cg:B→C can be composed to give a composition gof. This is a function from A to C defined by (gof)(x)=g(f(x))

Duality principle states that for any true statement, the dual statement obtained by interchanging unions into intersections (and vice versa) and interchanging Universal set into Null set (and vice versa) is also true. If dual of any statement is the statement itself, it is said self-dual statement.

Example − The dual of (A∩B)∪C is (A∪B)∩C

Cardinality of a set S, denoted by |S|, is the number of elements of the set. The number is also referred as the cardinal number. If a set has an infinite number of elements, its cardinality is ∞.

Example − |{1,4,3,5}|=4,|{1,2,3,4,5,…}|=∞|

If there are two sets X and Y,

  • |X|=|Y| denotes two sets X and Y having same cardinality. It occurs when the number of elements in X is exactly equal to the number of elements in Y. In this case, there exists a bijective function ‘f’ from X to Y.
  • |X|≤|Y| denotes that set X’s cardinality is less than or equal to set Y’s cardinality. It occurs when number of elements in X is less than or equal to that of Y. Here, there exists an injective function ‘f’ from X to Y.
  • |X|<|Y| denotes that set X’s cardinality is less than set Y’s cardinality. It occurs when number of elements in X is less than that of Y. Here, the function ‘f’ from X to Y is injective function but not bijective.
  • If |X|≤|Y| and |X|≤|Y|then |X|=|Y|. The sets X and Y are commonly referred as equivalent sets.

A proposition is a collection of declarative statements that has either a truth value "true” or a truth value "false". A propositional consists of propositional variables and connectives. We denote the propositional variables by capital letters (A, B, etc). The connectives connect the propositional variables.

Some examples of Propositions are given below −

  • "Man is Mortal", it returns truth value “TRUE”
  • "12 + 9 = 3 – 2", it returns truth value “FALSE”

Bell numbers give the count of the number of ways to partition a set. They are denoted by Bn where n is the cardinality of the set.

In propositional logic generally we use five connectives which are −

  • OR (∨)
  • AND (∧)
  • Negation/ NOT (¬)
  • Implication / if-then (→)
  • If and only if (⇔).

OR (∨) − The OR operation of two propositions A and B (written as A∨B) is true if at least any of the propositional variable A or B is true.

Set Operations include Set Union, Set Intersection, Set Difference, Complement of Set, and Cartesian Product.

Set Union: The union of sets A and B (denoted by A∪B) is the set of elements which are in A, in B, or in both A and B. Hence, A∪B={x|x∈A OR x∈B}.

Set Intersection: The intersection of sets A and B (denoted by A∩B) is the set of elements which are in both A and B. Hence, A∩B={x|x∈A AND x∈B}.

Set Difference/ Relative Complement

The set difference of sets A and B (denoted by A–B) is the set of elements which are only in A but not in B. Hence, A−B={x|x∈A AND x∉B}.

Complement of a Set: The complement of a set A (denoted by A′A′) is the set of elements which are not in set A. Hence, A′={x|x∉A}.

More specifically, A′=(U−A) where U is a universal set which contains all objects.

Mathematics can be broadly classified into two categories −

Continuous Mathematics − It is based upon continuous number line or the real numbers. It is characterized by the fact that between any two numbers, there are almost always an infinite set of numbers. For example, a function in continuous mathematics can be plotted in a smooth curve without breaks.

Discrete Mathematics − It involves distinct values; i.e. between any two points, there are a countable number of points. For example, if we have a finite set of objects, the function can be defined as a list of ordered pairs having these objects, and can be presented as a complete list of those pairs.