Terceira Prova de L´ ogica para Computa¸ c˜ ao (Reposi¸ c˜ ao) Professor Adolfo Neto (DAINF - UTFPR) Data: 8 de Junho de 2009 Aluno(a):

1a

Quest˜ ao (0,5 ponto)

´ poss´ıvel unificar os termos “p(g(x),g(h(x)),y,t,t)” e “p(g(w),g(h(f(b))),z,c,x)”? Responda “sim” ou “n˜ao”. Se a sua resposta E for “sim”, escreva uma unifica¸c˜ ao mais geral que unifique os dois termos. Se a sua resposta for “n˜ao”, explique o porquˆe. Descreva todos os passos do algoritmo que vocˆe utilizou.

2a

Quest˜ ao (1 ponto)

O que ´e um provador autom´ atico de teoremas? Com que l´ogica trabalha o provador de teoremas Otter? Que m´etodo de prova ele utiliza? Que m´etodo de prova o provador de teoremas KEMS utiliza? Com que l´ogicas ele trabalha?

3a

Quest˜ ao (1,5 ponto)

Na fase semifinal da competi¸c˜ ao de futebol (imagin´aria) chamada Copa do Sul II, dois times disputam uma vaga para a grande final. Uma das semifinais do ano de 2009 est´a sendo entre Coritiba e Internacional. Na primeira partida, em Porto Alegre, o Inter ganhou de 3 a 1. A segunda partida ser´a nesta semana em Curitiba e apenas alguns resultados podem levar o Coxa (apelido carinhoso do Coritiba) para a final. Os resultados na partida em Curitiba que permitir˜ao que o Coxa seja finalista s˜ ao: • ganhar a partida por trˆes ou mais gols de diferen¸ca; • ganhar a partida por dois gols de diferen¸ca, desde que fa¸ca mais do que trˆes gols; • ganhar a partida por trˆes a um e ganhar a disputa de pˆenaltis. A “l´ ogica” da competi¸c˜ ao ´e: 1. se um time fizer mais gols que o outro nas duas partidas, leva a vaga; 2. se houver empate no n´ umero de gols, leva a vaga quem fizer mais gols em casa; 3. se ainda assim persistir o empate, haver´ a uma disputa de no m´aximo 5 pˆenaltis. Se persistir o empate, o time que jogou a primeira em casa leva a vaga. A tarefa desta quest˜ ao ´e especificar formalmente (vocˆe escolhe o formalismo) uma opera¸c˜ao que recebe como entrada 6 valores inteiros, nesta sequencia: gols time1 jogo1, gols time1 jogo2, gols time1 penaltis, gols time2 jogo1, gols time2 jogo2, gols time2 penaltis. Onde gols time1 jogo1 s˜ ao os gols do time 1 no jogo 1 (suponha que o time 1 joga a primeira em casa). As pr´e-condi¸c˜ oes devem impedir que a entrada contenha valores negativos para os gols. Por defini¸c˜ao, se n˜ ao houver disputa de pˆenaltis, os valores dos gols dos times na disputa de pˆenaltis ser˜ao iguais a 0. Al´em disso, suponha que estes valores (os valores dos gols dos times na disputa de pˆenaltis) ser˜ao 0 se os outros valores decidirem a vaga. Para as p´ os-condi¸co˜es, trabalhe supondo a existˆencia da seguinte propriedade: ganhou vaga final(i): propriedade que retorna “verdadeiro” se o time[i] ganhou a vaga para a final e “falso” em caso contr´ ario. N˜ ao ´e necess´ ario definir as opera¸c˜ oes aritm´eticas b´asicas (+, -, , =, etc.) assim como os operadores l´ogicos b´ asicos. Aten¸c˜ ao: n˜ ao esque¸ca de comentar as f´ ormulas!

4a

Quest˜ ao (1 ponto)

Escreva um texto (com aproximadamente 25 linhas) sobre o tema do trabalho que vocˆe apresentou em sala de aula. Em seu texto, responda a trˆes perguntas: • qual foi o aspecto mais importante abordado pela sua apresenta¸c˜ao? • qual ´e a sua maior d´ uvida sobre o tema da sua apresenta¸c˜ao? • qual ´e a principal aplica¸c˜ ao computacional do tema da sua apresenta¸c˜ao?

1

5a

Quest˜ ao (1 ponto)

Escreva um texto (com aproximadamente 15 linhas) sobre o tema do trabalho que vocˆe ficou encarregado de debater em sala de aula. Em seu texto, responda a trˆes perguntas: • qual foi o aspecto mais importante abordado por aquela apresenta¸c˜ao? • qual ´e a sua maior d´ uvida sobre o tema daquela apresenta¸c˜ao? • qual ´e a principal aplica¸c˜ ao computacional do tema daquela apresenta¸c˜ao?

6a

Quest˜ ao (1 ponto)

O que ´e verifica¸c˜ ao de programas? Como a verifica¸c˜ao de programas se relaciona com a especifica¸c˜ao de programas? Qual ´e a importˆ ancia da verifica¸c˜ ao de programas na vida real (isto ´e, nos sistemas que s˜ao utilizados na vida real)? Cite alguma aplica¸c˜ ao potencial de verifica¸c˜ ao de programas na sua vida como estudante. Cite uma l´ogica (vista em sala de aula) especificamente criada para verifica¸c˜ ao de programas. Qual ´e o formato das asser¸c˜oes sobre programas nesta l´ ogica? Explique cada parte da asser¸c˜ ao.

7a

Quest˜ ao (1 ponto)

Escreva um par´ agrafo (aproximadamente 20 linhas) sobre algum tema (`a sua escolha) n˜ao abordado por vocˆe nas respostas das quest˜ oes anteriores. Introduza o tema, fale sobre sua importˆancia/relevˆancia e comente algum detalhe t´ecnico relacionado ao tema.

8a

Quest˜ ao (1 ponto)

Sejam as seguintes defini¸c˜ oes (nas defini¸c˜ oes abaixo, ignore o sexo – isto ´e, ao falar “tio” estamos querendo falar “tio” ou “tia”): • Tio ´e o irm˜ ao do seu progenitor; • Primo ´e o filho do seu tio. • Primo de segundo grau ´e o primo do seu primo (desde que n˜ao seja vocˆe mesmo ou seu irm˜ao). Suponha que na nossa base de dados temos apenas fatos nos seguintes formatos: • progenitor(X,Y): indicando que X ´e o progenitor de Y; • irmao(X,Y): indicando que X ´e o(a) irm˜ ao (irm˜a) de Y. Escreva a defini¸c˜ ao do predicado primo de segundo grau(X,Y) em Prolog que seja verdadeiro quando X ´e primo de segundo grau de Y.

2