Mat. Discreta Logica Formal (1)

Prévia do material em texto

LÓGICA FORMAL 
Tabelas Verdade 
Prof. Evanivaldo C. Silva Jr. 
Seção 1 
Tabelas Verdade 
•  Expressões: exclamações, interrogações, 
afirmações... 
Ø Aquele aluno deve ser inteligente. 
Ø Você já almoçou hoje? 
Ø Um elefante é maior do que um gato. 
•  Proposição ou sentença (p): pode ser somente 
verdadeira (V ou 1) ou falsa (F ou 0) 
EXEMPLOS: 
Ø Dez é menor que sete 
Ø A distância entre a terra e a lua é maior do que a 
distância entre a terra e o sol. 
2 
Tabelas Verdade 
•  Negação de uma proposição (~p): podemos 
negar uma sentença de modo a inverter o seu 
valor verdade 
Exemplo: 
Ø Seja p a sentença: 5 é menor que 3(*). Então ~p pode 
ser escrita como 5 não é menor que 3 ou 5 é maior 
ou igual a 3(**) 
OBS: 
 
(*) p possui valor (F ou 0) e ~p possui valor (V ou 1) 
(**) Devemos observar a tricotomia nos números reais, isto 
é, a>b, a<b ou a=b 
3 
Tabelas Verdade 
•  Conectivos e valores verdade 
Ø Conectivos são elementos utilizados para associar 
sentenças produzindo outras mais complexas 
 
EXEMPLOS: 
Ø  2 < 3 e 10 ≠ 7, temos o conectivo e (Conjunção) 
Ø  , temos o conectivo ou (Disjunção) 2
2
3ou2 >ℜ∉
4 
Tabelas Verdade 
•  Conjunção (^) 
Ø  O conectivo de conjunção p ^ q associa as sentenças p e q 
resultando valor verdade somente quando ambas p e q são 
verdadeiras. 
Ø  Correspondem ao e lógico 
Ø  A chamada tabela verdade desse conectivo é obtida fazendo-se 
todas as combinações possíveis que as sentenças p e q podem 
assumir. 
Ø  Assim temos: 
p q p ^ q 
V V V 
V F F 
F V F 
F F F 5 
Tabelas Verdade 
•  EXEMPLOS (Conectivo de conjunção): 
Ø (1) Qual o valor da sentença p: 5 > 12 e q: 9 ≠ 4? 
 
Ø (2) Analise a frase “Pessoas com mais de 18 
anos podem possuir carteira nacional de 
habilitação (CNH) e com mais de 60 anos 
possuem atendimento especial a filas e serviços. 
 
Ø (3) Considerando p: −2 < −1, q: (−2)2< (−1)2 
determinar o valor de p ^ q 
6 
Tabelas Verdade 
•  RESPOSTAS 
Ø (1) Temos que 5 > 12 (0) e 9 ≠ 4 (1). Então pela 
tabela verdade p ^ q resulta em (F) 
Ø (2) Para p:“Pessoas com mais de 18 anos 
podem possuir carteira nacional de habilitação 
(CNH)” é (V) e q:“pessoas com mais de 60 anos 
possuem atendimento especial a filas e 
serviços.” é (V), logo p ^ q resulta em (V) 
Ø (3) Temos que p é (V) e q (F), logo p ^ q resulta 
em (F) 7 
Tabelas Verdade 
•  Disjunção (v) 
Ø  O conectivo de disjunção p v q associa as sentenças p e q 
resultando valor falso somente quando ambas p e q são falsas. 
Ø  Corresponde ao ou lógico 
Ø  A tabela verdade desse conectivo é obtida fazendo-se todas as 
combinações possíveis que as sentenças p e q podem assumir. 
Ø  Assim temos: 
p q p v q 
V V V 
V F V 
F V V 
F F F 8 
•  EXEMPLOS (Conectivo de disjunção): 
Ø (1) Qual o valor da sentença p:5 > 12 ou q:9 ≠ 4? 
 
Ø (2) Analise a frase “Pessoas com mais de 18 anos 
podem possuir carteira nacional de habilitação (CNH) ou 
com mais de 60 anos possuem atendimento especial a 
filas e serviços. 
 
Ø (3) Considerando p: −2 < −1, q: (−2)2< (−1)2 determinar o 
valor de p v q 
Ø (4) Considerando p: 98 < 57, q: (7)2< (5)2 determinar o 
valor de p v q 
Tabelas Verdade 
9 
Tabelas Verdade 
•  RESPOSTAS 
Ø (1) Temos que 5 > 12 (F) e 9 ≠ 4 (V). Então pela tabela 
verdade p resulta em (V) 
Ø (2) Para p:“Pessoas com mais de 18 anos podem possuir 
carteira nacional de habilitação (CNH)” é (V) e 
q:“pessoas com mais de 60 anos possuem atendimento 
especial a filas e serviços.” é (V), logo p v q resulta em 
(V) 
Ø (3) Temos que p é (V) e q (F), logo p v q resulta em (V) 
Ø (4) p: 98 < 57 é (F) e q: (7)2< (5)2 é (F). Portanto o valor 
de p v q é (F) 10 
Tabelas Verdade 
•  Condicionais 
Ø Expressam, como o próprio nome diz, 
condição(ões) para uma dada sentença a 
partir de outra 
Ø Podem ser de implicação (→) ou de 
equivalência (↔) 
Ø Também geram tabelas verdades 
11 
Tabelas Verdade 
•  Condicional de implicação (→) 
Ø Se p e q são proposições dadas então denotamos o 
condicional por p → q o qual pode ser lido como “se p, 
então q” ou “p é condição necessária para q” ou ainda 
“q é suficiente para p” 
Ø O condicional p → q é falso somente quando p é 
verdadeira e q é falsa, ou seja, uma verdade não pode 
implicar em algo falso 
Ø Tabela verdade: p q p → q 
V V V 
V F F 
F V V 
F F V 12 
•  EXEMPLOS: 
Ø (1) Avalie a sentença: “Se peixes nadam então cães 
voam” 
 
Ø (2) Considerando p: 2|11, q: π ∉ ℜ determinar o valor de 
p → q 
Ø (3) Considerando p: 9,99 > 9,9, q: -2< (5)2 determinar o 
valor de p → q 
Ø (4) Avalie a sentença: “Se peixes latem então a maça é 
uma fruta” 
Tabelas Verdade 
13 
•  RESPOSTAS: 
Ø (1) Considerando p: “peixes nadam” e q: “cães voam” 
temos que p é (V) e q é (F) e p → q (F) 
 
Ø (2) p: 2|11 é (F) e q: π ∉ ℜ (F) então p → q (V) 
Ø (3) p: 9,99 > 9,9 é (V) e q: -2< (5)2 é (V) então p → q (V) 
Ø (4) Considerando p: “peixes latem” e q: “maça é uma 
fruta” temos que p é (F) e q é (V) e p → q (V) 
Tabelas Verdade 
14 
Tabelas Verdade 
•  Condicional de equivalência (↔) 
Ø Se p e q são proposições dadas então denotamos o 
condicional por p ↔ q o qual pode ser lido como “p se, 
e somente se, q” ou “p é condição necessária e 
suficiente para q” 
Ø O condicional p ↔ q é verdadeiro somente quando p e q 
são ambas falsas ou verdadeiras 
Ø Tabela verdade: 
p q p ↔ q 
V V V 
V F F 
F V F 
F F V 
Por que? 
15 
•  EXEMPLOS: 
Ø (1) Avalie a sentença: “Peixes nadam se, e somente se, 
cães latem” 
 
Ø (2) Considerando p: 4|5, q: 1+2i ∉ ℜ determinar o valor 
de p ↔ q 
Ø (3) Considerando p: 9,99 > 9,9, q: (-5)2 < -(52) determinar 
o valor de p ↔ q 
Ø (4) Avalie a sentença: “Peixes latem se, e somente se, 
maça é um derivado do leite” 
Tabelas Verdade 
16 
•  RESPOSTAS: 
Ø (1) Considerando p: “Peixes nadam” e q: “cães latem”, 
então p ↔ q é (V) 
 
Ø (2) Temos que p é (F) e q é (V) assim p ↔ q é (F) 
Ø (3) Temos que p é (V) e q é (F) assim p ↔ q é (F) 
Ø (4) Considerando p: “ Peixes latem” e q: “maça é um 
derivado do leite” então p ↔ q é (V) 
Tabelas Verdade 
17 
Tabelas Verdade 
•  Tautologias: uma proposição é chamada 
de tautologia ou proposição logicamente 
verdadeira quando sempre resulta no 
valor lógico (V) independente dos 
conetivos e condicionais envolvidos 
 
EXEMPLO: Consideremos a proposição 
(p ^ ~ p)→ (q v p) 
18 
Tabelas Verdade 
•  Resolução: 
P q ~p p ^ ~p q v p (p ^ ~ p)→ (q v p) 
 
F F V F F V 
F V V F V V 
V F F F V V 
V V F F V V 
19 
Tabelas Verdade 
•  Contradição: uma proposição é chamada de 
contradição ou proposição logicamente falsa 
quando sempre resulta no valor lógico (F) 
independente dos conetivos e condicionais 
envolvidos 
 
EXEMPLO: Consideremos a proposição 
(p v ~ q) ↔ (~p ^ q) 
20 
Tabelas Verdade 
•  Resolução: 
p q ~p ~q p v ~q ~p ^ q (p v ~ q) ↔ (~p ^ q) 
F F V V V F F 
F V V F F V F 
V F F V V F F 
V V F F V F F 
21 
Tabelas Verdade 
•  Aplicações: 
(1) Um circuito eletrônico basicamente é um 
dispositivo eletrônico formado por um conjunto de 
chaves chamadas de portas lógicas que podem 
ser representadas conforme diagrama abaixo: 
Porta aberta significa 
ausência de sinal com 
valor lógico 0 (ou F) 
Porta fechada significa 
presença de sinal com 
valor lógico 1 (ou V) 
OBS: As portas podem ser ligadas em série (uma seguida da outra) ou em 
paralelo. 22 
Tabelas Verdade 
•  Nesse contexto um sinal significa uma 
corrente elétrica, por exemplo 
•  Simbolicamente os conectivos lógicos são 
representados por: 
23 
Tabelas Verdade•  Assim, uma placa mãe de computador, por 
exemplo, é formada por componentes 
eletrônicos mais sofisticados mas que 
fundamentalmente trabalham com essas 
portas lógicas. 
•  Suponhamos que um sistema de segurança 
primário de uma usina termoelétrica seja 
formado pelos seguintes subsistemas 
monitorados por sensores tabelados a 
seguir: 
24 
Tabelas Verdade 
Rótulo Subsistemas (Pontos Críticos) Limiares 
A Pressão da caldeira Abaixo do valor crítico (0), 
acima (1) 
B Temperatura da caldeira Abaixo de 150 graus (0), 
acima (1) 
C Sistema de resfriamento do rotor Funcionando (0), com défict 
(1) 
Dados fictícios elaborados pelo autor, 2012. 
25 
Tabelas Verdade 
•  Seja uma rede lógica que determina a 
análise do sistema dada por: 
Ø Se (A v B) ^ C assumir valor 1 então bloquear 
funcionamento da caldeira 
•  Em quais condições o sistema de 
funcionamento da caldeira será 
bloqueado? 
 OBS: A rede lógica é determinada a partir de fatores de segurança e 
programada de acordo com as entradas (sinal) fornecidas pelos 
sensores. 26 
Tabelas Verdade 
•  Analisando a tabela verdade da proposição temos: 
A B C A v B (A v B) ^C 
1 1 1 1 1(*) 
1 1 0 1 0 
1 0 1 1 1(*) 
1 0 0 1 0 
0 1 1 1 1(*) 
0 1 0 1 0 
0 0 1 0 0 
0 0 0 0 0 
27 
Tabelas Verdade 
•  A caldeira será bloqueada quando o valor lógico 
de saída for 1. 
•  Assim, o sistema será acionado quando a saída 
for 1(*) o que significa: 
Ø Os três subsistemas falharem simultaneamente; 
Ø Os subsistemas A (Pressão da caldeira) e C 
(Resfriamento do rotor) falharem; ou 
Ø Os subsistemas B (Temperatura da caldeira) e C 
(Resfriamento do rotor) falharem 
28 
Tabelas Verdade 
•  Relação de Equivalência (⇔) 
Ø Dizemos que a sentença p é equivalente a sentença 
q, quando as tabelas verdade de p e q resultam nos 
mesmos valores lógicos, ou seja, possuem tabelas 
verdade iguais. 
Ø Denotamos por p ⇔ q 
Ø EXEMPLO: (p → q) ⇔ (~q → ~p) 
29 
Tabelas Verdade 
p q p → q 
V V V 
V F F 
F V V 
F F V 
~q ~p ~q → ~p 
F F V 
V F F 
F V V 
V V V 
mesmos valores lógicos 
30 
Tabelas Verdade 
•  Negação de Proposições 
Ø  Negação da conjunção: ~(p ^ q) ⇔ (~p v ~q) 
p q p ^ q ~(p ^ q) 
V V V F 
V F F V 
F V F V 
F F F V 
p q ~p ~q (~p v ~q) 
V V F F F 
V F F V V 
F V V F V 
F F V V V 
31 
Tabelas Verdade 
•  Negação de Proposições 
Ø  Negação da disjunção: ~(p v q) ⇔ (~p ^ ~q) 
p q p v q ~(p v q) 
F F F V 
F V V F 
V F V F 
V V V F 
p q ~p ~q (~p ^ ~q) 
F F V V V 
F V V F F 
V F F V F 
V V F F F 
32 
Tabelas Verdade 
•  Negação de Proposições 
Ø  Negação de um condicional: ~(p → q) ⇔ (p ^ ~q) 
p q p → q ~(p → q) 
F F V F 
F V V F 
V F F V 
V V V F 
p q ~q (p ^ ~q) 
F F V F 
F V F F 
V F V V 
V V F F 
33 
Tabelas Verdade 
•  Propriedades 
Ø  p ^ q = q ^ p e p v q = q v p (propriedade comutativa) 
Ø  (p ^ q) ^ z = p ^ (q ^ z) e (p v q) v z = p v (q v z) (propriedade 
associativa) 
Ø  p ^ (1) = p e p v (0) = p (Elemento identidade) 
Ø  ~(~p)=p 
Ø  p ^ p = p e p v p = p 
Ø  p ^ (q v z) = (p ^ q) v (p ^ z) e p v (q ^ z) = (p v q) ^ (p v z) 
(Propriedades distributivas) 
Ø  p ^ (~p) = (0) e p v (~p) = (1) 
34 
Tabelas Verdade 
•  Leis de DeMorgan 
Ø  ~(p ^ q) = ~p v ~q 
 
Ø  ~(p v q) = ~p ^ ~q 
35 
Tabelas Verdade 
•  Observações 
1.  Na análise de proposições mais complexas devemos considerar 
a seguinte ordem dos operadores lógicos: 
a)  ( ), [ ], { } 
b)  ~ 
c)  ^, v 
d)  →, ↔ 
2.  Os valores lógicos V e F podem ser representados pelos 
números 1 e 0, respectivamente. 
36 
Referências Bibliográficas 
[1] Iezzi, G. e Murakami, C., Fundamentos de 
matemática Elementar, vol. 1, ed. Atual, 
2005. 
[2] Scheinerman, E. R., Matemática Discreta: 
Uma introdução, ed. Thomson, 2000. 
[3] Gersting, J.L., Fundamentos Matemáticos 
para a Ciência da Computação., ed. Rio de 
Janeiro: Livros Técnicos e Científicos, 1995. 
37