Lógica para Computação
Prof. Celso Antônio Alves Kaestner, Dr. Eng.
celsokaestner (at) utfpr (dot) edu (dot) br
Lógica para Computação (IF61B)
Lógica Proposicional



Linguagem informal x linguagem formal;
Linguagem proposicional: envolve
proposições e conectivos, formando
fórmulas complexas;
Proposição: enunciado ao qual se pode
atribuir um valor verdade (verdadeiro ou
falso);
2
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional

Conectivos: conjunção (... E ...),
disjunção (... OU ...), negação (NÃO ...),
implicação (SE … ENTÃO…),
bicondicional (...SE E SOMENTE SE...);

A Lógica Proposicional NÃO trata de
relações sobre elementos de um
conjunto, como “todos”, “algum”, nem
utiliza variáveis; isto que será visto mais
adiante, no estudo da Lógica Predicativa.
3
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional

A linguagem proposicional utiliza:
1.
Variáveis proposicionais (ou símbolos
proposicionais, ou átomos):
P = {p0, p1, p2, … };
2.
3.
Conectivos:
a)
unário: negação:  (NÃO);
b)
binários: conjunção:  (E), disjunção: 
(OU), implicação:  (SE…ENTÃO);
Símbolos de pontuação: parênteses “(” e “)”.
4
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional

Fórmulas bem formadas (fbf) são definidas
indutivamente como o menor conjunto LLP com as
seguintes regras de formação:
1.
Caso básico: todos a variáveis proposicionais
são fbf, isto é: P  LLP ;
2.
Caso indutivo 1: Se A  LLP então ( A) LLP ;
3.
Caso indutivo 2: Se A, B  LLP então (A  B) 
LLP, (A  B)  LLP, e (A  B)  LLP.
5
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Exemplos de fórmulas:

•
((p0  ( p1))  ( (( p0)  p1)))
•
(p  (q  p))
•
(p  ( ( p)))
•
(( p)  ( (( q)  r)))
•
((p0  ( p1))  ( (( p0)  p1)))
•
(p  ((q  ( p))  ( q)))
6
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Regras para a omissão de parênteses:

•
O parênteses mais externo pode ser eliminado;
•
O uso repetido de  ou de  dispensa os parênteses;
neste caso considera-se que os parênteses são aninhados
à esquerda:
p  q  r   s representa (((p  q)  r)  ( s))
•
O uso repetido de  também dispensa os parênteses,
mas neste caso eles aninham-se à direita:
p  q  r   s representa (p  (q  (r  ( s))))
7
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional

Utiliza-se ainda a seguinte precedência entre
os conectivos: , ,  e .

Logo:
•
pq
•
p  q  r representa ((p  q)  r);
•
p  r  q representa ((p  r)  q).
representa
(( p)  q);
8
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional

Diz-se que g é uma subfórmula de uma fórmula
f se g atende as condições para ser uma fbf e
além disto é compatível com a estrutura de f.

O conjunto subf (f) das subfórmulas de f pode
ser obtido indutivamente por:
•
Se f = p (uma variável proposicional) então
Subf (f) = { p };
•
Se f =  g então Subf (f) = { g} U Subf (g);
•
Se f = g  h, f = g  h ou f = g  h então
Subf (f) = { f } U Subf (g) U Subf (h).
9
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional

Exemplo:
f =  p  r  (p  s) = (( p)  (r  (p  s)))
Subf(f)=
{ p  r  (ps)} U Subf( p) U Subf(r  (p  s)) =
{ p  r  (p  s)} U { p} U Subf(p) U {r  (p  s)} U
Subf(r) U Subf(p  s) =
{ p  r  (p  s),  p} U {p} U {r  (p  s)} U {r} U
{ps} U Subf(p) U Subf(s) =
{ p  r  (p  s),  p, r  (p  s)}, p, r, p  s} U {p}
U {s}
10
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Outra definição indutiva muito utilizada é a do
tamanho de uma fórmula:

•
|p| = 1 se p é uma variável proposicional;
•
|  f | = 1 + | f |;
•
| f  g | = |f  g|= |f  g|= 1 + |f | + |g|.
11
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Itens adicionais:

Expressando ideias em Lógica Proposicional
(ver item 1.2.4 da referência 1);

Exercícios (ver pg. 12 da referência 1).
12
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Semântica:

Consiste na atribuição de valores-verdade às
fórmulas da linguagem;

Os valores-verdade no caso clássico são
“verdadeiro” (1) e “falso” (0);

Os valores-verdade são associados aos
símbolos proposicionais por meio de uma
função de valoração (ou interpretação):
V: P  { 0,1 }
13
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Para as demais fórmulas:
1.
V ( A) = 1 se e somente se V (A) = 0 ;
2.
V (A  B) = 1 se e somente se V (A) = 1 e
V (B) = 1;
3.
V (A  B) = 1 se e somente se V (A) = 1 ou
V (B) = 1;
4.
V (A  B) = 1 se e somente se V (A) = 0
ou V (B) = 1.
14
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional

Dada uma fórmula proposicional f e uma
interpretação V, a atribuição de valores-verdade
definida anteriormente permite a obtenção do
valor-verdade V(f) da fórmula f;

Por exemplo, se f = (p  (q  p)) e se V(p) = 1 e
V(q) = 0, então o valor-verdade de f pode ser
computado por:
V(1  (0 1)) = V(1  1)) = V(1) = 1
15
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Os valores-verdade produzidos pelos conectivos podem
ser mais claramente vistos nas tabelas a seguir:
Não:
E:
f
f
0
1
1
0
f
g
f g
0
0
0
0
1
0
1
0
0
1
1
1
16
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Ou:
Implica:
f
g
f g
0
0
0
0
1
1
1
0
1
1
1
1
f
g
f g
0
0
1
0
1
1
1
0
0
1
1
1
17
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Satisfação e validade:
1. Uma fórmula A é satisfazível se e somente se
existe uma interpretação V tal que V (A) = 1;
2. Uma fórmula A é insatisfazível (ou uma
contradição) se e somente se para todas as
interpretações possíveis V tem-se V(A) = 0;
3. Uma fórmula A é válida (ou uma tautologia) se e
somente se para toda interpretação V tem-se
V(A) = 1;
4. Uma fórmula A é falsificável se e somente se
existe uma valoração V tal que V (A) = 0.
18
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Algumas consequências:
1.
Toda fórmula válida é também satisfazível;
2.
Toda fórmula insatisfazível é falsificável;
3.
Uma fórmula pode ser satisfazível e falsificável:
neste caso é dita contingente;
4.
Uma fórmula não pode ser válida e insatisfazível;
5.
Se A é válida,  A é insatisfazível e
reciprocamente;
6.
Se A é satisfazível,  A é falsificável e
reciprocamente.
19
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Tabelas-verdade:
1.
Dada uma fórmula proposicional f, a tabela
apresenta os valores-verdade de f para todas as
interpretações possíveis;
2.
Para uma fórmula com n variáveis existem 2n
interpretações possíveis;
3.
A ordem de avaliação dos conectivos deve ser
estritamente seguida;
4.
As propriedades lógicas da fórmula (validade,
satisfação, etc) são facilmente verificáveis.
20
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Exemplo de tabela-verdade:
(p

(q


p))
(1)
(4)
(1)
(3)
(2)
(1)
0
1
0
1
1
0
0
1
1
1
1
0
1
1
0
1
0
1
1
0
1
0
0
1
21
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional


Prática de tabelas-verdade:
•
http://www.math.csusb.edu/notes/quizzes
/tablequiz/tablepractice.html ;
•
http://en.wikipedia.org/wiki/Truth_table ;
•
http://www.brianborowski.com/Software/Truth/.
Exercícios (ver referência 1 à página 20).
22
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
23
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
24
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
f
g
0
...
0
...
1
1
0
...
1
1
0
...
1
1
25
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
26
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Algumas equivalências notáveis:
  p  p (dupla negação);
1.
2.
p  q   p  q (definição de  em função de 
e );
3.
 (p  q )  ( p   q ) e  (p  q )  ( p   q )
(leis de De Morgan);
4.
p  ( q  r )  ( p  q )  (p  r ) (distributividade
de  sobre );
5.
p  ( q  r )  ( p  q )  (p  r ) (distributividade de
 sobre ).
27
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Equivalência lógica usando tabelas-verdade: para que
se tenha A  B os valores-verdade de V(A) e de
V(B) devem ser os mesmos em todas as linhas.
f
g
...
...
0
0
1
1
...
...
1
1
0
0
1
1
28
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
Definições dos conectivos em função de  e  :
•
1.
p  q   p  q   (  p  q);
2.
p  q   ( p   q ).
É possível se definir todos os conectivos em
função de um só ?
29
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
A
B
0
0
1
1
0
1
0
1
1
0
0
1
1
1
0
0
30
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional
31
Prof. Celso A A Kaestner
05/11/2015
Lógica para Computação (IF61B)
Lógica Proposicional

Exercícios (página 27 da referência 1);

Desafios da Lógica Proposicional (ver
item 1.6 da referência 1 à página 28).
32
Prof. Celso A A Kaestner
05/11/2015