02 · Matemática Discreta

Resumo em 30 segundos

A disciplina inteira é escrita na linguagem de conjuntos, relações e funções. Um autômato é uma 5-upla; a função de transição é uma função $K\times V\to K$; o “zero ou mais passos” das derivações é o fecho reflexivo-transitivo $R^{\ast }$; e a minimização de autômatos (que vem depois) usa classes de equivalência e partições. Esta aula é a caixa de ferramentas.

Anterior: 01 - Introdução e Conceitos Básicos · Voltar ao mapa · Próxima: 03 - Gramáticas Regulares

---

Slide 2: conjuntos e seus tipos

Conjunto é uma coleção não ordenada e sem repetição. Então $\{a,b\}=\{b,a\}=\{a,a,b\}$.

Tipo	Definição do slide	Exemplo
Finito	limites conhecidos e determinados	$\{0,1\}$
Infinito	não é possível determinar os limites	$\mathbb{N}$
Contável	dá para associar os elementos a $\mathbb{N}=\{0,1,2,\dots \}$	$\mathbb{Z}$, $\{0,1{\}}^{\ast }$
Incontável	ver alerta abaixo	$\mathbb{R}$

Cuidado com a definição de "incontável" do slide 2

O slide diz que incontável é quando “sempre é possível definir um novo elemento entre dois elementos quaisquer”. Isso descreve um conjunto denso, não um conjunto incontável. Os racionais $\mathbb{Q}$ são densos (entre dois racionais sempre há outro) e mesmo assim são contáveis. A definição usual é: incontável = infinito e não existe bijeção com $\mathbb{N}$ (exemplo clássico: $\mathbb{R}$, pelo argumento da diagonal de Cantor). Vale conferir com o professor qual definição ele cobra.

Os dois livros confirmam: o Menezes diz que $\mathbb{Z}$ e $\mathbb{Q}$ são contáveis e que os irracionais e $\mathbb{R}$ não são (Exemplo 11, p. 13). O Ramos prova que $\mathbb{Q}$ é enumerável e que $\mathbb{R}$ não é, com o argumento da diagonal (Exemplos 1.54 e 1.55, p. 52 a 54).

Slide 3: simbologia

• Conjuntos em maiúsculas ($A,B,C$), elementos em minúsculas ($a,b,c$).
• $a\in A$ (pertence), $a\notin A$ (não pertence).
• Conjunto universo ou alfabeto: $S$ ou $U$.
• Conjunto vazio: $\varnothing$.

Slides 4 e 5: produto cartesiano

$A\times B=\{(x,y)\mid x\in A\text{ e }y\in B\}$

Exemplo do slide, com $A=\{a,b,c\}$ e $B=\{d,e\}$:

• $A\times B=\{(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)\}$
• $B\times A=\{(d,a),(d,b),(d,c),(e,a),(e,b),(e,c)\}$
• Repare: $A\times B\ne B\times A$ (os pares são ordenados), mas $|A\times B|=|A|\cdot |B|=6$ nos dois casos.

Extensões:

• $n$ conjuntos: $A_1\times \cdots \times A_n$ = conjunto de $n$-uplas.
• Potência: $A^n=A\times A\times \cdots \times A$ ($n$ vezes), com $A^1=A$. Exemplo: $A^2$ com $A=\{a,b,c\}$ tem $3^2=9$ pares.

Onde isso aparece no curso

A função de transição de um AFD tem domínio $K\times V$: cada par (estado, símbolo) precisa de um destino. É por isso que a tabela de transição tem uma linha por estado e uma coluna por símbolo. Ver 04 - Autômatos Finitos Determinísticos > Tabela de transições.

Slide 6: relações

Uma relação em $A_1,\dots ,A_n$ é qualquer conjunto de $n$-uplas: $R\subseteq A_1\times \cdots \times A_n$. O caso mais usado é a relação binária em um conjunto $A$: $R\subseteq A\times A$.

Slides 7 e 8: funções

Uma função $f:A\to B$ é uma relação $f\subseteq A\times B$ em que cada $x\in A$ tem exatamente um $y\in B$ com $(x,y)\in f$.

• Unicidade: $(x,y)\in f$ e $(x,z)\in f\Rightarrow y=z$.
• Notações: $f(x)=y$, $f:x\mapsto y$, $f:A\to B$.
• Domínio $A$, codomínio $B$, contradomínio (imagem) $=\{y\in B\mid \exists x\in A,f(x)=y\}$.

Exemplo do slide 8, função sucessor em $\mathbb{Z}$: $suc(i)=i+1$, ou como conjunto de pares $\{\dots ,(-2,-1),(-1,0),(0,1),(1,2),\dots \}$.

Detalhe de notação no slide 8

O slide escreve “suc: $\mathbb{Z}\times \mathbb{Z}$”. O esperado é $suc:\mathbb{Z}\to \mathbb{Z}$. A função é um subconjunto de $\mathbb{Z}\times \mathbb{Z}$, mas a assinatura se escreve com a seta.

Função × relação no curso

A diferença entre AFD e AFND é exatamente esta: no AFD a transição é uma função $K\times V\to K$ (um destino). No AFND ela vai para $2^K$ (um conjunto de destinos), o que na prática funciona como uma relação.

Slide 9: injeção, sobrejeção e bijeção

Tipo	Condição	Intuição
Injetora	cada $b\in B$ é imagem de no máximo um $a$	não há “colisão”
Sobrejetora	cada $b\in B$ é imagem de pelo menos um $a$	cobre todo o codomínio
Bijetora	injetora e sobrejetora	correspondência um para um

Nas sobrejeções e bijeções, codomínio e contradomínio coincidem.

Slides 10 a 12: conjuntos enumeráveis

$A$ é enumerável se é vazio ou se existe uma sobrejeção $f:\mathbb{N}\to A$. Aí a lista $f(0),f(1),f(2),\dots$ passa por todos os elementos de $A$ (repetições são permitidas).

Fatos (os slides 11 e 12 são idênticos):

• Todo conjunto finito é enumerável.
• Um conjunto infinito é enumerável se e somente se existe uma injeção $A\to \mathbb{N}$, ou, equivalentemente, uma bijeção $A\to \mathbb{N}$.
• $\mathbb{N}$ e $\mathbb{Z}$ são enumeráveis. Para $\mathbb{Z}$: $0,1,-1,2,-2,3,-3,\dots$
• Entre dois conjuntos infinitos enumeráveis sempre existe uma bijeção.
• Subconjunto de enumerável é enumerável.

Complemento: por que isso importa para linguagens

$V^{\ast }$ é enumerável: liste as palavras por tamanho e, dentro do mesmo tamanho, em ordem alfabética ($\epsilon ,0,1,00,01,\dots$). Como toda linguagem é subconjunto de $V^{\ast }$, toda linguagem é enumerável. Já o conjunto de todas as linguagens sobre $V$ é $2^{V^{\ast }}$, que é incontável. Como só existem enumeravelmente muitos autômatos e gramáticas, conclui-se que existem linguagens que nenhum autômato reconhece. Esse argumento é padrão na teoria da computação; os slides não o apresentam.

Slides 13 e 14: propriedades de relações binárias

Notação: $xRy$ significa $(x,y)\in R$.

• Reflexiva: $xRx$ para todo $x$.
• Simétrica: $xRy\Rightarrow yRx$.
• Transitiva: $xRy$ e $yRz\Rightarrow xRz$.
• Equivalência: reflexiva + simétrica + transitiva.

Tabela do slide 14 em $\mathbb{N}$ (conferi por programa em uma amostra de $\mathbb{N}$):

	Reflexiva	Simétrica	Transitiva
$<$	não	não	sim
$\le$	sim	não	sim
$=$	sim	sim	sim
$\ne$	não	sim	não

Por que $\ne$ não é transitiva?

$1\ne 2$ e $2\ne 1$, mas $1\ne 1$ é falso. Um contraexemplo basta.

Slides 15 a 17: composição de relações

$R\circ S=\{(x,z)\mid \exists y,(x,y)\in R\text{ e }(y,z)\in S\}$

Ordem de leitura nos slides

Nos slides, $R\circ S$ significa “primeiro $R$, depois $S$”, e por isso $(R\circ S)(x)=S(R(x))$. Muitos livros usam a ordem contrária ($S\circ R$ para “primeiro $R$”). Na prova, siga a convenção do professor, e em outros materiais confira qual ordem o autor usa.

O Menezes usa a ordem contrária à dos slides: na Definição 1.11 (p. 11), $(g\circ f)(a)=g(f(a))$, ou seja, $g\circ f$ aplica primeiro $f$. O que o slide escreve como $R\circ S$, o Menezes escreveria $S\circ R$.

Exemplo do slide 16 (conferido por programa): $R=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}$ e $S=\{(2,1),(3,2),(4,3)\}$.

Como calcular $R\circ S$ na mão: para cada par $(x,y)$ de $R$, procure pares de $S$ que começam em $y$.

$(x,y)\in R$	$(y,z)\in S$	gera
(1,2)	(2,1)	(1,1)
(1,3)	(3,2)	(1,2)
(1,4)	(4,3)	(1,3)
(2,3)	(3,2)	(2,2)
(2,4)	(4,3)	(2,3)
(3,4)	(4,3)	(3,3)

Resultado: $R\circ S=\{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\}$ e $S\circ R=\{(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)\}$. Composição não é comutativa.

Slide 17: quando $R$ e $S$ são funções, a composição também é função. Com $R=\{(1,2),(2,3),(3,4),(4,1)\}$ e $S=\{(1,1),(2,1),(3,1),(4,2)\}$: $R\circ S=\{(1,1),(2,1),(3,2),(4,1)\}$ e $S\circ R=\{(1,2),(2,2),(3,2),(4,3)\}$.

Potências de relações e fechos R* e R+

Slides 18 a 21. Definição recursiva:

$R^0=I_A=\{(x,x)\mid x\in A\},R^{i+1}=R^i\circ R$

$x{R}^{i}y$ quer dizer “dá para ir de $x$ até $y$ em exatamente $i$ passos de $R$”.

Fatos: $I_A$ é o elemento neutro da composição; $R^1=R$; potências da mesma relação comutam ($R^i\circ R^j=R^j\circ R^i$).

Exemplo do slide 19 com $A=\{1,2,3,4\}$ e $R$ = “menor que” (conferido por programa):

Potência	Pares	Leitura
$R^0$	(1,1),(2,2),(3,3),(4,4)	zero passos
$R^1$	(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)	um passo
$R^2$	(1,3),(1,4),(2,4)	diferença de pelo menos 2
$R^3$	(1,4)	só 1 chega a 4 em 3 passos
$R^4,R^5,\dots$	$\varnothing$	não há cadeias tão longas

Fecho reflexivo-transitivo: $R^{\ast }={\bigcup }_{i\ge 0}{R}^i=R^0\cup R^1\cup R^2\cup \dots$ (“zero ou mais passos”). É a menor relação que contém $R$ e é reflexiva e transitiva.

Fecho transitivo: $R^{+}={\bigcup }_{i\ge 1}{R}^i$ (“um ou mais passos”).

No exemplo: $R^{+}=R$ (porque “menor que” já é transitiva) e $R^{\ast }=R\cup I$, ou seja, a relação $\le$.

Onde R* e R+ voltam

Nas gramáticas, $\alpha {\Rightarrow }^{\ast }\beta$ (“deriva em zero ou mais passos”) e $\alpha {\Rightarrow }^{+}\beta$ (“um ou mais”) são exatamente $R^{\ast }$ e $R^{+}$ aplicados à relação “deriva em um passo”. E $V^{\ast }$, $V^{+}$ da aula 01 seguem a mesma ideia. Ver 03 - Gramáticas Regulares > Derivações.

Slides 22 e 23: partições

Partição de $A$ é uma família de blocos $\Pi =\{B_i\}$ tal que:

1. nenhum bloco é vazio;
2. a união dos blocos é $A$;
3. blocos diferentes são disjuntos.

Exemplos com $A=\{a,b,c,d,e\}$: $\{\{a,b,c,d,e\}\}$, $\{\{a\},\{b\},\{c\},\{d\},\{e\}\}$, $\{\{a,b\},\{c,d,e\}\}$, $\{\{a,e\},\{b,c,d\}\}$.

Exercício do slide 23: todas as partições de {a, b, c, d, e}

São 52 partições (esse número é o número de Bell $B_5$). Gerei e contei por programa. Agrupadas pelo formato dos blocos:

Formato	Quantidade
5	1
4+1	5
3+2	10
3+1+1	10
2+2+1	15
2+1+1+1	10
1+1+1+1+1	1
Total	52

Formato 1+1+1+1+1: {a},{b},{c},{d},{e}

Formato 2+1+1+1 (escolha o par): {a,b} {a,c} {a,d} {a,e} {b,c} {b,d} {b,e} {c,d} {c,e} {d,e}, cada um com os outros três elementos sozinhos.

Formato 3+1+1 (escolha o trio): {a,b,c} {a,b,d} {a,b,e} {a,c,d} {a,c,e} {a,d,e} {b,c,d} {b,c,e} {b,d,e} {c,d,e}, com os outros dois sozinhos.

Formato 2+2+1 (escolha o elemento sozinho e divida os outros 4 em dois pares):

• sozinho e: {a,b}{c,d} · {a,c}{b,d} · {a,d}{b,c}
• sozinho d: {a,b}{c,e} · {a,c}{b,e} · {a,e}{b,c}
• sozinho c: {a,b}{d,e} · {a,d}{b,e} · {a,e}{b,d}
• sozinho b: {a,c}{d,e} · {a,d}{c,e} · {a,e}{c,d}
• sozinho a: {b,c}{d,e} · {b,d}{c,e} · {b,e}{c,d}

Formato 3+2 (escolha o trio, o resto vira par): {a,b,c}{d,e} · {a,b,d}{c,e} · {a,b,e}{c,d} · {a,c,d}{b,e} · {a,c,e}{b,d} · {a,d,e}{b,c} · {b,c,d}{a,e} · {b,c,e}{a,d} · {b,d,e}{a,c} · {c,d,e}{a,b}

Formato 4+1: {a,b,c,d}{e} · {a,b,c,e}{d} · {a,b,d,e}{c} · {a,c,d,e}{b} · {b,c,d,e}{a}

Formato 5: {a,b,c,d,e}

Estratégia para não se perder: organize por formato, como acima, e confira a contagem com combinações ($\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$, $\left(\genfrac{}{}{0ex}{}{5}{3}\right)=10$ etc.).

Slides 24 e 25: classes de equivalência

Se $R$ é uma equivalência em $A$, a classe de $a$ é $[a]=\{x\in A\mid xRa\}$ (todos os elementos equivalentes a $a$). Sempre $a\in [a]$.

Exemplo do slide 25: $A=\{a,b,c,d,e,f\}$, equivalência gerada por $aRb$, $bRc$, $dRe$.

1. Reflexividade acrescenta $(a,a),(b,b),\dots ,(f,f)$.
2. Simetria acrescenta $(b,a),(c,b),(e,d)$.
3. Transitividade acrescenta $(a,c),(c,a)$.

Classes: $[a]=[b]=[c]=\{a,b,c\}$, $[d]=[e]=\{d,e\}$, $[f]=\{f\}$.

flowchart LR
  subgraph C1["[a] = {a,b,c}"]
    a --- b --- c
  end
  subgraph C2["[d] = {d,e}"]
    d --- e
  end
  subgraph C3["[f] = {f}"]
    f
  end

Slides 26 a 28: conjunto quociente

$A/R=\{[x]\mid x\in A\}$ é o conjunto das classes. No exemplo: $A/R=\{\{a,b,c\},\{d,e\},\{f\}\}$.

Resultado central (as duas direções):

• Toda equivalência $R$ em $A$ gera uma partição $A/R$ (classes não vazias, cobrem $A$, e duas classes diferentes são disjuntas; o slide 27 prova a disjunção usando simetria e transitividade).
• Toda partição $P$ gera uma equivalência (“estar no mesmo bloco”), e $A/R=P$.

Onde isso volta

A minimização de AFD (conteúdo que costuma vir depois das aulas destes slides) agrupa estados “equivalentes” em classes. Cada classe vira um estado do autômato mínimo. Saber partição e classe de equivalência agora poupa trabalho depois.

---

Autoavaliação

1. Se |A| = 3 e |B| = 4, quantos elementos tem A × B? E quantas relações existem de A para B?

$|A\times B|=12$. Uma relação é qualquer subconjunto de $A\times B$, então existem $2^{12}=4096$ relações.

2. Dê uma relação simétrica e transitiva que não seja reflexiva.

Em $A=\{1,2\}$, $R=\{(1,1)\}$. É simétrica e transitiva, mas falta $(2,2)$.

3. Qual a diferença entre R* e R+?

$R^{\ast }$ inclui $R^0$ (zero passos, a identidade). $R^{+}$ começa em um passo.

---

Aprofundamento com os livros

Páginas das edições da sua pasta: Menezes 3ª edição (2000) e Ramos, José Neto e Vega (Bookman).

Função parcial × função total (isso importa para autômatos)

O Menezes separa os dois conceitos logo cedo (Definições 1.9 e 1.10, p. 10 e 11):

• Função parcial: cada elemento do domínio tem no máximo uma imagem. Pode haver elementos sem imagem. Exemplo do livro: a divisão em $\mathbb{R}$, que não é definida quando o divisor é 0.
• Função total (ou aplicação): função parcial definida para todos os elementos do domínio.

O Ramos faz a mesma distinção (p. 39 e 40) e chama de bijetora a função que é ao mesmo tempo total, injetora e sobrejetora (p. 41).

Por que isso volta na aula de autômatos

No Menezes, a função de transição de um AFD é uma função parcial (p. 33). Por isso uma tabela de transições com lacunas ainda é um AFD válido para ele: se a transição não existe, o autômato para e rejeita. Os slides escrevem $T:K\times V\to K$ sem dizer se é parcial, e o exercício 3 da aula 04 tem lacunas. Pelo Menezes, está tudo certo.

Mais propriedades de relações (Menezes, Definições 1.4 a 1.6, p. 8 e 9)

Além de reflexiva, simétrica e transitiva, o Menezes define:

• Antissimétrica: se $aRb$ e $bRa$, então $a=b$. Exemplo: $\le$ em $\mathbb{N}$.
• Relação de ordem parcial: reflexiva, antissimétrica e transitiva. Exemplo: $\subseteq$ entre subconjuntos.
• Ordem total: ordem parcial em que quaisquer dois elementos são comparáveis. Exemplo: $\le$ em $\mathbb{N}$.

Simétrica e antissimétrica não são opostas: uma relação pode não ser nenhuma das duas, e a identidade é as duas ao mesmo tempo (p. 9).

Uma relação de equivalência sempre particiona o conjunto. O exemplo do Menezes (Exemplo 5, p. 9): “ter o mesmo resto na divisão por 2” divide $\mathbb{N}$ em pares e ímpares.

Fecho de uma relação, do jeito do Menezes (Definições 1.7 e 1.8, p. 10)

Fecho de $R$ em relação a um conjunto de propriedades $P$ é a menor relação que contém $R$ e satisfaz $P$. O fecho transitivo $R^{+}$ é construído por regras:

1. todo par de $R$ está em $R^{+}$;
2. se $(a,b)\in R^{+}$ e $(b,c)\in R^{+}$, então $(a,c)\in R^{+}$;
3. nada mais está em $R^{+}$.

E $R^{\ast }=R^{+}\cup \{(a,a)\mid a\in A\}$.

Grafo como relação (Menezes, Exemplo 6, p. 10)

Arestas $\{(1,2),(2,3),(3,4),(1,5)\}$ em $V=\{1,2,3,4,5\}$. O fecho reflexivo e transitivo acrescenta os laços $(v,v)$ e os “atalhos” $(1,3),(1,4),(2,4)$. Resultado (conferido por programa): $\{(1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4),(5,5)\}$.

Leitura: $(x,y)\in R^{\ast }$ quer dizer “existe um caminho de $x$ até $y$”. É exatamente o que um autômato faz ao ir de um estado a outro lendo uma palavra.

Cardinalidade e conjuntos infinitos

Resultado	Ideia	Fonte
Um conjunto é infinito se tem bijeção com um subconjunto próprio de si mesmo	$\mathbb{N}\to \mathbb{N}-\{0\}$ com $n\mapsto n+1$	Menezes Def. 1.13 (p. 13); Ramos Ex. 1.57 (p. 55)
$\mathbb{Z}$ é contável	$a\mapsto 2a$ se $a\ge 0$, $a\mapsto |2a|-1$ se $a<0$ (não negativos vão para os pares, negativos para os ímpares)	Menezes Ex. 9 e 10 (p. 12 e 13)
$\mathbb{N}\times \mathbb{N}$ e $\mathbb{Q}$ são enumeráveis	percorrer a tabela de pares em diagonais	Ramos Ex. 1.54 (p. 52 e 53)
$\mathbb{R}$ não é enumerável	argumento da diagonal: dada qualquer lista de reais entre 0 e 1, monta-se um número que difere do $i$-ésimo na $i$-ésima casa decimal	Ramos Ex. 1.55 (p. 53 e 54)
$|A|<|2^A|$ (Teorema de Cantor)	supondo uma bijeção $f$, o conjunto $S=\{x\mid x\notin f(x)\}$ não pode ser imagem de ninguém	Ramos Teorema 1.3 (p. 55)
Subconjunto e união de enumeráveis são enumeráveis	intercalar as duas listas $a_0,b_0,a_1,b_1,\dots$	Ramos Teoremas 1.4 e 1.5 (p. 55 e 56)

Ligação com linguagens

Pelo Teorema de Cantor, $|2^{{\Sigma }^{\ast }}|>|{\Sigma }^{\ast }|$. O Ramos observa que $2^{\mathbb{N}}$ é não enumerável (p. 54). Como ${\Sigma }^{\ast }$ é enumerável, o conjunto de todas as linguagens sobre $\Sigma$ é não enumerável, enquanto o conjunto de todas as gramáticas (textos finitos) é enumerável. Conclusão: existem linguagens que nenhuma gramática descreve.

Conjunto fechado em relação a uma operação (Ramos, p. 37)

Um conjunto é fechado para uma operação quando aplicar a operação a elementos dele sempre dá um elemento dele. $\mathbb{Z}$ é fechado para subtração; $\mathbb{N}$ não é ($1-2=-1$). Essa ideia volta nas propriedades de fechamento das linguagens regulares (ver 08 - Tópicos Complementares dos Livros).

Técnicas de demonstração (Menezes 1.4, p. 16 a 21; Ramos 1.6, p. 47 a 51)

As provas das aulas 04 a 07 (T-chapéu, equivalência AFD/AFND) usam essas técnicas, então vale revisar:

Técnica	Como funciona	Exemplo dos livros
Direta	supõe a hipótese e chega na tese	$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$ (Menezes Ex. 14)
Contraposição	prova $\neg q\Rightarrow \neg p$ no lugar de $p\Rightarrow q$	$n!>n+1\Rightarrow n>2$ vira “se $n\le 2$, então $n!\le n+1$”, que se testa com 0, 1 e 2 (Menezes Ex. 15)
Absurdo	supõe a hipótese e a negação da tese e chega a uma contradição	0 é o único neutro da adição (Menezes Ex. 16); $\sqrt{2}$ é irracional (Ramos Ex. 1.48)
Indução	base $p(0)$ + passo $p(k)\Rightarrow p(k+1)$	$1+2+\cdots +n=(n^2+n)/2$ (Menezes Ex. 17)

Exercício 1.18 do Menezes: onde está o erro nesta "prova por indução"?

A “prova” diz: se em um grupo de $n$ torcedores pelo menos um é gremista, todos são. O passo pega dois subgrupos de tamanho $n$ que se sobrepõem.

Minha resposta: o passo de indução falha de $n=1$ para $n=2$. Com dois torcedores $\{T_1,T_2\}$, os subgrupos de tamanho 1 são $\{T_1\}$ e $\{T_2\}$, que não se sobrepõem, então nada liga o gremista de um grupo ao outro. Como o passo precisa valer para todo $k$, a indução inteira desaba. Lição: o passo de indução tem que funcionar também para os valores pequenos.

Exercícios extras do Menezes (seção 1.6, p. 27 a 30)

1.6: dê uma relação que não é simétrica nem antissimétrica, e uma que é as duas coisas

Minha resposta: em $\{1,2,3\}$, $R=\{(1,2),(2,1),(1,3)\}$ não é simétrica (falta $(3,1)$) nem antissimétrica ($(1,2)$ e $(2,1)$ com $1\ne 2$). Conferido por programa. A relação identidade $\{(1,1),(2,2),(3,3)\}$ é simétrica e antissimétrica.

1.7: fecho transitivo e fecho transitivo e reflexivo de $R=\{(1,1),(1,2),(2,1)\}$

Minha resposta (conferida por programa): de $(2,1)$ e $(1,2)$ sai $(2,2)$. Então $R^{+}=\{(1,1),(1,2),(2,1),(2,2)\}$. Em $A=\{1,2\}$, $R^{\ast }$ é igual, porque os laços já estão todos lá.

1.10: o conjunto vazio é relação, função parcial ou função?

Minha resposta: é relação (subconjunto de qualquer $A\times B$) e função parcial (nenhum elemento tem duas imagens). É função total só se o domínio também for vazio; caso contrário algum elemento fica sem imagem.

Para aprofundar nos livros

Onde ler (páginas das edições da sua pasta)

• Menezes (3ª ed.): 1.2 Conjuntos, Relações e Funções, p. 5 a 13 (inclui fecho e cardinalidade); 1.4 Técnicas de Demonstração, p. 16 a 21; exercícios 1.2 a 1.18, p. 27 a 30.
• Ramos, José Neto e Vega: 1.1 Conjuntos, p. 31 a 35 (inclui partição e De Morgan); 1.2 Relações, p. 35 a 38; 1.3 Funções, p. 38 a 42; 1.6 Teoremas e Demonstrações, p. 47 a 51; 1.7 Conjuntos Enumeráveis, p. 51 a 56. O autor também publica slides do capítulo 1 no site dele.

Relacionadas: Glossário · Flashcards