A Teoria de Conjuntos é a teoria matemática que se ocupa dum universo $U$ de indivíduos a que chamamos conjuntos. Diz-se que os objecto $a$ e $A$ existem e são conjuntos, se pertencem ao domínio $U$. Vamos supor que se verificam certas relações fundamentais, da forma $a\in A$, entre objectos $a$ e $A$ do domínio $U$. Se para dois objectos $a$ e $A$ vale a relação $a\in A$, diremos que ''$a$ é um elemento de $A$'' ou que ''$A$ contém $a$ como elemento''. Um conjunto designa-se geralmente por uma letra maiúscula, reservando-se as letras minúsculas para os seus elementos. A negação de $x\in A$ representa-se simbolicamente por $x\not \in A$.
Um conjunto pode ser descrito em extensão (quando o número dos seus elementos for finito e suficientemente pequeno) enumerando explicitamente todos os seus elementos e colocados entre chavetas e separados por vírgulas ou em compreensão, enunciando uma propriedade caracterizadora dos seus elementos (isto é, uma propriedade que os seus e só os seus elementos possuem).
Conjunto das vogais $V$ é descrito em extensão $V=\{a,e,i,o,u\}$;
Conjunto $L$ das palavras da lingua portuguesa escritas com 5 letras vogais, está descrito em compreensão;
Conjunto dos números naturais pares pode ser descrito, em compreensão, como sendo definido por naturais $n$ para os quais existe um natural $q$ tal que $n=2q$.
$1\in \{1,2,3\},\;\; 2 \in \{4,2,5\},\;\;7\not\in\{1,2,3\},\;\;\{1\}\not\in \{1,2,3\}$
$1\in\{n:\; n \text{ é um natural ímpar}\}\;\;2\not\in\{n:\; n \text{ é um natural ímpar}\}$
Dois conjuntos $A$ e $B$ são iguais se e só se têm os mesmos elementos. Neste caso escrevemos, $A=B$.
Simbolicamente temos $$A=B\Leftrightarrow \forall x(x\in A \leftrightarrow x\in B)$$ Dada uma expressão proposicional $P(x)$ (um predicado colectivizante), há um só conjunto que tem por elementos os $x$ que satisfazem $P(x)$, tal conjunto será denotado por $$\{x:P(x)\}.$$
No domínio $U$ dos conjuntos temos a relação de igualdade de conjuntos satisfaz:
Quando não se quer ser tão formal, escrevemos de forma equivalente;
A relação de igualdade de conjuntos satisfaz, para todos os conjuntos $A$, $B$ e $C$:
Enfraquecendo a relação de igualdade, diremos que $A$ é subconjunto de $B$ se todo o elemento de $A$ é um elemento de $B$, que podemos traduzir simbolicamente escrevendo:
$$A\subseteq B \Leftrightarrow \forall x (x\in A \rightarrow x\in B)$$Se $A=\{\{1\},2,3\}$, então $\{1\}\in A$, $\{\{1\},2\}\subseteq A$, $2\in A$, $\{2,3\}\subseteq A$.
Com esta definição pode enunciar-se que para conjuntos $A$ e $B$:
"$A\subseteq B$ e $B \subseteq A$ se e só se $A = B$."
Propriedade que podemos demonstrar, recorrendo às propriedades da lógica proposicional:
$$A\subseteq B \wedge B \subseteq A$$$$\Leftrightarrow$$$$\forall x (x\in A \rightarrow x\in B)\wedge\forall x (x\in B \rightarrow x\in A)$$ $$\Leftrightarrow$$ $$\forall x ((x\in A \rightarrow x\in B)\wedge (x\in B \rightarrow x\in A))$$ $$\Leftrightarrow$$ $$\forall x (x\in A \leftrightarrow x\in B)$$ $$\Leftrightarrow$$ $$A = B$$
De forma idêntica pode-se demonstrar a veracidade de cada uma das afirmações apresentadas na proposição abaixo:
No domínio $U$ dos conjuntos valem para a relação de inclusão:
Para conjuntos $A$, $B$ e $C$ valem:
Assumimos que no universo dos conjuntos existe um conjunto que não contém qualquer elemento, que denotamos por $\emptyset$, e que designamos de conjunto vazio. Se $a$ é um conjunto, existe um conjunto que contém apenas o elemento $a$, que representamos em extensão por $\{a\}$, e que designamos de \textbf{conjunto singular}. Se $a$ e $b$ são conjuntos existe um conjunto que contém $a$ e $b$, e apenas $a$ e $b$ como elementos, que representamos em extensão por $\{a,b\}$, que designamos de par não ordenado.
m predicado $P(x)$ diz-se colectivizante se define um conjunto. Se $P(x)$ é colectivizante, para cada conjunto $A$ existe um conjunto cujos elementos são precisamente os elementos $a$ de $A$ para os quais $P(a)$ é verdadeira.
Isto é, para cada expressão proposicional colectivizante $P(x)$ e cada conjunto $A$, a fórmula $$x\in A \wedge P(x),$$ define um conjunto. Assegura-se assim que existe um conjunto definido pela expressão:$$\{x:x\in A \wedge P(x)\} \text{ ou }\{x\in A:P(x)\}$$
Assegurando-se assim a existência da intersecção de dois conjuntos $A$ e $B$, $$A\cap B=\{x:x\in A\wedge x\in B\}$$
Para conjuntos $A,B$ e $C$ valem
Dois conjuntos $A$ e $B$ são disjuntos se e só se $A\cap B = \emptyset$, ou seja se não têm elementos em comum.
Se $A_1=\{\{1,2\},\{3\}\}$, $A_2=\{\{1\},\{2,3\}\}$ e $A_3=\{\{1,2,3\}\}$, os conjuntos $A_1,A_2,A_3$ são disjuntos dois a dois, já que $A_1\cap A_2=\emptyset$, $A_1\cap A_3=\emptyset$ e $A_1\cap A_3=\emptyset$.
Dado um conjunto $F$, existe um conjunto cujos elementos são os elementos dos elementos de $F$. Este conjunto chama-se \textbf{união de} $F$ e denota-se por $$\bigcup_{A\in F}A.$$
Dado o conjunto $$F=\{\{a,b\},\{a,b,c\},\{d\}\},$$ pelo axioma da união existe o conjunto $$\bigcup_{A\in F}A=\{a,b,c,d\}.$$
Isto garante a existência do conjunto $$A\cup B=\{x: x\in A \vee y\in B\}$$ a união de $A$ e $B$.
Dado o conjunto $$F=\{\{a,b\},\{a,b,c\},\{d\}\},$$ podemos assim escrever $$\bigcup_{A\in F}A=\{a,b\}\bigcup \{a,b,c\}\bigcup \{d\}=\{a,b,c,d\}.$$
Para $S=\{a,b,c,d\}$ e $Q=\{c,d,g,h\}$, temos $S\cup Q=\{a,b,c,d,g,h\}$ e $S\cap Q=\{c,d\}$.
Para conjuntos $A,B$ e $C$ temos:
Podemos ainda acrescentar as propriedades:
Para a união e intersecção de conjuntos temos: \begin{enumerate}
Apresentamos a demonstração de que $A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$
$A\cup(B\cap C)$ = $\{x:x\in A \vee x\in B\cap C\}$ = $\{x:x\in A \vee (x\in B\wedge x\in C)\}$ = $\{x:(x\in A \vee x\in B) \wedge (x\in A\vee x\in C)\}$ = $\{x:(x\in A \cup B) \wedge (x\in A\cup C)\}$ = $(A\cup B)\cap(A\cup C)$
Para calcular $A\cup(A\cap B)$ e $A\cap(A\cup B)$ podemos usar diagramas de Venn:
Temos assim $A\cup(A\cap B)=A$ e $A\cap(A\cup B)=A$.
A diferença entre dois conjuntos $A$ e $B$ ou o complementar de $B$ em $A$, $A-B$ ou $A\setminus B$, está definida e é o conjunto $$A\setminus B=\{x:x\in A \wedge x\notin B\}.$$
Dados $A=\{2,5,6\}$, $B=\{3,4,2\}$ e $C=\{1,3,4\}$, temos $A\setminus B = \{5,6\}$, $B\setminus A = \{3,4\}$, e $A\setminus C = \{2,5,6\}$.
Mostre que para todo o par de conjuntos $A$ e $B$, $$A\backslash(A\cap B) = A\backslash B.$$
Entendemos por \textbf{diferença simétrica} ou \textbf{soma booleana} entre dois conjuntos $A$ e $B$, ao conjunto $$A\oplus B=(A\setminus B)\cup(B\setminus A)=(A\cup B)\setminus (A\cap B).$$
As seguintes igualdades são valias:
$$A\oplus B=B\oplus A,\;\; A\oplus (B\oplus C)=(A\oplus B)\oplus C,\;\;A\oplus \emptyset=A$$Mostre que para todo o conjunto $A$, $$A\oplus \emptyset = A$$
Dado um conjunto $A$, existe um conjunto cujos elementos são os subconjuntos de $A$. O conjunto cuja existência é decretada por este axioma, chama-se \textbf{conjunto potência} de $A$, ou \textbf{conjunto das partes} de $A$, que se denota por $\mathcal{P}$, e representamos em compreensão por $$\mathcal{P}(A)=\{x:x\subseteq A\}.$$
Temos assim:
Seja $A$ um conjunto. Se o conjunto $A$ tem $n$ elementos, dizemos que $A$ é um \textbf{conjunto finito} e que o \textbf{cardinal} de $A$ é $n$. Neste caso escrevemos [\sharp A=n \text{ ou } |A|=n.] Um conjunto $A$ diz-se \textbf{infinito} se não é finito.
Assim
Para conjuntos finitos $A$ e $B$ tem-se $$|A\cup B|=|A|+|B|-|A\cap B|.$$
Se $A$ é um conjunto finito com $n$ elementos, então $|\mathcal{P}(A)|=2^n$.
Procuremos ilustrar este resultado através da árvore de decisão representada pelo diagrama abaixo.
O diagrama tem a seguinte interpretação: Se seleccionar um subconjunto $S$ de $\{a,b,c\}$. O circulo do topo, chamado nó, pode ser interpretado como sendo a pergunta: Está $a$ em $S$? Os dois arcos que saem dele têm como rótulos as duas respostas possíveis (Sim ou Não). Se seguirmos o arco com a resposta apropriada chegamos a um novo nó. Este nó codifica a próxima questão: O $b$ é um elemento de $S$? Seguindo o arco com a resposta certa chegamos a um novo nó. Que codifica a questão: O $c$ é um elemento de $S$? Escolhendo o arco com a resposta certa alcançamos a lista de elementos do conjunto $S$ seleccionado.
Assim, a construção dum subconjunto de $\{a,b,c\}$ corresponde a um percurso no diagrama partido do topo até à base. Existem assim tantos subconjuntos quanto o número de folhas no último nível (a base). Como o número de nós duplica de nível para nível, existem $2^3=8$ nós no último nível (caso a selecção seja feita num conjunto com $n$ elementos teríamos $2^n$ nós na árvore ou seja $2^n$ subconjuntos diferentes).
Só com os axiomas enunciados pode arquitectar-se uma teoria de conjuntos satisfatória. Vamos exemplificar um pouco da teoria com mais algumas definições e teoremas. Dados dois conjuntos $a$ e $b$, o axioma dos conjuntos elementares garante a existência do conjunto $$\{\{a\},\{a,b\}\},$$ a que se chama \textbf{par ordenado} de coordenadas $a$ e $b$ e que denotamos por $$(a,b).$$ Com base nos axiomas e definições que apresentámos é fácil demonstrar que $$(a,b)=(c,d)\Leftrightarrow a=c\wedge b=d.$$ Dados dois conjuntos $A$ e $B$, existe um conjunto cujos elementos são precisamente todos os pares ordenados $(a,b)$, com $a\in A$ e $b\in B$, designado de \textit{produto cartsiano} de $A$ por $B$ e que se denota por $$A\times B,$$ i.e. define-se $$A\times B=\{(a,b):a\in A\wedge b\in B\}.$$ Adoptando-se as seguintes convenções $$A^2=A\times A,$$ $$A^3=A^2\times A,$$ $$\ldots$$ $$A^n=A^{n-1}\times A.$$ Naturalmente, que se tem:
Se $A$ e $B$ são conjuntos finitos com $|A|=n$ e $|B|=m$, então $$|A\times B|=n\times m.$$
Se $A=\{\alpha,\beta\}$ e $B=\{1,2,3\}$ tem-se
Para três conjuntos $A,B,C$ temos $$A\times(B\cup C)=(A\times B)\cup (A\times C)$$ $$A\times(B\cap C)=(A\times B)\cap (A\times C)$$
Mostre que, para conjuntos $A,B,C$, $A\times(B\cup C)=(A\times B)\cup (A\times C)$
Dois conjuntos $A$ e $B$ são disjuntos se e só se $A\cap B = \emptyset$. Um conjunto de conjuntos é definido por conjuntos disjuntos, se os conjuntos no conjunto são disjuntos dois a dois.
O conjunto de conjuntos $F=\{\{1,3\},\{2,4,5\},\{0,6,7\}\}$, é definida por conjuntos disjuntos dois a dois, já que $\{1,3\}\cap\{2,4,5\}=\emptyset$, $\{1,3\}\cap\{2,4,5\}=\emptyset$ e $\{2,4,5\}\cap\{0,6,7\}=\emptyset$. Neste caso dizemos que $F$ é uma partição $\{0,1,2,3,4,5,6,7\}$
A \textbf{diferença entre dois conjuntos} $A$ e $B$ (também designado \textbf{o complementar} de $B$ em $A$), que se denota por $A-B$ ou $A\setminus B$, está definida e é o conjunto $$A\setminus B=\{x:x\in A \wedge x\notin B\}.$$
Um conjunto $E$ diz-se \textbf{universal} se cotem todos os conjuntos em discussão. Neste sentido, para todo o conjunto $A$, $$A\subseteq E$$ ou dito de outra forma, para todo o predicado $P(x)$ $$ E=\{x: P(x)\vee \sim P(x)\}. $$ Por outro lado o conjunto que não cotem elementos é designado de conjunto vazio, ou seja, para todo o predicado $P(x)$ tem-se $$\emptyset = \{x: P(x)\wedge \sim P(x)\}. $$ Neste sentido, para todo o conjunto $A$, $$\emptyset\subseteq A \text{ já que } \forall x(x\in \emptyset \rightarrow x\in A)\text{ é uma proposição verdadeira.}$$
Seja $E$ um conjunto universal. Para todo o conjunto $A$, o complemento de $A$ em $E$, $E-A$ é designado de \textbf{complemento do conjunto} $A$ e é denotado por $\overline{A}$. Neste sentido $$\overline{A}=\{x\in E:\sim x\in A\}=\{x:x\notin A\}.$$
Para um conjunto universo valem as seguintes igualdades:
A igualdade $\overline{A\cup B}=\overline{A}\cap \overline{B}$ pode ser demonstrada através
$\overline{A\cup B}$ = $\{x:\sim (x\in A\cup B)\}$ = $\{x:\sim (x\in A \vee x\in B)\}$ = $\{x:\sim (x\in A) \wedge \sim (x\in B)\}$ = $\{x:x\notin A \wedge x\notin B\}$ = $\{x:x\notin A\} \cap \{x:x\notin B\}$ = $\overline{A}\cap \overline{B}$
Assim definido tem-se $$A\setminus B=A\cap \overline{B}.$$
Entendemos por \textbf{diferença simétrica} ou \textbf{soma booleana} entre dois conjuntos $A$ e $B$ ao conjunto $$A\oplus B=(A\setminus B)\cup(B\setminus A)=(A\cup B)\setminus (A\cap B).$$
Chama-se \textbf{relação binária} definida de $A$ para $B$ a qualquer subconjunto de $A\times B$. Diz-se \textbf{relação binária definida em} $A$ a qualquer subconjunto de $A^2=A\times A$.
Dada uma relação binária $R$
Se $R$ é uma relação, existe o conjunto, chamado \textbf{domínio} de $R$ e denotado por $D(R)$, cujos elementos são os conjuntos $x$ para os quais existe $y$ tal que $(x,y)\in R$, i.e. $$D(R)=\{x:\exists y(xRy)\}.$$ De modo análogo, existe o \textbf{conjunto imagem} de $R$ dado por $$Im(R)=\{y:\exists x(xRy)\}.$$
Qualquer gráfico no plano define uma relação em $\mathbb{R}$. Em particular o gráfico que descreve o conjunto dos pares de reais $(x,y)$ solução da equação $x^2+y^2=1$, define a relação $$R=\{(x,y):x^2+y^2=1\}$$ em $\mathbb{R}$. Neste caso $0R1$, $1R0$, $-1R0$, mas $1R\!\!\!\!/1$. Temos ainda $D(R)=\{x:-1\leq x\leq 1\}$ e $Im(R)=\{y:-1\leq y\leq 1\}$. \begin{center} \includegraphics[width=100pt]{circle} \end{center}
Caso o conjunto $A$ onde uma relação $R$ está definida, não tenha muitos elementos, a relação binária $R$ pode ser definida por:
\section{Relação complementar} A relação complementar da relação binária $R$ em $A$, é a relação [\R=A^2\backslash R ] que pode ser definida negando a condição que define $R$.
\begin{exam} Seja $R$ a relação binária em $A=\{1,2,3\}$ dada por \[aRb\Leftrightarrow a\leq b,\forall a,b\in A.\] Assim $ a\R b \Leftrightarrow \sim (a\leq b) \Leftrightarrow a>b,\forall a,b\in A$ ou seja $\R=\{(2,1),(3,1),(3,2)\}$ que tem por diagrama sagital \begin{center} \includegraphics[width=100pt]{fig3} \end{center} que podemos definir pela tabela \begin{center} \begin{tabular}{|c|ccc|} \hline \R & 1 & 2 & 3 \\ \hline 1 & V & V & V \\ 2 & F & V & V \\ 3 & F & F & V \\ \hline \end{tabular} ou $ M_{\R}= \left[ \begin{array}{ccc} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{array} \right] $ \end{center} \end{exam}\begin{exam} No conjunto $A=\{1,2,3\}$ a relação dada por $aRb \Leftrightarrow a = b,\forall a,b\in A$ é representada por \begin{center} \includegraphics[width=200pt]{fig4} \end{center} a relação complementar é dada por $a\R b \Leftrightarrow a \neq b,\forall a,b\in A$ e pode ser representada por \begin{center} \includegraphics[width=200pt]{fig5} \end{center} \end{exam}Vamos classificar uma relação binária $R$, definida num conjunto $A$, sob três pontos de vista: \begin{enumerate} \item Reflexividade \item Simetria \item Transitividade \end{enumerate}
\section{Reflexividade}Uma relação binária $R$ definida no conjunto $A$ diz-se: \begin{enumerate} \item \textbf{Reflexiva} se: $\forall x\in A: xRx$. \item \textbf{Não reflexiva} se: $\exists x\in A: x\R x$. \item \textbf{Anti-reflexiva} se: $\forall x,y\in A: xRy\rightarrow x\neq y$. \end{enumerate}
\begin{exam}Exemplos de relações reflexivas no conjunto $A=\{1,2,3,4\}$ \begin{center} \includegraphics[width=150pt]{fig6} \includegraphics[width=150pt]{fig7} \end{center} \end{exam}Note que, uma relação finita é reflexiva se no diagrama sagital cada ponto tem um laço, ou caso na matriz da relação todos os elementos da diagonal são 1. \begin{exam}Exemplos de relações anti-reflexivas no conjunto $A=\{1,2,3\}$ \begin{center} \includegraphics[width=150pt]{fig8} \includegraphics[width=150pt]{fig9} \end{center} \end{exam}
\section{Simetria} Uma relação binária $R$ definida no conjunto $A$ diz-se: \begin{enumerate} \item \textbf{Simétrica} se: $\forall x,y\in A: xRy\rightarrow yRx$. \item \textbf{Não simétrica} se: $\exists x,y\in A: xRy \wedge y\R x$. \item \textbf{Anti-simétrica} se: $\forall x,y\in A: xRy \wedge yRx \rightarrow x = y$. \end{enumerate}
\begin{exam}Exemplos de relações simétricas no conjunto $A=\{1,2,3,4\}$ \begin{center} \includegraphics[width=150pt]{fig10} \includegraphics[width=150pt]{fig12} \end{center} \end{exam}Note que, no diagrama sagital duma relação simétrica, sempre que existe uma seta de $x$ para $y$ temos também uma seta de $y$ para $x$. Uma matriz $M_R$ representa uma relação simétrica se é simétrica. \begin{center} \includegraphics[width=150pt]{Asymmetric} \includegraphics[width=150pt]{PartitionMatrixSym2} \includegraphics[width=150pt]{h-mat} \end{center} \begin{exam}Exemplos de relações anti-simétricas no conjunto $A=\{1,2,3\}$ \begin{center} \includegraphics[width=150pt]{fig13} \includegraphics[width=150pt]{fig14} \end{center} \end{exam}
\section{Transitividade} Uma relação binária $R$ definida no conjunto $A$ diz-se: \begin{enumerate} \item \textbf{Transitiva} se: $\forall x,y,z\in A: xRy \wedge yRz \rightarrow xRz$. \item \textbf{Não transitiva} se: $\exists x,y,z\in A: xRy \wedge yRz \wedge x\R z$. \end{enumerate}
\begin{exam}Exemplos de relações transitivas no conjunto $A=\{1,2,3,4\}$ \begin{center} \includegraphics[width=150pt]{fig15} \includegraphics[width=150pt]{fig16} \includegraphics[width=150pt]{fig17} \end{center} \end{exam}\begin{exam}Exemplo duma relação não transitiva no conjunto $A=\{1,2,3,4\}$ \begin{center} \includegraphics[width=150pt]{fig18} \end{center} \end{exam}Mostre que sempre que $f:A\rightarrow B$ e $g:B\rightarrow C$ são sobrejectivas, $g\circ f$ é sobrejectiva.
Os conjuntos abaixo definem funções no conjunto $\{(2,3),(2,4),(3,2),(3,4),(1,4)\}$? Nesse caso, determine o seu domínio e classifique se são injectivas ou sobrejectivas.
Para duas relações de equivalência, no conjunto $A=\{0,1,2\}$, $R$ e $S$ definidas pelas matrizes $M_S=\left[ \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right]$ e $M_R=\left[ \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \\ \end{array} \right].$ As relações $M_S\times M_R$ e $\{(a,b)\in A\times B: (b,a)\in S\}$ são também relações de equivalência?
Por $R$ representa-se a relação em $A=\{1,2,3,4,5,6\}$ tal que, $a R b$ se e só se, no autómato da Figura \ref{fig1} se pode transitar do estado $a$ para o estado $b$. Num autómato podemos transitar do estado $a$ para o estado $b$, sempre que existe um arco de $a$ para $b$. Por exemplo, no autómato da Figura \ref{fig1}, são verdade $2R2$,$2R4$,$2R6$ e $2R5$, mas é falso $2R3$ e $2R1$.
Considere o código em Python abaixo, que implementa uma função $$R(set,set)->set,$$ tal que $R(A,D)$ devolve uma relação em $A$, onde $D$ é também uma relação em $A$. def R(A,D): Rel = set() for x in A: A={(x,x)} B=set() while A!=B: B=set(A) for (a,b) in D: if (x,a) in A and not (x,b) in A: A.add((x,b)) Rel=Rel|A return Rel
Para $A=\{1,2,3,4\}$ e $D=\{(1,2),(1,3),(3,4)\}$. Determine os pares que definem a relação que resulta da execução de:
>>> R(A,D)
Considere o conjunto $X=\{1,2,3,4,5,6,7,8\}$ parcialmente ordenado de acordo com o seguinte diagrama de Hasse.
Considere ainda os subconjuntos $A=\{3,4,7\}$ e $B=\{2,3,4,5\}$. Determine caso existam:
Mostre que, $n^2+n$ é par, para todo o inteiro $n\geq 0$.
Mostre que, $1+2+4+8\cdots+2^{n-1}=2^n-1$, para todo o inteiro $n\geq 1$.
Mostre que, $\sum_{k=1}^nk2^k=(n-1)2^{n+1}+2$, para todo $n \geq 1$
Considere a seguinte função definida por recorrência:
def mdc(a,b): # onde a <= b
if a== 0:
return b
else:
mdc(b,a%b)
Calcule o valor devolvido pela função, para $mdc(4,155)$, justificando a resposta.
In [ ]:
Considere a seguinte função definida por recorrência:
def f(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return f(n-1)+f(n-2)
O dicionário abaixo representa uma árvore.
G={'A':['',{'B','C','D'}],
'B':['A',{'E','F'}],
'C':['A',set()],
'D':['A',set()],
'E':['B',set()],
'F':['B',{'G'}],
'G':['F',set()]
}
As chaves de $G$ definem os rótulos dos vértices da árvore. Por 'B':['A',{'E','F'}] descrevemos que B está ligado a A, E e F. Neste caso, dizemos que A é o pai de B e que E e F são filhos de B. Por 'A':['',{'B','C','D'}] identifica-se A como não tendo pai e por 'G':['F',set()] identifica-se G como não tendo filhos. Numa árvore um vértice sem \emph{pai} diz-se a raiz da árvore. Um vértice sem filhos diz-se uma folha.
A árvore descrita pelo dicionário $G$ pode assumir a representação abaixo.
Considere a função c(dict,str)-> set definida por:
def c(G,v):
A={v}
B=set()
L=set()
while A != B:
B = set(A)
print A
for v in B:
for x in G[v][1]:
if not x in A:
if len(G[x][1])== 0:
L.add(x)
else:
A.add(x)
return L
O dicionário
D ={1:[2,3], 2:[4], 3:[4], 4:[6,5], 5:[7], 6:[7],7:[]}
representa o diagrama de Hasse, de uma ordem parcial no conjunto $\{1,2,3,4,5,6,7\}$, onde por exemplo, 1:[2,3] codifica que $1\leq 2$ e $1\leq 3$. Considere a função $sup(dict,int)-> set$ definida por:
def sup(D,x):
aux=set()
for el in D[x]:
aux = aux | sup(D,el)
return set(D[x])| aux
Dada uma relação $R$, no conjunto $A=\{0,1,\ldots,n-1\}$, escreva em Python três funções:
Dada uma relação $R$, no conjunto $A=\{0,1,\ldots,n-1\}$, escreva em Python três funções:
In [ ]: