Logica Matematica 03

Prévia do material em texto

1
Lógica Matemática
Fórmulas e Tabelas-verdade
Fábio Gondim
fabio.iesp # gmail.com (# = @)
http://fabio.iesp.googlepages.com
Fórmulas
Vimos que o alfabeto da lógica proposicional é
constituído pelos símbolos de pontuação
(parênteses), pelos símbolos de verdade (V, F ),
pelos símbolos proposicionais (P, Q, R, S, P1,
Q1, R1, S1, P2, ...) e pelos conectivos
proposicionais (~, ∧, ∨, →, ↔).
As fórmulas da linguagem da Lógica
Proposicional são construídas a partir dos
símbolos do alfabeto conforme as regras a
seguir:
2
• Todo símbolo de verdade (V, F) é uma fórmula.
• Todo símbolo proposicional (P, Q1, r, s4, ...) é
uma fórmula.
• Se P é uma fórmula então (~P), a negação de
P é uma fórmula.
• Se P e Q são fórmulas então (P ∨ Q) é uma
fórmula. Esta fórmula é a disjunção das fórmula
P e Q.
3
Fórmulas Fórmulas
• Se P e Q são fórmulas então (P ∧ Q) é uma
fórmula. Esta fórmula é a conjunção de P e Q.
• Se P e Q são fórmulas então (P → Q) é uma
fórmula. Neste caso, P é o antecedente e Q o
conseqüente da fórmula (P → Q).
• Se P e Q são fórmulas então (P ↔ Q) é uma
fórmula. Neste caso, P é o lado esquerdo e Q o
lado direito da fórmula (P ↔ Q).
4
Formação de Fórmulas
É possível, a partir das regras definidas pela sintaxe da
linguagem proporcional, construir infinitas fórmulas.
Exemplo:
Conforme a definição, P, Q e o símbolo de verdade V
são fórmulas.
A partir de P e Q, e do conectivo “∧”, por exemplo, é
possível obter a fórmula (P ∧ Q).
A partir de (P ∧ Q), do símbolo de verdade V, e do
conectivo “→”, por exemplo, é possível obter a fórmula
((P ∧ Q) → V ).
Este raciocínio segue indefinidamente e infinitas
fórmulas podem ser formadas.
5
Fórmulas mal formadas
As concatenações dos símbolos a seguir não
constituem fórmulas pois não é possível obtê-las
a partir das regras definidas. Considere VVVV =
verdadeiro e FFFF = Falso:
(P~), (P ~ S), (PS), (P ~→ Q), (P ~ ↔ Q), 
(R ∧), (Q VVVV ), (R ∧→ S), (FFFF ∧ ∨ VVVV ), (R VVVV S)
Não confundir a última expressão
(R VVVV S) com (R ∨ S) que é válida
(VVVV : verdadeiro, ∨: disjunção inclusiva).
6
2
Uso de parênteses
De acordo com a definição de fórmula, o uso
de parênteses é obrigatório ao utilizar os
conectivos binários (∧, ∨, →, ↔). Na prática,
porém, usamos abreviações que permitem
omitir os parênteses em diversa situações:
– Os parênteses mais externos podem ser
omitidos.
Ex.: escrever p ∧ q em vez de (p ∧ q).
7
Uso de parênteses
– O uso repetido dos conectivos ∧ e ∨ dispensa o
uso de parênteses.
Ex.: escrever p∧q∧r∧s em vez de ((p∧q)∧r)∧s
(note que os parênteses aninham-se à
esquerda.
– O uso repetido do conectivo → também dispensa
o uso de parênteses, só que os parênteses
aninham-se à direita.
Ex.: escrever p → q → r para representar p →
(q → r).
− Além disso, nas fórmulas em que há combinação
de conectivos, define-se uma precedência entre
eles conforme discutido a seguir.
8
Prioridade dos conectivos
(Autores citados: ver bibliografia)
Edgard de Alencar Filho 
(pg. 38):
(1°) ~ ;
(2°) ∧ , ∨ ;
(3°) → , ↔ .
Jacob Daghlian (pg. 35):
(1°) ~ ;
(2°) ∧ , ∨ ;
(3°) → ;
(4°) ↔ .
Flávio Soares Corrêa da Silva
e outros (pg. 10):
(1°) ~ ;
(2°) ∧ ;
(3°) ∨ ;
(4°) → 
Obs.: Omite o conectivo ↔.
João Nunes de Souza (pg. 6):
(1°) ~ ;
(2°) → , ↔ ;
(3°) ∧ , ∨ .
Prioridade dos conectivos
(Autores citados: ver bibliografia)
Jair Minoro Abe e outros
(pg. 95):
(1°) ~ ;
(2°) ∧ , 
(3°) ∨ ;
(4°) → ;
(5°) ↔ .
Elliot Mendelson (Introduction 
to Mathematical Logic, pg. 20):
(1°) ~ ;
(2°) ∧ , 
(3°) ∨ ;
(4°) → ;
(5°) ↔ .
Elliot Mendelson, no livro Introduction to Mathematical Logic,
esclarece que a ordem é definida arbitrariamente: “Second, we
arbitrarily establish the following decreasing order of strength of
the connectives: ~, ∧, ∨,→, ↔.”.
Adotaremos esta ordem porque é a mais compatível com as
linguagens de programação vistas no decorrer do curso.
Múltiplas linhas
Para melhorar a leitura, as fórmulas podem
ser escritas utilizando várias linhas. A
fórmula (((P ∨ R) → Q) ↔ (Q ∧ S)), por
exemplo, pode ser escrita, também, da
seguinte forma:
(P ∨ R) → Q
↔
Q ∧ S
11
Interpretação de Fórmulas
João Nunes de Souza define uma interpretação I, na
Lógica Proposicional, como sendo uma função binária tal
que,
• o domínio de I é constituído pelo conjunto das fórmulas
da Lógica Proposicional,
• o contradomínio de I é o conjunto {V, F },
• o valor da interpretação I, tendo como argumentos os
símbolos de verdade é dado por I[verdadeiro] = V e
I[falso] = F e
• dado um símbolo proposicional P, então I[P] ∈∈∈∈ {V, F }.
12
3
Interpretação de Fórmulas
Exemplo (Solução durante a aula):
Seja
H = ((P → Q) → (((P ∧ Q) ↔ P) ∧ ((P ∨ Q) ↔ Q)))→ P
a) Se I[P] = FFFF o que se pode concluir a respeito de I[H]?
H = ((FFFF→ Q) → (((FFFF ∧ Q) ↔ FFFF ∧ ((FFFF ∨ Q) ↔ Q)))→ FFFF
I[H] = ?
b) Se I[P] = VVVV o que se pode concluir a respeito de I[H]?
H = ((VVVV→ Q) → (((VVVV ∧ Q) ↔ VVVV ∧ ((VVVV ∨ Q) ↔ Q)))→ VVVV
I[H] = ? 13
Interpretação de Fórmulas
Exemplo (Solução durante a aula):
Seja
H = ((P → Q) → (((P ∧ Q) ↔ P) ∧ ((P ∨ Q) ↔ Q)))→ P
a) Se I[P] = FFFF o que se pode concluir a respeito de I[H]?
H = ((FFFF→ Q) → (((FFFF ∧ Q) ↔ FFFF ) ∧ ((FFFF ∨ Q) ↔ Q)))→ FFFF
I[H] = ?
b) Se I[P] = VVVV o que se pode concluir a respeito de I[H]?
H = ((VVVV→ Q) → (((VVVV ∧ Q) ↔ VVVV ) ∧ ((VVVV ∨ Q) ↔ Q)))→ VVVV
I[H] = ? 14
Interpretação de Fórmulas
Exemplo (Solução durante a aula):
Seja
H = ((P → Q) → (((P ∧ Q) ↔ P) ∧ ((P ∨ Q) ↔ Q)))→ P
a) Se I[P] = FFFF o que se pode concluir a respeito de I[H]?
H = ((FFFF→ Q) → (((FFFF ∧ Q) ↔ FFFF ) ∧ ((FFFF ∨ Q) ↔ Q)))→ FFFF
15
Interpretação de Fórmulas
Exemplo (Solução durante a aula):
Seja
H = ((P → Q) → (((P ∧ Q) ↔ P) ∧ ((P ∨ Q) ↔ Q)))→ P
b) Se I[P] = VVVV o que se pode concluir a respeito de I[H]?
H = ((VVVV→ Q) → (((VVVV ∧ Q) ↔ VVVV ) ∧ ((VVVV ∨ Q) ↔ Q)))→ VVVV
16
Comprimento, Tamanho, ou 
Complexidade de uma Fórmula
O comprimento de uma fórmula H da lógica
proposicional, denotado por comp[H] (ou por |H|),
é definido como se segue:
– Se H é um símbolo proposicional ou de
verdade, então comp[H] = 1;
– Se H e G são fórmulas da Lógica Proposicional,
então:
comp[~H] = comp[H] + 1 (ou |~H| = |H| + 1);
comp[H ∨ G] = comp[H] + comp[G] + 1;
comp[H ∧ G] = comp[H] + comp[G] + 1;
comp[H → G] = comp[H] + comp[G] + 1;
comp[H ↔ G] = comp[H] + comp[G] + 1.
17
Exemplo:
Calcular o comprimento (ou a complexidade) da
fórmula: S = (p ∨∨∨∨ ~q) → (r ∧∧∧∧ ~q)
comp[(p ∨ ~q) → (r ∧ ~q)] =
1 + comp[(p ∨∨∨∨ ~q)] + comp[(r ∧∧∧∧ ~q)] =
1 + 2 + comp[p] + comp[~q] + comp[r] + comp[~q] =
1 + 2 + 2 + comp[p] + comp[q] + comp[r] + comp[q] =
1 + 2 + 2 + 4 = 9
ou
|(p ∨ ~q) → (r ∧ ~q)| = 1 + |(p ∨∨∨∨ ~q)| + |(r ∧∧∧∧ ~q)|
= 3 + |p| + |~q| + |r| + |~q|
= 5 + |p| + |q| + |r| + |q|
= 9 18
4
Subfórmulas
Se H é uma fórmula da Lógica Proposicional uma
subfórmula de H é definida por:
• H é uma subfórmula de H;
• Se H = (~G), então G é uma subfórmula de H;
• Se H é uma fórmula do tipo:
(G ∨ E), (G ∧ E), (G → E) ou (G ↔ E), 
então G e E são subfórmulas de H;
• Se G é subfórmula de H, 
então toda subfórmula de G é subfórmula de H.
Informalmente, uma subfórmula de H é um pedaço de H
que é fórmula.
19
Exemplo:
Liste todas as subfórmulas da fórmula: Q = (r ∨∨∨∨ s) → ~~p
Subf(Q)= { r, s, p, ~p, ~~p, (r ∨∨∨∨ s), (r ∨∨∨∨ s) → ~~p }
Observação: 
As subfórmulas próprias excluem a própria fórmula:
{ r, s, p, ~p, ~~p, (r ∨∨∨∨ s) }
Quem tem dificuldade em visualizar as subfórmulas pode
utilizar o método da árvore de decomposição exibido a
seguir.
20
Subfórmulas
Exemplo:
Liste todas as subfórmulas da fórmula: Q = (r ∨∨∨∨ s) → ~~p
(r ∨∨∨∨ s) → ~~p
(r ∨∨∨∨ s) ~~p
r s p ~p
p
Subf(Q)= { r, s, p, ~p, ~~p,(r ∨∨∨∨ s), (r ∨∨∨∨ s) → ~~p }
21
Subfórmulas Exemplo 2:
Liste todas as subfórmulas da fórmula:
R = ((p ∨ ~q) → (r ∧ ~q))
22
(p ∨ ~q) → (r ∧ ~q)
p ∨ ~q r ∧ ~q
p ~q r ~q
q q
Subf(R) = { p, q, r, ~q, p ∨ ~q, r ∧ ~q, (p ∨ ~q) → (r ∧ ~q) }
Exemplo 3:
Liste todas as subfórmulas da fórmula: 
R = ((r ∧∧∧∧ r) ↔ ((s ∨∨∨∨ r) → ((r ∨∨∨∨ s) → s)))
Subf(Q)={}
23
(r ∧ r) ↔ ((s ∨ r) → ((r ∨ s) → s))
(r ∧ r) ((s ∨ r) → ((r ∨ s) → s))
r r (s ∨ r) (r ∨ s) → s)
s r (r ∨ s) s
r s
Subf(R) = { r, s, r ∧ r, s ∨ r, r ∨ s, (r ∨ s) → s, 
(s ∨ r) → ((r ∨ s) → s), (r ∧ r) ↔ ((s ∨ r) → ((r ∨ s) → s)) }
Tabela-verdade de 
proposições compostas
1. Conta-se o número de proposições simples;
2. Se houver n proposições simples, a tabela-
verdade deverá conter 2n linhas para os
valores lógicos V e F, e mais uma linha para
as subfórmulas;
3. A tabela deverá ter uma coluna para cada
subfórmula que for possível extrair da fórmula
completa (inclusive ela mesma);
24
5
4. Preenche-se a linha de cabeçalho iniciando-se
pelas proposições simples (ex.: p, q, r, ...);
5. Em seguida vêm as negações das proposições
simples, quando existirem (ex.: ~p, ~q, ...) e as
duplas negações (~~q, ~~r, ...);
6. Segue-se informando as demais subfórmulas, de
modo que antecedam suas negações, quando
existirem (ex.: “p ∧ q” e “r → s”, antes de “~(p ∧ q)”
e “~(r → s)”), terminando pela fórmula completa
que ocupará o cabeçalho da última coluna;
7. Preenche as colunas das proposições simples
conforme explicado na aula anterior e
exemplificado a seguir: 25
Exemplo:
Dada uma proposição composta contendo 4
proposições simples, o preenchimento dos valores
VVVV e FFFF para as respectivas colunas será realizado da
seguinte forma:
A tabela-verdade conterá 24 linhas (16 linhas). Os
grupos de valores VVVV e FFFF se alternam de 8 em 8
(16/2) para a primeira proposição simples, de 4
em 4 (16/4) para a segunda, de 2 em 2 (16/8) para
a terceira e de 1 em 1 (16/16) para a quarta e
última proposição simples.
26
27
p q r s
1 V
2 V
3 V
4 V
5 V
6 V
7 V
8 V
9 F
10 F
11 F
12 F
13 F
14 F
15 F
16 F
16 Linhas?
Então de 8 em 8 
(16/2)
para a primeira 
coluna!
28
p q r s
1 V V
2 V V
3 V V
4 V V
5 V F
6 V F
7 V F
8 V F
9 F V
10 F V
11 F V
12 F V
13 F F
14 F F
15 F F
16 F F
16 Linhas?
Então de 4 em 4 
(16/4)
para a segunda 
coluna!
29
p q r s
1 V V V
2 V V V
3 V V F
4 V V F
5 V F V
6 V F V
7 V F F
8 V F F
9 F V V
10 F V V
11 F V F
12 F V F
13 F F V
14 F F V
15 F F F
16 F F F
16 Linhas?
Então de 2 em 2 
(16/8)
para a terceira 
coluna!
30
p q r s
1 V V V V
2 V V V F
3 V V F V
4 V V F F
5 V F V V
6 V F V F
7 V F F V
8 V F F F
9 F V V V
10 F V V F
11 F V F V
12 F V F F
13 F F V V
14 F F V F
15 F F F V
16 F F F F
A última 
proposição 
simples sempre 
alterna de um em 
um!
6
31
p q r s
1 V V V V
2 V V V F
3 V V F V
4 V V F F
5 V F V V
6 V F V F
7 V F F V
8 V F F F
9 F V V V
10 F V V F
11 F V F V
12 F V F F
13 F F V V
14 F F V F
15 F F F V
16 F F F F
Exemplo 2
Construir a tabela-verdade da proposição: P(p,q) = ~(p ∧ ~q)
Uma coluna para cada subfórmula
22+1
linhas p q ~q p ∧ ~q ~(p ∧ ~q)
1
2
3
4
32
Exemplo 2
Construir a tabela-verdade da proposição: P(p,q) = ~(p ∧ ~q)
p q ~q p ∧ ~q ~(p ∧ ~q)
V V
V F
F V
F F
Para uma tabela com 4 linhas:
Preenche a primeira metade da 
primeira coluna com V e a 
segunda com F.
Preenche a primeira quarta 
parte da segunda coluna com V, 
a segunda com F, a terceira com 
V e a última com F.
33
Exemplo 2
Construir a tabela-verdade da proposição: P(p,q) = ~(p ∧ ~q)
Preenche a tabela com o resultado
da interpretação das subfórmulas
p q ~q p ∧ ~q ~(p ∧ ~q)
V V F
V F V
F V F
F F V
Tenha cuidado para não ler a 
coluna errada.
Concentre-se nas colunas 
necessárias para a solução
da subfórmula.
Faça de conta que as colunas 
não necessárias no momento 
não existem.
34
Exemplo 2
Construir a tabela-verdade da proposição: P(p,q) = ~(p ∧ ~q)
p q ~q p ∧∧∧∧ ~q ~(p ∧ ~q)
V V F F
V F V V
F V F F
F F V F
35
Exemplo 2
Construir a tabela-verdade da proposição: P(p,q) = ~(p ∧ ~q)
p q ~q p ∧∧∧∧ ~q ~(p ∧∧∧∧ ~q)
V V F F V
V F V V F
F V F F V
F F V F V
36
7
Exemplo 2
Construir a tabela-verdade da proposição: P(p,q) = ~(p ∧ ~q)
E temos a tabela construída!
p q ~q p ∧ ~q ~(p ∧ ~q)
V V F F V
V F V V F
F V F F V
F F V F V
37
Bibliografia
• ABE, Jair Minoro; SCALZITTI, Alexandre; FILHO, João I. da Silva.
Introdução à lógica para a ciência da computação. São Paulo: Arte
& Ciência, 2002.
• ALENCAR FILHO, Edgard de. Iniciação à lógica matemática. São
Paulo: Nobel, 2002.
• DAGHLIAN, Jacob. Lógica e álgebra de Boole. 4. ed. São Paulo:
Atlas, 2006.
• MENDELSON, Elliot. Introduction to Mathematical Logic. 4. ed.
Boca Raton: Chapman & Hall, 2001.
• SILVA, Flávio S. Corrêa da; FINGER, Marcelo; MELO, Ana C. Vieira
de. Lógica para computação. São Paulo: Thompson Learning, 2006.
• SOUZA, João Nunes de. Lógica para ciência da computação.
Rio de Janeiro: Elsevier, 2002. 38