PROPOSITIONAL 2

PREVIOUs YEARS QUESTIONS

Ans. (pag)> (pvq)
First, we construct the truth table
PART-A
9pA pvq PAGpvg
T T T
T| F F T

Q.i Define finite state machines. IR.TU. 2019|

F

Ans. Finite automation as a machine equipped with an input Since in the last column, all are true i.e. T therefore
tape. The machine works on a discrete time scale. At every PAgpvg is a tautology.
point of time the machine is in one of its states, then it reads
the next letter on the tape (the letter under the reading head), Q.4 Find PCNF ofa statement S whose PDNF is
or maybe nothing (in the first variation), and then, according (P AqA) v (p AqA ~) v(~PA ~4 r).
to the transition function (depending on the actual state and R.T.U. 2017
the letter being read, if any) it goes to a/the next state. It may
Ans. First we obtain PDNF of ~s, which is the sum
happen in some variation that there is no transitions defined
(disjunction) of those minterms which are not present in the
for the actual state and letter, then the machine gets stuck
given PDNF of s. Hence the PDNF of ~s is
and cannot continue its run.
(PA~qA~r)v (-Paqar) v (P^ ~q n -r)
v (-Pa9-T)
Q.2 In how many ways can a team of I1 ericketers be Thus, the PCNF of S =[PDNF of (-s)}, i.e.
chosen for 6 bowlers, 4 wicket keepers and 11
batsmen to give majority of batsmen so that at least
E ((PAqA~r) v (-Pa~qar)
v(PA~qA~r) v (-Paqa-r)
4 bowlers are there andI wicketkeeper?/R.T.U. 2019 = (P vq vr) a (p vqv~r) a(-P vqvr)
A(PV~9Vr)
Ans. I wicketkeeper can be selected in C(4, 1) ways
4 bowlers chosen = C(6, 4) Q.5 Explain thefollowing for propositions with exumple:
Remaining 6batsmen=C(11,6) ( Logical Equivalence
Total possibilities=C(4, 1) *C(6,4) *C(11,6)=27720 (i) Tautological Implication
The batsmen has to be majority. So the split cannot be (ii) Normal Forms IR. TU. 20151
WC,5 Bowlers, 5 Batsmen.Itcan only be 1WC,4 bowlers
and 6 batsmen.
Ans.(i) Logical Equivalence: Any two propositions for
wihich the truth table is same are said to be LOGICALLY
.3 Show that (pa q)>(pvg) is a tautology.
IR.TU.20171 EQUIVALENT.
Ex.p>&- pvq
 B . T e c h .

Discrete Mathematics
DMS.22 Anss Given "

p v q) today 35°C Draw the trans

p:
t is hot is Q.9
t e m p e r a t u r e

:The
machine M (1,
temperature =
()pvq or the
is 350C
S S, S, O
F hot today follows-
Either it is
v q) temperature is 3s
nor
the 35° C
(ii) (p today
) Tautological Implication: Compound statements Neither it is hot
which are always true regardless ofthe truth or falseof is 2co.
temperature not S
and the
component statements are called tautologies. Obviously, the not hot today So
truth table ofa tautology will contain only T entries in the last It is
( i v ) p v ~q is not 350 S
olumn. and the temperature
It is not hot today
Example : The statement (p->q)(q>p) is Also, find the
a tautologgy
PART-B3
P P P | (P>4)+(°9 P)
T Ans. FSM, M (1, S, O
F
I= {a, b}
T F T ^
Q.8 (a) Showthat-(pv (-p D) =(-P)Af-9(wi S {So. Sy3
F T truth table)
(iii) Normal Forms : A literal L is either on after P or Write contrapositive converse and invere O-{0, 1}
(b) the statement "The home team wins when A>I
itsegation (-P). A clause D is a disjunction literals.
formula C is in NORMAL FORM if it is a conjunction of it is raining". Also construct the truth table Z O
ciause. each statement. 1. A finite set
IR.T.U.
LP-P A finite set
DLILv D 2.
Ans.(a) (pv (-p a q)) = pA(°pA~q) 3. A finite st
C DDaC
[De Morgan's Lai
Example : (a) (q vpvr)a (pvr)^nq 4. An initial s
(a)(p v r) a ( p v r) a (Pv r ) pAPV~q) [De Morgan's La
5. A next sta
PAPV~q) [Double Negation Lai
Q.6 Over the universe of animals, let 6. An op state
P(x): x is a whale; Q(x) : x is a fish (pAp) v(pA-q)
R(x):* lives in water. Fv-pA-q)
[Distributive Transition of fu
Transiate the following into English
PAp So-initial state
Ix (-R ())
pAP
3x (Q () A- Ans.(b) The given proposition is in the form F-finite state
P (x)) such that, "q wheneva
Vr (P (x) A R (x)) > Q (x) IR.TU. 2014
q
VP
Ans. : There exists an
(Conclusion): The home team wins.
x(-R(x}) animal which does not
lives in water.
P (hypothesis): It is raining.
Converse : q>p is
x(Qx)A~ P(x)): There exists a fish that is not a "If the home team wins theu Tr
whale. raining"
-> Output string fe
3 x(P(x) A R(x)) Q(x): Every whale that lives in Inverse:-P>-qis"If it is not
the water, is a fish. team does not
win". raining then the n
Contra 110 In a test 705
Q.7 Consider the following not win
pqsitive: -q>-p is "If d
then it is not the home tesi 65% in Ma
p: i is hot today raining".
q The temperature is 35°C and Mathen
Hrie in simple sentence the meaning p -pq subjects. Fim
ofthefollowing: the test.
PV4 (i) -(pva) (ii) -(pag)
(iv)p ~4 IR.T.U. 2013
 Diecrete Mathematics Structure
Ans. 70% passed in 65%
OMS.23
science, passed in mathematics,
0.9 Draw the transition diagram of thefinite state 27% failed in both.
machine M (1. S, 0, S, 1 g), where I = fa, b}, 100-27 73%
S-S 0- f0. 1}
S transition table
and the is a n(S) = 70%, n(M) = 65%, n(S nM) = 73%
follows- n(SUM) = n(S) + n{M)-- n(S n M)

70 +65- 73 62%
b
62
S passed in both subjects then total no of students= 100
Se S 124 passed in both subjects then total no of students
S
S
So S 100
x124 200.
Also, find the output string for the input b b a a 62

IR.TU. 2019
Q.11 Obtain the Principal disjunctive normal forms off
Ans. FSM, M (1. S, O, So» f.g) IR.T.U. 2019
I= {a, b}
Ans.
S-1So S,}
0 {0, 1} P9 pagsappr=b ec avbve
AI T T TT F F
T
T T FT
A finite set I
TIF T
. of alphabet
2. A finite set S of internal state
F TF
3. A finite state Z of O/P symbol
FFT F T
4 An initial state So inS F
FFF TI
S. A next state function f from Sx I into S. PDNF of (pnq) v (-p ar) v (q ar)
6. An op state functions of from Sx I into Z. (pA g)a(rv-) v ((-p Ar) n(qv~q))v ((qar)
A(pv p))
Transitionoffunction fif: SxI»P(S) (pAqAr)v (Pa qa~r)v(-parA g)
So initiai state vPAr~q) v (q a rap)v (qara~p)
F- finite state (pAqar) v (p aqa )v(-para q)
v-parA *p)
o/o (Deletion of identical min terms)
1/1
VP
Q.12 (a) Define Tautology, contradiction andcontingency
Determine the contrapositive ofeach statement:
Transitional diagram (Result) I f John is a poet, then he is poo.
Output string for bbaa is 1101. ii) Only if Mary studies will she pass the test
(b) Determine the validity ofthe argument:
All men are fallible
Q10 In a test 70% of the candidate passed in Science, Al kings are Men
65% in Mathematics, 27% failed in both Science Therefore, all kings are fallible. IR.TU. 20177
and Mathematics and 124 passed in both the
subjects. Find the total number of candidates for Ans.(a) Tautology: A compound statement that is always
the test. true for all possible truth values of its propositional variables,
is called a tautology. Obviously, its truth table contains only
IR.TU. 2019 truth valueT in the lastcolumn.
is ontradiction :
called le:Refer to Q.5(ii). B.Tech. (TV Sem.) c.S
only falsea Acompound statement that is
value in the Sole
last
contradiction.Obviously its always Tas -pp
Contingency: A column. truth table
contradiction
both T is statement that is contains
and F called neither a
The values at contingency.
least once inSo its truthtautology nor a
its last table contains FFT
Let p: contrapositive
John is a of p q is -q column.
p.
Since all the values are true, it is a ta
9 :He poet Ans.(b) Refer to Q.1.
Hence the is poor.
not
If join is contrapositive
(i) The of given Q.14Translate each of these statements
poo, then he is the
not a statement is: inte
given statement is poet. expressions using predicates,
the test, then
she logical connectives. anti
Let
equivalent to "If mary passes
p : Mary studied". No one is perfect
passes the test
q she studied. te (i) Not everyone is perfect
Hence its (i) All your friends are perfect
contrapositive is:
(iv) One ofyour friend is perfect
If Mary does
not
Ans.(b) Let study, then she will not
pass the test. (v) Everyone is your friend and perfect
M(x): x is a Man vi) Not every body is yourfriend or some
K(x): x is a king perfect.
FX):xis fallible
Then the Ans. Let p(x): x is perfect
argument takes the form q(x) :x is your friend
And the universe of discourse be the set of
Vx[M(x) F(x)] Then,
v[k(x)> M(x)] ) Vx-P(x)
V[k(x)>F(«)]
A formal proof is as follows: i) va(a(«)>P(«)
S.No. Step Reason
1. ) 3x(p(x)na(x)
Vx[M(x)> Fx)] Premise 1
2. M(c)>F (c) Step 1 and universal (Vs(p(x)n9(*))
instantiation (vi (vx-9(x))v(ax-p(«))
3. Vx[k(x) > M(x)] Premise2
4. K(c)>M(c) Step 3 and universal Q.15 Explain why predicate logic is better approm
instantiation
5. Hypothetical syllogism using propositional logic for knowledge represe
K(c)>F(c) Give some example also.
step 2 and 4
5 universal
6. Vx[K(x)-> F(x)] Step and Ams. (i) Predicate logic also known as predicate
generalization
and quantification theory- is a collection of forma
Hence the argument is valid. used in mathematics, philosophy, linguistics, and
science. Predicate logic admits quantified variables
is a tautolog
Prove that (-png) >1-(4->P) logical objects and allows the use of sentences thx
Q.13 (a) truth table.
with constructing such variables, so that rather than just proposito
disjunctive normal form Socrates is a man one can have expressions in
Obtain the principle truth ates is
(b) constructing
(-pw)v (qn) by a man where X is a variable. This distinguishe
of(png)v IR.T:U. 2016
propositional logic, which does not allow quantiliet
table. (i) Though propositional logic is one of tno
>Hq+p)] languages that demonstrates all the important po
:(-paq)
follows:
very limited ontology, making only the commit
Ans.(a) To proveis as
Truth table
 iscrete Mathematics Structure} DMS.25)
worid consists of facts. This made it difficult to represent (TRUE (Pv-Q)) v Q
even something as simple as the wumpus world. Predicate (Pv-)vQ
of commitments. The PvQv Q
iogic makes a stronger set ontological
main one is that the world consists of objects, that is, thing5 TRUE
individual identities and properties that distinguish them Hence, it is a tautology
from other objects.

m) First-order logic can also express facts about all of Q.18Sate the difference between deterministic and non
the objects in the universe. This, together with the implication
deterministic finite automata. R.T.U. 2015, 2014
connective from propositional logic, enables one to represent
general laws or rules.
(iv) Firstorder logic is universal in the sense that it can Ans. Deterministic and Non-deterministic Finite Acceptors
express anything that can be programmed. S. Deterministic Finite Non-deterministic Finite
() It is by far the most studied and best understood No. Acceptors Acceptors
scheme yet devised. 1. For every symbol of ie | We do not need to specify
alphabet, there is only how does the NFA react
one state transition. according tosome symbol.
Q.16 Find the DNF offollowing: 2. Cannot use empty string Can use empty string
( P ((p 0 - P v ~P) transition. transition.
Can be understood as Can be understood as multiple
(i) (P (Q n R). IR.T.U. 2015 one machine. little machines computing at
the same time.
ns. (i) A :P®(P->Q) A - ( - P v - P)) 4. It will reject the string if| If all of the branches of NFA
it end at other than dies or rejects the string, we
A DNF is an OR of ANND
accepting state. |can say that NFA reject the
we know that a > b =- avb
string.
So,A=-Pv(P>Q)A -(-PV-P) 5. The transition function is The transition function is
we also know, a v a = a &-(-a) =a single valued. multi-valued.
6. Checking membership is Checking membership is
SoA =-PV(P-> Q)a P)
A = Pv((-PvQ) A P) easy. diffieult.
A = -Pv ((-Pa P) a (Qa P)) 7.Construction is difficult. |Construction iseasy.
8. Space required is more. Space required is
A =-PvTv(Q^ P) (To true) Comparatively less.
( aa-a is a tautology) Backtracking
910. Can isallowed. Notpossiblein everycase.
A =-(P (Qn p)) > DNF be constructed for Cannot be constructed for
Gi) B =- (P->(Qa R)) every input and output. every input and output.
11. There can be more than There can only be one final
BE(Pv(QaR)) one final state. state.
-(-PvQ) a (-Pv R)
Byde Morgan's Law -(aa b) =(-av-b) Q.19 Prove pV (q A r) = (p Vq) A (p Vr). IR.TU. 20141
B = (-(PvQ)v(-(-PvR))
B= (PA-Q)v (P A-R) Ans. pV (q Ar)= (p V g) A (p V r)

17 Without constructing the truth table, show that

P 9rpv(gnr)pvg pv (pvg)a{pvr)
TITITT T T
pA(PVQ))>2 is a tautology. IR.TU 2015 T T F F T T

TF T F TT
Ans. We have, TIFFF
-PA(P Q) > Q F T T T
P A (Pv Q)) v Q FTFF
{using, A-B = ~A v B} F F TF
v F
Pv-P v) Q FFFFF FF
. (Pv-PA Q)) v Q Since the column (5) and (8) are identical.
CPv-P) a (Pv-0)) v Q So we have pV (q A r) = (p V q) A (p V r)
 Q.20 Show
that B.Tech. {rv Sem.) C.s
(pvg ) s
Solue
a tautology.
is studied or Maths:
(PAg) propositional formula,-s
a(rAs)=>P for any Thus, if Physics is not sta
Computer is studied is valid ccause if
ty . R . T U . 2013, 07
Ans. Given prepositions p-q Computer is studiSicg
then by fourth statement
studied then either Physics orAccount. and
not
(paq) a(ras) >P
P | PqFa)PAqA is stue
leads to study of Compûter.
(As) (pAg)
(ras) rAs)P Q.22 (a) Show that

P 4 =(P) vg
T (b) Show that (p A9^~(p v9 a
q) isis ao
F con

F F Ans. (a) P 9 P P9(P)vq

F T T|T| F T T
F F F F
FTF
T
TF T
T F F F
T
T T
F Thus, from truth table we have pee
T P =(P) V9.
F
Ans.
F (D)P g PA Pvg-(pvq) (pAg-(pV
TTT F F
FF T F T T F
F T F P
F F T F
F TF
FFF FFF
(pag)a(Tas)>p is always true Since in last column all the false result
Hence provedthatthe given propositional formula is (pA)n-(Pvq) is a contradiction.
atntology. Q.23(a) Obtain principal conjunctive normal
Swhere
Q.21 Using propositional Logie, prove the validity ofthe S = (p> t) a (q>p)
(b) Check the validity of following argun
argument [(Pv-q)]>ra(r®)ap=s Pvq
IR.TU. 2012
P
P
Aus Suppose
p:I will study Physics IR.TU
g:I will study Maths. Ans.(a) For obtaining the PCNF of S, we preparn
r:I willstudy Accounts table
s:lwill study Computer I will not study
will study Physics or T
(p vq):I
Maths.
I notwill study T
vq)>r:lflwill study Physics or
(p Accounts.
Maths, then I will study
T F
r s : Ifl willstudy
Accounts, then I willstudy
Computer then I study TT
will study Physics, will
p8:IfI F
LTF
Computer.
we can see that Computer
last two arguments is studied. From
Accounts
From the F
Physics o r that
studied ifeither we can see
will be argument

second
and third
the
DisCrete Mathematics Structure
IV, V, VI and VIll row.
DMS.27)
Here F appears in last oolumn in ll,
Therequired principal conjunctive normal form (PCNF)is Q.26 Prove the following equlvalences
vqv-)al-pvq )apv-qv-)a(pv-qvr)apvqvn (0 (pq)A(p>r)=p-(qAr)
ns(b) Constructing truth table to verify the given argument () (p >r)a(q->r)«(pvq)->r IR.T.U. 2010
valid ornotas:
is
Rew Ans.() (p->q)a (p->r)=p->(qAr)
Pv
P P1p>rpar(p-q)A(p->)p-qa)
TTIT
|T T|F
T T F
T F F
T
F T T
F F
T F T
F
Since in 5" row all the three prenmises namely pvq. From the 7 and 8 columns we see that
9 and prare true (T) but the corresponding truth (Pq)n(p->r)=p->(qar) Hence proved
ueofthe conclusion is false (F) so invalid. (i) (p->r)a(q->r)=(pvq)->r
24 efine the Contradiction. IR.TU. 201I P p- 9r|(pvr)p>ra(q>)(pvq)
T|T T
T TIF T
ns. Contradiction: If a compound statement is false for T
Ivalue assignments for its component statements, then it is F F F
T | T|
alled a contradiction, i.e. a compound statement is said to
ontradicting its truth value if it is false (F) for all ts entries
F
the truth table. If a statement is a contradiction then its EEE
gation will be a tautology. From the last two columns we see that
Example: The statement pa - p is a contradiction. Hence proved
(Pr)a(q)=(pvg)>r
etruth table for the given statement is as follows

AP PART-C
F
FT F

25Prove that the following implications are tautologies: Definefallucy and prove thefollowing
(i) pAgpvq (p Ag) v-p n ) is afallacy IR.T.U. 2019J
(i)-p-(p-q) R.T.U. 20117
Ans.Fallacy: A compound preposition, that is always false
s0) paq->pvq: Refer 1o Q.3. for any assignment of false value to the prepositional variable
() p > P 9 ) is called fallacy.

T T PA (paq)_(pag)v»(paq)|
F T
T T T
F T T
ce n the last column all entries are true.

P(p-q) is atautology (PA)vpaq) fallacy.

 B.Tech. (TV Sem.) C
Q.28 Define
The inputtape is
C.8, Solte
(vi) Input Tape: divide
a
(p>q)tautology and prove
ap} -> q is the each square containing single
alphabet . The end square of
Ans. tautology following-IR.T.U. 20191 of the
symbol ftointg
A
Tautology:
true for
the tape cog
any compound markers at the left end and
and at the
assigned
variable is called of the truth preposition is Absence of end-markers indicatese
values to thethat always hat the
Tautology prepositiona infinite length. The left-to-right
seque
between the end markers is is the
the
9(p>g)Ap (p>)Ap> processed.
input str-
head examines
(vii) Reading Head: The
at a time and can move one square either toonly
t
F he ler
we
right.For further analysis, strict the mov
(p>q)ap}q Tautology R-head only to the right side.
(vii) Finite Control: The input to the finite coe
contr
usually: symbol under the R-head, say a, or the n
Q.29 Describe the block
diagram of a finite automaton. of the
Consider the transition the machine, say q, to give the following o
of
motionma
of R-head the tape
along the
along next squ
system given below: tape to the
the next
square
a null move i.e. R-head remaining to the sama
permitted); (6) The next state of a finite state mach
by &(q, a).
101 10 Initial states are qo and qi
Final state is q3.
For checking the string acceptability, wesar
from initial ctate. If we reach the final state afterco
Fig.
Determine the initial states, the final state and thethe string, then we say that this string is acceptedby
system or not.
acceptability of 101011 and 111010.
IR.TU. 2016 Forstring 101011, the path value is go
i sthe final stateso this string is accepted by above
Ans. Finite Automaton :
A finite automaton can be System.
For string 111010, there is no path value. Sotm
represented by a 5-tuple (Q, E, 8, Qo» F), where
is a finite non-empty set of states. is not accepted by the above transition system.
() Q
called input
2 is a finite non-empty set of inputs
(ii) Q.30(a) Determine whether the conclusionC
alphabets.
into is usually
Qand logically from the premises H, H2a
(ii) 8 is a function which maps Qx2 function
function. This is the H: P vQ2
called direct transition
during the H: P-> R
which describes the changes states of
is usually represented by a
transition. This mapping H-Qv S
or a
transition diagram.
transition table C:SvR
initial state.

(iv) 9o e Q is the states. It is

assumed here that (b) Explain the followings:
is the set of final
Q state. () Argument
(v) F E o n e final
than
more
there may be i) Predicates
String being processed (iüi) Quantijiers
Input

Reading Aus. (a) We know that,

head
ABAvB
Finite Now we have,
automaton

control o f finite
diagram
Block
:
Fig.
Discrete Mathemaics Structure
v DMS.20)
from H1
(i)-(3xP())=Vr-P(x)
(ii)
{De Morgan's law]
Q S 3xP(x)->Qr)=VxP(x) -> 3xQ)
From H3 (iv) 3xP(x)>VxQ(x)= Vr(P(x)->Qx))
=Pv S = S->P
Hence, (v) 3r(P(x)vQx)= 3xP(x)v 3xQ(x)
S R (vi) -(3x-P() =VxP(x).
from H2}
S R Rv S Q.31 Discuss Mealy & Moore machines.
Hence, yes, the conclusion C follows logically from IR.TU. 20135
the premises H1,H2 and H3.
Ans. Finite automata may have
AIs.b) (i) An arangument is a statement which gives some outputs corresponding to each
facts and then claims something. The facts are called a transition. There are two types of finite state machine that
oremise& the claim is CONCLUSION. A sound argument generate output
is an argument which is valid and which has true premises.A (i) Mealy Machine
valid argument is an argument in which if the (ii) Moore Machine
premises are Mealy Machine:
irue then conclusion must be true.
) Predicates : A function P which can take two Mealy Machine is an FSM whose output depends on
alues, TRUE & FALSE present state as well as present input
It can be described by a six
P:X {True, False} (X is any set) where
tuple (Q, E, 0, 5, X, g)
(i) Quantifiers
Q is finite set of states
The way in which sentence can be turned into a
proposition is quantification. A quantifier is an operator that is finite set of
symbols called input alphabets
O is finite set of
imits the variables of a proposition. The two quantifiers, are symbols called output alphabets
heuniversal and existential quantifiers are as follows öis input transition function where 8:QXE>Q
X is output
(1)The Universal Quantifier : Suppose that P(x) is transition function where X:Q-0
propositional function with domain D. The universal go is initial state from where any input is
processed
ruantification ofP{x) is the proposition that asserts that P(x) (go, EQ). State diagram of Mealy machine is shown
true for all values below:
of x in the universe of discourse D ie.
x) is true for all values of x in D' written 'VxP(x)' and
ad 'for all x PCxY or 'for every x P(x). The symbol is Ox.1
ad as 'for alr or for every.
(2)The Existential Quantifier: With existential
uantification, we form a proposition that is true if and only
P(x) is true for at least one value in the universe of
iscourse.
The existential
quantification of P(x) is the proposition.
here exists an element x in
domain D such that P(x) is true' Fig
enoted by "3x P(x)' read as There exists x such that P(x) Moore Machine:
Tor some x P(xy or "There is at least one x such that Moore Machine is an FSM whose outputs depend on
only present state. It can be described by a 6 tuple (Q, 2,0,0,
)' The symbol 3 is read as 'there exists X, 8) where:
operties of Quantifiers
Qis a finite set of states
he negation of a quantified statement changes the i s a finite set of symbols called input alphabets
ntfier and also negates the given statement as mentioned
dow: Ois a finite set of symbols called output alphabets
dis input transition function
0-vP(} =x-P(x) {De Morgan's law] where8:Q X2Q
Xis the output transition function where X:QX2-+0
 B.Tech
convert the
have to he tram
we
all
DMS.30 First of follows
Ans.
transition
go is initial state from where any input is process tableas
into Next state
& EQ). State diagram is as shown below: Present state

Input 0 Output Iapt

2
Z
next state coBumn
the
look in
1:We
Step
and 9s associated
with no output, q, andn
q, is IL.e. Z, and Z.
diferent outputs
with two
Fig We don't split q, now wesplit q, anda
Step 2: After splitting
Mealy Machine v/s Moore Machine respectively. splitting the
and 431. 932 as follows:
table w e get is
S. Mealy Machine Moore Machine transition
Next state
No. Present state

Output depends only upon Input 0 Output Inpat

(i) Output depends
both upon present present state.
21 Z
state and present
input 921
(ii) Generally, it has Generally, it has more states 922
fewer states than than Mealy machine g21
Moore machine. 21 Z
432 transition tabei.
can cause we rearrange the
(iii) Output changes at Input change Now
Step 3: state in present state
change in output change as each
clock edges. way that
soon as logic is done. associated with a single output.
more
In moore machines, Next state
(iv)Mealymachines decode Present state
react faster to logic is needed to more Input 0 Input
inputs. the output since it has
circuit delays. 931

transition
a Mealy machine given by 922
Q.32Consider
moore machine equivalent to
Constructa g31 g32
diagram
this mealy machine 32
The transition diagram for Moore Machie

/1L

)us
Fig 45121
RTU 2013, 2009
This is the required solution.
 Dieerete Mathematics Structure
1
A DMS.31)
predicate P(x) is true or false depending on whether
Q.33 Hrite a mote on: property P holds for x.
(a) First Order Logic Example: ishappy (George) is true if George is happy
bFinite state machine as language recognizer but false otherwise.
Semantics of First-Order Logie
Ans. (a) First Order Logic In propositional logic, the truth value of formula
depends
on a truth
For some
applications, propositional logic is not
assignment to variables.
In FOL, truth value ofa formula
expressive enough but First-order logic is more depends interpretation
expressive: allows representing more complex facts of predicate symbols and variable over some
S domain
and making more sophisticated inferences. D.

For instance, consider the statement Consider a FOL formula-P(x)

"Anyone who
drives fast gets a speeding ticket" A possible interpretation:
From this, we should be able to conclude D-(o), P() = true, P(o) - false, x=
fast, he will get a speeding ticket"
"lf Joe drives
Under this interpretation, what's value
Similarly, we should be able to conclude "If Rachel What about ofx = o?.
of-P(x)?
drives fast, she will get a speeding ticket" and so on.
Ans.(b) Finite state machine as :
But Propositional Logic does inferences like
language Irecognizer
that because we cannot talk about
not allow Let A (Q, T, ao, 8, F). It is a
finite automation
concepts like (recognizer), where Q is the finite set of (inner) states, T is
"everyone", "someone" etc.
the input (or tape) alphabet, a e Q is the initial
First-order logic (predicate logic) allows making such state, FEQ
transition
in the set of final (or accepting) states and ô is the
kinds of Inferences.
function as follows.
Building Blocks of First-order Logic
8:Q (TU{A})+2° (for nondeterministic finite
The building blocks of were automata with allowed A-transitions):
propositional logic
propositions. 8:QxT2° (for nondeterministic finite automata
In first order logic, there are three kinds of basic without -transitions):
building blocks, constants, variables, predicates. 8:QxT>Q (for deterministic finite automata,A can
Constants:refer to specific objects (in a universe of be partially defined):
discourse) 8:Qx T-Q (for completely defined deterministic
Examples: George, 6, Austin CS311,. finite automata (it is not allowed that 8 is
partial
Variables :
function, it must be completely defined.))
range over objects (in a universe of
discourse) One can observe, that the second variation is a
special
case of the first one (not having A-transitions. The third
Example:x,y,z,... variation is a special case of the second one having sets with
In universe of discourse is cities in Texas, x can at most one element as images of the transition function, while
represent Houston, Austin, Dallas, San Antonio.. the fourth case is more specific allowing sets exactly with
Predicates: describe properties of objects or one element.
relationships between objects. Finite State Machines : Refer to Q..
Example: ishappy, better than, loves,>.. There are two widely used ways to
present automata,
Predicates can be applied to both constants and by Cayley tables or by graph. When an automaton is given
variables. by a Cayley table, then the 0 line and the 0 column of the
table are reserved for the states and for the alphabet,
Example: ishappy. (George), better than (x,y) loves
(George, Rachel), x>3, ... respectively (and it is marked in the 0th element the 0th
of
 B.Tech. V Sem.) C.s Soluei
zes are are draw
drawn as nor
edges
multiple
(DMS.32)- cases
these
in most labels.)
row). In some cases it is more convenient to put the states in than I
more

having the alphabet isal also gi-

the 0 row,while in some cases it is a better choice to put tn implicitly,
In this way, are
used
sed in the aut
letters
those
aiphabet there. We will look at both possibilities. The initial
state should be the first among the states (it is advisable to graph (only the edges).
labels on
mark it by a > sign also. The final states should also be appearas
appear even
more clarificatim
marked, they should be circled. The transition function is In order to
provide ation,
s a m e nondetermin
the nisi
written into the table: the elements of the set q,a) are written We describe
an example.
(if any) in the field of the column and row marked by the by a graph.
a table and
state q and by the letter a. In the case when A-transitions are
C92
also allowed, then the th row of the column
(that contains TQ g2. 93
the symbols a
of the alphabet) should be extended by the empty 90 90
word ()also. Then A-transitions can also be in the
indicated
table. Co 92
Automata can also be defined in a graphical way: let
the vertices (nodes. that are drawn as circles in this case) of
a graph represent the states of the automaton (we may write
the names
of the states into the
bc
circles). The initial state is
marked by an arrow going to it not from a node. The
states are marked
accepting
by double circles. The labeled arcs (edges)
ofthe graph represent the transitions of the automaton. If
peoq, a) for some p,q e Q, a e TU {A}, then there is an
edge from the circle representing state q to the circle
representing state p and this edge is labeled by a. (Note that bC
our
graph concept is wider here than the usual
concept, since it allow multiple edges connecting twodigraph
states, Fig