Sheet 4 Question 2

Question

Given a FSM: A={2Vin,2Vout,I,2Vstate,R} where Vin={a}, Vout={o}, Vstate={p,q}, I=q<->q<->q, R=next(q)&(next(p)|(p->o))&!(q->a)

Question : How to represent R in DNF? Please explain step by step. If there is any reference material available, where it is explained clearly, please let me know. 

Answer 1

next(q) means that q will be true in the next state of the FSM. You could also write it as q' (with a mark after the q) if that is easier for you to read. q' / next(q) is also a propositional variable. Computing DNFs is described in the chapter on Propositional Logic under Normal Forms, p.63.

Answer 2

q->a is equivalten to !q|a

Then you can use de Morgan's laws to get q&!a

Then you can use distributive law to get the DNF, e.g. a & (b|c) = a&b | a&c

Answer 3

As @choehne and @sschwarz have mentioned in their comments, R is a normal propositional formula. The same steps we use to compute a DNF for a given propositional formula is what we also us here.

If I substitute next(q) with q' and next(p) with p' for easy reading, then we can compute DNF as follows:

next(q)&(next(p)|(p->o))&!(q->a) =

q' & (p' | (p->o)) & !(q->a) = q' & (p' | (!p | o)) & !(!q | a) = q' & (p' | !p | o) & q & !a =(q&!a&p'&q') | (!p&q&!a&q) | (q&!a&o&q')

How should you interpret the bracket: Let's take as an example the 1st bracket. That means that any state where q is true when the input is !a, it can output either !o or o (since it is not specified) and change its internal state to p&q. You will have a transition from any state where q is true with input !a and output * to state where  p and q are true at the same time.