Exercícios MT1

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.

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.

$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.

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.

( 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.

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.

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.

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$.

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).

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.

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.

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.

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.

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.

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.

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.

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.