Name the variables a preimage step quantifies.
A set of states is a function of the current-state variables s, and the transition relation T(s, i, s') is 1 when input i takes state s to s'. The image of a set R is rename(exists s, i. R(s) & T(s, i, s'), s' -> s). The conjunction keeps the transitions out of R, the quantification forgets where they came from and with which input, and the renaming reads the result as current states.
s
T(s, i, s')
i
s'
R
rename(exists s, i. R(s) & T(s, i, s'), s' -> s)
A 2-bit counter with no input has state bits s1 and s0, and next-state bits n1 and n0. Its relation is T = (n1 ~^ (s1 ^ s0)) & (n0 ~^ ~s0): the next count is the current one plus 1.
s1
s0
n1
n0
T = (n1 ~^ (s1 ^ s0)) & (n0 ~^ ~s0)
Take R = ~s1 & ~s0, the state 00. R & T forces s1 = s0 = 0, and then n1 = 0 and n0 = 1.
R = ~s1 & ~s0
R & T
s1 = s0 = 0
n1 = 0
n0 = 1
Quantifying s1 and s0 gives ~n1 & n0; renamed to the current-state variables, that is the state 01.
~n1 & n0
The image of 00 is 01, the state one clock cycle later.
The preimage of a set B is the set of states from which one clock cycle, for some input, reaches a state in B. It is computed from B(s'), the set written over the next-state variables, and T.
B(s')
T
Which variables does it quantify?
The next-state variables s' and the inputs i.
The current-state variables s and the inputs i.
The next-state variables s' only.
The inputs i only.
Choose one of the four options.
One answer.
Ask which variables the result may still mention: a preimage is a set of current states.
Compute the preimage of the state 01 in the example's counter by hand, and note which variables you had to remove.
Kata 7.3 of Binary Decision Diagrams with CUDD on formal.org. The site checks the answer when you press Check answer; sign in to keep your progress.