|
Warning: this is an htmlized version!
The original is here, and the conversion rules are here. |
% (find-angg "LATEX/2018-2-MD-P1A.tex")
% (defun c () (interactive) (find-LATEXsh "lualatex -record 2018-2-MD-P1A.tex"))
% (defun d () (interactive) (find-xpdfpage "~/LATEX/2018-2-MD-P1A.pdf"))
% (defun e () (interactive) (find-LATEX "2018-2-MD-P1A.tex"))
% (defun u () (interactive) (find-latex-upload-links "2018-2-MD-P1A"))
% (find-xpdfpage "~/LATEX/2018-2-MD-P1A.pdf")
% (find-sh0 "cp -v ~/LATEX/2018-2-MD-P1A.pdf /tmp/")
% (find-sh0 "cp -v ~/LATEX/2018-2-MD-P1A.pdf /tmp/pen/")
% file:///home/edrx/LATEX/2018-2-MD-P1A.pdf
% file:///tmp/2018-2-MD-P1A.pdf
% file:///tmp/pen/2018-2-MD-P1A.pdf
% http://angg.twu.net/LATEX/2018-2-MD-P1A.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")
%
% (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.5in, left=1.5in%, includefoot
]{geometry}
%
\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 - 29/out/2018 - Eduardo Ochs
\par Turma grande (V1, com aulas nas segundas 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 ímpar é a soma de um par e um ímpar.
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$ é logicamente equivalente a
$¬P∨Q$ e não é logicamente equivalente a $P∨¬Q$.
\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 é $1→2→3→4$. Calcule $\setofst{(a,c)}{ a,b,c∈P,
\, aSb, \, bSc}$.
\bsk
5) \T(Total: 1.0 pts) Encontre um contra-exemplo para $a∈\Z, b∈\Z, a|b ⊢ a≤b$.
\bsk
6) \T(Total: 2.0 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$ \\
$\bigcup\calC = \setofst{a}{∃B∈\calC.a∈B}$ \\
\end{tabular}
}
\newpage
% ____ _ _ _
% / ___| __ _| |__ __ _ _ __(_) |_ ___
% | | _ / _` | '_ \ / _` | '__| | __/ _ \
% | |_| | (_| | |_) | (_| | | | | || (_) |
% \____|\__,_|_.__/ \__,_|_| |_|\__\___/
%
% «gabarito-1» (to ".gabarito-1")
{\bf Mini-gabarito}
\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 par
$b$ e um inteiro ímpar $c$'';
%
``Para todo inteiro par $a$ existem um inteiro par $b$ e um inteiro
ímpar $c$ tais que $a=b+c$''. E aí
$∀a∈\Z.\Impar(a)→(∃b∈\Z.∃c∈\Z.\Par(b)∧\Impar(c)∧(a=b+c))$, ou:
$∀a∈\Z.\Impar(a)→(∃b∈\Z.\Par(b)∧(∃c∈\Z.∧\Impar(c)∧(a=b+c)))$.
\bsk
1b) Podemos começar com uma demonstração em português e depois
formalizá-la. Seja $a$ um inteiro ímpar. Sejam $b=0$ e $c=a$; então
$b$ é par, $c$ é ímpar, e $a=b+c$. Portanto existem um inteiro par $b$
e um inteiro ímpar $c$ tais que $a=b+c$.
A menos que a gente tenha {\sl muita} prática é quase impossível
chegar direto a uma formalização desse demonstração sem trabalhar ``de
trás pra frente'' e ``fazendo primeiro as extremidades e depois o
meio'' como o livro sugere. Os últimos passos com ``Então'' da
demonstração vão ter estas traduções para a notação com `$⊢$:
$⊢ ∀a∈\Z.\Impar(a)→(∃b∈\Z.\Par(b)∧(∃c∈\Z.∧\Impar(c)∧(a=b+c)))$
$a∈\Z ⊢ \Impar(a)→(∃b∈\Z.\Par(b)∧(∃c∈\Z.∧\Impar(c)∧(a=b+c)))$
$a∈\Z, \Impar(a) ⊢ ∃b∈\Z.\Par(b)∧(∃c∈\Z.∧\Impar(c)∧(a=b+c))$
$a∈\Z, \Impar(a) ⊢ \Par(0) ∧ (∃c∈\Z.∧\Impar(c)∧(a=0+c))$
% $a∈\Z, \Impar(a) ⊢ \Par(0)$
$a∈\Z, \Impar(a) ⊢ ∃c∈\Z.∧\Impar(c)∧(a=0+c)$
$a∈\Z, \Impar(a) ⊢ \Impar(a)∧(a=0+a)$
$a∈\Z, \Impar(a) ⊢ \Impar(a)∧(a=0+a)$
\msk
\def\Suponha#1#2{\par $#1) \text{ Suponha $#2$.}$}
\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$})
$}
E vão ficar deste jeito no formato passo a passo:
{
\setlength{\parindent}{0em}
\NEntaoPor ? {\Impar(a)} {?}
\NEntaoPor ? {a=0+a} {?}
\NEntaoPor ? {\Impar(a)∧(a=0+a)} {?}
\NEntaoPorCom ? {∃c∈\Z.\Impar(a)∧(a=0+c)} {?} {c:=a}
\NEntaoPor ? {\Par(0)∧(∃c∈\Z.\Impar(a)∧(a=0+c))} {?}
\NEntaoPorCom ? {∃b∈\Z.\Par(b)∧(∃c∈\Z.\Impar(a)∧(a=b+c))} {?} {b:=0}
\NEntaoPor ? {\Impar(a)→∃b∈\Z.\Par(b)∧(∃c∈\Z.\Impar(a)∧(a=b+c))} {?}
\NEntaoPor ? {∀a∈\Z.\Impar(a)→∃b∈\Z.\Par(b)∧(∃c∈\Z.\Impar(a)∧(a=b+c))} {?}
}
\msk
A demonstração completa é:
{
\setlength{\parindent}{0em}
1) Queremos ver que $∀a∈\Z.\Impar(a)→(∃b∈\Z.\Par(b)∧(∃c∈\Z.∧\Impar(c)∧(a=b+c)))$.
\Suponha 2 {a∈\Z}
\Suponha 3 {\Impar(a)}
\NEntaoPor 4 {\Impar(a)} {3}
\NEntaoPor 5 {a=0+a} {2}
\NEntaoPor 6 {\Impar(a)∧(a=0+a)} {4, 5}
\NEntaoPorCom 7 {∃c∈\Z.\Impar(a)∧(a=0+c)} {6} {c:=a}
\NEntaoPor 8 {\Par(0)∧(∃c∈\Z.\Impar(a)∧(a=0+c))} {7}
\NEntaoPorCom 9 {∃b∈\Z.\Par(b)∧(∃c∈\Z.\Impar(a)∧(a=b+c))} {8} {b:=0}
\NEntaoPor {10} {\Impar(a)→∃b∈\Z.\Par(b)∧(∃c∈\Z.\Impar(a)∧(a=b+c))} {9}
\NEntaoPor {11} {∀a∈\Z.\Impar(a)→∃b∈\Z.\Par(b)∧(∃c∈\Z.\Impar(a)∧(a=b+c))} {10}
}
\bsk
1c) A linha 9 vira:
$a∈\Z, \Impar(a) ⊢ ∃b∈\Z.\Par(b)∧(∃c∈\Z.\Impar(a)∧(a=b+c))$.
\newpage
% «gabarito-2» (to ".gabarito-2")
2) Pela tabela:
$\begin{array}{ccccc}
P & Q & P→Q & ¬P∨Q & P∨¬Q \\\hline
\F & \F & \V & \V & \V \\
\F & \V & \V & \V & \F \\
\V & \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,4)\} \\
\setofst{(a,c)}{ a,b,c∈P, \, aSb, \, bSc} = \{(1,3), (2,4)\} \\
\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: