Teste LC 1 1819 corrigido

L?gica Computacional

Dura??o: 1h

?poca de 2018 / 19 ? 1? Teste de Avalia??o (sem Consulta)

Nome:

n?:

1. (2.5 val) Considere os mundos e a linguagem do Mundo de Tarski (com um tabuleiro de 3 ? 3 casas)

a) Desenhe um mundo (em 2D) em que sejam verdadeiras as seguintes f?rmulas 1. FrontOf(a,b) ? LeftOf(a,b) ? SameCol(b,d) 2. FrontOf(b,c) ? LeftOf(c,a) ? SameRow(b,d) 3. ?(SameShape(a,b) ? SameShape(b,c)) ? ? Tet(c) 4. (Tet(a) ? Dodec(c)) ? (Tet(c) ? Dodec(a))

c b,d

a

b) Verifique se a f?rmula FrontOf(f,a) ? satisfaz?vel em conjunto com as anteriores. Se sim indique uma adapta??o do mundo em que todas as f?rmulas sejam satisfeitas, e se essa adapta??o ? ?nica; caso contr?rio explique sucintamente porqu?.

A f?rmula n?o ? satisfaz?vel.

Num tabuleiro com 3 casas, estando o bloco a ? frente do bloco b e este ? frente do bloco c, ent?o o bloco a tem de estar na fila da frente.

Assim sendo, o bloco f n?o poder? ficar ? frente do bloco a.

Mas os blocos n?o est?o na mesma coluna (por 4). Assim, para estarem alinhados seria necess?rio (mas n?o suficiente) que os blocos b e c estivessem ambos ? esquerda ou ambos ? direita do bloco a, o que n?o sucede (por 4).

? poss?vel porque d ? um tetraedro.

2. (2.0 val) Traduza as seguintes frases para f?rmulas na linguagem do Mundo de Tarski. a) Os blocos a, b e c t?m todos formas diferentes. ? SameShape(a,b) ? ?SameShape(a,c) ? ?SameShape(b,c)

b) ? falso que um dos blocos a ou b seja grande. ? (Large(a) ? Large(b))

c) Os blocos d e f n?o est?o na mesma posi??o. ? SameRow(d,f) ? ? SameCol(d,f)

d) Um dos blocos a e b est? ? frente do bloco c, e o outro est? atr?s. (FrontOf(a,c) ? FrontOf(b,c)) ? (BackOf(a,c) ? BackOf(b,c))

L?gica Computacional

2018 / 2019 ? 1? Teste de Avalia??o ? 19 Outubro 2018

1/5

3. (3.0 val) Considere as seguintes frases ? O carro do Rui ? novo, mas o da Ana n?o. ? O carro do Rui custou 10000 e foi mais caro que o da Ana. ? A Ana conhece a autoestrada A1, mas a Sara n?o. ? Os carros da Ana e da Elsa foram registados no mesmo ano.

a) Apresente uma assinatura S = de uma linguagem de 1? ordem que lhe permita escrever f?rmulas de 1? ordem corespondentes

NF0: Constantes

ana, rui, sara, elsa, autoEstradaA1,

10000

NF1: Fun??es

carroDe /1 custoDe/1 anoRegisto/1

NP: Predicados

SerNovo/1 Conhece/2 =/2, >/2

b) Traduza para f?rmulas de 1? ordem as frases acima indicadas: i) O carro do Rui ? novo, mas o da Ana n?o. SerNovo(carroDe(rui)) ? ? SerNovo(carroDe(ana))

ii) O carro do Rui custou 10000 e foi mais caro que o da Ana. custoDe(carroDe(rui)) = 10000 ?

custoDe(carroDe(rui))> custoDe(carroDe(ana))

iii) A Ana conhece a autoestrada A1, mas a Sara n?o. Conhece(ana, autoEstradaA1) ? ? Conhece(sara, autoEstradaA1)

iv) Os carros da Ana e da Elsa foram registados no mesmo ano. anoRegisto(carroDe(ana)) = anoRegisto(carroDe(elsa))

4. (3.0 val) a) Indique no quadro (com V, P e F, respectivamente) se, nos diferentes n?veis de an?lise (Tautol?gico -TT, L?gico ? FO e Anal?tico ? TW) as f?rmulas abaixo s?o Verdades, meras Possibilidades ou Falsidades.

Nota 1: Uma Verdade deve ser indicada com V e n?o com P (embora o seja).

Nota 2: 3 respostas erradas na tabela eliminam uma correcta. A classifica??o nesta pergunta n?o pode ser negativa.

TT FO TW

Cube(a) ? Tet(b) ? a = b (?Cube(a) ? Cube(b)) ? a b Dodec(a) ? ?Dodec(a) ? LeftOf(a,b)

P P F P V V F F F

b) Indique, se houver, uma proposi??o P-FO que seja V-TT. Caso contr?rio escreva imposs?vel Imposs?vel

L?gica Computacional

2018 / 2019 ? 1? Teste de Avalia??o ? 19 Outubro 2018

2/5

5. (2.0 val) Para os argumentos abaixo, indique se s?o v?lidos, justificando informalmente a resposta.

a) Em geral, um bilhete de avi?o ? tanto mais caro quanto maior for a dist?ncia entre a origem e o destino da viagem. As companhias low cost t?m sempre pre?os mais baratos que as outras companhias se os bilhetes forem comprados com grande anteced?ncia. Assim sendo, se viajar no Natal, o custo de um bilhete numa companhia low cost entre Lisboa e Paris ? mais barato que um da TAP entre Lisboa e Bruxelas.

Argumento V?lido ? Sim:

N?o:

Justifica??o: O argumento n?o ? v?lido, apesar da conclus?o ser provavelmente verdadeira.

Por um lado, Paris ? mais perto que Bruxelas e por isso um bilhete para Paris deve ser mais barato, em geral. Por outro lado, um v?o low cost deve ser mais barato do que numa companhia como a TAP, especialmente se for comprado com anteced?ncia.

E, no entanto, apesar de ser uma viagem mais curta e numa companhia low cost, n?o ? garantido que o bilhete para Paris seja mais barato, j? que ambos os crit?rios (viagem mais curta e companhia low cost) apenas garantem que, em geral, o pre?o ser? mais barato, especialmente se o bilhete for comprado com anteced?ncia. Mas pode-se dar o caso da TAP estar a fazer uma promo??o de Natal, situa??o em que um bilhete nesta companhia poder? ser mais barato que um bilhete low cost, comprado sem anteced?ncia. Neste caso, ambas as premissas s?o verdadeiras mas a conclus?o ? falsa, pelo que o argumento n?o ? v?lido.

b) Algumas companhias a?reas permitem levar bagagem de por?o sem qualquer custo adicional at? um certo peso (por exemplo 23 kg), ao contr?rio do que acontece na generalidade dos casos em que se tem de pagar a bagagem de por?o. A compra de dois bilhetes no mesmo site nas mesmas condi??es (data de compra, data da viagem, companhia, seguros, etc...) tem o mesmo custo. O Jo?o comprou dois bilhetes, para si e para a Maria, nas mesmas condi??es, excepto por ter registado uma bagagem de por?o para si. Logo, o bilhete dele n?o foi mais barato do que o da Maria.

Sim:

N?o:

Justifica??o: O argumento ? v?lido.

Se o bilhete fosse comprado exatamente nas mesmas condi??es deveria ter o mesmo pre?o. Mas a ?nica diferen?a entre os bilhetes ? a bagagem de por?o associada ao bilhete do Jo?o. A bagagem de por?o geralmente torna o bilhete mais caro, mas pode n?o agravar o pre?o. O que nunca acontece ? tornar o bilhete mais barato.

Assim sendo, o bilhete do Jo?o n?o poder? ter sido mais barato.

6. (2.0 val) Considerando os mundos e a linguagem do Mundo de Tarski, indique (com S para sim e N para n?o) se os seguintes argumentos s?o v?lidos tautologicamente (Val-TT), logicamente (Val-FO) e/ou analiticamente nos mundos de Tarski (Val-TW). Nota: 3 respostas erradas na tabela eliminam uma correcta. A classifica??o da pergunta n?o pode ser negativa.

{Premissa 1, ..., Premissa n } Conclus?o

Val-TT Val-FO Val-TW

{ Cube(a), a = b } Cube(b) { Cube(a), Cube(b)} a b { Cube(a), Tet(b)} ? SameShape(a,b)

N

S

S

N

N

N

N

N

S

L?gica Computacional

2018 / 2019 ? 1? Teste de Avalia??o ? 19 Outubro 2018

3/5

7. (2.5 val) a) Preencha a tabela de verdade relativa ?s f?rmulas P1 e P2 abaixo indicadas P1: (?A ? B) ? C e P2: (?A ? C) ? B

A B C

V V V V V F V F V V F F F V V F V F F F V F F F

(?A ? B) ? C

FF V FF F FF V FF F VV V VV V VF V VF F

(?A ? C) ? B

FV V FF F FV F FF F VV V VV V VV F VV F

b) Com base na tabela assinale na caixa e justifique qual a rela??o tautol?gica entre P1 e P2

P1 ? consequ?ncia de P2

P2 ? consequ?ncia de P1

P1 e P2 s?o Equivalentes

Nenhuma das anteriores

Justifica??o: Existem duas interpreta??es ({A=V, B=F, C=V} e {A=F, B=F, C=V}) que tornam a f?rmula P1 verdadeira mas P2 falsa. Logo P2 n?o ? consequ?ncia tautol?gica de P1. Por outro lado, em todas as interpreta??es que tornam P2 verdadeira (isto ?, quando {A=V, B=V, C=V}, {A=F, B=V, C=V} ou {A=F, B=V, C=F} ), P1 tamb?m ? verdadeira, pelo que P1 ? uma consequ?ncia tautol?gica de P2.

8. (3.0 val) Converta a f?rmula seguinte (com chavetas e par?nteses retos para aumentar a legibilidade) para uma das formas normais conjuntiva (CNF) ou disjuntiva (DNF), simplificando-as da forma mais conveniente:

? {[A ? (A ? B)] ? [ B ? ?((A ? B) ? C)]}

? {[A ? (A ? B)] ? [ B ? ?((A ? B) ? C)]} 1 ? ? { A ? [ B ? ?((A ? B) ? C)]} 2 ? ? { (A ? B) ? ?((A ? B) ? C)} 3 ? ? {(A ? B) ? (?(A ? B) ? ?C)} 4 ? ? (A ? B) ? ?C) 5 ? ?A ? ?B ? C

Elimina??o Associa??o de Morgan Absor??o de Morgan

Esta f?rmula j? est? na forma CNF (conjun??o de 3 cl?usulas com 1 literal cada), n?o podendo ser simplificada.

De igual forma j? est? em DNF (1 s? mon?mio com 3 literais) n?o podendo ser simplificada.

L?gica Computacional

2018 / 2019 ? 1? Teste de Avalia??o ? 19 Outubro 2018

4/5

Resolu??o Alternativa ? {[A ? (A ? B)] ? [ B ? ?((A ? B) ? C)]}

? {[A ? (A ? B)] ? [ B ? ?((A ? B) ? C)]}

1 ? ? [A ? (A ? B)] ? ?[ B ? ?((A ? B) ? C)]}

de Morgan

2 ? [? A ? ? (A ? B)] ? [? B ? ??((A ? B) ? C)] de Morgan

3 ? [? A ? ? (A ? B)] ? [? B ? ((A ? B) ? C)]

Dupla Nega??o

4 ? [? A ? (?A ? ?B)] ? [? B ? ((A ? B) ? C)]

de Morgan

Esta f?rmula ( a menos de Associa??o) j? est? na forma CNF mas pode ser simplificada.

5 ? [(?A ? 0) ? (?A ? ?B)] ? [?B ? ((A ? B) ? C)] Elemento Neutro

6 ? [?A ? (0 ? ?B)] ? [?B ? ((A ? B) ? C)]

Distribui??o

7 ? [?A ? 0] ? [?B ? (A ? B ? C)]

Elemento Absorvente

8 ? ?A ? [?B ? (A ? B ? C)]

Elemento Neutro

9 ? ?A ? ?B ? (A ? B ? C)

Associa??o

Esta f?rmula CNF ainda pode ser simplificada

10 ? (?A ? ?B ? A) ? (?A ? ?B ? B) ? (?A ? ?B ? C) Distribui??o

Esta f?rmula j? est? na forma DNF, mas pode ser simplificada

11 ? 0 ? 0 ? (?A ? ?B ? C)

Contradi??o (e Ass e Com)

12 ? ?A ? ?B ? C

Elemento Neutro

Esta f?rmula j? est? na forma CNF (conjun??o de 3 cl?usulas com 1 literal cada), n?o podendo ser simplificada.

De igual forma j? est? em DNF (1 s? mon?mio com 3 literais) n?o podendo ser simplificada.

L?gica Computacional

2018 / 2019 ? 1? Teste de Avalia??o ? 19 Outubro 2018

5/5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download