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

Atendendo a um pedido, teremos uma V2 antecipada, no dia 13 de agosto (terça).

• A Primeira V2 será na terça, dia 13 de agosto, aberta a toda a turma. Quem quiser fazer a V2 no dia 13, deve preencher o formulário: [link].
• Mas quem fizer a V2 no dia 13 de agosto não poderá fazer novamente no dia 15 de agosto.
• Cada pessoa na turma terá apenas uma nota da V2.
• Teremos uma aula de discussão de questões no dia 13 de julho, para quem optar por fazer a V2 no dia 15 de agosto. Quem optar por fazer a V2 no dia 13 de agosto, poderá discutir questões e tirar dúvidas pelo email da turma (logcc_2024-1@id.uff.br).
• A vista de prova da V2 (primeira e segunda) será na terça, dia 20 de julho.

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.

LPO - Lógica de Primeira Ordem (ou Lógica dos Predicados, ou LQ - Lógica dos Quantificadores):

• Seções 4.1 e 4.2, 5.1 e 5.2 do livro [SFM2017]
• Capítulo 9 do livro [JNSouza2002]
• Capítulo 6 do livro [JNSouza2020]
• Lógica Monádica: sintaxe
• Lógica de Primeira Ordem: sintaxe
• Uma regra e 14 axiomas para LS (opcional)
• Lógica Sentencial: árvores de refutação
• Lógica Monádica: árvores de refutação
• Lógica de Primeira Ordem: semântica
• Seções 2.4 e 5.6 do livro [SFM2017] (tableaux analíticos = árvores de refutação)
• Demonstrações em LQ

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.

25 de abril

1. Refaça as questões da V1: [pdf].
2. Envie suas respostas, comentários, e dúvidas sobre as questões da V1 para o email da turma (logcc_2024-1@id.uff.br), para montarmos um gabarito colaborativo.

09 de julho

1. OBMEP 2022: Admita que seja "válidas" [verdadeiras] ambas as seguintes sentenças:
   
   • Pinóquio sempre mente.
   • Pinóquio diz: "Todos os meus chapéus são verdes".
   Podemos concluir dessas duas sentenças que: (A) Pinóquio tem pelo menos um chapéu. (B) Pinóquio tem apenas um chapéu verde. (C) Pinóquio não tem chapéus. (D) Pinóquio tem pelo menos um chapéu verde. (E) Pinóquio não tem chapéus verdes.
2. Divirta-se: [Youtube].
3. Lista - Quantificadores em domínios finitos: [pdf].

11 de julho

1. Leia os textos Lógica Sentencial: árvores de refutação, Lógica Monádica: árvores de refutação, e as seções 2.4 e 5.6 do livro [SFM2017] (tableaux analíticos = árvores de refutação).
2. Resolva os exercícios propostos nesses textos.

16 de julho

1. Leia o texto Lógica de Primeira Ordem: semântica.
2. Determine, intuitivamente, a validade de cada argumento a seguir. Em seguida, simbolize as premissas e a conclusão de cada argumento na linguagem de LQ (usando símbolos de função e igualdade, se necessário) e verifique a validade do argumento simbolizado (usando o método das árvores de refutação, por exemplo). Para cada argumento inválido, apresente uma interpretação segundo a qual as premissas do argumento são verdadeiras e a conclusão é falsa.
   (a) Todo gato é mamífero. Todo mamífero é carnívoro. LOGO, todo gato é carnívoro.
   (b) Todo gato é mamífero. Existem gatos herbívoros. LOGO, existem mamíferos herbívoros.
   (c) Existem gatos herbívoros. Existem mamíferos herbívoros. LOGO, existem gatos mamíferos.
   (d) Todo gato mia. Frajola é um gato. LOGO, Frajola mia.
   (e) Toda ninfa é um espírito da natureza. Quione é uma ninfa. LOGO, existem espíritos da natureza. (Considere que, nos contextos onde 'Quione é uma ninfa' é uma sentença verdadeira, Quione existe.)
   (f) Toda professora é amiga de qualquer estudante. Renata é professora e Maria Cecília é estudante. LOGO, Maria Cecília é amiga de Renata.
   (g) A relação de amizade é simétrica. Renata é amiga de Júlia. LOGO, Júlia é amiga de Renata. (Dizer que a relação amizade é simétrica é afirmar que, quando uma pessoa A é amiga de uma pessoa B, então a pessoa B também é amiga da pessoa A.)
   (h) Todas as sobrinhas de João são filhas de José. LOGO, nenhum irmão ou irmã de João tem filhas, com exceção possivelmente de José.
   (i) A soma de ímpares é par. 3 e 5 são ímpares. LOGO, 8 é par.

18 de julho

1. Leia o texto Demonstrações em LQ.
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 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).
• Exercício de 16 de abril: item 4.
• Primeira V1: Questão 1, item (a).

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.