UNIT- 03
PROPOSITIONAL LOGIC
Unit-03/Lecture-01
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 278-290}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Explain the following terms used with proposition (i) Logical connectives (ii) Biconditional |
June 2013 |
4
|
|
Q. 2 |
State and prove Demorgan’s laws |
Dec 2012 |
7 |
PROBLEMS ON TAUTOLOGY
Unit-03/Lecture-02
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 290-294}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Is the formula tautology P -> (p ^ (q-> p)) |
Dec 2008 |
5
|
|
Q. 2 |
Show that (p ^ q) -> (p v q) is a tautology |
Dec 2008 |
5 |
|
Q. 3 |
Prove that (p ó q) ^ (q ó r) => (p ó r) is a tautology |
Dec 2006 |
5 |
|
Q.4 |
Define tautology and contradiction show that P => (q => r) Ξ (p ^ q) =>r |
Dec 2012 |
7 |
|
Q.5 |
Show that the following is equivalent formula P v (p ^ q) ó p |
June 2005 |
7 |
|
Q. 6 |
Construct the truth table for the following (p -> (q -> r)) -> ((p->q)-> (p-> r)) |
Dec 2008 |
7 |
|
Q.7 |
Prove by truth table that the following formula is tautology (p ó (q ^ r)) => (~r => ~p) |
June 2009 Dec 2010 |
7 |
|
Q.8 |
Prove that the following is tautologies or contradiction or contingency (p v q) ^ {p v ~q} ^ {~p v q} ^ {~p v ~q} |
Dec 2011 |
7 |
|
Q.9 |
Is (P v Q) ^ (P -> R)^ (Q->R) => R , Tautology or contradiction |
June 2012 |
7 |
|
Q.10 |
Prove that the proposition (p v ~q)^(~p v ~q) v q is a tautology |
June 2014 |
2 |
|
Q.11 |
Prove that the propositions p v (~q ^ r) and (p v ~q) v ~r are equivalent. |
June 2014 |
2 |
CONVERSE, INVERSE AND CONTRAPOSITIVE PROPOSITION
Unit-03/Lecture-03
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 294-296}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Determine whether each of following is a tautology, contradiction or contingency (i)( P-> Q) ó (~Q -> ~P) (ii)Q v (P ^ ~Q) v (~P v ~Q) |
June 2011 |
5
|
|
Q. 2 |
Prove that the following statement is logically equivalent (p=> q) v r Ξ (p v r) => (q v r) |
June 2007 Dec 2013 |
7 |
|
Q. 3 |
Explain the following terms Converse, Inverse and Contrapositive |
June 2013 |
2 |
|
Q.4 |
Construct Converse, inverse and contrapositive of the direct statement if 4x – 2 = 10 then x = 3 |
June 2009 |
5 |
|
Q.5 |
Write short note on Quantifiers |
June 2011 |
2 |
NEGATION OF QUANTIFIERS, PROBLEMS ON QUANTIFIERS
Unit-03/Lecture-04
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 317-319}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Discuss Normal Forms |
June 2013 |
2
|
|
Q. 2 |
What is Predicate? |
June 2011 |
2 |
NORMAL FORMS
Unit-03/Lecture-05
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 326-328}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Express the following formula into disjunctive normal form ~ (p v q) ó (p ^ q) |
June 2013 |
2
|
|
Q. 2 |
Express the following formula into conjunctive normal form ~ (p v q) ó (p ^ q) |
June 2013 June 2009 |
2 |
|
Q. 3 |
Obtain the principal disjunctive normal form of (i) ~ P v Q (II) (P ^ Q) v (~P ^ R) v (Q ^ R) |
June 2011 |
7 |
|
Q. 4 |
Show that ~( p ^ q) => (~p v (~p v q)) ó (~p v q) |
June 2005 |
7 |
|
Q.5 |
Obtain the conjunctive Normal Form of (~p -> r)^(q<->p) |
June 2014 |
3 |
FINITE STATE AUTOMATA
Unit-03/Lecture-06
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 331-336}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Define finite state machines? Explain state table and state diagram of a finite state machine with the help of suitable example? |
June 2013 |
7
|
|
Q.2 |
Construct a finite state acceptor that will accept the set of natural numbers x which are divisible by 3 |
June 2014 |
7 |
FINITE AUTOMATA WITH OUTPUTS
Unit-03/Lecture-07
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 331-336}
MINIMIZATION OF FINITE AUTOMATA
Unit-03/Lecture-08
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 336-337}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
||||||||||||||||||||||||||||||||||||
|
Q.1 |
For the finite state machine below (i) List all 0- equivalent states (II) Find all equivalent states and obtain an equivalent finite state machine with the smallest no. of states
|
Dec 2011 |
7
|
||||||||||||||||||||||||||||||||||||
|
Q 2 |
Minimize the finite state machine given by
|
June 2011 |
7 |
||||||||||||||||||||||||||||||||||||
PROBLEMS ON MINIMIZATION
UNIT- 03/ LECTURE -09
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 336-337}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
||||||||||||||||||||||||||||||||||||
|
Q.1 |
Show that the two finite state machines shown in following tables are equivalent
|
Dec 2012 |
7
|
||||||||||||||||||||||||||||||||||||
|
Q 2 |
(I) List all 0- equivalent states (ii) Find all equivalent states and obtain an equivalent finite state machine with the smallest number of states
|
June 2009 |
7 |
||||||||||||||||||||||||||||||||||||
FINITE STATE MACHINES AS LANGUAGE RECOGNIZERS
Unit-03/Lecture-10
REFERENCES {DISCRETE STRUCTURES BY D.C. AGARWAL, 337-344}
|
S.NO |
RGPV QUESTIONS |
Year |
Marks |
|
Q.1 |
Show that the language L= { am : m= i2, i>=1} is not a finite state language |
June 2009, June 2014 |
10,7
|
|
Q 2 |
Show that the language L= {ak bk : k>=1 } is not a finite state language |
Nov 2007 |
7 |
|
Q. 3 |
Construct deterministic finite state machine that recognizes the set (i) { 0i 1j | i>=1, j>=0} (ii) Set of all binary strings ends with 00. |
Dec 2008 |
10 |