Sri Gommateshayanamaha
[Link] Prasaraka Sangha(Regd.)
BAHUBALI COLLEGE OF ENGINEERING
Shravanabelagola-573 135, District: Hassan
(Approved by AICTE, New Delhi, Recognised by Govt. of Karnataka and Affiliated to Visvesvaraya Technological University, Belagavi)
DEPARTMENT OF CSE/ISE/AIML
Discrete Mathematical Structure
BCS405A Question Bank
Q.
Module-1: Fundamentals of Logic
No
Define Tautology. Show that the following are Tautology:
𝒊) [(¬𝒒) ∧ (𝒑 → 𝒒)] → (¬𝒑)
𝒊𝒊) [(𝒑 → 𝒒) ∨ (𝒑 → 𝒓)] → [𝒑 → (𝒒 ∨ 𝒓)]
𝒊𝒊𝒊) [(𝒑 → 𝒒) ∧ (𝒑 → ¬𝒒)] ↔ ¬𝒑
1. 𝒊𝒗) [(𝒑 → 𝒒) ∧ (𝒒 → 𝒓)] → [(𝒑 ∨ 𝒒) → 𝒓]
𝒗) [(𝒑 ∨ 𝒒)) → 𝒓] ∧ (¬𝒑) → (𝒒 → 𝒓)
𝒗𝒊) [(𝒑 → 𝒒) ∧ (𝒒 → 𝒓)] → [𝒑 → 𝒓]
𝒗𝒊𝒊) [(𝒑 ∨ 𝒒) ∧ {(𝒑 → 𝒓) ∧ (𝒒 → 𝒓)}] → 𝒓
𝒗𝒊𝒊𝒊) [(𝒑 ∧ 𝒒) → 𝒓] → [𝒑 →(𝒒 ∨ 𝒓)]
𝒊𝒙) { 𝒑 →(𝒒 → 𝒓)} → {(𝒑 → 𝒒) → (𝒑 → 𝒓)}.
Show that the following are Logical Equivalence:
𝒊) [𝒑 → (𝒒 ∧ 𝒓)] ⇔ [ (𝒑 → 𝒒) ∧ (𝒑 → 𝒓) ]
𝒊𝒊) [(𝒑 ∨ 𝒒) → 𝒓] ⇔ [ (𝒑 → 𝒓) ∧ (𝒒 → 𝒓) ]
2.
𝒊𝒊𝒊) [ (𝒑 ∨ 𝒒) → 𝒓 ] ⇔ [ ¬𝒓 → ¬(𝒑 ∨ 𝒒) ]
𝒊𝒗) [ (𝒑 ↔ 𝒒) ∧ (𝒒 ↔ 𝒓) ∧ (𝒓 ↔ 𝒑) ] ⇔ [ (𝒑 → 𝒒) ∧ (𝒒 → 𝒓) ∧ (𝒓 → 𝒑) ]
𝒗) [ (𝒑 → 𝒒) ∧ (𝒑 → 𝒓) ] ⇔ 𝒑 → (𝒒 ∧ 𝒓).
Using the laws of logic, prove the following logical equivalences:
𝒊) 𝒑 ∨ [𝒑 ∧ (𝒑 ∨ 𝒒)] ⇔ 𝒑
𝒊𝒊) [𝒑 ∨ 𝒒 ∨ (¬𝒑 ∧ ¬𝒒 ∧ 𝒓)] ⇔ (𝒑 ∨ 𝒒 ∨ 𝒓)
𝒊𝒊𝒊) [(¬𝒑 ∨ ¬𝒒) → (𝒑 ∧ 𝒒 ∧ 𝒓)] ⇔ 𝒑 ∧ 𝒒
𝒊𝒗) [(𝒑 ∨ 𝒒) ∧ (𝒑 ∨ ¬𝒒)] ∨ 𝒒 ⇔ 𝒑 ∨ 𝒒
𝒗) (𝒑 → 𝒒) ∧ [¬𝒒 ∧ (𝒓 ∨ ¬𝒒)] ⇔ ¬(𝒒 ∨ 𝒑)
3.
𝒗𝒊) 𝒑 → (𝒒 → 𝒓) ⇔ (𝒑 ∧ 𝒒) → 𝒓
𝒗𝒊𝒊) [¬𝒑 ∧ (¬𝒒 ∧ 𝒓)] ∨ [(𝒒 ∧ 𝒓) ∨ (𝒑 ∧ 𝒓)] ⇔ 𝒓
𝒗𝒊𝒊𝒊) ¬ [(𝒑 ∨ 𝒒) ∧ 𝒓] → ¬𝒒] ⇔ 𝒒 ∧ 𝒓
𝒊𝒙) ¬ [¬ [(𝒑 ∨ 𝒒) ∧ 𝒓] ∨ ¬𝒒] ⇔ 𝒒 ∧ 𝒓
𝒙) [(¬𝒑 ∨ ¬𝒒) ∧ (𝑭𝟎 ∨ 𝒑) ∧ 𝒑] ⇔ 𝒑 ∧ ¬𝒒
𝒙𝒊) ¬ [(𝒑 ∨ 𝒒) ∧ 𝒓] → ¬𝒒] ⇔ ¬ [¬ [(𝒑 ∨ 𝒒) ∧ 𝒓] ∨ ¬𝒒] ⇔ 𝒒 ∧ 𝒓.
Sri Gommateshayanamaha
[Link] Prasaraka Sangha(Regd.)
BAHUBALI COLLEGE OF ENGINEERING
Shravanabelagola-573 135, District: Hassan
(Approved by AICTE, New Delhi, Recognised by Govt. of Karnataka and Affiliated to Visvesvaraya Technological University, Belagavi)
DEPARTMENT OF CSE/ISE/AIML
Test whether the following statements are valid:
a) If Rohith hits a Century then he gets a free car. Rohith hits a Century. Therefore Rohith
gets a free car.
b) If I study, then i do not fail in the examination. If I do not fail in the examination my
father gifts a car to me. Therefore, if i study then my father gifts a car to me.
c) If Ravi goes out with friends, he will not study. If Ravi does not study, his father becomes
angry. His father is not angry. Therefore, Ravi not goes out with friends.
d) If I study, I will not fail in the examination. If I do not watch TV in the evenings, I will
4. study. I failed in the examination. Therefore, I must have watched TV in the evenings.
e) If A gets a supervisor’s position and works hard, then he will get a raise. If he gets a raise,
then he will buy a car. He has not purchased a car. Therefore, he did not get the
supervisor’s position or he did not work hard.
f) If Ram studies then he will pass 12th. If Ram passes 12th then his father gifts him a bike. If
Ram doesn’t play video game then he will pass 12th. Ram did not get a bike. Therefore,
Ram played video game.
g) If a triangle has two equal sides, then it is isosceles. If a triangle is isosceles, then it has
two equal angles. A certain triangle PQR does not have two equal angles. Therefore, the
triangle PQR does not have two equal sides.
Establish the validity of the following argument using the rules of inference:
(𝒊) { 𝒑 ∧ (𝒑 → 𝒒) ∧ (𝒔 ∨ 𝒓) ∧ (𝒓 → ¬𝒒)} → (𝒔 ∨ 𝒕)
(𝒊𝒊) { (𝒑 → 𝒒) ∧ (𝒒 → (𝒓 ∧ ¬𝒔)) ∧ ¬𝒓 ∨ (¬𝒕 ∨ 𝒖) ∧ (𝒑 ∧ 𝒕)} → 𝒖
(𝒊𝒊𝒊) { 𝒑 → (𝒒 → 𝒓) ∧ (¬𝒒 → ¬𝒑) ∧ 𝒑 } → 𝒓
5. (𝒊𝒗) { (¬𝒑 ↔ 𝒒) ∧ (𝒒 → 𝒓) → 𝒓 } → 𝒑
(𝒗) { (𝒑 → 𝒓) ∧ (𝒓 → 𝒔) ∧ (𝒕 ∨ ¬𝒔) ∧ (¬𝒕 ∨ 𝒖) ∧ ¬𝒖 } → ¬𝒑
(𝒗𝒊) { (¬𝒑 ∨ 𝒒) → 𝒓 ∧ (𝒓 → (𝒔 ∨ 𝒕)) ∧ (¬𝒔 ∧ ¬𝒖) ∧ (¬𝒖 → ¬𝒕)} → 𝒑
(𝒗𝒊𝒊) { (¬𝒑 ∨ ¬𝒒) → (𝒓 ∧ 𝒔) ∧ (𝒓 → 𝒕) ∧ ¬𝒕 } → 𝒑
(𝒗𝒊𝒊𝒊){ (𝒑 → 𝒒) ∧ (𝒓 → 𝒔) ∧ ( ¬𝒒 ∨ ¬𝒔)} → ¬(𝒑 ∧ 𝒓).
Define logical equivalence of two propositions. Prove the following logical equivalences using
laws of logic:
(𝒊) 𝒑 ∨ [𝒑 ∧ (𝒑 ∨ 𝒒)] ⇔ 𝒑
6. (𝒊𝒊) [(¬𝒑 ∨ ¬𝒒) → (𝒑 ∧ 𝒒 ∧ 𝒓) ⇔ 𝒑 ∧ 𝒒
(𝒊𝒊𝒊) 𝒑 ∨ 𝒒 ∨ (~𝒑 ∧ ~𝒒 ∧ 𝒓) ≡ 𝒑 ∨ 𝒒 ∨ 𝒓
(𝒊𝒗) (𝒑 → 𝒒) ∧ (¬𝒒 ∧ (𝒓 ∨ ¬𝒒 )) ⇔ [𝒒 ∨ 𝒑]
(𝒗)[¬𝒑 ∧ (¬𝒒 ∧ 𝒓)] ∨ [(𝒒 ∧ 𝒓) ∨ (𝒑 ∧ 𝒓)] ⇔ 𝒓.
7. Define i) an open statement, ii) Quantifiers, iii) Proposition.
Test the validity of the following arguments:
(𝒊) 𝒑 ∧ 𝒒 (𝒊𝒊) 𝒑
8. 𝒑 → (𝒒 → 𝒓) 𝒑 → ~𝒒
∴ 𝒓 ~𝒒 → ~𝒓
∴~𝒓
9. Write the converse, inverse and contra positive of the conditional:
(i) If a quadrilateral is a parallelogram, then its diagonals bisect each other.
Sri Gommateshayanamaha
[Link] Prasaraka Sangha(Regd.)
BAHUBALI COLLEGE OF ENGINEERING
Shravanabelagola-573 135, District: Hassan
(Approved by AICTE, New Delhi, Recognised by Govt. of Karnataka and Affiliated to Visvesvaraya Technological University, Belagavi)
DEPARTMENT OF CSE/ISE/AIML
(ii) If a real number 𝒙𝟐 is greater than zero, then 𝒙 is not equal to zero.
(iii) If a triangle is not isosceles, then it is not equilateral.
(iv) If Ram can solve the puzzle, then Ram can solve the problem.
For the universe of all integers let 𝒑(𝒙): 𝒙>𝟎, 𝒒(𝒙)∶ x is even, 𝒓(𝒙): x is a perfect square, 𝒔(𝒙): x
is divisible by 3, 𝒕(𝒙): x is divisible by 7. Write the following statements in symbolic form:
(a) At least one integer is even,
10. (b) There exists a positive integer that is even,
(c) Some even integers are divisible by 3,
(d) Every integer is either even or odd,
(e) If x is even and a perfect square then x is not divisible by 3,
(f) If x is odd or is not divisible by 7 then x is divisible by 3.
11. Write the following statement in symbolic form and find its negation:
“If all triangles are right angled then no triangle is equilateral”.
For the following statements, the universe comprises all non-zero integers. Determine the
truth value of each statement.
12.
a) ∋ 𝒙 ∋ 𝒚[𝒙𝒚 = 𝟏], b) ∋ 𝒙∀𝒚[𝒙𝒚 = 𝟏], c) ∀𝒙𝒚[𝒙𝒚 = 𝟏], d) ∋ 𝒙𝒚[(𝟐𝒙 + 𝒚 = 𝟓) ∧
(𝒙 − 𝟑𝒚 = −𝟖)], e) ∋ 𝒙 ∋ 𝒚[(𝟑𝒙 − 𝒚 = 𝟕) ∧ (𝟐𝒙 + 𝟒𝒚 = 𝟑)].
Prove the following by Direct proof, Indirect Proof and Proof of contradiction:
(i) If m is an even integer then m + 7 is an odd integer.
13. (ii) If 𝒏𝟐 is an odd integer then n is an odd integer.
(iii) For all integers 𝒌 𝒂𝒏𝒅 𝒍, prove the following statements:
(a) if 𝒌 𝒂𝒏𝒅 𝒍 are both odd, then 𝒌 + 𝒍 is even.
(b) if 𝒌 𝒂𝒏𝒅 𝒍 are both odd then, 𝒌𝒍 is odd.
14. For any two odd integers m and n, show that: (i) m + n is odd (ii) mn is odd.
Prove the following by Direct proof, Indirect Proof and Proof of contradiction:
15. "If n is an odd integer then 𝒏 + 𝟗 is an even integer".
“The product of two even integers is an even integer”.