% (find-angg "LATEX/2018-2-MD-P2A.tex")
% (defun c () (interactive) (find-LATEXsh "lualatex -record 2018-2-MD-P2A.tex"))
% (defun d () (interactive) (find-xpdfpage "~/LATEX/2018-2-MD-P2A.pdf"))
% (defun e () (interactive) (find-LATEX "2018-2-MD-P2A.tex"))
% (defun u () (interactive) (find-latex-upload-links "2018-2-MD-P2A"))
% (find-xpdfpage "~/LATEX/2018-2-MD-P2A.pdf")
% (find-sh0 "cp -v  ~/LATEX/2018-2-MD-P2A.pdf /tmp/")
% (find-sh0 "cp -v  ~/LATEX/2018-2-MD-P2A.pdf /tmp/pen/")
%   file:///home/edrx/LATEX/2018-2-MD-P2A.pdf
%               file:///tmp/2018-2-MD-P2A.pdf
%           file:///tmp/pen/2018-2-MD-P2A.pdf
% http://angg.twu.net/LATEX/2018-2-MD-P2A.pdf

% «.gab-1»	(to "gab-1")
% «.gab-2»	(to "gab-2")
% «.gab-3»	(to "gab-3")
% «.gab-4»	(to "gab-4")
% «.gab-5»	(to "gab-5")

\documentclass[oneside]{book}
\usepackage[colorlinks]{hyperref} % (find-es "tex" "hyperref")
%\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{pict2e}
\usepackage{color}                % (find-LATEX "edrx15.sty" "colors")
\usepackage{colorweb}             % (find-es "tex" "colorweb")
%\usepackage{tikz}
%
% (find-dn6 "preamble6.lua" "preamble0")
\usepackage{proof}   % For derivation trees ("%:" lines)
\input diagxy        % For 2D diagrams ("%D" lines)
%\xyoption{curve}     % For the ".curve=" feature in 2D diagrams
\catcode`\^^J=10                      % (find-es "luatex" "spurious-omega")
\directlua{dofile "dednat6load.lua"}  % (find-LATEX "dednat6load.lua")
\def\expr#1{\directlua{output(tostring(#1))}}
\def\eval#1{\directlua{#1}}
%
\usepackage{edrx15}               % (find-angg "LATEX/edrx15.sty")
\input edrxaccents.tex            % (find-angg "LATEX/edrxaccents.tex")
\input edrxchars.tex              % (find-LATEX "edrxchars.tex")
\input edrxheadfoot.tex           % (find-dn4ex "edrxheadfoot.tex")
\input edrxgac2.tex               % (find-LATEX "edrxgac2.tex")
%
% (find-angg ".emacs.papers" "latexgeom")
% (find-latexgeomtext "total={6.5in,8.75in},")
\usepackage[%total={6.5in,4in},
            %textwidth=4in,  paperwidth=4.5in,
            %textheight=5in, paperheight=4.5in,
            a4paper,
            top=1.2in, left=1.2in%, includefoot
           ]{geometry}
%
\begin{document}

\catcode`\^^J=10

% \directlua{dofile "edrxtikz.lua"} % (find-LATEX "edrxtikz.lua")
% \directlua{dofile "edrxpict.lua"} % (find-LATEX "edrxpict.lua")
% %L V.__tostring = function (v) return format("(%.3f,%.3f)", v[1], v[2]) end






\def\V{\mathbf{V}}
\def\F{\mathbf{F}}

\def\Par  {\mathsf{par}}
\def\Impar{\mathsf{impar}}





%   ____      _                    _ _           
%  / ___|__ _| |__   ___  ___ __ _| | |__   ___  
% | |   / _` | '_ \ / _ \/ __/ _` | | '_ \ / _ \ 
% | |__| (_| | |_) |  __/ (_| (_| | | | | | (_) |
%  \____\__,_|_.__/ \___|\___\__,_|_|_| |_|\___/ 
%                                                

{\setlength{\parindent}{0em}
\footnotesize
\par Matemática Discreta
\par PURO-UFF - 2018.2
\par P2 - 17/dez/2018 - Eduardo Ochs
\par Turma grande (V1, com aulas nas segundas e quartas)
\par Respostas sem justificativas não serão aceitas {\sl em algumas questões}.
\par Proibido usar quaisquer aparelhos eletrônicos.

}

\bsk
\bsk

\def\T(Total: #1 pts){{\bf(Total: #1 pts)}}
\def\T(Total: #1 pts){{\bf(Total: #1)}}
\def\B       (#1 pts){{\bf(#1 pts)}}
% Usage:
% 1) \T(Total: 2.34 pts) Foo
% a) \B(0.45 pts) Bar






{
\setlength{\parindent}{0em}


1) \T(Total: 2.0 pts) Sejam $(R1)$, $(R2)$, $(R3)$ as regras
abaixo:
%:
%:
%:   Γ⊢A→B   Γ⊢¬B        A⊢C        A⊢B
%:   ------------(R1)   -----(R2)   ---(R3)
%:       Γ⊢¬A           A∨B⊢C       A⊢B∧C
%:
%:       ^R1             ^R2        ^R3
%:
\pu
$$\ded{R1} \qquad \ded{R2} \qquad \ded{R3}$$

a) \B(1.0 pts) Mostre que a regra $(R1)$ é admissível.

b) \B(0.5 pts) Mostre que a regra $(R2)$ é inadmissível.

c) \B(0.5 pts) Mostre que a regra $(R3)$ é inadmissível.

\bsk




2) \T(Total: 4.0 pts) Para cada $k∈\N$ seja $P(k)$ a seguinte
proposição: $1+3+\ldots+(2k+1)=(k+1)^2$.

a) \B(0.5 pts) Verifique $P(0)$, $P(1)$, $P(2)$, $P(3)$.

b) \B(0.5 pts) Defina uma função $f(k)$, sem `$\ldots$'s mas usando
somatório, tal que $f(k)=1+3+\ldots+(2k+1)$ para todo $k∈\N$.

c) \B(0.5 pts) Teste a sua definição do $f(k)$ usando $k=0$, $k=1$, $k=2$, $k=3$.

d) \B(0.5 pts) Calcule $f(21)-f(20)$.

e) \B(1.5 pts) Demonstre $k∈\N ⊢ P(k)→P(k+1)$.

f) \B(0.5 pts) Demonstre $∀n∈\N.P(n)$.


\bsk


% 3) \T(Total: 2.0 pts) Seja $F:\N×\N→\N$ uma função que obedece:
% 
% (F0) $F(0,0)=0$,
% 
% (FT) $∀n∈\N.     0<n → F(0,n)+1 = F(n+1,0)$,
% 
% (FS) $∀x,y∈\N. 0≤y<x → F(x,y)+1 = F(x,y+1)$,
% 
% (FE) $∀x,y∈\N. 0<x≤y → F(x,y)+1 = F(x-1,y)$.
% 
% Calcule os valores de $F(x,y)$ para todos os $(x,y)∈\{0,1,2,3\}^2$.


3) \T(Total: 2.0 pts) Seja $F:\N×\N→\N$ uma função que obedece:

(F0) $F(0,0)=0$,

(FT) $∀n∈\N. F(0,n)+1 = F(n+1,0)$,

(FD) $∀x,y∈\N. 1≤x → F(x,y)+1 = F(x-1,y+1)$.

a) \B(1.0 pts) Calcule os valores de $F(x,y)$ em pelo menos 10 pontos de $\N^2$.

b) \B(1.0 pts) Represente graficamente a função $F$.


\bsk


4) \T(Total: 2.0 pts) Seja $A=\{1,2,3,4,5,6\}$ e sejam $f,g:A→A$ as
seguintes permutações:

$f = (1\; 2\; 3)(4\; 5)$ \qquad $(=\{(1,2), (2,3), (3,1), (4,5), (5,4), (6,6)\})$

$g = (3\; 4)$

a) \B(0.5 pts) Calcule $f∘g$ e $g∘f$ e expresse-os na notação de ciclos.

b) \B(0.5 pts) Calcule $f, f^2, f^3, f^4, f^5, f^6$ e expresse-os na notação de ciclos.

c) \B(1.0 pts) Calcule $f^{20}$ e expresse-o na notação de ciclos.


\bsk

5) \T(Total: 1.0 pts) Sejam $A=\{2,3,4\}$, $B=\{3,4,5\}$.

a) \B(0.2 pts) Exiba um elemento de $B^A$.

b) \B(0.2 pts) Exiba um elemento de $A^B$.

c) \B(0.3 pts) Exiba um elemento $f∈B^A$ que obedeça $f:A→A$.

d) \B(0.3 pts) Exiba um elemento $g∈B^A$ que obedeça $¬(g:A→A)$.






\bsk
\bsk

Dicas:

$(∃!x∈A.P(a)) \;\; = \;\; (∃x∈A.P(a))∧(∀x',x''∈A.P(x')∧P(x'')→x'=x'')$

$(f:A→B) \;\; = \;\; (f⊆A×B) ∧ (∀a∈A.∃!b∈B.(a,b)∈f)$

$\{a,a+1,\ldots,b\} \;\; = \;\; \setofst{k∈\Z}{a≤k≤b}$

Se $f,g$ são funções então $(f∘g)(x)=f(g(x)), \; f^2=f∘f, \; f^3=f∘f∘f$

Se $A,B$ são conjuntos então $B^A = \setofst{f}{f:A→B}$

$\sum_{i=2}^{4} 10^i = 11100$, \;\; $\sum_{i=4}^{2} 10^i = 0$



\newpage

%   ____       _                _ _        
%  / ___| __ _| |__   __ _ _ __(_) |_ ___  
% | |  _ / _` | '_ \ / _` | '__| | __/ _ \ 
% | |_| | (_| | |_) | (_| | |  | | || (_) |
%  \____|\__,_|_.__/ \__,_|_|  |_|\__\___/ 
%                                          
{\bf Mini-gabarito (não revisado)}

\msk

% «gab-1» (to ".gab-1")

1a) Sejam $α=(Γ→(A→B))$, $β=(Γ→¬B)$, $γ=(Γ→¬A)$. Então:

$\begin{array}{ccccccc}
  Γ &  A &  B & Γ→(A→B) & Γ→¬B & Γ→¬A & α∧β→γ \\\hline
 \F & \F & \F &   \V    &  \V  &  \V  &   \V  \\
 \F & \F & \V &   \V    &  \V  &  \V  &   \V  \\
 \F & \V & \F &   \V    &  \V  &  \V  &   \V  \\
 \F & \V & \V &   \V    &  \V  &  \V  &   \V  \\
 \V & \F & \F &   \V    &  \V  &  \V  &   \V  \\
 \V & \F & \V &   \V    &  \F  &  \V  &   \V  \\
 \V & \V & \F &   \F    &  \V  &  \F  &   \V  \\
 \V & \V & \V &   \V    &  \F  &  \F  &   \V  \\
 \end{array}
$

\ssk

1b) Quando $A=\F$, $B=\V$, $C=\F$ temos $(A→C)→(A∨B→C)=\F$.

1c) Quando $A=\V$, $B=\V$, $C=\F$ temos $(A→B)→(A→B∧C)=\F$.

\msk

% «gab-2» (to ".gab-2")

2a) $P(0)=(1=(0+1)^2)=\V$;
    $P(1)=(1+(1·1+1)=(1+1)^2)=\V$;

    $P(2)=(1+3+(2·1+1)=(2+1)^2)=\V$;
    $P(3)=(1+3+5+(3·1+1)=(3+1)^2)=\V$.

2b) $f(k)=\sum_{i=0}^{k} 2i+1$

2c) $f(0)=2·0+1$, $f(1)=1+3$. $f(2)=1+3+5$, $f(3)=1+3+5+7$.

2d) $f(21)-f(20) = (\sum_{i=0}^{21} 2i+1) - (\sum_{i=0}^{20} 2i+1) =
2·21+1 = 43$

2e) Temos:

$\begin{array}[t]{rcl}
              f(k+1) &=& 1+3+\ldots+(2k+1)+(2(k+1)+1) \\
                     &=& f(k)+(2(k+1)+1) \\
                     &=& f(k)+2k+3 \\
         f(k+1)-f(k) &=& k+3 \\
             (k+2)^2 &=& k^2+4k+4 \\
             (k+1)^2 &=& k^2+2k+1 \\
     (k+2)^2-(k+1)^2 &=& 2k+3 \\
                     &=& f(k+1)-f(k) \\
              \end{array}$

\begin{tabular}[t]{lr}
    1) Suponha $k∈\N$ \\
    2) Suponha $P(k)$ \\
    3) Então $1+3+\ldots+(2k+1)=(k+1)^2$ \\
    4) Então $f(k) = (k+1)^2$ \\
    5) Então $f(k+1)-f(k) = (k+2)^2-(k+1)^2$ \\
    6) Então $f(k) + (f(k+1)-f(k)) = (k+1)^2 + ((k+2)^2-(k+1)^2)$ \\
    7) Então $f(k+1) = (k+2)^2$ \\
    8) Então $P(k+1)$ \\
    9) Então $P(k)→P(k+1)$   & (fecha 2) \\
    \end{tabular}

2f) Sabemos $P(0)$ e $∀k∈\N.P(k)→P(k+1)$. Por indução, $∀n∈\N.P(n)$.

% «gab-3» (to ".gab-3")

\msk

3a)
\begin{tabular}[t]{ll}
Por (F0),                  & $F(0,0)=0$ \\
Fazendo $n=0$ em (FT),     & $F(0,0)+1=F(1,0)=1$ \\
Fazendo $x=1,y=0$ em (FD), & $F(1,0)+1=F(0,1)=2$ \\
Fazendo $n=1$ em (FD),     & $F(0,1)+1=F(2,0)=3$ \\
Fazendo $x=2,y=0$ em (FD), & $F(2,0)+1=F(1,1)=4$ \\
Fazendo $x=1,y=1$ em (FD), & $F(1,1)+1=F(0,2)=5$ \\
Fazendo $n=2$ em (FD),     & $F(0,2)+1=F(3,0)=6$ \\
Fazendo $x=3,y=0$ em (FD), & $F(3,0)+1=F(2,1)=7$ \\
Fazendo $x=2,y=1$ em (FD), & $F(2,1)+1=F(1,2)=8$ \\
Fazendo $x=1,y=2$ em (FD), & $F(1,2)+1=F(0,3)=9$ \\
\end{tabular}

3b) \def\Fxy#1#2#3{F(#1,#2)=#3}
    $\begin{array}[t]{cccc}
     \Fxy039 & \\
     \Fxy025 & \Fxy128 & \\
     \Fxy012 & \Fxy114 & \Fxy217 & \\
     \Fxy000 & \Fxy101 & \Fxy203 & \Fxy306 \\
     \end{array}
    $

\newpage

% «gab-4» (to ".gab-4")

4a)
\begin{array}[t]{ccccc}
x & f(x) & g(x) & f(g(x))         & g(f(x)) \\\hline
1 &  2   &  1   & f(g(1))=f(1)=2  & g(f(1))=g(2)=2  \\
2 &  3   &  2   & f(g(2))=f(2)=3  & g(f(2))=g(3)=4  \\
3 &  1   &  4   & f(g(3))=f(4)=5  & g(f(3))=g(1)=1  \\
4 &  5   &  3   & f(g(4))=f(3)=1  & g(f(4))=g(5)=5  \\
5 &  4   &  5   & f(g(5))=f(5)=4  & g(f(5))=g(4)=3  \\
6 &  6   &  6   & f(g(6))=f(g)=6  & g(f(6))=g(6)=6  \\
\end{array}
\quad
\begin{array}[t]{l} \\
f∘g=(1\;2\;3\;5\;4) \\
g∘f=(1\;2\;4\;5\;3) \\
\end{array}

4b)
\begin{array}[t]{l}
f  =(1\;2\;3)(4\;5) \\
f^2=(1\;3\;2) \\
f^3=(4\;5) \\
f^4=(1\;2\;3) \\
f^5=(1\;3\;2)(4\;5) \\
f^6=() \\
\end{array}

4c) $f^{20} = f^6∘f^6∘f^6∘f^2 = ()∘()∘()∘(1\;3\;2) = (1\;3\;2)$

\msk

% «gab-5» (to ".gab-5")

5a) Soluções: $\{(2,x),(3,y),(4,z)\}$ com $x,y,z∈B$

5b) Soluções: $\{(3,x),(4,y),(5,z)\}$ com $x,y,z∈A$

5c) Soluções: $f=\{(2,x),(3,y),(4,z)\}$ com $x,y,z∈B∩A=\{3,4\}$

5d) Por exemplo $g=\{(2,x),(3,y),(4,2)\}$ com $x,y∈B$



}









\end{document}

% Local Variables:
% coding: utf-8-unix
% End: