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

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

\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")
%
\begin{document}

\catcode`\^^J=10
%\directlua{dednat6dir = "dednat6/"}
%\directlua{dofile(dednat6dir.."dednat6.lua")}
%\directlua{texfile(tex.jobname)}
%\directlua{verbose()}
%\directlua{output(preamble1)}
%\def\expr#1{\directlua{output(tostring(#1))}}
%\def\eval#1{\directlua{#1}}
%\def\pu{\directlua{pu()}}

\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 P1 - 8/nov/2018 - Eduardo Ochs
\par Turma pequena (C1, com aulas nas terças e quartas)
\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: 4.0 pts) Seja $(\star)$ a seguinte proposição: todo
inteiro par é a soma de dois ímpares.

a) \B(0.5 pts) Traduza $(\star)$ para notação matemática.

b) \B(3.0 pts) Demonstre $(\star)$ usando o formato que vimos no
curso, com passos numerados começando com ``Vamos mostrar que'',
``Suponha'' e ``Então''.

c) \B(0.5 pts) Traduza a antepenúltima linha começada com ``Então'' da
sua prova do item anterior para a notação com ``$⊢$''.



\bsk



2) \T(Total: 1.0 pts) Mostre que $P→(Q→R)$ é logicamente equivalente a
$(P∧Q)→R$ e não é logicamente equivalente a $(P→Q)→R$.



\bsk



3) \T(Total: 2.0 pts) Calcule

a) \B(0.5 pts) $\Pts(\{2, 3, \{2, 3\}\})$,

b) \B(1.0 pts) $\bigcup \{\{2, 3\}, \{4, 5\}\}$,
             
c) \B(0.5 pts) $\Pts(A∪B) = \Pts(A)∪\Pts(B)$ no caso em que $A =
\{1\}$ e $B = \{2\}$.



\bsk



4) \T(Total: 1.0 pts) Seja $(P, S)$ o grafo direcionado cuja
representação gráfica é a abaixo. Calcule $\setofst{(a,b,c)}{ a,b,c∈P,
  \, aSb, \, bSc, \, cSa}$.
%
%D diagram ??
%D 2Dx     100 +20 +20
%D 2D  100 1   2
%D 2D
%D 2D  +20 3   4   5
%D 2D
%D (( 1 2 -> 3 1 -> 2 3 -> 3 4 -> 4 5 -> 4 2 ->
%D
%D ))
%D enddiagram
%D
$$\pu
  \diag{??}
$$


\bsk



5) \T(Total: 0.5 pts) Encontre um contra-exemplo para $a∈\Z, b∈\Z, a|b ⊢ a≤b$.


\bsk


6) \T(Total: 1.5 pts) Calcule $\{a∈\Z, b∈\Z, a|b; a≤b\}$.


\bsk
\bsk


\begin{tabular}[t]{l}
Algumas definições: \\
$x \text{ natural} := x ∈ \N$ \\
$x \text{ inteiro} := x ∈ \Z$ \\
$\mathsf{par}  (x) := ∃a∈\Z. x = 2a$ \\
$\mathsf{impar}(x) := ∃a∈\Z. x = 2a + 1$ \\
$a|b := ∃k∈Z.ka = b$ \\
\end{tabular}
%
\qquad
%
\begin{tabular}[t]{l}
Algumas dicas: \\
$x∈A∪B = x∈A ∨ x∈B$ \\
$x∈\bigcup\calC = \setofst{a}{∃B∈\calC.a∈B}$ \\
\end{tabular}


}


\newpage

%   ____       _                _ _        
%  / ___| __ _| |__   __ _ _ __(_) |_ ___  
% | |  _ / _` | '_ \ / _` | '__| | __/ _ \ 
% | |_| | (_| | |_) | (_| | |  | | || (_) |
%  \____|\__,_|_.__/ \__,_|_|  |_|\__\___/ 
%                                          
% «gabarito-1» (to ".gabarito-1")

{\bf Mini-gabarito (não revisado)}

\msk

1a) Podemos começar traduzindo essa proposição para português mais
próximo de linguagem matemática, em vários passos:
%
``todo inteiro par $a$ pode ser expresso como soma de um inteiro ímpar
$b$ e um inteiro ímpar $c$'';
%
``Para todo inteiro par $a$ existem um inteiro ímpar $b$ e um inteiro
ímpar $c$ tais que $a=b+c$''. E aí chegamos a:

$∀a∈\Z.\Par(a)→(∃b∈\Z.∃c∈\Z.\Impar(b)∧\Impar(c)∧(a=b+c))$, ou:

$∀a∈\Z.\Par(a)→(∃b∈\Z.\Impar(b)∧(∃c∈\Z.∧\Impar(c)∧(a=b+c)))$.

\bsk

1b) Podemos começar com uma demonstração em português e depois
formali\-zá-la. Seja $a$ um inteiro par. Sejam $b=9$ e $c=a-9$; então
$b$ é ímpar (porque $9=2·4+1$), $c$ é ímpar (porque $c = a-9 = 2k-9 =
2(k-5)+1$), e $a=b+c$. Portanto existem um inteiro ímpar $b$ e um
inteiro ímpar $c$ tais que $a=b+c$.

Vamos começar com demonstrando um lema primeiro: que se $a$ é par
então $c=a-9$ é impar.

\msk

{\setlength{\parindent}{0em}

$a∈\Z, \Par(a) ⊢ \Par(a)$

$a∈\Z, \Par(a) ⊢ ∃k∈\Z.a=2k$

$a∈\Z, \Par(a), k∈\Z, a=2k ⊢ a-9 = 2k-9 = 2(k-5)+1$

$a∈\Z, \Par(a), k∈\Z, a=2k ⊢ k-5 ∈ \Z$

$a∈\Z, \Par(a), k∈\Z, a=2k ⊢ a-9 = 2(k-5)+1$

$a∈\Z, \Par(a), k∈\Z, a=2k ⊢ ∃n∈\Z. a-9 = 2n+1$ \quad (com $n:=k-5$)

$a∈\Z, \Par(a), k∈\Z, a=2k ⊢ \Impar(a-9)$

$a∈\Z, \Par(a) ⊢ \Impar(a-9)$

$a∈\Z ⊢ \Par(a)→\Impar(a-9)$

$⊢ ∀a∈\Z.\Par(a)→\Impar(a-9)$

}

\msk

Não vou demonstrar que 9 é ímpar. $=)$

\msk

Agora:

\msk

{\setlength{\parindent}{0em}

$a∈\Z, \Par(a) ⊢ \Impar(9)$

$a∈\Z, \Par(a) ⊢ \Impar(a-9)$

$a∈\Z, \Par(a) ⊢ a=9+(a-9)$

$a∈\Z, \Par(a) ⊢ \Impar(a-9)∧a=9+(a-9)$

$a∈\Z, \Par(a) ⊢ ∃c∈\Z.(\Impar(c)∧a=9+c)$ \quad (com $c:=a-9$)

$a∈\Z, \Par(a) ⊢ ∃b∈\Z.\Impar(b)∧(∃c∈\Z.(\Impar(c)∧a=b+c))$ \quad (com $b:=9$)

$a∈\Z, ⊢ \Par(a) → (∃b∈\Z.\Impar(b)∧(∃c∈\Z.(\Impar(c)∧a=b+c)))$

⊢ $∀a∈\Z. (\Par(a) → (∃b∈\Z.\Impar(b)∧(∃c∈\Z.(\Impar(c)∧a=b+c))))$

}


\def\Suponha#1#2{\par $#1) \text{ Suponha $#2$.}$}
\def\NEntaopor#1#2#3{\par $
  #1)    \text{ Entao } #2.   \qquad (\text{#3})
  $}
\def\NEntaoPor#1#2#3{\par $
  #1)    \text{ Entao } #2.   \qquad (\text{Por #3})
  $}
\def\NEntaoPorCom#1#2#3#4{\par $
  #1)    \text{ Entao } #2.   \qquad (\text{Por #3, com $#4$})
  $}

\newpage

A demonstração completa é:

{
\setlength{\parindent}{0em}

1) Queremos ver que

$\phantom{mm} ∀a∈\Z. (\Par(a) → (∃b∈\Z.\Impar(b)∧(∃c∈\Z.(\Impar(c)∧a=b+c))))$.

\Suponha      2 {a∈\Z}
\Suponha      3 {\Par(a)}
\NEntaopor    4                                                {\Impar(9)}   {Por um lema}
\NEntaopor    4                                              {\Impar(a-9)}   {Por outro lema}
\NEntaopor    5                                                {a=9+(a-9)}   {Por álgebra}
\NEntaoPor    6                                      {\Impar(a)∧a=9+(a-9)}  {4, 5}
\NEntaoPorCom 7                                  {∃c∈\Z.(\Impar(c)∧a=9+c)}  {6} {c:=a-9}
\NEntaoPor    8                       {\Impar(9)∧(∃c∈\Z.(\Impar(c)∧a=9+c))} {4, 7}
\NEntaoPorCom 9                {∃b∈\Z.(\Impar(b)∧(∃c∈\Z.(\Impar(c)∧a=b+c)))} {8} {b:=9}
\NEntaoPor {10}        {\Par(a)→∃b∈\Z.(\Impar(b)∧(∃c∈\Z.(\Impar(c)∧a=b+c)))} {9}
\NEntaoPor {11} {∀a∈\Z.(\Par(a)→(∃b∈\Z.\Impar(b)∧(∃c∈\Z.(\Impar(c)∧a=b+c))))} {10}

}

\bsk

1c) A linha 9 vira:

$a∈\Z, \Par(a) ⊢ ∃b∈\Z.(\Impar(b)∧(∃c∈\Z.(\Impar(c)∧a=b+c)))$.



\newpage

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

2) Pela tabela:

$\begin{array}{ccccccc}
 P  & Q  & R  & P→(Q→R) & (P∧Q)→R & (P→Q)→R \\\hline
 \F & \F & \F &   \V    &   \V    &  \F  \\
 \F & \F & \V &   \V    &   \V    &  \V  \\
 \F & \V & \F &   \V    &   \V    &  \F  \\
 \F & \V & \V &   \V    &   \V    &  \V  \\
 \V & \F & \F &   \V    &   \V    &  \V  \\
 \V & \F & \V &   \V    &   \V    &  \V  \\
 \V & \V & \F &   \F    &   \F    &  \F  \\
 \V & \V & \V &   \V    &   \V    &  \V  \\
 \end{array}
$

\bsk

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

{

\def\H#1{\hbox{$#1$}}
\def\h#1{\hbox{\phantom{$#1$}}}
\def\A{\H{2}}
\def\a{\h{2}}
\def\B{\H{3}}
\def\b{\h{3}}
\def\C{\H{\{2,3\}}}
\def\c{\h{\{2,3\}}}
\def\O{\H{,\,}}
\def\o{\h{,\,}}
\def\oc{\o\c}

3a)
$\Pts(\{2, 3, \{2, 3\}\})
 =
 \begin{array}[t]{rlll}
 \{ & \{\a\o\b\oc\}, & \{\a\o\b\o\C\},      \\
    & \{\a\o\B\oc\}, & \{\a\o\B\O\C\},      \\
    & \{\A\o\b\oc\}, & \{\A\O\b\o\C\},      \\
    & \{\A\O\B\oc\}, & \{\A\O\B\O\C\}  & \}. \\
 \end{array}
$

}

3b) $\begin{array}[t]{rcl}
       \bigcup \{\{2, 3\}, \{4, 5\}\}
           &=& \setofst{a}{∃B∈\{\{2, 3\}, \{4, 5\}\}.a∈B} \\
           &=& \setofst{a}{a∈\{2, 3\} ∨ a∈\{4, 5\}} \\
           &=& \setofst{a}{a∈\{2, 3\}∪\{4, 5\}} \\
           &=& \setofst{a}{a∈\{2, 3, 4, 5\}} \\
           &=& \{2, 3, 4, 5\} \\
     \end{array}
    $

3c) $\begin{array}[t]{l}
     \Pts(A∪B) = \Pts(\{2\}∪\{3\}) = \Pts(\{2,3\}) = \{∅,\{2\},\{3\},\{2,3\}\} \\
     \Pts(A)∪\Pts(B) = \Pts(\{2\})∪\Pts(\{3\}) = \{∅,\{2\}\} ∪ \{∅,\{3\}\} = \{∅,\{2\},\{3\}\} \\
     (\Pts(A∪B)=\Pts(A)∪\Pts(B)) = (\{∅,\{2\},\{3\},\{2,3\}\} = \{∅,\{2\},\{3\}\}) = \F \\
     \end{array}
    $

\bsk

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

4) $\begin{array}[t]{l}
    P = \{1,2,3,4\} \\
    S = \{(1,2),(2,3),(3,1),(3,4),(4,2),(4,5)\} \\
    \setofst{(a,b,c)}{ a,b,c∈P,  \, aSb, \, bSc, \, cSa} =  \\
    \;\;\; \{(1,2,3), (2,3,1), (2,3,4), (3,1,2), (3,4,2), (4,2,3)\} \\
    \end{array}
    $

\bsk

5) Se $a=2$ e $b=-6$ então $a|b$ é verdade mas $a≤b$ é falso.

\bsk

% "Stop":
% (find-es "tex" "vrule")
\def\S{\omit\vrule\phantom{$\scriptstyle($}\hss}   % stop

6) Para quaisquer $a,b∈\Z$ o resultado de $a≤b$ é sempre $\F$ ou $\V$, então:

  $\{a∈\Z, b∈\Z; a≤b\} ⊆ \{\F, \V\}$

  $\{a∈\Z, b∈\Z, a|b; a≤b\} ⊆ \{\F, \V\}$

  Podemos calcular $\{a∈\Z, b∈\Z, a|b; a≤b\}$ por um {\sl pedaço} da
  tabela, que é infinita...

  $\begin{array}{cccc}
   a & b & a|b & a≤b \\\hline
   2 &  3 & \F  & \S \\
   2 &  4 & \V  & \V \\
   2 & -4 & \V  & \F \\
   \end{array}
  $

  Daí $\{a∈\Z, b∈\Z, a|b; a≤b\} = \{\F, \V\}$.





\end{document}

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