API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 8th, 2020
319
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Latex 14.90 KB | None | 0 0
raw download clone embed print report
  1. \documentclass{article}
  2. \usepackage[utf8]{inputenc}
  3. \usepackage[portuguese]{babel}%
  4. \usepackage[shortlabels]{enumitem}
  5. \usepackage{amsfonts}
  6. \usepackage{amsmath}
  7. \usepackage{amssymb}
  8. \usepackage{setspace}
  9. \doublespacing
  10. \newtheorem{lemma}{Lema}
  11. \newtheorem{thm}{Teorema}
  12. \newtheorem{corollary}{Corolário}
  13. \newtheorem{definition}{Definição}
  14. \usepackage[margin=2cm]{geometry}
  15. \usepackage[divipsnames]{xcolor}
  16. \newenvironment{proof}[1][Prova]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
  17.  
  18. \title{Lista 1 - MAC0329}
  19. \author{Gustavo Korzune Gurgel\\No USP: 4778350}
  20. \date{Abril 2020}
  21.  
  22. \begin{document}
  23.  
  24. \maketitle
  25.  
  26. Irei demonstrar que a sêxtupla $\langle B^n,\,+,\,\cdot,\,-,\,\mathbf{0},\,\mathbf{1}  \rangle$ é uma álgebra booleana por meio dos axiomas da álgebra booleana.
  27.  
  28. \begin{proof}
  29.            A partir das próprias operações e identidades de $\langle B^n,\,+,\,\cdot,\,-,\,\mathbf{0},\,\mathbf{1}  \rangle$ definidas nas notas de aula, das operações e identidades $\langle B,\,\textcolor{magenta}{+},\,\textcolor{magenta}{\cdot},\,\textcolor{magenta}{-},\,\textcolor{magenta}{0},\,\textcolor{magenta}{1}  \rangle$ e do fato que $\langle B,\,\textcolor{magenta}{+},\,\textcolor{magenta}{\cdot},\,\textcolor{magenta}{-},\,\textcolor{magenta}{0},\,\textcolor{magenta}{1}  \rangle$ é uma álgebra booleana faremos todos os argumentos dessa prova.\\
  30.    Segue-se agora a prova de que os quatro axiomas da álgebra booleana são satisfeitos por $\langle B^n,\,+,\,\cdot,\,-,\,\mathbf{0},\,\mathbf{1}  \rangle$.
  31.        
  32.        \begin{enumerate}[1.]
  33.            \item \underline{As operações $+$ e $\cdot$ são comutativas:} \footnote{Repare que na Eq. \eqref{comut+} e Eq. \eqref{comut.} usamos, respectivamente, o fato que a operação $\textcolor{magenta}{+}$ é comutativa e que a operação $\textcolor{magenta}{\cdot}$ é comutativa.}
  34.  
  35.            \begin{equation}
  36.            \label{comut+}
  37.            \begin{split}
  38.                (x_1, \;x_2, \;\dots, \;x_{n}) + (y_1,\;y_2,\;\dots,\;y_{n}) = (x_1 \; \textcolor{magenta}{+} \; y_1, \; x_2 \; \textcolor{magenta}{+} \; y_2, \; \dots,\; x_{n} \; \textcolor{magenta}{+} \; y_{n})\\
  39.                = (y_1 \; \textcolor{magenta}{+} \; x_1, \; y_2 \; \textcolor{magenta}{+} \; x_2, \; \dots, \; y_{n} \; \textcolor{magenta}{+} \; x_{n}) \\
  40.                = (y_1,\;y_2,\;\dots,\;y_{n}) + (x_1, \;x_2, \;\dots, \;x_{n})
  41.            \end{split}
  42.            \end{equation}
  43.            Portanto, $$ (x_1, \;x_2, \;\dots, \;x_{n}) + (y_1,\;y_2,\;\dots,\;y_{n}) = (y_1,\;y_2,\;\dots,\;y_{n}) + (x_1, \;x_2, \;\dots, \;x_{n}) $$
  44.            Que, por definição, significa que $+$ é comutativa. \checkmark
  45.            
  46.            \begin{equation}
  47.            \label{comut.}
  48.            \begin{split}
  49.                (x_1, \;x_2, \;\dots, \;x_{n}) \cdot (y_1,\;y_2,\;\dots,\;y_{n}) = (x_1 \; \textcolor{magenta}{\cdot} \; y_1, \; x_2 \; \textcolor{magenta}{\cdot} \; y_2, \; \dots, \; x_{n} \; \textcolor{magenta}{\cdot} \; y_{n}) \\
  50.                = (y_1 \; \textcolor{magenta}{\cdot} \; x_1, \; y_2 \; \textcolor{magenta}{\cdot} \; x_2, \; \dots , \; y_{n} \; \textcolor{magenta}{\cdot} \; x_{n})\\
  51.                = (y_1,\;y_2,\;\dots,\;y_{n}) \cdot (x_1, \;x_2, \;\dots, \;x_{n})
  52.            \end{split}
  53.            \end{equation}
  54.            
  55.            Portanto, \newpage
  56.            $$ (x_1, \;x_2, \;\dots, \;x_{n}) \cdot (y_1,\;y_2,\;\dots,\;y_{n}) = (y_1,\;y_2,\;\dots,\;y_{n}) \cdot (x_1, \;x_2, \;\dots, \;x_{n}) $$
  57.            Que, por definição, significa que $\cdot$ é comutativa. \checkmark
  58.        
  59.            Sendo assim, $+$ e $\cdot$ são comutativas. \qquad $\square$
  60.        
  61.        \item \underline{$\cdot$ é distributiva em $+$, e, $+$ é distributiva em $\cdot$ :}
  62.        
  63.        \begin{equation*}
  64.            \begin{split}
  65.                (x_1, \;x_2, \;\dots, \;x_{n}) \cdot \big((y_1,\;y_2,\;\dots,\;y_{n}) + (z_1, \;z_2, \;\dots, \;z_{n})\big) = \\
  66.                (x_1, \;x_2, \;\dots, \;x_{n}) \cdot (y_1 \; \textcolor{magenta}{+} \; z_1, \; y_2 \; \textcolor{magenta}{+} \; z_2, \; \dots, \; y_{n} \; \textcolor{magenta}{+} \; z_{n}) = \\
  67.                \big(x_1 \textcolor{magenta}{\cdot} (y_1 \; \textcolor{magenta}{+} \; z_1), \; x_2 \textcolor{magenta}{\cdot} (y_2 \; \textcolor{magenta}{+} \; z_2), \; \dots, \; x_{n} \textcolor{magenta}{\cdot} (y_{n} \; \textcolor{magenta}{+} \; z_{n})\big)
  68.            \end{split}
  69.        \end{equation*}
  70.        
  71.        Sabemos das notas de aula que $\textcolor{magenta}{\cdot}$ é distributiva em $\textcolor{magenta}{+}$, e sabemos também que \\ $\forall i \in \{ 1, 2, ..., n \} (x_i \in B \, \wedge \, y_i \in B \, \wedge \, z_i \in B)$. Portanto,
  72.        
  73.        \begin{equation*}
  74.            \begin{split}
  75.                \big(x_1 \; \textcolor{magenta}{\cdot} \; (y_1 \; \textcolor{magenta}{+} \; z_1), \; x_2 \; \textcolor{magenta}{\cdot} \; (y_2 \; \textcolor{magenta}{+} \; z_2), \; \dots, \; x_{n} \; \textcolor{magenta}{\cdot} \; (y_{n} \; \textcolor{magenta}{+} \; z_{n})\big) = \\
  76.                \big((x_1 \; \textcolor{magenta}{\cdot} \; y_1) \; \textcolor{magenta}{+} \; (x_1 \; \textcolor{magenta}{\cdot} \; z_1), \; (x_2 \; \textcolor{magenta}{\cdot} \; y_2) \; \textcolor{magenta}{+} \; (x_2 \; \textcolor{magenta}{\cdot} \; z_2), \; \dots, \; (x_{n} \; \textcolor{magenta}{\cdot} \; y_{n}) \; \textcolor{magenta}{+} \; (x_{n} \; \textcolor{magenta}{\cdot} \; z_{n})\big) = \\
  77.                (x_1 \; \textcolor{magenta}{\cdot} \; y_1, \; x_2 \; \textcolor{magenta}{\cdot} \; y_2, \; \dots, \; x_{n} \; \textcolor{magenta}{\cdot} \; y_{n}) + (x_1 \; \textcolor{magenta}{\cdot} \; z_1, \; x_2 \; \textcolor{magenta}{\cdot} \; z_2, \; \dots, \;  x_{n} \; \textcolor{magenta}{\cdot} \; z_{n}) =\\
  78.                \big((x_1, \;x_2, \;\dots, \;x_{n}) \cdot (y_1,\;y_2,\;\dots,\;y_{n})\big) + \big((x_1, \;x_2, \;\dots, \;x_{n}) \cdot (z_1,\;z_2,\;\dots,\;z_{n})\big)
  79.            \end{split}
  80.        \end{equation*}
  81.    
  82.        
  83.        Portanto,
  84.        
  85.         \begin{equation*}
  86.            \begin{split}
  87.                (x_1, \;x_2, \;\dots, \;x_{n}) \cdot \big((y_1,\;y_2,\;\dots,\;y_{n}) + (z_1, \;z_2, \;\dots, \;z_{n})\big) = \\
  88.                \big((x_1, \;x_2, \;\dots, \;x_{n}) \cdot (y_1,\;y_2,\;\dots,\;y_{n})\big) + \big((x_1, \;x_2, \;\dots, \;x_{n}) \cdot (z_1,\;z_2,\;\dots,\;z_{n})\big)
  89.            \end{split}
  90.        \end{equation*}
  91.        
  92.        Que, por definição, significa que $\cdot$ é distributiva em $+$ \checkmark
  93.        
  94.         \begin{equation*}
  95.            \begin{split}
  96.                (x_1, \;x_2, \;\dots, \;x_{n}) + \big((y_1,\;y_2,\;\dots,\;y_{n}) \cdot (z_1, \;z_2, \;\dots, \;z_{n})\big) = \\
  97.                (x_1, \;x_2, \;\dots, \;x_{n}) + (y_1 \; \textcolor{magenta}{\cdot} \; z_1, \; y_2 \; \textcolor{magenta}{\cdot} \; z_2, \; \dots, \; y_{n} \; \textcolor{magenta}{\cdot} \; z_{n}) = \\
  98.                \big(x_1 \; \textcolor{magenta}{+} \; (y_1 \; \textcolor{magenta}{\cdot} \; z_1), \; x_2 \; \textcolor{magenta}{+} \; (y_2 \; \textcolor{magenta}{\cdot} \; z_2), \; \dots, \; x_{n} \; \textcolor{magenta}{+} \; (y_{n} \; \textcolor{magenta}{\cdot} \; z_{n})\big)
  99.            \end{split}
  100.        \end{equation*}
  101.        
  102.        Sabemos das notas de aula que $\textcolor{magenta}{+}$ é distributiva em $\textcolor{magenta}{\cdot}$, e sabemos também que \\ $\forall i \in \{ 1, 2, ..., n \} (x_i \in B \, \wedge \, y_i \in B \, \wedge \, z_i \in B)$. Portanto,
  103.        
  104.        \begin{equation*}
  105.            \begin{split}
  106.                \big(x_1 \; \textcolor{magenta}{+} \; (y_1 \; \textcolor{magenta}{\cdot} \; z_1), \; x_2 \; \textcolor{magenta}{+} \; (y_2 \; \textcolor{magenta}{\cdot} \; z_2), \; \dots, \; x_{n} \; \textcolor{magenta}{+} \; (y_{n} \; \textcolor{magenta}{\cdot} \; z_{n})\big) = \\
  107.                \big((x_1 \; \textcolor{magenta}{+} \; y_1) \; \textcolor{magenta}{\cdot} \; (x_1 \; \textcolor{magenta}{+} \; z_1), \; (x_2 \; \textcolor{magenta}{+} \; y_2) \; \textcolor{magenta}{\cdot} \; (x_2 \; \textcolor{magenta}{+} \; z_2), \; \dots, \; (x_{n} \; \textcolor{magenta}{+} \; y_{n}) \; \textcolor{magenta}{\cdot} \; (x_{n} \; \textcolor{magenta}{+} \; z_{n})\big) = \\
  108.                (x_1 \; \textcolor{magenta}{+} \; y_1, \; x_2 \; \textcolor{magenta}{+} \; y_2, \; \dots, \; x_{n} \; \textcolor{magenta}{+} \; y_{n}) \cdot (x_1 \; \textcolor{magenta}{+} \; z_1, \; x_2 \; \textcolor{magenta}{+} \; z_2, \; \dots, \;  x_{n} \; \textcolor{magenta}{+} \; z_{n}) =\\
  109.                \big((x_1, \;x_2, \;\dots, \;x_{n}) + (y_1,\;y_2,\;\dots,\;y_{n})\big) \cdot \big((x_1, \;x_2, \;\dots, \;x_{n}) + (z_1,\;z_2,\;\dots,\;z_{n})\big)
  110.            \end{split}
  111.        \end{equation*}
  112.        
  113.        Portanto,
  114.        
  115.         \begin{equation*}
  116.            \begin{split}
  117.                (x_1, \;x_2, \;\dots, \;x_{n}) + \big((y_1,\;y_2,\;\dots,\;y_{n}) \cdot (z_1, \;z_2, \;\dots, \;z_{n})\big) = \\
  118.                \big((x_1, \;x_2, \;\dots, \;x_{n}) + (y_1,\;y_2,\;\dots,\;y_{n})\big) \cdot \big((x_1, \;x_2, \;\dots, \;x_{n}) + (z_1,\;z_2,\;\dots,\;z_{n})\big)
  119.            \end{split}
  120.        \end{equation*}
  121.        
  122.        Que, por definição, significa que $+$ é distributiva em $\cdot$ \checkmark
  123.        \\
  124.        Sendo assim, $\cdot$ é distributiva em $+$, e, $+$ é distributiva em $\cdot$ $\quad \square$
  125.        
  126.        \item \underline{\textbf{0} e \textbf{1} são identidade:}
  127.        $$ (x_1, \;x_2, \;\dots, \;x_{n}) + \mathbf{0} = (x_1, \;x_2, \;\dots, \;x_{n}) + (\textcolor{magenta}{0},\; \textcolor{magenta}{0}, \; \dots, \; \textcolor{magenta}{0}) = (x_1 \; \textcolor{magenta}{+} \; \textcolor{magenta}{0}, \; x_2 \; \textcolor{magenta}{+} \; \textcolor{magenta}{0} ,\;\dots , \;x_{n} \; \textcolor{magenta}{+} \; \textcolor{magenta}{0}) $$
  128.        
  129.        $\forall i \in \{ 1,2, \dots, n \}\big( x_i \in B \big) \implies \forall i \in \{ 1,2, \dots, n \} \big(x_i \; \textcolor{magenta}{+} \; \textcolor{magenta}{0} = x_i\big) $. \\
  130.        $\therefore (x_1 \; \textcolor{magenta}{+} \; \textcolor{magenta}{0}, \; x_2 \; \textcolor{magenta}{+} \; \textcolor{magenta}{0} ,\;\dots , \;x_{n} \; \textcolor{magenta}{+} \; \textcolor{magenta}{0}) = (x_1, \; x_2 ,\;\dots , \;x_{n})$ e, portanto, $(x_1, \; x_2 ,\;\dots , \;x_{n}) + \textbf{0} = (x_1, \; x_2 ,\;\dots , \;x_{n})$, em outras palavras, \textbf{0} é identidade. \checkmark
  131.       \\
  132.        $$ (x_1, \;x_2, \;\dots, \;x_{n}) \cdot \mathbf{1} = (x_1, \;x_2, \;\dots, \;x_{n}) \cdot (\textcolor{magenta}{1},\; \textcolor{magenta}{1}, \; \dots, \; \textcolor{magenta}{1}) = (x_1  \; \textcolor{magenta}{\cdot} \; \textcolor{magenta}{1}, \; x_2  \; \textcolor{magenta}{\cdot} \; \textcolor{magenta}{1} ,\;\dots , \;x_{n} \; \textcolor{magenta}{\cdot} \; \textcolor{magenta}{1})$$
  133.        
  134.        $\forall i \in \{ 1,2, \dots, n \}\big( x_i \in B \big) \implies \forall i \in \{ 1,2, \dots, n \} \big(x_i \; \textcolor{magenta}{\cdot} \; \textcolor{magenta}{1} = x_i\big) $. \\
  135.        $\therefore (x_1 \; \textcolor{magenta}{\cdot} \; \textcolor{magenta}{1}, \; x_2 \; \textcolor{magenta}{\cdot} \; \textcolor{magenta}{1} ,\;\dots , \;x_{n} \; \textcolor{magenta}{\cdot} \; \textcolor{magenta}{1}) = (x_1, \; x_2 ,\;\dots , \;x_{n})$ e, portanto, $(x_1, \; x_2 ,\;\dots , \;x_{n}) \cdot \textbf{1} = (x_1, \; x_2 ,\;\dots , \;x_{n})$, em outras palavras, \textbf{1} é identidade. \checkmark
  136.        
  137.        Em suma, conclui-se que \textbf{0} e \textbf{1} são identidade. \quad $\square$
  138.        
  139.        \item \underline{$\overline{(x_1, \;x_2, \;\dots, \;x_{n})}$ é complemento de $(x_1, \;x_2, \;\dots, \;x_{n})$:}
  140.        
  141.        \begin{equation*}
  142.            \begin{split}
  143.                \overline{(x_1, \;x_2, \;\dots, \;x_{n})} + (x_1, \;x_2, \;\dots, \;x_{n}) = (\textcolor{magenta}{\overline{\textcolor{black}{x}}}_1, \; \textcolor{magenta}{\overline{\textcolor{black}{x}}}_2, \;\dots, \; \textcolor{magenta}{\overline{\textcolor{black}{x}}}_{n}) + (x_1, \;x_2, \;\dots, \;x_{n}) \\
  144.                = (\textcolor{magenta}{\overline{\textcolor{black}{x}}}_1 \; \textcolor{magenta}{+} \; x_1, \; \textcolor{magenta}{\overline{\textcolor{black}{x}}}_2 \; \textcolor{magenta}{+} \; x_2 , \;\dots, \; \textcolor{magenta}{\overline{\textcolor{black}{x}}}_{n} \; \textcolor{magenta}{+} \; x_n )
  145.            \end{split}
  146.        \end{equation*}
  147.        
  148.        $\forall i \in \{ 1,2, \dots, n \}\big( \textcolor{magenta}{\overline{\textcolor{black}{x}}}_{i} \; \textcolor{magenta}{+} \; x_i = 1 \big) \Rightarrow (\textcolor{magenta}{\overline{\textcolor{black}{x}}}_1 \; \textcolor{magenta}{+} \; x_1, \; \textcolor{magenta}{\overline{\textcolor{black}{x}}}_2 \; \textcolor{magenta}{+} \; x_2 , \;\dots, \; \textcolor{magenta}{\overline{\textcolor{black}{x}}}_{n} \; \textcolor{magenta}{+} \; x_n ) = (\textcolor{magenta}{1},\; \textcolor{magenta}{1}, \; \dots, \; \textcolor{magenta}{1}) = \textbf{1}.$\\
  149.        $\therefore \overline{(x_1, \;x_2, \;\dots, \;x_{n})} + (x_1, \;x_2, \;\dots, \;x_{n}) = \textbf{1}$ \checkmark
  150.        
  151.        \begin{equation*}
  152.            \begin{split}
  153.                \overline{(x_1, \;x_2, \;\dots, \;x_{n})} \cdot (x_1, \;x_2, \;\dots, \;x_{n}) = (\textcolor{magenta}{\overline{\textcolor{black}{x}}}_1, \; \textcolor{magenta}{\overline{\textcolor{black}{x}}}_2, \;\dots, \; \textcolor{magenta}{\overline{\textcolor{black}{x}}}_{n}) \cdot (x_1, \;x_2, \;\dots, \;x_{n}) \\
  154.                = (\textcolor{magenta}{\overline{\textcolor{black}{x}}}_1 \; \textcolor{magenta}{\cdot} \; x_1, \; \textcolor{magenta}{\overline{\textcolor{black}{x}}}_2 \; \textcolor{magenta}{\cdot} \; x_2 , \;\dots, \; \textcolor{magenta}{\overline{\textcolor{black}{x}}}_{n} \; \textcolor{magenta}{\cdot} \; x_n )
  155.            \end{split}
  156.        \end{equation*}
  157.        
  158.        $\forall i \in \{ 1,2, \dots, n \}\big( \textcolor{magenta}{\overline{\textcolor{black}{x}}}_{i} \; \textcolor{magenta}{\cdot} \; x_i = 0 \big) \Rightarrow (\textcolor{magenta}{\overline{\textcolor{black}{x}}}_1 \; \textcolor{magenta}{\cdot} \; x_1, \; \textcolor{magenta}{\overline{\textcolor{black}{x}}}_2 \; \textcolor{magenta}{\cdot} \; x_2 , \;\dots, \; \textcolor{magenta}{\overline{\textcolor{black}{x}}}_{n} \; \textcolor{magenta}{\cdot} \; x_n ) = (\textcolor{magenta}{0},\; \textcolor{magenta}{0}, \; \dots, \; \textcolor{magenta}{0}) = \textbf{0}.$\\
  159.        $\therefore \overline{(x_1, \;x_2, \;\dots, \;x_{n})} + (x_1, \;x_2, \;\dots, \;x_{n}) = \textbf{0}$ \checkmark
  160.        
  161.        Logo, $\overline{(x_1, \;x_2, \;\dots, \;x_{n})}$ é complemento de $(x_1, \;x_2, \;\dots, \;x_{n}). \qquad \square $
  162.        
  163.         \end{enumerate}{}
  164.        
  165.         Por fim, uma vez que os quatro axiomas da álgebra booleana mostraram-se satisfeitos para a sêxtupla $\langle B^n,\,+,\,\cdot,\,-,\,\mathbf{0},\,\mathbf{1}  \rangle$ com as operações e elementos definidos tal qual o enunciado da lista, pode-se concluir que, de fato, $\langle B^n,\,+,\,\cdot,\,-,\,\mathbf{0},\,\mathbf{1}  \rangle$ é uma álgebra booleana.
  166. \end{proof}
  167.  
  168. \end{document}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!