Solution Question Bank 1 PDF

Preview

Summary

Question Bank-Unit 1(Propositional Logic)S. No. Questions COBloom ’s Taxono my LevelDiffi culty Leve lCompetiti ve Exam Question Y/NArea Topic U n itM a r k s1 Which of these sentences are propositions? What are the truth values of those that are propositions? a) 2 + 3 = 5 ( True implies proposition...

Description

Question Bank-Unit 1 (Propositional Logic) S. Que s t i o ns No .

CO

Compe t i t i ffi Bl oo m Di eEx a m c ul t y v ’ s e s t i o n v e Qu Ta x on o Le l Y/ my N Le v e l

1

Wh i c ho ft h e s es e nt e nc e sa r epr o po s i t i o ns ?Wh a ta r et h et r ut hv a l ue soft ho s et ha t a r epr o po s i t i on s ? a)2+3=5( Tr uei mpl i e spr opos i t i o n) . b)Ans we rt hi s q u e s t i on .( no tde c l a r a t i v ei mpl i e sno tapr o pos i t i o n)

1

K1

L

N

2

Che c kwhe t he rt h e s es t a t e me nt sa r ewff( we l lf o r me df o r mul a )orno t : ( a )( pq ˅ )∧

∼r 1

K2

L

N

Ar e a

To pi c

U M n a i t r k s 1 2

2 1

( b)pq ˅ ∧r Ans .we l lf o r me df or mul a

- ⋀ q ,−⋀ pq Ex a mp l e :p q ⋀ ,p 3

n o twe l lf or me d

Che c kwhe t he rt h e s es t a t e me nt sa r ewfforno t :( a )( p∧( q ∧r ) ) →s( b )( ( pq ˅ ) ∧r →q)

1

K2

L

N

1 2

1

K2

L

N

1 2

1

K2

L

N

1 2

1

K2

L

N

1 2

Ans .we l lf or me df or mul a 4

Determine whether these biconditionals are true or false. a) 2 + 2 = 4 if and only if 1 + 1 = 2. b) 1 + 1 = 2 if and only if 2 + 3 = 4. Sol. a. T and T= T

5

Determine whether these biconditionals are true or false. a) 1 + 1 = 3 if and only if monkeys can fly. b) 0 >1 if and only if 2 >1. (16/14/KR) Sol. a. F and F=T

6

b. T and F= F

b. F and T=F

Determine whether each of these conditional statements is true or false. a) If 1 + 1 = 2, then 2 + 2 = 5. b) If 1 + 1 = 3, then 2 + 2 = 4.

(17/14/KR) Sol. a. T and F= F

b. F and T=T

7

Determine whether each of these conditional statements is true or false. a) If 1 + 1 = 3, then 2 + 2 = 5. b) If monkeys can fly, then 1 + 1 = 3. (17/14/KR) Sol. a. F and F=T b. F and F=T 8 State the converse, contrapositive, and inverse of the conditional statements. If it snows today, then I will ski tomorrow. (27/15/KR)

1

K2

L

N

1 2

1

K2

L

N

1 2

1

K2

M

N

1 6

1

K2

M

N

1 6

1

K2

L

N

1 2

Sol. If it snows today, then I will ski tomorrow.

9

Converse: If I will ski tomorrow, then it snows today Contra-positive: If I will not ski tomorrow, then It does not snow today Inverse: If it does not snow today, then I will not ski tomorrow State the converse, contrapositive, and inverse of each of these conditional statements. I come to class whenever (if) there is going to be a quiz. (27/15/KR) Sol. I come to class whenever (if) there is going to be a quiz. OR we can re-write above statement as If there is going to be a quiz, then I come to class. same as above

1 0. State the converse, contrapositive, and inverse of the conditional statements. A positive integer is a prime only if it has no divisors other than 1 and itself. (27/15/KR)

Sol. OR we can re-write above statement as If a positive integer is a prime, then it has no divisors other than 1 and itself. 1 1 Let P(x) denote the statement “x ≤ 4.” What are these truth values? a) P(4) b) P(6) (1/53/KR)

Sol. P(x): x ≤ 4 (given) Then, P(4): 4 ≤ 4-----(True) P(6): 6≤ 4-----(False)

1 2

1

K2

L

N

1 2

1

K2

L

N

1 2

Determine the truth value of each of these statements if the domain consists of all integers. a) ∀n(n + 1 > n) b) ∃n (2n = 3n) (13/53/KR)

1

K2

L

N

1 2

1 5 Determine the truth value of each of these statements if the domain consists of all integers. a) ∃n(n = −n) b) ∀n(3n ≤ 4n) (13/53/KR)

1

K2

L

N

1 2

1 6 Define Skolemization. 1 7 Define Skolem constant. 1 8 Define skolem function.

1 1 1

K1 K1 K1

L L L

N N N

1 2 1 2 1 2

Let P(x) be the statement “x = x2.” If the domain consists of the integers, what are these truth values? a) P(0) b) ∀xP(x) (11/53/KR) Sol. Then,

P ( x ) : x= x . 2

P ( 0 ) : 0=0 2

True

b. Since P(x) is only true for 0 and 1 this implies ∀xP(x) is false 1 3

Let P(x) be the statement “x = x2.” If the domain consists of the integers, what are these truth values? a) P(1) b) ∃xP(x) (11/53/KR)

P ( x ) : x= x2 . Then, P(1) is True 1=12 Sol.

b. ∃-existantential quantifier ∃xP(x) is true since it is true for 0 and 1.

1 4

(Not in syllabus) (Not in syllabus) (Not in syllabus)

1 9 Let p, q, r denote the statements “It is raining”, “It is cold”, and “It is pleasant”, respectively. Then the statement “It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold” is represented by (a) (￢p ∧r )∧(￢r → (p ∧q)) (b) (￢p ∧ r ) ∧ ((p ∧q) →￢r) (c) (￢p ∧r )∨((p ∧q) →￢r) (d) (￢p ∧ r ) ∨(r → (p ∧q))

1

K3

H

Y

1 6

1

K2

M

Y

1 2

1

K2

M

Y

1 2

(GATE 2017, 1 mark)

Sol. p: It is raining, q: It is cold, r: It is pleasant. Then the statement “It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold”

Logic:

− p ∧r) ∧ (-r ¿

p∧ q )) →¿

(option (a))

2 0 Which one of the following is not equivalent to p↔q? (a) (￢p ∨q )∧ (p ∨￢q) (c) (￢p ∧q )∨ (p ∧￢q)

(b) (￢p ∨ q ) ∧ (q→ p) (d) (￢p ∧￢ q ) ∨ (p ∧q)

(GATE 2015, 1 mark) Sol. Exercise Ans. c

2 1 Let p, q, and r be propositions and the expression (p→q) →r be a contradiction. Then the expression (r→p) →q is (a) a tautology (b) a contradiction (c) always TRUE when p is FALSE (d) always TRUE when q is TRUE (GATE 2017, 2 mark) Sol. In conditional proposition false implies 1st is T and 2nd is F. This implies (p→q (1st is not T and 2nd is not F)) always True and r always false. r is false this implies that r→ p is always true.

(r→p) always ture and if q is true=true (r→p) always ture and if q is False=false Ans. d

2 2. The statement (￢p) → (￢q) is logically equivalent to : I. p → q II. q → p (a) I only (b) I and IV only (c) II only

III. ( ￢q)∨ p (d) II and III only

1

Y

1 2

IV. ( ￢p)∨ q (GATE 2017, 1 mark)

Sol. Will continue in next class i.e., 17th July 2020 2 3. Consider the following two statements: S1: If a candidate is known to be corrupt, then he will not be elected. S2: If a candidate is kind, he will be elected. Which one of the following statements follows from S1 and S2 as per sound inference rules of logic? (a) If a person is known to be corrupt, he is kind. (b) If a person is not known to be corrupt, he is not kind. (c) If a person is kind, he is not known to be corrupt. (d) If a person is not kind, he is not known to be corrupt.

1

K3

H

Y

1 6

1

K2

H

Y

1 2

(GATE2015, 1)

2 4 Let p, q, r, s represent the following propositions:

p : x {8, 9,10,11,12}, q: x is a composite number, r: x is a perfect square, s: x is a prime number The integer x 2 which satisfies ￢((p→q ) ∧ (￢r ∨￢s) ) is…………………… (GATE2016, 1)

Sol. p : x {8, 9,10,11,12} q: x is a composite number={8,9,10,12} r: x is a perfect square={9} -r={8,10,11,12} s: x is a prime number={11} -s={8,9,10,12} (￢r ∨￢s)=union={8,9,10,11,12} p→q ={8,9,10,12} (p→q ) ∧ (￢r ∨￢s) =intersection or common member={8,9,10,12} -( (p→q ) ∧ (￢r ∨￢s) )=11 Ans

2 5

Which one of the following well formed formula in predicate calculus is NOT valid? (a) (∀x p(x) →∀x q(x)) →(∃x ￢p(x) ∨∀x q(x)) (b) (∃x p(x) ∨∃x q(x)) →∃x (p(x) ∨ q(x)) (c) ∃x (p(x) ∧ q(x)) →(∃x p(x) ∧∃x q(x)) (d) ∀x( p(x) ∨ q(x)) →(∀xp(x) ∨∀x q(x))

1

K2

M

Y

1 2

1

K2

M

Y

1 2

1

K2

M

Y

1 2

(GATE 2016, 2 mark)

2 6 What is the logical translation of the following statements? “ None of my friends are perfect” (a) ∃x(F(x)∧￢P(x)) (b) ∃x(￢F(x)∧ P(x)) (c) ∃x(￢F(x)∧￢P(x)) (d) ￢∃x(F(x)∧ P(x)) (GATE 2013, 2 mark)

2 7

Consider the statement:“ Not all that glitters is gold” Predicate glitters(x) is true if x glitters and predicate gold(x) is true if x is gold. Which one of the following logical formula represents the above statement?

(a) ∀x:glitters(x) →￢gold(x) (b) ∀x: gold (x) → glitters(x) (c) ∃x: gold(x) ∧￢glitters(x) (d) ∃x: glitters (x) ∧￢gold (x) (GATE 2014, 1 mark) 2 8 Construct a truth table for each of these compound propositions.

a) (p → q) ↔ (￢q →￢p) b) (p → q) → (q → p)

1

K1

L

N

1 6

1

K2

L

N

1 6

1

K2

L

N

1 6

1

K2

L

N

1 6

1

K2

M

1

K2

M

N

1 6

1

K2

M

N

1 6

(31/15/KR)

2 9 Construct a truth table for each of these compound propositions.

a) (p ∨ q) → (p ⊕q) b) (p ⊕q) → (p ⊕￢q) (33/15/KR) 3 0 Use De Morgan’s laws to find the negation of each of the following

statements. tomorrow.

a) Jasbir is rich and happy b) Rajan will bicycle or run

(7/34/KR) 3 1 Use De Morgan’s laws to find the negation of each of the following

statements. a) Shakila walks or takes the bus to class. smart and hard working.

b) Ibrahim is

(7/34/KR) 2 4 Show that each of these conditional statements is a tautology by using truth

1 6

tables. (And then without using the truth tables.) a) (p ∧ q) → p b) p → (p ∨ q) c) ￢p → (p → q) (9, 11/35/KR) 2 5 Show that each of these conditional statements is a tautology by using truth

tables. (And then without using the truth tables.) (a) (p ∧ q) → (p → q)( b)￢(p → q) → p (c) ￢(p → q)→￢q (9, 11/35/KR) 2 6

Show that (p → q) ∧(q → r) → (p → r) is a tautology.

(29/35/KR) 1

K2

L

N

1 2

1

K2

M

N

1 6

1

K2

M

N

1 6

3 0. Show that two compound propositions are logically implied:

1

K2

M

N

1 6

3 1 Show that two compound propositions are logically implied:

1

K2

M

N

3 2 Determine whether each of these compound propositions is satisfiable.

1

K2

M

N

2 7 Show that two compound propositions are logically equivalent:

a) ￢(p ↔ q) and p ↔￢q b). ￢p ↔ q and p ↔￢q c) ￢(p ↔ q) and ￢p ↔ q (17,19,21,23/35/KR) 2 8

Show that two compound propositions are logically equivalent: (p → r) ∧(q → r) and (p ∨q) → r (17,19,21,23/35/KR)

2 9 Show that (p → q) → r and p → (q → r) are not logically

equivalent.

(31/35/KR)

a) (p ∨￢q) ∧ (￢p ∨ q) ∧ (￢p ∨￢q) b) (p → q) ∧ (p →￢q) ∧ (￢p → q) ∧ (￢p →￢q) c) (p ↔ q) ∧ (￢p ↔ q) (61,62/36/KR)

1 6

3 3 Find the dual of each of these compound propositions.

a) p ∧￢q ∧￢r

b) (p ∧ q ∧ r) ∨ s

1

K3

M

N

1 6

1

K2

H

N

1 6

1

K3

H

N

1 6

c) (p ∨ F) ∧ (q ∨ T)

(35/35/KR) 3 4 Find the Disjunctive Normal Form (DNF) of

(p ∨ q)→¬r.

(31/35/KR)

Definition: Disjunctive normal form: If conjunctive propositions can written as disjunction propositions. (p ∧q ∧r) ∨ (-r∧-s) Example: (p ∧q) ∨

Q. Find the Disjunctive Normal Form (DNF) of (p ∨ q)→¬r. p q r -r p∨q (p ∨ q)→¬r T T T F T F T T F T T T T F T F T F T F F T T T F T T F T F F T F T T T F F T F F T F F F T F T

Then the (dnf) is (p∧q∧-r) ∨ (p∧-q∧-r) ∨ (-p∧q∧-r) ∨ (-p∧-q∧r) ∨ (-p∧-q∧ -r) Ans. 3 5 Find the Disjunctive Normal Form (DNF) of

S= (∼p →r)∧ (p↔ q).

(Ex 4.28/4.26/SS)

p

q

r

-p

(∼p →r

(p↔ q).

S

T T T T F F F F

T T F F T T F F

T F T F T F T F

F F F F T T T T

T T T T T F T F

T T F F F F T T

T T F F F F T F

(p∧q∧r) ∨ (p∧q∧-r) ∨ (-p ∧-q ∧r)

Then, the DNF is

3 6 Find the Disjunctive Normal Form (DNF) of

ans

S= p↔ (∼p ˅∼q). ).

1

K3

H

N

1 6

1

K3

H

N

1 6

(Ex 4.27/4.25/SS) Sol.

p

q

-p

-q

(∼p ˅∼q)

S

T

T

F

F

F

F

T

F

F

T

T

T

F

T

T

F

T

F

F

F

T

T

T

F

Ans. (p∧-q)

ans.

3 7 Put the following into Conjunctive Normal form

. (42/35/KR) Conjunctive normal form: If disjunctive propositions can written as conjunction propositions. ∧ (-r∨ -s) ∧ (p∨-r∨-s∨q∨t). Example: (p∨ q) ∧ (p∨ q∨ r)

Sol. Note: For CNF 1st find DNF and then replace p by –p, q by –q and vice versa and ∧ by ∨ and ∨ by ∧ by De Morgon’s law.

p

q

r

T T T T F F F F

T T F F T T F F

T F T F T F T F

p→ q −( p → q) T T F F T T T T

F F T T F F F F

r → p −( p → q ) ∨ r→p T T T T F T F T

T T T T F T F T

DNF is (p∧q∧r) ∨ (p∧q∧-r) ∨ (p∧-q∧r)∨ (p∧-q∧-r)∨ (-p∧q∧-r)∨ (p∧-q∧-r).

Then, CNF (or negation of DNF) is (-p∨ -q∨ -r) ∧ (-p∨ -q∨ r) ∧ (-p∨ q∨ -r) ∧ (-p∨ q∨ r) ∧ (p∨ -q∨ r) ∧ (p∨ q∨ r) ans. 3 8 Put the following into Conjunctive Normal form (p∧q)˅(∼p∧q∧r).

1

K3

H

N

1 6

1

K3

H

N

1 6

1

K2

H

N

1 6

1

K2

H

N

1 6

(Ex 4.26/4.25/SS)

3 9 Put the following into Conjunctive Normal form

(p˅∼q)→q.

(Ex 4.27/4.25/SS)

4 0 Translate each of these statements into logical expressions using predicates,

quantifiers, and logical connectives. a) No one is perfect. b) Not everyone is perfect. c) All your friends are perfect. d) At least one of your friends is perfect. e) Everyone is your friend and is perfect. f )Not everybody is your friend or someone is not perfect. (25/54/KR) 4 1 Find the argument form for the following argument and determine whether

it is valid. Can we conclude that the conclusion is true if the premises are

true? If Socrates is human, then Socrates is mortal. Socrates is human. ∴ Socrates is mortal. (1/78/KR) 4 2 Check the validity of the following arguments: Show that the premises “It is

1

K2

H

N

1 9

1

K2

H

N

1 6

not sunny this afternoon and it is colder than yesterday,” “We will go swimming only if it is sunny,” “If we do not go swimming, then we will take a canoe trip,” and “If we take a canoe trip, then we will be home by sunset” lead to the conclusion “We will be home by sunset.” Sol. p: It is sunny this afternoon, q= it is colder than yesterday, r= We will go swimming, s= we take a canoe trip, t= we will be home by sunset Premises: -p ∩q , r → p ,−r → s, s → t Conclusion: t

− p∩ q

Proof:

premises Simplification

-p

r→p

or

– p →− r

-r

−r → s s

s →t t

premises by modus ponens

premise by modus ponens premise

result

Thus, the conclusion is valid 4 3

Consider the argument: “If you invest in the stock market, then you will get rich” “if you get rich, then you will be happy” therefore” if you invest in the stock market, then you will be happy”

check whether the given argument is valid. Sol. premises : Conclusion: Proof: p→ r

p→ q ,q → r ,

¿ p

p→ q ,q → r

premises

Result

Conclusion is valid 4 4

Use rules of inference to show that the hypotheses “Randy works 1 hard(p),” “If Randy works hard, then he is a dull boy(q),” and “If Randy is a dull boy, then he will not get the job” imply the conclusion “Randy will not get the job.” (5/78/KR)

K2

M

N

1 6

K2

M

N

1 6

Sol.Premises: p , p → q , q →−r Conclusion: -r Proof: p premises p→ q premises q by modus ponens q →−r premise -r result Thus, the conclusion is valid

4 5

For each of these arguments, explain which rules of inference are used for each step:“Danish, a student in this class, knows how to write programs in JAVA. Everyone who knows how to write programs in JAVA can get a highpaying job. Therefore, someone in this class can get a high-paying job.” Sol. C- represents class

1

x- represents “is a student in this class” W- know how to write of programs in JAVA J- get a high-paying job Then, the premises are: C(Danish), W(Danish), ∀x (W ( x ) → J ( x ) ) Conclusion: someone in this class can get a high-paying job. premises ∀x (W ( x ) → J ( x ) ) W ( Danish ) → J ( Danish) by universal

Proof: C(Danish), W(Danish), From 3rd premise instantiation

Now from 2nd premise and the above result J(Danish) by modus ponens Now from 1st premise and the above result C(Danish) ⋀ J (Danish) by conjunction

∃x ( C(x) ⋀ J ( x )

)

by existential generalization

Conclusion is valid. 4 6

Determine whether each of ...