Automatas e Linguagens Formais

Teoria dos Conjuntos

1. 1. Conjuntos

Teoria dos conjuntos começa com uma fundamental relação binária entre um objeto o e um conjunto A. Se o é um membro (ou elemento) de A, nós escrevemos o∈ A. Uma vez que conjuntos são objetos, a relação de pertinência também pode relacionar conjuntos.
Uma relação binária derivada entre dois conjuntos é a relação subconjunto, também chamada 'está contido'. Se todos os elementos do conjunto A também são elementos do conjunto B, então A é um subconjunto de B, denotado por A ⊆ B. Por exemplo, {1,2} é um subconjunto de {1,2,3} , mas {1,4} não é. A partir desta definição, é óbvio que um conjunto é um subconjunto de si mesmo; nos casos em que se deseja evitar isso, o termo subconjunto próprio é definido para excluir esta possibilidade.
Assim como a aritmética caracteriza operações binárias sobre números, teoria dos conjuntos caracteriza operações binárias sobre conjuntos. O (A):

União dos conjuntos A e B, denotada por A ∪ B, é o conjunto de todos os objetos que são membros de A, ou B, ou ambos. A união de {1, 2, 3} e {2, 3, 4} é o conjunto {1, 2, 3, 4}.

Interseção dos conjuntos A e B, denotada por A ∩ B, é o conjunto de todos os objetos que são membros de ambos A e B. A interseção de {1, 2, 3} e {2, 3, 4} é o conjunto {2, 3}.

Diferença de conjuntos de U e A, denotada por U \ A é o conjunto de todos os membros de U que não são membros de A. A diferença de conjuntos {1,2,3} \ {2,3,4} é {1}, enquanto a diferença de conjuntos {2,3,4} \ {1,2,3} é {4}. Quando A é um subconjunto de U, a diferença de conjuntos U \ A é também chamada de complemento de A em U. Neste caso, se a escolha de U é clara a partir do contexto, a notação Ac é algumas vezes usada no lugar de U \ A, particularmente se U é um conjunto universo como no estudo de diagramas de Venn.

Diferença simétrica dos conjuntos A e B é o conjunto de todos os objetos que são membros de exatamente um de A e B (elementos que estão em um dos conjuntos, mas não em ambos).