Universidade Federal do Ceará Departamento de Computação CB0515 Prof. João Fernando a Exercícios X Aluno(a): Josberto Francisco Barbosa Vieira Matrícula: 344106 Hacking with: for i in *.pdf ; do pdftotext "${i}" ; done

1. Mostre que uma proposição com n conectivos possui no máximo 2n + 1 subfórmulas.

2. Mostre que toda fórmula proposicional σ não-atômica possui uma única maneira de ser decomposta, isto é, há duas proposições φ e ψ tal que σ = (φ2ψ) (em que e ∈ {∧, ∨, →}), ou (exclusivo) há uma proposição φ tal que σ = (¬φ).

3. Seja ⊧ φ → ψ tal que φ e ψ possuem pelo menos um símbolo proposicional em comum. Prove que há uma fórmula σ construída somente a partir dos símbolos proposicionais ocorrendo em ambos φ e ψ tal que φ → σ e σ → ψ. Observação: Em respeito à Convenção de Genebra e ao Protocolo de Kyoto, sou instado a parar com essas provas por indução... Por enquanto...

4. Para ver se você está ligado(a)... O que há de errado com o seguinte argumento? “Se eu correr os 100 metros abaixo de 10 segundos, serei admitido na delegação brasileira que vai às Olimpíadas de Londres. Como eu não estou correndo os 100 a metros abaixo de 10 segundos, eu não serei admitido na delegação brasileira que vai às Olimpíadas de Londres.”

5. Para treinar o uso de tabelas-verdade e representação do conhecimento através de fórmulas da Lógica Proposicional. Observe as seguintes declarações: Toda pessoa com um ouvido musical é capaz de cantar apropriadamente. Ninguém é um verdadeiro músico se não consegue extasiar sua audiência. Ninguém que não tem um ouvido musical pode extasiar sua audiência. Ninguém, exceto um verdadeiro músico, pode compor uma sinfonia.

Com base nessas informações, que propiedades tem uma pessoa que compôs uma sinfonia? Formalize essas declarações usando fórmulas da Lógica Proposicional e use tabelas verdade para responder essa questão.