Question

Seja o conjunto A = {0; 1}. Quantas relações binárias distintas podem ser definidas sobre o conjunto A?

Answer 1

Para ver o número de relações binárias sobre A, devemos ver quantos elementos tem AxA.

Se A tem dois elementos, AxA terá 2² = 4 elementos - (0,0), (0,1), (1,0), e (1,1).
Uma relação binária em A é um subconjunto de AxA. Para saber o número de relações distintas em A, devemos saber quantos subconjuntos distintos existem em AxA.

O número de subconjuntos de AxA, sendo que este possui 4 elementos, será 2^4 = 16. Portanto, há 16 relações binárias distintas sobre A.