Introdução às Linguagens Formais e Autômatos/Fundamentos Matemáticos
Elementos de Matemática Discreta 5 1.1 Conjuntos 1.2 Relações 1.3 Funções 1.4 Grafos 1.6 Teoremas e Demonstrações 1.7 Conjuntos Enumeráveis
1.1 Conjuntos
Um conjunto é uma coleção de símbolos, também denominados átomos ou elementos,
em que não são consideradas ocorrências múltiplas dos mesmos nem há relação de ordem
entre eles.
Exemplo 1.1 A inclusão do símbolo ♦ no conjunto {♣,♦,♥,♠} resulta no próprio conjunto{♣,♦,♥,♠}, pois o mesmo já faz parte do conjunto e, portanto, não deve ser considerado novamente. Por outro lado, o conjunto {♣,♦,♥,♠} é igual ao conjunto {♦,♣,♠,♥}, uma vez que não existe relação de ordem entre os elementos que os compõem. 2 Um símbolo corresponde a uma representação gráfica única e indivisível. Se formado por caracteres, um símbolo pode ser composto por um número arbitrário deles.
Exemplo 1.2 São exemplos de símbolos: “a”, “abc”, “♠”, “1” etc. 2 Alguns conjuntos podem ser especificados através da simples enumeração de todos
os seus elementos, denotados entre chaves e separados por vírgulas.
Exemplo 1.3 O conjunto formado pelos elementos 0, 1, 2, 3 é representado por {0, 1, 2, 3}. O conjunto {a, b, c, d, e, f } é formado pelas seis primeiras letras do alfabeto romano. O conjunto {01, 231, 33, 21323} contém os elementos 01, 231, 33 e 21323.
2 Conjuntos podem ser referenciados através de nomes, arbitrariamente escolhidos.
Exemplo 1.4 X = {0, 1, 2, 3}, Y = {a, b, c, d, e, f }. Assim, os nomes X e Y passam a denotar os conjuntos correspondentes. 2
O número de elementos contido em um conjunto A é denotado por |A|.
Exemplo 1.5 No exemplo 1.4, |X| = 4, |Y| = 6. 2
Os símbolos ∈ e 6∈ servem para denotar se um determinado elemento pertence ou não pertence a um conjunto, respectivamente.
Exemplo 1.6 No exemplo 1.4, 0 ∈ X, 5 6∈ X, 2 6∈ Y , b 6∈ X, c ∈ Y, h 6∈ Y.
2 Conjuntos podem conter um número finito ou infinito de elementos. No primeiro caso, o conjunto pode ser denotado enumerando-se (relacionando-se explicitamente) todos
os elementos que o compõem, como foi feito para os conjuntos X e Y do exemplo 1.4, que são conjuntos finitos.
1.2 Relações
Uma relação R sobre dois conjuntos A e B é definida como um subconjunto de A×B.
Relações representam abstrações de conceitos matemáticos fundamentais, como, por exemplo, as operações aritméticas, lógicas e relacionais, além de constituírem a base
teórica para o estudo sistemático das funções. O conjunto de todas as relações definíveis sobre A×B é dado por 2A×B.
Exemplo 1.20 A relação R1 = {(a, b) | a, b ∈ N e a > b}, sobre N × N, contém, entre infinitos outros, os elementos (2, 1), (7, 4) e (9, 3). A relação R2 = {(x, y, z ) | x, y, z ∈ Z e x2 = y2 + z 2}, sobre Z × Z × Z, contém os elementos (0, 0, 0), (1, 1, 1), (−1,−1,−1), (5, 4, 3), (−10, 8,−6) etc.
2 Uma relação R aplicada sobre um elemento a de um conjunto A e outro elemento b de um conjunto B pode ser denotada, em notação infixa, por aRb. Se (a, b) ∈ R, diz-se,
de forma abreviada, que aRb. Os conjuntos A e B recebem, respectivamente, os nomes domínio e co-domínio (ou contradomínio) da relação R. Por envolver dois conjuntos, essa relação é dita binária e seus elementos recebem a designação de pares ordenados. Relações binárias
sobre um mesmo conjunto A representam subconjuntos de A × A.
Exemplo 1.21 Considere-se a relação binária “6=” sobre o conjunto dos números inteiros. Essa relação se define como o conjunto dos pares ordenados tais que suas duas componentes são diferentes. Alguns dos elementos do conjunto definido por essa relação são (1, 3), (−5, 0), (8,−2) etc. Utilizando a notação introduzida, os elementos citados, pertencentes a essa relação, são denotados por 1 6= 3, −5 6= 0 e 8 6= −2, coincidindo, portanto, com a representação tradicional da relação.
Notar que (1, 1), (0, 0) e (−5,−5) são exemplos de pares ordenados que não satisfazem a essa relação binária, pois suas duas componentes coincidem. 2 O conceito de relação pode ser generalizado para mais de dois conjuntos, consistindo, sempre, em subconjuntos definidos sobre o produto cartesiano dos conjuntos participantes
da relação. A relação, nesse caso, é dita uma relação “n-ária”, e corresponde a um subconjunto do produto cartesiano dos conjuntos envolvidos. Sejam n conjuntos
A1,A2, ...An. Os elementos pertencentes ao conjunto definido por uma relação n-ária sobre A1,A2, ...An são, portanto, elementos de A1 × A2 × ... × An, e têm a seguinte
forma: (a1, a2, a3, ..., an)
onde a1 ∈ A1, a2 ∈ A2, ...an ∈ An.
1 Elementos de Matemática Discreta 11
Tais elementos são denominados ênuplas ordenadas. Em casos particulares, como para n = 2, 3, 4, 5 etc., as ênuplas recebem nomes especiais, geralmente os ordinais de n:
pares, triplas, quádruplas, quíntuplas etc. Quando n é grande, usa-se em geral o nome “n-tupla ordenada”. Por exemplo, (a1, a2, ...a10) é considerada uma décupla (ou uma
10-tupla) ordenada. Uma relação binária R sobre um conjunto A é dita:
• Reflexiva: se aRa, ∀ a ∈ A;
• Simétrica: se aRb implica bRa, ∀ a, b ∈ A;
• Transitiva: se aRb e bRc implicam aRc, ∀ a, b, c ∈ A;
sendo que a, b, c não precisam ser necessariamente distintos.
Exemplo 1.22 A relação binária “identidade” (=) definida sobre o conjunto dos números inteiros Z como o conjunto de todos os pares ordenados para os quais as duas componentes são idênticas. Ela é reflexiva, pois a = a, ∀ a ∈ Z; é simétrica, pois a = b implica b = a, ∀ a, b ∈ Z; e transitiva, uma vez que a = b e b = c implica a = c, ∀ a, b, c ∈ Z. Alguns elementos do conjunto definido por essa relação são (4, 4), (0, 0), (−7,−7) etc. Notar que pares ordenados, tais como (1,−3), (0, 5) e (7, 9), não pertencem a essa relação. 2 Por outro lado, a relação binária “maior” (>), definida como o conjunto dos pares ordenados cujas primeiras componentes tenham valor maior que as segundas componentes, aplicada sobre o mesmo conjunto Z, revela-se não-reflexiva, pois não é verdade que
a > a, ∀ a ∈ Z; não-simétrica, já que a > b não implica b > a, ∀ a e b ∈ Z; porém ela é
transitiva, uma vez que a > b e b > c implica a > c, ∀ a, b, c ∈ Z.
Uma relação que seja simultaneamente reflexiva, simétrica e transitiva é denominada
relação de equivalência. Se R é uma relação de equivalência sobre um conjunto A,
então R estabelece uma partição do conjunto A.
Suponha-se que R seja uma relação binária sobre A, e Ai , i ≥ 0, uma partição de
A induzida por R. Então, valem as seguintes propriedades:
• Se (a, b) ∈ R, então a ∈ Ai , b ∈ Aj e i = j ;
• Se (a, b) 6∈ R, então a ∈ Ai , b ∈ Aj e i 6= j .