$ % 01-Jun-2023 \def\Nat{\mathbb{N}} \def\atmost{\subseteq} \def\comp{\mathbin\cdot} \def\conj#1#2{\mathopen{\langle} #1, #2\mathclose{\rangle}} \def\conv#1{#1^\circ} \def\i#1{\mathit{i}_{#1}} \def\p#1{\pi_{#1}} \def\implied{\Leftarrow} \def\implies{\Rightarrow} \def\just#1#2{\\& \mathopen{\{}~\mbox{#2}~\mathclose{\}}\\&&} \def\kons#1{\underline{#1}} \def\larrow#1#2#3{#3\ \xleftarrow{#2}\ #1} \def\rarrow#1#2#3{#1\ \xrightarrow{#2}\ #3} \def\rcb#1#2#3#4{\mathopen{\langle}#1 #2 : #3 : #4\mathclose{\rangle}} \def\sep{\rule{15em}{0.3pt}} \def\syd#1#2{\frac{#1}{#2}} \def\to{\rightarrow} \def\from{\leftarrow} \def\rdiv{\mathbin{\setminus}} \def\ldiv{\mathbin{/}} \def\fun#1{\mathsf{#1}} \def\plus{\mathbin{\dagger}} \def\crflx#1{\Phi_{#1}} \def\dom#1{\delta {#1}} \def\shrunkby{\mathbin{\upharpoonright}} \def\start{&&} \def\more{\\&&} $
Q1 - Como é que, na questão Q3.3 das fichas práticas, eu sei se \begin{eqnarray*} id \cap \conv P \comp R \end{eqnarray*} quer dizer \begin{eqnarray*} id \cap (\conv P \comp R) \end{eqnarray*} ou \begin{eqnarray*} (id \cap \conv P) \comp R ~ ? \end{eqnarray*}
R: Como se disse nas aulas, para poupar parênteses associam-se prioridades aos operadores. Os unários têm prioridade máxima e, quanto aos binários, a composição ($\cdot$) prioridade sobre qualquer outro. Logo, é o primeiro caso acima que é a interpretação correcta.
As restantes prioridades são as convencionais, e.g. $\cap > \cup$, $\times > +$ etc. Nos casos em que pode haver ambiguidade, usam-se parênteses.
Q2 - Tenho uma dúvida relativa ao exercício 4 do miniteste de 2018/2019, onde estou a pensar usar a monotonia (lei (5.81) do formulário) e aquelas leis designadas "lowering / raising the upper-side" etc. É uma boa abordagem?
\begin{eqnarray} [R, S] \subseteq X & \equiv & R \subseteq X \comp i_1 ~\land~ S \subseteq X \comp i_2 \end{eqnarray}R: Há melhores, neste caso. Uma das vantagens de (5.114) é que as alternativas relacionais têm as mesmas propriedades que as funcionais, e mais ainda
como se mostrou nas aulas (slide 135). Usando fusão-+ em $dE \comp [V,V']$ e essa lei, o cálculo fica bastante mais simples.
Q3 - Se eu tiver $\rcb\forall{a,b}{a\ X\ b}{a=b}$ posso trocar para $\rcb\forall{a,b}{a=b}{a\ X\ b}$ e depois aplicar 'one point', correcto?
R: Não (!) Isso é se o quantificador for o existencial (∃). No caso do universal, a troca possível é de $\rcb\forall{a,b}{a\ X\ b}{a=b}$ para $\rcb\forall{a,b}{}{a\ X\ b \implies a=b}$ cf. a regra Trading-∀ do formulário (A.1) do formulário, para $R = true$.
Q4 - Tenho dificuldade em decorar a diferença entre núcleo e imagem de uma relação. Há alguma mnemónica que possa ajudar?
R: Haverá concerteza muitas, por exemplo: decore o nome feminino "NEIDE" e leia-o como o acrónimo de "Núcleo, Esquerda, Imagem, Direita, Etc", isto por sua vez abreviatura de "num núcleo $\conv R \comp R$, o converso está à esquerda; numa imagem $R\comp\conv R$ está à direita, etc". Haverá melhores, mas esta dica já pode ajudar.
Q5 - Na questão 1 do teste de 3-12-2020, tenho dificuldade em começar: as projecções $\pi_1$ e $\pi_2$ permitem-me obter $Cliente$ e $Produto$, mas não faço ideia como prosseguir...
R: De notar, antes de mais, que a query $Q$ é uma relação, o que nos permite escrevê-la de forma muito variada. Por exemplo, usando a própria conversa de $Q$, $\conv Q : Data \to Cliente \times Produto$, que pode ser especificada usando splits, e.g. da forma $\conj R S \comp \conv{data}$.
Agora só falta descobrir $R : Venda \to Cliente$ e $S: Venda \to Produto$. Atenção: uma dessas relações tem de passar por $Cupon$, pois só os produtos comprados com cupões é que interessam… E não se coíbam de usar conversos, sempre que necessitarem.
Q6 - Estou com dificuldades em resolver a questão 4 do teste de 15-2-2021. Na primeira alínea, sei que $id \atmost R \cap id$ fazendo $ X := id$ e $S := id$ em (5.58) do formulário, pois $R$ é reflexiva. Como continuo? A segunda alínea não sei como começar.
R: O pouco que demos (para já) quanto a coreflexivas não permite abordar a segunda alínea. Quanto à primeira, o facto a que alude permite-lhe, por monotonia, "descer o lado superior": ora veja lá...
Q7 - Ao estudar o teste do ano passado deparei-me com uma dúvida num dos passos: $\conv{[\bot,id]}=\i2$. Como sabemos isto?
R: Se substituir, na definição (5.117) do formulário, $R$ por $\bot$ e $S$ pela identidade, terá esse resultado, uma vez que $\bot$ é o elemento absorvente da composição e neutro da reunião.
Q8 - Estou com algumas dúvidas relativamente à resolução do exercício 2 deste teste dos anos anteriores. Estou maioritariamente a usar leis de conversos e divisão de funções mas não consigo chegar ao resultado de ambos os lados. Devo passar tudo para pointwise?
\begin{eqnarray} && id \atmost \frac f g \comp \frac f g \just\equiv {(5.49)} id \atmost \conv g \comp f \comp \conv g \comp f \just\equiv {leis de 'shunting'} g \comp \conv f \atmost f \comp \conv g \just\equiv {(5.137), (5.16), (5.17)} f \comp \conv g \atmost \conv{(f \comp \conv g)} \\ ~ \end{eqnarray}R: Pointwise não, iria ser um "overkill"! Se substituir o lado direito da igualdade pela sua definição, terá:
Obtém, pela definição de simetria, que $f \comp \conv g$ é simétrica.
Q9 - No exercicio 3 deste teste eu acho que para $R$ ser função tenho de provar que é simples e inteira. Por isso, primeiramente, desenvolvi $R$ e cheguei a conclusão que $R = \conv{[\kons{Nothing}, Just]}$. Para prosseguir, tenho de calcular a imagem e o núcleo de $R$, etc - é isso?
R: Não! Isso seria trabalho desnecessário. Repare que $[\kons{Nothing}, Just] = \mathsf{in}$, que no enunciado se diz ser um isomorfismo (bijecção). Logo $R = \conv{\mathsf{in}}$ é bijecção também, cf. (5.38) do formulário, regra de algibeira cuja prova foi feita nas aulas.
Q10 - No exercício Q1.6 das fichas práticas, concordo com o facto de não tipar; no entanto, não percebo como é que o facto de adicionar um $\top$ na parte superior irá ajudar... Conseguia-me explicar o porquê, por favor?
\begin{eqnarray*} \rcb\forall {nt,nr}{nt\ R \ nr \vee nt\ S\ nr}{ \rcb\exists {nm} {} {nm\ I\ nr}} \end{eqnarray*}R: Como $\rarrow {Nr} I {Nome}$ e $\rarrow{Nr} {R \cup S} {Nota}$, ter-se-á $\rarrow {Nome} \top {Nota}$ em $ R \cup S \atmost \top \comp I $.
Como $nt\ \top\ nm = True$ para todo o $nt, nm$, o significado ficará o desejado:
Q11 - Surgiu uma dúvida na resolução do exercício 3 deste exame. Não basta dizer que em ambas as variantes de $S$, essa relação seria sempre mais pequena que $R$? (E como "mais que pequeno que simples é sempre simples" bastaria saber que $R$ é simples.)
R: Temos $S = R \cdot \conv f$ para $f=\conj{id}{\kons t_0}$, logo $S$ e $R$ não são comparáveis pois são de tipos diferentes e o raciocínio não pode ser esse. Ora, para vermos se $S$ é simples temos que calcular a sua imagem, $R \cdot \conv f \cdot f \cdot \conv R$. Mas esta reduz-se a $R \cdot \conv R$, pois $f$ é uma injecção - porquê? Fica essa justificação (e o caso em que $\kons t_0$ dá lugar a $\top$) para pensarem.
Q12 - A primeira alínea da questão 4 do exame de 15-2-2021 já foi assunto de uma FAQ acima. E para a segunda alínea, há alguma pista que se possa dar para a resolver?
R: Primeira dica: $id \cap ker\ R = \delta R$, o domínio de $R$; segunda dica: $R \atmost \top \cdot \delta R$. Ora vejam lá agora...
Q13 - Na resolução proposta para a questão 3 deste teste, não percebo o ponto de partida, $Maybe\;R\mathrel{=}\mathsf{in} \comp ({id}\mathbin{+}R) \comp \conv{\mathsf{in}}$...
R: $Maybe\; X$ é isomorfo a $\fun F X = 1+X$, como se mostra no diagrama. Como $\fun F R = id + R$, usamos $\mathsf{out}$ para ir de $Maybe\; X$ para $\fun F X$, corremos $\fun F R$ e regressamos ao $Maybe$ por $\mathsf{in}$.
Q14 - Tenho dificuldades em como abordar a questão 1 do teste de 16 de Janeiro de 2020.
\begin{eqnarray*} \def\Conid#1{#1} \def\Varid#1{#1} \def\alt#1#2{[#1,#2]} && {inv_{12} \;(\Conid{V},\Conid{V'})\mathrel{=}{id}\leq \alt{\Conid{V}}{\Conid{V'}}} \\ && {\mathit{inv_3} \;(\Conid{V},\Conid{V'})\mathrel{=}\Varid{dE} \comp \alt{\Conid{V}}{\Conid{V'}}\; \subseteq \;\alt{\Conid{Di}}{\Varid{dC}}} \end{eqnarray*}R: Os invariantes que se pede para verificar
\begin{eqnarray*} \def\Conid#1{#1} \def\Varid#1{#1} \def\alt#1#2{[#1,#2]} && \Varid{dE} \comp \Conid{V} \subseteq \Conid{Di} \land \Varid{dE} \comp \Conid{V'} \subseteq \Varid{dC} \end{eqnarray*}afectam as relações $V$ (entre eleitores e partidos), $V'$ (entre eleitores e candidatos), $Di$ (indicando em que distritos os partidos concorrem) e as funções $dE$ (distrito do eleitor) e $dC$ (distrito do candidato). Se aplicar a fusão-+ relacional, no caso de $inv_3$ ficará com:
Olhe para a instância Alloy e verifique se estas condições se verificam.
Q15 - No mesmo teste (16-Jan-2020), tenho dificuldade em escrever o tipo da função $\mathit{findIndices}$ por forma a poder formular o teorema grátis.
R: Tem-se \begin{eqnarray*} findIndices : t \end{eqnarray*} onde, escrito por ordem inversa \begin{eqnarray*} t = (\mathbb{Z}^\star \from a^\star) \from (\mathbb{B} \from a) \end{eqnarray*} Logo \begin{eqnarray*} R_t = (id \from R^\star) \from (id \from R) \end{eqnarray*} pois $\mathbb{Z}$ e $\mathbb{B}$ são tipos constantes, não polimórficos.
Q16 - Numa matriz de $1$'s e $0$'s, como se identifica se a relação é difuncional?
R: Ver Program Design by Calculation, páginas 227-228.
Q17 - Relativamente à última pergunta do teste de 9 de Junho de 2022, estou com dúvida em perceber o passo entre
\begin{eqnarray*} \Conid{Follows}\mathbin\cup{\kons{\Varid{v}} \comp \conv{\kons{\Varid{u}}}}\; \subseteq \;(\not=) \end{eqnarray*}e \begin{eqnarray*} \mathit{inv_2} \;\Conid{Follows}\mathrel{\wedge}\underbrace{{\kons{\Varid{v}} \comp \conv{\kons{\Varid{u}}}}\subseteq{(\not=)}}_{\Conid{WP}} \end{eqnarray*}
R: Aplique a lei (5.59) e simplifique.
Q18 - Uma dúvida comum a vários exercícios: pelo que entendi, fazer shunting de $P$ em $P \comp Q \atmost S$ não é possível a não ser que $P$ seja uma função. No entanto, o shunting de $Q$ é possível?
R: Sim, fazer shunting de $P$ em $P \comp Q \atmost S$ só é possível se $P$ for uma função - lei (5.46) do formulário - ou se $Q$ for a conversa de uma função, pela lei (5.47).
Contudo, se precisarmos mesmo de nos "livrar" de $P$ ou de $Q$ no lado inferior, temos a possiblidadde de usar as divisões, cf. leis (5.157) e (5.159).
(Em suma: "shunting" é um caso particular de divisão, apenas válido para funções.)
Q19 - No exercício 54 solicita-se a prova que $R \dagger \bot = R$. No entanto, quando o tento fazer apenas consigo obter $R \plus \bot = \bot$...
R: Pela definição (130) dos slides, tem-se $R \dagger S = S \cup R \cap \bot/\conv S$.
Fazendo $S :=\bot$, tem-se $R \dagger \bot = \bot \cup R \cap \bot/{\conv\bot} = R$, pois $\bot/\bot = \top$.
Q20 - Não percebo como realizar a prova do exercício 68 apesar de perceber informalmente que faz sentido ser verdade.
R: A estratégia é sempre começar pelo que se pretende mostrar que, de acordo com a definição (162), é \begin{eqnarray*} (g\comp f) \comp \crflx p \atmost \crflx q \comp \top \end{eqnarray*} Então: \begin{eqnarray*} && (g\comp f) \comp \crflx p \atmost \crflx q \comp \top % \just\implied { pois $f \comp \crflx p \atmost \crflx r \comp \top $ ("subir o lado inferior") } % g\comp \crflx r \comp \top \atmost \crflx q \comp \top % \just\implied { pois $g\comp \crflx r \atmost \crflx q \comp \top $ ("subir o lado inferior") } % \crflx q \comp \top \comp \top \atmost \crflx q \comp \top % \just\equiv { $\top\comp\top=\top$} % true ~ \end{eqnarray*}
Q21 - Estou com dúvidas relativamente ao exercício 5 do teste de 2021. Desenvolvi (F4) mas não consegui tirar conclusões.
R: Em exercícios como este, onde há a alternativa da lei não se verificar, é de usar a intuição antes de passar aos cálculos. Numa sobreposição $R \plus S$, onde $S$ estiver definida todas as "setas" de $R$ são eliminadas. Vejam o caso extremo em que $R=\top$ e $S$ é uma função $f$. O que acontece aqui?
Q22 - Partindo de $\dom R = \top \comp R \cap id$ podemos afirmar que $R \cap T \comp S = R \comp \dom S$?
R: Sim, mas não é imediato - há cálculos a fazer, usando (5.63) etc.
Q23 - Leis (5.62) (Distribution 1) e (5.63) (Distribution 2) do formulário: no caso da distributividade na união de relações, esta não vem acompanhada de nenhuma side condition, pelo que pode ser aplicada livremente. No caso da distributidade na interseção de relações (fórmulas referidas) temos de provar a side condition ou assumir que a mesma é verdade?
R: Nas leis distributivas referidas, tem de estar garantida a respectiva side condition para que a distributividade possa ser aplicada.
Q24 - Lei (5.104), Pairing-fusion do formulário: sei que as alternativas relacionais são iguais às funcionais. No caso do split relacional, isto já não se verifica, pois não? Cf. (5.103). Então, sempre que formos aplicar (5.104) temos de provar a side condition ou simplesmente assumir que ela é verdade?
R: É o que diz: coprodutos relacionais têm as mesmas propriedades que os funcionais. Já os splits têm uma propriedade universal mais fraca (5.103) de que resulta uma lei de fusão-$\times$ cuja side-condition tem de estar garantida.
Q25 - No exercício 63, aplicando pointwise ao apresentado e a definição pointwise da relação de interseção e da implicação, obtive o resultado:
\begin{eqnarray*} b(\leq_{mark1} \mathbin;\leq_{mark2})a & ~ \equiv ~ & mark1\ b \leq mark2\ b \land (mark1\ a \leq mark1\ b \implies mark2\ b \leq mark2\ a) \end{eqnarray*}Duvido deste resultado e estou a ter dificuldades a interpretá-lo.
R: O que obteve está bem e resulta da versão pointwise da definição de $R\mathbin;S$.
Interpretação: estamos a comparar dois alunos $a$ e $b$ dando prioridade à nota $mark1$. Se por acaso $mark1\ a = mark2\ b$, então comparamo-los pela nota $mark2$.
Q26 - No exercício 65, não consigo desenvolver nenhuma das igualdades. Tentei a igualdade indireta e a definição do operador $\plus$, complementando com Universal-(-), sem sucesso.
R: Recordar que $\crflx{false} = \bot$ e $\crflx{true} = id$.
Logo $R_{false}^f$ reduz-se ao caso tratado na Q19 acima.
O caso $R_{true}^f$ resulta em $R \plus (f \comp R) = f \comp R \cup (R \shrunkby \bot)$, que pela lei (128) dos slides dá $f \comp R$. (Há uns cálculos intermédios a fazer.)
O caso $R_{p}^{id}$ resulta em $R \plus (R \comp \crflx p)$ que é $R$. Aqui os cálculos são mais elaborados, com matéria sobre coreflexivas que não demos este ano, logo vamos ignorar este caso.
Q27 - Na questão 7 do exame de 30-01-2020, o que é que se entende por "tipo relacional"?
R: Este ano passamos apenas ao de leve por essa noção: se se verificar $f (S \from R) f$ numa "seta de Reynolds", dizemos que $f$ tem tipo relacional $\larrow R f S$, o que como sabemos quer dizer $f \comp R \atmost S \comp f$, ou seja: \begin{eqnarray*} b R a \implies (f\ b) S (f\ a) \end{eqnarray*} Esta noção pode ser estendida a relações que não são funções: dizemos que $\larrow R Q S$ se verifica sempre que $Q \comp R \atmost S \comp Q$. É o caso de $\larrow{\crflx{active}}{L}{\crflx{active}}$ no exercício em causa.
Q28 - Na resolução proposta para a teste de 09-06-2022 não compreendo 2 etapas:
R: Na primeira etapa, ${{{R}}\mathbin\cap{\bot \mathbin{/}\conv{{S}}}}$ é menor do que $R$ (por cancelamento-$\cap$) e "menor que simples é simples"; na segunda, subindo o lado inferior para $(\bot \mathbin/ {\conv S})\comp \conv S$, a garantia dada permite-nos subir ainda mais, obtendo-se a tautologia $\bot \atmost id$.
Q30 - Tenho uma dúvida na segunda parte do primeiro exercício deste miniteste. Acho que para cada par $(Aluno, Ano\ letivo)$, $\p1 \comp R$ não deve ter a mesma disciplina repetida, pois isso significaria a atribuição de duas notas finais à mesma disciplina. No entanto, não entendo que informação retirar das opções para as excluir ou incluir como opção correta.
R: Olhando para o tipo de $\p1 \comp R$, que é $A \times AL \to D$, vê-se que é impossível poder dizer alguma coisa sobre notas finais ($NF$), pois essa informação desapareceu. Terá pois que ser um dos outros casos, em que essa informação não é descartada. Ora veja lá agora...