Department of Mathematics
Course title-Discrete Mathematical Structures
[As per Choice Based Credit System (CBCS) scheme]
(Effective from the academic year 2023-24)
SEMESTER -IV
Subject Code BCS405A IA Marks 25 +25 = 50
Marks
Number of Lecture 2:2:0:0 SEE Exam Marks 100 MARKS
Hours/Week
Total Number of Lecture Hours 40 HOURS Exam Hours 3 HOURS
CREDITS–3
QUESTION BANK - MODULE 1
SI Questions Mark
No.
1 Define the following: Proposition, Tautology, Contradiction and Dual of the statement with an 6M
example for each.
2 Determine whether the following compound proposition is Tautology or not 7M
i) {( p ∨ q) → r}↔ {¬ r → ¬( p ∨ q)}
ii) ((¬q)^(p→q)) → ¬ p
3 i) Show that the statement 𝑝 → (𝑝 → 𝑞) is a contingency. 7M
ii) Show that the statement ( 𝑝 → (𝑞 ∧ 𝑟)) →∼ (𝑝 → 𝑞) is a contingency.
4 Prove that, for any propositions p,q,r the compound proposition 7M
[( p ∨ q) → r] ⇔[( p → r ) ∧ (q → r )]
5 Prove that, for any propositions p,q,r the compound proposition 7M
[( p ↔ q) ∧ (q ↔ r ) ∧ (r ↔ p)] ⇔[( p → q) ∧ (q → r ) ∧ (r → p)]
6 Solve the following logical equivalences without using truth table 7M
[(¬ p ∨ ¬q) → ( p ∧ q ∧ r )]⇔p ∧ q
7 Simplify the compound statement ¬ (¬((p∨ q)∧ r)∨ ¬q) using laws of logic. 7M
8 Prove the logical equivalence by using the laws of logic. 7M
( p → q) ∧ [¬ q ∧ (r ∨ ¬ q)]⇔¬(q ∨ p)
9 Prove the logical equivalence by using the laws of logic. 7M
[ ¬ p ∧ ( ¬ q ∧ r )]∨ [ (q ∧ r ) ∨ ( p ∧ r )] ⇔r
10 Prove the following logical equivalences without using the truth tables 7M
i)¬[¬{(𝑝˅𝑞 )˄𝑟}˅¬𝑞 ] ⇔ 𝑞˄𝑟 ii) 𝑝 → (𝑞 → 𝑟) ⇔ (𝑝˄𝑞 ) → 𝑟.
11 Construct the truth table for NAND and NOR connectives and write down the converse, 7M
Inverse and contra positive statement of “If a triangle is isosceles then it is equilateral.”
12 Write the dual of a logical statement. If p, q are primitive statements prove that 6M
(¬𝑝˅𝑞 )˄(𝑝˄(𝑝˄𝑞 ))⬄(𝑝˄𝑞)
13 Define Converse, Inverse and Contrapositive of a conditional. Identify converse, inverse and 7M
contrapositive of Ɐx, (𝑥 > 3) → (𝑥 2 > 9)where universal set is R.
14 Test validity of the following statement: 5M
If there is strike by students , the examination will be postponed
The exam was not postponed
There was no strike by students
15 Test for the validity of the following arguments 5M
If a person is poor, he is unhappy
If a person is unhappy, he dies young
poor person die young
16 Test for the validity of the following arguments 5M
If interest rates fall, the stack market will rise
Interest rates are not falling
The stock market will not rise
17 Establish the following : 7M
18 Test for the validity of the following argument using the rules of inference: 7M
𝑝˅𝑞
¬p
¬q˅𝑟
𝑠 → ¬𝑟
¬𝑠
19 Test whether the following argument is valid or not 7M
𝑝→𝑞
𝑟→𝑠
𝑝˅𝑟
_______
𝑞˅𝑠
20 Test for the validity of the following argument using the rules of inference: 7M
𝑝 → (𝑞˄𝑟)
𝑟→𝑠
¬(𝑞˄𝑠)
________
¬𝑝
21 Explain the i) Direct Proof, ii) Indirect proof, iii) Proof by Contradiction, for the following 7M
statement: “If n is an odd integer, then n+9 is an even integer”
22 Let 𝑃(𝑥 ): 𝑥 ≥ 0, 𝑞 (𝑥): 𝑥 2 ≥ 0 𝑎𝑛𝑑 𝑟(𝑥): 𝑥 2 − 3𝑥 − 4 = 0, then for the universe completing of 7M
all real numbers, find the truth value of
i) ∃𝑥, {𝑝(𝑥 )˄𝑞(𝑥 )}
ii) ∀𝑥, {𝑝(𝑥 ) → 𝑞 (𝑥 )}
iii) ∃𝑥, {𝑞 (𝑥 )˄𝑟(𝑥 )}
23 Let 𝑝(𝑥 ): 𝑥 2 − 7𝑥 + 10 = 0, 𝑞(𝑥 ): 𝑥 2 − 2𝑥 − 3 = 0, 𝑟(𝑥 ): 𝑥 < 0 . Determine the truth or 7M
falsity of the statement for which the universe contains only the integers 2 and 5. If a statement
is false, provide a counter example or explanation
24 For each of the following statements, provide an indirect proof of the given statements: 7M
i) For all integers k and l, if kl is odd, then both k and l are odd.
ii) For all integers k and l, if k+l even, then k and l are both even or both odd.
25 Provide a proof by contradiction of the following statements: 7M
i) For every integer n, if 𝑛2 is odd then n is odd.
ii) For all real numbers x and y, if 𝑥 + 𝑦 ≥ 100, 𝑡ℎ𝑒𝑛 𝑥 ≥ 50 𝑜𝑟 𝑦 ≥ 50
26 Write down the following proposition in symbolic form and find its negation 7M
“All integers are rational numbers and some rational numbers are not integers.”
27 Write down the negation of each of the following statements 7M
i) For all integers ‘n’, if n is not divisible by 2 then n is odd.
ii) If k, m, n are any integers where (k-m) and (m-n) are odd, then (k-n) is even.
iii) For all real numbers x, if | x-3 | <7, then -4 < x < 10.Type equation here.
iv) If x is a real number where 𝑥 2 > 16, 𝑡ℎ𝑒𝑛 𝑥 < −4 𝑜𝑟 𝑥 > 4.
28 Find whether the following variable is valid 7M
No engineering students of 1 st or 2nd sem studies logic
Anil is an engineering student who studies logic
Anil is not in second semester.
29 Prove that the following argument is not valid 7M
All squares have four sides
The Quadrilateral ABCD has four sides
ABCD is a square.
30 Find the Negation for the following quantified statements 7M
i) ∀𝑥, ∃𝑦, [{𝑝(𝑥, 𝑦) ˄ 𝑞(𝑥, 𝑦)} → 𝑟(𝑥, 𝑦)]
ii) ∀𝑥, ∀𝑦, [(𝑥 < 𝑦) → ∃𝑧, ( 𝑥 < 𝑧 < 𝑦 )]
iii) ∀𝑥, ∀𝑦, [ |𝑥| = |𝑦| → (𝑦 = ±𝑥 )]
iv) [∀𝑥, ∀𝑦, ((𝑥 < 0) ˄ ( 𝑦 > 0))] → [∃𝑧, ( 𝑥𝑧 > 𝑦 )]
