PROPOSIÇÕES, REPRESENTAÇÕES SIMBÓLICAS E TAUTOLOGIAS

1) Proposições e Sentenças

Uma proposição (ou declaração) é uma sentença que só pode ser verdadeira ou falsa. Sentenças que não indicam um valor de verdade claro, como “Ela é muito talentosa” sem identificar quem é “ela”, não são proposições.

Exemplos do texto: - “Dez é menor do que sete.” (proposição, falsa) - “Cheyenne é a capital de Wyoming.” (proposição, verdadeira) - “Ela é muito talentosa.” (não é proposição, falta referência) - “Existem outras formas de vida no universo.” (proposição, pode ser verdadeira ou falsa)

Observação: o valor lógico de uma proposição pode ser utilizado para combinar proposições com conectivos lógicos para formar sentenças mais complexas.

2) Conectivos e Valores Lógicos

Conectivos lógicos são operadores que combinam proposições para formar novas sentenças. Principais conectivos:

• Conjunção (A ∧ B): “e”
• Disjunção (A ∨ B): “ou”
• Condicional (A → B): “se A, então B”
• Bicondicional (A ↔ B): “A se e somente se B”
• Negação (A′): “não A”

Exemplos de valores lógicos: - A ∧ B é verdadeiro apenas se A e B são verdadeiras. - A ∨ B é verdadeiro se pelo menos um entre A ou B é verdadeiro. - A → B é verdadeiro em todos os casos, exceto quando A é verdadeiro e B é falso (componente intuitivo da “condição”). - A ↔ B é verdadeira quando A e B têm o mesmo valor lógico.

Observação: a negação de uma proposição deve ser aplicada com cuidado, especialmente em proposições compostas (ver Tabela 1.6 do texto).

3) Fórmulas Bem Formadas (fbf) e Precedência

Pode-se encadear proposições com conectivos e parênteses para formar fbfs. A ordem de precedência facilita a leitura: 1) parênteses internos, 2) negação, 3) conjunção e disjunção, 4) condicional, 5) bicondicional.

Exemplos: - A ∨ B′ → (A ∨ B)′ é lida como (A ∨ B′) → (A ∨ B)′, com o conectivo principal sendo →. - (A ∨ B) ∧ C é diferente de A ∨ (B ∧ C); a precedência importa.

Observação: letras maiúsculas próximas ao fim do alfabeto (P, Q, R, S) podem representar fbfs, simplificando o foco no conectivo principal.

4) tautologias, contradições e fbfs equivalentes

Uma tautologia é uma fbf que é verdadeira em todas as atribuições de verdade. Exemplo simples: A ∨ A′. Uma contradição é falsa em todas as atribuições, por exemplo: A ∧ A′.

FBFs equivalentes: se P e Q são fbfs equivalentes, então P pode ser substituída por Q sem alterar o valor lógico global. Notação: P ⇔ Q é verdadeira quando P e Q são equivalentes.

Observação: Leis básicas de equivalência (comutatividade, associatividade, distributividade, leis de De Morgan) ajudam a transformar fbfs de forma segura e intuitiva.

5) Um Algoritmo para testar tautologia

Para verificar se P → Q é uma tautologia, podemos usar um procedimento mais eficiente do que montar toda a tabela-verdade, especialmente quando P e Q são fbfs complexas. A ideia é procurar uma atribuição que torne P → Q falsa (P verdadeiro e Q falso). Se não houver tal atribuição, P → Q é tautologia. Caso contrário, encontramos uma configuração que a torne falsa, provando que não é tautologia.

Essa ideia dá origem a um algoritmo que percorre possibilidades de valores lógicos para as letras de proposição até encontrar uma contradição ou concluir tautologia.

6) Conectivos no Mundo Real

Conectivos lógicos aparecem em buscas na internet, programação e circuitos digitais. Por exemplo, expressões com E (AND), OU (OR) e NÃO (NOT) ajudam a refinar pesquisas, a controlar fluxos de decisão em programas e a construir portas lógicas (E, OU, NÃO) que formam os circuitos dos computadores.

7) Um Exemplo de Aplicação em Algoritmos

Considere uma expressão condicional em programação: se ((FluxoDeSaída > FluxoDeEntrada) e não ((FluxoDeSaída > FluxoDeEntrada) e (Pressão < 1000))) então faça Algo; senão faça OutraCoisa. A expressão condicional pode ser simplificada usando regras de De Morgan e tautologias para reduzir o código.

8) Tabela Verdade como Ferramenta

Para testar uma fbf com n letras de proposição, a tabela verdade tem 2^n linhas. Se o conectivo principal for um condicional P → Q, pode-se aplicar um procedimento rápido para verificar tautologia, como descrito acima.