GAN00166 - Lógica para Ciência da Computação, 2024-1

Turma B1 - terças e quintas, 14-16h
Sala 406, Bloco H (UFASA), Campus da Praia Vermelha
Email da turma: logcc_2024-1@id.uff.br (com a participação da professora)

Profa Renata de Freitas (renatafreitas@id.uff.br)
Atendimento: gabinete 45, 4o andar, ala C, bloco G, Gragoatá (com agendamento por email)

Calendário

Em função da deflagração da greve de docentes da UFF, faremos as seguintes modificações no nosso calendário:

• A V1 será antecipada para o dia 25 de abril (quinta).
• Faremos outra V1 no primeiro dia de aula após o término da greve, aberta a toda a turma.
• Para quem fizer a V1 no dia 25 de abril e também após o término da greve, vai valer apenas a maior nota obtida.
• Estarei disponível para atendimento na quarta, dia 24 de abril, de 14 às 21h, no Gragoatá (bloco G, 4o andar, ala C, gabinete 45).

Referências

• [SFM2017] Flávio Soares Corrêa da Silva, Marcelo Finger, e Ana Cristina Vieira de Melo, Lógica para Computação, 2a ed., Cengage, São Paulo, 2017.
• [JNSouza2002] João Nunes de Souza, Lógica para Ciência da Computação, Campus, Rio de Janeiro, 2002.
• [JNSouza2020] João Nunes de Souza, Lógica para Ciência da Computação e áreas afins: uma introdução concisa sobre os fundamentos da Lógica, UFU, Uberlândia, 2020 [pdf].

Leituras

Introdução:

• O que é Lógica
• Validade, forma e conteúdo de argumentos

  Para quem lê em inglês, trechos do livro da Shin, 선주신 (Sun-Joo Shin, The Logical Status of Diagrams, Cambridge University Press, 1995), sobre diagramas de Euler, diagramas de Venn e diagramas de Peirce: [Shin-Euler-Venn], [Shin-Venn-Peirce].

  .

• Euler e a princesa (resuminho histórico): páginas 16 a 19 do TCC de João Roberto Bêta Casal, Lógica na Matemática e no cotidiano: uma reflexão sobre o papel da Lógica no ensino, Licenciatura em Matemática, UFF, 2018 [RIUFF].
• Algumas regras de inferência do Sistema de Diagramas de Venn: [pdf].
• Algumas regras de inferência do Sistema de Diagramas de Venn-Peirce: [pdf].
• Um exemplo de prova com diagramas de Venn: [pdf].
• Sobre diagramas de Venn, incluindo como desenhar diagramas gerais para qualquer número de conjuntos: A Survey of Venn Diagrams (Frank Ruskey & Mark Weston, Department of Computer Science, University of Victoria, Canada).

LP - Lógica Proposicional (ou LS - Lógica Sentencial, ou LC - Lógica dos Conectivos):

• Seção 1.2 do livro [SFM2017]
• Capítulo 1 do livro [JNSouza2002] ou do livro [JNSouza2020]
• Capítulo 5 do livro [JNSouza2002]
• Lógica Sentencial: sintaxe
• Lógica dos Conectivos: simbolização
• Seções 1.3 e 1.4 do livro [SFM2017]
• Capítulos 2 e 3 do livro [JNSouza2002] ou do livro [JNSouza2020]
• Lógica Sentencial: semântica
• Lógica Sentencial: consequência
• Seções 2.1 e 2.3 do livro [SFM2017]
• Capítulo 7 do livro [JNSouza2002] ou Capítulo 5 do livro [JNSouza2020]
• Lógica dos Conectivos: demonstrações diretas
• Lógica dos Conectivos: demonstrações indiretas

P=NP:

Celina M. H. de Figueiredo, Resolver ou Verificar? Uma pergunta que vale um milhão de dólares. Ciência Hoje 48/287:42-46, 2011.

Celina M. H. de Figueiredo, A Perfect Path from Computational Biology to Quantum Computing, palestra de 14/06/2023 no canal do Youtube do PESC-COPPE-UFRJ.

Exercícios

Não esqueçam os exercícios "escondidos" nos textos 😉

19 de março

1. Leia o texto O que é Lógica.
2. Lista 0 - Diagramas (tente resolver os exercícios usando apenas diagramas de Venn, veja um exemplo de resolução aqui: pdf).

21 de março

1. Leia o texto Validade, forma e conteúdo de argumentos.
2. Volte aos exercícios da Lista 0 - Diagramas (desta vez, tente resolver os exercícios usando diagramas de Venn-Peirce).

26 de março

Releia a definição de prova no texto que apresenta algumas regras de inferência do Sistema de Diagramas de Venn-Peirce: [pdf] e o texto sobre validade de argumentos: [pdf] e responda as perguntas que a turma apresentou em sala:

1. É possível construir uma prova da conclusão de um argumento a partir das suas premissas quando o argumento não é válido?
2. Existem argumento válidos com conclusão falsa (em algum contexto)?
3. Existem argumento válidos com premissas falsas (em algum contexto)?
4. É possível mostrar que um argumento não é válido usando provas?

28 de março

Leia o texto Lógica Sentencial: sintaxe e comece a pensar nos exercícios propostos.

2 de abril

1. Capítulo 5 do livro [JNSouza2002], página 76, itens 5 a 9.
2. Comece a resolver os exercícios da Lista 1.
3. Leia os textos Lógica Sentencial: sintaxe e Lógica dos Conectivos: simbolização (opcional). Resolva os exercícios propostos nesses textos.
4. Mostre que as seguintes sequências de símbolos do alfabeto de LC não são fórmulas:
   (a) ->p(
   (b) )(
   (c) pq^r
5. Encontre, se possível, uma definição indutiva do conjunto dos números inteiros pares (positivos, negativos, e nulo) que tenha legibilidade única.
6. Prove o seguinte Lema:
   Toda fórmula da Lógica Proposicional possui pelo menos uma ocorrência de variável.

4 de abril

1. Continue a resolver os exercícios da Lista 1.
2. Uma sequência (s1,s2,s3,...) pode ser vista como uma função s cujo domínio é o conjunto ℕ dos números naturais não nulos. Por exemplo, a sequência de Fibonacci (1,1,2,3,5,...) pode ser vista como uma função F:ℕ→ℕ tal que F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, ... Considere a definição indutiva usual do conjunto dos números naturais não nulos e apresente uma definição recursiva da sequência de Fibonacci.

9 de abril

1. Refaça as questões do teste de 4 de abril: [pdf].
2. Envie suas respostas, comentários, e dúvidas sobre as questões do teste para o email da turma (logcc_2024-1@id.uff.br), para montarmos um gabarito colaborativo.
3. Estamos fazendo um gabarito colaborativo também para os exercícios das listas e dos textos. Envie foto das suas resoluções e também suas dúvidas e comentários para o email da turma (logcc_2024-1@id.uff.br).

16 de abril

1. Continue a resolver os exercícios da Lista 1.
2. Leia os textos Lógica Sentencial: semântica e Lógica Sentencial: consequência.
3. Resolva os exercícios propostos nesses textos.
4. Apresente uma definição recursiva da sequência de Fibonacci.

18 de abril

1. Leia o texto Lógica dos Conectivos: demonstrações diretas.
2. Resolva os exercícios propostos nesse texto.

Gabarito colaborativo

Resoluções corretas de alguns exercícios (nem sempre completas), enviadas por email ou apresentadas em sala:

• Lista 0: Questão 5, Questão 10.
• Lista 1: Questão 1, Questão 2 (resolução correta, mas a redação está bem informal; para elaborar uma redação mais formal, temos duas opções: organizar o seu texto para deixar explícito que se trata de uma prova por casos ou fazer uma prova por indução do enunciado: "para toda fórmula A, temos que o comprimento de A não é igual a 2"), Questão 7, Questão 12, itens (a,b,c).
• Texto Sintaxe de LS: Exercício 4 - item (i), item (ii), item (iii), item (iv).
• 16 de abril - item 4.

Observações

1. Faremos duas verificações de aprendizagem: (V1) e (V2). A média (M) será a média aritmética: (M) = (V1)+(V2) / 2.
2. A vista de prova acontecerá sempre na aula seguinte à aplicação de cada verificação de aprendizagem.
3. A tolerância máxima de atraso em dias de verificação de aprendizagem é de 30 minutos. Por causa disso, não é permitido entregar a prova e sair antes de decorridos 30 minutos de prova.
4. Não é permitido durante a prova sair e retornar à sala (salvo em situação de urgência).
5. Não é permitido usar aparelhos eletrônicos (calculadora, celular, relógio, etc) durante a prova.
6. A 2a Chamada está aberta a todes e obrigatoriamente substitui uma das notas anteriores, (V1) e (V2), mesmo que a nota da 2a Chamada seja menor que as outras. Após decorridos 30 minutos de prova, você poderá optar por não fazer a 2a Chamada (se optar por não fazer, não assinará a lista de presença).
7. Está aprovade quem tiver média maior ou igual a 6,0 e frequência igual ou superior a 75% (que corresponde a no máximo 7 faltas).
8. A VS - Verificação Suplementar seguirá as regras usuais da UFF: quem tiver frequência igual ou superior a 75% e média entre 4,0 e 5,9 pode fazer a VS, e estará aprovade se tiver nota maior ou igual a 6,0 na VS.
9. Só poderá fazer uma verificação de aprendizagem quem tiver frequência suficiente (número de faltas inferior a 25%, que corresponde a no máximo 7 faltas).
10. Qualquer dúvida, me escreva: renatafreitas @ id.uff.br.