$ % 15-Dec-2025 \def\Nat{\mathbb{N}} \def\N{\Nat} \def\B{Bool} \def\Seq#1{{#1}^{\star}} \def\alt#1#2{[#1,#2]} \def\ana#1{(\hskip -1ex[#1]\hskip -1ex )} \def\atmost{\subseteq} \def\bang{{!}} \def\cata#1{(\hskip -1.1pt[\hskip 0.1pt #1 \hskip 0.1pt]\hskip -1.1pt)} \def\comp{\mathbin\cdot} \def\conj#1#2{\mathopen{\langle} #1, #2\mathclose{\rangle}} \def\conv#1{#1^\circ} \def\crflx#1{\Phi_{#1}} \def\dom#1{\delta {#1}} \def\fB{\fun B} \def\ensuremath#1{#1} \def\from{\leftarrow} \def\fun#1{\mathsf{#1}} \def\i#1{\mathit{i}_{#1}} \def\img#1{\mathbf{img}\ {#1}} \def\implied{\Leftarrow} \def\implies{\Rightarrow} \def\inT{\mathsf{in}} \def\iso{\cong} \def\just#1#2{\\& \mathopen{\{}~\mbox{#2}~\mathclose{\}}\\&&} \def\cjust#1#2{\just{#1}{ ..................................................................... }} \def\ker#1{\mathbf{ker}\ {#1}} \def\kons#1{\underline{#1}} \def\larrow#1#2#3{#3\ \xleftarrow{#2}\ #1} \def\ldiv{\mathbin{/}} \def\mcond#1#2#3{#1 \rightarrow #2\;,\;#3} \def\more{\\&&} \def\outT{\mathsf{out}} \def\p#1{\pi_{#1}} \def\plus{\mathbin{\dagger}} \def\rarrow#1#2#3{#1\ \xrightarrow{#2}\ #3} \def\rcb#1#2#3#4{\mathopen{\langle}#1 #2 : #3 : #4\mathclose{\rangle}} \def\rdiv{\mathbin{\setminus}} \def\scata#1{⦅\, #1 \,⦆} \def\sep{\rule{15em}{0.3pt}} \def\sep{\rule{15em}{0.3pt}} \def\shrunkby{\mathbin{\upharpoonright}} \def\sse#1#2{{#1}\subseteq{#2}} \def\start{&&} \def\syd#1#2{\frac{#1}{#2}} \def\to{\rightarrow} \def\trans#1{\overline{#1}} \newenvironment{lcbr}{\left\{\begin{array}{l}}{\end{array}\right.} %-------- \def\Varid#1{\mathbin{#1}} \def\ensuremath#1{#1} \def\Conid#1{\mathbin{#1}} $
Q1 - No exercício 38 dos slides, primeira alínea, o que é para mostrar?
R: Uma pré-ordem é uma relação reflexiva e transitiva. Logo a alínea tem duas partes: reflexividade de $\def\leqf{(\leq_f)}\leqf$, \begin{eqnarray*} id \atmost \leqf \end{eqnarray*} e a sua transitividade: \begin{eqnarray*} \leqf\comp\leqf \atmost \leqf \end{eqnarray*} Sugestões: (a) usar as leis de shunting (o mais possível) e o facto de $(\leq)$ ser, ela própria, uma pré-ordem; (b) usar as regras de monotonia ("subir lado inferior" ou "descer lado superior") onde for necessário.
Q2 - A solução dada para a questão 6 deste teste sugere, nos dois últimos passos, "composição; guardanapo". No entanto, não consigo ver como é que essas dicas ajudam a resolver o exercício. Por exemplo, a lei do "guardanapo" diz que precisamos de um $\conv f$, mas $\top$ e a função constante $\kons{capital\ d}$ não estão no converso. (O formulário nem sequer menciona as relações entre $\top$ e funções ou relações. Por exemplo, eu não sabia que $\top \comp f = \top$.)
R: Vamos por partes: (a) se tivermos, na lei do "guardanapo", $f=id$, ficamos com $R \comp g$, que no caso são $R = \top \comp Cities$ e $g = \kons{capital\ d}$. (b) o formulário define $\top = \syd \bang \bang$, claramente relacionando $\top$ com funções (constantes). Na última aula viu-se que $\top \comp f = \top$ resulta dessa definição e da propriedade natural de qualquer função constante.
Q3 - Sinto-me inseguro relativamente às propriedades de $\ensuremath{\top }$, $\ensuremath{\bot }$ e $\ensuremath{{id}}$ para relações e para funções.
R: Em geral, sempre que uma propriedade se verifica para qualquer relação $\ensuremath{\Conid{R}}$, então verifica-se sempre para qualquer função $\ensuremath{\Varid{f}}$. (As letras minúsculas identificam funções; as maiúsculas identificam quaisquer relações, funções incluídas).
Assim, as propriedades de $\ensuremath{\top }$, $\ensuremath{\bot }$ e $\ensuremath{{id}}$, ou estão explícitas no formulário , ou derivam-se de outras leis por instanciação e simplificação. Por exemplo, $\ensuremath{{\Varid{f}}\mathbin\cup{\top }\mathrel{=}\top }$ deriva-se de $\textbf{Top-$\cup$}$ do formulário fazendo $\ensuremath{\Conid{R}\mathrel{=}\Varid{f}}$.