Algebra Boole

Prévia do material em texto

Algebra de Boole
Renato Ramos da Silva
Universidade Federal de Lavras
renato.ramos@dcc.ufla.br
5 de outubro de 2015
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 1 / 19
Overview
1 Algebra de Boole
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 2 / 19
Algebra de Boole
Introdução
estudo dos princípios e métodos usados para distinguir sentenças
verdadeiras de falsas (operadores lógicos)
Lógica permite definir teoremas
Demonstração (solução computacional)
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 3 / 19
Algebra de Boole
Proposição
Todo o conjunto de palavras ou símbolos que exprimem um pensamento de
sentido completo.
Exemplos
A Lua é satélite da Terra
Belo Horizonte é capital de
Minas Gerais
pi >
√
5
Vasco da Gama descobriu o
Brasil
3
4 é um número inteiro
A Rússia fica na América
Central
Vá tomar banho.
Que horas são?
Parabéns!
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 19
Algebra de Boole
Proposição
Todo o conjunto de palavras ou símbolos que exprimem um pensamento de
sentido completo.
Exemplos
A Lua é satélite da Terra
Belo Horizonte é capital de
Minas Gerais
pi >
√
5
Vasco da Gama descobriu o
Brasil
3
4 é um número inteiro
A Rússia fica na América
Central
Vá tomar banho.
Que horas são?
Parabéns!
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 19
Algebra de Boole
Proposição
Todo o conjunto de palavras ou símbolos que exprimem um pensamento de
sentido completo.
Exemplos
A Lua é satélite da Terra
Belo Horizonte é capital de
Minas Gerais
pi >
√
5
Vasco da Gama descobriu o
Brasil
3
4 é um número inteiro
A Rússia fica na América
Central
Vá tomar banho.
Que horas são?
Parabéns!
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 19
Algebra de Boole
Proposição
Todo o conjunto de palavras ou símbolos que exprimem um pensamento de
sentido completo.
Exemplos
A Lua é satélite da Terra
Belo Horizonte é capital de
Minas Gerais
pi >
√
5
Vasco da Gama descobriu o
Brasil
3
4 é um número inteiro
A Rússia fica na América
Central
Vá tomar banho.
Que horas são?
Parabéns!
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 19
Algebra de Boole
Proposição
Todo o conjunto de palavras ou símbolos que exprimem um pensamento de
sentido completo.
Exemplos
A Lua é satélite da Terra
Belo Horizonte é capital de
Minas Gerais
pi >
√
5
Vasco da Gama descobriu o
Brasil
3
4 é um número inteiro
A Rússia fica na América
Central
Vá tomar banho.
Que horas são?
Parabéns!
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 19
Algebra de Boole
Proposição
Todo o conjunto de palavras ou símbolos que exprimem um pensamento de
sentido completo.
Exemplos
A Lua é satélite da Terra
Belo Horizonte é capital de
Minas Gerais
pi >
√
5
Vasco da Gama descobriu o
Brasil
3
4 é um número inteiro
A Rússia fica na América
Central
Vá tomar banho.
Que horas são?
Parabéns!
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 19
Algebra de Boole
Proposição
Todo o conjunto de palavras ou símbolos que exprimem um pensamento de
sentido completo.
Exemplos
A Lua é satélite da Terra
Belo Horizonte é capital de
Minas Gerais
pi >
√
5
Vasco da Gama descobriu o
Brasil
3
4 é um número inteiro
A Rússia fica na América
Central
Vá tomar banho.
Que horas são?
Parabéns!
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 19
Algebra de Boole
Proposição
Todo o conjunto de palavras ou símbolos que exprimem um pensamento de
sentido completo.
Exemplos
A Lua é satélite da Terra
Belo Horizonte é capital de
Minas Gerais
pi >
√
5
Vasco da Gama descobriu o
Brasil
3
4 é um número inteiro
A Rússia fica na América
Central
Vá tomar banho.
Que horas são?
Parabéns!
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 19
Algebra de Boole
Proposição
Todo o conjunto de palavras ou símbolos que exprimem um pensamento de
sentido completo.
Exemplos
A Lua é satélite da Terra
Belo Horizonte é capital de
Minas Gerais
pi >
√
5
Vasco da Gama descobriu o
Brasil
3
4 é um número inteiro
A Rússia fica na América
Central
Vá tomar banho.
Que horas são?
Parabéns!
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 4 / 19
Algebra de Boole
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.
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 5 / 19
Algebra de Boole
Proposição simples.
Proposição composta.
Conectivos:
1 conjunção (e)- ∧
2 disjunção (ou) - ∨(inclusiva) ∨(exclusiva)
3 negação (não) - ∼ ou ¬
4 condicional (se ... então) - →
5 bicondicional (... se e somente se ...) - ↔
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 6 / 19
Algebra de Boole
Tautologia ou Proposição tautológica t
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 ou Proposição contraditória c
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 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).
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 7 / 19
Implicação Lógica
Definição
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.
Propriedades
Reflexiva: P(q, r , s, ...) =⇒ P(q, r , s, ...)
Transitiva: Se P(q, r , s, ...) =⇒ Q(q, r , s, ...) e
Q(q, r , s, ...) =⇒ R(q, r , s, ...), então P(q, r , s, ...) =⇒ R(q, r , s, ...)
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 8 / 19
Implicação Lógica
Teorema
A proposição P(p,q,r,...) implica a proposição Q(p,q,r,...), isto é:
P(q, r , s, ...) =⇒ Q(q, r , s, ...)
se e somente se a condicional:
P(q, r , s, ...)→ Q(q, r , s, ...)
é tautologica
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 9 / 19
Implicação Lógica
Adição: p =⇒ p ∨ q ou q =⇒ p ∨ q
Simplificação: p ∧ q =⇒ p ou p ∧ q =⇒ q
Regra do Silogismo Disjuntivo: (p ∨ q) ∧ ¬p =⇒ q ou
(p ∨ q) ∧ ¬q =⇒ p
Regra Modus Ponens: (p → q) ∧ p =⇒ q
Regra Modus Tollens: (p → q) ∧ ¬q =⇒ ¬p
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 10 / 19
Regras de Equivalência
Definição
Diz-se que uma proposição P(p,q,r,...) é logicamente equivalente ou
apenas equivalente uma proposição Q(p,q,r,...), se as tabelas-verdade
destas duas proposições são idênticas. Representado por:
P(q, r , s, ...)⇐⇒ Q(q, r , s, ...)
Propriedades
Reflexiva: P(q, r , s, ...)⇐⇒ P(q, r , s, ...)
Simétrica: Se P(q, r , s, ...)⇐⇒ Q(q, r , s, ...) então
Q(q, r , s, ...)⇐⇒ P(q, r , s, ...)
Transitiva: Se P(q, r , s, ...)⇐⇒ Q(q, r , s, ...) e
Q(q, r , s, ...)⇐⇒ R(q, r , s, ...), então P(q, r , s, ...)⇐⇒ R(q, r , s, ...)
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 11 / 19
Regras de Equivalência
Teorema
A proposição P(p,q,r,...)é equivalente a proposição Q(p,q,r,...), isto é:
P(q, r , s, ...)⇐⇒ Q(q, r , s, ...)
se e somente se a condicional:
P(q, r , s, ...)↔ Q(q, r , s, ...)
é tautologica
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 12 / 19
Regras de Equivalência
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 13 / 19
Regras de Equivalência
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 14 / 19
Regras de Equivalência
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 15 / 19
Método Dedutivo
c =⇒ p
c → p é uma tautologia
(implicação) ⇐⇒∼ c ∨ p
⇐⇒ t ∨ p
⇐⇒ t
p =⇒ t
p → t é uma tautologia
(implicação) ⇐⇒∼ p ∨ p
⇐⇒ t
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 16 / 19
Método Dedutivo
c =⇒ p
c → p é uma tautologia
(implicação) ⇐⇒∼ c ∨ p
⇐⇒ t ∨ p
⇐⇒ t
p =⇒ t
p → t é uma tautologia
(implicação) ⇐⇒∼ p ∨ p
⇐⇒ t
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 16 / 19
Método Dedutivo
c =⇒ p
c → p é uma tautologia
(implicação) ⇐⇒∼ c ∨ p
⇐⇒ t ∨ p
⇐⇒ t
p =⇒ t
p → t é uma tautologia
(implicação) ⇐⇒∼ p ∨ p
⇐⇒ t
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 16 / 19
Método Dedutivo
c =⇒ p
c → p é uma tautologia
(implicação) ⇐⇒∼ c ∨ p
⇐⇒ t ∨ p
⇐⇒ t
p =⇒ t
p → t é uma tautologia
(implicação) ⇐⇒∼ p ∨ p
⇐⇒ t
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 16 / 19
Método Dedutivo
c =⇒ p
c → p é uma tautologia
(implicação) ⇐⇒∼ c ∨ p
⇐⇒ t ∨ p
⇐⇒ t
p =⇒ t
p → t é uma tautologia
(implicação) ⇐⇒∼ p ∨ p
⇐⇒ t
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 16 / 19
Método Dedutivo
c =⇒ p
c → p é uma tautologia
(implicação) ⇐⇒∼ c ∨ p
⇐⇒ t ∨ p
⇐⇒ t
p =⇒ t
p → t é uma tautologia
(implicação) ⇐⇒∼ p ∨ p
⇐⇒ t
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 16 / 19
Método Dedutivo
c =⇒ p
c → p é uma tautologia
(implicação) ⇐⇒∼ c ∨ p
⇐⇒ t ∨ p
⇐⇒ t
p =⇒ t
p → t é uma tautologia
(implicação) ⇐⇒∼ p ∨ p
⇐⇒ t
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 16 / 19
Método Dedutivo
p ∧ q =⇒ p (Simplificação)
p ∧ q → p é uma tautologia
(implicação) ⇐⇒∼ (p ∧ q) ∨ p
(De Morgan)
⇐⇒ (∼ p∨ ∼ q) ∨ p
(Associatividade)
⇐⇒ (∼ p ∨ p)∨ ∼ q
(Tautologia) ⇐⇒ T∨ ∼ q
⇐⇒ T
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 17 / 19
Método Dedutivo
p ∧ q =⇒ p (Simplificação)
p ∧ q → p é uma tautologia
(implicação) ⇐⇒∼ (p ∧ q) ∨ p
(De Morgan)
⇐⇒ (∼ p∨ ∼ q) ∨ p
(Associatividade)
⇐⇒ (∼ p ∨ p)∨ ∼ q
(Tautologia) ⇐⇒ T∨ ∼ q
⇐⇒ T
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 17 / 19
Método Dedutivo
p ∧ q =⇒ p (Simplificação)
p ∧ q → p é uma tautologia
(implicação) ⇐⇒∼ (p ∧ q) ∨ p
(De Morgan)
⇐⇒ (∼ p∨ ∼ q) ∨ p
(Associatividade)
⇐⇒ (∼ p ∨ p)∨ ∼ q
(Tautologia) ⇐⇒ T∨ ∼ q
⇐⇒ T
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 17 / 19
Método Dedutivo
p ∧ q =⇒ p (Simplificação)
p ∧ q → p é uma tautologia
(implicação) ⇐⇒∼ (p ∧ q) ∨ p
(De Morgan)
⇐⇒ (∼ p∨ ∼ q) ∨ p
(Associatividade)
⇐⇒ (∼ p ∨ p)∨ ∼ q
(Tautologia) ⇐⇒ T∨ ∼ q
⇐⇒ T
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 17 / 19
Método Dedutivo
p ∧ q =⇒ p (Simplificação)
p ∧ q → p é uma tautologia
(implicação) ⇐⇒∼ (p ∧ q) ∨ p
(De Morgan)
⇐⇒ (∼ p∨ ∼ q) ∨ p
(Associatividade)
⇐⇒ (∼ p ∨ p)∨ ∼ q
(Tautologia) ⇐⇒ T∨ ∼ q
⇐⇒ T
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 17 / 19
Método Dedutivo
p ∧ q =⇒ p (Simplificação)
p ∧ q → p é uma tautologia
(implicação) ⇐⇒∼ (p ∧ q) ∨ p
(De Morgan)
⇐⇒ (∼ p∨ ∼ q) ∨ p
(Associatividade)
⇐⇒ (∼ p ∨ p)∨ ∼ q
(Tautologia) ⇐⇒ T∨ ∼ q
⇐⇒ T
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 17 / 19
Método Dedutivo
Adição: p =⇒ p ∨ q
Regra Modus Ponens: (p → q) ∧ p =⇒ q
Regra Modus Tollens: (p → q) ∧ ¬q =⇒ ¬p
Regra do Silogismo Disjuntivo: (p ∨ q) ∧ ¬p =⇒ q
p ∧ q =⇒ p ∨ q
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 18 / 19
The End
Renato Ramos da Silva (UFLA) Short title 5 de outubro de 2015 19 / 19
	Algebra de Boole