(Parte 1 de 9)

UFU – Universidade Federal de Uberlândia Faculdade de Computação

Apostila de Lógica Proposicional (Fundamentos Básicos)

Prof. Luiz Gustavo Almeida Martins

UFU - Faculdade de Computação Lógica Proposicional

Fundamentos Básicos da Lógica INTRODUÇÃO

A lógica é o estudo sobre a natureza do raciocínio e do conhecimento. Ela é usada para formalizar e justificar os elementos do raciocínio empregados nas demonstrações / provas de teoremas.

A lógica clássica se baseia em um mundo bivalente ou binário (visão restrita do mundo real), onde os conhecimentos são representados por sentenças que só podem assumir dois valores verdade (verdadeiro ou falso). Portanto, nesse contexto, uma demonstração é um meio de descobrir uma verdade pré-existente deste mundo.

1.2 Lógica Proposicional

A lógica proposicional é a forma mais simples de lógica. Nela os fatos do mundo real são representados por sentenças sem argumentos, chamadas de proposições.

Ex: MUNDO REAL PROPOSIÇÃO LÓGICA

Hoje está chovendo P A rua está molhada Q

Se está chovendo, então a rua está molhada. P → Q

Definição (proposição): uma proposição é uma sentença, de qualquer natureza, que pode ser qualificada de verdadeiro ou falso.

Ex: 1 + 1 = 2 é uma proposição verdadeira da aritmética. 0 > 1 é uma proposição falsa da aritmética.

Se não é possível definir a interpretação (verdadeiro ou falso) da sentença, esta não é uma proposição. Alguns exemplos deste tipo de sentença são apresentados abaixo:

• Frases Interrogativas (ex: Qual o seu nome?).

• Frases Imperativas (ex: Preste atenção!).

• Paradoxos Lógicos (ex: Esta frase é falsa).

Exercício de Fixação Verifique se as expressões abaixo são proposições. Justifique sua resposta. a) Boa sorte! b) Todas as mulheres possuem sua beleza.

Prof. Luiz Gustavo A. Martins Pág.:1 c) Márcio não é irmão do Mário.

UFU - Faculdade de Computação Lógica Proposicional d) Não faça isto! e) Cecília é escritora. f) Quantos japoneses moram no Brasil?

1.3 Lógica e Informática Na computação, a lógica pode ser utilizada, entre outras coisas, para:

• Conceber circuitos lógicos (o raciocínio do computador é um raciocínio lógico);

• Representar conhecimento (programação lógica);

• Validar algoritmos e corrigir programas (testes lógicos das especificações em engenharia de software).

2 Sintaxe

2.1 Linguagem e Alfabeto

O conjunto de fórmulas da lógica proposicional é denominado L∅ (lógica de ordem ∅). Cada fórmula deste conjunto é uma proposição gerada pela concatenação de símbolos pertencentes ao alfabeto da lógica proposicional, definido inicialmente.

Este alfabeto é infinito, constituído por:

• Símbolos verdade: true e false;

• Símbolos proposicionais: P, Q, R, S, P1, P2, P3, etc;

• Conectivos proposicionais: ¬ (não), ∨ (ou inclusivo), ∧ (e), → (implica ou “se, então”) e ↔ (equivalência, bi-implicação ou “se e somente se”); e

• Símbolos de pontuação: ( e ).

Vale ressaltar que, assim como na linguagem portuguesa, nem toda a concatenação é válida, ou seja, pertence à linguagem da lógica proposicional.

As fórmulas proposicionais são construídas, a partir do alfabeto proposicional, de acordo com as seguintes regras:

1. Todo símbolo verdade é uma fórmula; 2. Todo símbolo proposicional é uma fórmula; 3. Se P é uma fórmula, então a sua negação (¬P) também é uma fórmula; 4. Se P e Q são fórmulas, então:

4.1. A disjunção de P e Q (P ∨ Q) também é uma fórmula; 4.2. A conjunção de P e Q (P ∧ Q) também é uma fórmula;

Prof. Luiz Gustavo A. Martins Pág.:2 4.3. A implicação de P em Q (P → Q) também é uma fórmula;

UFU - Faculdade de Computação Lógica Proposicional

4.4. A bi-implicação de P e Q (P ↔ Q) também é uma fórmula;

Nesta definição, as fórmulas mais elementares são os símbolos verdade e proposicionais. A partir destes e utilizando as regras 3 e 4, recursivamente, é possível obter um conjunto infinito de fórmulas.

Note que o conectivo ¬ é unário (aplicado sobre uma única fórmula) e fica na ordem pré-fixa, enquanto que os demais conectivos são binários (aplicado sobre duas fórmulas) e fica na ordem infixa.

Exemplos de Fórmulas Válidas

As construções acima são fórmulas proposicionais, pois podem ser derivadas a partir da aplicação das regras de construção descritas.

Exemplos de Fórmulas Inválidas

PQR (R True →) ( False ∨∧ (↔ Q P) )

As construções acima não constituem fórmulas proposicionais, pois não é possível derivá-las a partir das regras descritas.

Exercício: Dado os símbolos proposicionais P e Q. Mostre que ( (P ∧ Q) ∨ ( (¬P) → (¬Q) ) ) é uma fórmula proposicional.

Solução: P e Q são fórmulas(aplicando a Regra 2)
(P ∧ Q) é fórmula(aplicando a Regra 4.2)

(¬P) e (¬Q) são fórmulas (aplicando a Regra 3)

( (¬P) ∧ (¬Q) ) é fórmula (aplicando a Regra 4.3) ( (P ∧ Q) ∨ ( (¬P) ∧ (¬Q) ) ) é fórmula (aplicando a Regra 4.2)

(Parte 1 de 9)

Comentários