Capı́tulo 2
A Sintaxe da Lógica Proposicional
(Prof. Flávio L. C. de Moura)
Linguagens naturais vs. Linguagens formais
Linguagens naturais, como o Português ou o Inglês, são suscetı́veis a ambiguidades:
A mãe observou o filho em seu quarto.
Esta é uma das razões pelas quais o estudo da lógica matemática e computacional utiliza uma
linguagem formal.
Mas o que é Lógica?
• Mendelson: “Lógica é a análise de métodos de raciocı́nio.”
• Mortari: “Lógica é a ciência que estuda princı́pios e métodos de inferência, tendo o objetivo
principal de determinar em que condições certas coisas se seguem (são consequência), ou não,
de outras.”
• Como veremos neste curso, “a Lógica está interessada principalmente na forma e não no
conteúdo dos argumentos.” (Souza)
Neste curso estudaremos basicamente duas lógicas:
1. Lógica proposicional;
2. Lógica de predicados (ou lógica de primeira ordem).
A Sintaxe da Lógica Proposicional
A lógica proposicional é baseada na noção de proposição, que é qualquer expressão que possa ser
qualificada como verdadeira ou falsa.
Exemplos de proposições:
1. O número 2 é par.
2. O conjunto dos números reais é enumerável.
7
3. Se a oferta de morangos aumentar então o seu preço vai diminuir.
Não são proposições:
1. Qual é o seu nome?
2. Feche a porta!
Algumas proposições são minimais (ou atômicas) no sentido que não existe uma subexpressão
dela que ainda seja uma proposição. Por exemplo,
• 2 2 {1, 3, 5}
• O número 2 é par.
Proposições mais complexas são podem ser construı́das a partir de proposições atômicas por
meio de conectivos:
p
• 2 é um número par e 2 é um número racional.
• Se 2+2=5 então hoje é dia 10.
p
• 2 é um número par ou 2 é um número racional.
Para o estudo da Lógica Proposicional (e também da Lógica de Primeira Ordem) consideraremos
dois aspectos: o sintático e o semântico. A sintaxe de uma linguagem nos permite conhecer as
expressões bem formadas, enquanto que a semântica se refere ao seu significado. Por exemplo, a
palavra “lójica” não é uma expressão bem formada do Português..
A representação simbólica da lógica é feita utilizando-se um alfabeto.
Definição 3 (Alfabeto da Lógica Proposicional). O alfabeto da lógica proposicional é definido por:
(a) Sı́mbolos de pontuação: “(” e “)”;
(c) Um conjunto enumerável de sı́mbolos proposicionais: p0 , p1 , p2 , . . .
(d) Conectivos lógicos:
– de aridade zero: ? (constante que denota a proposição falsa);
– unário: ¬ (negação);
– binários: ^ (conjunção), _ (disjunção), ! (implicação).
Os sı́mbolos proposicionais e ? constituem proposições indivisı́veis que chamaremos de átomos ou
proposições atômicas.
As fórmulas da lógica proposicional são cadeias de sı́mbolos (strings) do alfabeto definidas
indutivamente. Conjuntos indutivos são particularmente importantes tanto em Matemática quanto
em Computação. O primeiro conjunto indutivo que tivemos contato foi o conjunto dos números
naturais:
nat ::= 0:nat | S:nat ! nat
8
A definição acima nos diz que um número natural possui dois construtores: 0, e a função sucessor
S. Por exemplo, S 0, S(S 0) e S(S(S 0)) são números naturais construı́dos a partir da gramática
acima. Alternativamente, o conjunto dos números naturais pode ser definido da seguinte forma:
Definição 4. O conjunto N dos números naturais é o menor conjunto tal que:
(i) 0 2 N
(ii) se n 2 N então S(n) 2 N.
De maneira análoga podemos definir o conjunto PROP das fórmulas das lógica proposicional:
Definição 5. O conjunto PROP das fórmulas bem formadas (fbf ) da lógica proposicional é o menor
conjunto tal que:
1. p 2 PROP (sı́mbolos proposicionais) e ? 2 PROP;
2. Se a, b 2 PROP então (a ^ b), (a _ b), (¬a), (a ! b) 2 PROP.
Exemplos:
(a) (¬((p ^ q) ! r))
(b) ((p ! q) ^ (¬((r _ p) ! q)))
(c) ((p ! q) ! (r ! (s _ t)))
Teorema 2 (Princı́pio de indução). Seja A uma propriedade. Temos que A(') (i.e. a fórmula '
satisfaz a propriedade A) para todo ' 2 PROP se, e somente se
1. A(?) é verdadeira
2. A(p) é verdadeira para toda variável proposicional p
3. Se A(') e A( ) então A('⇤ ), onde ⇤ 2 {!, ^, _}
4. Se A(') então A(¬')
Prova.
Let X = {' 2 PROP | A(')}. Temos que X satisfaz os itens 1 e 2 da Definição 5 e
portanto PROP ✓ X. Logo A(') é verdadeiro para toda fórmula '.
⇤
Propriedades sobre conjuntos indutivos são demonstradas utilizando-se indução, como explicado
no capı́tulo anterior. As fórmulas da lógica proposicional também são definidas indutivamente.
Definição 6. Definimos indutivamente as fórmulas bem formadas (fbf) da seguinte maneira:
1. Um sı́mbolo proposicional e ? são fbf (chamadas de fórmulas atômicas);
2. Se a e b são fbf então (a ^ b), (a _ b), (¬a) e (a ! b) também são fbf.
3. Cláusula maximal: a linguagem da lógica proposicional é o menor conjunto que satisfaz as
regras 1 ou 2 acima.
Parênteses mais externos podem ser omitidos já que estes não geram ambiguidade:
9
(a) ¬((p ^ q) ! r)
(b) (p ! q) ^ (¬((r _ p) ! q))
(c) (p ! q) ! (r ! (s _ t))
Definição 7 (Subfórmula). Dada uma fbf a, definimos recursivamente as subfórmulas de a da
seguinte forma:
(a) a é uma subfórmula de a;
(b) Se a = ¬b então b é uma subfórmula de a;
(c) Se a = b ^ c, b _ c, b ! c então b e c são subfórmulas de a.
Exemplo 1. Denotando por Subf (a), o conjunto das subfórmulas de a, temos que
Subf ((p _ ¬q) ! (r ^ ¬q)) = {p, q, r, ¬q, p _ ¬q, r ^ ¬q,
(p _ ¬q) ! (r ^ ¬q)}
Pela definição anterior, uma fórmula é sempre subfórmula de si mesma. Dizemos que uma
subfórmula b de a é própria se b 2 Subf (a) e b 6= a.
Definição 8. O tamanho ou complexidade de uma fórmula a, representado por |a|, é um número
inteiro positivo definido por:
1. |p| = 1, para toda fórmula atômica p;
2. |¬a| = 1 + |a|;
3. |a b| = 1 + |a| + |b|, para
2 {^, _, !}.
Exemplos 1. Se p, q e r são variáveis proposicionais então:
• |¬p| = 2
• |p ! q ^ r| = 5
Exercı́cios
1. Determine quais das fórmulas a seguir são bem formadas:
(a) ! p
(b) p ^ q ! p
(c) pq ^ ¬b
(d) p¬
(e) p ! p ! q ! q
(f ) (p ^ q) ! (p _ (q ^ r))
2. Determine todas as subfórmulas das fórmulas dadas a seguir.
(a) ¬p ^ q ! r
10
(b) (p ! q) ^ ¬(r _ p ! q)
(c) (p ! q) ! (r ! s _ t)
(d) p _ (¬q ! p ^ r)
(e) p _ q ! ¬p ^ r
(f ) p _ p ! ¬r
3. Calcule a complexidade das fórmulas dadas no exercı́cio anterior.
4. Definir por indução sobre a estrutura das fórmulas a função at( ) que retorna o conjunto de
todos os átomos que ocorrem na fórmula . Por exemplo, at(p ^ (p ! q _ p)) = {p, q}.
5. Defina por indução sobre a estrutura das fórmulas a função imp( ) que retorna o número de
implicações que ocorrem em . Exemplo: imp(p ! (p ! ¬q)) = 2.
6. Prove que uma fórmula da lógica proposicional com n conectivos possui, no máximo, 2n + 1
subfórmulas.
11