Dado un circuito C, la clase de equivalencia de C es el conjunto de todos los circuitos con dos señales de entrada y una señal de salida que tienen...

Dado un circuito C, la clase de equivalencia de C es el conjunto de todos los circuitos con dos señales de entrada y una señal de salida que tienen la misma tabla de entrada/salida como C. Ahora cada tabla de entrada/salida tiene exactamente cuatro renglones, correspondiendo a cuatro posibles combinaciones de entradas: 11, 10, 01 y 00. Una tabla de entrada/salida típica es la siguiente:
Entrada Salida
P Q R
1 1 0
1 0 0
0 1 0
0 0 1
Hay exactamente tantas tablas como cadenas binarias de longitud 4. La razón es que las distintas tablas de entrada/salida se pueden formar cambiando el patrón de los cuatro 0 y 1 en la columna de salida y hay tantas maneras de formarlas como cadenas de cuatro 0 y 1 hay. Pero el número de cadenas binarias de longitud 4 es 24 16. Por tanto hay 16 tablas distintas de entrada/salida. Esto implica que hay exactamente 16 clases de equivalencia de circuitos, una para cada tabla distinta de entrada/salida. Sin embargo, hay un infinito de circuitos que dan lugar a cada tabla. Por ejemplo a continuación se muestran dos circuitos para la tabla anterior de entrada/salida.
AND
NOT
NOTP
Q
R OR NOT
P
Q
R
Congruencia módulo n
En el ejemplo 8.2.4 se muestra que la relación de congruencia módulo 3 es reflexiva, simétrica y transitiva. Por tanto, está es una relación de equivalencia.
Ejemplo 8.3.10 Clases de equivalencia de congruencia módulo 3
Sea R la relación de congruencia módulo 3 sobre el conjunto Z de todos los enteros. Es decir, para todos los enteros m y n,
m R n 3 (m ฀ n) m n (mod 3).
Describe las distintas clases de equivalencia de R.