01-Algebra-Boole Slides do Renato de Matematica discreta

Prévia do material em texto

Álgebra de Boole
GCC103 - Matemática Discreta
DCC/UFLA
Prof. Eric
 
Lógica Matemática
● Básica para qualquer estudo em Computação
● É básica, em particular, para a Matemática Discreta
● Para desenvolvimento de qualquer algoritmo é 
necessário o conhecimento de lógica
 
Lógica Matemática
● Lógica permite definir Teorema
● Por que teoremas e suas demonstrações são 
fundamentais para a Computação e Informática?
– teorema (freqüentemente) pode ser visto como 
problema a ser implementado 
computacionalmente
– Demonstração
● solução computacional
● algoritmo o qual prova-se, sempre funciona!
 
Lógica Matemática
● Objetivo
– introduzir principais conceitos e terminologia 
necessários para MD
● não é uma abordagem ampla nem detalhada
● existe uma disciplina específica de Lógica
 
Lógica
● Estudo centrado em
– Lógica Booleana ou Lógica de Boole
● George Boole: inglês, 1815-1864
– um dos precursores da Lógica
● estudo dos princípios e métodos usados para 
distinguir sentenças verdadeiras de falsas
 
Conceito de Proposição
Definição 1: Chama-se proposição todo o conjunto 
de palavras ou símbolos que exprimem um 
pensamento de sentido completo.
 
Conceito de Proposição
As proposições transmitem pensamentos, isto é, 
afirmam fatos. Exemplos:
● A Lua é satélite da Terra
● Belo Horizonte é capital de Minas Gerais
● π > √5
 
Conceito de Proposição
● Exp: Não são proposições
– Vá tomar banho.
– Que horas são?
– Parabéns!
 
Conceito de Proposição
As proposições que se seguem são falsas:
● Vasco da Gama descobriu o Brasil
● ¾ é um número inteiro
● A Rússia fica na América Central
 
Conceito de Proposição
Princípios fundamentais da Lógica Matemática, 
dita bivalente:
1 – Princípio da não contradição: uma proposição 
não pode ser verdadeira e falsa ao mesmo tempo
2 – Princípio do terceiro excluído: toda a 
proposição ou é verdadeira ou é falsa, isto é, 
verifica-se sempre um destes casos e nunca um 
terceiro.
 
Valores Lógicos das Proposições
Definição 2: Chama-se valor lógico de uma 
proposição a verdade se a proposição é verdadeira e 
falsidade se a proposição é falsa.
 
Proposições Simples e Compostas
Definição 3: Chama-se proposição simples ou 
proposição atômica aquela que não contém nenhuma 
outra proposição como parte integrante de si mesma.
 
Proposições Simples e Compostas
As proposições simples são geralmente designadas 
por letras latinas minúsculas, conforme exemplo a 
seguir:
p: Carlos é careca
q: Marcelo é engenheiro
r: O gato mia
 
Proposições Simples e Compostas
Definição 4: Chama-se proposição composta ou 
proposição molecular aquela formada pela 
combinação de duas ou mais proposições.
 
Proposições Simples e Compostas
As proposições compostas são geralmente designadas 
por letras latinas maiúsculas, conforme exemplo a 
seguir:
P: Carlos é careca e Pedro é engenheiro
Q: Se Carlos é careca, então é rico
R: O gato mia ou o cachorro pia
 
Conectivos
Definição 5: Chamam-se conectivos palavras que 
se usam para formar novas proposições a partir de 
outras.
 
Conectivos
São conectivos usuais em Lógica Matemática as 
palavras:
● “e” (conjunção),
● “ou” (disjunção), 
● “não” (negação), 
● “se ... então” (condicional), 
● “... se e somente se ...” (bicondicional).
 
Tabela Verdade
● como construir uma tabela verdade de uma dada 
fórmula?
● explicitar todas as combinações possíveis dos 
valores lógicos
– das fórmulas atômicas componentes
● fórmula atômica não-constante
– dois valores lógicos: V e F
● fórmula atômica constante
– valor verdade fixo (V ou F)
 
Tabela Verdade
Princípio 1: O valor lógico de qualquer proposição 
composta depende unicamente dos valores lógicos 
das proposições simples componentes, ficando por 
eles univocamente determinado.
 
Tabela Verdade
Para aplicar esse princípio na prática à 
determinado valor lógico de uma proposição 
composta, recorre-se a um dispositivo chamado 
tabela-verdade. 
Essa tabela contém todas as possibilidades de 
valores lógicos da proposição composta 
correspondentes a todas as possíveis atribuições de 
valores lógicos dadas às proposições simples.
 
Tabela Verdade
Uma tabela verdade terá sempre linhas, onde n 
é o número de proposições simples que compõem a 
proposição composta.
 
Tabela Verdade
Construção da Tabela Verdade para a fórmula 
p v ~q
 
Operações sobre Proposições
Ao raciocinarmos, utilizamos muitas vezes 
operações sobre proposições, chamadas também de 
operações lógicas. Estas seguem regras de um 
cálculo denominado cálculo proposicional, 
semelhante ao da aritmética sobre números. As 
operações abaixo são utilizadas nesse cálculo.
 
Negação ( /~ )
Definição 6: Chama-se negação de uma proposição p 
a proposição representada por “não p”, cujo valor 
lógico é a verdade (V) quando p é falsa e a falsidade 
(F) quando p é verdadeira.
 
Negação
Assim, “não p” tem valor lógico oposto daquele de 
p. Simbolicamente, a negação de p é notada por “~p”. 
A seguinte tabela-verdade define a negação:
p ~p
V F
F V
 
Negação
A negação da proposição:
p: O Sol é uma estrela é ~p: O Sol não é uma 
estrela
 
Conjunção (^)
Definição 7: Chama-se conjunção de duas 
proposições p e q a proposição representada por “p e 
q”, cujo valor lógico é a verdade (V) quando as 
proposições p e q são ambas verdadeiras e a 
falsidade (F) nos demais casos.
 
Conjunção
Simbolicamente, a conjunção de duas proposições p e 
q é representada por “p ^ q”, onde lê-se “p e q”. A 
tabela-verdade que define o valor lógico da conjunção 
é dada abaixo:
p q p^q
V V V
V F F
F V F
F F F
 
Disjunção (v)
Definição 8: Chama-se disjunção de duas 
proposições p e q a proposição representada por “p 
ou q”, cujo valor lógico é a verdade (V) quando ao 
menos uma das proposições p e q é verdadeira e 
falsidade (F) quando as proposições p e q são ambas 
falsas.
 
Disjunção
Simbolicamente, a disjunção de duas proposições p e 
q é representada por “p v q”, onde lê-se “p ou q”. A 
tabela verdade que define o valor lógico da disjunção 
é dada abaixo:
p q p v q
V V V
V F V
F V V
F F F
 
Disjunção Exclusiva ( v )
Na linguagem utilizada cotidianamente, a palavra 
“ou” apresenta dois sentidos. Consideremos as 
seguintes proposições compostas:
P: Carlos é médico ou professor
Q: Márcio é alagoano ou gaúcho
 
Disjunção Exclusiva
Dizemos que P é “ou” inclusivo, enquanto Q é 
“ou” exclusivo. O símbolo para o “ou” exclusivo é v, 
sendo a simbologia utilizada da seguinte forma:
P: Carlos é médico v Carlos é professor
Q: Márcio é alagoano v Márcio é gaúcho
 
Disjunção Exclusiva
A tabela-verdade é dada abaixo:
p q P v q
V V F
V F V
F V V
F F F
 
Condicional (→)
Definição 9: Chama-se proposição condicional ou 
apenas condicional uma proposição representada por 
“se p então q”, cujo valor lógico é a falsidade (F) no 
caso em que p é verdadeira e q é falsa e a verdade (V) 
nos demais casos.
 
Condicional
Utiliza-se o símbolo “→”, chamado de implicação 
para representar a condicional de duas proposições. A 
tabela-verdade da condicional é dada abaixo:
p q p → q
V V V
V F F
F V V
F F V
 
Condicional
● p → q: Se GALOIS morreu em duelo (p), então π é 
um número real (q)
V(p → q) = V(p) → V(q) = V → V = V
● p → q: Se o mês de Maio tem 31 dias (p), então o 
ano tem 9 meses (q)
V(p → q) = V(p) → V(q) = V → F = F
 
Condicional
Uma condicional afirma unicamente uma relação 
entre os valores lógicos do antecedente e do 
consequente deacordo com sua tabela verdade.
 
Bicondicional (↔)
Definição 10: Chama-se proposição bicondicional 
ou apenas bicondicional uma proposição 
representada por “p se e somente se q”, cujo valor 
lógico é a verdade (V) quando p e q são ambos 
verdadeiras ou ambas falsas, e a falsidade (F) nos 
demais casos.
 
Bicondicional
O símbolo utilizado para indicar a bicondicional de 
duas proposições p e q é utilizando a notação p ↔ q, 
o que denota que:
● p é condição necessária e suficiente para q
● q é condição necessária e suficiente para p
 
Bicondicional
A tabela verdade que denota os valores lógicos para 
duas proposições é dada abaixo:
p q p ↔ q
V V V
V F F
F V F
F F V
 
Bicondicional
● p ↔ q: Roma fica na Europa (p) se e somente se a 
neve é branca (q)
V(p↔q) = V(p) ↔ V(q) = V ↔ V = V
● p ↔ q: Vasco da Gama descobriu o Brasil se e 
somente se Tiradentes foi enforcado
V(p↔q) = V(p) ↔ V(q) = F ↔ V = F
 
Tautologia
Definição 11: Denomina-se tautologia ou 
proposição tautológica a proposição composta que é 
sempre verdadeira. Na tabela de verdade de uma 
proposição tautológica, a última coluna contém 
somente valores V (verdadeiro).
 
Contradição
Definição 12: Denomina-se contradição ou 
proposição contraditória a proposição composta que 
é sempre falsa. Na tabela de verdade de uma 
proposição contraditória, a última coluna contém 
somente valores F (falso).
 
Contingência
Definição 13: Denomina-se contingência ou 
proposição contingencial a proposição composta que 
pode ser verdadeira e pode ser falsa. Na tabela de 
verdade de uma proposição contingencial, a última 
coluna contém valores V (verdadeiro) e F(falso).
 
Fórmulas
● Fórmulas Lógicas ou simplesmente Fórmulas
– palavras da Linguagem Lógica
– introduzido formalmente adiante
● quando do estudo da Definição Indutiva
● informalmente, sentença lógica corretamente 
construída sobre o alfabeto cujos símbolos são
– Conetivos ( , , →, …)∧ ∨
– Parênteses
– identificadores (p, q, r, …)
– constantes, etc.
 
Fórmulas
● Se a fórmula contém variáveis 
– não necessariamente possui valor verdade 
associado
– valor lógico depende do valor verdade das 
sentenças que substituem as variáveis na fórmula
 
Fórmulas
● Exp: Fórmulas
● Suponha p, q e r são sentenças variáveis
– valores verdade constantes V e F
– qualquer proposição
● p, q e r
● ¬p, p q, p q, p → q e p ↔ q∧ ∨
● p (¬q)∨
● (p ¬q) → F∧
● ¬(p q) ↔ (¬p ¬q)∧ ∨
● • p (q r) ↔ (p q) (p r)∨ ∧ ∨ ∧ ∨
 
Fórmulas
● Precedência entre os conetivos
– reduzir os parênteses
– simplificar visualmente
● Ordem de precedência entre os conetivos
– entre parênteses, dos mais internos para os mais 
externos
– Negação (¬)
– conjunção ( ) e disjunção ( )∧ ∨
– Condição (→)
– bicondição (↔)
 
Fórmulas
● Exp: Precedência de Conetivos
● p (¬q)∨ p ¬q∨
● (p ¬q) → F∧ p ¬q → F∧
● ¬(p q) ↔ (¬p ¬q)∧ ∨ ¬(p q) ↔ ¬p ¬q∧ ∨
● p (q r) ↔ (p q) (p r)∨ ∧ ∨ ∧ ∨
– qualquer omissão de parênteses resulta em 
ambiguidade (por quê?)
 
Fim da Aula 01
● Exercícios
● Determinar V(p) em cada um dos seguintes casos:
– V(q) = F e V(p ^ q) = F
– V(q) = F e V(p v q) = F
– V(q) = F e V(p → q) = F
– V(q) = F e V(q → p) = V
– V(q) = V e V(p ↔ q) = F
– V(q) = F e V(q ↔ p) = V
 
Fim da Aula 01
● Exercícios
● Determinar V(p) e V(q) em cada um dos seguintes 
casos:
– V(p → q) = V e V(p ^ q) = F
– V(p → q) = V e V(p v q) = F
– V(p ↔ q) = V e V(p ^ q) = V
– V(p ↔ q) = V e V(p v q) = V
– V(p ↔ q) = F e V(~p v q) = V
 
Implicação Lógica
Definição 14: Diz-se que uma proposição P(p,q,r,...) 
implica logicamente ou apenas implica uma 
proposição Q(p,q,r,...), se Q(p,q,r,...) é verdadeira (V) 
todas as vezes que P(p,q,r,...) é verdadeira (V). Em 
outras palavras, Q é consequência lógica de P, P => 
Q, se e somente se Q é verdadeira sempre que P é 
verdadeira.
 
Implicação Lógica
A Implicação Lógica apresenta duas propriedades, a 
saber:
Reflexiva (R): P(p,q,r,...) => P(p,q,r,...)
Transitiva (T): Se P(p,q,r...) => Q(p,q,r,...) e 
Q(p,q,r,...) => R(p,q,r,...), então P(p,q,r,...) => 
R(p,q,r,...)
 
Implicação Lógica
Teorema 1: A proposição P(p,q,r,...) implica a 
proposição Q(p,q,r,...), isto é:
P(p,q,r,...) => Q(p,q,r,...)
se e somente se a condicional:
P(p,q,r,...) → Q(p,q,r,...)
é tautológica.
 
Implicação Lógica
A partir das implicações podemos inferir algumas 
regras importantes para a álgebra booleana. 
Considere a seguinte tabela:
p q p ^ q p v q
V V V V
V F F V
F V F V
F F F F
 
Dada a tabela, podemos inferir as seguintes regras:
– Adição: p => p v q e q => p v q
– Simplificação: p ^ q => p e p ^ q => q
p q p ^ q p v q
V V V V
V F F V
F V F V
F F F F
 
Tomemos agora a seguinte tabela verdade para a 
proposição (p v q) ^ ~p:
A partir daí, podemos afirmar a seguinte implicação 
lógica:
(p v q) ^ ~p => q e (p v q) ^ ~q => p
denominada Regra do Silogismo Disjuntivo.
p q p v q ~p (p v q) ^ 
~p
V V V F F
V F V F F
F V V V V
F F F V F
 
● A tabela acima é referente à proposição 
(p → q) ^ p.
● Dessa tabela, podemos fazer a inferência que gera 
a Regra Modus Ponens:
– (p → q) ^ p => q
p q p → q (p → q)^p
V V V V
V F F F
F V V F
F F V F
 
● A tabela para as proposições (p → q)^~q e ~p pode 
ser vista acima.
Essa tabela nos permite fazer a inferência lógica 
denominada Regra Modus Tollens:
(p → q) ^ ~q => ~p
p q ~p ~q p → q (p → q)^~q
V V F F V F
V F F V F F
F V V F V F
F F V V V V
 
Regras de Equivalência
● Definição 15: Diz-se que uma proposição 
P(p,q,r,...) é logicamente equivalente ou apenas 
equivalente a uma proposição Q(p,q,r,...), se as 
tabelas-verdade destas duas proposições são 
idênticas.
 
Regras de Equivalência
● Simbolicamente, representamos duas expressões 
logicamente equivalentes da seguinte forma:
– P(p,q,r,...) <=> Q(p,q,r,...)
 
Regras de Equivalência
● A relação de equivalência lógica apresenta as 
seguintes propriedades:
● 1. Reflexiva (R): P(p,q,r,...) <=> P(p,q,r,...)
● 2. Simétrica (S): Se P(p,q,r,...) <=> Q(p,q,r,...), então 
Q(p,q,r,...) <=> P(p,q,r,...)
● 3. Transitiva (T): Se P(p,q,r,...) <=> Q(p,q,r,...) e Q(p,q,r,...) 
<=> R(p,q,r,...), então P(p,q,r,...) <=> R(p,q,r,...)
 
Regras de Equivalência
● A partir das equivalências lógicas, podemos concluir 
algumas regras importantes, conforme veremos a seguir.
● (i) As proposições “~~p” e “p” são equivalentes, o que 
pode ser demonstrado pela tabela-verdade abaixo. Essa 
equivalência ~~p <=> p gera a chamada Regra da dupla 
negação.
p ~p ~~p
V F V
F V F
 
Regras de Equivalência
● (ii) As proposições “~p → p” e “p” também são 
equivalentes, ou seja, ~p → p <=> p. Isso pode ser 
visto na tabela abaixo e caracteriza a Regra de 
Clavius.
p ~p ~p → p
V F V
F V F
 
Regras de Equivalência
● (iii) A partir das proposições “p → p ^ q” e “p → 
q” chegamos à Regra da absorção, onde:
p → p ^ q <=> p → q
Exercício: Faça a tabela verdade e demonstre que 
essa relação se comprova.
 
Regras de Equivalência
● (iv) A condicional “p → q” e a disjunção “~p v q” 
têm tabelas idênticas, e por consequência lógica, 
são equivalentes, ou seja:
p → q <=> ~p v q
Exercício: Faça a tabela verdade e demonstre que 
essa relação se comprova.
 
Regras de Equivalência
● (v) A bicondicional “p ↔ q” e a conjunção “(p → 
q) ^ (q → p)” têm tabelas-verdade idênticas, o que 
nos leva à conclusão de que há equivalência lógica 
conforme segue:
p ↔ q <=> (p → q) ^ (q → p)
Exercício: Faça a tabela verdade e demonstre que 
essa relaçãose comprova.
 
Regras de Equivalência
● (vi) A bicondicional “p ↔ q” e a disjunção “(p 
^q) v (~p ^ ~q)” têm tabelas idênticas, e são 
portanto equivalentes, ou seja:
p ↔ q <=> (p ^q) v (~p ^ ~q)
Exercício: Faça a tabela verdade e demonstre que 
essa relação se comprova.
 
Regras de Equivalência
● Teorema 2: A proposição P(p,q,r,...) é equivalente 
à proposição Q(p,q,r,...), isto é:
P(p,q,r,...) <=> Q(p,q,r,...) se e somente se a 
bicondicional: P(p,q,r,...) ↔ Q(p,q,r,...) é 
tautológica.
 
Regras de Equivalência
P ^ V <=> P
P v F <=> P
Identidade
P v V <=> V
P ^ F <=> F
Dominação
P v P <=> P
P ^ P <=> P
Idempotência
~(~P) <=> P Dupla negação
P v Q <=> Q v P
P ^ Q <=> Q ^ P
Comutatividade
(P v Q) v R <=> P v (Q v R)
(P ^ Q) ^ R <=> P ^ (Q ^ R)
Associatividade
 
Regras de Equivalência
P ^ (Q v R) <=> (P ^ Q) v (P ^ R)
P v (Q ^ R) <=> (P v Q) ^ (P v R)
Distributividade
~(P ^ Q) <=> ~P v ~Q
~(P v Q) <=> ~P ^ ~Q
De Morgan
P → Q <=> ~P v Q Implicação
P v ~P <=> V Tautologia
P ^ ~P <=> F Contradição
(P → Q) ^ (Q → P) <=> P ↔ Q Equivalência
 
Regras de Equivalência
(P → Q) ^ (P → ~Q) <=> ~P Absurdo
(P → Q) <=> (~Q → ~P) Contrapositiva
P v (P ^ Q) <=> P
P ^(P v Q) <=> P
Absorção
(P ^ Q) → R <=> P → (Q → R) Exportação
 
Método Dedutivo
Até aqui utilizamos tabelas verdade para demonstrar 
equivalências e implicações. O Método Dedutivo é 
uma alternativa mais eficiente, onde desempenham 
papel importante as equivalências relativas à Álgebra 
das Proposições, que subsistem quando as 
proposições simples p, q, r, t (Verdadeira) e c (Falsa), 
que nelas figuram, são substituídas respectivamente 
por proposições compostas P, Q, R, T (tautologia) e C 
(contradição).
 
Método Dedutivo
● Demonstre as implicações:
● (i) c => p
– c → p <=> ~c v p <=> t v p <=> t
● (ii) p => t
– p → t <=> ~p v t <=> t
 
Método Dedutivo
● Demonstrar a implicação p ^ q => p 
(Simplificação)
– p ^ q → p <=> ~(p ^ q) v p <=> (~p v ~q) v p 
<=> (~p v p) v ~q <=> T v ~q <=> T
● Demonstrar a implicação p => p v q (Adição)
– p → p v q <=> ~p v (p v q) <=> (~p v p) v q <=> 
T v q <=> T
 
Método Dedutivo
● Demonstrar a implicação (p → q) ^ p => q (Modus 
Ponens)
– (p → q) ^ p <=> p ^(~p v q) <=> (p^~p) v (p^q) 
<=> C v (p ^ q) <=> p ^ q => q
● Demonstrar a implicação (p → q) ^ ~q => ~p 
(Modus tollens)
– (p → q) ^ ~q <=> (~p v q) ^ ~q <=> (~p ^ ~q) v 
(q ^ ~q) <=> (~p ^ ~q) v C <=> ~p ^ ~q => ~p
 
Método Dedutivo
● Demonstrar a implicação (p v q) ^ ~p => q 
(Silogismo Disjuntivo)
– (p v q) ^ ~p <=> (p ^ ~p) v (q ^ ~p) <=> C v 
(q^~p) <=> q ^ ~p => q
● Demonstrar a implicação p ^ q => p v q
– p ^ q → p v q <=> ~(p ^ q) v (p v q) <=> (~p v 
~q) v (p v q) <=> (~p v p) v (~q v q) <=> T v T 
<=> T
 
Método Dedutivo
Redução no número de conectivos
Teorema: Entre os cinco conectivos fundamentais (~, 
^, v, →, ↔), três exprimem-se em termos de apenas 
dois dos pares:
– (1) ~ e v
– (2) ~ e ^
– (3) ~ e → 
 
Método Dedutivo
Redução no número de conectivos
(1) ^, → e ↔ exprimem-se em função de ~ e v
p^q <=> ~~p ^ ~~q <=> ~(~p v ~q)
p → q <=> ~p v q
p ↔ q <=> (p → q)^(q → p) <=> ~(~(~p v q) v ~(~q 
v p))
 
Método Dedutivo
Redução no número de conectivos
(2) v, → e ↔ exprimem-se em função de ~ e ^
p v q <=> ~~p v ~~q <=> ~(~p ^ ~q)
p → q <=> ~p v q <=> ~(p ^ ~q)
p ↔ q <=> (p → q) ^ (q → p) <=> ~(p ^ ~q) ^ ~(~p ^ 
q)
 
Método Dedutivo
Redução no número de conectivos
(3) ^, v, ↔ exprimem-se em função de ~ e → 
p ^ q <=> ~(~p v ~q) <=> ~(p → ~q)
p v q <=> ~~p v q <=> ~p → q
p ↔ q <=> (p → q) ^ (q → p) <=> ~((p → q) → ~(q 
→ p))
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73
	Slide 74
	Slide 75
	Slide 76
	Slide 77
	Slide 78
	Slide 79
	Slide 80
	Slide 81