Exercícios MT2

A tradução correta é: todos os alunos do DEI que tiveram 20 a AMAT recebem um prémio.

A estrutura $\forall x\,(A(x) \to \exists y\, B(x,y))$ lê-se "para todo o $x$ que satisfaz $A$, existe um $y$ tal que $B$". Aqui $A(x)$ é "$x$ é aluno do DEI com nota 20 a AMAT" e $B(x,y)$ é "$x$ recebe o prémio $y$".

• Todos os alunos do DEI que tiveram 20 a AMAT recebem um prémio. O universal percorre os alunos do DEI com nota 20 a AMAT e a implicação garante a existência de um prémio para cada um deles.
• Só os alunos do DEI que tiveram 20 a AMAT recebem um prémio. A fórmula não exclui que outros alunos recebam prémios; apenas garante o prémio aos do DEI com 20 a AMAT.
• Pelo menos um aluno do DEI que teve 20 a AMAT recebeu um prémio. A fórmula exige o prémio para todos esses alunos, não apenas para um.
• Quem teve 20 a AMAT recebe um prémio, seja ou não do DEI. A fórmula restringe a garantia aos alunos do DEI; não afirma nada sobre os restantes.

A tradução correta é: todos os alunos que recebem pelo menos um prémio são do DEI.

Por equivalência, $\neg A \vee \neg B \vee C$ é $A \wedge B \to C$. Assim, se $x$ é aluno de $y$ e recebe algum prémio, então $y = dei$.

• Todos os alunos que recebem pelo menos um prémio são do DEI. A disjunção equivale a $Aluno(x,y) \wedge \exists z\, RecebePremio(x,z) \to y = dei$: quem é aluno e recebe prémio tem de ser do DEI.
• Nenhum aluno do DEI recebe qualquer prémio. A fórmula não proíbe prémios no DEI; proíbe prémios fora do DEI.
• Todos os alunos que não recebem um prémio são do DEI. A condição da fórmula é receber pelo menos um prémio, não deixar de receber.
• Alguns alunos do DEI recebem um prémio. A fórmula é universal e não afirma a existência de nenhum prémio.

A tradução correta é: os estudantes que frequentam Programação não frequentam mais nenhuma unidade curricular.

O existencial negado, $\neg \exists y\, (Uc(y) \wedge Frequenta(x,y) \wedge y \neq prog)$, afirma que não existe outra unidade curricular frequentada por $x$.

• Os estudantes que frequentam Programação não frequentam mais nenhuma unidade curricular. A fórmula proíbe a existência de outra unidade curricular frequentada por quem frequenta Programação.
• Se todos os estudantes frequentarem Programação, então não frequentam mais nenhuma unidade curricular. A condição é por estudante individual, não sobre todos os estudantes em conjunto.
• Se algum estudante frequentar Programação, então nenhum estudante frequenta uma unidade curricular além de Programação. A conclusão da implicação diz respeito ao próprio $x$, não a todos os estudantes.
• Todos os estudantes frequentam Programação e mais nenhuma unidade curricular. A fórmula é uma implicação; não afirma que alguém frequenta Programação.

A fórmula é verdadeira na situação descrita.

Basta um exemplo: $x = carlos$ e $y = zupt$ satisfazem $RecebePremio(x,y)$ e $\neg Aluno(x, dei)$, pois o Carlos é do DEQ e teve 20 a ALG e a AMAT.

• Verdadeira. O Carlos é aluno do DEQ e teve 20 às duas cadeiras, logo recebe o portátil ZUPT.
• Falsa. Há pelo menos um aluno fora do DEI com prémio: o Carlos, do DEQ.

A fórmula é falsa na situação descrita.

Para $x = isabel$ (ou $x = joao$), a hipótese $Aluno(x, dei) \wedge \exists y\, Proprietario(x, y)$ é verdadeira, mas $\exists y\, RecebePremio(x, y)$ é falsa. Logo o universal é falso.

• Falsa. A Isabel e o João são alunos do DEI, têm calculadora XPTO, mas não recebem prémio algum.
• Verdadeira. A implicação falha para a Isabel e para o João, que violam a conclusão.

A fórmula é válida FO, mas não é tautologia.

Se $\exists x\, Dodec(x)$ é falso, o primeiro membro é verdadeiro. Se for verdadeiro e $\forall x\, Large(x)$ também, o primeiro membro é verdadeiro. Se $\exists x\, Dodec(x)$ for verdadeiro e houver algum objeto não grande, então existe algum objeto médio (esse objeto), e o segundo membro, $\forall x\,(Medium(x) \to \exists x\, Dodec(x))$, é verdadeiro porque $\exists x\, Dodec(x)$ se verifica. A validade usa o significado dos quantificadores, pelo que não é tautologia.

• Tautologia. Abstraindo proposicionalmente, a fórmula é $(P \to Q) \vee S$, que não é sempre verdadeira.
• Válida FO mas não tautologia. Se existir algum dodecaedro e nem tudo for grande, então existe algum objeto médio; nesse caso o segundo membro garante $\exists x\, Dodec(x)$. Se não houver objetos médios, o segundo membro é vacuamente verdadeiro.
• Satisfazível mas não verdade lógica. A fórmula é verdadeira em todas as estruturas, não apenas em algumas.
• Não satisfazível. Há estruturas que a satisfazem, por exemplo um mundo só com dodecaedros grandes.

A fórmula é uma tautologia.

Sejam $P = \exists x\, Estudante(x)$ e $Q = \forall y\,(Curso(y) \wedge Matricula(ana,y))$. A fórmula é $P \to (Q \to P)$, que é verdadeira qualquer que seja o valor de $P$ e $Q$.

• Tautologia. Abstraindo proposicionalmente, a fórmula tem a forma $P \to (Q \to P)$, que é sempre verdadeira.
• Válida FO mas não tautologia. A validade já se vê ao nível proposicional, logo é tautologia.
• Satisfazível mas não verdade lógica. É verdadeira em todas as estruturas.
• Não satisfazível. É satisfeita, por exemplo, num mundo sem estudantes.

$\exists x\,\exists y\,\exists z\, ((P(a, x) \wedge \neg S(x, z)) \to (\neg Q(y, b) \wedge \neg R(y)))$.

A implicação $A \to \neg B$ equivale a $\neg A \vee \neg B$. Tem-se $\neg \forall x\, P(a,x) \equiv \exists x\, \neg P(a,x)$, $\neg \forall x\,\forall z\, \neg S(x,z) \equiv \exists x\,\exists z\, S(x,z)$ e $\neg \forall x\,(Q(x,b) \vee R(x)) \equiv \exists x\,(\neg Q(x,b) \wedge \neg R(x))$. Juntando e renomeando variáveis para evitar capturas, obtém-se $\exists x\,(\neg P(a,x) \vee \exists z\, S(x,z)) \vee \exists y\,(\neg Q(y,b) \wedge \neg R(y))$, que em prenexa dá $\exists x\,\exists y\,\exists z\,((P(a,x) \wedge \neg S(x,z)) \to (\neg Q(y,b) \wedge \neg R(y)))$.

$\forall x\,\exists y\,\forall u\,\exists v\, (P(a, x, y) \wedge \neg Q(v, b) \wedge \neg R(u))$.

$\neg(A \to B) \equiv A \wedge \neg B$, com $A = \forall x\,\exists y\, P(a,x,y)$ e $\neg B = \forall x\,(\exists y\, \neg Q(y,b) \wedge \neg R(x))$. Renomeando as variáveis repetidas ($x \to u$, $y \to v$ no segundo bloco), obtém-se $\forall x\,\exists y\, P(a,x,y) \wedge \forall u\,\exists v\,(\neg Q(v,b) \wedge \neg R(u))$, cuja prenexa é $\forall x\,\exists y\,\forall u\,\exists v\,(P(a,x,y) \wedge \neg Q(v,b) \wedge \neg R(u))$.

$\forall x\,\exists y\,\forall u\,\exists v\, ((A(x, y) \wedge C(x, u)) \to C(x, v))$.

A implicação $A \to B$ equivale a $\neg A \vee B$. Como $A$ está precedido de $\forall y$ e contém $\exists u$, e $B = \exists u\, C(x,u)$ tem de ser renomeado para $\exists v\, C(x,v)$, a prenexa correcta é $\forall x\,\exists y\,\forall u\,\exists v$.

• $\forall x\,\exists y\,\forall u\,\exists v\, ((A(x, y) \wedge C(x, u)) \to C(x, v))$. O antecedente $\forall y\,(A(x,y) \wedge \exists u\, C(x,u))$ passa a $\exists y\,\forall u$ e o consequente $\exists u\, C(x,u)$ passa a $\exists v\, C(x,v)$, com as variáveis todas distintas.
• $\forall x\,\forall y\,\exists u\,\exists v\, ((A(x, y) \wedge C(x, u)) \to C(x, v))$. O $y$ do antecedente fica depois de um universal no prenexo, mas o $\exists u$ interno tem de sair para fora de $\forall y$.
• $\forall x\,\exists y\,\forall u\, ((A(x, y) \wedge C(x, u)) \to C(x, u))$. O $u$ do consequente é um existencial novo e não pode ficar ligado ao $u$ do antecedente.
• $\forall x\,\exists y\,\forall u\,\exists u\, ((A(x, y) \wedge C(x, u)) \to C(x, u))$. A variável $u$ aparece duas vezes como quantificada, o que não é permitido numa prenexa.

Sim, o argumento é válido: de $P(c) \wedge Q(c)$ e de $P(c) \to (\neg R(c) \to \neg Q(c))$ segue $Q(c) \to R(c)$ (contrapositivo), logo $R(c)$ e portanto $\exists x\, R(x)$.

A contrapositiva de $\neg R(x) \to \neg Q(x)$ é $Q(x) \to R(x)$. Instanciando o universal em $c$ e o existencial numa testemunha $c$ com $P(c) \wedge Q(c)$, obtém-se $R(c)$ por modus ponens duas vezes.

O argumento é válido: de $P(z)$ e $P(z) \to Q(z)$ sai $Q(z)$; da contrapositiva de $\neg R(z) \to \neg Q(z)$, que é $Q(z) \to R(z)$, sai $R(z)$; logo $\exists x\, R(x)$.

A segunda premissa equivale a $\forall x\,(Q(x) \to R(x))$. Com a testemunha $z$ de $\exists z\, P(z)$, a cadeia $P(z) \Rightarrow Q(z) \Rightarrow R(z)$ prova a conclusão.

Não é consequência lógica. Contraexemplo: um mundo com dois cubos $a, b$ e um tetraedro $c$.

No mundo proposto, $a$ e $b$ têm a mesma forma e são os únicos com essa forma, logo a fórmula dada é verdadeira. Mas o tetraedro $c$ é o único da sua forma, pelo que $card(c) = 1 \neq 2$, e $\forall x\,(card(x) = 2)$ é falso. Como há uma estrutura onde as premissas são verdadeiras e a conclusão é falsa, não há consequência lógica.

É reflexiva ($altura(a) \geq altura(a)$), transitiva e antissimétrica, mas não simétrica. É uma ordem parcial, não total, porque duas pessoas com alturas diferentes não são comparáveis nos dois sentidos.

A reflexividade e a transitividade seguem das propriedades de $\geq$ em $\mathbb R$. Se $aRb$ e $bRa$, então $altura(a) = altura(b)$, logo vale a antissimetria. Não é simétrica: basta uma pessoa mais alta que outra. Como há pares não comparáveis (alturas distintas), não é ordem total.

$R$ é relação de equivalência e $[Mariana] = \{Maria, Mariana\}$.

A igualdade de alturas é reflexiva, simétrica e transitiva, logo define uma equivalência. A classe da Mariana reúne todas as pessoas com a mesma altura que ela, ou seja, a Maria (160 cm) e a própria Mariana.

Há $2^4 = 16$ relações binárias e $2^3 = 8$ contêm o par $(0, 1)$.

Uma relação binária em $\{0,1\}$ é um subconjunto de $\{0,1\} \times \{0,1\}$, que tem 4 pares, logo há $2^4 = 16$ relações. Se $(0,1)$ tem de pertencer, restam 3 pares opcionais, logo há $2^3 = 8$ relações.

São bijeções $f(x) = 2x + 1$ e $f(x) = x^3$. As outras duas não o são.

$2x+1$ é injetiva e sobrejetiva (inversa $(y-1)/2$). $x^3$ também o é (inversa $\sqrt[3]{y}$). $x^2+1$ não é injetiva ($f(1)=f(-1)$) nem sobrejetiva (imagem $[1,+\infty[$). A rácio $(x^2+1)/(x^2+2)$ não é injetiva (é par) e a sua imagem é $[1/2, 1[$, logo também não é sobrejetiva.