Discrete Mathematics Assignment Solution - Comprehensive Analysis

This document presents a comprehensive solution to a discrete mathematics assignment. The solution covers several key areas within the subject, including combinatorial problems involving choosing players for a team. It provides detailed explanations and applications of Boolean algebra laws, demonstrating concepts such as annulment, identity, idempotent, complement, commutative, double negation, De Morgan's theorem, distributive, absorptive, and associative laws. The assignment also explores predicate logic, offering solutions to problems involving predicates and quantifiers. Furthermore, the document addresses the binary sort algorithm, illustrating its application to sort an unsorted array and insert a new element. Finally, the solution includes an explanation of decision trees, describing their structure and functionality in the context of problem-solving. This assignment provides valuable insight into fundamental concepts of discrete mathematics.

Running Head: Discrete Maths 1
Discrete Mathematics
Name of Student
Name of Professor
Date

Discrete Maths 2
Question 1
a) nCr= n!
r !× ( n−r ) ! = 6 !
1! × ( 6−1 ) ! =6
b) 6
c) 24 =16
d) Choosing bowlers 4 out of 5
Choosing 1 wicketkeeper out of 2
Choosing the remaining 6 players out of 11
( 5 C 4 ) ( 2C 1 ) ( 10 C 6 )+ (5 C 4 ) ( 2 C 2 ) ( 10C 5 ) + ( 5C 5 ) ( 2C 1 ) ( 10 C 5 ) + ( 5 C 5 ) ( 2C 2 ) ( 10 C 4 ) = ( 5× 2× 210 ) + ( 5 ×
¿ 2100+1260+504 +210
¿ 4074
Question 2
Laws of Boolean Algebra
a) Annulment law
A .0=0 ;
A 0
0
A+1=1 ;

Discrete Maths 3
A 1
1
b) Identity law
A+0= A ;
A A
0
A .1= A;
A A
1
c) Indempotent law
A+ A= A;
A A
A
A . A= A;

Discrete Maths 4
A A
A
d) Complement law
A+ A'=1
A 1
A '
A . A' =0
A 0
A '
e) Commutative law
A . B=B . A
A AB ≡ B BA

Discrete Maths 5
B A
A+B=B+ A
A A+B ≡ B B+A
B A
f) Double Negation Law
A double complement of a variable is equal to the variable
A' '= A
A '
A A
g) De Morgan’s theorem
A+B= A . B
A A
B ≡ B
A . B= A+ B

Discrete Maths 6
A A
B ≡ B
h) Distributive law
A ( B+C ) =A . B+ A . C
A
A B
B ≡ A
C C
g) Absorptive law
A+ ( A . B ) = A
A A
A
B
A ( A+ B )= A

Discrete Maths 7
A A
A
B
i) Associative law
A+ ( B+C ) = ( A+B ) +C= A+ B+C
A bb A A+B
B A+ (B+C) = B
C B+C C
A ( B .C )= ( A . B ) C= A . B . C

Discrete Maths 8
A A
B ≡ B
C C
Question 3
a) ∀ x [Px → Qx] where P is the predicate man ,Q is the predicate mortal
b)∃ xPxwhere P(x) is the predicate that denotes x is dishonest and∃(x) denotes some men
c) Q ( 3 ,4 ,5) is true for x2+ y2=z2 . Q (2,2,1) is false. The following values make the statement
true
Q(3, 4, 5), Q(5,12,13), Q(7,24,25) Q(8,15,17) Q(9,40,41) Q(11,60,61) Q(12,35,37)
Q(13,84,85) Q(16,63,65) Q(20 21 29) Q(28,45,53) Q(33,56,65) Q(36,77,85) Q(39,80,89)
Q(48,55,73) Q(65,72,97) hence 16 values make the predicate true.
Question 4
a) The binary sort algorithm is used to order an unsorted array into increasing elements.
The array contains eight elements.
113, 114, 97, 116, 120, 123, 125, 127

Discrete Maths 9
Thus, dividing the list into two. The middle numbers are 116 and 120 which are in order.
Dividing the array into 2 with four elements and then dividing them further by 2 gives 114 and
97 which are not okay and they are therefore switched to 97,114 and the second part has 123 and
125 which are okay.
The array is thus
113, 97, 114, 116,120,123,125,127
Dividing the array further by two yields the parts
113, 97 114, 116 120,123 125,127
The first part is unsorted thus switching the elements gives 97,113. The other elements are well
sorted. The sorted complete array is thus,
97, 113, 114, 116, 120, 123, 125, 127
b) To insert 121 a binary search is done. The middle numbers are 120 and 123. 120<121 and
123>121 therefore the number falls in between the two numbers.
The full array is thus 97, 113, 114, 116, 120, 121, 123, 125, 127
Question 5
A decision tree is made in the form of a flowchart with the node representing a test and the
branches representing the results of that test. The leaf nodes represent the decision that has been
done after computation of all characteristics. Initially, the whole function is considered as the
root with the entropy (uncertainty level) of every case being progressively added on the branches
at the nodes.