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

Turma A1 - Segundas e quartas, 14-16h, sala IC-204

Turma B1 - Terças e quintas, 14-16h, sala IC-217

Grupo no Telegram: [convite].

Calendário

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]. Um exemplo de prova com diagramas de Venn: [pdf]. (Quase) tudo 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 (errata - já corrigido na nova versão: no Exercício 5, item (ii), trocar 2 por 4)
• 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.

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

• 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
• 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)
• Uma regra e 14 axiomas para LS (opcional)

Exercícios

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

3, 4, 5 e 6 de abril

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

10, 11, 12 e 13 de abril

1. Capítulo 5 do livro [JNSouza2002], página 76, itens 5 a 9.
2. Lista 1.
3. Leia os textos Lógica Sentencial: sintaxe, Lógica dos Conectivos: simbolização (opcional), Lógica Sentencial: semântica, Lógica Sentencial: consequência (e resolva os exercícios propostos nesses textos).

17 de abril

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

18 de abril

1. Mostre que, para todas as fórmulas A e B, temos que A e B são equivalentes se, e somente se, a fórmula (A<->B) é uma tautologia.
2. Mostre que, para toda fórmula A, temos que A é uma tautologia se, e somente se, (~A) não é satisfazível.
3. Dados um conjunto finito de fórmulas {B1,B2,...,Bn} e uma fórmula A, encontre uma fórmula X (que deve ser construída a partir de B1, B2, ... , Bn, e A) tal que A é consequência de {B1,B2,...,Bn} se, e somente se X é uma tautologia.
4. Dados um conjunto finito de fórmulas {A1,A2,...,An}, encontre uma fórmula X (que deve ser construída a partir de A1, A2, ... , An) tal que {A1,A2,...,An} é contraditório se, e somente se X é uma tautologia.

19 de abril - Dia Nacional dos Povos Indígenas

Considere os seguintes resultados:

-Teorema do Rodrigo Chimelli- Para toda fórmula A, se o número de ocorrências do conectivo não em A é par, então o comprimento de A é ímpar.

-Lema 1- Para toda fórmula A, comp[A] = compsn[A] + nn[A] (onde nn[A] é o número de ocorrências do conectivo não em A e compsn[A] é o número de ocorrências de símbolos diferentes do símbolo do não em A).

-Lema 2- Para toda fórmula A, compsn[A] é ímpar.

1. Defina compsn[A] por recursão.
2. Defina nn[A] por recursão.
3. Defina comp[A] por recursão (se é que você não definiu esse conceito ainda).
4. Prove o Lema 1 por indução.
5. Prove o Lema 2 por indução.
6. Prove o Teorema do Rodrigo Chimelli, usando o Lema 1 e o Lema 2.

20 de abril

1. Leia a Seção 1 - Passos Lógicos, do texto Lógica dos Conectivos: demonstrações diretas.
2. Resolva os exercícios 1, 2 e 3 (páginas 7 e 8) da Seção 1 - Passos Lógicos, do texto Lógica dos Conectivos: demonstrações diretas.

24 de abril

1. Compartilhe com a turma a sua solução dos exercícios propostos em sala, como fez a Laura, para contribuir com o nosso gabarito colaborativo.
2. Estamos especialmente interessados em provas (demonstrações) diferentes da validade de um mesmo argumento. Compartilhe sua resolução dos exercícios com a turma.

2, 3, e 5 de maio

1. Resolva o Exercício 4 (página 18) da Seção 3 - Redação das demonstrações diretas, do texto Lógica dos Conectivos: demonstrações diretas.
2. Resolva o Exercício 1 (página 3) da Seção 1 - Demonstrações diretas, do texto Lógica dos Conectivos: demonstrações indiretas.
3. Resolva o Exercício 2 (página 10) da Seção 2 - Olhe para a conclusão!, do texto Lógica dos Conectivos: demonstrações indiretas.
4. Resolva o Exercício 3 (página 15) da Seção 3 - Primeiras estratégias de demonstração, do texto Lógica dos Conectivos: demonstrações indiretas.
5. Resolva o Exercício 4 (página 26) da Seção 4 - Principais estratégias de demonstração, do texto Lógica dos Conectivos: demonstrações indiretas.

17 e 18 de maio

Vamos usar os exemplos a seguir para discutir a questão do poder expressivo da linguagem da Lógica dos Conectivos. Determine, intuitivamente, a validade de cada argumento a seguir. Em seguida, simbolize as premissas e a conclusão de cada argumento na linguagem de LC (quando possível) e verifique a validade do argumento simbolizado (usando o método das tabelas, por exemplo).

1. Todo gato é mamífero. Todo mamífero é carnívoro. LOGO, todo gato é carnívoro.
2. Todo gato é mamífero. Existem gatos herbívoros. LOGO, existem mamíferos herbívoros.
3. Existem gatos herbívoros. Existem mamíferos herbívoros. LOGO, existem gatos mamíferos.
4. Todo gato mia. Frajola é um gato. LOGO, Frajola mia.
5. 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.)
6. Toda professora é amiga de qualquer estudante. Renata é professora e Maria Cecília é estudante. LOGO, Maria Cecília é amiga de Renata.
7. 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.)
8. 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é.
9. A soma de ímpares é par. 3 e 5 são ímpares. LOGO, 8 é par.

22 e 23 de maio

1. Lista - Sintaxe de LM.

24 e 25 de maio

1. Leia o texto Lógica Sentencial: árvores de refutação, (e resolva os exercícios propostos nesse texto).
2. Lista - Árvores de Refutação em LM.

29 de maio

Com o objetivo de conhecer o perfil de estudantes de Lógica na graduação e no mestrado, que estão em seus primeiros anos de contato com a área, João Mendes - UFRN e o prof. João Marcos - UFRN, apoiados pela Sociedade Brasileira de Lógica (SBL), elaboraram um censo:

https://cutt.ly/censoEstudantesLogica

O formulário ficará aberto para respostas até o dia 11/06/23, domingo, e o tempo estimado para resposta é de 7 minutos. A SBL agradece pela participação.

05 a 08 de junho

1. Leia o texto Lógica Monádica: árvores de refutação (e resolva os exercícios propostos nesse texto).

12 a 15 de junho

1. Leia o texto Lógica de Primeira Ordem: método de demonstração, (e resolva os exercícios propostos nesse texto).
2. Lista - Demonstrações em LM.

19 de junho

1. Um problema para o André, (opcional).
2. Lista - demonstrações em LPO, (opcional).

20 de junho

• Válido ou inválido?

Resultados

Turma A1.

Turma B1.

Observações

Faremos duas verificações de aprendizagem: (V1) e (V2). A média (M) será a média aritmética: (M) = (V1)+(V2) / 2.

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.

Não é permitido durante a prova sair e retornar à sala (salvo em situação de urgência).

Não é permitido usar aparelhos eletrônicos (calculadora, celular, relógio, etc) durante a prova.

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

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

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.

Qualquer dúvida, me escreva: renatafreitas @ id.uff.br.