UC1DMA101 Discrete Mathematics Assignment: Logic, Sets, and Relations

This assignment solution addresses key concepts in discrete mathematics, encompassing two main parts. Part 1 focuses on propositional logic, including identifying valid propositions, constructing truth tables, determining tautologies and contradictions, writing logical expressions, and applying logical equivalences. It also covers conditional statements, quantifiers, and translating between English sentences and logical notation. Part 2 delves into set theory, exploring set operations such as union, intersection, and complement, and identifying subsets and power sets. It also includes problems involving set builder notation, Venn diagrams, and relations. Finally, the assignment tackles concepts of reflexive and transitive relations. The solution provides detailed answers and explanations for each question, offering a comprehensive understanding of the topics covered.

PART 1
1)
a) Not a valid proposition as it is not a fact.
b) It is a pythagorean triplet so a valid proposition
c) Not a valid proposition
d) RGB it is a valid proposition
e) It is a valid proposition but the truth value is false as 3/2 is 1.5 which is not a natural
number
f) Area = L X B, it is a valid proposition
g) It is a valid proposition
h) It is not a valid proposition
i) It is a valid proposition
j) It is not a valid proposition
2)
P q p↔q p ^ ~q ~p ^ q (p ^ ~q)\/( ~p ^ q)
T T T F F F
T F F T F T
F T F F T T
F F T F F F
Therefore, (p↔q) ≡ ~ (p ^ ~q)\/( ~p ^ q)
3)
P q (~p /\ (q →p)) →~q
F F T
F T T
T F T
T T T
So it is a tautology.
4)
P q r p→q q→~r r→p F(p,q,r)
F F F T T T T
F T F T T T T
F T T T F F T
F F T T T F F
T F F F T T T
T F T F T T T
T T F T T T T
T T T T F T T

5)
a) ~ r /\ ~q
b) ~r /\ (p \/ q)
c) r /\ r
d) (~p /\ q) \/ (p /\ ~q)
6)
a) ( x, y € S) ~ (x*y = y-x)Ɐ
b) ⱻ x € A ~ (x1/2 ≤ x)
c) ⱻ x ⱻ y ~ Q(x, y)
d) x y ~ Q(x, -y)Ɐ Ɐ
e) x yⱯ Ɐ ⱻ z, ~ Q(x, y, z/2) + ~P x
7)
a) If the cook didn’t do it then the butler didn’t do it.
b) If the butler did it or the lawyer did it, then the cook did it.
c) The cook did it if and only if the butler did it and the lawyer did it.
d) If the butler did it, then the cook did it and if the lawyer didn’t do it then the butler
didn’t do it or the cook didn’t do it.
8)
a) He is not tall or not handsome.
b) He has neither blonde hair nor blue eyes.
c) He is rich or happy
d) He has not lost his job and he did go to work today.
9)
a) aⱯ
b) a /\ ~b
c) ~ a → b
d) ~ a → (b \/ a)
e) (a /\ b) \/ (~ a /\ ~b)
10)
a) False
b) True
c) True
d) False
11)
a) It is tautology, so it is true.
b) It is a contradiction, so it is entirely false.

c) It is a contradition, so it is entirely false.
12)
a) Note that hence
b) Note that hence
13)
a) True, since both p and q is false then the statement (p->q) should be true.
b) True, p : (6− 1=5), q: (5−3=2) and r: (2+5=7) since p, q and r true so the statement is
true
c) True, as it is an OR statement
d) True, as both p and q are true so p->q should be true.
14)
a) Contrapositive of if p then not q is – if not q then not p
Converse of if p then not q is - if q then p
Inverse of if p then not q is - if not p then not q
b) Contrapositive of If today is Wednesday, then I have a test today is – if I have a test
today then today is not Wednesday
Converse of If today is Wednesday, then I have a test today is - if I don’t have a test
today then today is Wednesday
Inverse of If today is Wednesday, then I have a test today is - If today is not Wednesday,
then I have a test today
15)
a) All x eats some y
b) No they are not same
16)
a) If the product is not divisible by 2 then it is a product of even and odd numbers
b) If today is Tuesday then it is sunny
c) If it is fish then it has eyes
d) If you are a king then you have a crown
17) He is not in Norway
18) Today it won’t snow
19) P (2, 2) truth value of the proposition is true
P (2, -2) truth value of the proposition is false.

20)
a)
P Q R S
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
S=PQ + R+QR
S=PQ . ´R +Q+R
S= ( P+ Q ) . R+Q+R
S=P R+Q R+Q+ R
S=P R+Q(R +1)+R
S=P R+Q+ R
b) The output S = 1 for the given input.
21)
((P \/ R) /\ (Q \/ R)) /\ T
 S = ((P \/ R) /\T) /\ ((Q \/ R) /\ T)
 S = ((P /\ T) \/ (R /\ T)) /\ ((Q /\ T) \/ (R /\ T))
The half-moon shape gates are AND gate and the crescent shape moon are OR gate.

PART 2
1)
a) {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
b) {1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196}
2)
a) Yes they are equal. b) They are not equal
c) No, they are not equal
3)
a) {3}
b) Null set
c) {1, 2, 4, 8, 16}
d) {1, 2, 3, 4 …}
4)
a) A = {x € Z | -3 ≤ x ≤ 3 & x ≠ 0}
b) B = {x | x = 2p | p € {0, 1, 2, 3, 4, 5}}
5) A = {1, 2, 3} and B = {-3 – 2i, -3 + 2i}
They are disjoint sets.
6)
a) ( x−1 ) 2=3
(x−1)=± √3
x=1 ± √ 3
Since given x is irrational so it is not an empty set.
b) ( x +1 ) 2=2
( x +1)=± √2
x=−1 ± √2
Since x is given rational and we get irrational values do it is an empty set.
7)
a) A = {-3, 3}
P (A) = {{-3}, {3}, {-3, 3}, φ}, therefore there are 4 elements.
b) B = {1, 2, 3}, P (B) = {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, φ}
There are going to be an 8 elements.
8) T = tablet, M = mobile
N (T) = 78, N (M) = 85,
N (T’ M’) = 8Ո
Total is 100. Therefore, N (T U M) = 100 - N (T’ M’) = 100 – 8 = 92.Ո
Now we know N (T U M) = N (T) + N (M) – N (T M)Ո

92 = 78 + 85 – N (T M)Ո
N (T M) = 71.Ո
There person liking both tablet and mobile is 71.
9)
10)
a) {1, 4, T, W}
b) {1, 4, c, x, y, z, 5, T, W}
c) Union Set U
d) Null set
e) P (C U B) = {{a}, {b}, {T}, {W} …} there will be total 16 elements in that.
f) C X B = {aT, aW, bT, bW}
g) B X A = {a, 4a, b, 4b}
h) A X B X C = { aT, aW, bT, bW, 4aT, 4aW, 4bT, 4bW}
i) B X A X B = {a2, 4a2, ba, 4ba, ab, 4ab, b2, 4 b2}
j) P (B X A X B) there will be 256 elements.
11)
a) Reflexive
b) Reflexive and Transitive
c) Nothing
d) Transitive

12)
A = Audi, B = BMW, M = Mercedes.
N (A) = 36, N (B) = 30, N (M) = 32, N (A B) = 10, N (B M) = 17, N (A M) = 21.Ո Ո Ո
N (A U B U M) = N (A) + N (B) +N (M) - N (A B) - N (B M) - N (A M) + N (AՈ Ո Ո Ո
M B)Ո
70 = 36 + 30 + 32 – 10 -17 -21 + N (A M B)Ո Ո
N (A M B) = 20Ո Ո
Since N (A M B) > N (A B) and N (A M B) > N (B M) which is not possible,Ո Ո Ո Ո Ո Ո
so there must be discrepancy in the data.
a) The data is not correct
b) The data is not correct
c) 20 people liked all the three cars
d) The data is not correct
13)
a) {2, 2}, {3, 2}, {3, 3}, {10, 2}, {10, 3}, {10, 4}, {10, 6}
b) Domain is {2, 3, 10}
c) Co Domain is {2, 3, 4, 6}