· 置换性划分的定义：
　　设πk是状态集的一个划分，Si是πk的一个类，
　　　　　　πk = { S1, S2, …Si, …Sm }　　　　　……（4-18）
　　　　　　Si = { si1, si2 , …sip …sin} 　　　 ……（4-19）
　　Iip是输入I取值的任意一个组合，我们定义：
　　　　　　St= N（ Si , Ip）= { sv| sv= N（sip , Ip）, sip∈Si}
　　是Si中所有状态在Ip作用下后继状态的集合，若St能被πk中某一个类所包含，则称πk是一个置换性划分。
　　由上述定义可知，置换性划分具有封闭性。
　　举例：对于表4.15所描述的时序机，其状态集为：
　　　　　　　　　　　S = { a, b, c, d, e }
　　它的某个划分 　 　πr = { S1, S2, S3}
　　其中　　　　　　　S1 = { a, b }
　　　　　　　　　　　S2 = { c }
　　　　　　　　　　　S3= { d, e }
　　我们对πr中的每一个类进行检查，观察在每一输入情况下的次态（见表4.16）,它符合置换性划分的定义。
表4.16 　πr在各种输入组合情况下的后继状态
当前状态
State
输入信号
In
后继状态
Next
S1
0
S1
S1
1
S2
S2
0
S1
S2
1
S3
S3
0
S1
S3
1
S3
　　πt 是此状态集S的另一个划分
　　　　　　　　　　　πt = {S1, S2, S3}
　　其中　　　　　　　　S1 = { a, b, c }
　　　　　　　　　　　　S2 = { d }
　　　　　　　　　　　　S3 = { e }
　　对πt进行检查，发现它不是一个置换性划分。例如，若当前状态为S1 ，在输入信号In取值为1的情况下，其次态将落入πt的两个类（ S1和 S2）之中，而不是落入πt的某一个类之中。
　　· 输出一致的划分
　　设Ip 是输入I取值的任意一个组合，πk是状态集合S的一个划分，Si是πk中的任意一个类 (Si∈πk)，sip, siq 是S i中的任意两个状态 (sip , siq∈S i) ，若满足下列关系：
　　　　　　Z(sip , Ip)= Z(siq , Ip)
　　则说πk是一个输出一致的划分。

　　· 输出一致的置换性划分
　　设πk是状态集合S的一个划分，若πk既满足输出一致的要求，又满足置换性划分的要求，则称πk为输出一致的置换性划分。
　　输出一致的置换性划分中的元素Si是等价类，Si中各个状态彼此等价，可以合并为一个状态。因此，时序机状态最小化就是在输出一致的置换性划分中寻求一个最小化划分（其中等价类个数最少）。