Teste LC 1 1819

L��gica Computacional

Dura??o: 1h

?poca de 2018 / 19 �C 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))

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 �C 1? Teste de Avalia??o �C 19 Outubro 2018

1/4

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

0

1

NF : Constantes

NF : Fun??es

ana, rui,

sara, elsa,

autoEstradaA1,

10000

carroDe /1

custoDe/1

anoRegisto/1

0

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 �C FO e Anal��tico �C 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

P

P

F

Cube(a) ? Tet(b) ? a = b

(?Cube(a) ? Cube(b)) ? a �� b

Dodec(a) ? ?Dodec(a) ? LeftOf(a,b)

P

F

V

F

V

F

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

Cube(a) ? Tet(a) ? Dodec(a)

L��gica Computacional

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

2/4

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 ?

N?o: ?

Sim:

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

N

S

S

N

N

N

N

N

S

? Cube(b)

{ Cube(a), Cube(b)} ? a �� b

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

{ Cube(a), a = b }

L��gica Computacional

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

3/4

7. (2.5 val) a) Preencha a tabela de verdade relativa ��s f��rmulas P1 e P2 abaixo indicadas

P1: (?A ? B) ? C

A

B

C

V

V

V

V

F

F

F

F

V

V

F

F

V

V

F

F

V

F

V

F

V

F

V

F

e

P2: (?A ? C) ? B

(?A ? B) ? C

F

F

F

F

V

V

V

V

F

F

F

F

V

V

F

F

V

F

V

F

V

V

V

F

(?A ? C) ? B

F

F

F

F

V

V

V

V

V

F

V

F

V

V

V

V

V

F

F

F

V

V

F

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

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)]}

Elimina??o

2

��

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

Associa??o

3

��

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

de Morgan

4

��

? (A ? B) ? ?C)

Absor??o

5

��

? A ? ? B ? C

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 �C 1? Teste de Avalia??o �C 19 Outubro 2018

4/4

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

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

Google Online Preview   Download