# Exercícios MT1

Questões de exames antigos de Matemática Discreta, com resolução.

Página: https://resumos.rgo.pt/cadeiras/md/exercicios-mt1/

## Tradução para lógica de primeira ordem

Traduzir a história das duas lojas para lógica de primeira ordem

Teste 1, 2019/20

O José e o Pedro são irmãos. Em 2008 o José emigrou para Paris e aí abriu, nesse ano, uma loja chamada "pérola do Eliseu". Em 2011 o Pedro abriu uma loja em Lisboa, que se chama "pérola do Chiado". O vinho do Porto é o artigo mais vendido em ambas as lojas. Quando o José vende mais do que 300 garrafas de vinho do Porto, o Pedro envia-lhe o stock disponível de vinho do Porto e, em troca, recebe do José o stock disponível de vinho da Madeira.

Defina uma linguagem de lógica de primeira ordem adequada para representar a situação, indicando as constantes, os predicados e as funções (com o significado de cada um), e traduza para essa linguagem todas as frases acima.

Solução

Constantes: jose, pedro, paris, lisboa, 2008, 2011, 300, peroladoeliseu, peroladochiado, vinhodoporto, vinhodamadeira. Função: maisvendido(x), o artigo mais vendido na loja x. Predicados: Irmao(x,y), Emigrou(x,y,t), AbriuLoja(x,y,z,t), VendeMaisQue(x,y,z), EnviaStock(x,y,z), e a igualdade.

Traduções: Irmao(jose, pedro); Emigrou(jose, paris, 2008); AbriuLoja(jose, peroladoeliseu, paris, 2008); AbriuLoja(pedro, peroladochiado, lisboa, 2011); maisvendido(peroladoeliseu) = vinhodoporto ∧ maisvendido(peroladochiado) = vinhodoporto; VendeMaisQue(jose, 300, vinhodoporto) → (EnviaStock(pedro, jose, vinhodoporto) ∧ EnviaStock(jose, pedro, vinhodamadeira)).

Cada facto da narrativa corresponde a uma fórmula atómica ou a uma conjunção/implicação de fórmulas atómicas. A frase condicional exige uma implicação cujo antecedente é VendeMaisQue(jose, 300, vinhodoporto) e o consequente é a conjunção dos dois envios de stock.

Confere a tua resposta:

*   A resposta define constantes, predicados e funções com significado descrito.
*   A resposta traduz corretamente a frase condicional sobre o envio de stock.
*   A resposta traduz o facto de o vinho do Porto ser o mais vendido nas duas lojas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/quantificadores/#dom%C3%ADnio-e-tradu%C3%A7%C3%A3o)

Traduzir um cenário de contas bancárias para lógica de primeira ordem

Teste 1, 2016/17

As empresas clientes de um banco podem ter dois tipos de contas, contas à ordem e contas a prazo, a cada uma das quais está associado um determinado saldo. Para além disso, as empresas podem ou não ser elegíveis para contrair empréstimos.

"NRG", "XPTO", "SUN" e "UNIV" são empresas. A XPTO tem um saldo de 5000€ na sua conta à ordem. A NRG tem um saldo à ordem de 3000€ e um saldo a prazo de 20000€. O saldo à ordem da SUN, que é uma subsidiária da UNIV, é superior ao saldo a prazo da XPTO. Se a soma dos saldos à ordem e a prazo da UNIV for superior a 20000€, então a UNIV é elegível para um empréstimo.

Defina uma linguagem de lógica de primeira ordem adequada para representar a situação, indicando constantes, predicados e funções, e traduza para essa linguagem cada uma das frases acima.

Solução

Constantes: nrg, xpto, sun, univ, ordem, prazo. Predicados: Empresa(x), TemSaldo(x,y,z), Emprestimo(x). Funções: saldoOrdem(x), saldoPrazo(x), subsidiaria(x).

Traduções: Empresa(nrg) ∧ Empresa(xpto) ∧ Empresa(sun) ∧ Empresa(univ); TemSaldo(xpto, 5000, ordem); TemSaldo(nrg, 3000, ordem) ∧ TemSaldo(nrg, 20000, prazo); saldoOrdem(subsidiaria(univ)) > saldoPrazo(xpto) ∧ subsidiaria(univ) = sun; saldoOrdem(univ) + saldoPrazo(univ) > 20000 → Emprestimo(univ).

A hierquia "SUN é subsidiária da UNIV" traduz-se por subsidiaria(univ) = sun, e a comparação de saldos usa as funções de saldo aplicadas aos termos adequados. A última frase é uma implicação entre uma comparação de soma de saldos e o predicado de elegibilidade.

Confere a tua resposta:

*   A resposta define as funções saldoOrdem(x), saldoPrazo(x) e subsidiaria(x).
*   A resposta traduz corretamente a frase sobre a subsidiária da UNIV.
*   A resposta traduz a frase condicional sobre o empréstimo da UNIV.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/quantificadores/#dom%C3%ADnio-e-tradu%C3%A7%C3%A3o)

Tradução de "O gato mia e o urso gosta de mel"

Teste 1, 2019/20

Qual é a tradução em lógica de primeira ordem da frase "O gato mia e o urso gosta de mel"?

Solução

$operatorname{Mia}(operatorname{gato}) wedge operatorname{Gosta}(operatorname{urso}, operatorname{mel})$.

Na linguagem de primeira ordem, os verbos são predicados e os nomes são constantes: "mia" é propriedade do gato, "gosta de mel" é uma relação entre o urso e o mel, e as duas afirmações unem-se por $wedge$.

*   **$operatorname{Gato}(operatorname{mia}) wedge operatorname{Urso}(operatorname{gostaMel})$.** Trata os verbos como argumentos de predicados unários, em vez de predicados sobre os animais.
*   **$operatorname{Mia}(operatorname{gato}) wedge operatorname{Gosta}(operatorname{urso}, operatorname{mel})$.** Mia é predicado do gato e Gosta é predicado binário do urso e do mel, ligados por conjunção.
*   **$operatorname{Mia}(operatorname{gato}) o operatorname{Gosta}(operatorname{urso}, operatorname{mel})$.** Usa implicação, mas a frase original usa "e".
*   **$operatorname{Animais}(operatorname{gato} wedge operatorname{ursoGostaMel})$.** Coloca uma conjunção de termos dentro de um predicado unário.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/quantificadores/#dom%C3%ADnio-e-tradu%C3%A7%C3%A3o)

Passar uma fórmula de primeira ordem para linguagem natural

Teste 1, 2019/20

Considere a linguagem em que Nota(x, n, t) significa "a aluna x teve a nota n no teste t" e Faz(x, t) significa "a aluna x tem de fazer o teste t". Qual é a tradução para linguagem natural de $(operatorname{Nota}(operatorname{ana}, 20, t1) wedge operatorname{Nota}(operatorname{carolina}, 20, t1)) o ( egoperatorname{Faz}(operatorname{ana}, t2) wedge egoperatorname{Faz}(operatorname{carolina}, t2))$?

Solução

Se a Ana e a Carolina tiverem 20 no teste 1, então não têm que fazer o teste 2.

A fórmula tem a forma $(A wedge B) o (C wedge D)$, que em linguagem natural é "se A e B, então C e D".

*   **A Ana e a Carolina tiveram 20 no teste 1 e não têm que fazer o teste 2..** Escreve a implicação como uma conjunção de factos.
*   **Se a Ana e a Carolina tiverem 20 no teste 1, então não têm que fazer o teste 2..** O antecedente é a conjunção das duas notas e o consequente é a conjunção das duas negações.
*   **A Ana e a Carolina não têm que fazer o teste 2, mas têm que tirar 20 no teste 1..** Inverte o sentido da implicação.
*   **A Ana e a Carolina não têm que fazer o teste 1 se tiverem 20 no teste 2..** Troca os testes 1 e 2 e altera a estrutura lógica.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/quantificadores/#dom%C3%ADnio-e-tradu%C3%A7%C3%A3o)

## Lógica proposicional

Forma normal disjuntiva de uma bicondicional

Teste 1, 2019/20

Obtenha uma expressão equivalente a $( eg P o R) leftrightarrow (P o eg Q)$ na forma normal disjuntiva, apresentando a cadeia de equivalências.

Solução

( eg P o R) leftrightarrow (P o eg Q) Leftrightarrow ( eg Q wedge P) ee ( eg P wedge R) ee ( eg Q wedge R).

A bicondicional desdobra-se em $(( eg P o R) o (P o eg Q)) wedge ((P o eg Q) o ( eg P o R))$. Eliminando as implicações e distribuindo, os únicos casos verdadeiros são: $P$ verdadeiro e $Q$ falso; $P$ falso e $R$ verdadeiro; $Q$ falso e $R$ verdadeiro.

Confere a tua resposta:

*   A resposta expande a bicondicional como conjunção das duas implicações.
*   A resposta chega a ( eg Q wedge P) ee ( eg P wedge R) ee ( eg Q wedge R).

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/logica-proposicional/#formas-normais)

Forma normal conjuntiva de uma implicação dupla

Teste 1, 2016/17

Obtenha uma expressão equivalente a (P o R) o ((P ee Q) o R) na forma normal conjuntiva.

Solução

P ee eg Q ee R.

(P o R) o ((P ee Q) o R) Leftrightarrow eg( eg P ee R) ee ( eg(P ee Q) ee R) Leftrightarrow (P wedge eg R) ee ( eg P wedge eg Q) ee R. Na forma normal conjuntiva, as cláusulas com $P$ e $ eg P$ ou com $R$ e $ eg R$ são tautológicas e desaparecem, restando apenas P ee eg Q ee R.

Confere a tua resposta:

*   A resposta elimina as implicações: (P wedge eg R) ee ( eg P wedge eg Q) ee R.
*   A resposta simplifica para a cláusula única P ee eg Q ee R.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/logica-proposicional/#formas-normais)

Completude de uma única conetiva binária

Teste 1, 2016/17

Defina uma conetiva binária $*$ pela tabela de verdade em que $A * B$ é verdadeiro sse $A$ é verdadeiro e $B$ é falso (assim, por exemplo, $operatorname{True} * B Leftrightarrow eg B$). Dispondo apenas de portas $*$ e do valor constante $operatorname{True}$, será possível implementar qualquer expressão da lógica proposicional? Justifique, mostrando como implementar a negação, a conjunção e a disjunção (ou a implicação).

Solução

Sim, o conjunto ${*}$ é completo. Com $operatorname{True} * B = eg B$ obtém-se a negação; depois $A wedge B = A * (operatorname{True} * B)$ e A ee B = operatorname{True} \* ((operatorname{True} \* A) \* (operatorname{True} \* B)).

Como $* mathrm{e} wedge$ com o segundo argumento negado, a negação sai diretamente com a entrada constante $operatorname{True}$. A conjunção resulta de negar duas vezes o segundo operando, e a disjunção segue de De Morgan a partir da negação e da conjunção.

Confere a tua resposta:

*   A resposta identifica $A * B$ como $A wedge eg B$.
*   A resposta mostra a negação: $ eg B = operatorname{True} * B$.
*   A resposta mostra a conjunção e a disjunção usando apenas $*$ e $operatorname{True}$, concluindo que o conjunto é completo.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/logica-proposicional/#conjuntos-completos-de-conetivas)

Classificar a fórmula (s ∨ ¬p) → (q ∧ ¬p)

Teste 1, 2022/23

A fórmula do cálculo proposicional (s ee eg p) o (q wedge eg p) é:

Solução

Nenhuma das anteriores: a fórmula não é tautologia nem contradição.

Com $s=V$, $p=F$, $q=V$ tem-se (V ee V) o (V wedge V) = V, e com $s=V$, $p=F$, $q=F$ tem-se $V o F = F$. Logo a fórmula é satisfazível mas não válida.

*   **Uma tautologia..** Para $s=V$, $p=F$, $q=F$ a fórmula é falsa.
*   **Uma contradição..** Para $s=V$, $p=F$, $q=V$ a fórmula é verdadeira.
*   **Nenhuma das anteriores..** A fórmula toma ambos os valores: é falsa para $s=V$, $p=F$, $q=F$ e verdadeira para $s=V$, $p=F$, $q=V$.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/logica-proposicional/#consequ%C3%AAncia-e-contraexemplos)

Consequência semântica de um conjunto de fórmulas

Teste 1, 2022/23

Qual das seguintes fórmulas é uma consequência semântica do conjunto {(s o eg q) ee p, (p ee q) o s}?

Solução

eg q ee p é consequência semântica do conjunto dado.

Para haver contraexemplo a eg q ee p, é preciso $q=V$ e $p=F$. Nessas condições, (p ee q) o s só é verdadeira com $s=V$, mas nesse caso (s o eg q) ee p é falsa. Portanto toda a afetação que satisfaz as premissas satisfaz eg q ee p.

*   **$s wedge eg q$.** A afetação $s=F$, $p=F$, $q=F$ satisfaz as premissas mas não satisfaz $s wedge eg q$.
*   **eg q ee p.** Se eg q ee p fosse falsa, teríamos $q=V$ e $p=F$; a segunda premissa obriga então $s=V$, mas a primeira fica falsa. Logo não há contraexemplo.
*   **s o (q ee p).** A afetação $s=V$, $p=F$, $q=F$ satisfaz as premissas mas não satisfaz s o (q ee p).

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/logica-proposicional/#consequ%C3%AAncia-e-contraexemplos)

Forma normal negativa de uma disjunção negada

Teste 1, 2022/23

Determine a forma normal negativa de eg((s o eg p) ee ( eg q wedge p)).

Solução

s wedge p wedge (q ee eg p).

eg((s o eg p) ee ( eg q wedge p)) Leftrightarrow eg( eg s ee eg p) wedge eg( eg q wedge p) Leftrightarrow (s wedge p) wedge (q ee eg p). Na forma normal negativa só restam negações aplicadas a variáveis.

Confere a tua resposta:

*   A resposta aplica De Morgan e a dupla negação: $s wedge p wedge eg( eg q wedge p)$.
*   A resposta indica s wedge p wedge (q ee eg p).

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/logica-proposicional/#formas-normais)

## Provas formais em Fitch

Prova em Fitch da transitividade da implicação

Teste 1, 2019/20

Prove formalmente, sem premissas e usando o sistema de Fitch (sem usar a regra "Con"), que $(A o B) o [(B o C) o (A o C)]$ é uma tautologia.

Solução

1.  $A o B$ (hipótese)\\quad 2. $B o C$ (hipótese)\\quad 3. $A$ (hipótese)\\quad 4. $B$ ($ o$E, 1, 3)\\quad 5. $C$ ($ o$E, 2, 4)\\quad 6. $A o C$ ($ o$I, 3-5)\\quad 7. $(B o C) o (A o C)$ ($ o$I, 2-6)\\quad 8. $(A o B) o [(B o C) o (A o C)]$ ($ o$I, 1-7).

A transitividade prova-se assumindo sucessivamente os três antecedentes e chaining duas eliminações da implicação; as introduções da implicação fecham as caixas na ordem inversa.

Confere a tua resposta:

*   A prova abre três caixas encaixadas com ipotesi $A o B$, $B o C$ e $A$.
*   A resposta deriva $B$ e depois $C$ por eliminación da implicação e fecha as caixas por introducción da implicação.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/provas-proposicionais/#regras-b%C3%A1sicas)

Prova por casos de P ∨ R

Teste 1, 2016/17

Prove formalmente, recorrendo ao sistema de Fitch, que P ee R é consequência de P ee Q e de eg Q ee R.

Solução

De P ee Q e eg Q ee R: no caso $P$, P ee R por eeI; no caso $Q$, de eg Q ee R segue $R$ (pois $ eg Q$ é falso) e depois P ee R por eeI. Logo P ee R.

É o silogismo disjuntivo: ou vale $P$, ou vale $Q$; se vale $Q$, a segunda premissa obriga a $R$. Em qualquer dos casos, P ee R.

Confere a tua resposta:

*   A prova usa eliminação da disjunção sobre P ee Q.
*   No caso $P$ conclui P ee R por introdução da disjunção; no caso $Q$, deriva $R$ de eg Q ee R e conclui P ee R.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/provas-proposicionais/#provar-por-casos)

Argumento inválido: indicar um contraexemplo

Teste 1, 2016/17

Será que de $(P wedge Q) o S$ e de eg S ee R se pode concluir $(P o R) wedge (Q o R)$? Em caso afirmativo, prove-o; em caso negativo, indique um contraexemplo (uma afetação que satisfaz as premissas e falsifica a conclusão).

Solução

Não se pode concluir. Contraexemplo: $P=V$, $Q=F$, $R=F$, $S=F$. As premissas são verdadeiras: $(V wedge F) o F = V$ e eg F ee F = V. Mas a conclusão $(V o F) wedge (F o F) = F wedge V = F$.

As premissas só garantem que, quando $P$ e $Q$ são ambos verdadeiros, $R$ também o é (pois $S$ seria verdadeiro e eg S ee R obriga a $R$). Com $Q$ falso, a conclusão exige $P o R$, que falha no contraexemplo.

Confere a tua resposta:

*   A resposta responde que não se pode concluir.
*   A resposta dá uma afetação com $P=V$, $Q=F$, $R=F$, $S=F$ (ou equivalente).
*   A justificação verifica que as premissas são verdadeiras e a conclusão é falsa nessa afetação.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/provas-proposicionais/#nega%C3%A7%C3%A3o-e-contradi%C3%A7%C3%A3o)

Dedução de θ → (γ → ϕ) em Fitch

Teste 1, 2022/23

Usando o sistema de dedução em notação de Fitch, mostre que ( heta wedge gamma) o phi dash heta o (gamma o phi), anotando as regras de cada passo.

Solução

1.  $( heta wedge gamma) o phi$ (premissa)\\quad 2. $ heta$ (hipótese)\\quad 3. $gamma$ (hipótese)\\quad 4. $ heta wedge gamma$ ($wedge$I, 2, 3)\\quad 5. $phi$ ($ o$E, 1, 4)\\quad 6. $gamma o phi$ ($ o$I, 3-5)\\quad 7. $ heta o (gamma o phi)$ ($ o$I, 2-6).

É a regra de curryficação: a conjunção dos dois antecedentes pode ser reescrita como duas implicações encaixadas, bastando introduzir as hypothèses e eliminar a conjunção e a implicação.

Confere a tua resposta:

*   A prova abre as hipótesis $ heta$ e $gamma$ em caixas encaixadas.
*   A resposta deriva $ heta wedge gamma$ por $wedge$I e $phi$ por $ o$E, fechando com duas $ o$I.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/provas-proposicionais/#regras-b%C3%A1sicas)

## Quantificadores e semântica

Fórmula de primeira ordem que não é válida

Teste 1, 2022/23

Qual das seguintes fórmulas de lógica de primeira ordem não é válida?

Solução

A fórmula não válida é $(exists w, gamma wedge exists w, phi) o exists w, (gamma wedge phi)$.

Os quantificadores existenciais em separado não garantem a mesma testemunha. Num domínio ${1, 2}$ com $gamma = {1}$ e $phi = {2}$, o antecedente é verdadeiro e o consequente falso.

*   **(exists w, gamma ee exists w, phi) o exists w, (gamma ee phi).** É válida: se existe algum $w$ com $gamma$ ou algum $w$ com $phi$, existe um $w$ com gamma ee phi.
*   **(orall w, gamma ee orall w, phi) o orall w, (gamma ee phi).** É válida: se $gamma$ vale para todos ou $phi$ vale para todos, então gamma ee phi vale para todos.
*   **$(exists w, gamma wedge exists w, phi) o exists w, (gamma wedge phi)$.** Não é válida: o $w$ que satisfaz $gamma$ pode ser diferente do $w$ que satisfaz $phi$. Por exemplo, num domínio com dois elementos em que $gamma$ só vale no primeiro e $phi$ só no segundo.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/semantica-primeira-ordem/#validade-satisfazibilidade-e-modelos)

Forma normal prenexa de uma fórmula negada

Teste 1, 2022/23

Qual das seguintes opções não é uma forma normal prenexa de eg(orall w, R(w) o exists w, eg(exists y, Q(y, w) wedge orall x, P(x)))?

Solução

A fórmula eg(orall w, R(w) o exists w, eg(exists y, Q(y, w) wedge orall x, P(x))) equivale a orall w, orall x, exists y (R(w) wedge Q(y, w) wedge P(x)); a opção com $Q(y, z)$ não é prenexa dessa fórmula.

$ eg(A o B) Leftrightarrow A wedge eg B$, logo a fórmula fica orall w, R(w) wedge orall w, (exists y, Q(y, w) wedge orall x, P(x)). Na forma prenexa, o existencial $exists y$ fica depois dos universais e a matriz é $R(w) wedge Q(y, w) wedge P(x)$, com $Q$ a depender de $w$.

*   **orall x, exists y, orall z, orall w (R(w) wedge Q(y, z) wedge P(x)).** Não é equivalente: na matriz, $Q(y, z)$ deveria ser $Q(y, w)$, pois a testemunha $y$ depende do $w$ quantificado em $R(w)$.
*   **orall x, orall w, exists y (R(w) wedge Q(y, w) wedge P(x)).** É uma forma normal prenexa equivalente da fórmula dada.
*   **orall w, orall x, exists y (R(w) wedge Q(y, w) wedge P(x)).** É outra forma normal prenexa equivalente, com a ordem dos universais trocada.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/semantica-primeira-ordem/#forma-normal-prenexa)

Substituição sem captura numa fórmula com quantificadores

Teste 1, 2022/23

Seja gamma = (orall x, eg exists y, orall u, P(x, y)) o eg(exists z, P(x, y) o orall y, P(u, y)). Determine $gamma[f(a, b)/y]$, onde $f$ é uma função de aridade 2 e $a$, $b$ são constantes.

Solução

gamma\[f(a, b)/y\] = (orall x, eg exists y, orall u, P(x, y)) o eg(exists z, P(x, f(a, b)) o orall y, P(u, y)).

Na expressão, $y$ ocorre livre apenas em $P(x, y)$ dentro de $exists z$; nas restantes ocorrências está ligada pelos quantificadores $exists y$ e orall y. A substituição só pode ser feita em variáveis livres, para não haver captura.

Confere a tua resposta:

*   A resposta substitui apenas as ocorrências livres de $y$: em $exists z, P(x, y)$.
*   A resposta mantém orall y, P(u, y) inalterado, pois aí $y$ está ligada.
*   A resposta indica (orall x, eg exists y, orall u, P(x, y)) o eg(exists z, P(x, f(a, b)) o orall y, P(u, y)).

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/md/quantificadores/#substitui%C3%A7%C3%A3o-sem-captura)