\documentclass[10pt]{beamer} %\usepackage[brazil]{babel} \usepackage[english]{babel} \usepackage[T1]{fontenc} \usepackage{ae} \usepackage[utf8x]{inputenc} \usepackage{amsmath,amsfonts,amssymb,amsthm} \usepackage{graphicx, color} \usepackage{verbatim} \usepackage{tikz} \usepackage{tkz-graph} \usetikzlibrary{calc} \usepackage[normalem]{ulem} \usepackage{latexsym,enumerate} \usepackage{fancybox} \usepackage[T1]{fontenc} \usepackage{scalefnt} \newcommand{\esp}[1]{\hspace{#1 mm}} \usepackage{centernot} \usepackage[thicklines]{cancel} \newcommand*{\mynot}[1]{\renewcommand{\CancelColor}{\color{#1}}\cancel} \def\cnot{\mynot{red}} %\def\cnot{\not\mathrel} \def\And{\wedge} \def\Or{\vee} \def\AND{\bigwedge} \def\OR{\bigvee} \def\iff{\Leftrightarrow} \def\tto{\Rightarrow} \def\Iff{\Longleftrightarrow} \def\Tto{\Longrightarrow} \newcommand{\TtoB}[1]{\stackrel{\corB{#1}}{\Tto}} \newcommand{\IffB}[1]{\stackrel{\corB{#1}}{\Iff}} \newcommand{\EqB}[1]{\stackrel{\cor{#1}}{=}} \def\NN{{\mathbb N}} \def\RR{{\mathbb R}} \def\QQ{{\mathbb Q}} \def\ZZ{{\mathbb Z}} \def\CC{{\mathbb C}} \def\PP{{\mathbb P}} \def\TT{{\mathbb T}} \def\EE{{\mathbb E}} \definecolor{red}{rgb}{1,0,0} \definecolor{redy}{rgb}{0.9,0,0} \definecolor{greeny}{rgb}{0,0.8,0} \definecolor{bluey}{rgb}{0.3,0.3,0.6} \definecolor{blue}{rgb}{0,0,1} \definecolor{orange}{rgb}{0.8,0.2,0} \definecolor{whitey}{rgb}{1,1,1} \definecolor{purple}{rgb}{0.4,0,0.4} \definecolor{pink}{rgb}{0.7,0,0.6}%{0.8,0.1,0.5}{1,1,0.9-light} \definecolor{brown}{rgb}{0.5,0.3,0.2} \definecolor{dkblue}{rgb}{0,0.4,0.3} \definecolor{lblue}{rgb}{0.2,0.2,0.7} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{question}[theorem]{Question} \begin{document} \setbeamercovered{highly dynamic} \def\pix{p} \def\x{\mathbf{x}} \def\y{\mathbf{y}} \def\z{\mathbf{z}} \def\p{\mathbf{p}} \def\u{\mathbf{u}} \def\e{\mathbf{e}} \def\w{\mathbf{w}} \def\eps{\varepsilon} \def\S{\mathfrak{S}} \def\PP{\mathbb{P}} \def\EE{\mathbb{E}} \def\cor{\textcolor{blue}} \def\corB{\textcolor{green}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{\centering \huge{\alert{Capítulo 5.6\\INDUÇÃO MATEMÁTICA\\COMPLETA (ou FORTE)}} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Indução Matemática Forte (ou Completa)} \begin{block}{Princípio da Indução Matemática Forte} \begin{itemize} \item A indução matemática normal é contemplada pela indução forte. \item \cor{Indução normal 1:} Provar que vale para $n+1$ assumindo que vale para $n$ \item \cor{Indução normal 2:} Provar que vale para $n$ assumindo que vale para $n-1$ \item \cor{Indução forte:} Provar que vale para $n$ assumindo que vale para todo valor menor que $n$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Números $F_n$ de Fibonacci} \begin{block}{Números de Fibonacci:\ \ $0,1,1,2,3,5,8,13,21,34,55,89,\ldots$} \begin{itemize} \item $F_0=0;\ \ \ F_1=1$ \item $F_n\ =\ F_{n-1}+F_{n-2},\ \ \forall n\geq 2$ \end{itemize} \end{block} \begin{block}{Limite superior: $F_{n}<2^n,\ \ \forall n\geq 0$} \begin{itemize} \item\textbf{Caso base:} $F_0=0<1=2^0$;\ \ \ $F_1=1<2^1$ \item\textbf{H.I.:} Fixe $n\geq 2$ e suponha $F_k<2^k,\ \forall\ 0\leq k (1.6^n)/3,\ \ \forall n>0$} \begin{itemize} \item\textbf{Caso base:} $F_1=1> 1.6^1/3$;\ \ $F_2=1> 1.6^2/3$ \item\textbf{H.I.:} Fixe $n\geq 3$ e suponha $F_k> 1.6^k/3,\ \forall\ 1\leq k 1.6^n/3$.} \item $F_n\ =\ F_{n-1}+F_{n-2}\ >\ 1.6^{n-1}/3+1.6^{n-2}/3\ =$ \item $=\ 2.6\cdot(1.6)^{n-2}/3\ >\ 2.56\cdot(1.6)^{n-2}/3\ =\ 1.6^n/3$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Números $F_n$ de Fibonacci} \begin{block}{Números de Fibonacci:\ \ $0,1,1,2,3,5,8,13,21,34,55,89,\ldots$} \begin{itemize} \item $F_0=0;\ \ \ F_1=1$ \item $F_n\ =\ F_{n-1}+F_{n-2},\ \ \forall n\geq 2$ \end{itemize} \end{block} \begin{block}{Limite superior: $F_{n}<1.618^n,\ \ \forall n\geq 0$} \begin{itemize} \item\textbf{Proporção Áurea:} \alert{$x=(1+\sqrt{5})/2=1.618\ \Tto\ x^2=x+1$.} \item\textbf{Caso base:} $F_0=0<1=1.618^0$;\ \ \ $F_1=1<1.618^1$ \item\textbf{H.I.:} Fixe $n\geq 2$ e suponha $F_k<1.618^k,\ \forall\ 0\leq k (1.618^n)/3,\ \ \forall n>0$} \begin{itemize} \item\textbf{Proporção Áurea:} \alert{$x=(1+\sqrt{5})/2=1.618\ \Tto\ x^2=x+1$.} \item\textbf{Caso base:} $F_1=1> 1.618^1/3$;\ \ $F_2=1> 1.618^2/3$ \item\textbf{H.I.:} Fixe $n\geq 3$ e suponha $F_k>1.618^k/3,\ \forall\ 1\leq k 1.618^n/3$.} \item $F_n\ =\ F_{n-1}+F_{n-2}\ >\ 1.618^{n-1}/3+1.618^{n-2}/3\ =$ \item $=\ (2.618)\cdot 1.618^{n-2}/3\ =\ (1.618)^2\cdot 1.618^{n-2}/3\ =\ 1.618^n/3$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Números $F_n$ de Fibonacci:\ \ $0,1,1,2,3,5,8,13,21,34,\ldots$} \begin{figure}\centering \includegraphics[scale=0.5]{fibonacci.png} %\caption{} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Números $F_n$ de Fibonacci:\ \ $0,1,1,2,3,5,8,13,21,34,\ldots$} \begin{itemize} \item $F_0=0;\ \ \ F_1=1$;\ \ \ $F_n\ =\ F_{n-1}+F_{n-2},\ \ \forall n\geq 2$ \item Proporção Áurea: \alert{$x^2-x-1=0\ \Tto$ raízes $\alpha,\beta=(1\pm\sqrt{5})/2$.} \item Provar por indução que: $F(n)=F'(n)$, onde \end{itemize} \[ F'(n)\ =\ \frac{\alpha^n-\beta^n}{\alpha-\beta}\ =\ \frac{1}{\sqrt{5}} \left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\} \] \begin{block}{Prova por Indução Forte} \begin{itemize} \item \cor{BASE:} $F'(0)=0$ e $F'(1)=1$. \alert{OK} \item \cor{Hipótese de Indução:} Fixe $n\geq 2$ e suponha valer para todo valor $k=0,\ldots,n-1$. \item \alert{Passo da Indução}: Vamos provar que vale para $n$. \item $F(n)\ =\ F(n-1)+F(n-2)\ =\ F'(n-1)+F'(n-2)$. Logo: \[ F(n)\ =\ \frac{\alpha^{n-1}-\beta^{n-1}+\alpha^{n-2}-\beta^{n-2}}{\alpha-\beta}\ =\ \frac{\alpha^{n-2}(\alpha+1)-\beta^{n-2}(\beta+1)}{\alpha-\beta} \] \item $F(n)\ =\ (\alpha^{n-2}\cdot\alpha^2\ -\ \beta^{n-2}\cdot\beta^2)/(\alpha-\beta)\ =\ F'(n)$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Números $F_n$ de Fibonacci:\ \ $0,1,1,2,3,5,8,13,21,34,\ldots$} \begin{figure}\centering \includegraphics[scale=0.5]{fibonacci2.png} %\caption{} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\frame{ %\frametitle{Proporção Áurea} %\textbf{Proporção Áurea:} \alert{$x=(1+\sqrt{5})/2=1.618\ \Tto\ x^2=x+1$.} %Dizemos que $a>b$ estão em proporção áurea se $(a+b)/a\ =\ a/b$, o que implica que $a/b=1.618$. Nesse caso, vale: %\[ % \frac{a+b}{a}=\frac{a}{b}=\frac{b}{a-b}=\frac{a-b}{2b-a}=\frac{2b-a}{2a-3b}=\frac{2a-3b}{5b-3a}=\frac{5b-3a}{5a-8b} %\] %\begin{figure}\centering %\includegraphics[scale=0.5]{fibonacci2.png} %\end{figure} %} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Exercícios de prova passada} \alert{Prove que} $\forall n\geq 700:\ \ n\ <\ (1.01)^n$.\ \ {\bf Dica:} $(1.01)^{231}<10<(1.01)^{232}$. \begin{itemize} \item Base: $696<700<10^3<(1.01)^{3\cdot 232}=(1.01)^{696}<1.01^{700}$ \item H.I: Fixe $n>700$ e assuma valer para todo inteiro $700\leq k1.01\cdot(n-1)=n+0.01\cdot(n-100)>n$ \end{itemize} \alert{Prove que} $\forall n\geq 96:\ \ n^2\ <\ (1.1)^n$.\ \ \ {\bf Dica:} $(1.1)^{23}<10<(1.1)^{24}$. \begin{itemize} \item Base: $(96)^2<(100)^2=10^4<(1.1)^{4\cdot 24}=(1.1)^{96}$ \item H.I: Fixe $n>96$ e assuma valer para todo inteiro $96\leq k1.1\cdot(n-1)^2=n^2+0.1\cdot(n^2-22n+10)>n^2$ \end{itemize} \alert{Prove que} $\forall n\geq 100:\ \ n^{10}\ <\ 2^n$.\ \ \ \ \ {\bf Dica:} $10^3<2^{10}$\ \ e\ \ $(1.01)^{10}<2$. \begin{itemize} \item Base: $100^{10}=10^{20}<10^{30}=(1000)^{10}<1024^{10}=2^{100}$ \item H.I: Fixe $n>100$ e assuma valer para todo inteiro $100\leq k2(n-1)^{10}>(1.01)^{10}(n-1)^{10}=$ \item $=(1.01n-1.01)^{10}=(n+0.01\cdot(n-101))^{10}\geq n^{10}$ \end{itemize} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Exercícios de prova passada} \begin{figure}\centering \includegraphics[scale=0.5]{prova1.inducao1.png} %\caption{} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Exercícios de prova passada} \begin{figure}\centering \includegraphics[scale=0.5]{prova1.inducao2.png} %\caption{} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Exercícios de prova passada} \alert{\bf Prove que}, para todo inteiro $n\geq 2$, o {\bf complemento da interseção} de $n$ conjuntos quaisquer $A_1,A_2,\ldots,A_n$ é igual a \cor{união dos complementos} desses $n$ conjuntos. \vspace{1cm} \cor{Prova por indução forte} (apesar da indução normal ser suficiente) \begin{itemize} \item \cor{\bf Base} $n=2$: $\overline{A_1\cap A_2}\ =\ \overline{A_1}\cup\overline{A_2}$ (OK por De Morgan) \item \cor{\bf H.I:} Fixe $n>2$ e assuma valer para todo inteiro $2\leq k2$ e assuma valer para todo inteiro $2\leq k, blue, thick] (x) edge node[above]{$T$} (z) edge node[below]{$T$} (z2); \path[->, red, thick] (z) edge node[above]{$R$} (y); \path[->, green, thick] (z2) edge node[below]{$S$} (y); \end{tikzpicture}} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ %\frametitle{Relações - Exercício 6.8} \begin{block}{Exercício 6.8:} Sejam $R,S,T$ relações quaisquer. Prove que: \begin{itemize} \item \alert{$(R\cap S)\circ T\ \subseteq\ R\circ T\ \cap\ S\circ T$} \item $(R\cup S)\circ T\ =\ R\circ T\ \cup\ S\circ T$ \item $(R-S)\circ T \ \supseteq\ R\circ T\ - \ S\circ T$ \end{itemize} \end{block} \begin{block}{Solução} \begin{itemize} \item $(x,y)\in(R\cap S)\circ T\iff \exists z: (x,z)\in T\And(z,y)\in R\cap S\iff$ \item $\iff\exists z: (x,z)\in T\And(z,y)\in R\And(z,y)\in S\alert{\tto}$ \item $\alert{\tto}(\exists z: (x,z)\in T\And(z,y)\in R)\And(\exists z': (x,z')\in T\And(z',y)\in S)\iff$ \item $\iff(x,y)\in R\circ T\And(x,y)\in S\circ T\iff$ \item $\iff(x,y)\in R\circ T\ \cap\ S\circ T\ \ \ \square$ \end{itemize} \end{block} \begin{block}{Contraexemplo da igualdade} \begin{itemize} \item $T=\{(x,z),(x,z')\}$, $R=\{(z,y)\}$, $S=\{(z',y)\}\ \tto$ \item $\tto\ R\cap S=\emptyset\tto(R\cap S)\circ T=\emptyset$ \item $R\circ T=\{(x,y)\}$ e $S\circ T=\{(x,y)\}\ \tto\ R\circ T\ \cap\ S\circ T=\{(x,y)\}$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ %\frametitle{Relações - Exercício 6.8} \begin{block}{Exercício 6.8:} Sejam $R,S,T$ relações quaisquer. Prove que: \begin{itemize} \item $(R\cap S)\circ T\ \subseteq\ R\circ T\ \cap\ S\circ T$ \item \alert{$(R\cup S)\circ T\ =\ R\circ T\ \cup\ S\circ T$} \item $(R-S)\circ T \ \supseteq\ R\circ T\ - \ S\circ T$ \end{itemize} \end{block} \begin{block}{Solução} \begin{itemize} \item $(x,y)\in(R\cup S)\circ T\iff \exists z: (x,z)\in T\And(z,y)\in R\cup S\iff$ \item $\iff\exists z: (x,z)\in T\And((z,y)\in R\Or(z,y)\in S)\iff$ \item $\iff\exists z: ((x,z)\in T\And(z,y)\in R)\Or((x,z)\in T\And(z,y)\in S)\iff$ \item $\iff\exists z: ((x,z)\in T\And(z,y)\in R)\Or\exists z':((x,z')\in T\And(z',y)\in S)\iff$ \item $\iff(x,y)\in R\circ T\Or(x,y)\in S\circ T\iff$ \item $\iff(x,y)\in R\circ T\ \cup\ S\circ T\ \ \ \square$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ %\frametitle{Relações - Exercício 6.8} \begin{block}{Exercício 6.8:} Sejam $R,S,T$ relações quaisquer. Prove que: \begin{itemize} \item $(R\cap S)\circ T\ \subseteq\ R\circ T\ \cap\ S\circ T$ \item $(R\cup S)\circ T\ =\ R\circ T\ \cup\ S\circ T$ \item \alert{$(R-S)\circ T \ \supseteq\ R\circ T\ - \ S\circ T$} \end{itemize} \end{block} \begin{block}{Solução} \begin{itemize} \item $(x,y)\in R\circ T\ -\ S\circ T\iff$ \item $\iff(x,y)\in R\circ T\And(x,y)\not\in S\circ T\iff$ \item $\iff\exists z: ((x,z)\in T\And(z,y)\in R)\And\forall z':(x,z')\in T\to(z',y)\not\in S)\alert{\tto}$ \item $\alert{\tto}\exists z: (x,z)\in T\And(z,y)\in R\And(z,y)\not\in S\iff$ \item $\iff\exists z: (x,z)\in T\And(z,y)\in R-S\iff(x,y)\in(R-S)\circ T$ \end{itemize} \end{block} \begin{block}{Contraexemplo da igualdade} \begin{itemize} \item $T=\{(x,z),(x,z')\}$, $R=\{(z,y)\}$, $S=\{(z',y)\}\ \tto$ \item $\tto\ R-S=\{(z,y)\}\tto(R-S)\circ T=\{(x,y)\}$ \item $R\circ T=\{(x,y)\}$ e $S\circ T=\{(x,y)\}\ \tto\ R\circ T\ -\ S\circ T=\emptyset$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ %\frametitle{Relações - Exercício 6.8} \begin{block}{Exercício 6.9:} Seja $n\geq 1$ um número natural e $A$ o conjunto dos inteiros entre 1 e $n$, inclusive. Note que o conjunto $A\times A$ tem $n^2$ pares. Encontre duas relações $R$ e $S$ sobre $A$, cada uma com no máximo $2n$ pares, tal que $R\circ S$ seja o conjunto $A\times A$. \end{block} \begin{block}{Solução} \begin{itemize} \item $S\ =\ \{(1,1),(2,1),(3,1),\ldots,(n,1)\}$ \item $R\ =\ \{(1,1),(1,2),(1,3),\ldots,(1,n)\}$ \item $\forall x,y\in A:\ (x,1)\in S$ e $(1,y)\in R$\ \ $\Tto$\ \ $(x,y)\in R\circ S$ \item $R\circ S\ =\ A\times A$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Inversa da Composta} \begin{block}{Lema (inversa da composta)} Dadas relações $R$ e $S$, temos que \[ (S\circ R)^{-1}\ =\ R^{-1}\circ S^{-1} \] \end{block} \begin{block}{Prova:} \begin{itemize} \item $(x,y)\in(S\circ R)^{-1}\ \Iff\ (y,x)\in S\circ R\ \Iff$ \item $\Iff\ \exists z: (y,z)\in R\ \And (z,x)\in S\ \Iff$ \item $\Iff\ \exists z: (x,z)\in S^{-1}\ \And (z,y)\in R^{-1}\ \Iff$ \item $\Iff\ (x,y)\in R^{-1}\circ S^{-1}$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Associatividade da Composição de Relações} \begin{block}{Lema} Dadas relações $R$, $S$ e $T$, temos que: \[ T\circ(S\circ R)\ =\ (T\circ S)\circ R \] \end{block} \begin{block}{Prova - Exercício 6.13} \begin{itemize} \item $(a,d)\in T\circ(S\circ R)\ \Iff\ \exists c: (a,c)\in S\circ R\And(c,d)\in T\Iff$ \item $\exists c: (\exists b: (a,b)\in R\And(b,c)\in S)\And(c,d)\in T\Iff$ \item $\exists b:\ \exists c: (a,b)\in R\And(b,c)\in S\And(c,d)\in T\Iff$ \item $\exists b: (a,b)\in R\And(b,d)\in T\circ S\ \Iff\ (a,d)\in (T\circ S)\circ R$ \end{itemize} \end{block} \begin{figure}\centering\scalebox{0.8}{ \begin{tikzpicture}[auto] \tikzstyle{vertex}=[draw,circle,fill=yellow!25,minimum size=12pt,inner sep=1pt] \node[vertex] (a) at (0,0) {$a$}; \node[vertex] (b) at (2,0) {$b$}; \node[vertex] (c) at (4,0) {$c$}; \node[vertex] (d) at (6,0) {$d$}; \path[->, blue, thick] (a) edge node[above]{$R$} (b); \path[->, red, thick] (b) edge node[above]{$S$} (c); \path[->, green, thick] (c) edge node[above]{$T$} (d); \end{tikzpicture}} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Potência de uma Relação $R$} \begin{block}{Definição recursiva} $R^1=R$ e $\forall m\in\NN$, $m\geq 1$:\ \ $R^{m+1}=R^m\circ R$ \end{block} \begin{block}{Exemplo:} Seja $R$ a relação em $\NN$ tal que $(x,y)\in R\ \Iff\ y=x+1$. Ou seja, $R=\{(0,1),\ (1,2),\ (2,3),\ldots\}$. \end{block} \begin{block}{Descreva $R^m$ para $m\geq 1$ qualquer} \begin{itemize} \item $\forall x\in\NN: (x,x+1)\in R$ e $(x+1,x+2)\in R$\ \ $\Iff$\ \ $(x,x+2)\in R^2$ \item $\forall x\in\NN: (x,x+1)\in R$ e $(x+1,x+3)\in R^2$\ \ $\Iff$\ \ $(x,x+3)\in R^3$ \item $\forall x\in\NN: (x,x+1)\in R$ e $(x+1,x+4)\in R^3$\ \ $\Iff$\ \ $(x,x+4)\in R^4$ \item $\ldots$ \item $R^m\ =\ \{(x,x+m)\ :\ x\in\NN\}$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Potência de uma Relação $R$} \begin{block}{Definição recursiva} $R^1=R$ e $\forall m\in\NN$, $m\geq 1$:\ \ $R^{m+1}=R^m\circ R$ \end{block} \begin{block}{Exemplo:} Seja $R$ a relação em $\NN$ tal que $(x,y)\in R\ \Iff\ y=x+1\ \Or\ y=x+2$. Ou seja, $R=\{(x,x+1),\ (x,x+2)\ :\ x\in\NN\}$.\\ Ou seja, $R=\{(0,1),\ (0,2),\ (1,2),\ (1,3),\ (2,3),\ (2,4),\ldots\}$. \end{block} \begin{block}{Descreva $R^m$ para $m\geq 1$ qualquer} \begin{itemize} \item $R^2=\{(x,x+2),(x,x+3),(x,x+4)\ :\ x\in\NN\}$ \item $R^3=\{(x,x+3),(x,x+4),(x,x+5),(x,x+6)\ :\ x\in\NN\}$ \item $R^4=\{(x,x+4),\ldots,(x,x+8)\ :\ x\in\NN\}$ \item $\ldots$ \item $R^m\ =\ \{(x,x+m),\ldots,(x,x+2m)\ :\ x\in\NN\}$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Potência de uma Relação $R$} \begin{block}{Definição recursiva} $R^1=R$ e $\forall m\in\NN$, $m\geq 1$:\ \ $R^{m+1}=R^m\circ R$ \end{block} \begin{block}{Exercício 6.16} Prove que, para toda relação $R$ e quaisquer $m$ e $n$ inteiros positivos: $R^m\circ R^n = R^{m+n}$. \end{block} \begin{block}{Solução} \begin{itemize} \item Prova por indução em $n$. \item \textbf{Caso base:} $n=1\ \tto\ R^m\circ R^1\ =\ R^m\circ R\ =\ R^{m+1}$. OK \item \textbf{HI:} Fixe $n>1$ e assuma que vale para todo $n',red,thick] (a) to [bend right=15] (b); \draw[->,red,thick] (b) to [bend right=15] (a); \draw[->,red,thick] (c) to [bend right=15] (d); \draw[->,red,thick] (d) to [bend right=15] (a); \draw[->,red,thick] (a) to [out=150,in=210,looseness=10] (a); \draw[->,red,thick] (b) to [out=-30,in=30,looseness=10] (b); \draw[->,red,thick] (c) to [out=-30,in=30,looseness=10] (c); \draw[->,red,thick] (d) to [out=150,in=210,looseness=10] (d); \node[vert2] (a) at (5,1) {$1$}; \node[vert2] (b) at (7,1) {$2$}; \draw[->,green,thick] (a) to [bend right=15] (b); \draw[->,green,thick] (b) to [bend right=15] (a); \draw[->,green,thick] (a) to [out=150,in=210,looseness=10] (a); \node[vert3] (a) at (10,2) {$1$}; \node[vert3] (b) at (12,2) {$2$}; \node[vert3] (c) at (12,0) {$3$}; \node[vert3] (d) at (10,0) {$4$}; \draw[->,blue,thick] (a) to [bend right=15] (b); \draw[->,blue,thick] (b) to [bend right=15] (a); \draw[->,blue,thick] (a) to [bend right=15] (d); \draw[->,blue,thick] (d) to [bend right=15] (a); \draw[->,blue,thick] (a) to [out=150,in=210,looseness=10] (a); \draw[->,blue,thick] (b) to [out=-30,in=30,looseness=10] (b); \draw[->,blue,thick] (c) to [out=-30,in=30,looseness=10] (c); \draw[->,blue,thick] (d) to [out=150,in=210,looseness=10] (d); \end{tikzpicture}} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ %\frametitle{Propriedades de Relações} \begin{block}{Relação $R$ em $A$\ \ - \ \ $R\subseteq A\times A$\ - \ \ $Dom(R)\cup Img(R)\subseteq A$} \begin{itemize} \item Reflexiva sobre $A$: $\forall a\in A: (a,a)\in R$ \esp{15}\alert{Todos os laços} \item Irreflexiva:\esp{13}$\nexists a: (a,a)\in R$ \esp{22}\alert{Nenhum laço} \item Simétrica:\esp{13}$(x,y)\in R\ \Tto\ (y,x)\in R$ \esp{4}\alert{Vai e volta} \item Antissimétrica:\esp{6}$(x,y)\in R,x\ne y\ \Tto\ (y,x)\not\in R$ \esp{1}\alert{Vai, não volta} \item Transitiva:\esp{13}$(x,y)\in R\ \And\ (y,z)\in R\ \Tto\ (x,z)\in R$ \end{itemize} \end{block} \begin{block}{Exemplos: $A=\{1,2,3,4\}$} \begin{itemize} \item \textcolor{red}{\bf $R_4\ =\ \{(2,1),\ (3,1),\ (3,2),\ (4,1),\ (4,2),\ (4,3)\}$} \item \textcolor{green}{\bf $R_5\ =\ \{(1,1),\ (1,2),\ (1,3),\ (1,4),\ (2,2),\ (2,3),\ (2,4),\ (3,3),\ (3,4),\ (4,4)\}$} \item \textcolor{blue}{\bf $R_6\ =\ \{(3,4)\}$} \end{itemize} \end{block} \begin{figure}\centering\scalebox{0.8}{ \begin{tikzpicture}[auto] \tikzstyle{vert1}=[draw,circle,fill=red!25,minimum size=12pt,inner sep=1pt] \tikzstyle{vert2}=[draw,circle,fill=green!25,minimum size=12pt,inner sep=1pt] \tikzstyle{vert3}=[draw,circle,fill=blue!25,minimum size=12pt,inner sep=1pt] \node[vert1] (a) at (0,2) {$1$}; \node[vert1] (b) at (2,2) {$2$}; \node[vert1] (c) at (2,0) {$3$}; \node[vert1] (d) at (0,0) {$4$}; \draw[->,red,thick] (b) to [bend right=15] (a); \draw[->,red,thick] (c) to [bend right=15] (a); \draw[->,red,thick] (c) to [bend right=15] (b); \draw[->,red,thick] (d) to [bend right=15] (a); \draw[->,red,thick] (d) to [bend right=15] (b); \draw[->,red,thick] (d) to [bend right=15] (c); \node[vert2] (a) at (5,2) {$1$}; \node[vert2] (b) at (7,2) {$2$}; \node[vert2] (c) at (7,0) {$3$}; \node[vert2] (d) at (5,0) {$4$}; \draw[->,green,thick] (a) to [bend right=15] (b); \draw[->,green,thick] (a) to [bend right=15] (c); \draw[->,green,thick] (a) to [bend right=15] (d); \draw[->,green,thick] (b) to [bend right=15] (c); \draw[->,green,thick] (b) to [bend right=15] (d); \draw[->,green,thick] (c) to [bend right=15] (d); \draw[->,green,thick] (a) to [out=150,in=210,looseness=10] (a); \draw[->,green,thick] (b) to [out=-30,in=30,looseness=10] (b); \draw[->,green,thick] (c) to [out=-30,in=30,looseness=10] (c); \draw[->,green,thick] (d) to [out=150,in=210,looseness=10] (d); \node[vert3] (c) at (10,1) {$3$}; \node[vert3] (d) at (12,1) {$4$}; \draw[->,blue,thick] (c) to [bend right=15] (d); \end{tikzpicture}} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{6.3. Propriedades de Relações} \begin{block}{Exercício 6.17} Prove que uma relação $R$ é irreflexiva se e somente se ela é disjunta de $I_A$ onde $A = Dom(R)$ \alert{ou $A=Img(R)$}. \end{block} \begin{block}{Lembretes:} \begin{itemize} \item $I_A\ =\ \{(a,a):\ a\in A\}$ (\alert{relação Identidade do conjunto $A$}) \item $R$ é irreflexiva se e só se $\nexists a: (a,a)\in R$. \end{itemize} \end{block} \begin{block}{Solução} \begin{itemize} \item $R$ é irreflexiva\ $\Iff$\ $\nexists a: (a,a)\in R$\ $\Iff$ \item $\Iff\ \nexists a\in Dom(R): (a,a)\in R$\ $\Iff$\ $R\cap I_{Dom(R)}=\emptyset$ \item $\ldots$ \item $\Iff\ \nexists a\in Img(R): (a,a)\in R$\ $\Iff$\ $R\cap I_{Img(R)}=\emptyset$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{6.3. Propriedades de Relações} \begin{block}{Exercício 6.18} Prove que uma relação $R$ é simétrica se e somente se ela é igual à sua inversa. \end{block} \begin{block}{Lembretes:} \begin{itemize} \item $R^{-1}\ =\ \{(y,x):\ (x,y)\in R\}$ (\alert{relação Inversa de $R$}) \item $R$ é simétrica se e só se $\forall (x,y)\in R:\ (y,x)\in R$. \end{itemize} \end{block} \begin{block}{Solução} \begin{itemize} \item $R$ é simétrica\ $\Iff$\ $\forall (x,y)\in R:\ (y,x)\in R$\ $\Iff$ \item $\Iff\ \forall (x,y)\in R:\ (x,y)\in R^{-1}$\ $\Iff$\ $R\subseteq R^{-1}\ \Iff$ \item $\ldots$ \item $\Iff\ \forall (y,x)\in R^{-1}:\ (y,x)\in R$\ $\Iff$\ $R^{-1}\subseteq R\ \Iff$ \item $\ldots$ \item $\Iff\ R=R^{-1}$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{6.3. Propriedades de Relações} \begin{block}{Exercício 6.19} Prove que uma relação $R$ é antissimétrica \alert{e irreflexiva} se e somente se ela é disjunta de sua inversa. \end{block} \begin{block}{Lembretes:} \begin{itemize} \item $A$ e $B$ são disjuntos se e só se $A\cap B=\emptyset$ \item $R^{-1}\ =\ \{(y,x):\ (x,y)\in R\}$ (\alert{relação Inversa de $R$}) \item $R$ é antissimétrica se e só se $\forall x\ne y:\ (x,y)\in R\tto(y,x)\not\in R$. \end{itemize} \end{block} \begin{block}{Solução} \begin{itemize} \item $R$ é antissimétrica e irreflexiva\ $\Iff$\ $\forall (x,y)\in R: (y,x)\not\in R$\ $\Iff$ \item $\Iff\ \forall (x,y)\in R:\ (x,y)\not\in R^{-1}$\ $\Iff$\ $R\cap R^{-1}\ =\ \emptyset$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{6.3. Propriedades de Relações} \begin{block}{Exercício 6.20} Seja $R$ uma relação simétrica e transitiva sobre um conjunto $A$. Prove que, se para todo $x\in A$, existe um $y\in A$ tal que $xRy$, então $R$ é reflexiva. \end{block} \begin{block}{Lembretes:} \begin{itemize} \item $xRy\ \ \Iff\ \ (x,y)\in R$ \item $R$ é simétrica se e só se $\forall (x,y)\in R:\ (y,x)\in R$. \item $R$ é transitiva se e só se $\forall (x,y),(y,z)\in R:\ (x,z)\in R$. \item $R$ é reflexiva sobre $A$ se e só se $\forall a\in A:\ (a,a)\in R$. \end{itemize} \end{block} \begin{block}{Solução} \begin{itemize} \item Seja $R$ uma relação simétrica e transitiva tal que $\forall x\in A:\ \exists y: xRy$. \item Seja $x$ um elemento qualquer de $A$. Logo existe $y$ tal que $(x,y)\in R$. \item $R$ é simétrica: $(y,x)\in R$. \item Como $R$ é transitiva: $(x,y)\in R \And (y,x)\in R$\ $\Iff$\ $(x,x)\in R$. \item Como $\forall x\in A:\ (x,x)\in R$, então $R$ é reflexiva. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ %\frametitle{Propriedades de Relações} \begin{block}{Exercício Lista 2} Mostre que se $R$ é uma relação reflexiva e transitiva, então $R \cap R^{-1}$ é uma reflexiva, simétrica e transitiva. \end{block} \begin{block}{Solução} \begin{itemize} \item \textcolor{green}{REF:} $x\in Dom(R\cap R^{-1})\Tto(x,x)\in R\Tto(x,x)\in R^{-1}\Tto$ \item $\Tto\ (x,x)\in R\cap R^{-1}$\ $\Tto$\ \alert{$R\cap R^{-1}$ é reflexiva} \item \textcolor{green}{SIM:} $(x,y)\in R\cap R^{-1}\Tto(x,y)\in R\Tto(y,x)\in R^{-1}$ \item \esp{8}$(x,y)\in R\cap R^{-1}\Tto(x,y)\in R^{-1}\Tto(y,x)\in R$ \item $(x,y)\in R\cap R^{-1}\Tto(y,x)\in R\cap R^{-1}$\ $\Tto$\ \alert{$R\cap R^{-1}$ é simétrica} \item \textcolor{green}{TR:} $(x,y),(y,z)\in R\cap R^{-1}\Tto(x,y),(y,z)\in R\Tto(x,z)\in R$. \item \esp{7}$(x,y),(y,z)\in R\cap R^{-1}\Tto(x,y),(y,z)\in R^{-1}\Tto$ \item $\Tto(z,y),(y,x)\in R\Tto(z,x)\in R\Tto(x,z)\in R^{-1}$. \item $(x,y),(y,z)\in R\cap R^{-1}\tto(x,z)\in R\cap R^{-1}$$\tto$\alert{$R\cap R^{-1}$ é transitiva} \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ %\frametitle{Propriedades de Relações} \begin{block}{Exercício Lista 2} Sejam $A$ um conjunto e $R \subseteq A \times A$. Seja ainda $S=R^2=R\circ R$: \[ S = \{ (a, a') \mid \exists a'' \in A, (a, a'') \in R \And (a'', a') \in R \}. \] Prove ou dê um contra-exemplo: \begin{itemize} \item[(a)] $R$ é reflexiva, simétrica e transitiva\ $\Tto$\ $S$ também o é. \item[(b)] $S$ é reflexiva, simétrica e transitiva\ $\Tto$\ $R$ também o é. \end{itemize} \end{block} \begin{block}{Solução (b): Contraexemplo} \begin{itemize} \item $R=\{(1,2),\ (2,1)\}$\ $\Tto$\ $S=\{(1,1),\ (2,2)\}$\ $\Tto$ \item $\Tto$\ $S$ é reflexiva, simétrica e transitiva, mas $R$ \alert{não} é reflexiva. \end{itemize} \end{block} \begin{figure}\centering\scalebox{0.8}{ \begin{tikzpicture}[auto] \tikzstyle{vert1}=[draw,circle,fill=blue!25,minimum size=12pt,inner sep=1pt] \tikzstyle{vert2}=[draw,circle,fill=red!25,minimum size=12pt,inner sep=1pt] \node[vert1] (a) at (0,0) {$1$}; \node[vert1] (b) at (2,0) {$2$}; \draw[->,blue,thick] (a) to [bend right=15] (b) node[above]{\textcolor{blue}{$R$}}; \draw[->,blue,thick] (b) to [bend right=15] (a) node[above]{\textcolor{blue}{$R$}}; \node[vert2] (a) at (6,0) {$1$}; \node[vert2] (b) at (8,0) {$2$}; \draw[->,red,thick] (a) to [out=60,in=120,looseness=10] (a) node[above]{\alert{$S$}}; \draw[->,red,thick] (b) to [out=60,in=120,looseness=10] (b) node[above]{\alert{$S$}}; \end{tikzpicture}} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ %\frametitle{Propriedades de Relações} \begin{block}{Exercício Lista 2} Sejam $A$ um conjunto e $R \subseteq A \times A$. Seja ainda $S=R^2=R\circ R$: \[ S = \{ (a, a') \mid \exists a'' \in A, (a, a'') \in R \And (a'', a') \in R \}. \] Prove ou dê um contra-exemplo: \begin{itemize} \item[(a)] $R$ é reflexiva, simétrica e transitiva\ $\Tto$\ $S$ também o é. \item[(b)] $S$ é reflexiva, simétrica e transitiva\ $\Tto$\ $R$ também o é. \end{itemize} \end{block} \begin{block}{Solução (a):} \begin{itemize} \item \textcolor{green}{REF:} $a\in A$\ $\Tto$\ $(a,a)\in R$\ $\Tto$ \item $\Tto$\ $(a,a)\in R\And(a,a)\in R$\ $\Tto$\ $(a,a)\in S$\ $\Tto$\ \alert{$S$ é reflexiva}. \item \textcolor{green}{SIM:} $(a,c)\in S$\ $\Tto$\ $\exists b: (a,b),(b,c)\in R$\ $\Tto$ \item $\Tto$\ $(c,b),(b,a)\in R$\ $\Tto$\ $(c,a)\in S$\ $\Tto$\ \alert{$S$ é simétrica}. \item \textcolor{green}{TR:} $(a,c),(c,e)\in S$\ $\Tto$\ $\exists b,d: (a,b),(b,c),(c,d),(d,e)\in R$\ $\Tto$ \item $\Tto$\ $(a,c),(c,e)\in R$\ $\Tto$\ $(a,e)\in S$\ $\Tto$\ \alert{$S$ é transitiva}. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{6.3.1. Composição e Transitividade} \begin{block}{Exercício 6.21} Demonstre a afirmação, ou encontre um contraexemplo: ``Se $R^4\subseteq R$, então $R$ é transitiva''. \end{block} \begin{block}{Lembretes:} \begin{itemize} \item Teorema 6.3: $R$ é transitiva\ $\Iff$\ $R\circ R=R^2\subseteq R$ \item Teorema 6.4: $R$ é transitiva\ $\Iff$\ $R^n\subseteq R, \forall n\geq 1$ \end{itemize} \end{block} \begin{block}{Solução: contraexemplo} \begin{itemize} \item $R=\{(1,2),\ (2,3),\ (3,1)\}$ \item $R^2=\{(1,3),\ (2,1),\ (3,2)\}$ \item $R^3=\{(1,1),\ (2,2),\ (3,3)\}$ \item $R^4=\{(1,2),\ (2,3),\ (3,1)\}$ \item $R^4=R$, mas $R$ \alert{não} é transitiva \item $\square$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{6.3.1. Composição e Transitividade} \begin{block}{Exercício 6.21'} Demonstre a afirmação, ou encontre um contraexemplo: ``Se $R^5\subseteq R$, então $R$ é transitiva''. \end{block} \begin{block}{Lembretes:} \begin{itemize} \item Teorema 6.3: $R$ é transitiva\ $\Iff$\ $R\circ R=R^2\subseteq R$ \item Teorema 6.4: $R$ é transitiva\ $\Iff$\ $R^n\subseteq R, \forall n\geq 1$ \end{itemize} \end{block} \begin{block}{Solução: contraexemplo} \begin{itemize} \item $R =\{(1,2),\ (2,3),\ (3,4),\ (4,1)\}$ \item $R^2=\{(1,3),\ (2,4),\ (3,1),\ (4,2)\}$ \item $R^3=\{(1,4),\ (2,1),\ (3,2),\ (4,3)\}$ \item $R^4=\{(1,1),\ (2,2),\ (3,3),\ (4,4)\}$ \item $R^5=\{(1,2),\ (2,3),\ (3,4),\ (4,1)\}$ \item $R^5=R$, mas $R$ \alert{não} é transitiva\ \ \ $\square$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{6.3.1. Composição e Transitividade} \begin{block}{Exercício 6.21''} Demonstre a afirmação, ou encontre um contraexemplo: ``Se $R^3\subseteq R$, então $R$ é transitiva''. \end{block} \begin{block}{Lembretes:} \begin{itemize} \item Teorema 6.3: $R$ é transitiva\ $\Iff$\ $R\circ R=R^2\subseteq R$ \item Teorema 6.4: $R$ é transitiva\ $\Iff$\ $R^n\subseteq R, \forall n\geq 1$ \end{itemize} \end{block} \begin{block}{Solução: contraexemplo} \begin{itemize} \item $R =\{(1,2),\ (2,1)\}$ \item $R^2=\{(1,1),\ (2,2)\}$ \item $R^3=\{(1,2),\ (2,1)\}$ \item $R^3=R$, mas $R$ \alert{não} é transitiva\ \ \ $\square$ \item pois $(1,2)\in R$ e $(2,1)\in R$, mas $(1,1)\not\in R$ e $(2,2)\not\in R$ \item $\square$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{6.4. Representação de Relações usando Matrizes} \begin{block}{Notações $\sum$ (somatório) e $\prod$ (produtório)} Sejam $x_1,x_2,\ldots,x_n$ números reais. \[ \sum_{k=1}^n x_k\ \ =\ \ x_1+x_2+x_3+\ldots+x_n \] \[ \prod_{k=1}^n x_k\ \ =\ \ x_1\ \cdot\ x_2\ \cdot\ x_3\ \cdot\ldots\cdot\ x_n \] \end{block} \begin{block}{Notações $\AND$\ e\ $\OR$} Sejam $S_1,S_2,\ldots,S_n$ sentenças lógicas (com valor \textbf{F} ou \textbf{V}). \[ \OR_{k=1}^n S_k\ \ =\ \ S_1\Or S_2\Or S_3\Or\ldots\Or S_n \] \[ \AND_{k=1}^n S_k\ \ =\ \ S_1\And S_2\And S_3\And\ldots\And S_n \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{6.4. Representação de Relações usando Matrizes} \begin{block}{Notações $\bigcap$ e $\bigcup$} Sejam $C_1,C_2,\ldots,C_n$ conjuntos. \[ \bigcup_{k=1}^n C_k\ \ =\ \ C_1\cup C_2\cup C_3\cup\ldots\cup C_n \] \[ \bigcap_{k=1}^n C_k\ \ =\ \ C_1\cap C_2\cap C_3\cap\ldots\cap C_n \] \end{block} \begin{block}{Notações $\AND$\ e\ $\OR$} Sejam $S_1,S_2,\ldots,S_n$ sentenças lógicas (com valor \textbf{F} ou \textbf{V}). \[ \OR_{k=1}^n S_k\ \ =\ \ S_1\Or S_2\Or S_3\Or\ldots\Or S_n \] \[ \AND_{k=1}^n S_k\ \ =\ \ S_1\And S_2\And S_3\And\ldots\And S_n \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Fecho Reflexivo} \begin{block}{Exemplo: $A=\{1,2,3,4,5\}$} \begin{itemize} \item \cor{$R\ =\ \{(1,2),\ (2,3),\ (3,4),\ (4,5)\}$} \item \item \alert{$I_A\ =\ \{(1,1), (2,2), (3,3), (4,4), (5,5)\}$} \item Fecho Reflexivo de $R\ =\ R\ \cup\ I_A$ \end{itemize} \end{block} \begin{figure}\centering\scalebox{0.8}{ \begin{tikzpicture}[auto] \tikzstyle{vert1}=[draw,circle,fill=black!15,minimum size=12pt,inner sep=1pt] \node[vert1] (a) at (0,0) {$1$}; \node[vert1] (b) at (2,0) {$2$}; \node[vert1] (c) at (4,0) {$3$}; \node[vert1] (d) at (6,0) {$4$}; \node[vert1] (e) at (8,0) {$5$}; \draw[->,blue,thick] (a) to [bend left=15] (b); \node at (1,0.4) {$\cor{R}$}; \draw[->,blue,thick] (b) to [bend left=15] (c); \node at (3,0.4) {$\cor{R}$}; \draw[->,blue,thick] (c) to [bend left=15] (d); \node at (5,0.4) {$\cor{R}$}; \draw[->,blue,thick] (d) to [bend left=15] (e); \node at (7,0.4) {$\cor{R}$}; \draw[->,red] (a) to [out=-120,in=-60,looseness=10] (a); \node at (0,-1) {\alert{I$_A$}}; \draw[->,red] (b) to [out=-120,in=-60,looseness=10] (b); \node at (2,-1) {\alert{I$_A$}}; \draw[->,red] (c) to [out=-120,in=-60,looseness=10] (c); \node at (4,-1) {\alert{I$_A$}}; \draw[->,red] (d) to [out=-120,in=-60,looseness=10] (d); \node at (6,-1) {\alert{I$_A$}}; \draw[->,red] (e) to [out=-120,in=-60,looseness=10] (e); \node at (8,-1) {\alert{I$_A$}}; \end{tikzpicture}} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Fecho Simétrico} \begin{block}{Exemplo: $A=\{1,2,3,4,5\}$} \begin{itemize} \item \cor{$R\ =\ \{(1,2),\ (2,3),\ (3,4),\ (4,5)\}$} \item \item \textcolor{green}{\bf $R^{-1}\ =\ \{(2,1),\ (3,2),\ (4,3),\ (5,4)\}$} \item Fecho Simétrico de $R\ =\ R\ \cup\ R^{-1}$ \end{itemize} \end{block} \begin{figure}\centering\scalebox{0.8}{ \begin{tikzpicture}[auto] \tikzstyle{vert1}=[draw,circle,fill=black!15,minimum size=12pt,inner sep=1pt] \node[vert1] (a) at (0,0) {$1$}; \node[vert1] (b) at (2,0) {$2$}; \node[vert1] (c) at (4,0) {$3$}; \node[vert1] (d) at (6,0) {$4$}; \node[vert1] (e) at (8,0) {$5$}; \draw[->,blue,thick] (a) to [bend left=15] (b); \node at (1,0.4) {$\cor{R}$}; \draw[->,blue,thick] (b) to [bend left=15] (c); \node at (3,0.4) {$\cor{R}$}; \draw[->,blue,thick] (c) to [bend left=15] (d); \node at (5,0.4) {$\cor{R}$}; \draw[->,blue,thick] (d) to [bend left=15] (e); \node at (7,0.4) {$\cor{R}$}; \draw[->,green,thick] (b) to [bend left=15] (a); \node at (1,-0.4) {\textcolor{green}{\bf $R^{-1}$}}; \draw[->,green,thick] (c) to [bend left=15] (b); \node at (3,-0.4) {\textcolor{green}{\bf $R^{-1}$}}; \draw[->,green,thick] (d) to [bend left=15] (c); \node at (5,-0.4) {\textcolor{green}{\bf $R^{-1}$}}; \draw[->,green,thick] (e) to [bend left=15] (d); \node at (7,-0.4) {\textcolor{green}{\bf $R^{-1}$}}; \end{tikzpicture}} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Fecho Transitivo} \begin{block}{Exemplo: $A=\{1,2,3,4,5\}$} \begin{itemize} \item \cor{$R\ =\ \{(1,2),\ (2,3),\ (3,4),\ (4,5)\}$} \item \item \alert{$R^2\ =\ \{(1,3), (2,4), (3,5)\}$} \item \textcolor{green}{\bf $R^3\ =\ \{(1,4), (2,5)\}$} \item \textcolor{yellow}{\bf $R^4\ =\ \{(1,5)\}$} \item Fecho Transitivo $R^*\ =\ R\ \cup\ R^2\ \cup\ R^3\ \cup\ R^4$ \end{itemize} \end{block} \begin{figure}\centering\scalebox{0.8}{ \begin{tikzpicture}[auto] \tikzstyle{vert1}=[draw,circle,fill=black!15,minimum size=12pt,inner sep=1pt] \node[vert1] (a) at (0,0) {$1$}; \node[vert1] (b) at (2,0) {$2$}; \node[vert1] (c) at (4,0) {$3$}; \node[vert1] (d) at (6,0) {$4$}; \node[vert1] (e) at (8,0) {$5$}; \draw[->,blue,thick] (a) to [bend left=15] (b); \node at (1,0.3) {\cor{$R$}}; \draw[->,blue,thick] (b) to [bend left=15] (c); \node at (3,0.3) {\cor{$R$}}; \draw[->,blue,thick] (c) to [bend left=15] (d); \node at (5,0.3) {\cor{$R$}}; \draw[->,blue,thick] (d) to [bend left=15] (e); \node at (7,0.3) {\cor{$R$}}; \draw[->,red,thick] (a) to [bend left=30] (c); \node at (2,0.8) {\alert{$R^2$}}; \draw[->,red,thick] (b) to [bend left=30] (d); \node at (4,0.8) {\alert{$R^2$}}; \draw[->,red,thick] (c) to [bend left=30] (e); \node at (6,0.8) {\alert{$R^2$}}; \draw[->,green,thick] (a) to [bend left=45] (d); \node at (3,1.5) {\textcolor{green}{\bf $R^3$}}; \draw[->,green,thick] (b) to [bend left=45] (e); \node at (5,1.5) {\textcolor{green}{\bf $R^3$}}; \draw[->,yellow,thick] (a) to [bend left=60] (e); \node at (4,2.35) {\textcolor{yellow}{\bf $R^4$}}; \end{tikzpicture}} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Fecho Transitivo} \begin{block}{Teorema 6.6: Relação $S$ transitiva: $R\subseteq S\ \Tto\ R^*\subseteq S$} Dada uma relação $R$, toda relação transitiva $S$ que contém $R$ também contém o fecho transitivo $R^*$ de $R$. \end{block} \begin{block}{Prova:} \begin{itemize} \item Relações $R$ e $S$ tais que $R\subseteq S$ e $S$ é transitiva. \item \alert{Teorema 6.2:} $R\subseteq S\ \Tto\ R^n\subseteq S^n,\ \forall n\geq 1$. \item \alert{Teorema 6.4:} $S$ transitiva$\ \Tto\ S^n\subseteq S,\ \forall n\geq 1$. \item Logo $R^n\ \subseteq\ S, \forall n\geq 1$. \item $R^*\ =\ R^1\cup R^2\cup R^3\cup\ldots\ \subseteq S$. $\square$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Fechos de uma Relação - Exercício 6.22} \begin{block}{Exercício 6.22:} Encontre os fechos reflexivo, simétrico e transitivo das seguintes relações: \begin{itemize} \item $A = \{a, b, c\}$ e $R_1 = \{(a, a), (a, b), (b, c), (c, b)\}$. \item $A = \{0, 1, 2, 3\}$ e $R_2 = \{(0, 1), (1, 1), (1, 2), (2, 0), (2, 2), (3, 0)\}$. \end{itemize} \end{block} \begin{block}{Solução:} \begin{itemize} \item Reflexivo\esp{7} $\ =\ R_1\ \cup\ \{(b,b),(c,c)\}$ \item Simétrico\esp{6} $\ =\ R_1\ \cup\ \{(b,a)\}$ \item Transitivo $R_1^*\ =\ R_1\ \cup\ \{(a,c),(b,b),(c,c)\}$ \item \item \item Reflexivo\esp{7} $\ =\ R_2\ \cup\ \{(0,0),(3,3)\}$ \item Simétrico\esp{6} $\ =\ R_2\ \cup\ \{(1,0),(2,1),(0,2),(0,3)\}$ \item Transitivo $R_2^*\ =\ R_2\ \cup\ \{(0,2),(0,0),(1,0),(2,1),(3,1),(3,2)\}$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Fechos de uma Relação - Exercício 6.23} \begin{block}{Exercício 6.23:} Sejam $A = \{1, 2, 3, 4, 5\}$ e $R = \{(1, 3), (2, 4), (3, 1), (3, 5), (4, 3), (5, 1), (5, 2), (5, 4)\}$. Encontre as potências $R^2$, $R^3$, $R^4$, $R^5$, $R^6$ e o fecho transitivo $R^*$. \end{block} \begin{block}{Solução:} $R^2 = \{$(1,1),(1,5),\cor{(2,3)},(3,3),(3,1),(3,2),(3,4),\cor{(4,1),(4,5)},(5,3),(5,4)$\}$ \\ $R^3 = \{$(1,1),(1,2),(1,3),(1,4),\alert{(2,1),(2,5)},(3,1),(3,3),(3,4),(3,5),\\ \esp{10}\alert{(4,1),(4,2),(4,3),(4,4)},(5,1),(5,3),(5,5)$\}$\\ $R^4 = \{$(1,\underline{1-3-4-5}),\cor{(2,\underline{1-2-3-4})},(3,\underline{1-2-3-4-5}),\cor{(4,\underline{1-3-4-5})},(5,\underline{1-2-3-4-5})$\}$\\ $R^5 = \{$(1,\underline{1-2-3-4-5}),\alert{(2,\underline{1-3-4-5})},(3,\underline{1-2-3-4-5}),\alert{(4,\underline{1-2-3-4-5})},(5,\underline{1-2-3-4-5})$\}$\\ $R^6 = \{$(1,\underline{1-\ldots-5}),\ \cor{(2,\underline{1-\ldots-5})},\ (3,\underline{1-\ldots-5}),\ \cor{(4,\underline{1-\ldots-5})},\ (5,\underline{1-\ldots-5})$\}$\\ \begin{itemize} \item \cor{$R^* =\ R^1\cup R^2\cup R^3\cup R^4\cup R^5\cup R^6\ =\ R^6\ =\ A\times A$} \item \alert{$(1,3), (3,5), (5,2), (2,4), (4,3), (3,1) \in R$} \item \textcolor{green}{Ciclo com todos os elementos de $A\ \Tto\ R^*\ =\ A\times A$} \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Fechos de uma Relação - Exercício 6.24} \begin{block}{Exercício 6.24:} Seja $A = \{0, 1, 2, 3, 4, 5\}$. Encontre a menor relação contendo a relação $R = \{(1, 2), (1, 4), (3, 3), (4, 1)\}$ que é: \begin{itemize} \item[(a)] Simétrica e reflexiva sobre $A$. \item[(b)] Reflexiva sobre $A$ e transitiva. \item[(c)] Simétrica e transitiva. \item[(d)] Reflexiva sobre $A$, simétrica e transitiva. \end{itemize} \end{block} \begin{block}{Solução:} \begin{itemize} \item[(a)] $R\cup\{(0,0),(1,1),(2,2),(4,4),(5,5),(2,1)\}$ \item[(b)] $R\cup\{(0,0),(1,1),(2,2),(4,4),(5,5)\}$ \item[(c)] $R\cup\{(2,1),(1,1),(2,2),(4,4)\}$ \item[(d)] $R\cup\{(0,0),(1,1),(2,2),(4,4),(5,5),(2,1)\}$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Fechos de uma Relação - Exercício 6.25} \begin{block}{Exercício 6.25:} Sejam $R_1$ e $R_2$ relações sobre o conjunto $A$, tais que $R_1\subseteq R_2$. \begin{itemize} \item $S_1$ e $S_2$ fechos \alert{reflexivos} de $R_1$ e $R_2$. Prove que $S_1\subseteq S_2$. \item $S_1$ e $S_2$ fechos \alert{simétricos} de $R_1$ e $R_2$. Prove que $S_1\subseteq S_2$. \item $S_1$ e $S_2$ fechos \alert{transitivos} de $R_1$ e $R_2$. Prove que $S_1\subseteq S_2$. \end{itemize} \end{block} \begin{block}{Solução:} \begin{itemize} \item \alert{REF:} $R_1\subseteq R_2\ \Tto\ R_1\cup I_A\subseteq R_2\cup I_A\ \Tto\ S_1\subseteq S_2$.\ \ $\square$ \item \alert{SIM:} $R_1\subseteq R_2\ \Tto\ R_1^{-1}\subseteq R_2^{-1}\ \Tto\ R_1\cup R_1^{-1}\subseteq R_2\cup R_2^{-1}\ \Tto\ S'_1\subseteq S'_2$.\ \ $\square$ \item \alert{TR:} $R_1\subseteq R_2\ \Tto\ R_1^{n}\subseteq R_2^{n},\ \forall n\geq 1\ \Tto\ R_1^1\cup R_1^2\cup\ R_1^3\ldots\subseteq R_2^1\cup R_2^2\cup\ R_2^3\ldots\ \Tto\ R_1^*\subseteq R_2^*$.\ \ $\square$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Fechos de uma Relação - Exercício 6.26} \begin{block}{} Sejam $R_1$ e $R_2$ relações sobre o conjunto $A$, e $R = R_1\cup R_2$. \begin{itemize} \item $S_1$, $S_2$ e $S$ fechos \alert{reflexivos} de $R_1$, $R_2$ e $R$. Prove $S_1\cup S_2 = S$. \item $S_1$, $S_2$ e $S$ fechos \alert{simétricos} de $R_1$, $R_2$ e $R$. Prove $S_1\cup S_2 = S$. \item $S_1$, $S_2$ e $S$ fechos \alert{transitivos} de $R_1$, $R_2$ e $R$. Prove $S_1\cup S_2\subseteq S$. Encontre um exemplo em que não é igual. \end{itemize} \end{block} \begin{block}{Solução:} \begin{itemize} \item \cor{REF:} $S=(R_1\cup R_2)\cup I_A=(R_1\cup I_A)\cup(R_2\cup I_A)=S_1\cup S_2.\ \ \ \square$ \item \cor{SIM:} $S=(R_1\cup R_2)\cup(R_1\cup R_2)^{-1}=(R_1\cup R_2)\cup(R_1^{-1}\cup R_2^{-1})=S_1\cup S_2.\ \ \ \square$ \item \cor{TR:} $R_1^n\cup R_2^n\subseteq (R_1\cup R_2)^n,\ \forall n\geq 1\ \Tto\ R_1^*\cup R_2^*\subseteq (R_1\cup R_2)^*$. \item \alert{Exemplo:} $R_1=\{(1,2)\},\ R_2=\{(2,3)\}\ \Tto$ \item $\Tto\ R_1^*\cup R_2^*=\{(1,2),(2,3)\}\ne\{(1,2),(2,3),(1,3)\}=(R_1\cup R_2)^*$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Fechos de uma Relação - Exercício 6.27} \begin{block}{} Sejam $R_1$ e $R_2$ relações sobre o conjunto $A$, e $R = R_1\cap R_2$. \begin{itemize} \item $S_1$, $S_2$ e $S$ fechos \alert{reflexivos} de $R_1$, $R_2$ e $R$. Prove $S = S_1\cap S_2$. \item $S_1$, $S_2$ e $S$ fechos \alert{simétricos} de $R_1$, $R_2$ e $R$. Prove $S\subseteq S_1\cap S_2$. Mostre um exemplo em que não é igual. \item $S_1$, $S_2$ e $S$ fechos \alert{transitivos} de $R_1$, $R_2$ e $R$. Prove $S\subseteq S_1\cap S_2$. Mostre um exemplo em que não é igual. \end{itemize} \end{block} \begin{block}{Solução:} \begin{itemize} \item \cor{REF:} $S=(R_1\cap R_2)\cup I_A=(R_1\cup I_A)\cap(R_2\cup I_A)=S_1\cap S_2.\ \ \ \square$ \item \cor{SIM:} $S=(R_1\cap R_2)\cup(R_1\cap R_2)^{-1}=(R_1\cap R_2)\cup(R_1^{-1}\cap R_2^{-1})=S_1\cap S_2\cap(R_1\cup R_2^{-1})\cap(R_2\cup R_1^{-1}).\ \ \ \square$ \item $R_1=\{(1,2)\}$, $R_2=\{(2,1)\}\tto R=\emptyset, S_1=S_2=\{(1,2),(2,1)\}$ \item \cor{TR:} $(R_1\cap R_2)^n\subseteq R_1^n\cap R_2^n ,\ \forall n\geq 1\ \Tto\ (R_1\cap R_2)^*\subseteq R_1^*\cup R_2^*$. \item \alert{Exemplo:} $R_1=\{(1,2),(2,4)\}, R_2=\{(1,3),(3,4)\}\ \Tto$ \item $\Tto\ (R_1\cap R_2)^*=\emptyset\ne\{(1,4)\}= R_1^*\cap R_2^*$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Fechos de uma Relação - Exercício 6.28} \begin{block}{Exercício 6.28:} Seja $R$ a relação sobre o conjunto dos números inteiros positivos tal que $aRb$ se e somente se existe um número primo $p$ tal que $a = pb$. Qual é o fecho reflexivo de $R$? Qual é o fecho transitivo de $R$? Qual é o fecho transitivo e reflexivo? \end{block} \begin{block}{Solução:} \begin{itemize} \item \cor{REF:} $S\ =\ R\cup\ I_{\NN^*}$, onde $\NN^*=\NN-\{0\}$. Ou seja, \item $aSb$ se e só se $a=pb$ para $p$ primo ou igual a $p=1$. \item \cor{TR:} $aR^*b$ se e só se $a>b>0$ e $a$ é múltiplo de $b$. \item \cor{TR+REF:} $aR^{**}b$ se e só se $a\geq b>0$ e $a$ é múltiplo de $b$ \item \alert{Exemplo:} $300R100,100R50,50R10,10R2\tto 100R^*2$ \item \alert{Mais formalmente:} $aR^n b\ \Iff\ \exists\ primos\ p_1,\ldots,p_n:\ a=p_1p_2\ldots p_n\ b$. Pelo Teorema Fudamental da Aritmética, todo número$>1$ pode ser decomposto em um produto de números primos e por $R^*=R^1\cup R^2\cup R^3\ldots$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{\centering \huge{\alert{Capítulo 7.1\\ORDENS PARCIAIS}} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Ordens Parciais - Exercício 7.1} \begin{block}{Exercício 7.1:} Seja $R$ a relação sobre o conjunto dos números inteiros positivos ($\ZZ^+=\NN^*$) tal que $aRb$ se e somente se existe um inteiro positivo $k$ tal que $a = k\cdot b$. Prove que $R$ é uma relação de ordem. \end{block} \begin{block}{Solução:} \begin{itemize} \item \cor{REF:} $a\ =\ 1\cdot a,\ \forall a\in\ZZ^+$\ \ $\alert{\Iff}$\ \ $aRa$\ \ $\alert{\Iff}$\ \ $(a,a)\in R$.\ \ \ $\square$ \item \cor{AntiSIM:} $aRb\ \And\ a\ne b$\ \ $\alert{\Tto}$\ \ $a=kb$ para $k\geq 2$\ \ $\alert{\Tto}$\ \ $b,blue,thick] (a) to [bend left=15] (b); \draw[->,blue,thick] (b) to [bend left=15] (c); \draw[->,blue,thick] (c) to [bend left=15] (d); \draw[->,blue,thick] (d) to [bend left=15] (e); \draw[->,blue,thick] (a) to [bend left=30] (c); \draw[->,blue,thick] (b) to [bend left=30] (d); \draw[->,blue,thick] (c) to [bend left=30] (e); \draw[->,blue,thick] (a) to [bend left=45] (d); \draw[->,blue,thick] (b) to [bend left=45] (e); \draw[->,blue,thick] (a) to [bend left=60] (e); \node[vert1] (e2) at (0,0) {$1$}; \node[vert1] (d2) at (2,0) {$3$}; \node[vert1] (c2) at (4,0) {$5$}; \node[vert1] (b2) at (6,0) {$7$}; \node[vert1] (a2) at (8,0) {$9$}; \draw[->,red,thick] (a2) to [bend left=15] (b2); \draw[->,red,thick] (b2) to [bend left=15] (c2); \draw[->,red,thick] (c2) to [bend left=15] (d2); \draw[->,red,thick] (d2) to [bend left=15] (e2); \draw[->,red,thick] (a2) to [bend left=30] (c2); \draw[->,red,thick] (b2) to [bend left=30] (d2); \draw[->,red,thick] (c2) to [bend left=30] (e2); \draw[->,red,thick] (a2) to [bend left=45] (d2); \draw[->,red,thick] (b2) to [bend left=45] (e2); \draw[->,red,thick] (a2) to [bend left=60] (e2); \path[->,green,thick] (a) edge (a2) edge (b2) edge (c2) edge (d2) edge (e2) (b) edge (a2) edge (b2) edge (c2) edge (d2) edge (e2) (c) edge (a2) edge (b2) edge (c2) edge (d2) edge (e2) (d) edge (a2) edge (b2) edge (c2) edge (d2) edge (e2) (e) edge (a2) edge (b2) edge (c2) edge (d2) edge (e2); \draw[->,blue,thin] (a) to [out= 120,in= 60,looseness=7] (a); \draw[->,blue,thin] (b) to [out= 120,in= 60,looseness=7] (b); \draw[->,blue,thin] (c) to [out= 120,in= 60,looseness=7] (c); \draw[->,blue,thin] (d) to [out= 120,in= 60,looseness=7] (d); \draw[->,blue,thin] (e) to [out= 120,in= 60,looseness=7] (e); \draw[->,red ,thin] (a2) to [out=-120,in=-60,looseness=7] (a2); \draw[->,red ,thin] (b2) to [out=-120,in=-60,looseness=7] (b2); \draw[->,red ,thin] (c2) to [out=-120,in=-60,looseness=7] (c2); \draw[->,red ,thin] (d2) to [out=-120,in=-60,looseness=7] (d2); \draw[->,red ,thin] (e2) to [out=-120,in=-60,looseness=7] (e2); \end{tikzpicture}} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Ordens Parciais - Exercício 7.2} \begin{block}{Exercício 7.2:} Seja $A$ o conjunto dos inteiros de $0$ a $9$ e seja $R$ a relação sobre $A$ tal que $aRb$ se e somente se $a$ é par e $b$ é ímpar, ou ambos são pares e $a\leq b$, ou ambos são ímpares e $a\geq b$. Esta é uma relação de ordem? \end{block} \begin{block}{Solução:\ \alert{SIM}} \begin{itemize} \item \cor{REF:} $a\leq a\ \And\ a\geq a$\ \ $\alert{\Iff}$\ \ $aRa$,\ $\forall a\in\ZZ$.\ \ \ $\square$ \item \cor{AntiSIM:} \item[i] $aRb, a$\ par e $b$\ ímpar\ \ $\alert{\Tto}$\ \ $(b,a)\not\in R$\ \ \ $\square$ \item[ii] $aRb, a,b$\ pares e $ab$\ \ $\alert{\Tto}$\ \ $b\not\geq a$\ \ $\Tto$\ \ $(b,a)\not\in R$.\ \ \ $\square$ \item \cor{TR:} $aRb\ \And\ bRc$: \item $a,b,c$ pares e $a\leq b\leq c$\ \ $\alert{\Tto}$\ \ $a,c$ pares e $a\leq c$\ \ $\alert{\Tto}$\ \ $aRc$ \item $a,b$ pares, $c$ ímpar e $a\leq b$\ \ $\alert{\Tto}$\ \ $a$ par e $c$ ímpar\ \ $\alert{\Tto}$\ \ $aRc$ \item $a$ par, $b,c$ ímpares e $b\leq c$\ \ $\alert{\Tto}$\ \ $a$ par e $c$ ímpar\ \ $\alert{\Tto}$\ \ $aRc$ \item $a,b,c$ ímpares e $a\geq b\geq c$\ \ $\alert{\Tto}$\ \ $a,c$ ímpares e $a\geq c$\ \ $\alert{\Tto}$\ \ $aRc$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Ordens Parciais - Exercício 7.3} \begin{block}{Exercício 7.3:} Considere a relação $R$ sobre os pares ordenados de inteiros $\ZZ\times\ZZ$ tal que $(a,b) R (c,d)\Iff(a\leq c)\Or(b\leq d)$ para quaisquer inteiros $a$, $b$, $c$ e $d$. Esta é uma relação de ordem? \end{block} \begin{block}{Solução:\ \ \alert{NÃO}} \begin{itemize} \item \underline{Contraexemplo:} \item $a=d=1$ e $b=c=2$\ \ $\alert{\Tto}$\ \ $(1,2) R (2,1)$, pois $a\leq c$ \item $a=d=2$ e $b=c=1$\ \ $\alert{\Tto}$\ \ $(2,1) R (1,2)$, pois $b\leq d$ \item Portanto $R$ não é antissimétrica. Logo $R$ não é uma relação de ordem. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Ordens Parciais - Exercício 7.3b} \begin{block}{Exercício 7.3b:} Considere a relação $R$ sobre os pares ordenados de inteiros $\ZZ\times\ZZ$ tal que $(a,b) R (c,d)\Iff(a\leq c)\cor{\And}(b\leq d)$ para quaisquer inteiros $a$, $b$, $c$ e $d$. Esta é uma relação de ordem? \end{block} \begin{block}{Solução:\ \ \alert{SIM}} \begin{itemize} \item \cor{REF:} $a\leq a\ \And\ b\leq b$\ \ $\alert{\Tto}$\ \ $(a,b)R(a,b)$,\ $\forall a,b\in\ZZ$.\ \ \ $\square$ \item \cor{AntiSIM:} $(a,b)R(c,d)\ \And (c,d)R(a,b)$\ \ $\alert{\Tto}$\ \ $a\leq c\ \And\ b\leq d\ \And c\leq a\ \And\ d\leq b$\ \ $\alert{\Tto}$\ \ $a=c\ \And\ b=d$\ \ $\alert{\Tto}$\ \ $(a,b)=(c,d)$.\ \ \ $\square$ \item \cor{TR:} $(a,b)R(c,d)\ \And\ (c,d)R(x,y)$\ \ $\alert{\Tto}$\ \ $a\leq c\leq x\ \And\ b\leq d\leq y$\ \ $\alert{\Tto}$\ \ $a\leq x\ \And\ b\leq y$\ \ $\alert{\Tto}$\ \ $(a,b)R(x,y)$.\ \ \ $\square$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Ordens Parciais - Exercício 7.4} \begin{block}{Exercício 7.4:} Seja $R$ uma relação de ordem sobre um conjunto $B$ ($R\subseteq B\times B$). Prove que, para todo subconjunto $A$ de $B$ ($A\subseteq B$), a restrição $R'$ de $R$ a $A$ é uma relação de ordem sobre $A$. \end{block} \begin{block}{Solução:} \begin{itemize} \item \textbf{Lembrete:} $xR'y\ \ \Iff\ \ xRy\ \And\ x,y\in A$ \item \cor{REF:} $a\in A$\ \ $\alert{\Tto}$\ \ $a\in B$\ \ $\alert{\Tto}$\ \ $(a,a)\in R$\ \ $\alert{\Tto}$\ \ $(a,a)\in R'$.\ \ \ $\square$ \item \cor{AntiSIM:} $xR'y$\ \ $\alert{\Tto}$\ \ $xRy$\ \ $\alert{\Tto}$\ \ $(y,x)\not\in R$\ \ $\alert{\Tto}$\ \ $(y,x)\not\in R'$.\ \ \ $\square$ \item \cor{TR:} $xR'y\ \And\ yR'z$\ \ $\alert{\Tto}$\ \ $x,y,z\in A\ \And\ xRy\ \And\ yRz$\ \ $\alert{\Tto}$\ \ $x,z\in A\ \And\ xRz$\ \ $\alert{\Tto}$\ \ $xR'z$.\ \ \ $\square$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Ordens Parciais - Exercício 7.5} \begin{block}{Exercício 7.5:} Para quaisquer relações de ordem $R$ e $S$ sobre um conjunto $A$, a relação $R\cup S$ é sempre uma relação de ordem sobre $A$? E a relação $R\cap S$? Prove suas respostas. \end{block} \begin{block}{Solução: \alert{NÃO para $R\cup S$}} \begin{itemize} \item \underline{Contraexemplo:} $A=\{1,2,3\}$, $R=\{(1,1),(1,2),(2,2),(3,3)\}$ e $S=\{(1,1),(2,2),(2,3),(3,3)\}$\ \ $\alert{\Tto}$\ \ $R$ e $S$ são ordens parciais. \item No entanto, $\{(1,2),(2,3)\}\subseteq R\cup S$, mas $(1,3)\not\in R\cup S$. \end{itemize} \end{block} \begin{block}{Solução: \alert{SIM para $R\cap S$}} \begin{itemize} \item \cor{REF:} $(a,a)\in R\ \And\ (a,a)\in S,\ \forall a\in A$\ \ $\alert{\Tto}$\ \ $(a,a)\in R\cap S$.\ \ \ $\square$ \item \cor{AntiSIM:} $(x,y)\in R\cap S\ \And x\ne y$\ \ $\alert{\Tto}$\ \ $(y,x)\not\in R\ \And\ (y,x)\not\in S$\ \ $\alert{\Tto}$\ \ $(y,x)\not\in R\cap S$.\ \ \ $\square$ \item \cor{TR:} $(x,y)\in R\cap S\ \And\ (y,z)\in R\cap S$\ \ $\alert{\Tto}$\ \ $(x,z)\in R\ \And\ (x,z)\in S$\ \ $\alert{\Tto}$\ \ $(x,z)\in R\cap S$.\ \ \ $\square$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Ordens Parciais - Exercício 7.6} \begin{block}{Exercício 7.6:} Seja $A$ o conjunto de todos os arquivos em um sistema de arquivos e seja $R$ a relação sobre $A$ tal que $aRb$ se e somente se o arquivo $a$ contém uma cópia do conteúdo do arquivo $b$, possivelmente com informações adicionais antes do início de $b$ ou depois do fim de $b$. A relação $R$ é uma relação de ordem? \end{block} \begin{block}{Solução: \alert{SIM}} \begin{itemize} \item \cor{REF:} Arquivo $a$ contém $a$\ \ $\alert{\Tto}$\ \ $(a,a)\in R$.\ \ \ $\square$ \item \cor{AntiSIM:} $(a,b)\in R\ \And a\ne b$\ \ $\alert{\Tto}$\ \ arquivo $a$ tem cópia do arquivo $b$ e possui dados extras antes ou depois de sua cópia interna de $b$\ \ $\alert{\Tto}$\ \ $b$ não tem cópia de $a$\ \ $\alert{\Tto}$\ \ $(b,a)\not\in R$.\ \ \ $\square$ \item \cor{TR:} $(a,b)\in R\ \And\ (b,c)\in R$\ \ $\alert{\Tto}$\ \ $a$ tem cópia de $b$ e $b$ tem cópia de $c$\ \ $\alert{\Tto}$\ \ $a$ tem cópia de $c$\ \ $\alert{\Tto}$\ \ $(a,c)\in R$.\ \ \ $\square$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Ordens Parciais - Exercício 7.7} \begin{block}{Exercício 7.7:} Seja $A$ um conjunto de caixas e seja $R$ a relação sobre $A$ tal que $aRb$ se e somente se a caixa $a$ cabe dentro da caixa $b$. Prove que $R$ é uma relação de ordem estrita. \end{block} \begin{block}{Solução:} \begin{itemize} \item \cor{IRREF:} Caixa $a$ não cabe em $a$\ \ $\alert{\Tto}$\ \ $(a,a)\not\in R$.\ \ \ $\square$ \item \cor{AntiSIM:} $(a,b)\in R$\ \ $\alert{\Tto}$\ \ caixa $a$ cabe em $b$\ \ $\alert{\Tto}$\ \ caixa $b$ não cabe em $a$\ \ $\alert{\Tto}$\ \ $(b,a)\not\in R$.\ \ \ $\square$ \item \cor{TR:} $(a,b)\in R\ \And\ (b,c)\in R$\ \ $\alert{\Tto}$\ \ caixa $a$ cabe em $b$ e caixa $b$ cabe em $c$\ \ $\alert{\Tto}$\ \ caixa $a$ cabe na caixa $c$\ \ $\alert{\Tto}$\ \ $(a,c)\in R$.\ \ \ $\square$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Ordens Parciais - Exercício 7.8} \begin{block}{Exercício 7.8:} A ordem estrita sobre um conjunto de caixas definida no exercício 7.7 é uma ordem total? \end{block} \begin{block}{Solução: \alert{NÃO}} \begin{itemize} \item Podem existir duas caixas $a$ e $b$ tais que $a$ não cabe em $b$ e também $b$ não cabe em $a$. \item Por exemplo, caixas com medidas $1\times 1\times 5$ e $2\times 2\times 2$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Ordens Parciais - Exercício 7.9} \begin{block}{Exercício 7.9:} Seja $R$ uma relação de ordem \cor{total} sobre um conjunto $B$ ($R\subseteq B\times B$). Prove que, para todo subconjunto $A$ de $B$ ($A\subseteq B$), a restrição $R'$ de $R$ a $A$ também é uma relação de ordem \cor{total} sobre $A$. (Veja o exercício 7.4.) \end{block} \begin{block}{Exercício 7.4:} Seja $R$ uma relação de ordem \alert{\sout{total}} sobre um conjunto $B$ ($R\subseteq B\times B$). Prove que, para todo subconjunto $A$ de $B$ ($A\subseteq B$), a restrição $R'$ de $R$ a $A$ também é uma relação de ordem \alert{\sout{total}} sobre $A$. \end{block} \begin{block}{Solução Ex. 7.9:} \begin{itemize} \item \textbf{Lembrete:} $xR'y\ \ \Iff\ \ xRy\ \And\ x,y\in A$ \item No Exercício 7.4, provamos que $R'$ é uma relação de ordem. Falta provar que é \textbf{total}. \item $x,y\in A$ \ \ $\alert{\Tto}$\ \ $x,y\in B$\ \ $\alert{\Tto}$\ \ $xRy\ \Or\ yRx$\ \ $\alert{\Tto}$\ \ $xR'y\ \Or\ yR'x$.\ \ \ \ $\square$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ %\frametitle{Ordens Parciais - Exercício 7.10} \begin{block}{Exercício 7.10:} Seja $R$ uma relação sobre um conjunto $A$ e seja $S$ a relação complementar, $S=(A\times A)-R$. Prove ou mostre um contraexemplo: \begin{itemize} \item[(i)] $R$ é de ordem \esp{7}\ \ \textbf{se e só se}\ \ $S$ é de ordem estrita.\esp{8} (\alert{F}) \item[(ii)] $R$ é de ordem \cor{total}\ \ \textbf{se e só se}\ \ $S$ é de ordem estrita \cor{total}. (\textcolor{green}{\bf V}) \end{itemize} \end{block} -------------------------------------------------- %\begin{block}{Solução: \alert{Falso para (i)}} \begin{itemize} \item \textbf{Contraexemplo (i):} $A=\{1,2\}$, $1R1$, $2R2$, $1S2$ e $2S1$. \item $R$ é ordem, mas $S$ não é antissimétrica (não é ordem estrita) \end{itemize} %\end{block} -------------------------------------------------- %\begin{block}{Solução: \cor{Verdadeiro para (ii)}} \begin{itemize} \item \textbf{Prova (ii):} $R$ é reflexiva se e somente se $S$ é irreflexiva. \cor{Ok}. \item Suponha que $R$ é uma ordem total e $x,y,z\in A$ são distintos. \item $x,y\in A\ \Tto\ xRy\ \Or\ yRx$ (pois $R$ é \textbf{total}) \item $\Tto\ (xRy\And y\cnot{R} x)\ \Or\ (yRx\And x\cnot{R} y)$ (pois $R$ é \textbf{antissimétrica}) \item $\Tto\ (x\cnot{S} y\And ySx)\ \Or\ (y\cnot{S} x\And xSy)$ $\Tto$ $S$ é \cor{total e antissimétrica} \item $xSy \And ySz \Tto zRy \And yRx \Tto zRx \Tto xSz \Tto S$ \cor{transitiva}. \item Argumento análogo para: $S$ é de ordem estrita\ \ $\Tto$\ \ $R$ é de ordem. \end{itemize} %\end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Conjunto $A^k$ de $k$-uplas sobre um alfabeto $A$} \begin{block}{Definição $k$-upla} \begin{itemize} \item \textbf{$k$-upla}\ \ =\ \ generalização de Par Ordenado para $k$ ordenadas. \item pares (duplas $k$=2), triplas ($k$=3), quádruplas ($k$=4), quíntuplas ($k$=5), $\ldots$ \item \cor{Ex1:} Triplas pitagóricas (3,4,5),\ (5,12,13),\ (6,8,10). \item \cor{Ex2:} Pontos $(x,y,z)$ da esfera de raio 1:\ $x^2+y^2+z^2\leq 1$. \end{itemize} \end{block} \begin{block}{Definição $A^k\ =\ A\times A\times\ldots\times A$ ($k$ vezes)} Dado conjunto $A$ , definimos $A^k$ o conjunto das $k$-uplas (ordenadas) com elementos de $A$. \begin{itemize} \item \cor{Ex1:} $\RR^3$: pontos do espaço tridimensional. \item \cor{Ex2:} $\{C,K\}^5\ =\ $ conjunto dos possíveis resultados ao lançar uma moeda 5 vezes, para C (cara) e K (coroa)\ =\ \Big\{(C,C,C,C,C),\ (C,C,C,C,K),\ (C,C,C,K,C),\ (C,C,C,K,K),\ (C,C,K,C,C),\ldots\Big\}. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Conjunto $A^*$ de palavras sobre um conjunto $A$} \begin{block}{Definição $A^*$ ($A$ estrela)} Dado conjunto $A$ (alfabeto), definimos $A^*$ ($A$ estrela) como o conjunto das sequências (palavras) finitas de elementos de $A$ (a ordem importa). \begin{itemize} \item \cor{Ex1:} $A=\{a\}$,\ \ \ \ $A^*=\{\varepsilon,a,aa,aaa,aaaa,\ldots\}$. \item \cor{Ex2:} $A=\{a,b\}$, $A^*=\{\varepsilon,a,b,aa,ab,ba,bb,aaa,aab,\ldots\}$. \end{itemize} Chamaremos os elementos de $A$ de letras e os elementos de $A^*$ de palavras. O tamanho de uma palavra $u$ é o seu número de letras. A palavra vazia, denotada por $\varepsilon$ ou $()$, tem tamanho 0. \end{block} \begin{block}{Concatenação:} Dadas duas palavras $u$ e $v$, a \cor{concatenação} de $u$ e $v$, escrita $uv$ é a palavra obtida ao se escrever as letras de $u$ seguidas das letras de $v$. \begin{itemize} \item \cor{Exemplo:} Alfabeto $A=\{a,b\}$,\ $u=ab$\ e\ $v=ba$. \item $uv\ =\ abba$,\ \ $vu\ =\ baab$,\ \ $uuvv=ababbaba$ \item $baa$ é \textbf{prefixo} de $vu$;\ \ $aba$ é \textbf{sufixo} de $uuvv$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Ordem Lexicográfica $R^*$ de uma relação $R$} É uma Relação de Ordem ($R^*$) sobre o conjunto $A^*$ de palavras sobre um alfabeto $A$ (dada uma relação de ordem $R$ sobre os elementos de $A$). \textit{Não confundir com fecho transitivo} $R^*$. \textbf{Exemplo:} dicionário.\\ \begin{block}{Ordem lexicográfica $\textcolor{green}{\bf R^*}$ de uma relação $R$} Dada uma relação de ordem $\cor{R}$ sobre um conjunto $A$, seja $\textcolor{green}{\bf R^*}$ (\textcolor{green}{\bf ordem lexicográfica induzida} por $\cor{R}$) a relação sobre $A^*$ tal que $u\textcolor{green}{\bf R^*}v$ se e só se: \begin{itemize} \item[(i)] $u$ é prefixo de $v$;\ \ ou \item[(ii)] $u=wau'$\ e\ $v=wbv'$, onde $w$ é o maior prefixo comum entre $u$ e $v$, os sufixos $u',v'\in A^*$ e as letras $a,b\in A$ satisfazem $aRb$. \end{itemize} \end{block} \begin{block}{Exemplo: Dicionário} \begin{itemize} \item $A=\{a,b,c,\ldots\}$ e \cor{$R$} a relação natural das letras: $a \cor{R} b \cor{R} c \cor{R} d \cor{R}\ldots$ \item $\varepsilon$\ $\textcolor{green}{\bf R^*}$\ a\ $\textcolor{green}{\bf R^*}$\ aa\ $\textcolor{green}{\bf R^*}$\ amar\ $\textcolor{green}{\bf R^*}$\ amo\ $\textcolor{green}{\bf R^*}$\ amor\ $\textcolor{green}{\bf R^*}$\ amora\ $\textcolor{green}{\bf R^*}$\ b\ $\textcolor{green}{\bf R^*}$\ ba. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Ordem Lexicográfica $R^*$ de uma relação $R$} É uma Relação de Ordem ($R^*$) sobre o conjunto $A^*$ de palavras sobre um alfabeto $A$ (dada uma relação de ordem $R$ sobre os elementos de $A$). \textit{Não confundir com fecho transitivo} $R^*$. \textbf{Exemplo:} dicionário.\\ \begin{block}{Ordem lexicográfica $\textcolor{green}{\bf R^*}$ de uma relação $R$} Dada uma relação de ordem $\cor{R}$ sobre um conjunto $A$, seja $\textcolor{green}{\bf R^*}$ (\textcolor{green}{\bf ordem lexicográfica induzida} por $\cor{R}$) a relação sobre $A^*$ tal que: \begin{itemize} \item[(L1)] Para toda palavra $u\in A^*$: $\varepsilon\textcolor{green}{\bf R^*}u$. \item[(L2)] Para toda palavra $u\in A^*$: $u\ne\varepsilon\ \Tto\ u\cnot{\textcolor{green}{\bf R^*}} \varepsilon$. \item[(L3)] $u$ e $v$ palavras não vazias: $u \textcolor{green}{\bf R^*} v$ \cor{se e só se} $(u_1\ne v_1 \And u_1 \cor{R} v_1)\Or$ $\Or(u_1=v_1\And u' \textcolor{green}{\bf R^*} v')$, onde $u_1$ e $v_1$ são as letras iniciais de $u$ e $v$, e $u'$ e $v'$ são o que resta de $u$ e $v$ retirando-se estes elementos iniciais. \end{itemize} \end{block} \begin{block}{Exemplo: Dicionário} \begin{itemize} \item $A=\{a,b,c,\ldots\}$ e \cor{$R$} a relação natural das letras: $a \cor{R} b \cor{R} c \cor{R} d \cor{R}\ldots$ \item $\varepsilon$\ $\textcolor{green}{\bf R^*}$\ a\ $\textcolor{green}{\bf R^*}$\ aa\ $\textcolor{green}{\bf R^*}$\ amar\ $\textcolor{green}{\bf R^*}$\ amo\ $\textcolor{green}{\bf R^*}$\ amor\ $\textcolor{green}{\bf R^*}$\ amora\ $\textcolor{green}{\bf R^*}$\ b\ $\textcolor{green}{\bf R^*}$\ ba. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Ordens Parciais - Exercício 7.11} \begin{block}{Exercício 7.11:} Seja $R$ uma relação de ordem parcial sobre um conjunto $A$. Prove que a ordem lexicográfica $R^*$ induzida por $R$ é reflexiva. \end{block} \begin{block}{Prova:} \begin{itemize} \item Seja $u\in A^*$ uma palavra qualquer. Queremos provar que $uR^*u$ por indução no tamanho $n$ de $u$. \item \textbf{Caso base:} $n=0$\ $\Tto$\ $u=\varepsilon$\ $\Tto$\ $uR^*u$. (\textbf{Ok}) \item \textbf{H.I.:} Fixe $n\geq 1$ e suponha valer para toda palavra de tam $,blue,thick] (a) to [bend left=15] (b); \draw[->,blue,thick] (b) to [bend left=15] (c); \draw[->,blue,thick] (c) to [bend left=15] (d); \draw[->,blue,thick] (d) to [bend left=15] (e); \draw[->,blue,thick] (a) to [bend left=30] (c); \draw[->,blue,thick] (b) to [bend left=30] (d); \draw[->,blue,thick] (c) to [bend left=30] (e); \draw[->,blue,thick] (a) to [bend left=45] (d); \draw[->,blue,thick] (b) to [bend left=45] (e); \draw[->,blue,thick] (a) to [bend left=60] (e); \draw[->,blue,thin] (a) to [out=-30,in=30,looseness=7] (a); \draw[->,blue,thin] (b) to [out=-30,in=30,looseness=7] (b); \draw[->,blue,thin] (c) to [out=-30,in=30,looseness=7] (c); \draw[->,blue,thin] (d) to [out=-30,in=30,looseness=7] (d); \draw[->,blue,thin] (e) to [out=-30,in=30,looseness=7] (e); \end{tikzpicture}} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Mínimos e Máximos - Exercício 7.20} \begin{block}{Exercício 7.20:} Prove que todo conjunto ordenado tem no máximo um elemento mínimo e um elemento máximo. \end{block} \begin{block}{Solução:} \begin{itemize} \item Provar por contradição que não pode haver 2 mínimos. \item Seja $R$ uma relação de ordem sobre um conjunto $A$ qualquer. \item Suponha que existam dois mínimos $a$ e $b$ distintos em $A$. \item Pela definição de mínimo: $\forall x\in A:\ aRx$\ e\ $bRx$. \item Portanto $aRb$ e $bRa$. Contradição, pois $R$ é antissimétrica. \item Argumento análogo para o máximo. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Mínimos e Máximos - Exercício 7.21} \begin{block}{Exercício 7.21:} Prove que um conjunto finito $B$ não vazio \textbf{totalmente} ordenado tem exatamente um elemento mínimo e um elemento máximo. \end{block} \begin{block}{Solução: por indução} \begin{itemize} \item Seja $R$ uma relação de ordem \textbf{total} sobre o conjunto $B$. \item Vamos provar por indução no tamanho $n$ de $B$. \item \textbf{Caso base:} $n=1\ \Tto\ $o único elemento de $B$ é mínimo. (\textbf{Ok}) \item \textbf{H.I:} Fixe $n>1$ e assuma valer para todo conjunto de tamanho $<\ n$. \item \textbf{P.I:} \cor{Vamos provar que vale para $n$. Ou seja, se $B$ tem tamanho $n$, então $B$ tem elemento mínimo sob a relação $R$.} \item Seja $b\in B$. Por H.I., $B-\{b\}$ tem elemento mínimo $m$ sob $R$. \item $R$ é total\ $\Tto$\ $mRb$ ou $bRm$. Se $mRb$, então $m$ é mínimo de $B$. \item Suponha então $bRm$. Como $\forall\ x\in B-\{b\}:\ mRx$, \item então $\forall\ x\in B-\{b\}:\ bRx$ por transitividade. \item Como $bRb$ (pois $R$ é reflexiva em $B$), então $b$ é mínimo em $B$ sob $R$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Notação $a \leq_R b$ para uma relação de ordem $R$} \begin{block}{Notação $\leq_R$} Dada uma \textbf{relação de ordem parcial} $R$, existem três modos de representar pares de $R$: \begin{itemize} \item $(a,b)\ \in\ R$; ou \item $aRb$; ou \item $a\leq_R b$. \end{itemize} Muitas vezes, dizemos que $\leq_R$ é a própria relação de ordem. \end{block} \begin{block}{Exemplo:} \begin{itemize} \item Reflexiva em $A$:\ $x\leq_R x$,\ $\forall x\in A$. \item Antissimétrica:\ Se $x\leq_R y$\ e\ $x\ne y$, então $y\cnot{\leq}_Rx$. \item Antissimétrica:\ Se $x\leq_R y$\ e\ $y\leq_R x$, então $x=y$ . \item Transitiva:\ Se $x\leq_R y$ e $y\leq_R z$, então $x\leq_R z$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Notações $\leq_R$, $\geq_R$, $<_R$ e $>_R$ } \begin{itemize} \item $\leq_R$ é a própria relação de ordem $R$ \item $\geq_R$ é a relação de ordem inversa $R^{-1}$ de $R$ \item $<_R$ é a relação de ordem estrita associada a $R$ \item $>_R$ é a relação de ordem estrita associada a $R^{-1}$ \end{itemize} \begin{block}{Definições:} \begin{itemize} \item $x\geq_R y$ \textbf{se e somente se} $y\leq_R x$. \item $x<_R y$ \textbf{se e somente se} $x\leq_R y$ e $x\ne y$. \item $x>_R y$ \textbf{se e somente se} $x\geq_R y$ e $x\ne y$. \item $R$ é total \textbf{se e somente se} $x\leq_R y$ ou $x\geq_R y$, $\forall x,y$. \end{itemize} \end{block} \begin{block}{Exemplo: $R$ relação de continência $\subseteq$} \begin{itemize} \item $\leq_R$ é a própria relação de ordem $\subseteq$. \item $\geq_R$ é a relação de ordem $\supseteq$. \item $<_R$ é a relação de ordem estrita $\subsetneq$. \item $>_R$ é a relação de ordem estrita $\supsetneq$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ %\frametitle{Diagrama de Hasse - Exercício 7.23} \begin{block}{Exercício 7.23:} Encontre um conjunto $A$ e uma relação de ordem $R$ sobre $A$ tal que existe um único elemento minimal em $A$ sob $R$, mas que n˜ao é mínimo. \end{block} \begin{block}{Solução:} Conjunto $A=\ZZ\cup\{\alpha\}$. Relação $R$ sobre $A$ tal que $x\leq_R y$ \textbf{se e somente se} $x$ e $y$ estão em $\ZZ$, ou $x=\alpha$ e $y\in\ZZ$ e $y\geq 0$, ou $x=y=\alpha$. \end{block} \begin{figure}\centering\scalebox{1}{ \begin{tikzpicture}[auto] \tikzstyle{vert1}=[draw,circle,fill=blue!15,minimum size=12pt,inner sep=1pt] \tikzstyle{vert2}=[draw,circle,fill=red!25,minimum size=18pt,inner sep=1pt] \node[vert1] (a) at (0,0) {$-2$}; \node[vert1] (b) at (0,1) {$-1$}; \node[vert1] (c) at (0,2) {$0$}; \node[vert1] (d) at (0,2.8) {$1$}; \node[vert1] (e) at (0,3.6) {$2$}; \node[vert2] (f) at (1,1) {$\alpha$}; \node (g1) at (0,-0.7) {$\bullet$}; \node (g2) at (0,-0.9) {$\bullet$}; \node (g3) at (0,-1.1) {$\bullet$}; \node (h1) at (0,4.3) {$\bullet$}; \node (h2) at (0,4.5) {$\bullet$}; \node (h3) at (0,4.7) {$\bullet$}; \path[-,blue,thick] (a) edge (b) (b) edge (c) (c) edge (d) (d) edge (e) (e) edge (h1) (a) edge (g1); \path[-,red,thick] (f) edge (c); \end{tikzpicture}} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Minimais e Maximais - Exercício 7.24} \begin{block}{Exercício 7.24:} Prove que um conjunto finito ordenado \alert{não vazio} tem pelo menos um elemento minimal e um elemento maximal. \end{block} \begin{block}{Solução: por indução} \begin{itemize} \item Seja $R$ uma relação de ordem sobre um conjunto finito $B$. \item Vamos provar por indução no tamanho $n$ de $B$. \item \textbf{Caso base:} $n=1\ \Tto\ $o único elemento de $B$ é minimal e maximal. (\textbf{Ok}) \item \textbf{H.I:} Fixe $n>1$ e assuma valer para todo conjunto de tamanho $<\ n$. \item \textbf{P.I:} \cor{Vamos provar que vale para $n$. Ou seja, se $B$ tem tamanho $n$, então $B$ tem elemento minimal e maxinal sob a relação $R$.} \item Seja $b\in B$. Por H.I., $B-\{b\}$ tem minimal $m$ e maximal $M$ sob $R$. \item Por definição, $\forall x\in B-\{b\}: x\cnot{\leq}_R m$ e $M\cnot{\leq}_R x$. \item Se $b\cnot{\leq}_R m \tto$\ $m$ é minimal em $B$. Se $b\leq_R m$\ $\tto$\ $b$ é minimal em $B$. \item Se $M\cnot{\leq}_R b \tto$\ $M$ é maximal em $B$. Se $M\leq_R b$\ $\tto$\ $b$ é maximal em $B$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Minimais e Maximais - Exercício 7.25} %\begin{block}{Exercício 7.25:} Seja $A=\{3,6,9,\ldots\}$ o conjunto dos múltiplos positivos de $3$ e seja $R$ a relação sobre $A$ tal que $x\leq_R y$ se e só se todos os algarismos decimais de $x$ aparecem em $y$ na mesma sequência. Por exemplo, $262\leq_R 12682$, mas $262\cnot{\leq}_R 12268$. Ache os minimais de $A$ sob $R$. Existe algum maximal? %\end{block} \begin{block}{Solução:} \begin{itemize} \item \cor{Não há maximal.} Todo $x$ múltiplo de 3 é sequência de $10\cdot x$. \item \alert{Minimais} pertencem à $A$: múltiplos de 3. Não tem sequência múltipla de 3 em sua sequência de algarismos, além dele mesmo. \item 3,6,9,12,15,18,21,24,27,42,45,48,51,54,57,72,75,78,81,84,87 \item 111, 114, 117, 141, 144, 147, 171, 174, 177, \item 222, 225, 228, 252, 255, 258, 282, 285, 288, \item 411, 414, 417, 441, 444, 447, 471, 474, 477, \item 522, 525, 528, 552, 555, 558, 582, 585, 588, \item 711, 714, 717, 741, 744, 747, 771, 774, 777, \item 822, 825, 828, 852, 855, 858, 882, 885, 888, \item \textbf{Não há minimais com 4 algarismos ou mais}. \alert{\bf PROVE}. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Minimais e Maximais - Exercício 7.25} %\begin{block}{Exercício 7.25:} Seja $A=\{3,6,9,\ldots\}$ o conjunto dos múltiplos positivos de $3$ e seja $R$ a relação sobre $A$ tal que $x\leq_R y$ se e só se todos os algarismos decimais de $x$ aparecem em $y$ na mesma sequência. Por exemplo, $262\leq_R 12682$, mas $262\cnot{\leq}_R 12268$. Ache os minimais de $A$ sob $R$. Existe algum maximal? %\end{block} \begin{block}{Solução:} \begin{itemize} \item 1 algarismo: deve ser múltiplo de três: 3, 6 e 9. \item 2 algarismos: Não pode ter algarismo múltiplo de 3: um resto 1 e outro resto 2 na divisão por 3. \item 3 algarismos: Não pode ter algarismo múltiplo de 3, não pode ter um com resto 1 e outro resto 2 na divisão por 3: todos tem resto 1 ou resto 2. \item $\geq 4$ algarismos: terá uma sequência de tamanho 1, 2 ou 3 de um número múltiplo de 3. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Minimais e Maximais - Exercício 7.28} \begin{block}{Exercício 7.28:} Seja $A$ o conjunto das sequências de 4 bits (algarismos 0 ou 1), exceto a sequência 0000, e seja $R$ a relação de ordem parcial tal que $x\leq_R y$ se e só se cada bit de $x$ é menor ou igual ao bit correspondente de $y$. Assim, por exemplo, $0100\leq_R 1100$, mas $1001\cnot{\leq}_R 0101$. Quais são os elementos mínimos, máximos, minimais e maximais de $A$ sob $R$? \end{block} \begin{figure}\centering \includegraphics[scale=0.45]{hasse-4bits.png} %\caption{Spider operations: thin and thick spiders} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Minimais e Maximais - Exercício 7.28} \begin{block}{Exercício 7.28:} Seja $A$ o conjunto das sequências de 4 bits (algarismos 0 ou 1), \alert{exceto a sequência 0000}, e seja $R$ a relação de ordem parcial tal que $x\leq_R y$ se e só se cada bit de $x$ é menor ou igual ao bit correspondente de $y$. Assim, por exemplo, $0100\leq_R 1100$, mas $1001\cnot{\leq}_R 0101$. Quais são os elementos mínimos, máximos, minimais e maximais de $A$ sob $R$? \end{block} \begin{figure}\centering \includegraphics[scale=0.45]{hasse-4bits2.png} %\caption{Spider operations: thin and thick spiders} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{\centering \huge{\alert{Capítulo 7.2\\RELAÇÕES DE EQUIVALÊNCIA}} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Notação $x\equiv_R y$ para Relação de Equivalência $R$} \begin{block}{Notação $x\equiv_R y$ p/ Relação de Equivalência $R$} \begin{itemize} \item $x$ é equivalente a $y$ módulo $R$ \item $x\equiv_R y$\ $\Iff$\ $x\equiv y$ mod $R$\ $\Iff$\ $x R y$\ $\Iff$\ $(x,y)\in R$. \item $x\not\equiv_R y$\ $\Iff$\ $x\not\equiv y$ mod $R$\ $\Iff$\ $x\cnot{R}y$\ $\Iff$\ $(x,y)\not\in R$. \end{itemize} \end{block} \begin{block}{Contraste com ordens parciais} \begin{itemize} \item $x\leq_R y$,\ \ \ $x\geq_R y$,\ \ \ $x<_R y$,\ \ \ $x>_R y$. \end{itemize} \end{block} \begin{block}{Exemplo divisibilidade (Teoria dos Números)} \begin{itemize} \item Divisibilidade / Congruência \item $x\equiv y\ mod\ z$\ $\Iff$\ $x-y$ é múltiplo de $z$. \item $x\equiv y\ mod\ z$\ $\Iff$\ $x$ e $y$ tem o mesmo resto na divisão por $z$. \item $11\equiv 20\ mod\ 3$\ \ e\ \ $40\equiv 49\ mod\ 3$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Relações de Equivalência - Teorema 7.1} \begin{block}{Teorema 7.1:} Seja $R$ uma relação de equivalência sobre um conjunto $A$ não vazio. As seguintes afirmações são equivalentes. \begin{itemize} \item $a\equiv_ Rb\ \ \Iff\ \ [a]_R = [b]_R\ \ \Iff\ \ [a]_R\cap[b]_R\neq\emptyset$ \end{itemize} \end{block} \begin{block}{Prova :\ \ \textbf{$1\ \ \Tto\ \ 2$}} \begin{itemize} \item Suponha \alert{$a\equiv_R b$}. Logo \cor{$b\equiv_R a$}. \item $c\in[a]_R\ \TtoB{def}\ \alert{c\equiv_R a}\ \TtoB{tr}\ \alert{c\equiv_R b}\ \TtoB{def}\ c\in[b]_R$ \item Logo $[a]_R\subseteq[b]_R$. \item $c\in[b]_R\ \TtoB{def}\ \cor{c\equiv_R b}\ \TtoB{tr}\ \cor{c\equiv_R a}\ \TtoB{def}\ c\in[a]_R$ \item Logo $[b]_R\subseteq[a]_R$. \item Portanto $[a]_R=[b]_R$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Relações de Equivalência - Teorema 7.1} \begin{block}{Teorema 7.1:} Seja $R$ uma relação de equivalência sobre um conjunto $A$ não vazio. As seguintes afirmações são equivalentes. \begin{itemize} \item $a\equiv_ Rb\ \ \Iff\ \ [a]_R = [b]_R\ \ \Iff\ \ [a]_R\cap[b]_R\neq\emptyset$ \end{itemize} \end{block} \begin{block}{Prova :\ \ \textbf{$2\ \ \Tto\ \ 3$}} \begin{itemize} \item Suponha $[a]_R=[b]_R$. \item Como $(a,a)\in R$, então $a\in[a]_R$ \item Logo $[a]_R=[b]_R\ne\emptyset$. \item Portanto $[a]_R\cap[b]_R$ não é vazio. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Relações de Equivalência - Teorema 7.1} \begin{block}{Teorema 7.1:} Seja $R$ uma relação de equivalência sobre um conjunto $A$ não vazio. As seguintes afirmações são equivalentes. \begin{itemize} \item $a\equiv_ Rb\ \ \Iff\ \ [a]_R = [b]_R\ \ \Iff\ \ [a]_R\cap[b]_R\neq\emptyset$ \end{itemize} \end{block} \begin{block}{Prova :\ \ \textbf{$3\ \ \Tto\ \ 1$}} \begin{itemize} \item Suponha que $[a]_R\cap[b]_R$ não é vazio. \item Seja $c\in[a]_R\cap[b]_R$. Logo $c\equiv_R a$ e $c\equiv_R b$. \item Por simetria, $a\equiv_R c$. \item Por transitividade, $a\equiv_R b$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Relações de Equivalência - Teorema 7.2} \begin{block}{Teorema 7.2:} Seja $P$ uma partição do conjunto $A$. A relação $R$ tal que $a\equiv_R b$ se e só se $a$ e $b$ estão em uma mesma parte (bloco) de $P$ é uma relação de equivalência, e suas classes de equivalências são as partes (blocos) da partição $P$. \end{block} \begin{block}{Prova:} \begin{itemize} \item \textbf{\cor{REF:}} $a$ e $a$ pertencem ao mesmo bloco, pois são iguais. Logo $a\equiv_R a$ \item \textbf{\cor{SIM:}} $a\equiv_R b\Tto\ $ $a$ e $b$ estão no mesmo bloco\ $\Tto$\ $b\equiv_R a$. \item \textbf{\cor{TR:}} $a\equiv_R b\ \And\ b\equiv_R c\ \Tto\ $ $a$, $b$ e $c$ estão no mesmo bloco\ $\Tto$\ $a\equiv_R c$. \item Lembrar que os blocos de uma partição são disjuntos (interseção vazia). \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Relações de Equivalência - Exercício 7.29} \begin{block}{Exercício 7.29:} Seja $S=\{(x,y)\in\RR\times\RR : x−y\in\QQ\}$. Prove que $S$ é uma relação de equivalência. \end{block} \begin{block}{Solução:} \begin{itemize} \item \textbf{\cor{REF:}} $x-x=0\in\QQ\ \TtoB{def}\ (x,x)\in S$ \item \textbf{\cor{SIM:}} $(x,y)\in S\ \TtoB{def}\ x-y\in\QQ\ \Tto\ y-x\in\QQ\ \TtoB{def}\ (y,x)\in S$ \item \textbf{\cor{SIM:}} \ \ $x\equiv_S y\ \ \ \TtoB{def}\ x-y\in\QQ\ \Tto\ y-x\in\QQ\ \TtoB{def}\ \ y\equiv_S x$ \item \textbf{\cor{TR:}} $x\equiv_S y\ \And\ y\equiv_S z\ \TtoB{def}\ x-y\in\QQ\ \And\ y-z\in\QQ$ \item $\Tto\ (x-y)+(y-z)=x-z\in\QQ\ \TtoB{def}\ x\equiv_S z$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Relações de Equivalência - Exercício 7.30} \begin{block}{Exercício 7.30:} Seja $R$ a relação sobre o conjunto dos pares ordenados de inteiros positivos tal que $(a,b)R(c,d)$ se e só se $a\cdot d = b\cdot c$. (a) Prove que $R$ é uma relação de equivalência. (b) Descreva a classe de equivalência de $(1,2)$ em $R$. \end{block} \begin{block}{Solução (a):} \begin{itemize} \item \textbf{\cor{REF:}} $a\cdot b=b\cdot a\ \TtoB{def}\ (a,b)R(a,b)$ \item \textbf{\cor{SIM:}} $(a,b)R(c,d)\ \TtoB{def}\ a\cdot d = b\cdot c\ \TtoB{def}\ (c,d)R(a,b)$. \item \textbf{\cor{TR:}} $(a,b)R(c,d)\ \And\ (c,d)R(e,f)\ \TtoB{def}\ a\cdot d = b\cdot c\ \And\ c\cdot f=d\cdot e$ \item $\Tto\ a\cdot(c\cdot f)=a\cdot(d\cdot e)=(b\cdot c)\cdot e$ \item $\Tto\ a\cdot f=b\cdot e\ \TtoB{def}\ (a,b)R(e,f)$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Relações de Equivalência - Exercício 7.30} \begin{block}{Exercício 7.30:} Seja $R$ a relação sobre o conjunto de pares ordenados de $\ZZ^+$ (inteiros positivos) tal que $(a,b)R(c,d)$ se e só se $a\cdot d = b\cdot c$. (a) Prove que $R$ é uma relação de equivalência. (b) Descreva a classe de equivalência de $(1,2)$ em $R$. \end{block} \begin{block}{Solução (b):} \begin{itemize} \item $(x,y)R(1,2)\ \TtoB{def}\ 2x=y$. Portanto, \item $[(1,2)]_R\ =\ \{(x,2x)\ :\ x\in\ZZ^+\}$. \item $[(1,2)]_R\ =\ \{(1,2),\ (2,4),\ (3,6),\ (4,8)\ ,(5,10),\ \ldots\}$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Relações de Equivalência - Exercício 7.31} \begin{block}{Exercício 7.31:} Seja $R$ a relação sobre o conjunto dos pares ordenados de $\ZZ^+$ tal que $(a,b)R(c,d)$ se e sé se $a + d = b + c$. (a) Prove que $R$ é uma relação de equivalência. (b) Descreva a classe de equivalência de $(3,1)$ sob $R$. (c) Descreva as classes de equivalência de $R$. \end{block} \begin{block}{Solução (a):} \begin{itemize} \item \textbf{\cor{REF:}} $a+b=b+a\ \TtoB{def}\ (a,b)R(a,b)$ \item \textbf{\cor{SIM:}} $(a,b)R(c,d)\ \TtoB{def}\ a+d = b+c\ \TtoB{def}\ (c,d)R(a,b)$. \item \textbf{\cor{TR:}} $(a,b)R(c,d)\ \And\ (c,d)R(e,f)\ \TtoB{def}\ a+d = b+c\ \And\ c+f=d+e$ \item $\Tto\ a+(c+f)=a+(d+e)=(b+c)+e$ \item $\Tto\ a+f=b+e\ \TtoB{def}\ (a,b)R(e,f)$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Relações de Equivalência - Exercício 7.31} \begin{block}{Exercício 7.31:} Seja $R$ a relação sobre o conjunto dos pares ordenados de $\ZZ^+$ tal que $(a,b)R(c,d)$ se e sé se $a + d = b + c$. (a) Prove que $R$ é uma relação de equivalência. (b) Descreva a classe de equivalência de $(3,1)$ sob $R$. (c) Descreva as classes de equivalência de $R$. \end{block} \begin{block}{Solução (b):} \begin{itemize} \item $(x,y)R(3,1)\ \TtoB{def}\ x+1=y+3\ \Tto\ x=y+2$. Portanto, \item $[(3,1)]_R\ =\ \{(y+2,y)\ :\ y\in\ZZ^+\}$. \item $[(3,1)]_R\ =\ \{(3,1),\ (4,2),\ (5,3),\ (6,4)\ ,(7,5),\ \ldots\}$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Relações de Equivalência - Exercício 7.31} \begin{block}{Exercício 7.31:} Seja $R$ a relação sobre o conjunto dos pares ordenados de $\ZZ^+$ tal que $(a,b)R(c,d)$ se e só se $a + d = b + c$. (a) Prove que $R$ é uma relação de equivalência. (b) Descreva a classe de equivalência de $(3,1)$ sob $R$. (c) Descreva as classes de equivalência de $R$. \end{block} \begin{block}{Solução (c):} \begin{itemize} \item $x>y\ \Tto\ (x,y)R(x-y+1,1)\ \Tto\ (x,y)\ \in\ [(x-y+1,1)]_R$. \item $x,blue,thick] (a) to [bend left=15] (b); \draw[<->,blue,thick] (b) to [bend left=15] (c); \draw[<->,blue,thick] (c) to [bend left=15] (d); \draw[<->,blue,thick] (d) to [bend left=15] (e); \draw[<->,blue,thick] (a) to [bend left=30] (c); \draw[<->,blue,thick] (b) to [bend left=30] (d); \draw[<->,blue,thick] (c) to [bend left=30] (e); \draw[<->,blue,thick] (a) to [bend left=45] (d); \draw[<->,blue,thick] (b) to [bend left=45] (e); \draw[<->,blue,thick] (a) to [bend left=60] (e); \draw[->,blue,thin] (a) to [out=-30,in=30,looseness=5] (a); \draw[->,blue,thin] (b) to [out=-30,in=30,looseness=5] (b); \draw[->,blue,thin] (c) to [out=-30,in=30,looseness=5] (c); \draw[->,blue,thin] (d) to [out=-30,in=30,looseness=5] (d); \draw[->,blue,thin] (e) to [out=-30,in=30,looseness=5] (e); \node[vert1] (a) at (2,4) {$1$}; \node[vert1] (b) at (2,3) {$4$}; \node[vert1] (c) at (2,2) {$7$}; \node[vert1] (d) at (2,1) {$10$}; \node[vert1] (e) at (2,0) {$13$}; \draw[<->,green,thick] (a) to [bend left=15] (b); \draw[<->,green,thick] (b) to [bend left=15] (c); \draw[<->,green,thick] (c) to [bend left=15] (d); \draw[<->,green,thick] (d) to [bend left=15] (e); \draw[<->,green,thick] (a) to [bend left=30] (c); \draw[<->,green,thick] (b) to [bend left=30] (d); \draw[<->,green,thick] (c) to [bend left=30] (e); \draw[<->,green,thick] (a) to [bend left=45] (d); \draw[<->,green,thick] (b) to [bend left=45] (e); \draw[<->,green,thick] (a) to [bend left=60] (e); \draw[->,green,thin] (a) to [out=-30,in=30,looseness=5] (a); \draw[->,green,thin] (b) to [out=-30,in=30,looseness=5] (b); \draw[->,green,thin] (c) to [out=-30,in=30,looseness=5] (c); \draw[->,green,thin] (d) to [out=-30,in=30,looseness=5] (d); \draw[->,green,thin] (e) to [out=-30,in=30,looseness=5] (e); \node[vert1] (a) at (4,4) {$2$}; \node[vert1] (b) at (4,3) {$5$}; \node[vert1] (c) at (4,2) {$8$}; \node[vert1] (d) at (4,1) {$11$}; \node[vert1] (e) at (4,0) {$14$}; \draw[<->,red,thick] (a) to [bend left=15] (b); \draw[<->,red,thick] (b) to [bend left=15] (c); \draw[<->,red,thick] (c) to [bend left=15] (d); \draw[<->,red,thick] (d) to [bend left=15] (e); \draw[<->,red,thick] (a) to [bend left=30] (c); \draw[<->,red,thick] (b) to [bend left=30] (d); \draw[<->,red,thick] (c) to [bend left=30] (e); \draw[<->,red,thick] (a) to [bend left=45] (d); \draw[<->,red,thick] (b) to [bend left=45] (e); \draw[<->,red,thick] (a) to [bend left=60] (e); \draw[->,red,thin] (a) to [out=-30,in=30,looseness=5] (a); \draw[->,red,thin] (b) to [out=-30,in=30,looseness=5] (b); \draw[->,red,thin] (c) to [out=-30,in=30,looseness=5] (c); \draw[->,red,thin] (d) to [out=-30,in=30,looseness=5] (d); \draw[->,red,thin] (e) to [out=-30,in=30,looseness=5] (e); \end{tikzpicture}} \end{figure} 3 classes de equivalência. } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Partições e Relações de Equivalência} \begin{block}{Exemplo} Relação de congruência módulo $4$. \end{block} \begin{figure}\centering\scalebox{1}{ \begin{tikzpicture}[auto] \tikzstyle{vert1}=[draw,circle,fill=black!15,minimum size=12pt,inner sep=1pt] \node at (9.35,0) {.}; \node[vert1] (a) at (0,4) {$0$}; \node[vert1] (b) at (0,3) {$4$}; \node[vert1] (c) at (0,2) {$8$}; \node[vert1] (d) at (0,1) {$12$}; \node[vert1] (e) at (0,0) {$16$}; \draw[<->,blue,thick] (a) to [bend left=15] (b); \draw[<->,blue,thick] (b) to [bend left=15] (c); \draw[<->,blue,thick] (c) to [bend left=15] (d); \draw[<->,blue,thick] (d) to [bend left=15] (e); \draw[<->,blue,thick] (a) to [bend left=30] (c); \draw[<->,blue,thick] (b) to [bend left=30] (d); \draw[<->,blue,thick] (c) to [bend left=30] (e); \draw[<->,blue,thick] (a) to [bend left=45] (d); \draw[<->,blue,thick] (b) to [bend left=45] (e); \draw[<->,blue,thick] (a) to [bend left=60] (e); \draw[->,blue,thin] (a) to [out=-30,in=30,looseness=5] (a); \draw[->,blue,thin] (b) to [out=-30,in=30,looseness=5] (b); \draw[->,blue,thin] (c) to [out=-30,in=30,looseness=5] (c); \draw[->,blue,thin] (d) to [out=-30,in=30,looseness=5] (d); \draw[->,blue,thin] (e) to [out=-30,in=30,looseness=5] (e); \node[vert1] (a) at (2,4) {$1$}; \node[vert1] (b) at (2,3) {$5$}; \node[vert1] (c) at (2,2) {$9$}; \node[vert1] (d) at (2,1) {$13$}; \node[vert1] (e) at (2,0) {$17$}; \draw[<->,green,thick] (a) to [bend left=15] (b); \draw[<->,green,thick] (b) to [bend left=15] (c); \draw[<->,green,thick] (c) to [bend left=15] (d); \draw[<->,green,thick] (d) to [bend left=15] (e); \draw[<->,green,thick] (a) to [bend left=30] (c); \draw[<->,green,thick] (b) to [bend left=30] (d); \draw[<->,green,thick] (c) to [bend left=30] (e); \draw[<->,green,thick] (a) to [bend left=45] (d); \draw[<->,green,thick] (b) to [bend left=45] (e); \draw[<->,green,thick] (a) to [bend left=60] (e); \draw[->,green,thin] (a) to [out=-30,in=30,looseness=5] (a); \draw[->,green,thin] (b) to [out=-30,in=30,looseness=5] (b); \draw[->,green,thin] (c) to [out=-30,in=30,looseness=5] (c); \draw[->,green,thin] (d) to [out=-30,in=30,looseness=5] (d); \draw[->,green,thin] (e) to [out=-30,in=30,looseness=5] (e); \node[vert1] (a) at (4,4) {$2$}; \node[vert1] (b) at (4,3) {$6$}; \node[vert1] (c) at (4,2) {$10$}; \node[vert1] (d) at (4,1) {$14$}; \node[vert1] (e) at (4,0) {$18$}; \draw[<->,red,thick] (a) to [bend left=15] (b); \draw[<->,red,thick] (b) to [bend left=15] (c); \draw[<->,red,thick] (c) to [bend left=15] (d); \draw[<->,red,thick] (d) to [bend left=15] (e); \draw[<->,red,thick] (a) to [bend left=30] (c); \draw[<->,red,thick] (b) to [bend left=30] (d); \draw[<->,red,thick] (c) to [bend left=30] (e); \draw[<->,red,thick] (a) to [bend left=45] (d); \draw[<->,red,thick] (b) to [bend left=45] (e); \draw[<->,red,thick] (a) to [bend left=60] (e); \draw[->,red,thin] (a) to [out=-30,in=30,looseness=5] (a); \draw[->,red,thin] (b) to [out=-30,in=30,looseness=5] (b); \draw[->,red,thin] (c) to [out=-30,in=30,looseness=5] (c); \draw[->,red,thin] (d) to [out=-30,in=30,looseness=5] (d); \draw[->,red,thin] (e) to [out=-30,in=30,looseness=5] (e); \node[vert1] (a) at (6,4) {$3$}; \node[vert1] (b) at (6,3) {$7$}; \node[vert1] (c) at (6,2) {$11$}; \node[vert1] (d) at (6,1) {$15$}; \node[vert1] (e) at (6,0) {$19$}; \draw[<->,thick] (a) to [bend left=15] (b); \draw[<->,thick] (b) to [bend left=15] (c); \draw[<->,thick] (c) to [bend left=15] (d); \draw[<->,thick] (d) to [bend left=15] (e); \draw[<->,thick] (a) to [bend left=30] (c); \draw[<->,thick] (b) to [bend left=30] (d); \draw[<->,thick] (c) to [bend left=30] (e); \draw[<->,thick] (a) to [bend left=45] (d); \draw[<->,thick] (b) to [bend left=45] (e); \draw[<->,thick] (a) to [bend left=60] (e); \draw[->,thin] (a) to [out=-30,in=30,looseness=5] (a); \draw[->,thin] (b) to [out=-30,in=30,looseness=5] (b); \draw[->,thin] (c) to [out=-30,in=30,looseness=5] (c); \draw[->,thin] (d) to [out=-30,in=30,looseness=5] (d); \draw[->,thin] (e) to [out=-30,in=30,looseness=5] (e); \end{tikzpicture}} \end{figure} 4 classes de equivalência. } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Partições e Relações de Equivalência} \begin{block}{Exemplo} Relação de congruência módulo $5$. \end{block} \begin{figure}\centering\scalebox{1}{ \begin{tikzpicture}[auto] \tikzstyle{vert1}=[draw,circle,fill=black!15,minimum size=12pt,inner sep=1pt] \node at (9.35,0) {.}; \node[vert1] (a) at (0,4) {$0$}; \node[vert1] (b) at (0,3) {$5$}; \node[vert1] (c) at (0,2) {$10$}; \node[vert1] (d) at (0,1) {$15$}; \node[vert1] (e) at (0,0) {$20$}; \draw[<->,blue,thick] (a) to [bend left=15] (b); \draw[<->,blue,thick] (b) to [bend left=15] (c); \draw[<->,blue,thick] (c) to [bend left=15] (d); \draw[<->,blue,thick] (d) to [bend left=15] (e); \draw[<->,blue,thick] (a) to [bend left=30] (c); \draw[<->,blue,thick] (b) to [bend left=30] (d); \draw[<->,blue,thick] (c) to [bend left=30] (e); \draw[<->,blue,thick] (a) to [bend left=45] (d); \draw[<->,blue,thick] (b) to [bend left=45] (e); \draw[<->,blue,thick] (a) to [bend left=60] (e); \draw[->,blue,thin] (a) to [out=-30,in=30,looseness=5] (a); \draw[->,blue,thin] (b) to [out=-30,in=30,looseness=5] (b); \draw[->,blue,thin] (c) to [out=-30,in=30,looseness=5] (c); \draw[->,blue,thin] (d) to [out=-30,in=30,looseness=5] (d); \draw[->,blue,thin] (e) to [out=-30,in=30,looseness=5] (e); \node[vert1] (a) at (2,4) {$1$}; \node[vert1] (b) at (2,3) {$6$}; \node[vert1] (c) at (2,2) {$11$}; \node[vert1] (d) at (2,1) {$16$}; \node[vert1] (e) at (2,0) {$21$}; \draw[<->,green,thick] (a) to [bend left=15] (b); \draw[<->,green,thick] (b) to [bend left=15] (c); \draw[<->,green,thick] (c) to [bend left=15] (d); \draw[<->,green,thick] (d) to [bend left=15] (e); \draw[<->,green,thick] (a) to [bend left=30] (c); \draw[<->,green,thick] (b) to [bend left=30] (d); \draw[<->,green,thick] (c) to [bend left=30] (e); \draw[<->,green,thick] (a) to [bend left=45] (d); \draw[<->,green,thick] (b) to [bend left=45] (e); \draw[<->,green,thick] (a) to [bend left=60] (e); \draw[->,green,thin] (a) to [out=-30,in=30,looseness=5] (a); \draw[->,green,thin] (b) to [out=-30,in=30,looseness=5] (b); \draw[->,green,thin] (c) to [out=-30,in=30,looseness=5] (c); \draw[->,green,thin] (d) to [out=-30,in=30,looseness=5] (d); \draw[->,green,thin] (e) to [out=-30,in=30,looseness=5] (e); \node[vert1] (a) at (4,4) {$2$}; \node[vert1] (b) at (4,3) {$7$}; \node[vert1] (c) at (4,2) {$12$}; \node[vert1] (d) at (4,1) {$17$}; \node[vert1] (e) at (4,0) {$22$}; \draw[<->,red,thick] (a) to [bend left=15] (b); \draw[<->,red,thick] (b) to [bend left=15] (c); \draw[<->,red,thick] (c) to [bend left=15] (d); \draw[<->,red,thick] (d) to [bend left=15] (e); \draw[<->,red,thick] (a) to [bend left=30] (c); \draw[<->,red,thick] (b) to [bend left=30] (d); \draw[<->,red,thick] (c) to [bend left=30] (e); \draw[<->,red,thick] (a) to [bend left=45] (d); \draw[<->,red,thick] (b) to [bend left=45] (e); \draw[<->,red,thick] (a) to [bend left=60] (e); \draw[->,red,thin] (a) to [out=-30,in=30,looseness=5] (a); \draw[->,red,thin] (b) to [out=-30,in=30,looseness=5] (b); \draw[->,red,thin] (c) to [out=-30,in=30,looseness=5] (c); \draw[->,red,thin] (d) to [out=-30,in=30,looseness=5] (d); \draw[->,red,thin] (e) to [out=-30,in=30,looseness=5] (e); \node[vert1] (a) at (6,4) {$3$}; \node[vert1] (b) at (6,3) {$8$}; \node[vert1] (c) at (6,2) {$13$}; \node[vert1] (d) at (6,1) {$18$}; \node[vert1] (e) at (6,0) {$23$}; \draw[<->,thick] (a) to [bend left=15] (b); \draw[<->,thick] (b) to [bend left=15] (c); \draw[<->,thick] (c) to [bend left=15] (d); \draw[<->,thick] (d) to [bend left=15] (e); \draw[<->,thick] (a) to [bend left=30] (c); \draw[<->,thick] (b) to [bend left=30] (d); \draw[<->,thick] (c) to [bend left=30] (e); \draw[<->,thick] (a) to [bend left=45] (d); \draw[<->,thick] (b) to [bend left=45] (e); \draw[<->,thick] (a) to [bend left=60] (e); \draw[->,thin] (a) to [out=-30,in=30,looseness=5] (a); \draw[->,thin] (b) to [out=-30,in=30,looseness=5] (b); \draw[->,thin] (c) to [out=-30,in=30,looseness=5] (c); \draw[->,thin] (d) to [out=-30,in=30,looseness=5] (d); \draw[->,thin] (e) to [out=-30,in=30,looseness=5] (e); \node[vert1] (a) at (8,4) {$4$}; \node[vert1] (b) at (8,3) {$9$}; \node[vert1] (c) at (8,2) {$14$}; \node[vert1] (d) at (8,1) {$19$}; \node[vert1] (e) at (8,0) {$24$}; \draw[<->,yellow,thick] (a) to [bend left=15] (b); \draw[<->,yellow,thick] (b) to [bend left=15] (c); \draw[<->,yellow,thick] (c) to [bend left=15] (d); \draw[<->,yellow,thick] (d) to [bend left=15] (e); \draw[<->,yellow,thick] (a) to [bend left=30] (c); \draw[<->,yellow,thick] (b) to [bend left=30] (d); \draw[<->,yellow,thick] (c) to [bend left=30] (e); \draw[<->,yellow,thick] (a) to [bend left=45] (d); \draw[<->,yellow,thick] (b) to [bend left=45] (e); \draw[<->,yellow,thick] (a) to [bend left=60] (e); \draw[->,yellow,thin] (a) to [out=-30,in=30,looseness=5] (a); \draw[->,yellow,thin] (b) to [out=-30,in=30,looseness=5] (b); \draw[->,yellow,thin] (c) to [out=-30,in=30,looseness=5] (c); \draw[->,yellow,thin] (d) to [out=-30,in=30,looseness=5] (d); \draw[->,yellow,thin] (e) to [out=-30,in=30,looseness=5] (e); \end{tikzpicture}} \end{figure} 5 classes de equivalência. } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Partições e Relações de Equivalência} \corB{Exemplo (ver Ex. 7.16 de ordens}):\\ \textbf{\cor{Relação de ordem parcial}} $x\sqsubset y$ $\Iff$ $x$ é subpalavra de $y$.\\ \textbf{\alert{Relação de equivalência}}\ \ \ $x\ \#\ y$ $\Iff$ $x$ e $y$ tem o mesmo tamanho. \begin{figure}\centering\scalebox{1.0}{ \begin{tikzpicture}[auto] %\tikzstyle{vert1}=[draw,circle,fill=black!15,minimum size=12pt,inner sep=1pt] \tikzstyle{vert1}=[] \node[vert1] (a) at (0,0) {$b$}; \node[vert1] (b) at (2,0) {$a$}; \node[vert1] (c) at (4,0) {$n$}; \node[vert1] (x) at (0,1) {$ba$}; \node[vert1] (y) at (2,1) {$an$}; \node[vert1] (z) at (4,1) {$na$}; \path[-,blue,thick] (a) edge (x) (b) edge (x) edge (y) edge (z) (c) edge (y) edge (z); \node[vert1] (a) at (0,2) {$ban$}; \node[vert1] (b) at (2,2) {$ana$}; \node[vert1] (c) at (4,2) {$nan$}; \path[-,blue,thick] (a) edge (x) edge (y) (b) edge (y) edge (z) (c) edge (y) edge (z); \node[vert1] (x) at (0,3) {$bana$}; \node[vert1] (y) at (2,3) {$anan$}; \node[vert1] (z) at (4,3) {$nana$}; \path[-,blue,thick] (a) edge (x) (b) edge (x) edge (y) edge (z) (c) edge (y) edge (z); \node[vert1] (a) at (1,4) {$banan$}; \node[vert1] (b) at (3,4) {$anana$}; \path[-,blue,thick] (a) edge (x) edge (y) (b) edge (y) edge (z); \node[vert1] (x) at (2,5) {$banana$}; \path[-,blue,thick] (x) edge (a) edge (b); \node[vert1] (a) at (6+0,0) {$b$}; \node[vert1] (b) at (6+2,0) {$a$}; \node[vert1] (c) at (6+4,0) {$n$}; \draw[<->,red,thick] (a) to [bend left=15] (b); \draw[<->,red,thick] (b) to [bend left=15] (c); \draw[<->,red,thick] (a) to [bend left=25] (c); \draw[->,red,thin] (a) to [out=60,in=120,looseness=5] (a); \draw[->,red,thin] (b) to [out=60,in=120,looseness=5] (b); \draw[->,red,thin] (c) to [out=60,in=120,looseness=5] (c); \node[vert1] (a) at (6+0,1) {$ba$}; \node[vert1] (b) at (6+2,1) {$an$}; \node[vert1] (c) at (6+4,1) {$na$}; \draw[<->,red,thick] (a) to [bend left=15] (b); \draw[<->,red,thick] (b) to [bend left=15] (c); \draw[<->,red,thick] (a) to [bend left=25] (c); \draw[->,red,thin] (a) to [out=60,in=120,looseness=5] (a); \draw[->,red,thin] (b) to [out=60,in=120,looseness=5] (b); \draw[->,red,thin] (c) to [out=60,in=120,looseness=5] (c); \node[vert1] (a) at (6+0,2) {$ban$}; \node[vert1] (b) at (6+2,2) {$ana$}; \node[vert1] (c) at (6+4,2) {$nan$}; \draw[<->,red,thick] (a) to [bend left=15] (b); \draw[<->,red,thick] (b) to [bend left=15] (c); \draw[<->,red,thick] (a) to [bend left=25] (c); \draw[->,red,thin] (a) to [out=60,in=120,looseness=5] (a); \draw[->,red,thin] (b) to [out=60,in=120,looseness=5] (b); \draw[->,red,thin] (c) to [out=60,in=120,looseness=5] (c); \node[vert1] (a) at (6+0,3) {$bana$}; \node[vert1] (b) at (6+2,3) {$anan$}; \node[vert1] (c) at (6+4,3) {$nana$}; \draw[<->,red,thick] (a) to [bend left=15] (b); \draw[<->,red,thick] (b) to [bend left=15] (c); \draw[<->,red,thick] (a) to [bend left=25] (c); \draw[->,red,thin] (a) to [out=60,in=120,looseness=5] (a); \draw[->,red,thin] (b) to [out=60,in=120,looseness=5] (b); \draw[->,red,thin] (c) to [out=60,in=120,looseness=5] (c); \node[vert1] (a) at (6+1,4) {$banan$}; \node[vert1] (b) at (6+3,4) {$anana$}; \draw[<->,red,thick] (a) to [bend left=15] (b); \draw[->,red,thin] (a) to [out=60,in=120,looseness=5] (a); \draw[->,red,thin] (b) to [out=60,in=120,looseness=5] (b); \node[vert1] (a) at (6+2,5) {$banana$}; \draw[->,red,thin] (a) to [out=60,in=120,looseness=5] (a); \end{tikzpicture}} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Partições e Relações de Equivalência} \corB{Exemplo (ver Ex. 7.16 de ordens}):\\ \textbf{\cor{Relação de ordem parcial}} $x\sqsubset y$ $\Iff$ $x$ é subpalavra de $y$.\\ \textbf{\alert{Relação de equivalência}}\ \ \ $x\ \#\ y$ $\Iff$ $x$ e $y$ tem o mesmo tamanho. \begin{figure}\centering\scalebox{1.0}{ \begin{tikzpicture}[auto] %\tikzstyle{vert1}=[draw,circle,fill=black!15,minimum size=12pt,inner sep=1pt] \tikzstyle{vert1}=[] \node[vert1] (a) at (0.0,0) {$b$}; \node[vert1] (b) at (1.5,0) {$o$}; \node[vert1] (c) at (3.0,0) {$c$}; \node[vert1] (d) at (4.5,0) {$a$}; \node[vert1] (w) at (1.5,1) {$bo$}; \node[vert1] (x) at (0.0,1) {$ob$}; \node[vert1] (y) at (3.0,1) {$oc$}; \node[vert1] (z) at (4.5,1) {$ca$}; \path[-,blue,thick] (a) edge (w) edge (x) (b) edge (w) edge (x) edge (y) (c) edge (y) edge (z) (d) edge (z); \node[vert1] (a) at (0.0,2) {$bob$}; \node[vert1] (b) at (1.5,2) {$obo$}; \node[vert1] (c) at (3.0,2) {$boc$}; \node[vert1] (d) at (4.5,2) {$oca$}; \path[-,blue,thick] (a) edge (w) edge (x) (b) edge (w) edge (x) (c) edge (w) edge (y) (d) edge (y) edge (z); \node[vert1] (x) at (0.5,3) {$bobo$}; \node[vert1] (y) at (2.25,3){$oboc$}; \node[vert1] (z) at (4.0,3) {$boca$}; \path[-,blue,thick] (a) edge (x) (b) edge (x) edge (y) (c) edge (y) edge (z) (d) edge (z); \node[vert1] (a) at (1.2,4) {$boboc$}; \node[vert1] (b) at (3.3,4) {$oboca$}; \path[-,blue,thick] (a) edge (x) edge (y) (b) edge (y) edge (z); \node[vert1] (x) at (2.25,5) {$boboca$}; \path[-,blue,thick] (x) edge (a) edge (b); \node[vert1] (a) at (6+0.0,0) {$b$}; \node[vert1] (b) at (6+1.5,0) {$o$}; \node[vert1] (c) at (6+3.0,0) {$c$}; \node[vert1] (d) at (6+4.5,0) {$a$}; \draw[<->,red,thick] (a) to [bend left=10] (b); \draw[<->,red,thick] (b) to [bend left=10] (c); \draw[<->,red,thick] (c) to [bend left=10] (d); \draw[<->,red,thick] (a) to [bend left=25] (c); \draw[<->,red,thick] (b) to [bend left=25] (d); \draw[<->,red,thick] (a) to [bend left=30] (d); \draw[->,red,thin] (a) to [out=60,in=120,looseness=5] (a); \draw[->,red,thin] (b) to [out=60,in=120,looseness=5] (b); \draw[->,red,thin] (c) to [out=60,in=120,looseness=5] (c); \draw[->,red,thin] (d) to [out=60,in=120,looseness=5] (d); \node[vert1] (a) at (6+0.0,1) {$bo$}; \node[vert1] (b) at (6+1.5,1) {$ob$}; \node[vert1] (c) at (6+3.0,1) {$oc$}; \node[vert1] (d) at (6+4.5,1) {$ca$}; \draw[<->,red,thick] (a) to [bend left=10] (b); \draw[<->,red,thick] (b) to [bend left=10] (c); \draw[<->,red,thick] (c) to [bend left=10] (d); \draw[<->,red,thick] (a) to [bend left=25] (c); \draw[<->,red,thick] (b) to [bend left=25] (d); \draw[<->,red,thick] (a) to [bend left=30] (d); \draw[->,red,thin] (a) to [out=60,in=120,looseness=5] (a); \draw[->,red,thin] (b) to [out=60,in=120,looseness=5] (b); \draw[->,red,thin] (c) to [out=60,in=120,looseness=5] (c); \draw[->,red,thin] (d) to [out=60,in=120,looseness=5] (d); \node[vert1] (a) at (6+0.0,2) {$bob$}; \node[vert1] (b) at (6+1.5,2) {$obo$}; \node[vert1] (c) at (6+3.0,2) {$boc$}; \node[vert1] (d) at (6+4.5,2) {$oca$}; \draw[<->,red,thick] (a) to [bend left=10] (b); \draw[<->,red,thick] (b) to [bend left=10] (c); \draw[<->,red,thick] (c) to [bend left=10] (d); \draw[<->,red,thick] (a) to [bend left=25] (c); \draw[<->,red,thick] (b) to [bend left=25] (d); \draw[<->,red,thick] (a) to [bend left=30] (d); \draw[->,red,thin] (a) to [out=60,in=120,looseness=5] (a); \draw[->,red,thin] (b) to [out=60,in=120,looseness=5] (b); \draw[->,red,thin] (c) to [out=60,in=120,looseness=5] (c); \draw[->,red,thin] (d) to [out=60,in=120,looseness=5] (d); \node[vert1] (a) at (6+0.0,3) {$bobo$}; \node[vert1] (b) at (6+2.25,3){$oboc$}; \node[vert1] (c) at (6+4.5,3) {$boca$}; \draw[<->,red,thick] (a) to [bend left=15] (b); \draw[<->,red,thick] (b) to [bend left=15] (c); \draw[<->,red,thick] (a) to [bend left=25] (c); \draw[->,red,thin] (a) to [out=60,in=120,looseness=5] (a); \draw[->,red,thin] (b) to [out=60,in=120,looseness=5] (b); \draw[->,red,thin] (c) to [out=60,in=120,looseness=5] (c); \node[vert1] (a) at (6+1.0,4) {$boboc$}; \node[vert1] (b) at (6+3.5,4) {$oboca$}; \draw[<->,red,thick] (a) to [bend left=20] (b); \draw[->,red,thin] (a) to [out=60,in=120,looseness=5] (a); \draw[->,red,thin] (b) to [out=60,in=120,looseness=5] (b); \node[vert1] (a) at (6+2.25,5) {$boboca$}; \draw[->,red,thin] (a) to [out=60,in=120,looseness=5] (a); \end{tikzpicture}} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{\centering \huge{\alert{Capítulo 8\\FUNÇÕES}} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{FUNÇÕES (Capítulo 8)} \begin{block}{Definição de Função} Dizemos que uma relação $f$ é uma \textbf{função} se, para todo $a\in Dom(f)$, existe exatamente um $b$ tal que $(a,b)\in f$ (ou $a\ f\ b$). Nesse caso, dizemos que $f(a)=b$. Ver exemplos do livro. \end{block} \vspace{1cm} \begin{block}{Observação: Funções são Relações} Toda função é uma relação. Então todos os conceitos de relações, continuam a existir para funções. \begin{itemize} \item Domínio $Dom(f)$ e Imagem $Img(f)$ \item Relação Composta $g\circ f$ de $f$ com $g$ (veremos que também é Função) \item Relação Inversa $f^{-1}$ de $f$ (veremos que nem sempre é Função) \item Restrição de uma Relação a subconjuntos do Domínio e da Imagem \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{FUNÇÕES - Domínio, Imagem e ContraDomínio} \begin{block}{Domínio e Imagem} \begin{itemize} \item $Dom(f)\ =\ \{a\ :\ \exists b,\ f(a)=b\}$ \item $Img(f)\ \ =\ \{b\ :\ \exists a,\ f(a)=b\}$ \end{itemize} \end{block} \begin{block}{Notação $f:A\to B$ e ContraDomínio} Escrevemos \cor{$f:A\to B$} quando \cor{$Dom(f)=A$}\ \ e\ \ \cor{$Img(f)\subseteq B$}.\\ Nessa notação, dizemos que $B$ é o \textbf{ContraDomínio} de $f$.\\ \cor{ContraDomínio} \alert{só faz sentido} na notação $f:A\to B$. \end{block} \begin{block}{Relação Inversa de uma função $f$} \begin{itemize} \item $f^{-1}\ =\ \Big\{\ (f(x),x)\ :\ x\in Dom(f)\ \Big\}$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{FUNÇÕES - Inversa - Exercício 8.2} \begin{block}{Exercício 8.2} $f:\RR\to\RR$. Determine se a inversa é uma função. (a) $f(x) = x^3$. (b) $f(x)=e^x$. (c) $f(x)=sen(x)$. (d) $f(x) = x^5 + x$. (e) $f(x) = x^5 − x$. \end{block} \begin{block}{Solução:} (a) $f^{-1}(x)\ =\ x^{1/3}$. SIM é função.\\ (b) $f^{-1}(x)\ =\ \ell n(x)$. SIM é função.\\ (c) $f^{-1}(x)\ =\ arcsen(x)$. NÃO é função, pois $f(2\pi)=f(0)=0$\\ (d) $f^{-1}(x)$ SIM é função, pois $f'(x)=5x^4+1>0\ \Tto\ f$ é estritamente crescente.\\ (e) $f^{-1}(x)$ NÃO é função, pois $f(0)=f(1)=0$\\ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{FUNÇÕES - Imagem e Imagem Reversa de conjunto} \begin{block}{$f(A)\ =\ \{f(x):\ x\in A\cap Dom(f)\}$} \begin{itemize} \item $x\in A\ \tto\ f(x)\in f(A)$ \item $f(x)\in f(A)\ \cnot{\tto}\ x\in A$\ \ \ (contraexemplo: $f(x)=7, \forall x\in\ZZ$) \end{itemize} \end{block} \begin{block}{$f^{-1}(U)\ =\ \{x\in Dom(f):\ f(x)\in U\}$} \begin{itemize} \item $f(x)\in U\ \cor{\Iff}\ x\in f^{-1}(U)$ \item $f(f^{-1}(U)) = \{f(x): x\in f^{-1}(U)\} = \{f(x): f(x)\in U\} = U\cap Img(f)$ \end{itemize} \end{block} \begin{block}{Conclusões para $U\subseteq Img(f)$:} \begin{itemize} \item $f(x)\in U\ \cor{\Iff}\ x\in f^{-1}(U)$ \item $x\in A\ \cor{\Tto}\ f(x)\in f(A)\ \cor{\Iff}\ x\in f^{-1}(f(A))$ \item $f(x)\in U\ \cor{\Iff}\ x\in f^{-1}(U)\ \cor{\Iff}\ f(x)\in f(f^{-1}(U))$ \item \alert{Conclusões:} \cor{$f^{-1}(f(A))\supseteq A$}\ \ \ e\ \ \ \cor{$f(f^{-1}(U))=U$} \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{FUNÇÕES - Inversa - Exercício 8.3} %\begin{block}{Exercício 8.3} Dada uma função $f$, subconjuntos $A,B\subseteq Dom(f)$ e $U,V\subseteq Img(f)$, prove ou disprove:\esp{29} \cor{(a)} $f(A\cup B)=f(A)\cup f(B)$.\\ \cor{(b)} $f(A-B)=f(A)-f(B)$.\esp{12} \cor{(c)} $B\subseteq A\ \Iff\ f(B)\subseteq f(A)$.\\ \cor{(d)} $f^{-1}(U\cap V)=f^{−1}(U)\cap f^{−1}(V)$.\\ \cor{(e)} $f^{−1}(U\cup V)=f^{−1}(U)\cup f^{−1}(V)$.%\\ %\cor{(f)} $f^{−1}(U-V)=f^{ −1}(U)-f^{−1}(V)$.\\ %\cor{(g)} $U\subseteq V\ \Iff\ f^{−1}(U)\subseteq f^{−1}(V)$.\\ %\cor{(h)} $f^{−1}(f(A)) = A$.\esp{28} %\cor{(i)} $f(f^{−1}(U)) = U$. %\end{block} \begin{block}{Solução:} \corB{(a) SIM:} $y\in f(A\cup B)\Iff \exists x\in A\cup B: f(x)=y\ \Iff$\\ $\Iff y\in f(A)\ \Or\ y\in f(B)\ \Iff y\in f(A)\cup f(B)$\\ \alert{(b) NÃO.} ContraEx: $f(1)$=$f(2)$=$3$. $A$=$\{1\}$, $B$=$\{2\}$, $f(A)$=$f(B)$=$\{3\}$.\\ \corB{(c) SIM p/ ida ($\tto$):} $B\subseteq A\ \Tto\ (\forall x: x\in B\to x\in A)\ \Tto$\\ $\Tto (\forall x: f(x)\in f(B)\to f(x)\in f(A))\ \Tto\ f(B)\subseteq f(A)$.\\ \alert{(c) NÃO p/ volta ($\Leftarrow$):} ContraEx: $f(x)=0, \forall x\in\ZZ$, $A$=$\ZZ^-$, $B$=$\ZZ^+$.\\ \corB{(d) SIM.} $x\in f^{-1}(U\cap V)\iff f(x)\in U\cap V\iff f(x)\in U\ \cor{\And}\ f(x)\in V\iff$\\ $\iff x\in f^{-1}(U)\ \cor{\And}\ x\in f^{-1}(V)\Iff x\in f^{-1}(U)\cap f^{-1}(V)$.\\ \corB{(e) SIM.} $x\in f^{-1}(U\cup V)\iff f(x)\in U\cup V\iff f(x)\in U\ \cor{\Or}\ f(x)\in V\iff$\\ $\iff x\in f^{-1}(U)\ \cor{\Or}\ x\in f^{-1}(V)\Iff x\in f^{-1}(U)\cup f^{-1}(V)$. \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{FUNÇÕES - Inversa - Exercício 8.3} %\begin{block}{Exercício 8.3} Dada uma função $f$, subconjuntos $A,B\subseteq Dom(f)$ e $U,V\subseteq Img(f)$, prove ou disprove:\esp{15}\cor{(f)} $f^{−1}(U-V)=f^{ −1}(U)-f^{−1}(V)$.\\ \cor{(g)} $U\subseteq V\ \Iff\ f^{−1}(U)\subseteq f^{−1}(V)$.\\ \cor{(h)} $f^{−1}(f(A)) = A$.\esp{15} \cor{(i)} $f(f^{−1}(U)) = U$. %\end{block} \begin{block}{Solução:} \corB{(f) SIM.} $x\in f^{-1}(U-V)\iff f(x)\in U-V\iff f(x)\in U\ \cor{\And}\ f(x)\not\in V\iff$\\ $\Iff x\in f^{-1}(U)\ \cor{\And}\ x\not\in f^{-1}(V)\Iff x\in f^{-1}(U)-f^{-1}(V)$.\\ \corB{(g) SIM:}\ \ \ $U\subseteq V\ \Iff\ (\forall y: y\in U\to y\in V)\ \iff$\\ $\iff(\forall x: f(x)\in U\to f(x)\in V) \iff (\forall x: x\in f^{-1}(U)\to x\in f^{-1}(V))\iff$\\ $\iff f^{-1}(U)\subseteq f^{-1}(V)$\\ \alert{(h) NÃO:} ContraEx: $f(x)$=$7, \forall x\in\ZZ$. $A$=$\{0\}$, $f(A)$=$\{7\}$, $f^{-1}(\{7\})$=$\ZZ$.\\ \cor{(h) $f^{−1}(f(A)) \supseteq A$}. Já visto.\\ \corB{(i) SIM:} Já visto. \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\frame{ %\frametitle{FUNÇÕES - $f(A)$ e $f^{-1}(U)$} %\begin{figure}[ht] %\centering %\begin{tikzpicture}[scale=1] %\draw (0,0) ellipse (0.9cm and 1.5cm); %\draw (0,0.5) ellipse (0.3cm and 0.4cm); %\draw (0,-0.5) ellipse (0.3cm and 0.4cm); % %\draw (3,0) ellipse (0.9cm and 1.5cm); %\draw (3,0.5) ellipse (0.3cm and 0.4cm); %\draw (3,-0.5) ellipse (0.3cm and 0.4cm); %\end{tikzpicture} %\end{figure} %} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{FUNÇÕES - Composição de funções} Funções $f$ e $g$ tais que $Im(f)\subseteq Dom(g)$. \begin{block}{$g\circ f$: relação composta de $f$ com $g$ é função} \begin{itemize} \item $(x,z)\in g\circ f\ \cor{\Tto}\ \exists y: (x,y)\in f\And(y,z)\in g\ \cor{\Tto}$ \item $\cor{\Tto}\ y=f(x)\And z=g(y)\ \cor{\Tto}\ z=g(f(x))$ \item $g\circ f(x)\ =\ g(f(x))$ é apenas um valor: $g\circ f$ é função. \end{itemize} \end{block} \begin{figure}\centering \includegraphics[scale=0.3]{composta.jpg} \end{figure} \begin{itemize} \item $Dom(g\circ f)\ =\ Dom(f)$. \item $Im(g\circ f)\subseteq Im(g)$. \item Se $f:A\to B$ e $g:B\to C$, então $g\circ f:A\to C$. \end{itemize} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{FUNÇÕES - Injetora, Sobrejetora, Bijetora} \begin{block}{$f$ é Injetora} Uma função $f$ é \cor{Injetora} se e só se: \begin{itemize} \item $f(x_1)=f(x_2)\ \Tto\ x_1=x_2$ para todo $x_1,x_2\in Dom(f)$; ou seja, \item $\forall y\in Im(f):\exists! x\in Dom(f), f(x)=y$; ou seja, \item Para todo elemento $y$ da Imagem de $f$, existe exatamente um elemento $x$ do Domínio de $f$ tal que $f(x)=y$; ou seja, \item $x_1\ne x_2\ \Tto\ f(x_1)\ne f(x_2)$ para todo $x_1,x_2\in Dom(f)$. \end{itemize} \end{block} \vspace{0.5cm} \begin{block}{$f:A\to B$ é Sobrejetora} Uma função $f:A\to B$ é \cor{Sobrejetora} se e só se $Im(f)=B$. Ou seja, $\forall y\in B: \exists x\in A, f(x)=y$. \end{block} \vspace{0.5cm} \begin{block}{$f:A\to B$ é Bijetora} Uma função $f:A\to B$ é \cor{Bijetora} se é injetora e sobrejetora. \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{FUNÇÕES - Tipos de Funções - Exercício 8.6/8.10} \begin{block}{Exercício 8.6/8.10} Sejam $f:A\to B$ e $g:B\to C$. Prove que se $f$ e $g$ são injetoras então $g\circ f$ é injetora. \end{block} \begin{block}{Solução:} \begin{itemize} \item $g(f(x_1))=g(f(x_2))\TtoB{g.inj} f(x_1)=f(x_2)\TtoB{f.inj} x_1=x_2$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{FUNÇÕES - Tipos de Funções - Exercício 8.7} \begin{block}{Exercício 8.7} Prove que uma função $f$ tem função inversa $f^{-1}$ se e só se $f$ é injetora. \end{block} \begin{block}{Solução:} \begin{itemize} \item Seja $A=Dom(f)=Img(f^{-1})$ e $B=Im(f)=Dom(f^{-1})$. \item $f^{-1}$ é função $\IffB{def} \forall b\in B:\exists! a, (b,a)\in f^{-1}\iff$. \item $\iff \forall b\in B:\exists! a, (a,b)\in f\iff$ \item $\iff \forall b\in B:\exists! a,\ f(a)=b\iff$ \item $\iff f$ é injetora. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{FUNÇÕES - Tipos de Funções - Exercício 8.8} \begin{block}{Exercício 8.8} Sejam $f:A\to C$ e $g:B\to D$ duas funções injetoras. Considere a função $h:A\times B\to C\times D$ tal que $h(a,b)=(f(a),g(b))$. Prove que $h$ é uma função injetora. \end{block} \begin{block}{Solução:} \begin{itemize} \item $h(a,b)=h(x,y)\ \cor{\Tto}\ (f(a),g(b))=(f(x),g(y))\ \cor{\Tto}$ \item $\cor{\Tto}\ f(a)=f(x)\And g(b)=g(y)\ \cor{\TtoB{f,g\ inj.}}$ \item $\cor{\TtoB{f,g\ inj.}}\ (a=x)\And(b=y)\cor{\Tto} (a,b)=(x,y)$. \item Como vale para quaisquer pares $(a,b)$ e $(x,y)$, então $h$ é injetora. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{FUNÇÕES - Tipos de Funções - Exercício 8.9} %\begin{block}{Exercício 8.3} Seja $f$ uma função e sejam $A,B\subseteq Dom(f)$. Prove que\\ \textbf{(a)} $f(A\cap B)\subseteq f(A)\cap f(B)$. Mais ainda, prove que\\ \textbf{(b)} se $f$ é injetora, então $f(A\cap B)=f(A)\cap f(B)$. Prove também que\\ \textbf{(c)} se $f$ é injetora, então $f(B)\subseteq f(A)$ se e só se $B\subseteq A$. %\end{block} \begin{block}{Solução:} \begin{itemize} \item \textbf{(a)} $y\in f(A\cap B)\corB{\Iff}\exists x\in A\cap B: f(x)=y\ \cor{\Tto}$ \item $\cor{\tto}(\exists x\in A: f(x)=y)\And(\exists x'\in B: f(x')=y)\ \corB{\iff} y\in f(A)\cap f(B)$. \item Contraexemplo p/ =: $f(1)=f(2)=3$, $A=\{1\}$, $B=\{2\}$. $f(A\cap B)=\emptyset$, $f(A)\cap f(B)=\{3\}$. \item \textbf{(b)} $y\in f(A\cap B)\corB{\Iff}\exists x\in A\cap B: f(x)=y\ \corB{\Iff}$ \item $\corB{\iff}(\exists x\in A: f(x)=y)\And(\exists x'\in B: f(x')=y)\ \corB{\iff} y\in f(A)\cap f(B)$. \item \textbf{(c)} $B\subseteq A\ \corB{\Iff}\ (\forall x: x\in B\to x\in A)\ \corB{\IffB{f\ inj.}}$ \item $\corB{\IffB{f\ inj.}} (\forall x: f(x)\in f(B)\to f(x)\in f(A))\ \corB{\Iff}\ f(B)\subseteq f(A)$. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{FUNÇÕES - Tipos de Funções - Exercício 8.11} \begin{block}{Exercício 8.11} Seja $R$ uma relação de $A$ para $B$. Escreva expressões lógicas formais (sem palavras, apenas variáveis e símbolos), com todos os quantificadores necessários, que expresse as afirmações: (a) ``A relação $R$ é transitiva''. (b) ``A relação $R$ é uma função injetora''. \end{block} \begin{block}{Solução:} \begin{itemize} \item (a) $\forall x,y,z:\ ((x,y)\in R\ \And\ (y,z)\in R)\ \longrightarrow\ (x,z)\in R$ \item (a) $\forall x,y,z:\ (xRy\ \And\ yRz)\ \longrightarrow\ xRz$ \item (b) $\forall x_1,x_2,y_1,y_2:\ ((x_1Ry_1\And x_1Ry_2)\ \longrightarrow y_1=y_2)\ \And$\item \esp{25}$\And\ ((x_1Ry_1\And x_2Ry_1)\ \longrightarrow x_1=x_2)$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{} \begin{block}{FUNÇÕES - Exercício Lista 2} Para $n\geq 3$, considere $n$ funções $f_1,\ldots,f_n$ tais que $Img(f_k)\subseteq Dom(f_{k+1})$ para $k\in\{1,\ldots,n-1\}$. Prove por indução que: \[ f_n\circ(f_{n-1}\circ(\ldots\circ(f_3\circ(f_2\circ f_1))\ldots))\ \ =\ \ ((\ldots((f_n\circ f_{n-1})\circ f_{n-2})\circ\ldots)\circ f_2)\circ f_1. \] \end{block} \begin{block}{Solução: Indução forte} \begin{itemize} \item \alert{Caso base (n=3):} Queremos provar que $f_3\circ(f_2\circ f_1)=(f_3\circ f_2)\circ f_1$. \item Seja $x\in Dom(f_1)$ e sejam $y=f_1(x)$, $z=f_2(y)$ e $w=f_3(z)$. \item $f_3\circ (f_2\circ f_1)(x)=f_3(f_2\circ f_1(x)))=f_3(f_2(f_1(x)))=f_3(f_2(y)=f_3(z)=w$. \item $((f_3\circ f_2)\circ f_1)(x)=(f_3\circ f_2)(f_1(x))=(f_3\circ f_2)(y)=f_3(f_2(y))=w$. \item \alert{Hipótese da Indução:} Fixe $n>3$ e suponha valer para qualquer número $ 1$.\\ \alert{Progressão Geométrica} (P.G.): \cor{$a_{n}=a_{n-1}\cdot q$},\ \ \ \ para $n> 1$. \end{block} \begin{block}{Exemplos de P.A. e P.G.} \cor{P.A.} $(a_n)_{n\in\NN^*}$ com \alert{razão $r=2$} e primeiro termo \alert{$a_1=0$}.\\ $(a_n)\ =\ (0,2,4,6,8,10,12,\ldots)$\ \ \ \ -\ \ \ \cor{naturais pares}\\ \cor{P.A.} $(a_n)_{n\in\NN^*}$ com \alert{razão $r=2$} e primeiro termo \alert{$a_1=1$}.\\ $(a_n)\ =\ (1,3,5,7,9,11,13,\ldots)$\ \ \ \ -\ \ \ \cor{naturais ímpares}\\ \cor{P.G.} $(a_n)_{n\in\NN^*}$ com \alert{quociente $q=2$} e primeiro termo \alert{$a_1=1$}.\\ $(a_n)\ =\ (1,2,4,8,16,32,64,\ldots)$\ \ \ \ -\ \ \ \cor{potências de 2}\\ \cor{P.G.} $(a_n)_{n\in\NN^*}$ com \alert{quociente $q=3$} e primeiro termo \alert{$a_1=1$}.\\ $(a_n)\ =\ (1,3,9,27,81,243,279,\ldots)$\ \ \ \ -\ \ \ \cor{potências de 3}\\ \cor{P.A.\ /\ P.G.} $(a_n)_{n\in\NN^*}$ com \alert{razão $r=0$ / quociente $q=1$}.\\ $(a_n)\ =\ (a_1,a_1,a_1,a_1,a_1,a_1,a_1,\ldots)$\ \ \ \ -\ \ \ \cor{sequência constante}\\ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Sequências Recorrentes - Capítulo 10} \begin{block}{Sequência $(a_n)_{n\in\NN}$} Uma sequência $(a_n)_{n\in\NN}$ é definida como uma função $a:\NN\to\RR$, onde $a_n=a(n)$ para todo $n\in\NN$. \end{block} \begin{block}{Exemplos: P.A (razão $r$) e P.G (quociente $q$)} \alert{Progressão Aritmética} (P.A.): \cor{$a_{n}=a_{n-1}+r$},\ \ \ \ para $n\geq 1$.\\ \alert{Progressão Geométrica} (P.G.): \cor{$a_{n}=a_{n-1}\cdot q$},\ \ \ \ para $n\geq 1$. \end{block} \begin{block}{Soma P.A (Exerc. 9.1) e Soma P.G. (Exerc. 9.3)} P.A. $(a_n)_{n\in\NN}$ com razão $r$ e primeiro termo $a_0$. \[ \sum_{k=0}^{n-1} a_k\ =\ a_0\cdot n\ +\ \frac{r\cdot n(n+1)}{2} \] P.G. $(a_n)_{n\in\NN}$ com quociente $q$ e primeiro termo $a_0$. \[ \sum_{k=0}^{n-1} a_k\ =\ \frac{a_0\cdot(q^n-1)}{q-1} \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Sequências Recorrentes - Mais exemplos} \begin{block}{Sequência de Fibonacci} $F_n=F_{n-1}+F_{n-2}$ para $n\geq 2$ com $F_0=0$ e $F_1=1$.\\ $(F_n)_{n\in\NN}\ =\ (\alert{0,1},\cor{1,2,3,5,8,13,21,34,55,89},\ldots)$ \end{block} \begin{block}{Somatórios} Dada uma sequência $(x_n)_{n\in\NN}$, podemos definir\\ uma sequência soma $(S_n)_{n\in\NN^*}$, como $S_1=x_0$ e, para $n\geq 2$, \[ S_n\ =\ \sum_{k=0}^{n-1} x_k\ =\ S_{n-1}\ +\ x_{n-1};\ ou \] uma sequência soma $(S_n)_{n\in\NN}$, como $S_0=x_0$ e , para $n\geq 1$, \[ S_n\ =\ \sum_{k=0}^{n} x_k\ =\ S_{n-1}\ +\ x_{n} \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Sequências Recorrentes - Definição} %\begin{block}{Equação de Recorrência} Muitas vezes, uma sequência é dada por uma \cor{Equação de Recorrência}, definindo um termo genérico através de termos anteriores da sequência. \corB{\textbf{Exemplos:} PA, PG, Fibonacci, Somatórios, etc...} Em geral, o objetivo é \alert{resolver a recorrência}, ou seja, encontrar uma \alert{\textbf{fórmula fechada}} para a sequência, sem depender de termos da própria sequência. %\end{block} \begin{block}{Exemplos:} \esp{10}\alert{Recorrência}\esp{15}\alert{Fórmula fechada}\\ \cor{\textbf{P.A.:}} $a_{n}=a_{n-1}+r\ \ \Tto\ \ a_{n}\ =\ a_0\ +\ r\cdot n$\\ \cor{\textbf{P.G.:}} $a_{n}=a_{n-1}\cdot q\ \ \Tto\ \ a_{n}\ =\ a_0\cdot q^n$\\ \cor{\textbf{Somatório dos quadrados perfeitos:}} $S_{n}=S_{n-1}+n^2\ \ (S_0=0)\ \Tto$ \[ \alert{\mbox{Fórmula fechada:}}\ \ \ S_n\ =\ \sum_{k=1}^{n} k^2\ =\ \frac{n(n+1)(2n+1)}{6} \] \cor{\textbf{Fibonacci:}} $F_{n}=F_{n-1}+F_{n-2}\ \ (F_0=0, F_1=1)\ \Tto$ \[ \alert{\mbox{Fórmula fechada:}}\ \ \ F_n\ =\ \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right] \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Sequências Recorrentes - Tipos} \begin{block}{Recorrência de 1$^o$ ordem} $a_n$ depende apenas do termo anterior $a_{n-1}$.\ \ \ \ \ \ $a_0$ deve ser dado.\\ \alert{Exemplos:} \cor{P.A., P.G., somatório} dos $n$ primeiros quadrados perfeitos. \end{block} \begin{block}{Recorrência de 2$^o$ ordem} $a_n$ depende apenas dos dois termos anteriores $a_{n-1}$ e $a_{n-2}$.\\ $a_0$ e $a_1$ devem ser dados.\\ \alert{Exemplos:} \cor{Fibonacci $F_n=F_{n-1}+F_{n-2}$},\ \ \ \corB{$a_n=3\cdot a_{n-2}$}. \end{block} \begin{block}{Recorrência de k$^o$ ordem} $a_n$ depende apenas dos $k$ termos anteriores $a_{n-1},\ldots,a_{n-k}$.\\ $a_0,\ldots,a_{k-1}$ devem ser dados. \alert{Exemplo:} $a_n=a_{n-k}+1$.\\ \alert{Exemplo:} $a_n=a_{n-1}+a_{n-2}+a_{n-3}+\ldots+a_{n-k}$.\\ \alert{Exemplo:} $a_n=a_{n-3}\cdot 10$ com $a_0=1$, $a_1=2$ e $a_2=3$.\\ $\cor{a_n}\ =\ (\cor{1,2,3},\corB{10,20,30},\alert{100,200,300},\ldots)$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $1^o$-ordem - 10.4.1.Aditiva simples} \begin{block}{Recorrência de 1$^o$ ordem - aditiva simples} \alert{\bf Recorrência:} \cor{$a_n\ =\ a_{n-1}\ +\ f(n)$}\\ \textbf{Ex: \cor{P.A.}} é um caso particular quando $f(n)=r$ constante.\\ \alert{\bf Solução: Fórmula fechada} para qualquer $0\leq mm$: $a_n = a_m + \sum_{k=m+1}^{n}r\ =\ a_m+r\cdot(n-m)$\\ Se $n0$) com $a_0=2$} $\alert{a_n =} a_0 + \sum_{k=1}^{n}\pi^2\ =\ \alert{2+\pi^2n}$ \end{block} \begin{block}{Exercício 10.5: $a_n=a_{n-1}+n^2$ ($n>0$) com $a_0=0$} $\alert{a_n =} a_0 + \sum_{k=1}^{n}k^2\ =\ \alert{n(n+1)(2n+1)/6}$ \end{block} \begin{block}{Exercício 10.5': $a_n=a_{n-1}+n^3$ ($n>0$) com $a_0=0$} $\alert{a_n =} a_0 + \sum_{k=1}^{n}k^3\ =\ \alert{n^2(n+1)^2/4}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $1^o$-ordem - 10.4.1.Aditiva simples} \begin{block}{Recorrência de 1$^o$ ordem - aditiva simples} \alert{\bf Recorrência:} \cor{$a_n\ =\ a_{n-1}\ +\ f(n)$}\\ \textbf{Ex: \cor{P.A.}} é um caso particular quando $f(n)=r$ constante.\\ \alert{\bf Solução: Fórmula fechada} para qualquer $0\leq m0$) com $a_0=0$} $\alert{a_n =} a_0 + \sum_{k=1}^{n}2^{k-1}\ =\ \sum_{i=0}^{n-1}2^i\ =\ \alert{2^n-1}$ \end{block} \begin{block}{Exercício 10.6: $a_n=a_{n-1}+2^n$ ($n>0$) com $a_1=1$} $\alert{a_n =} a_1 + \sum_{k=2}^{n}2^k\ =\ 1+\sum_{k=0}^{n}2^k-2^0-2^1\ =\ 1+(2^{n+1}-1)-3=\alert{2^{n+1}-3}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $1^o$-ordem - Retas no plano} \begin{block}{Recorrência de 1$^o$ ordem - aditiva simples} \alert{\bf Recorrência:} \cor{$a_n\ =\ a_{n-1}\ +\ f(n)$}\\ \textbf{Ex: \cor{P.A.}} é um caso particular quando $f(n)=r$ constante.\\ \alert{\bf Solução: Fórmula fechada} para qualquer $0\leq m0$) com $a_1=2$\\ \cor{Fórmula fechada:} $\alert{a_n =} a_1 + \sum_{k=2}^{n}k\ =\ \alert{1+n(n+1)/2}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $1^o$-ordem - Retas no plano} \begin{block}{Recorrência de 1$^o$ ordem - aditiva simples} \alert{\bf Recorrência:} \cor{$a_n\ =\ a_{n-1}\ +\ f(n)$}\\ \textbf{Ex: \cor{P.A.}} é um caso particular quando $f(n)=r$ constante.\\ \alert{\bf Solução: Fórmula fechada} para qualquer $0\leq m1$) com $a_1=2$\\ \cor{Fórmula fechada:} $\alert{a_n =} a_1 + \sum_{k=2}^{n}2\ =\ \alert{2\cdot n}$ (para $n\geq 1$) \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $1^o$-ordem - Círculos no plano} \begin{block}{Recorrência de 1$^o$ ordem - aditiva simples} \alert{\bf Recorrência:} \cor{$a_n\ =\ a_{n-1}\ +\ f(n)$}\\ \textbf{Ex: \cor{P.A.}} é um caso particular quando $f(n)=r$ constante.\\ \alert{\bf Solução: Fórmula fechada} para qualquer $0\leq m1$ com $a_1=2$\\ \textbf{(b)} \cor{Fórmula fechada:} $\alert{a_n =} a_1 + \sum_{k=2}^{n}2(k-1)\ =\ \alert{n^2-n+2}$ ($n\geq 1$) \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $1^o$-ordem - Círculos no plano} \begin{block}{Recorrência de 1$^o$ ordem - aditiva simples} \alert{\bf Recorrência:} \cor{$a_n\ =\ a_{n-1}\ +\ f(n)$}\\ \textbf{Ex: \cor{P.A.}} é um caso particular quando $f(n)=r$ constante.\\ \alert{\bf Solução: Fórmula fechada} para qualquer $0\leq m1$ com $a_1=2$\\ \textbf{(b)} \cor{Fórmula fechada:} $\alert{a_n =} a_1 + \sum_{k=2}^{n}2(k-1)\ =\ \alert{n^2-n+2}$ ($n\geq 1$) \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $1^o$-ordem - Círculos no plano} \begin{block}{Recorrência de 1$^o$ ordem - aditiva simples} \alert{\bf Recorrência:} \cor{$a_n\ =\ a_{n-1}\ +\ f(n)$}\\ \textbf{Ex: \cor{P.A.}} é um caso particular quando $f(n)=r$ constante.\\ \alert{\bf Solução: Fórmula fechada} para qualquer $0\leq m1$ com $a_1=2$\\ \textbf{(b)} \cor{Fórmula fechada:} $\alert{a_n =} a_1 + \sum_{k=2}^{n}2(k-1)\ =\ \alert{n^2-n+2}$ ($n\geq 1$) \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $1^o$-ordem - Exercício 10.8} \begin{block}{Recorrência de 1$^o$ ordem - aditiva simples} \alert{\bf Recorrência:} \cor{$a_n\ =\ a_{n-1}\ +\ f(n)$}\\ \textbf{Ex: \cor{P.A.}} é um caso particular quando $f(n)=r$ constante.\\ \alert{\bf Solução: Fórmula fechada} para qualquer $0\leq m1$) com $I_0=0$\\ $P_n=3^n-I_n\ \ \Tto\ \ \alert{I_n=I_{n-1}+3^{n-1}}$.\\ .\\ \textbf{(b)} \cor{Fórmula fechada:}\\ $\alert{I_n =} I_0 + \sum_{k=1}^{n}3^{k-1}\ =\ \sum_{i=0}^{n-1}3^i\ =\ (3^n-1)/(3-1)\ =\ \alert{(3^n-1)/2}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $1^o$-ordem - 10.4.2. Multiplicativa simples} \begin{block}{Recorrência de 1$^o$ ordem - multiplicativa simples} \alert{\bf Recorrência:} \cor{$a_n\ =\ a_{n-1}\ \cdot\ f(n)$}\\ \textbf{Ex: \cor{P.G.}} é um caso particular quando $f(n)=q$ constante.\\ \alert{\bf Solução: Fórmula fechada} para qualquer $0\leq mm$: $a_n = a_m \cdot \prod_{k=m+1}^{n}q\ =\ a_m\cdot q^{n-m}$\\ Se $n0$ e suponha valer para menos de $n$ discos.\\ \textbf{P.I.:} Vamos provar que também vale para $n$ discos.\\ $a_n=2\cdot a_{n-1}+1\ \TtoB{H.I.}\ a_n=2\cdot\corB{(2^{n-1}-1)}+1\ =\ 2^n-2+1$\\ \alert{$a_n\ =\ 2^n-1$.} \textbf{cqd}\ $\square$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $2^o$-ordem} \begin{block}{Recorrência de 2$^o$ ordem} $a_n$ depende apenas dos dois termos anteriores $a_{n-1}$ e $a_{n-2}$.\\ $a_0$ e $a_1$ devem ser dados.\\ \alert{Exemplo:} \cor{Fibonacci\ $F_n=F_{n-1}+F_{n-2}$},\ \ \ \ \ \ \ \ \ \corB{$G_n\ =\ -G_{n-2}$}.\\ \alert{Exemplo:} \cor{Fibonacci' $F'_n=F'_{n-1}+F'_{n-2}+1$},\ \ \ \corB{$G'_n\ =\ -G'_{n-2}\ +\ 1$}. \end{block} \begin{block}{Recorrência de 2$^o$ ordem homogênea} É da forma \alert{$a_n=s_1\cdot a_{n-1}+s_2\cdot a_{n-2}$}.\\ $a_0$ e $a_1$ devem ser dados, e $s_1$ e $s_2$ são constantes.\\ \alert{Exemplos:} $F_n$ e $G_n$ são homogêneas. $F'_n$ e $G'_n$ são não-homogêneas. \end{block} \begin{block}{Recorrência de k$^o$ ordem homogênea} É da forma \alert{$a_n=s_1\cdot a_{n-1}+s_2\cdot a_{n-2}+\ldots+s_k\cdot a_{n-k}$}.\\ $a_0,a_1,\ldots,a_{k-1}$ devem ser dados, e $s_1,s_2,\ldots,s_k$ são constantes.\\ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $2^o$-ordem homogêneas} É da forma \alert{$a_n=s_1\cdot a_{n-1}+s_2\cdot a_{n-2}$}.\\ \begin{block}{Soluções do tipo $a_n\ =\ r^n$ para $r\ne 0$:} $a_n=s_1\cdot a_{n-1}+s_2\cdot a_{n-2}\ \ \Tto\ \ r^n=s_1r^{n-1}+s_2r^{n-2}\ \TtoB{\div r^{n-2}}$\\ $\TtoB{\div r^{n-2}}\ r^2=s_1r+s_2\ \tto\ \alert{r^2-s_1r-s_2=0}$ (Eq. 2$^o$-grau: raízes \cor{$r_1$} e \cor{$r_2$})\\ Portanto \cor{$a_n=r_1^n$} e \cor{$a_n=r_2^n$} são soluções (\corB{ignorando} \cor{$a_0$} e \cor{$a_1$})\\ .\\ Se \alert{$a'_n$} e \alert{$a''_n$} são soluções, então \alert{$a_n=c_1a'_n+c_2a''_n$} é solução, pois\\ $\alert{a_n}\ \cor{=}\ c_1a'_n+c_2a''_n\ \cor{=}\ c_1(s_1a'_{n-1}+s_2a'_{n-2})+c_2(s_1a''_{n-1}+s_2a''_{n-2})\ \cor{\Tto}$\\ $\alert{a_n}\ \cor{=}\ s_1(c_1a'_{n-1}+c_2a''_{n-1})+s_2(c_1a'_{n-2}+c_2a''_{n-2})\ \cor{=}\ \alert{s_1a_{n-1}+s_2a_{n-2}}$\\ \end{block} \begin{block}{Soluções do tipo $a_n\ =\ c_1r_1^n+c_2r_2^n$ para $r_1\ne r_2$:} $a_0=c_1r_1^0+c_2r_2^0\ \Tto\ c_1+c_2=a_0$\\ $a_1=c_1r_1^1+c_2r_2^1\ \Tto\ r_1c_1+r_2c_2=a_1$\\ Resolver sistema 2 equações e variáveis $c_1$ e $c_2$:\\ \[ c_1\ =\ \frac{a_1-a_0r_2}{r_1-r_2}\ \ \ \ e\ \ \ \ c_2\ =\ \frac{-a_1+a_0r_1}{r_1-r_2} \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $2^o$-ordem homogêneas} \textbf{\cor{Teorema:}} Sejam $r_1$ e $r_2$ as raízes de \cor{$x^2-s_1x-s_2=0$}. Se $r_1\ne r_2$, então toda solução para a recorrência \alert{$a_n=s_1a_{n-1}+s_2a_{n-2}$} é da forma \cor{$a_n=c_1r_1^n+c_2r_2^n$}. Ademais, \[ c_1\ =\ \frac{a_1-a_0r_2}{r_1-r_2}\ \ \ \ e\ \ \ \ c_2\ =\ \frac{-a_1+a_0r_1}{r_1-r_2} \] \begin{block}{Exerc.13(c)L2: $a_n=5a_{n-1}-6a_{n-2}$ com $a_0=1$ e $a_1=3$} $s_1=5,\ s_2=-6:$ \alert{eq. caract. $x^2-5x+6=0$}\ $\Tto\ $raízes $r_1=3$ e $r_2=2$\\ $\corB{c_1\ =\ }(3-1\cdot 2)/(3-2)\corB{\ =\ 1}$\ \ e\ \ $\corB{c_2\ =\ }(-3+1\cdot 3)/(3-2)\corB{\ =\ 0}$\\ \cor{$a_n\ =\ 1\cdot 3^n+0\cdot 2^n$} $\ \Tto\ $ \alert{$a_n=3^n$} \end{block} \begin{block}{Exerc.13(c')L2: $a_n=5a_{n-1}-6a_{n-2}$ com $a_0=1$ e $a_1=2$} $\corB{c_1\ =\ }(2-1\cdot 2)/(3-2)\corB{\ =\ 0}$\ \ e\ \ $\corB{c_2\ =\ }(-2+1\cdot 3)/(3-2)\corB{\ =\ 1}$\\ \cor{$a_n\ =\ 0\cdot 3^n+1\cdot 2^n$} $\ \Tto\ $ \alert{$a_n=2^n$} \end{block} \begin{block}{Exerc.13(c'')L2: $a_n=5a_{n-1}-6a_{n-2}$ com $a_0=0$ e $a_1=1$} $\corB{c_1\ =\ }(1-0\cdot 2)/(3-2)\corB{\ =\ 1}$\ \ e\ \ $\corB{c_2\ =\ }(-1+0\cdot 3)/(3-2)\corB{\ =\ -1}$\\ \cor{$a_n\ =\ (1)\cdot 3^n+(-1)\cdot 2^n$} $\ \Tto\ $ \alert{$a_n=3^n-2^n$} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $2^o$-ordem homogêneas} \textbf{\cor{Teorema:}} Sejam $r_1$ e $r_2$ as raízes de \cor{$x^2-s_1x-s_2=0$}. Se $r_1\ne r_2$, então toda solução para a recorrência \alert{$a_n=s_1a_{n-1}+s_2a_{n-2}$} é da forma \cor{$a_n=c_1r_1^n+c_2r_2^n$}. Ademais, \[ c_1\ =\ \frac{a_1-a_0r_2}{r_1-r_2}\ \ \ \ e\ \ \ \ c_2\ =\ \frac{-a_1+a_0r_1}{r_1-r_2} \] \begin{block}{Exemplo: $a_n=3a_{n-1}+4a_{n-2}$ com $a_0=3$ e $a_1=2$} $s_1=3,\ s_2=4:$ \alert{eq. caract. $x^2-3x-4=0$}\ $\Tto\ $raízes $r_1=4$ e $r_2=-1$\\ $\corB{c_1\ =\ }(2-3(-1))/(4-(-1))\corB{\ =\ 1}$\ \ e\ \ $\corB{c_2\ =\ }(-2+3\cdot 4)/(4-(-1))\corB{\ =\ 2}$\\ \cor{$a_n\ =\ 1\cdot 4^n+2\cdot(-1)^n$} $\ \Tto\ $ \alert{$a_n\ =\ 4^n+2\cdot(-1)^n$} \end{block} \begin{block}{Fibonacci: $F_n=F_{n-1}+F_{n-2}$ com $F_0=0$ e $F_1=1$} $s_1=1,\ s_2=1:$ \alert{eq. caract. $x^2-x-1=0$}\ $\Tto\ $raízes $r_1,r_2=(1\pm\sqrt{5})/2$\\ $\corB{c_1\ =\ }(1-0(r_2))/\sqrt{5}\corB{\ =\ 1/\sqrt{5}}$\ \ e\ \ $\corB{c_2\ =\ }(-1+0\cdot r_1)/\sqrt{5}\corB{\ =\ -1/\sqrt{5}}$\\ \alert{$F_n\ =\ \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $2^o$-ordem homogêneas} \textbf{\cor{Teorema:}} Sejam $r_1$ e $r_2$ as raízes de \cor{$x^2-s_1x-s_2=0$}. Se $r_1\ne r_2$, então toda solução para a recorrência \alert{$a_n=s_1a_{n-1}+s_2a_{n-2}$} é da forma \cor{$a_n=c_1r_1^n+c_2r_2^n$}. Ademais, \[ c_1\ =\ \frac{a_1-a_0r_2}{r_1-r_2}\ \ \ \ e\ \ \ \ c_2\ =\ \frac{-a_1+a_0r_1}{r_1-r_2} \] \begin{block}{Exemplo: $a_n=-a_{n-2}$ com $a_0=4$ e $a_1=6$} $a_n\ =\ (4,6,-4,-6,\cor{4,6,-4,-6},4,6,-4,-6,\ldots)$\\ $s_1=0,\ s_2=-1:$ \alert{eq. caract. $x^2+1=0$}\ $\tto\ $raízes $r_1=i=\sqrt{\mbox{-}1}$ e $r_2=\mbox{-}i$\\ $\corB{c_1\ =\ }(6-4(-i))/(i-(-i))\corB{\ =\ 2-3i}$\ \ e\ \ $\corB{c_2\ =\ }(-6+4\cdot i)/2i\corB{\ =\ 2+3i}$\\ \cor{$a_n\ =\ (2-3i)\cdot i^n+(2+3i)\cdot(-i)^n$} $\ \Tto\ $ \alert{$a_n\ =\ 2\cdot i^n(1+(-1)^n)+3\cdot i^{n-1}(1+(-1)^{n-1})$}\\ $n$ par $\ \Tto\ a_n=\pm 4$\ \ \ \ \ \ \ \ $n$ ímpar $\ \Tto\ a_n=\pm 6$\\ .\\ Na verdade, é melhor resolver recorrências desse tipo \alert{$a_n=s_2\cdot a_{n-2}$} como duas P.G.'s separadas nos índices pares e nos índices ímpares, com quociente $q$ e primeiros valores $a_0$ e $a_1$, respectivamente. \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $2^o$-ordem homogêneas (raiz repetida)} \textbf{\cor{Teorema:}} Sejam $r_1$ e $r_2$ de forma que a equação \cor{$x^2-s_1x-s_2=0$} tenha apenas uma raiz $r\ne 0$. Então toda solução para a recorrência \alert{$a_n=s_1a_{n-1}+s_2a_{n-2}$} é da forma \cor{$a_n=c_1\cdot r^n+c_2n\cdot r^n$}. Ademais, \[ c_1\ =\ a_0\ \ \ \ e\ \ \ \ c_2\ =\ \frac{a_1-a_0r}{r} \] \begin{block}{Intuição da Prova:} $x^2-s_1x-s_2=0$ tem só 1 raiz $\cor{\tto}$ Eq. $(x\mbox{-}r)^2=x^2\mbox{-}2rx\mbox{+}r^2$ $\cor{\tto}$\\ $\cor{\tto}\ s_1=2r$ e $s_2=-r^2\ \Tto$\ usa-se isso p/ mostrar que $n\cdot r^n$ é solução.\\ .\\ $\alert{nr^n = s_1(n-1)r^{n-1}+s_2(n-2)r^{n-2}}\cor{\IffB{\div r^{n-2}}} r^2n=s_1r(n-1)+s_2(n-2)\cor{\IffB{s_1,s_2}}$\\ $\cor{\IffB{s_1,s_2}} r^2n=2r^2(n-1)-r^2(n-2)\cor{\IffB{\div r^2}}n=2(n-1)-(n-2)\ \cor{\iff}\ 0=0$\\ .\\ \alert{Além disso,}\\ $a_0=c_1r^0+c_2\cdot 0\cdot r^0\ \Tto\ c_1=a_0$\\ $a_1=c_1r^1+c_2\cdot 1\cdot r^1\ \Tto\ c_1r+c_2r=a_1\ \Tto\ c_2=(a_1-a_0r)/r$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $2^o$-ordem homogêneas (raiz repetida)} \textbf{\cor{Teorema:}} Sejam $r_1$ e $r_2$ de forma que a equação \cor{$x^2-s_1x-s_2=0$} tenha apenas uma raiz $r\ne 0$. Então toda solução para a recorrência \alert{$a_n=s_1a_{n-1}+s_2a_{n-2}$} é da forma \cor{$a_n=c_1\cdot r^n+c_2n\cdot r^n$}. Ademais, \[ c_1\ =\ a_0\ \ \ \ e\ \ \ \ c_2\ =\ \frac{a_1-a_0r}{r} \] \begin{block}{Exerc.13(d): $a_n=4a_{n-1}-4a_{n-2}$ com $a_0=1$ e $a_1=3$} $s_1=4,\ s_2=-4:$ \alert{eq. caract. $x^2-4x+4=0$}\ $\Tto\ $raíz única $r=2$\\ $\corB{c_1\ =\ }a_0\corB{\ =\ 1}$\ \ e\ \ $\corB{c_2\ =\ }(3-1\cdot 2)/2\corB{\ =\ 1/2}$\\ \cor{$a_n\ =\ 1\cdot 2^n+(1/2)\cdot n\cdot 2^n$} $\ \Tto\ $ \alert{$a_n\ =\ (2+n)\cdot 2^{n-1}$} \end{block} \begin{block}{Exerc.13(d'): $a_n=4a_{n-1}-4a_{n-2}$ com $a_0=1$ e $a_1=4$} $\corB{c_1\ =\ }a_0\corB{\ =\ 1}$\ \ e\ \ $\corB{c_2\ =\ }(4-1\cdot 2)/2\corB{\ =\ 1}$\\ \cor{$a_n\ =\ 1\cdot 2^n+1\cdot n\cdot 2^n$} $\ \Tto\ $ \alert{$a_n\ =\ (1+n)\cdot 2^{n}$} \end{block} \begin{block}{Exerc.13(d''): $a_n=4a_{n-1}-4a_{n-2}$ com $a_0=1$ e $a_1=6$} $\corB{c_1\ =\ }a_0\corB{\ =\ 1}$\ \ e\ \ $\corB{c_2\ =\ }(6-1\cdot 2)/2\corB{\ =\ 2}$\\ \cor{$a_n\ =\ 1\cdot 2^n+2\cdot n\cdot 2^n$} $\ \Tto\ $ \alert{$a_n\ =\ (1+2n)\cdot 2^{n}$} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $2^o$-ordem homogêneas (raiz repetida)} \textbf{\cor{Teorema:}} Sejam $r_1$ e $r_2$ de forma que a equação \cor{$x^2-s_1x-s_2=0$} tenha apenas uma raiz $r\ne 0$. Então toda solução para a recorrência \alert{$a_n=s_1a_{n-1}+s_2a_{n-2}$} é da forma \cor{$a_n=c_1\cdot r^n+c_2n\cdot r^n$}. Ademais, \[ c_1\ =\ a_0\ \ \ \ e\ \ \ \ c_2\ =\ \frac{a_1-a_0r}{r} \] \begin{block}{Exemplo: $a_n=6a_{n-1}-9a_{n-2}$ com $a_0=2$ e $a_1=9$} $s_1=6,\ s_2=-9:$ \alert{eq. caract. $x^2-6x+9=0$}\ $\Tto\ $raíz única $r=3$\\ $\corB{c_1\ =\ }a_0\corB{\ =\ 2}$\ \ e\ \ $\corB{c_2\ =\ }(9-2\cdot 3)/3\corB{\ =\ 1}$\\ \cor{$a_n\ =\ 2\cdot 3^n+1\cdot n\cdot 3^n$} $\ \Tto\ $ \alert{$a_n\ =\ (2+n)\cdot 3^{n}$} \end{block} \begin{block}{Exemplo: $a_n=6a_{n-1}-9a_{n-2}$ com $a_0=2$ e $a_1=6$} $\corB{c_1\ =\ }a_0\corB{\ =\ 2}$\ \ e\ \ $\corB{c_2\ =\ }(6-2\cdot 3)/3\corB{\ =\ 0}$\\ \cor{$a_n\ =\ 2\cdot 3^n+0\cdot n\cdot 3^n$} $\ \Tto\ $ \alert{$a_n\ =\ 2\cdot 3^{n}$} \end{block} \begin{block}{Exemplo: $a_n=6a_{n-1}-9a_{n-2}$ com $a_0=2$ e $a_1=3$} $\corB{c_1\ =\ }a_0\corB{\ =\ 2}$\ \ e\ \ $\corB{c_2\ =\ }(3-2\cdot 3)/3\corB{\ =\ -1}$\\ \cor{$a_n\ =\ 2\cdot 3^n+(-1)\cdot n\cdot 3^n$} $\ \Tto\ $ \alert{$a_n\ =\ (2-n)\cdot 3^{n}$} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $2^o$-ordem homogêneas (raiz repetida)} \textbf{\cor{Teorema:}} Sejam $r_1$ e $r_2$ de forma que a equação \cor{$x^2-s_1x-s_2=0$} tenha apenas uma raiz $r\ne 0$. Então toda solução para a recorrência \alert{$a_n=s_1a_{n-1}+s_2a_{n-2}$} é da forma \cor{$a_n=c_1\cdot r^n+c_2n\cdot r^n$}. Ademais, \[ c_1\ =\ a_0\ \ \ \ e\ \ \ \ c_2\ =\ \frac{a_1-a_0r}{r} \] \begin{block}{Exemplo: $a_n=2a_{n-1}-a_{n-2}$ com $a_0$ e $a_1$} $s_1=2,\ s_2=-1:$ \alert{eq. caract. $x^2-2x+1=0$}\ $\Tto\ $raíz única $r=1$\\ $\corB{c_1\ =\ a_0}$\ \ e\ \ $\corB{c_2\ =\ }(a_1-a_0\cdot 1)/1\corB{\ =\ (a_1-a_0)}$\\ \cor{$a_n\ =\ a_0\cdot 1^n+(a_1-a_0)\cdot n\cdot 1^n$} $\ \Tto\ $ \alert{$a_n\ =\ (a_1-a_0)n+a_0$} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $2^o$-ordem NÃO-homogêneas} \begin{block}{Teorema:} Dada uma recorrência \alert{$a'_n=s_1a'_{n-1}+s_2a'_{n-2}+s_3$}, se $s_1+s_2\ne 1$, então \cor{$a'_n=a_n-b$}, onde $(a_n)_n\in\NN$ é tal que \cor{$a_n=s_1a_{n-1}+s_2a_{n-2}$} e $b=s_3/(s_1+s_2-1)$. \end{block} \begin{block}{Prova:} $a'_n=a_n-b\ \cor{\iff}\ (a_n-b)=s_1(a_{n-1}-b)+s_2(a_{n-2}-b)+s_3\ \cor{\iff}$\\ $\cor{\iff}\ a_n=s_1a_{n-1}+s_2a_{n-2}+s_3-b(s_1+s_2-1)\ \cor{\iff}\ a_n=s_1a_{n-1}+s_2a_{n-2}$ \end{block} \begin{block}{Ex: Fibonacci' $F'_n=F'_{n\mbox{-}1}+F'_{n\mbox{-}2}+1$ com $F'_0=\mbox{-}1$ e $F'_1=0$} \textbf{Intuição:} Observar que \alert{$F'_n=F_n-1$} funciona, pois\\ $F_n=F_{n-1}+F_{n-2}\ \cor{\iff}\ F_n-1=(F_{n-1}-1)+(F_{n-2}-1)+1\ \cor{\iff}$\\ $\cor{\iff}\ F'_n=F'_{n-1}+F'_{n-2}+1$\\ $F'_n\ =\ ( \cor{-1,0,}0,1,2,4,7,12,20,33,54,\ldots)$\\ $F_n\ \ =\ (\ \ \cor{0,1,}1,2,3,5,8,13,21,34,55,\ldots)$\\ \alert{$F'_n\ =\ \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]\ \ -\ 1$} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Recorrências de $2^o$-ordem NÃO-homogêneas} \begin{block}{Teorema:} Dada uma recorrência \alert{$a'_n=s_1a'_{n-1}+s_2a'_{n-2}+s_3$}, se $s_1+s_2\ne 1$, então \cor{$a'_n=a_n-b$}, onde $(a_n)_n\in\NN$ é tal que \cor{$a_n=s_1a_{n-1}+s_2a_{n-2}$} e $b=s_3/(s_1+s_2-1)$. \end{block} \begin{block}{Exemplo: $a'_n=6a'_{n-1}-9a'_{n-2}+4$ com $a'_0=3$ e $a'_1=7$} $b=4/(6\mbox{-}9\mbox{-}1)=\mbox{-}1\ \cor{\tto}\ a'_n=a_n\mbox{+}1$ com \cor{$a_n=6a_{n\mbox{-}1}\mbox{-}9a_{n\mbox{-}2}$}, $a_0=2, a_1=6$\\ $\cor{a_n=2\cdot 3^n}\ \Tto\ \alert{a'_n=2\cdot 3^n\ \ +\ \ 1}$ \end{block} \begin{block}{Exemplo: $a'_n=-a'_{n-2}+4$ com $a'_0=6$ e $a'_1=8$} $b=4/(0-1-1)=-2\ \cor{\Tto}\ a'_n=a_n+2$ com \cor{$a_n=-a_{n-2}$}, $a_0=4, a_1=6$\\ %\cor{$a_n\ =\ (2-3i)\cdot i^n+(2+3i)\cdot(-i)^n$}\ $\Tto$\ \\ \alert{$a'_n\ =\ (2-3i)\cdot i^n+(2+3i)\cdot(-i)^n\ \ +\ \ 2$}\\ $a'_n\ =\ (\cor{6,8,}-2,-4,6,8,-2,-4,\ldots)$\\ $a_n\ \ =\ (\cor{4,6,}-4,-6,4,6,-4,-6,\ldots)$\\ \end{block} \begin{block}{CASOS MAIS GERAIS: Funções geradoras} Técnica das Funções Geradoras: \alert{não será ensinado aqui}. \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Sequências Recorrentes - RESUMO} \begin{block}{Recorrências de 1$^o$ ordem: $a_n=a_{n-1}\cdot s(n)\ +\ t(n)$} \begin{itemize} \item Aditiva simples ($s(n)=1$):\ \cor{$a_n=a_0+\sum_{k=1}^n t(k)$} \item Multipl. simples ($t(n)=0$):\ \cor{$a_n=a_0\cdot\prod_{k=1}^n s(k)$} \item Caso geral com constantes ($s\ne 1$ e $t$):\ \cor{$a_n=c_1\cdot s^n+c_2$} \end{itemize} \end{block} \begin{block}{Recorrências de 2$^o$ ordem hom: $a_n=s_1a_{n-1}+s_2a_{n-2}$} \begin{itemize} \item Equação característica: \alert{$x^2-s_1x-s_2=0$} com raízes $r_1,r_2$ \item Raízes distintas ($r_1\ne r_2$):\ \cor{$a_n=c_1\cdot r_1^n+c_2\cdot r_2^n$} \item Raízes iguais ($r_1\mbox{=}r_2\mbox{=}r$):\ \ \cor{$a_n=c_1\cdot r^n+c_2\cdot n\cdot r^n$} \end{itemize} \end{block} \begin{block}{Recorrências de 2$^o$ ordem NÃO-hom: $a'_n=s_1a'_{n-1}+s_2a'_{n-2}+s_3$} \begin{itemize} \item Se \alert{$s_1+s_2\ne 1$}, seja $b=s_3/(s_1\mbox{+}s_2\mbox{-}1)$. \item Rec. hom corr: \cor{$a_n=s_1a_{n\mbox{-}1}\mbox{+}s_2a_{n\mbox{-}2}$} com $a_0=a'_0\mbox{+}b$ e $a_1=a'_1\mbox{+}b$ \item Solução: \cor{$a'_n\ =\ a_n-b$} \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{\centering \huge{\alert{Capítulo 11\\COMBINATÓRIA}} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{Ex 11.1: 3 bolas rotuladas 1 a 3 em caixas numeradas A e B.} \begin{itemize} \item $2^3=8$ modos: AAA,AAB,ABA,ABB,BAA,BAB,BBA,BBB \item[(a)] E se bolas idênticas com caixas distintas ? \item 4 modos: 3-0, 2-1, 1-2, 0-3 \item[(b)] E se bolas distintas com caixas idênticas ? \item 4 modos: 123-$\emptyset$, 12-3, 13-2, 1-23 \item[(c)] E se bolas idênticas com caixas idênticas ? \item 2 modos: 3-0, 2-1 \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{Ex 11.10: 20 pessoas em 4 viagens, cada uma com 5 pessoas.} \[ \binom{20}{5}\cdot\binom{15}{5}\cdot\binom{10}{5}\cdot\binom{5}{5} \ =\ \frac{20!}{5!\cnot{15!}}\cdot\frac{\cnot{15!}}{5!\cnot{10!}}\cdot\frac{\cnot{10!}}{5!\cnot{5!}}\cdot\frac{\cnot{5!}}{5!0!} \ =\ \frac{20!}{5!5!5!5!} \] Faz uma permutação das 20 pessoas: as 5 primeiras vão na 1$^o$ viagem e assim por diante. Dentro dessa permutação maior, qualquer permutação das posições 1 a 5, ou de 6 a 10, ou de 11 a 15, ou de 16 a 20, gerará a mesma configuração de viagem. Por isso, devemos dividir por $5!$ quatro vezes. \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{Exercício 11.13:} \begin{itemize} \item Sejam $X$ e $Y$ conjuntos finitos, com $|X| = m$ e $|Y| = n$. Seja $R$ um subconjunto de $X$ com $r$ elementos, e $S$ um subconjunto de $Y$ com $s$ elementos. Quantas funções $F$ distintas existem de $X$ para $Y$ tais que $F(x)\in S$ para todo $x$ em $R$? \end{itemize} \end{block} \begin{block}{Solução:} \begin{itemize} \item Cada elemento de $R$ tem $s$ valores possíveis e cada elemento fora de $R$ tem $n$ valores possíveis. Pelo princípio multiplicativo: \end{itemize} \[ Resposta\ =\ s^r\ \cdot\ n^{m-r} \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{Exercício 11.22:} \begin{itemize} \item Quantas ``mãos'' diferentes de cinco cartas podem ser obtidas de um baralho de 52 cartas? \end{itemize} \end{block} \begin{block}{Solução:} \begin{itemize} \item De 52 cartas diferentes, temos que escolher 5. A ordem não importa: \end{itemize} \[ Resposta\ =\ \binom{52}{5}\ =\ \frac{52!}{5!(52-5)!}\ =\ \frac{52\cdot 51\cdot 50\cdot 49\cdot 48\cdot\cnot{47!}}{5\cdot 4\cdot 3\cdot 2\cdot 1 \cdot \cnot{47!}} \] \[ \binom{52}{5}\ =\ 52\cdot 51\cdot 5\cdot 49\cdot 4\ =\ 52\cdot 51\cdot 980\ =\ 2.598.960 \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{Exercício 11.23:} \begin{itemize} \item Quantas maneiras há de empilhar 3 laranjas (indistinguíveis) e 2 maçãs (indistinguíveis) dentro um vaso estreito de vidro? \end{itemize} \end{block} \begin{block}{Solução:} \begin{itemize} \item Das 5 posições dentro do vaso estreito, temos que escolher 2 para as maçãs. As 3 posições restantes serão das laranjas. \end{itemize} \[ Resposta\ =\ \binom{5}{2}\ =\ \frac{5!}{2!(5-2)!}\ =\ \frac{5\cdot 4\cdot\cnot{3!}}{2\cdot 1\cdot\cnot{3!}}\ =\ \frac{20}{2}\ =\ 10 \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{Exercício 11.23':} Quantas maneiras há de empilhar 5 frutas (laranjas ou maçãs indistinguíveis) dentro um vaso estreito de vidro? \begin{itemize} \item[(a)] Se o número de maçãs é 0: $\binom{5}{0}\ =\ \frac{5!}{0!5!}\ =\ \cor{1}$ \item[(b)] Se o número de maçãs é 1: $\binom{5}{1}\ =\ \frac{5!}{1!4!}\ =\ \cor{5}$ \item[(c)] Se o número de maçãs é 2: $\binom{5}{2}\ =\ \frac{5!}{2!3!}\ =\ \cor{10}$ \item[(d)] Se o número de maçãs é 3: $\binom{5}{3}\ =\ \frac{5!}{3!2!}\ =\ \cor{10}$ \item[(e)] Se o número de maçãs é 4: $\binom{5}{4}\ =\ \frac{5!}{4!1!}\ =\ \cor{5}$ \item[(f)] Se o número de maçãs é 5: $\binom{5}{5}\ =\ \frac{5!}{5!0!}\ =\ \cor{1}$ \item[(g)] Total = $1+5+10+10+5+1\ =\ \cor{32}\ =\ 2^5\ =\ 2\cdot 2\cdot 2\cdot 2\cdot 2$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{Exercício 11.24:} \begin{itemize} \item Há $2^n$ sequências distintas de $n$ bits (algarismos 0 e 1). Quantas dessas sequências tem exatamente $k$ bits iguais a 1? \end{itemize} \end{block} \begin{block}{Solução:} \begin{itemize} \item Das $n$ posições na sequência, temos que escolher $k$ para o bit 1. As $n-k$ posições restantes serão do bit 0. \end{itemize} \[ Resposta\ =\ \binom{n}{k}\ =\ \frac{n!}{k!(n-k)!} \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{Exercício 11.24':} \begin{itemize} \item Há $3^n$ sequências distintas de $n$ letras A, B ou C. Quantas dessas sequências tem exatamente $k$ letras iguais a A? \end{itemize} \end{block} \begin{block}{Solução:} \begin{itemize} \item Das $n$ posições na sequência, temos que escolher $k$ para a letra A. As $n-k$ posições restantes serão das letras B e C: duas escolhas (B ou C) para cada posição. Pelo princípio multiplicativo: \end{itemize} \[ Resposta\ =\ \binom{n}{k}\cdot 2^{n-k}\ =\ \frac{n!}{k!(n-k)!}\cdot 2^{n-k} \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{Exercício 11.24':} \begin{itemize} \item Há $5^n$ sequências distintas de $n$ letras A, B, C, D ou E. Quantas dessas sequências tem exatamente $k$ letras iguais a A e $\ell$ letras iguais a B? \end{itemize} \end{block} \begin{block}{Solução:} \begin{itemize} \item Das $n$ posições na sequência, temos que escolher $k$ para a letra A. Das $n-k$ posições restantes, temos que escolher $\ell$ para a letra B. As $n-k-\ell$ posições restantes serão das letras C, D e E: três escolhas (C, D ou E) para cada posição. Pelo princípio multiplicativo: \end{itemize} \[ Resposta\ =\ \binom{n}{k}\cdot\binom{n-k}{\ell}\cdot 3^{n-k-\ell} \] \[ =\ \frac{n!}{k!(n-k)!}\cdot\frac{(n-k)!}{\ell!(n-k-\ell)!}\cdot3^{n-k-\ell}\ =\ \frac{n!\ 3^{n-k-\ell}}{k!\ell!(n-k-\ell)!} \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{Ex 11.10: 20 pessoas em 4 viagens, cada uma com 5 pessoas.} \[ \binom{20}{5}\cdot\binom{15}{5}\cdot\binom{10}{5}\cdot\binom{5}{5} \ =\ \frac{20!}{5!\cnot{15!}}\cdot\frac{\cnot{15!}}{5!\cnot{10!}}\cdot\frac{\cnot{10!}}{5!\cnot{5!}}\cdot\frac{\cnot{5!}}{5!0!} \ =\ \frac{20!}{5!5!5!5!} \] Faz uma permutação das 20 pessoas: as 5 primeiras vão na 1$^o$ viagem e assim por diante. Dentro dessa permutação maior, qualquer permutação das posições 1 a 5, ou de 6 a 10, ou de 11 a 15, ou de 16 a 20, gerará a mesma configuração de viagem. Por isso, devemos dividir por $5!$ quatro vezes. \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{Propriedades do Binômio de Newton} \begin{align*} \mbox{\bf (a)}\ \ \ \cor{\binom{n}{k}}\ \ &\cor{=\ \binom{n}{n-k}}\ =\ \frac{n!}{k!(n-k)!}\\ \mbox{\bf (b)} \binom{n+1}{k+1} &=\ \frac{(n+1)!}{(k+1)!(n-k)!}\ =\ \frac{(n+1)\cdot n!}{(k+1)!(n-k)!}\ =\\ &=\ \frac{(k+1\ +\ n-k)\cdot n!}{(k+1)!(n-k)!}\ =\ \frac{n!}{k!(n-k)!}+\frac{n!}{(k+1)!(n-k-1)!}\\ \cor{\binom{n+1}{k+1}} &\cor{=\ \binom{n}{k}\ +\ \binom{n}{k+1}}\ \ \mbox{\alert{Identidade de Pascal ou Relação de Stifel}} \end{align*} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{Propriedades do Binômio de Newton} \begin{align*} \mbox{\bf (c)}\ \ (a+b)^n &=\ (a+b)\cdot(a+b)\cdot(a+b)\cdot\ldots\cdot(a+b)\\ \mbox{Fazendo a } &\mbox{distributividade, os termos desse produto serão da forma}\\ &a\cdot b\cdot b\cdot\ldots\cdot a\ =\ a^{n-k}\cdot b^k\ \ (\mbox{onde $k$ é o número de $b$'s})\\ \ \ \cor{(a+b)^n}\ \ &\cor{=\ \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k} \end{align*} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{Exercício 11.28:} \begin{itemize} \item Seja $X$ um conjunto de $n$ elementos. Usando a fórmula do exercício 11.27, prove que o número de subcojuntos de $X$ de tamanho par é igual ao número de subconjuntos de tamanho ímpar. \end{itemize} \end{block} \begin{block}{Solução:} \begin{align*} \cor{(a+b)^n}\ \ &\cor{=\ \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k}.\ \mbox{Tomando $a=1$ e $b=-1$:}\\ \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\ &=\ \binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\binom{n}{3}+\ldots+(-1)^n\binom{n}{n}\\ \binom{n}{0}+\binom{n}{2}&+\binom{n}{4}+\ldots\ =\ \binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\ldots \end{align*} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Capítulo 11 - Contagem - Combinatória} \begin{block}{} \begin{align*} \binom{n}{r}\ &=\ \frac{n!}{r!(n-r)!}\ =\ \frac{n(n-1)(n-2)\ldots(n-r+1)\cnot{(n-r)!}}{r!\cnot{(n-r)!}}\\ \binom{n}{r}\ &=\ \frac{n}{r}\cdot\frac{n-1}{r-1}\cdot\frac{n-2}{r-2}\cdot\ldots\cdot\frac{n-r+1}{1}\\ \cor{\binom{n}{r}}\ &\cor{=\ \prod_{k=1}^r\frac{n-k+1}{k}} \end{align*} \end{block} É mais fácil calcular computacionalmente assim.\\ Em exercícios dessa disciplina, é melhor deixar em formato de binômio mesmo, amenos que os valores sejam pequenos e possam ser calculados à mão, usando a fórmula original: \begin{align*} \binom{n}{r}\ &=\ \frac{n!}{r!(n-r)!} \end{align*} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Exercício 6 da Lista 3} Se enumerarmos todas as permutações dos algarismos 1, 2, 3, 4 e 5 em ordem crescente, então: \begin{itemize} \item[\textbf{(a)}] Que posição ocupa o número 42513? \item[\textbf{(b)}] Qual número ocupa a posição 73? \end{itemize} \begin{block}{Solução (a):} \begin{itemize} \item Existem $4!$ permutações começando em 1. \item Existem $4!$ permutações começando em 2. \item Existem $4!$ permutações começando em 3. \item Existem $3!$ permutações começando em 41. \item Existem $2!$ permutações começando em 421. \item Existem $2!$ permutações começando em 423. \item Após todas essas, teremos a permutação 42513. \item Posição = $1\ +\ 3\cdot 4!+3!+2\cdot 2!\ =\ \cor{83}$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Exercício 6 da Lista 3} Se enumerarmos todas as permutações dos algarismos 1, 2, 3, 4 e 5 em ordem crescente, então: \begin{itemize} \item[\textbf{(a)}] Que posição ocupa o número 42513? \item[\textbf{(b)}] Qual número ocupa a posição 73? \end{itemize} \begin{block}{Solução (b):} \begin{itemize} \item Existem $1\cdot 4!=24$ permutações começando em 1. \item Existem $2\cdot 4!=48$ permutações começando em 1 ou 2. \item Existem $3\cdot 4!=72$ permutações começando em 1, 2 ou 3. \item Posição 73: \cor{Permutação 41235}. \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Exercício 7 da Lista 3} Quantos são os subconjuntos de $k$ elementos de $\{1,2,\cdots,n\}$ nos quais: \begin{itemize} \item[\textbf{(a)}] $1$ aparece? \item[\textbf{(b)}] $1$ não aparece? \item[\textbf{(c)}] $1$ e $2$ aparecem? \item[\textbf{(d')}] $1$ aparece e $2$ não aparece? \item[\textbf{(e')}] $1$ e $2$ não aparecem? \end{itemize} \begin{block}{Solução:} \begin{itemize} \item[(a)] $\binom{n-1}{k-1}$ \item[(b)] $\binom{n-1}{k}$ \item[(c)] $\binom{n-2}{k-2}$ \item[(d')] $\binom{n-2}{k-1}$ \item[(e')] $\binom{n-2}{k}$ \end{itemize} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Exercício 8 da Lista 3} Considere todos os subconjuntos com 5 elementos de $\{1,2,\cdots,12\}$. Se ordenarmos todos esses subconjuntos por ordem crescente de índices, em quantos subconjuntos o elemento $8$ aparece na posição 3 da sua ordenação? \begin{block}{Solução:} \begin{itemize} \item 5 posições com o 8 aparecendo na posição 3. \item Nas posições 1 e 2, devemos ter números menores que 8. \item Nas posições 4 e 5, devemos ter números maiores que 8. \item Escolher 2 em $\{1,\ldots.7\}$ e escolher 2 em $\{9,\ldots,12\}$. \end{itemize} \[ \binom{7}{2}\cdot 1\cdot \binom{4}{2}\ =\ \frac{7\cdot 6}{2\cdot 1}\cdot\frac{4\cdot 3}{2\cdot 1}\ =\ 7\cdot 6\cdot 3\ =\ \cor{126} \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Exercício 9(a) da Lista 3} \begin{itemize} \item Quantas soluções inteiras existem para $x_1+x_2+x_3+x_4=50$ com $x_i\geq 0$? \end{itemize} \begin{block}{Solução:} \begin{itemize} \item É equivalente a $x'_1+x'_2+x'_3+x'_4=54$ com $x'_i\geq 1$, fazendo $x'_i=x_i+1$ \item Dividir colocando 3 barras entre os 54 doces. \end{itemize} \[ \binom{53}{3}\ =\ \binom{50+4-1}{4-1}\ =\ \binom{50+4-1}{50} \] Fórmula geral: $p$ variáveis naturais que somam $n$: \[ \binom{n+p-1}{p-1}\ =\ \binom{n+p-1}{n} \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Exercício 9(a)' da Lista 3} \begin{itemize} \item Quantas soluções inteiras existem para $x_1+x_2+x_3+x_4+x_5=50$ com $x_1\geq -2, x_2\geq -1, x_3\geq 0$, $x_4\geq 1$ e $x_5\geq 2$? \end{itemize} \begin{block}{Solução:} \begin{itemize} \item É equivalente a $x'_1+x'_2+x'_3+x'_4+x'_5=55$ com $x'_i\geq 1$, fazendo $x'_1=x_1+3$, $x'_2=x_2+2$, $x'_3=x_3+1$, $x'_4=x_4$ e $x'_5=x_5-1$, pois. \item $x_1+x_2+x_3+x_4+x_5=50\ \Tto$ \item $\Tto\ (x'_1-3)+(x'_2-2)+(x'_3-1)+(x'_4)+(x'_5+1)=50\ \Tto$ \item $\Tto\ x'_1+x'_2+x'_3+x'_4+x'_5=55$. \item Dividir colocando 4 barras entre os 55 doces. \end{itemize} \[ \binom{54}{4}\ =\ \binom{50+5-1}{5-1}\ =\ \binom{50+5-1}{50} \] Fórmula geral: $p$ variáveis naturais que somam $n$: \[ \binom{n+p-1}{p-1}\ =\ \binom{n+p-1}{n} \] \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Exercício 11 da Lista 3} Determine o coeficiente de $x^3$ no desenvolvimento de \[ \left( x^2 + \frac{1}{x^3} \right)^{99} \ \ \ \ \ \ \ \mbox{ e }\ \ \mbox{ de }\ \ \ \ \ \ \ \left( x^2 + \frac{1}{x^3} \right)^{100} \] \begin{block}{Solução:} \[ \cor{(a+b)^n\ \ =\ \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k} \] \[ (x^2+x^{-3})^{99}\ =\ \sum_{k=0}^{99}\binom{99}{k}x^{2(99-k)}x^{-3k}\ =\ \sum_{k=0}^{99}\binom{99}{k}x^{2\cdot 99-5k} \] $5k=198-3=195\ \tto\ k=39$. \textbf{Coeficiente:} \cor{$\binom{99}{39}=\binom{99}{60}$} \[ (x^2+x^{-3})^{100}\ =\ \sum_{k=0}^{100}\binom{100}{k}x^{2(100-k)}x^{-3k}\ =\ \sum_{k=0}^{100}\binom{100}{k}x^{2\cdot 100-5k} \] $5k=200-3=197\ \Tto\ k=197/3$. \textbf{Coeficiente:} \alert{0 (não existe $x^3$)}. \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.7 - Permutações e Arranjos Circulares} \begin{block}{Exercício 11.32 (a)} \begin{align*} Resposta_1\ &=\ \binom{10}{5}\cdot\frac{5!}{5}\ =\ \frac{10!}{5!\cnot{5!}}\cdot\frac{\cnot{5!}}{5}\ =\ \frac{10\cdot 9\cdot 8\cdot 7\cdot 6\cdot\cnot{5!}}{\cnot{5!}\cdot 5}\ =\ \cor{6048}\\ Resposta_2\ &=\ \frac{10!}{5!}\cdot\frac{1}{5}\ =\ \cor{6048}\\ Resposta_3\ &=\ \Big(10\cdot 9\cdot 8\cdot 7\cdot 6\Big)\cdot\frac{1}{5}\ =\ \cor{6048} \end{align*} \end{block} \begin{block}{Exercício 11.32 (b)} \begin{align*} Resposta_1\ &=\ \binom{10}{5}\cdot\frac{5!}{5}\cdot\frac{5!}{5}\ =\ \frac{10!}{\cnot{5!}\cnot{5!}}\cdot\frac{\cnot{5!}}{5}\cdot\frac{\cnot{5!}}{5}\ =\ \frac{10!}{25}\ =\ \cor{145152}\\ Resposta_2\ &=\ \Big(10!\Big)\cdot\frac{1}{5}\cdot\frac{1}{5}\ =\ \cor{145152\ =\ 6048\cdot 4!}\\ \end{align*} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.10 - Combinações múltiplas} \begin{block}{Exercício 11.35} Quantas maneiras existem de distribuir 5 cartas para cada um de 4 jogadores, de um baralho de 52 cartas? \end{block} \begin{block}{Solução} \begin{align*} Resposta_1\ &=\ \binom{52}{5}\cdot\binom{47}{5}\cdot\binom{42}{5}\cdot\binom{37}{5}\ =\ \frac{52!}{5!\cnot{47!}}\cdot\frac{\cnot{47!}}{5!\cnot{42!}}\cdot\frac{\cnot{42!}}{5!\cnot{37!}}\cdot\frac{\cnot{37!}}{5!32!}\\ &=\ \cor{\frac{52!}{5!5!5!5!32!}}\\ Resposta_2\ &=\ \cor{\binom{52}{5,5,5,5,32}}\ =\ \frac{52!}{5!5!5!5!32!} \end{align*} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.10 - Combinações múltiplas} \begin{block}{Exercício 11.36} Quantas maneiras distintas existem de pintar 20 casas com as cores \alert{vermelha}, \cor{azul}, \corB{verde} e \textcolor{yellow}{\bf amarela} (cada casa de uma só cor), sendo que deve haver o mesmo número (5) de casas de cada cor? \end{block} \begin{block}{Solução} \begin{align*} Resposta_1\ &=\ \binom{20}{5}\cdot\binom{15}{5}\cdot\binom{10}{5}\cdot\binom{5}{5}\ =\ \frac{20!}{5!\cnot{15!}}\cdot\frac{\cnot{15!}}{5!\cnot{10!}}\cdot\frac{\cnot{10!}}{5!\cnot{5!}}\cdot\frac{\cnot{5!}}{5!0!}\\ &=\ \cor{\frac{20!}{5!5!5!5!}}\\ Resposta_2\ &=\ \cor{\binom{20}{5,5,5,5}}\ =\ \frac{20!}{5!5!5!5!} \end{align*} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.10 - Combinações múltiplas} \begin{block}{Exercício 11.38} Quantas maneiras há de dividir 16 alunos em 3 grupos de estudo, para Física, Química e Matemática; sendo que deve haver 6 alunos em cada um dos dois primeiros grupos, e 4 no último? \end{block} \begin{block}{Solução} \begin{align*} Resposta_1\ &=\ \binom{16}{6}\cdot\binom{10}{6}\cdot\binom{4}{4}\ =\ \frac{16!}{6!\cnot{10!}}\cdot\frac{\cnot{10!}}{6!4!}\ =\ \cor{\frac{16!}{6!6!4!}}\\ Resposta_2\ &=\ \cor{\binom{16}{6,6,4}}\ =\ \frac{16!}{6!6!4!} \end{align*} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.9 - Permutações com alguns elementos iguais} \begin{block}{Exemplo: Anagramas} Quantos anagramas existem da palavra BANANAS? \end{block} \begin{block}{Solução} \begin{align*} Resposta_1\ &=\ \cor{\frac{7!}{3!2!}}\\ Resposta_2\ &=\ \binom{7}{1}\cdot\binom{6}{3}\cdot\binom{3}{2}\cdot\binom{1}{1}\ =\ \frac{7!}{1!\cnot{6!}}\cdot\frac{\cnot{6!}}{3!\cnot{3!}}\cdot\frac{\cnot{3!}}{2!\cnot{1!}}\cdot\frac{\cnot{1!}}{1!0!}\\ &=\ \cor{\frac{7!}{1!3!2!1!}}\\ Resposta_3\ &=\ \cor{\binom{7}{1,3,2,1}}\ =\ \frac{7!}{1!3!2!1!} \end{align*} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.9 - Permutações com alguns elementos iguais} \begin{block}{Exemplo: Anagramas} Quantos anagramas existem da palavra PARALELEPIPEDO? \end{block} \begin{block}{Solução} (P,E,A,L,R,I,D,O)=(3,3,2,2,1,1,1,1). Total: 14 letras. \begin{align*} Resposta_1\ &=\ \cor{\frac{14!}{3!3!2!2!}}\\ Resposta_2\ &=\ \binom{14}{3}\cdot\binom{11}{3}\cdot\binom{8}{2}\cdot\binom{6}{2}\cdot 4!\ =\ \frac{14!}{3!\cnot{11!}}\cdot\frac{\cnot{11!}}{3!\cnot{8!}}\cdot\frac{\cnot{8!}}{2!\cnot{6!}}\cdot\frac{\cnot{6!}}{2!\cnot{4!}}\cdot\cnot{4!}\\ &=\ \cor{\frac{14!}{3!3!2!2!}}\\ Resposta_3\ &=\ \cor{\binom{14}{3,3,2,2,1,1,1,1}}\ =\ \frac{14!}{3!3!2!2!} \end{align*} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 11.41:} Uma roleta tem 10 setores numerados. Deve-se pintar cada setor com uma cor diferente das de seus dois vizinhos. Há 5 cores disponíveis. De quantas maneiras podemos pintar essa roleta? \begin{block}{Solução:} \textbf{$1^o$ tentativa:} Escolhe uma das 5 cores para o setor 1, depois uma das 4 cores para o setor 2, 4 cores para o setor 3, $\ldots$ e 4 cores para o setor 9.\\ Falta escolher as cores do setor 10. Até aí temos $5\cdot 4^{n-2}$ possibilidades.\\ Para o setor 10, temos 3 ou 4 possibilidades, dependendo se a cor do setor 9 é diferente ou igual a do setor 1. \textit{Não parece ser fácil por aí...} \end{block} \begin{figure}\centering \includegraphics[scale=0.3]{circ-div10a.png} %\caption{} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 11.41:} Uma roleta tem 10 setores numerados. Deve-se pintar cada setor com uma cor diferente das de seus dois vizinhos. Há 5 cores disponíveis. De quantas maneiras podemos pintar essa roleta? \begin{block}{Solução:} \textbf{$2^o$ tentativa:} Recorrência. Seja $a_n$ o número de modos de pintar uma roleta com $n$ setores. Queremos calcular $a_{10}$.\\ $\mathbf{a_2=}5\cdot 4=20,\ \ \mathbf{a_3=}5\cdot 4\cdot 3=60,\ \ \mathbf{a_4=}5\cdot 4\cdot 3\cdot 3\ +\ 5\cdot 1\cdot 4\cdot 4\ =\ 260$\\ \end{block} \begin{figure}\centering \includegraphics[scale=0.3]{circ-div10c.png} %\caption{} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 11.41:} Uma roleta tem 10 setores numerados. Deve-se pintar cada setor com uma cor diferente das de seus dois vizinhos. Há 5 cores disponíveis. De quantas maneiras podemos pintar essa roleta? \begin{block}{Solução:} \textbf{$2^o$ tentativa:} Recorrência. Seja $a_n$ o número de modos de pintar uma roleta com $n$ setores. Queremos calcular $a_{10}$.\\ $\mathbf{a_2=}20,\ \ \ \ \ \ \ \mathbf{a_3=}60,\ \ \ \ \ \ \ \mathbf{a_4=}260$\\ \cor{$a_n\ =\ 3a_{n-1}+4a_{n-2}$}, para $n\geq 5$\\ \end{block} \begin{figure}\centering \includegraphics[scale=0.3]{circ-div10b.png} %\caption{} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 11.41:} Uma roleta tem 10 setores numerados. Deve-se pintar cada setor com uma cor diferente das de seus dois vizinhos. Há 5 cores disponíveis. De quantas maneiras podemos pintar essa roleta? \begin{block}{Solução:} \textbf{$2^o$ tentativa:} Recorrência. Seja $a_n$ o número de modos de pintar uma roleta com $n$ setores. Queremos calcular $a_{10}$.\\ $\mathbf{a_2=}20,\ \ \ \ \ \ \ \mathbf{a_3=}60,\ \ \ \ \ \ \ \mathbf{a_4=}260$\\ \cor{$a_n\ =\ 3a_{n-1}+4a_{n-2}$}, para $n\geq 5$\\ \vspace{0.5cm} Recorrência de 2$^o$-ordem: \alert{eq. caract.} $\mathbf{x^2-3x-4=0}$\\ Raízes $\mathbf{r_1=4}$ e $\mathbf{r_2=-1}$\ \ \ $\Tto$\ \ \ \cor{$a_n\ =\ c_1\cdot 4^n+c_2\cdot(-1)^n$}\\ Podemos calcular facilmente $c_1=1$ e $c_2=4$ com os valores de $a_2$ e $a_3$.\\ \vspace{0.5cm} $\cor{\mathbf{a_n\ =\ 4^n\ +\ 4\cdot(-1)^n}}$,\ \ \ para $n\geq 2$. %$a_1$ é um caso especial, que deve ser considerado separadamente. \vspace{0.5cm} $\mathbf{a_{10}}\ =4^{10}+4\cdot(-1)^{10}\ =\ (1024)^2+4\ =\ \mathbf{1.048.580}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 11.41'':} Uma roleta tem $n$ setores numerados. Deve-se pintar cada setor com uma cor diferente das de seus dois vizinhos. Há $k+1$ cores disponíveis. De quantas maneiras podemos pintar essa roleta? \begin{block}{Solução:} \textbf{$1^o$ tentativa:} Escolhe uma das $k+1$ cores para o setor 1, depois uma das $k$ cores para o setor 2, $\ldots$ e $k$ cores para o setor $n-1$.\\ Faltam as cores do setor $n$. Até aí temos $(k+1)\cdot k^{n-2}$ possibilidades.\\ Para o setor $n$, temos $k-1$ ou $k$ possibilidades, dependendo se a cor do setor $n-1$ é diferente ou igual a do setor 1. \textit{Não parece ser fácil por aí...} \end{block} \begin{figure}\centering \includegraphics[scale=0.3]{circ-div10ak.png} %\caption{} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 11.41'':} Uma roleta tem $n$ setores numerados. Deve-se pintar cada setor com uma cor diferente das de seus dois vizinhos. Há $k+1$ cores disponíveis. De quantas maneiras podemos pintar essa roleta? \begin{block}{Solução:} \textbf{$2^o$ tentativa:} Recorrência. Seja $a_n$ o número de modos de pintar uma roleta com $n$ setores usando $k+1$ cores.\\ $\mathbf{a_2=}(k+1)\cdot k=\mathbf{k^2+k},\ \ \mathbf{a_3=}(k+1)\cdot k\cdot(k-1)\ =\ \mathbf{k^3-k}$\\ $\mathbf{a_4=}(k+1)\cdot k\cdot(k-1)^2\ +\ (k+1)\cdot 1\cdot k^2\ =\ \mathbf{k^4+k}$\\ \end{block} \begin{figure}\centering \includegraphics[scale=0.3]{circ-div10ck.png} %\caption{} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 11.41'':} Uma roleta tem $n$ setores numerados. Deve-se pintar cada setor com uma cor diferente das de seus dois vizinhos. Há $k+1$ cores disponíveis. De quantas maneiras podemos pintar essa roleta? \begin{block}{Solução:} \textbf{$2^o$ tentativa:} Recorrência. Seja $a_n$ o número de modos de pintar uma roleta com $n$ setores usando $k+1$ cores.\\ $\mathbf{a_2=}\mathbf{k^2+k},\ \ \ \ \ \mathbf{a_3=}\mathbf{k^3-k},\ \ \ \ \ \mathbf{a_4=}\mathbf{k^4+k}$\\ \cor{$a_n\ =\ (k-1)\cdot a_{n-1}+k\cdot a_{n-2}$}, para $n\geq 5$\\ \end{block} \begin{figure}\centering \includegraphics[scale=0.3]{circ-div10bk.png} %\caption{} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 11.41'':} Uma roleta tem $n$ setores numerados. Deve-se pintar cada setor com uma cor diferente das de seus dois vizinhos. Há $k+1$ cores disponíveis. De quantas maneiras podemos pintar essa roleta? \begin{block}{Solução:} \textbf{$2^o$ tentativa:} Recorrência. Seja $a_n$ o número de modos de pintar uma roleta com $n$ setores usando $k+1$ cores.\\ $\mathbf{a_2=k^2+k},\ \ \ \ \ \mathbf{a_3=k^3-k},\ \ \ \ \ \mathbf{a_4=k^4+k}$\\ \cor{$a_n\ =\ (k-1)\cdot a_{n-1}+k\cdot a_{n-2}$}, para $n\geq 5$\\ \vspace{0.5cm} Recorrência de 2$^o$-ordem: \alert{eq. caract.} $\mathbf{x^2-(k-1)x-k=0}$\\ Raízes $\mathbf{r_1=k}$ e $\mathbf{r_2=-1}$\ \ \ $\Tto$\ \ \ \cor{$a_n\ =\ c_1\cdot k^n+c_2\cdot(-1)^n$}\\ Podemos calcular facilmente $c_1=1$ e $c_2=k$ com os valores de $a_2$ e $a_3$.\\ \vspace{0.5cm} $\cor{\mathbf{a_n\ =\ k^n\ +\ k\cdot(-1)^n}}$,\ \ \ para $n\geq 2$.\\ %$a_1 é um caso especial, que deve ser considerado separadamente. \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 10(b) - Lista 3:} ${p+n+1\choose p+1}\ =\ \sum_{r = 0}^n {p+r\choose p}\ =\ \binom{p}{p}+\binom{p+1}{p}+\binom{p+2}{p}+\ldots+\binom{p+n-1}{p}+\binom{p+n}{p}$ \begin{block}{Resolução: equação $x_1+x_2+\ldots+x_{p+1}+x_{p+2}=n$} Número de soluções naturais: $\binom{n+(p+2)-1}{(p+2)-1}\ =\ \mathbf{\binom{p+n+1}{p+1}}$\\ \textbf{Resolução alternativa:}\\ \cor{Caso 0:} $x_{p+2}=0\ \Tto$\ \textbf{n$^o$ soluções:} $\binom{(n-0)+(p+1)-1}{(p+1)-1}\ =\ \binom{p+n}{p}$\\ \cor{Caso 1:} $x_{p+2}=1\ \Tto$\ \textbf{n$^o$ soluções:} $\binom{(n-1)+(p+1)-1}{(p+1)-1}\ =\ \binom{p+n-1}{p}$\\ \cor{Caso 2:} $x_{p+2}=2\ \Tto$\ \textbf{n$^o$ soluções:} $\binom{(n-2)+(p+1)-1}{(p+1)-1}\ =\ \binom{p+n-2}{p}$\\ \cor{Caso 3:} $x_{p+2}=3\ \Tto$\ \textbf{n$^o$ soluções:} $\binom{(n-3)+(p+1)-1}{(p+1)-1}\ =\ \binom{p+n-3}{p}$\\ $\ldots$\\ $\ldots$\\ \cor{Caso $n$:} $x_{p+2}=n\ \Tto$\ \textbf{n$^o$ soluções:} $\binom{(n-n)+(p+1)-1}{(p+1)-1}\ =\ \binom{p}{p}$\\ \vspace{0.5cm} Pelo \cor{princípio aditivo da contagem}, temos por \textbf{dupla contagem}:\\ ${p+n+1\choose p+1}\ =\ \sum_{r = 0}^n {p+r\choose p}\ =\ \binom{p}{p}+\binom{p+1}{p}+\binom{p+2}{p}+\ldots+\binom{p+n-1}{p}+\binom{p+n}{p}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 10(b) - Lista 3:} ${p+n+1\choose p+1}\ =\ \sum_{r = 0}^n {p+r\choose p}\ =\ \binom{p}{p}+\binom{p+1}{p}+\binom{p+2}{p}+\ldots+\binom{p+n-1}{p}+\binom{p+n}{p}$ \vspace{2cm} {\bf Exercício 10(a) - Lista 3:} ${n+p+1\choose p}\ =\ \sum_{r = 0}^p {n+r\choose r}\ =\ \binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\ldots+\binom{n+p-1}{p-1}+\binom{n+p}{p}$ \begin{block}{Resolução:} $\sum_{r = 0}^p {n+r\choose r}\ =\ \sum_{r = 0}^p {n+r\choose n}\ \EqB{(b)}\ \binom{n+p+1}{n+1}\ =\ \binom{n+p+1}{p}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 10(c) - Lista 3:} $\binom{n+2}{p+2}\ =\ \binom{n}{p}+2\cdot\binom{n}{p+1}+\binom{n}{p+2}$ \vspace{0.5cm} \begin{block}{Resolução:} Em um grupo de $n$ homens e 2 mulheres, selecionar $p+2$ pessoas.\\ Total: $\binom{n+2}{p+2}$ \vspace{0.5cm} \textbf{Resolução alternativa:}\\ \cor{Caso 2:} Tem 2 mulheres: \ \ \ \ \ $\binom{n}{p}$\\ \cor{Caso 1:} Tem 1 mulher:\ \ \ \ $2\cdot\binom{n}{p+1}$\\ \cor{Caso 0:} Tem 0 mulheres:\ \ \ \ \ $\binom{n}{p+2}$\\ \vspace{0.5cm} Pelo \cor{princípio aditivo da contagem}, temos por \textbf{dupla contagem}:\\ $\binom{n+2}{p+2}\ =\ \binom{n}{p}+2\cdot\binom{n}{p+1}+\binom{n}{p+2}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 10(d) - Lista 3:} $\binom{n+3}{p+3}\ =\ \binom{n}{p}+3\cdot\binom{n}{p+1}+3\cdot\binom{n}{p+2}+\binom{n}{p+3}$ \vspace{0.5cm} \begin{block}{Resolução:} Em um grupo de $n$ homens e 3 mulheres, selecionar $p+3$ pessoas.\\ Total: $\binom{n+3}{p+3}$ \vspace{0.5cm} \textbf{Resolução alternativa:}\\ \cor{Caso 3:} Tem 3 mulheres:\ \ \ \ \ \ \ $\binom{n}{p}$\\ \cor{Caso 2:} Tem 2 mulheres: $3\cdot\binom{n}{p+1}$\\ \cor{Caso 1:} Tem 1 mulher:\ \ \ \ $3\cdot\binom{n}{p+2}$\\ \cor{Caso 0:} Tem 0 mulheres:\ \ \ \ \ $\binom{n}{p+3}$\\ \vspace{0.5cm} Pelo \cor{princípio aditivo da contagem}, temos por \textbf{dupla contagem}:\\ $\binom{n+3}{p+3}\ =\ \binom{n}{p}+3\cdot\binom{n}{p+1}+3\cdot\binom{n}{p+2}+\binom{n}{p+3}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 10(e) - Lista 3:} $\binom{n+4}{p+4}\ =\ \binom{n}{p}+4\cdot\binom{n}{p+1}+6\cdot\binom{n}{p+2}+4\cdot\binom{n}{p+3}+\binom{n}{p+4}$ \vspace{0.5cm} \begin{block}{Resolução:} Em um grupo de $n$ homens e 4 mulheres, selecionar $p+4$ pessoas.\\ Total: $\binom{n+4}{p+4}$ \vspace{0.5cm} \textbf{Resolução alternativa:}\\ \cor{Caso 4:} Tem 4 mulheres: \ \ \ \ $\binom{n}{p}$\\ \cor{Caso 3:} Tem 3 mulheres: $4\cdot\binom{n}{p+1}$\\ \cor{Caso 2:} Tem 2 mulheres: $6\cdot\binom{n}{p+2}$\\ \cor{Caso 1:} Tem 1 mulher:\ \ \ \ $4\cdot\binom{n}{p+3}$\\ \cor{Caso 0:} Tem 0 mulheres:\ \ \ \ \ $\binom{n}{p+4}$\\ \vspace{0.5cm} Pelo \cor{princípio aditivo da contagem}, temos por \textbf{dupla contagem}:\\ $\binom{n+4}{p+4}\ =\ \binom{n}{p}+4\cdot\binom{n}{p+1}+6\cdot\binom{n}{p+2}+4\cdot\binom{n}{p+3}+\binom{n}{p+4}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.11 - Princípio aditivo da contagem} {\bf Exercício 10(f) - Lista 3:} ${n+k\choose p+k} = \sum_{r=0}^k {k\choose r}\cdot{n\choose p+r}$ \vspace{0.2cm} \begin{block}{Resolução:} Em um grupo de $n$ homens e $k$ mulheres, selecionar $p+k$ pessoas.\\ Total: $\binom{n+k}{p+k}$ \vspace{0.2cm} \textbf{Resolução alternativa:}\\ \cor{Caso $0$:} Tem $k-0$ mulheres:\ \ \ \ \ \ \ \ \ \ \ $\binom{n}{p}$\\ \cor{Caso $1$:} Tem $k-1$ mulheres:\ \ \ \ \ \ $k\cdot\binom{n}{p+1}$\\ ..................................................................\\ \cor{Caso $r$:} Tem $k-r$ mulheres: $\binom{k}{k-r}\cdot\binom{n}{p+r}\ =\ \binom{k}{r}\cdot\binom{n}{p+r}$\\ ..................................................................\\ \cor{Caso $k-2$:} Tem $2$ mulheres: $\binom{k}{2}\cdot\binom{n}{p+k-2}\ =\ \binom{k}{k-2}\cdot\binom{n}{p+k-2}$\\ \cor{Caso $k-1$:} Tem 1 mulher:\ \ \ \ \ \ \ $k\cdot\binom{n}{p+k-1}\ =\ \binom{k}{k-1}\cdot\binom{n}{p+k-1}$\\ \cor{Caso $k-0$:} Tem 0 mulheres:\ \ \ \ \ \ \ \ \ \ $\binom{n}{p+k}$\\ \vspace{0.3cm} Pelo \cor{princípio aditivo da contagem}, temos por \textbf{dupla contagem}:\\ ${n+k\choose p+k} = \sum_{r=0}^k {k\choose r}\cdot{n\choose p+r}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Questão 10 Lista 3 (soluções alternativas)} {\bf Exercício 10(a) - Lista 3:} ${n+p+1\choose p}\ =\ \sum_{r = 0}^p {n+r\choose r}\ =\ \binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\ldots+\binom{n+p-1}{p-1}+\binom{n+p}{p}$ \vspace{0.3cm} \begin{block}{Resolução: Relação de Stifel ou Identidade de Pascal} $\ \binom{n}{0}\ \ +\binom{n+1}{1}+\binom{n+2}{2}+\binom{n+3}{3}+\ldots+\binom{n+p}{p}=$\\ $\binom{n+1}{0}+\binom{n+1}{1}+\binom{n+2}{2}+\binom{n+3}{3}+\ldots+\binom{n+p}{p}=$\\ $\binom{n+2}{1}+\binom{n+2}{2}+\binom{n+3}{3}+\binom{n+4}{4}+\ldots+\binom{n+p}{p}=$\\ $\binom{n+3}{2}+\binom{n+3}{3}+\binom{n+4}{4}+\binom{n+5}{5}+\ldots+\binom{n+p}{p}=$\\ $\binom{n+4}{3}+\binom{n+4}{4}+\binom{n+5}{5}+\binom{n+6}{6}+\ldots+\binom{n+p}{p}=$\\ $\binom{n+5}{4}+\binom{n+5}{5}+\binom{n+6}{6}+\binom{n+7}{7}+\ldots+\binom{n+p}{p}=$\\ ...........................................................................\\ $\binom{n+p-2}{p-3}+\binom{n+p-2}{p-2}+\binom{n+p-1}{p-1}+\binom{n+p}{p}=$\\ $\binom{n+p-1}{p-2}+\binom{n+p-1}{p-1}+\binom{n+p}{p}=$\\ $\binom{n+p}{p-1}+\binom{n+p}{p}=$\\ $\mathbf{\binom{n+p+1}{p}}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Questão 10 Lista 3 (soluções alternativas)} {\bf Exercício 10(b) - Lista 3:} ${p+n+1\choose p+1}\ =\ \sum_{r = 0}^n {p+r\choose p}\ =\ \binom{p}{p}+\binom{p+1}{p}+\binom{p+2}{p}+\ldots+\binom{p+n-1}{p}+\binom{p+n}{p}$ \vspace{0.3cm} \begin{block}{Resolução: Relação de Stifel ou Identidade de Pascal} $\ \binom{p}{p}\ \ +\binom{p+1}{p}+\binom{p+2}{p}+\binom{p+3}{p}+\ldots+\binom{p+n}{p}=$\\ $\binom{p+1}{0}+\binom{p+1}{1}+\binom{p+2}{2}+\binom{p+3}{3}+\ldots+\binom{p+n}{n}=$\\ $\binom{p+2}{1}+\binom{p+2}{2}+\binom{p+3}{3}+\binom{p+4}{4}+\ldots+\binom{p+n}{n}=$\\ $\binom{p+3}{2}+\binom{p+3}{3}+\binom{p+4}{4}+\binom{p+5}{5}+\ldots+\binom{p+n}{n}=$\\ $\binom{p+4}{3}+\binom{p+4}{4}+\binom{p+5}{5}+\binom{p+6}{6}+\ldots+\binom{p+n}{n}=$\\ $\binom{p+5}{4}+\binom{p+5}{5}+\binom{p+6}{6}+\binom{p+7}{7}+\ldots+\binom{p+n}{n}=$\\ ...........................................................................\\ $\binom{p+n-2}{n-3}+\binom{p+n-2}{n-2}+\binom{p+n-1}{n-1}+\binom{p+n}{n}=$\\ $\binom{p+n-1}{n-2}+\binom{p+n-1}{n-1}+\binom{p+n}{n}=$\\ $\binom{p+n}{n-1}+\binom{p+n}{n}=$\\ $\mathbf{\binom{p+n+1}{n}}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Questão 10 Lista 3 (soluções alternativas)} {\bf Exercício 10(c) - Lista 3:} $\binom{n+2}{p+2}\ =\ \binom{n}{p}+2\binom{n}{p+1}+\binom{n}{p+2}$ \vspace{1cm} \begin{block}{Resolução: Relação de Stifel ou Identidade de Pascal} $\binom{n}{p}\ \ \ +\ \ \ 2\binom{n}{p+1}\ \ +\ \ \binom{n}{p+2}=$\\ $\binom{n}{p}+\binom{n}{p+1}\ \ \ +\ \ \ \binom{n}{p+1}+\binom{n}{p+2}=$\\ \ \ \ $\binom{n+1}{p+1}\ \ \ \ \ \ \ \ +\ \ \ \ \ \ \ \ \binom{n+1}{p+2}=$\\ \vspace{1cm} \esp{20}$\mathbf{\binom{n+2}{p+2}}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Questão 10 Lista 3 (soluções alternativas)} {\bf Exercício 10(d) - Lista 3:} $\binom{n+3}{p+3}\ =\ \binom{n}{p}+3\binom{n}{p+1}+3\binom{n}{p+2}+\binom{n}{p+3}$ \vspace{1cm} \begin{block}{Resolução: Relação de Stifel ou Identidade de Pascal} $\binom{n}{p}+\esp{8}3\binom{n}{p+1}+\esp{20}3\binom{n}{p+2}+\esp{10}\binom{n}{p+3}=$\\ $\binom{n}{p}+\binom{n}{p+1}\ \ \ +\ \ \ 2\binom{n}{p+1}+2\binom{n}{p+2}\ \ \ +\ \ \ \binom{n}{p+2}+\binom{n}{p+3}=$\\ \ \ \ $\binom{n+1}{p+1}\ \ \ \ \ \ \ \ +\ \ \ \ \ \ \ \ 2\binom{n+1}{p+2}\ \ \ \ \ \ \ \ +\ \ \ \ \ \ \ \ \binom{n+1}{p+3}\esp{15}\EqB{(c)}$\\ \vspace{1cm} $\mathbf{\binom{n+3}{p+3}}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Questão 10 Lista 3 (soluções alternativas)} {\bf Exercício 10(e) - Lista 3:} $\binom{n+4}{p+4}\ =\ \binom{n}{p}+4\cdot\binom{n}{p+1}+6\cdot\binom{n}{p+2}+4\cdot\binom{n}{p+3}+\binom{n}{p+4}$ \vspace{0.3cm} \begin{block}{Resolução: Relação de Stifel ou Identidade de Pascal} $\binom{n}{p}\ \ +\ \ 4\binom{n}{p+1}+\esp{16}6\binom{n}{p+2}+\esp{16}4\binom{n}{p+3}\ \ \ +\binom{n}{p+4}=$\\ $\binom{n}{p}+\binom{n}{p+1}\ \ \ +\ \ \ 3\binom{n}{p+1}+3\binom{n}{p+2}\ \ \ +\ \ \ 3\binom{n}{p+2}+3\binom{n}{p+3}\ \ \ +\ \ \ \binom{n}{p+3}+\binom{n}{p+4}=$\\ $\binom{n+1}{p+1}\ \ \ \ \ \ \ \ \ \ +\ \ \ \ \ \ \ \ \ \ 3\binom{n+1}{p+2}\ \ \ \ \ \ \ \ \ \ +\ \ \ \ \ \ \ \ \ \ 3\binom{n+1}{p+3}\ \ \ \ \ \ \ \ \ \ +\ \ \ \ \ \ \ \ \ \ \binom{n+1}{p+4}\esp{5}\EqB{(d)}$\\ \vspace{0.5cm} $\mathbf{\binom{n+4}{p+4}}$ \end{block} \vspace{0.8cm} {\bf Exercício 10(f) - Lista 3:} ${n+k\choose p+k} = \sum_{r=0}^k {k\choose r}\cdot{n\choose p+r}$\\ É possível provar por indução em $k$ usando esse mesmo esquema. } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.12 - Princípio Subtrativo da Contagem} {\bf Exercício 11.43:} Quantas mãos de 4 cartas podem ser tiradas de um baralho comum (de 52 cartas) nas quais aparecem pelo menos dois ases? \vspace{0.4cm} \begin{block}{Solução pelo Princípio Subtrativo: Tudo menos 0 ou 1 Ás} Total = $\binom{52}{4}$\\ Complemento (no máximo 1 Ás):\ $\binom{48}{4}\ +\ 4\cdot\binom{48}{3}$\\ Resultado = $\binom{52}{4}-\binom{48}{4}-4\cdot\binom{48}{3}\ =\ \frac{52!}{4!48!}-\frac{48!}{4!44!}-4\cdot\frac{48!}{3!45!}$\\ \vspace{0.3cm} \esp{15}$=\frac{52\cdot 51\cdot 50\cdot 49}{4\cdot 3\cdot 2\cdot 1}-\frac{48\cdot 47\cdot 46\cdot 45}{4\cdot 3\cdot 2\cdot 1}-4\cdot\frac{48\cdot 47\cdot 46}{3\cdot 2\cdot 1}\ =\ \textbf{\cor{6961}}$ \end{block} \vspace{0.4cm} \begin{block}{Solução pelo Princípio Aditivo: 4 Ases + 3 Ases + 2 Ases} Resultado = $\binom{4}{4}\binom{48}{0}\ +\ \binom{4}{3}\cdot\binom{48}{1}\ +\ \binom{4}{2}\binom{48}{2}\ =\ 1\ +\ 4\cdot 48\ +\ 6\cdot\frac{48\cdot 47}{2}\ =\ \textbf{\cor{6961}}$ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{\centering \huge{\alert{Capítulo 11.13\\INCLUSÃO E EXCLUSÃO}} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.13 - Princípio da Inclusão e Exclusão} $\mathbf{|A\cup B\cup C\cup D|\ =}\ \cor{|A|+|B|+|C|+|D|}\ \ \alert{-}$\\ \esp{10}$\alert{-|A\cap B|-|A\cap C|-|A\cap D|-|B\cap C|-|B\cap D|-|C\cap D|}\ \ \cor{+}$\\ \esp{10}$\cor{+|A\cap B\cap C|+|A\cap B\cap D|+|A\cap C\cap D|+|B\cap C\cap D|}\ \ \alert{-}$\\ \esp{10}$\alert{-|A\cap B\cap C\cap D|}$ \vspace{1.0cm} $\mathbf{|A\cup B\cup C\cup D\cup E|\ =}\ \cor{|A|+|B|+|C|+|D|+|E|}\ \ \alert{-}$\\ \esp{0}\alert{-|A$\cap$B|-|A$\cap$C|-|A$\cap$D|-|A$\cap$E|}%\\ \esp{0}\alert{-|B$\cap$C|-|B$\cap$D|-|B$\cap$E|-|C$\cap$D|-|C$\cap$E|-|D$\cap$E|}\ \ \cor{+}\\ \esp{0}\cor{+|A$\cap$B$\cap$C|+|A$\cap$B$\cap$D|+|A$\cap$B$\cap$E|+|A$\cap$C$\cap$D|+|A$\cap$C$\cap$E|+}\\ \esp{0}\cor{+|A$\cap$D$\cap$E|+|B$\cap$C$\cap$D|+|B$\cap$C$\cap$E|+|B$\cap$D$\cap$E|+|C$\cap$D$\cap$E|}\ \alert{$-$}\\ \esp{0}\alert{-|A$\cap$B$\cap$C$\cap$D|-|A$\cap$B$\cap$C$\cap$E|-|A$\cap$C$\cap$D$\cap$E|-|B$\cap$C$\cap$D$\cap$E|}\\ \esp{0}$\cor{+|A\cap B\cap C\cap D\cap E|}$ } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.13 - Princípio da Inclusão e Exclusão} \begin{figure}\centering \includegraphics[scale=0.25]{3circ-0.png} %\caption{} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.13 - Princípio da Inclusão e Exclusão} \begin{figure}\centering \includegraphics[scale=0.3]{4circ-0.png} %\caption{} \end{figure} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.13 - Princípio da Inclusão e Exclusão} {\bf Exercício:} Quantos números entre 1 e 60 não são divisíveis por 2, 3 ou 5? \vspace{0.2cm} \begin{block}{Solução pelo Princípio da Inclusão e Exclusão} $A_k$: conjunto dos múltiplos de $k$ de 1 a 60 $\Tto\ |A_k|=\left\lfloor\frac{60}{k}\right\rfloor$.\\ \vspace{0.1cm} \cor{$|A_2|=\left\lfloor\frac{60}{2}\right\rfloor\ =\ 30$}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cor{$|A_3|=\left\lfloor\frac{60}{3}\right\rfloor\ =\ 20$}\\ \cor{$|A_5|=\left\lfloor\frac{60}{5}\right\rfloor\ =\ 12$}\\ \alert{$|A_2\cap A_3|\ =|A_{2\cdot 3}|\ =\left\lfloor\frac{60}{6}\right\rfloor\ =\ 10$}\\ \alert{$|A_2\cap A_5|\ =|A_{2\cdot 5}|\ =\left\lfloor\frac{60}{10}\right\rfloor\ =\ 6$}\\ \alert{$|A_3\cap A_5|\ =|A_{3\cdot 5}|\ =\left\lfloor\frac{60}{15}\right\rfloor\ =\ 4$}\\ \cor{$|A_2\cap A_3\cap A_5|\ =|A_{2\cdot 3\cdot 5}|\ =\left\lfloor\frac{60}{30}\right\rfloor\ =\ 2$}\\ \vspace{0.5cm} Pelo Princípio da Inclusão e Exclusão, temos que:\\ $|A_2\cup A_3\cup A_5|\ =\ \cor{30+20+12}\alert{-10-6-4}\cor{+2}\ =\ \ \textbf{44}$ \vspace{0.5cm} \textbf{Resultado final} = 60 - 44 = \cor{\textbf{16}}\ \ \ (Princípio Subtrativo)\\ \textbf{1},7,11,13,17,19,23,29,31,37,41,43,47,\textbf{49},53,59 \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.13 - Princípio da Inclusão e Exclusão} {\bf Exercício:} Quantos números entre 1 e 1001 não são divisíveis por 7, 11 ou 13? \vspace{0.2cm} \begin{block}{Solução pelo Princípio da Inclusão e Exclusão} $A_k$: conjunto dos múltiplos de $k$ de 1 a 1001 $\Tto\ |A_k|=\left\lfloor\frac{1001}{k}\right\rfloor$.\\ \vspace{0.1cm} \cor{$|A_7|=\left\lfloor\frac{1001}{7}\right\rfloor\ =\ 143$}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cor{$|A_{11}|=\left\lfloor\frac{1001}{11}\right\rfloor\ =\ 91$}\\ \cor{$|A_{13}|=\left\lfloor\frac{1001}{13}\right\rfloor\ =\ 77$}\\ \alert{$|A_7\cap A_{11}|\ =|A_{7\cdot 11}|\ =\left\lfloor\frac{1001}{77}\right\rfloor\ =\ 13$}\\ \alert{$|A_7\cap A_{13}|\ =|A_{7\cdot 13}|\ =\left\lfloor\frac{1001}{91}\right\rfloor\ =\ 11$}\\ \alert{$|A_{11}\cap A_{13}|\ =|A_{11\cdot 13}|\ =\left\lfloor\frac{1001}{143}\right\rfloor\ =\ 7$}\\ \cor{$|A_7\cap A_{11}\cap A_{13}|\ =|A_{7\cdot 11\cdot 13}|\ =\left\lfloor\frac{1001}{1001}\right\rfloor\ =\ 1$}\\ \vspace{0.5cm} Pelo Princípio da Inclusão e Exclusão, temos que:\\ $|A_7\cup A_{11}\cup A_{13}|\ =\ \cor{143+91+77}\alert{-13-11-7}\cor{+1}\ =\ \ \textbf{281}$ \vspace{0.5cm} \textbf{Resultado final} = 1001 - 281 = \cor{\textbf{720}}\ \ \ (Princípio Subtrativo)\\ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.13 - Princípio da Inclusão e Exclusão} {\bf Ex. 02 da Lista 3:} Quantos números entre 1 e 350.000 não são divisíveis por 7, 11, 13, 17 ou 19? \vspace{0.2cm} \begin{block}{Solução pelo Princípio da Inclusão e Exclusão} $A_k$: conjunto dos múltiplos de $k$ de 1 a 350.000 $\Tto\ |A_k|=\left\lfloor\frac{350.000}{k}\right\rfloor$.\\ \vspace{0.1cm} \cor{$|A_7|=\left\lfloor\frac{350.000}{7}\right\rfloor\ =\ 50000$}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cor{$|A_{11}|=\left\lfloor\frac{350.000}{11}\right\rfloor\ =\ 31818$}\\ \cor{$|A_{13}|=\left\lfloor\frac{350.000}{13}\right\rfloor\ =\ 26923$}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \cor{$|A_{17}|=\left\lfloor\frac{350.000}{17}\right\rfloor\ =\ 20588$}\\ \cor{$|A_{19}|=\left\lfloor\frac{350.000}{19}\right\rfloor\ =\ 18421$}\\ \alert{$|A_7\cap A_{11}|\ =|A_{7\cdot 11}|\ =\left\lfloor\frac{350.000}{7\cdot 11}\right\rfloor\ =\ 4545$}\\ \alert{$|A_7\cap A_{13}|\ =|A_{7\cdot 13}|\ =\left\lfloor\frac{350.000}{7\cdot 13}\right\rfloor\ =\ 3846$}\\ \alert{$|A_7\cap A_{17}|\ =|A_{7\cdot 17}|\ =\left\lfloor\frac{350.000}{7\cdot 17}\right\rfloor\ =\ 2941$}\\ \alert{$|A_7\cap A_{19}|\ =|A_{7\cdot 19}|\ =\left\lfloor\frac{350.000}{7\cdot 19}\right\rfloor\ =\ 2631$}\\ \alert{$|A_{11}\cap A_{13}|=|A_{11\cdot 13}|=\left\lfloor\frac{350.000}{11\cdot 13}\right\rfloor\ =\ 2447$}\\ \alert{$|A_{11}\cap A_{17}|=|A_{11\cdot 17}|=\left\lfloor\frac{350.000}{11\cdot 17}\right\rfloor\ =\ 1871$}\\ \alert{$|A_{11}\cap A_{19}|=|A_{11\cdot 19}|=\left\lfloor\frac{350.000}{11\cdot 19}\right\rfloor\ =\ 1674$}\\ \alert{$|A_{13}\cap A_{17}|=|A_{13\cdot 17}|=\left\lfloor\frac{350.000}{13\cdot 17}\right\rfloor\ =\ 1583$}\\ \alert{$|A_{13}\cap A_{19}|=|A_{13\cdot 19}|=\left\lfloor\frac{350.000}{13\cdot 19}\right\rfloor\ =\ 1417$}\\ \alert{$|A_{17}\cap A_{19}|=|A_{17\cdot 19}|=\left\lfloor\frac{350.000}{17\cdot 19}\right\rfloor\ =\ 1083$} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.13 - Princípio da Inclusão e Exclusão} {\bf Ex. 02 da Lista 3:} Quantos números entre 1 e 350.000 não são divisíveis por 7, 11, 13, 17 ou 19? \vspace{0.2cm} \begin{block}{Solução pelo Princípio da Inclusão e Exclusão} $A_k$: conjunto dos múltiplos de $k$ de 1 a 350.000 $\Tto\ |A_k|=\left\lfloor\frac{350.000}{k}\right\rfloor$.\\ \vspace{0.1cm} \cor{$|A_7\cap A_{11}\cap A_{13}|\ =|A_{7\cdot 11\cdot 13}|\ =\left\lfloor\frac{350.000}{7\cdot 11\cdot 13}\right\rfloor\ =\ 349$}\\ \cor{$|A_7\cap A_{11}\cap A_{17}|\ =|A_{7\cdot 11\cdot 17}|\ =\left\lfloor\frac{350.000}{7\cdot 11\cdot 17}\right\rfloor\ =\ 267$}\\ \cor{$|A_7\cap A_{11}\cap A_{19}|\ =|A_{7\cdot 11\cdot 19}|\ =\left\lfloor\frac{350.000}{7\cdot 11\cdot 19}\right\rfloor\ =\ 239$}\\ \cor{$|A_7\cap A_{13}\cap A_{17}|\ =|A_{7\cdot 13\cdot 17}|\ =\left\lfloor\frac{350.000}{7\cdot 13\cdot 17}\right\rfloor\ =\ 226$}\\ \cor{$|A_7\cap A_{13}\cap A_{19}|\ =|A_{7\cdot 13\cdot 19}|\ =\left\lfloor\frac{350.000}{7\cdot 13\cdot 19}\right\rfloor\ =\ 202$}\\ \cor{$|A_7\cap A_{17}\cap A_{19}|\ =|A_{7\cdot 17\cdot 19}|\ =\left\lfloor\frac{350.000}{7\cdot 17\cdot 19}\right\rfloor\ =\ 154$}\\ \cor{$|A_{11}\cap A_{13}\cap A_{17}|=|A_{11\cdot 13\cdot 17}|=\left\lfloor\frac{350.000}{11\cdot 13\cdot 17}\right\rfloor\ =\ 143$}\\ \cor{$|A_{11}\cap A_{13}\cap A_{19}|=|A_{11\cdot 13\cdot 19}|=\left\lfloor\frac{350.000}{11\cdot 13\cdot 19}\right\rfloor\ =\ 128$}\\ \cor{$|A_{11}\cap A_{17}\cap A_{19}|=|A_{11\cdot 17\cdot 19}|=\left\lfloor\frac{350.000}{11\cdot 17\cdot 19}\right\rfloor\ =\ 98$}\\ \cor{$|A_{13}\cap A_{17}\cap A_{19}|=|A_{13\cdot 17\cdot 19}|=\left\lfloor\frac{350.000}{13\cdot 17\cdot 19}\right\rfloor\ =\ 83$}\\ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.13 - Princípio da Inclusão e Exclusão} {\bf Ex. 02 da Lista 3:} Quantos números entre 1 e 350.000 não são divisíveis por 7, 11, 13, 17 ou 19? \vspace{0.2cm} \begin{block}{Solução pelo Princípio da Inclusão e Exclusão} $A_k$: conjunto dos múltiplos de $k$ de 1 a 350.000 $\Tto\ |A_k|=\left\lfloor\frac{350.000}{k}\right\rfloor$.\\ \vspace{0.1cm} \alert{$|A_{7}\cap A_{11}\cap A_{13}\cap A_{17}|\ =|A_{7\cdot 11\cdot 13\cdot 17}|\ =\left\lfloor\frac{350.000}{7\cdot 11\cdot 13\cdot 17}\right\rfloor\ =\ 20$}\\ \alert{$|A_{7}\cap A_{11}\cap A_{13}\cap A_{19}|\ =|A_{7\cdot 11\cdot 13\cdot 19}|\ =\left\lfloor\frac{350.000}{7\cdot 11\cdot 13\cdot 19}\right\rfloor\ =\ 18$}\\ \alert{$|A_{7}\cap A_{11}\cap A_{17}\cap A_{19}|\ =|A_{7\cdot 11\cdot 17\cdot 19}|\ =\left\lfloor\frac{350.000}{7\cdot 11\cdot 17\cdot 19}\right\rfloor\ =\ 14$}\\ \alert{$|A_{7}\cap A_{13}\cap A_{17}\cap A_{19}|\ =|A_{7\cdot 13\cdot 17\cdot 19}|\ =\left\lfloor\frac{350.000}{7\cdot 13\cdot 17\cdot 19}\right\rfloor\ =\ 11$}\\ \alert{$|A_{11}\cap A_{13}\cap A_{17}\cap A_{19}|=|A_{11\cdot 13\cdot 17\cdot 19}|=\left\lfloor\frac{350.000}{11\cdot 13\cdot 17\cdot 19}\right\rfloor\ =\ 7$}\\ \vspace{1cm} \cor{$|A_{7}\cap A_{11}\cap A_{13}\cap A_{17}\cap A_{19}|=|A_{7\cdot 11\cdot 13\cdot 17\cdot 19}|=\left\lfloor\frac{350.000}{7\cdot 11\cdot 13\cdot 17\cdot 19}\right\rfloor\ =\ 1$}\\ \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.13 - Princípio da Inclusão e Exclusão} {\bf Ex. 02 da Lista 3:} Quantos números entre 1 e 350.000 não são divisíveis por 7, 11, 13, 17 ou 19? \vspace{0.5cm} \begin{block}{Solução pelo Princípio da Inclusão e Exclusão} Pelo Princípio da Inclusão e Exclusão, temos que: $|A_7\cup A_{11}\cup A_{13}\cup A_{17}\cup A_{19}|$\ =\ \cor{50000+31818+26923+20588+18421}\ \ \alert{$-$}\\ \alert{-4545-3846-2941-2631-2447-1871-1674-1583-1417-1083}\ \ \cor{$+$}\\ \cor{+349+267+239+226+202+154+143+128+98+83}\ \ \alert{$-$}\\ \alert{$-20-18-14-11-7$}\ \ \ \cor{+\ 1}\ \ =\ \ \textbf{125.532} \vspace{0.5cm} Pelo Princípio Subtrativo da Contagem:\\ \textbf{Resultado final} = 350.000 - 125.532 = \cor{\textbf{224.468}} \end{block} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \frame{ \frametitle{Seção 11.13 - Princípio da Inclusão e Exclusão} \[ |A_1\cup A_2\cup\ldots\cup A_n|\ =\ \cor{\sum_{i}|A_i|}\alert{-\sum_{i