Lógica Computacional
(cod.11555)

Departamento de Informática
Universidade da Beira Interior

Ano lectivo 2016/2017

—
Three logicians walk into a bar. The bartender says
“Do you all want something to drink?”
The first logicians says “I don’t know.”
The second logician says “I don’t know.”
The third logician says “Yes.”
—

Figure 1: from logicomix

Esta página no formato pdf

1 Novidades

Consulta/resolução da Prova Escrita do Exame: sala 6.25, Segunda Feira 6 de Fevereiro, 15:00.
Notas exame.
Só dois dos alunos que foram a exames melhoraram as notas relativamente à avaliação contínua. Os alunos são:
n^o Trab Prova ex. Nota final

34510 11,7 8,1 9,54

38535 9,7 5,5 7,18

De resto todos os outros alunos mantêm na avaliação por exame a nota da avaliação contínua por não terem melhorado na prova escrita do exame a prova escrita que resultou na avaliação contínua.
Consulta/resolução da Frequência: sala 6.25, Segunda Feira 23 de Janeiro, 15:00.
Avaliação contínua: (aqui)
Os alunos seguintes:
35887, 35585, 36458, 25382, 35445, 35407, 35373, 35264, 35696, 35802, 35536, 36295, 35760, 35964, 35388, 31845, 34683, 33823, 36609, 35302, 36195, 31167, 35206, 35474, 35354, 35223, 34518, 33995, 35864, 35388, 36644, 35334

devem dirigir-se para o gabinete do regente (sala 6.25) desta UC dia 13 de Janeiro entre as 10h00 e às 12h30, as 15h30 e às 17h30.
18/12/2016 - Prazo de entrega dos problemas B e C extendido para a semana do dia 19 de Dezembro.
15/11/2016 - Prazo de entrega do problema B extendido de uma semana.
07/11/2016 - Esta semana: Não haverá excepcionalmente aulas teóricas (esta segunda) nem aula prática PL1 (quarta feira). As restantes aulas decorrem como previsto. As aulas em causa serão repostas posteriormente.
11/10/2016 - Sala para a aula suplementar do dia 14: 4.01 (Bloco 4!)
04/10/2016 - Os Problemas C e D foram disponibilizados (e introduzidos na plataforma mooshak).
04/10/2016 - Aulas Teóricas: Mudança de sala, passamos a usar a sala 6.26.
28/09/2016 - Site com informação sobre instalação de OCaml no windows (link)
20/09/2016 - Problema B disponível e configurado no Mooshak.
20/09/2016 - Mooshak: configurado para o vosso registo e pronto para aceitar as vossas soluções ao Problema A,
20/09/2016 - Mooshak: processo de registo (link aqui).

O sistema mooshak encontra-se desde já configurado para a presente disciplina. Queira proceder ao seu registo. No processo de registo, escolhe o seu nome da seguinte forma: "a + numero de aluno + primeiro nome. Por exemplo, Luís com o numero 12345 tem por registo mooshak "a12345Luis".
19/09/2016 - Considere seguir:
A MOOC to learn functional programming with the OCaml programming language
(registos, neste link).

O curso inicia-se dia 26 de setembro e tem a duração de 6 semanas. Espera-se que haja subtítulos em Portugês!
19/09/2016 - O problema A já se encontra disponível (o mooshak ainda não) - Ver secção “Trabalhos Práticos”.
Consultar a secção 9 para aceder aos material electrónico (teórico e prático) exposto nas aulas.
Como colocar uma dúvida ao regente da Unidade Curricular?
1. Comparecer nas aulas e colocá-la directamente ao regente
2. Comparecer no horário de atendimento do regente e colocá-la directamente
3. enviar um email ao regente (desousaUUU@UUUdi.ubi.pt, (retire os UUU) ) com o assunto "LC: XXXX" em que XXX é o título da dúvida em questão. Qualquer outro formato no assunto arrisca condenar o email ao esquecimento.
Inscrição em turmas práticas: via site dos serviços académicos.
As aulas práticas começam logo na primeira semana de aulas.
Os alunos com estatuto de trabalhador estudante são convidados a dirigir-se ao regente para discutir eventuais alterações dos critérios de avaliação.
Primeira versão da página. Encontrará aqui as novidades associadas à disciplina de Lógica Computacional. A sua consulta regular é necessária ao bom funcionamento da Unidade Curricular.

1 Novidades
2 Docentes
3 Objectivos
- 3.1 Agradecimentos
4 Programa
5 Critérios de Avaliação
6 Datas Importantes
7 Horário
8 Atendimento
9 Material Pedagógico e Funcionamento da Disciplina
10 Resultados da avaliação
11 Bibliografia Principal

2 Docentes

Simão Melo de Sousa (regente) - Gabinete 3.17 - Laboratório Release (6.25) - Bloco VI.
Sérgio Magalhães

3 Objectivos

Esta disciplina apresenta as principais conceitos da Lógica, na sua vertente computacional, i.e. acompanhados dos algoritmos e das técnicas computacionais que permitam o seu uso num contexto de engenharia informática.

Competências da UC ou Resultados da Aprendizagem.

Pretende-se que o aluno aprenda as noções básicas do raciocínio lógico e seja capaz de utilizar corretamente os sistemas dedutivos; compreenda as relações entre as semânticas e os sistemas dedutivos e a sua caracterização do ponto de vista da decidibilidade; reconheça o papel dos sistemas formais nas várias áreas da Engenharia Informática.

3.1 Agradecimentos

O regente da disciplina gostaria de agradecer ao Professor Doutor António Ravarra (DI-FCT-UNL- Nova lincs) por lhe ter facultado a sebenta de Lógica Computacional de que é autor e por lhe permitido um uso livre e intensivo desta última.

4 Programa

Apresentação Contextual e Histórica da Lógica
Conjuntos Indutivos, Indução Estrutural e Bem Fundada
Lógica Proposicional
- Sintaxe:
  - Termos a partir de descrições em linguagem natural
  - Conectores lógicos
  - Definição indutiva de linguagem proposicional
  - Formas Normais: Negativa, Conjuntiva e Disjuntiva
- Semântica:
  - Tabelas de verdade e álgebra de Boole
  - Valoração e relação de satisfação
  - Validade e consequência lógica
  - Equivalência e raciocínio equacional
- Sistema semântico: algoritmos para a resolução SAT
- Sistema semântico: resolução
  - Forma normal conjuntiva e forma clausal
  - Algoritmo de Horn
  - Resolução e refutação
- Sistema dedutivo: dedução natural
  - Regras de introdução e eliminação
  - Derivação e prova
  - Coerência e Completude
Lógica de primeira ordem
- Sintaxe:
  - Termos a partir de descrições em linguagem natural
  - Alfabeto e Definição indutiva de linguagem de 1^ra ordem
  - Variáveis livres e substituição
- Semântica:
  - Valoração e estrutura de interpretação: relação de satisfação
  - Validade e consequência lógica
  - Equivalência e raciocínio equacional
- Sistemas semânticos: SMT
  - Método e algoritmo DPLL
  - Teorias de Primeira Ordem
  - Combinação de Teorias
- Sistema dedutivo: resolução
  - Forma Normal de Skolem e skolemização
  - Unificação e resolução
- Sistema dedutivo: dedução natural
  - Regras de introdução e eliminação
  - Derivação e prova
Extensões à Lógica Predicativa

5 Critérios de Avaliação

5.1 Actividades de Ensino-Aprendizagem e Metodologias Pedagógicas

Por fim a avaliar as competências adquiridas, as actividades de Ensino-Aprendizagem avaliarão tanto a compreensão dos conceitos teóricos expostos como a capacidade em por estes em prática.

Assim, a avaliação será constituída por uma componente teórica e por uma componente prática

Fraudes

A equipa docente realça que qualquer tipo de fraude em qualquer dos itens desta disciplina implica a reprovação automática do aluno faltoso, podendo ainda vir a ser este alvo de processo disciplinar.

Listamos a seguir as diferentes componentes da avaliação.

5.2 Componente Prática

Esta avaliação mede em termos práticos a aquisição dos conceitos expostos. Como tal é baseada na avaliação da resolução de trabalho prático. Esta avaliação tomará a forma da resolução de desafios de programação dos conceitos introduzidos nas aulas
Os exercícios avaliados são em número de 4 e resolvidos de uma forma sequencial e individual. As datas exactas de entrega encontram-se na secção 6. A entrega é feita de forma electrónica no site mooshak da UC.
A Nota da Componente Prática (NCP, 20 valores) é resultante da avaliação atribuída ao trabalho prático.

5.3 Componente Teórica

A avaliação da componente teórica consiste numa frequência (ver secção 6 para conhecer a data prevista da frequência).

Da avaliação desta prova resulta a Nota da Componente Teórica (NCT, 20 valores).

5.4 Concessão de Frequência e Avaliação Contínua

O parâmetro de "Frequência" atribuído no final desta unidade curricular traduz, no contexto da avaliação contínua, a "avaliação mínima" do estudante ao longo do processo de ensino-aprendizagem no final das actividades de contacto.

Considera-se que o estudante demonstrou ter adquirido o grau de conhecimentos mínimos (durante o processo de aprendizagem ao longo das actividades lectivas) quando este demonstrou as mínimas competências nas componentes avaliadas.

É assim concedido Frequência ao aluno que obteve os mínimos (6) em vigor na Universidade da Beira Interior em ambas as componentes (NCP e NCT). Ou seja:

Notas Mínimas

De forma detalhada, é instaurado um regime de notas mínimas como critério de validação da nota final. Esses mínimos são:

6 valores (em 20) para a NCP
6 valores (em 20) para a NCT

Uma nota abaixo desses valores implica reprovação à disciplina (Não Admitido a Exame).

Avaliação contínua quantitativa

No caso de Frequência, a avaliação quantitativa, designada aqui de Nota da Avaliação Contínua (NAC), é determinada da seguinte forma:

NAC =

componente prática (NCP) × 0.8 + componente teórica (NCT) × 1.2

Se a avaliação quantitativa resultar numa nota maior ou igual a 10 então o aluno é dispensado de exame (Frequência com dispensa de exame).

5.5 Avaliação por Exame

A nota da prova escrita do exame substituirá a nota da componente teórica da Avaliação Contínua. Em consequência, a Nota da Avaliação por Exame segue o mesmo cálculo que a Nota da Avaliação Contínua.

6 Datas Importantes

Frequência: Segunda feira 9 de Janeiro de 2017 das 14h00 às 16h00.
Componente prática:
- Entrega do enunciado do primeiro exercício: Primeira semana de Outubro.
- Entrega do primeiro exercício: Semana do 17 de Outubro.
- Entrega do enunciado do segundo exercício: Semana do 17 de Outubro.
- Entrega do segundo exercício: Semana do 19 de Dezembro (novo prazo).
- Entrega do enunciado do terceiro exercício: Semana do 14 de Novembro.
- Entrega do terceiro exercício: Semana do 19 de Dezembro (novo prazo).
- Entrega do enunciado do quarto exercício:Semana do 12 de Dezembro.
- Entrega do quarto exercício: Semana do 9 de Janeiro.
Exame Época 1 : (conferir no site dos académicos).
Exame Época 2 : (conferir no site dos académicos).
Exame Época Especial : (conferir no site dos académicos).

7 Horário

Tipo de aula	Horário	Sala	Docente
Teórica	Segunda-Feira das 14h00 às 16h00	6.26	S. Melo de Sousa
Práticas Laboratoriais 1	Quarta-Feira das 9h00 às 11h00	6.13	S. Melo de Sousa
Práticas Laboratoriais 3	Quinta-Feira das 9h00 às 11h00	6.13	S. Magalhães
Práticas Laboratoriais 4	Quinta-Feira das 11h00 às 13h00	6.14	S. Magalhães
Práticas Laboratoriais 2	Quinta-Feira das 16h00 às 18h00	6.19	S. Magalhães

8 Atendimento

Por marcação (por email) ou

Horário	Docente
Quarta Feita das 16h00 às 18h00	S. Melo de Sousa

9 Material Pedagógico e Funcionamento da Disciplina

Os Apontamentos serão atempadamente disponibilizados nas aulas e por meios electrónicos. É esperado e assumido que o aluno tenha lido os acetatos referentes ao capítulo em curso antes das aulas teóricas.

Teóricas

Lógica Computacional

(Regra geral: cada conjunto de acetatos (aula) seguinte corresponde a uma hora teórica)

Práticas

Ficha prática OCaml

Ficha Técnicas Matemáticas de Demonstração (da UC Teoria de Computação)

(Regra geral: cada ficha prática seguinte corresponde a uma hora de aulas práticas)

Trabalhos Práticos

Para alguns dos exercícios por resolver, vai precisar de umas funções OCaml que façam o parsing das entradas

Este ficheiro fornece tais utilitários para os problemas B e C: (link aqui)

Este ficheiro fornece utilitário para o problema D: (link aqui)

Complementos pedagógicos

Resolução da frequência 2016-2017 (aqui)

10 Resultados da avaliação

Avaliação contºinua disponível (aqui)

11 Bibliografia Principal

As referencias principais são:

Michael Huth and Mark Ryan. Logic in Computer Science: Modelling and reasoning about systems. Cambridge University Press, 2004.
J.B. Almeida, M.J. Frade, J.S. Pinto, and S. Melo de Sousa. Rigorous Software Development, An Introduction to Program Verification. Volume 103 of UTiCS. Springer-Verlag, first edition, 307 p. 52 illus. edition, 2011.
(Capítulos 3,4 e 5)

Utilizaremos ocasionalmente as referências:

D. van Dalen. Logic and Structure. 5th Edition, Springer Verlag, Berlin, Germany, 2013
René Cori e Daniel Lascar. Mathematical Logic: a course with exercices. Part I: propositional calculus, boolean algebras, predicate calculus. Oxford Press, 2007.
Mordechai Ben-Ari. Mathematical Logic for Computer Science. SV, 2nd edition, 2001.
Shawn Hedman. A First Course in Logic: An Introduction to Model Theory, Proof Theory, Computability, and Complexity. Oxford Texts in Logic, 2004.
Jon Barwise and John Etchemendy. Language Proof and Logic (4th edition) CSLI Publications, 2003.

Enviar comentários e dúvidas para (retire os UUU) : desousaUUU@UUUdi.ubi.pt

This document was translated from L^AT_EX by H^EV^EA.

n^o	Trab	Prova ex.	Nota final
34510	11,7	8,1	9,54
38535	9,7	5,5	7,18

Lógica Computacional (cod.11555)

Departamento de Informática Universidade da Beira Interior