Fundamentos Matemáticos para Computação - Lógica

Lógica Proposicional e Lógica de Predicados

Lógica proposicional: trabalha com sentenças simples (verdadeiro/falso). Conectivos (⊤, ∧, ∨, →, ¬) formam proposições compostas. Ex.: Se João estuda (A) e tira boas notas (B), então A ∧ B é verdadeiro se ambas são verdadeiras.

Lógica de predicados envolve quantificadores sobre domínios (∀, ∃). Ex.: Todo carro esportivo tem motor potente: ∀x (A(x) → C(x)). Existem carros de luxo com motor potente: ∃x (D(x) ∧ C(x)).

Exemplos práticos

Proposição: “Ou as pessoas participam da votação ou a situação da cidade não vai melhorar. As pessoas não participam da votação ou as melhorias no cotidiano da cidade serão implementadas. Logo, se a situação na cidade melhorar, melhorias no cotidiano da cidade serão implementadas.”

Forma lógica: (A∨B’) ∧ (A’∨C) → (B→C), com hipóteses (A∨B’), (A’∨C) e tese (B→C).

Sobre predicados: parâmetros como x em A(x), C(x), etc., exibem regras de especialização ao remover e recombinar quantificadores.

Técnicas de Demonstração

Direta: assume P ⊢ Q para obter P → Q.

Contraposição: de P → Q deduz Q’ → P’ (equivalência P → Q ↔ Q’ → P’). Útil quando provar partir da negação de Q facilita a demonstração.

Absurdo (prova por contradição): supor P ∧ ¬Q e chegar a uma contradição.

Indução matemática: - Primeiro Princípio: provar P(1) e P(k) → P(k+1); - Segundo Princípio: provar P(r) para 1 ≤ r ≤ k, e então P(k+1).

Exemplos resolvidos

Provar que o número n é par se e somente se 3n+2 é par. Ida (A→B): n par → 3n+2 par. Volta (B→A): usa contraposição ou prova direta; contrapartes mostram a equivalência entre as duas formas.

Inindária de laço e Hoare

Invariante de laço: propriedade que permanece verdadeira em todas as iterações.

Tripla de Hoare: {Q} P {R}, com axioma da atribuição e regras para condicional e laço.

Exemplo: dividir x por y com resto r. A evidência usa a invariante x = q·y + r.

Relações de Recorrência

Métodos: - Expandir, supor e verificar (expand-suppose-verify). - Soluções lineares de primeira ordem: S(n) = a S(n-1) + b. - Recorrências lineares de segunda ordem: S(n) = p S(n-1) + q S(n-2). - Dividir para conquistar: S(n) = c S(n/2) + g(n).

Exemplos resolvidos

T(n) = n T(n-1) com T(1)=1 → T(n) = n!

T(n) = 4 T(n/2) + 3n^2 → aplicação do Teorema Mestre: a=4, b=2, c=2 → Θ(n^2 log n)

Teorema Mestre

Dado S(n) = a S(n/b) + n^c, compare a com b^c: - se a < b^c → Θ(n^c) - se a = b^c → Θ(n^c log n) - se a > b^c → Θ(n^{log_b a})

Grafos, Relação Binária e Matrizes Booleanas

Matriz de adjacência A para um grafo direcionado com pares p = {(1,2), (2,3), (3,1), (4,3), (4,4)}.

Matriz de acessibilidade R obtida por R = A ∨ A^2 ∨ ... ∨ A^n; para o grafo acima, R = 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1

Resumo detalhado por tópicos

1. Lógica Proposicional e Lógica de Predicados
   • Sentenças, proposições, conectivos (∧, ∨, →, ¬) e equivalências básicas.
   • Predicados com quantificadores universais e existenciais.
   • Exemplos práticos: A → B, ∀x A(x) → C(x), ∃x D(x) ∧ C(x).
2. Técnicas de Demonstração
   • Demonstração Direta: partir da hipótese para chegar à conclusão.
   • Contraposição: usar ¬Q → ¬P para P → Q.
   • Absurdo: prova por contradição usando P ∧ ¬Q → 0.
   • Indução: primeiro e segundo princípio; exemplos com soma de selos e propriedades.
   • Invariante de laço: Q permanece verdadeira antes e depois de cada iteração.
   • Tripla de Hoare: {Q} P {R}; axioma de atribuição; regras para condicional e laço.
3. Relações de Recorrência
   • Expanda-suponha-verifique; resoluções para recursões lineares de primeira e segunda ordem.
   • Dividir para conquistar: S(n) = c S(n/2) + g(n) com soluções usando Mestre.
   • Exemplos práticos resolvidos com T(n) = n! e T(n) = n^2(1+3 log n).
4. Grafos, Relação Binária e Matrizes Booleanas
   • Matriz de adjacência, relação binária e matriz de acessibilidade.
   • Cálculo da relação de acessibilidade com multiplicação booleana.
   • Exemplo do grafo com resultado final R.

Mapa mental (Mermaid)