Conjuntos_Logica_AlgConjuntos

Prévia do material em texto

UNIVERSIDADE FEDERAL DE PELOTAS 
CENTRO DE DESENVOLVIMENTO TECNOLÓGICO 
CURSO DE CIÊNCIA DA COMPUTAÇÃO 
CURSO DE ENGENHARIA DE COMPUTAÇÃO 
 
 
Sistemas Discretos I 
Prof. Aline Brum LoretoProf. Aline Brum LoretoProf. Aline Brum LoretoProf. Aline Brum Loreto 
 
 
MATEMÁTICA DISCRETA ou SISTEMAS DISCRETOS I 
 
Introdução 
 Praticamente, qualquer estudo em Computação e Informática, teórico ou aplicado, 
exige como pré-requisito conhecimentos de diversos tópicos de Matemática. Tal fato é 
normalmente explicitado na maioria dos livros de Computação e Informática, sendo que 
alguns possuem um capítulo específico no qual tais tópicos são brevemente ou 
resumidamente introduzidos. 
 A importância da Matemática é explicitada nas Diretrizes Curriculares do MEC 
para cursos de Computação e Informática, como segue (a matéria Matemática é 
integrante da área de Formação Básica): 
 “A formação básica tem por objetivo introduzir as matérias necessárias ao 
desenvolvimento tecnológico da computação. O principal ingrediente desta área é a 
ciência da computação, que caracteriza o egresso como pertencente à área de 
computação. A maioria das matérias tecnológicas são aplicações da ciência da 
computação. São matérias de formação básica dos cursos da área de computação: a 
ciência da computação, a matemática, a física e eletricidade e a pedagogia.”(MEC 
2004) 
 Especificadamente, em relação à Matemática, o texto destaca que: 
 “A Matemática, para a área de computação, deve ser vista como uma ferramenta 
a ser usada na definição formal de conceitos computacionais (linguagem, autômatos, 
métodos, etc.). ...... 
 Considerando que a maioria dos conceitos computacionais pertence ao domínio 
do discreto, a Matemática Discreta (ou também chamada Álgebra Abstrata, Sistemas 
Discretos) é fortemente empregada. ....” 
 Uma questão importante para o entendimento do que segue é a origem do termo 
Matemática Discreta. Intuitivamente falando, qualquer sistema de computador possui 
limitações finitas em todos os seus principais aspectos como, por exemplo, tamanho da 
 2 
memória, número de instruções que pode executar, número de símbolos diferentes que 
pode tratar, etc. Assim, o estudo dos conjuntos finitos é fundamental. 
 O fato de um sistema de computador possuir limitações finitas não implica 
necessariamente uma limitação ou pré-fixação de tamanhos máximos. Por exemplo, no 
que se refere à capacidade de armazenamento, um computador pode possuir unidades 
auxiliares como discos removíveis, fitas, etc. Portanto, para um correto entendimento de 
diversos aspectos computacionais, freqüentemente não é possível pré-fixar limites, o que 
implica tratar tais questões em um contexto infinito. 
 Entretanto, qualquer conjunto de recursos computacionais, finito ou infinito, é 
contável ou discreto (em oposição ao termo contínuo), no sentido em que seus elementos 
(recursos) podem ser enumerados ou seqüenciados (segundo algum critério) de tal forma 
que não existe um elemento entre quaisquer dois elementos consecutivos da enumeração. 
Por exemplo, o conjunto dos números naturais é obviamente contável. Um importante 
contra-exemplo é o conjunto dos números reais, o qual é não-contável ou não-discreto. 
Isso significa que existem conjuntos infinitos contáveis e conjuntos infinitos não-
contáveis. 
 Assim, a Matemática Discreta possui como ênfase os estudos matemáticos 
baseados em conjuntos contáveis, finitos e infinitos. 
 (Paulo Blauth Menezes, Matemática Discreta para Computação e Informática) 
 
O que é Matemática Discreta? 
a) Grandezas físicas discretas x grandezas físicas contínuas 
Ex: Discretas: número de alunos de uma sala de aula, número de carros em um 
estacionamento; 
Contínuas: temperatura, distância percorrida, quantidade (número de litros) num tanque 
de gasolina. 
Exemplo Prático: Relógios de Pulso 
A matemática contínua corresponde aos relógios analógicos � – o tipo que separa os 
ponteiros das horas, minutos e segundos. Os ponteiros se movem suavemente ao longo do 
tempo. Do ponto de vista de um relógio analógico, entre 12:02 pm e 12:03 pm há um 
número infinito de diferentes tempos possíveis, na medida em que o ponteiro dos 
segundos percorre o mostrador. A matemática contínua estuda conceitos infinitos em seu 
objetivo, em que um objeto pode combinar-se suavemente com o próximo. O sistema dos 
números reais está no cerne da matemática contínua e – tal como o relógio -, entre dois 
números reais quaisquer, há uma infinidade de números reais. 
 
A matemática discreta é comparável a um relógio digital , em que há apenas um número 
finito possível de tempos diferentes entre 12:02 pm e 12:03 pm. Um relógio digital não 
reconhece frações de segundos. Não há tempo algum entre 12:02:03 e 12:02:04. O 
relógio salta de um instante para o próximo. Um relógio digital só pode mostrar um 
número finito de tempos diferentes, e a transição de um tempo para o próximo é bem 
 3 
definida e sem ambigüidade. Assim, como o sistema de números reais desempenha papel 
central na matemática contínua, os inteiros são o instrumento principal da matemática 
discreta. A matemática discreta é o instrumento de escolha em uma diversidade de 
aplicações, dos computadores ao planejamento de chamadas telefônicas, e das atribuições 
de pessoal à genética. 
 
 
b) Conjuntos Discretos x ContinuUm 
Um conjunto é dito discreto se for finito ou infinito enumerado (conjunto dos números 
naturais) e todos seus elementos são isoláveis. Ex: IN, Z, {1, 2, 3, 4, 5} 
 Um conjunto é dito um continuum se de modo análogo ao que ocorre com um 
intervalo, uma superfície ou um sólido, seus elementos formam uma ordenação 
ininterrupta. Ex: o intervalo [0,1]; IR 
Obs: O conjunto dos números racionais {Q} não é discreto mas também não é um 
continuUm. 
c) Matemática Discreta: 
É a parte da matemática que se restringe a objetos definidos em termo de conjuntos 
discretos. 
 Campos da Matemática Discreta: 
- Álgebra Discreta 
- Geometria Discreta 
- Estatística Discreta 
- Probabilidade Discreta. 
 
 
1- Conceitos Básicos de Teoria dos Conjuntos 
 
� Conjuntos. É uma coleção de zero ou mais objetos distintos, chamados elementos 
do conjunto os quais não possuem qualquer ordem associada. 
Exemplos: 
a) As vogais a, e, i o, u; 
b) Os dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9; 
c) Todos os brasileiros; 
d) Os números pares 0, 2, 4, 6,... . 
 
 A definição de um conjunto listando todos os seus elementos é denominada 
denotação por extensão e é dada pela lista de todos os seus elementos, sem repetição, em 
qualquer ordem (separados por vírgula) e entre chaves, como por exemplo: 
Vogais= {a, e, i, o, u} 
 4 
 A definição de um conjunto por propriedades é denominada denotação por 
compreensão como, por exemplo: 
Pares= {n׀ n é número par} 
(conjunto de todos os elementos n tal que n é número par) 
 Assim a forma geral de definição de um conjunto por propriedade é: 
{x׀ p(x)} 
de maneira que um determinado elemento a é elemento desse conjunto se a propriedade p 
é verdadeira para a, ou seja, se p(a) é verdadeira. Por exemplo, para o conjunto: 
B={x׀ x é brasileiro} 
Pelé é elemento de B e Bill Gates não é elemento de B. 
 Embora seja possível definir qualquer conjunto por compreensão, freqüentemente é 
conveniente especificar conjuntos da forma: 
Dígitos={0, 1, 2, 3,..., 9} 
Pares={0, 2, 4, 6,...} 
Nos quais os elementos omitidos podem ser facilmente deduzidos do contexto. 
 
� Pertinência. 
Se um determinado elemento a é elemento de um conjunto A, tal fato é denotado por: 
a∈A (a pertence ao conjunto A). 
 Caso contrário, afirma-se que a não pertence ao conjunto A: a∉A. 
 
Exemplos: 
a) Vogais = {a, e, i, o, u} 
a∈Vogais 
h∉Vogais 
b) B = {x׀ x é brasileiro}Pelé∈B 
 Bill Gates∉B 
 
Conjuntos Importantes 
N Conjunto do Números Naturais 
Z Conjunto dos Números Inteiros 
Q Conjunto dos Números Racionais 
I Conjunto dos Números Irracionais 
ℜℜℜℜ Conjunto dos Números Reais 
 
� Conjunto vazio: é o conjunto que não contém elementos e é representado por { } 
ou φ . 
 
 
 5 
Exemplos: 
a) O conjunto de todos os números que são simultaneamente pares e ímpares; 
b) A = {x∈R ׀ x2 + 1 = 0}. 
 
� Conjunto Unitário: é o conjunto constituído por um único elemento. 
Exemplos: 
a) O conjunto de todos os números que são simultaneamente pares e primos; 
b) A = {x∈N ׀ x + 2 = 8}. 
 
� Conjunto Universo. 
Normalmente denotado por U, contém todos os conjuntos que estão sendo considerados. 
O conjunto universo define o contexto de discussão (e, portanto, U não é um conjunto 
fixo). 
Exemplos: 
a) A = {x∈R ׀ 41 << x }, U = R , é um conjunto infinito; 
b) B = { x∈N ׀ 41 << x }, U = N, é um conjunto finito = {2, 3}. 
 
� Subconjunto. 
Um conjunto A é subconjunto de B ou, A está contido em B ou, B contém A, se todo 
elemento que pertence a A, pertence, também a B. 
 A⊆⊆⊆⊆B ou B⊇⊇⊇⊇A 
 A negação de A⊆⊆⊆⊆B é indicada por A⊆⊆⊆⊆B. 
Obs.: Nesse caso (A⊆⊆⊆⊆B ou B⊇⊇⊇⊇A) afirma-se que A é subconjunto de B. 
Simbolicamente: A⊆⊆⊆⊆B ( )( )BxAxx ∈→∈∀↔ 
 A⊆⊆⊆⊆B ( ) ( )BxAxx ∉∧∈∃↔ 
 
Observações: 
• Como B⊆⊆⊆⊆B, B é subconjunto de B, qualquer que seja o conjunto B. 
• Como ⊆φ B, φ é subconjunto de qualquer que seja o conjunto B. 
• B e φ são subconjuntos triviais de B. 
• Se A⊆⊆⊆⊆B mas existe b ∈ B tal que b ∉A, então afirma-se que A está 
contido propriamente em B, ou que A é subconjunto próprio de B, e 
denota-se por: A ⊂ B. Ou, alternativamente, que B contém propriamente 
A, denota-se por B ⊃ A. 
Exemplo: Seja B = {1, 2, 3}. 
 Subconjuntos de B = φ , {1}, {2}, {3}, {1,2}, {1, 3}, {2, 3}, {1, 2, 3} onde φ e 
{1, 2, 3} são subconjuntos triviais e {1}, {2}, {3}, {1, 2}, {1, 3} e {2, 3} são 
subconjuntos próprios. 
 
 6 
� Igualdade de Conjuntos. 
Dois conjuntos A e B dizem-se iguais se e somente se, todo elemento pertencente a um 
deles também pertence ao outro, ou seja, A⊆⊆⊆⊆B e B⊆⊆⊆⊆A. 
Simbolicamente: A = B : ( )( )BxAxx ∈↔∈∀ ou 
 A = B ABBA ⊆∧⊆↔ . 
Exemplos: 
a) {1,2,3} ={x ∈ Nx > 0 e x < 4} 
b) N = {x ∈ Zx ≥0} 
c) {1,2,3} = {3,3,3,2,2,1} 
 
 
 
 
É importante distinguir entre ⊆ e ∈. A notação x ∈A significa que x é um elemento (ou 
membro) de A. A notação A⊆B significa que todo elemento de A é também elemento de 
B. Exemplificando, considere o conjunto A={1,2,3,4}, então ∅⊆{1,2,3} é verdadeiro, 
mas ∅∈{1,2,3} é falso. 
A diferença entre ∈ e ⊂ é análoga à diferença entre x e {x}. O símbolo x se refere a um 
objeto e a notação {x} significa o conjunto cujo único elemento é x. 
Correto escrever x ∈{x}, mas não é correto escrever x = {x} ou x ⊆ {x}. 
 
Exemplos: Considere o conjunto A = {1,2,3,∅, {a}, {b,c}}. Então: 
a) {1} ∉A, {1} ⊆A 
b) ∅∈A, ∅⊆A 
c) {a} ∈A, {b,c} ∈A 
d) {1,2,3}∉A, {1,2,3}⊆A 
 
� Conjunto das Partes de um Conjunto (ou Conjunto Potência). 
A partir de um conjunto A, é o conjunto cujos elementos são todos os subconjuntos (ou 
partes) de A. Indicamos por P(A). 
Simbolicamente: P(A) = {X ׀ X⊆A} 
 
Exemplos: 
1) B = {a, b}, P(B) = {φ , {a}, {b}, {a,b}} 
2) B = φ , P(B) = {φ } 
 
Observação: Se A tem n elementos, então P(A) tem n2 elementos (subconjuntos). 
 
 
 
Obs.: Os símbolos ⊆ e ∈ possuem significados relacionados, porém diferentes. 
Não podem ser permutados! 
 7 
� Conjuntos Finitos e Infinitos 
Um conjunto pode possuir um número finito ou infinito de elementos. Informalmente, um 
conjunto é dito: 
a) Conjunto finito se pode ser denotado por extensão, ou seja, listando 
exaustivamente todos os seus elementos; 
b) Conjunto infinito, caso contrário. 
 
Exemplos: 
a) Os seguintes conjuntos são finitos: 
∅, 
{ε}, 
Vogais={a, e, i, o, u} 
Dígitos={0, 1,2, 3, 4, 5, 6, 7, 8, 9} 
A={ x ∈ N | x >0 e x< 4} 
B={x  x é brasileiro} 
 
b) Os seguintes conjuntos são infinitos: 
Z 
R 
{x ∈ Z  x ≥0} 
Pares={y  y=2x e x ∈ N} 
 
� Alfabetos, Palavras e Linguagens 
A noção de conjunto permite definir linguagem, um dos conceitos mais fundamentais 
em Computação. 
• Alfabeto: é um conjunto finito. Os elementos de um alfabeto são usualmente 
denominados de símbolos ou caracteres. 
O conjunto vazio é um alfabeto, e um conjunto infinito não é um alfabeto. 
 
• Palavra, Cadeia de Caracteres, Sentença: Uma Palavra ou Cadeia de 
Caracteres ou Sentença sobre um alfabeto é uma sequência finita de símbolos 
(do alfabeto) justapostos. 
Uma cadeia sem símbolos é uma palavra válida, e o símbolo: 
ε denota a cadeia vazia, palavra vazia ou sentença vazia; 
∑ representa um alfabeto; 
∑* denota o conjunto de todas as palavras possíveis sobre ∑. 
 
Exemplos: 
a) Os conjuntos ∅ e {a, b, c} são alfabetos; 
b) O conjunto N não é um alfabeto; 
c) ε é uma palavra sobre o alfabeto {a, b, c}; 
d) a, e, i, o, u, ai, oi, ui, e aeiou são exemplos de palavras sobre Vogais; 
e) 1 e 001 são exemplos de palavras distintas sobre Dígitos; 
f) {a,b}*= {ε, a, b, aa, ab, ba, bb, aaa,...}. 
 8 
� Linguagem Formal 
Uma Linguagem Formal, ou simplesmente Linguagem, é um conjunto de palavras sobre 
um alfabeto. 
Exemplos: Suponha o alfabeto ∑ = {a,b}. Então: 
a) O Conjunto vazio e o conjunto formado pela palavra vazia são linguagens sobre ∑, 
obviamente ∅ ≠ ε; 
 
b) O conjunto de palíndromas (palavras que tem a mesma leitura da esquerda para a 
direita e vice-versa) sobre ∑ é um exemplo de linguagem (finita); 
Palíndromos = {ε, a, b, aa, bb, aaa, aba, bab, bbb, aaaa, ....}. 
 
c) Linguagens de Programação: as linguagens de programação como Pascal, C e Java 
são linguagens sobre o alfabeto constituído por letras, dígitos e alguns símbolos 
especiais (como espaço, parênteses, pontuação, etc.). Nesse caso, cada programa na 
linguagem corresponde a uma palavra sobre o alfabeto. Ou seja, uma linguagem de 
programação é definida por todos os seus programas possíveis. Portanto, Pascal, C, 
Java, bem como qualquer linguagem de programação de propósitos gerais, são 
conjuntos infinitos. 
 
 
2- Noções de Lógica 
Algumas considerações: 
 
Lógica Matemática é básica para qualquer estudo em Computação e Informática 
e, em particular, para o estudo da Matemática Discreta (Sistemas Discretos). 
As Diretrizes Curriculares do MEC para Cursos de Computação e Informática destacam 
que: 
 
Lógica Matemática é uma ferramenta fundamental na definição de conceitos 
computacionais. 
 
E, para algumas disciplinas da Área de Formação Tecnológica, como Inteligência 
Artificial, esse texto destaca, enfaticamente que: 
Com base ao estudo da Inteligência Artificial são imprescindíveis conhecimentos de 
Lógica Matemática... 
 
Lógica permite definir a noção de teorema. Em computação, um teorema 
freqüentemente pode ser visto como um problema a ser implementado 
computacionalmente, e sua correspondente demonstração, pode ser vista como uma 
solução computacional, ou seja, um algoritmo. Adicionalmente, o algoritmo que 
soluciona o problema, prova-se, sempre funciona. 
 
Fonte: Livro de Matemática Discreta para Computação e Informática 
 Paulo Blauth Menezes 
 
 
 9 
 
Lógica 
Entende-se por Lógica Booleana ou Lógica de Boole o estudo dos princípios e métodos 
usados para distinguir sentenças verdadeiras de falsas. 
 
a) Proposição. É uma construção (sentença, frase, pensamento) à qual se pode 
atribuir juízo do tipo verdadeiro-falso. 
 
Em Lógica Matemática, a forma tradicional de tratar com a “verdade” é considerardois 
valores-verdade V e F (verdadeiro e falso, respectivamente) e estipular que as 
proposições só podem assumir esses dois valores. 
 
Para uma dada proposição p, denota-se por: V(p) o valor verdade de p. 
 
 
Exemplos: 
a) Proposições: 
Brasil é um país 
3 + 4 > 5 
7 – 1 =5 
 
Para cada uma dessas proposições, o valor verdade é: 
V(Brasil é um país) = V 
V(3 + 4>5) = V 
V(7-1=5) = F 
 
b) Não são proposições: 
Vá tomar banho. 
Que horas são? 
 
b) Conetivos Lógicos: ou operadores lógicos, são utilizados para construir 
proposições mais complexas através da composição de proposições (proposições 
compostas). 
~ : negação 
∧ : e 
∨ : ou 
→ : se... então 
↔ : se e somente se 
 Sejam p e q proposições. O valor lógico (ou valor verdade) das proposições 
compostas obtidas do uso dos conetivos, depende dos valores lógicos das proposições p 
e q. 
*Negação (~p). A negação de uma proposição é construída, introduzindo-se a palavra 
não de forma apropriada o prefixando-se a proposição por “não é fato que” (ou expressão 
equivalente). 
 10
Exemplos: 
Considere as seguintes proposições: 
a) Brasil é um país. 
b) 3 + 4 >5 
 
A negação dessas proposições é como segue, respectivamente: 
aa) Brasil não é um país. 
bb) Não é fato que 3 + 4>5. 
 
Notação: p denota uma proposição; 
 A negação de p é ¬p ou ~p a qual é lida como “não p”. 
Interpretação: 
- se p é verdadeira, então ~p é falsa; 
- se p é falsa, então ¬p é verdadeira. 
 
 
Tabela Verdade: é uma tabela que descreve os valores lógicos de uma proposição em 
termos das possíveis combinações dos valores lógicos das proposições componentes e 
dos conetivos usados. Para cada combinação de valores verdade e de conetivos, a tabela 
verdade fornece o valor verdade da expressão resultante. 
 
p ~p 
V F 
F V 
Figura1: Tabela verdade - negação 
 
 
*Conjunção (p∧ q) . Reflete uma noção de simultaneidade para se verdadeira. 
A proposição composta p ∧ q é: 
- verdadeira, apenas quando p e q são simultaneamente verdadeiras; 
- falsa, em qualquer outro caso. 
p q p∧q 
V V V 
V F F 
F V F 
F F F 
Figura 2: Tabela Verdade - conjunção 
 
Obs.: Em relação a tabela verdade acima, observamos que para expressar todas as 
combinações possíveis de valores lógicos das proposições p e q, foram necessárias 
quatro linhas. 
 
Exemplos: 
V: Windows é um sistema operacional, e Pascal é uma linguagem de programação; 
F: Windows é um sistema operacional, e Pascal é uma planilha eletrônica; 
F: Windows é um editor de texto, e Pascal é uma linguagem de programação; 
F: Windows é um editor de texto, e Pascal é uma planilha eletrônica. 
 
 11
*Disjunção (p∨q). Reflete a noção de que pelo menos uma (eventualmente duas) das 
proposições componentes deve ocorrer para que a resultante seja verdadeira. A 
proposição composta p∨q é; 
- verdadeira, quando pelo menos uma das proposições é verdadeira; 
- falsa, somente quando simultaneamente p e q são falsas. 
 
 
 
 
 
 
 Figura 3: Tabela Verdade - disjunção 
Exemplos: 
V: Windows é um sistema operacional, ou Pascal é uma linguagem de programação; 
V: Windows é um sistema operacional, ou Pascal é uma planilha eletrônica; 
V: Windows é um editor de texto, ou Pascal é uma linguagem de programação; 
F: Windows é um editor de texto, ou Pascal é uma planilha eletrônica. 
 
*Condição (p →q ). A partir de uma premissa verdadeira, obrigatoriamente deve-se 
chegar a uma conclusão verdadeira para que p→q seja verdadeira. Entretanto, partindo 
de uma premissa falsa, qualquer conclusão pode ser verdadeira. 
Lê-se: “se p então q” 
Partindo de uma premissa falsa, qualquer conclusão pode ser considerada. Assim, a 
proposição composta p→q é: 
- falsa, quando p é verdadeira e q é falsa; 
- verdadeira, caso contrário. 
p q p→q 
V V V 
V F F 
F V V 
F F V 
Figura 4: Tabela Verdade: condição 
Exemplos: 
V: se Windows é um sistema operacional, então Pascal é uma linguagem de 
programação; 
F: se Windows é um sistema operacional, então Pascal é uma planilha eletrônica; 
V: se Windows é um editor de texto, então Pascal é uma linguagem de programação; 
V: se Windows é um editor de texto, então Pascal é uma planilha eletrônica. 
 
*Bicondição (p ↔ p). Reflete a noção de condição nos dois sentidos, portanto, 
considerando a noção de condição, deve-se ter ambas verdadeiras ou ambas falsas para 
que p ↔ p seja verdadeira. 
p q p∨q 
V V V 
V F V 
F V V 
F F F 
 12
Lê-se: “p se e somente se q”. 
A noção de condição “nos dois sentidos” considera, simultaneamente: 
- sentido de “ida: p é premissa e q é conclusão; 
- sentido de “volta”: q é premissa e p é conclusão. 
 
 
 
 
 
 
Figura 5: Tabela Verdade - bicondição 
Exemplos: 
V: Windows é um sistema operacional se e somente se Pascal é uma linguagem de 
programação; 
F: Windows é um sistema operacional se e somente se Pascal é uma planilha eletrônica; 
F: Windows é um editor de texto se e somente se Pascal é uma linguagem de 
programação; 
V: Windows é um editor de texto se e somente se Pascal é uma planilha eletrônica. 
 
c)Fórmulas, Linguagem Lógica e Tabelas Verdade 
Fórmulas Lógicas ou simplesmente Fórmulas são as palavras da Linguagem Lógica, ou 
seja, uma sentença lógica corretamente construída sobre o alfabeto cujos símbolos são 
conetivos (∧, ¬, ∨, →, ↔), parênteses, identificadores (p, q, r, etc.), constantes, etc. 
Se uma fórmula contém variáveis, então esta não necessariamente possui valor verdade 
associado. Ou seja, seu valor lógico depende do valor verdade das sentenças que 
substituem as variáveis na fórmula. 
Exemplos: 
Suponha que p, q e r são sentenças variáveis. Então, são fórmulas: 
a) Os valores verdade constantes V e F 
b) p, q e r 
c) ¬p, p ∧ q, p ∨ q, p → q, p ↔ q 
d) p ∨ (¬q) 
e) (p ∧ ¬q) → F 
 
���� Atenção! Ordem de procedência dos conetivos: 
1. Conetivos entre parênteses, dos mais internos para os mais externos; 
2. Negação (¬) 
3. Conjunção (∧) e disjunção (∨) 
4. Condição (→) 
5. Bicondição (↔). 
p q p↔q 
V V V 
V F F 
F V F 
F F V 
 13
Exemplos: 
a)p ∨ (¬q) é equivalente a p ∨ ¬q 
b) (p ∧ ¬q) → F é equivalente a p ∧ ¬q → F 
 
Tabela Verdade: deve explicitar todas as combinações possíveis dos valores lógicos das 
fórmulas atômicas componentes. Observe que; 
- cada fórmula atômica não constante pode assumir dois valores lógicos: V ou F; 
- para n fórmulas atômicas (não constantes), são necessárias 2n linhas na tabela verdade 
para expressar todas as combinações possíveis de valores lógicos. 
 
Exemplos: 
Construa as tabelas verdade das seguintes fórmulas: 
a) p ∧ ¬q 
b) p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p∨ r) 
 
d)Tautologia e Contradição 
Definição: Seja w uma fórmula. Então: 
a) w é dita uma Tautologia se w é verdadeira, ou seja, se for verdadeira para todas 
as combinações possíveis de valores de sentenças variáveis; 
b) w é dita uma Contradição se w é falsa, ou seja, se for falsa para todas as 
combinações possíveis de valores de sentenças variáveis. 
 
Exemplo: Suponha p uma fórmula. Considere a tabela verdade abaixo: 
 
 
 
 Figura 6: Tabela verdade - tautologia e contradição 
a) A fórmula p ∨∨∨∨ ¬¬¬¬p é uma tautologia. 
b) A fórmula p ∧∧∧∧ ¬¬¬¬p é uma contradição. 
 
e)Implicação e Equivalência 
Os conetivos de condição e bicondição induzem as relações de implicação e de 
equivalência entre fórmulas, respectivamente. 
a) Relação de implicação: está diretamente relacionada com o conceito de teorema; 
b) Relação de equivalência: permite definir a noção de “mesmo significado” entre 
duas fórmulas (sintaticamente) diferentes. 
Relação de Implicação: Sejam p e qduas fórmulas. Então p implica q, denotado por: 
p ⇒ q 
se e somente se p → q é uma tautologia. 
p ¬¬¬¬p p ∨∨∨∨ ¬¬¬¬p p ∧∧∧∧ ¬¬¬¬p 
V F V F 
F V V F 
 14
Exemplo: Considere a tabela verdade da Figura 7. Então, valem as seguintes implicações: 
a) Adição: p ⇒ p ∨ q 
b) Simplificação: p ∧ q ⇒ p 
p q p∨q p→(p∨q) p∧q (p∧q)→p 
V V V V V V 
V F V V F V 
F V V V F V 
F F F V F V 
Figura 7: Tabela Verdade - adição e simplificação 
Relação de Equivalência: Sejam p e q duas fórmulas. Então p é equivalente a q, 
denotado por 
p ⇔ q 
se e somente se p ↔ q é uma tautologia. 
 
Exemplo: Considere a fórmula p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p∨ r) e respectiva tabela 
verdade: 
Figura 8: Tabela verdade 
Observando a tabela verdade, vale a relação de equivalência 
p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p∨ r) 
onde mostra que a distributividade do conetivo ou sobre o conetivo e é verdadeira 
sempre. 
 
Exemplos Importantes: 
 
Exemplo 1: Bicondição x Condição 
Considere a seguinte fórmula p ↔q ⇔ (p→q) ∧ (q→p) e respectiva tabela verdade: 
Figura 9: Tabela Verdade – bicondição x condição 
 
Este exemplo mostra formalmente por que a bicondição pode ser expressa por duas 
condições: ‘ida” e “volta”. 
 
 
p q r q∧r p∨(q∧r) p∨q p∨r (p∨q)∧(p∨r) p∨(q∧r)↔(p∨q)∧(p∨r) 
V V V V V V V V V 
V V F F V V V V V 
V F V F V V V V V 
V F F F V V V V V 
F V V V V V V V V 
F V F F F V F F V 
F F V F F F V F V 
F F F F F F F F V 
p q p↔q p→q q→p (p→q)∧(q→p) (p↔q)↔(p→q)∧(q→p) 
V V V V V V V 
V F F F V F V 
F V F V F F V 
F F V V V V V 
 15
 
Exemplo 2: Contraposição 
Considere a fórmula p →q ⇔ ¬q → ¬p e respectiva tabela verdade: 
 
 
 
 
 
 
 
Figura 10: Tabela Verdade – contraposição 
 
Exemplo 3: Redução ao Absurdo 
Considere a fórmula p→q ⇔ p∧ ¬q → F. Pela tabela verdade, verifica-se que a 
relação de equivalência é válida (conhecida por redução ou absurdo). 
 
 
 
 
 
 
Figura 11: Tabela Verdade – redução ao absurdo. 
 
f) Quantificadores 
 
Proposição Sobre um Conjunto 
 
Definição: Uma Proposição Sobre A é uma proposição cujo valor lógico depende do 
elemento x ∈ A considerado. 
 
Exemplos: São proposições sobre o conjunto N: 
a) n >1 
b) n! <10 
c) n+1 > n 
d) 2n é par 
Quais proposições são verdadeiras para qualquer n ∈ N? 
 
Uma proposição p a qual descreve alguma propriedade de um elemento x ∈ A é 
usualmente denotada por 
p(x). 
 
Toda proposição p sobre A determina dois conjuntos, como segue: 
a) Conjunto verdade de p 
{x ∈ A  p(x) é verdadeira} 
 
b) Conjunto falsidade de p 
{ x ∈ A  p(x) é falsa}. 
 
 
 
p q ¬p ¬q p→q ¬q→¬p p→q ↔ ¬q→ ¬p 
V V F F V V V 
V F F V F F V 
F V V F V V V 
F F V V V V V 
P q ¬q p→q p∧ ¬q p∧ ¬q →F p→q ↔ p∧ ¬q → F 
V V F V F V V 
V F V F V F V 
F V F V F V V 
F F V V F V V 
 16
Exemplos: Suponha os conjuntos N. Então: 
a) Para a proposição n >1: 
{2, 3, 4, ...} é o conjunto verdade; 
{0,1} é o conjunto falsidade; 
 
b) Para a proposição n!<10: 
{0,1,2,3} é o conjunto verdade; 
{n ∈ N n>3} é o conjunto falsidade; 
 
c) Para a proposição n + 1 >n: 
N é o conjunto verdade (é o próprio conjunto universo); 
∅ é o conjunto falsidade; 
 
d) Para a proposição “2n é ímpar”: 
∅ é o conjunto verdade; 
N é o conjunto falsidade (é o próprio conjunto universo). 
 
OBS.: Uma proposição p sobre A é uma: 
a) Tautologia se p(x) é verdadeira para qualquer x ∈ A, ou seja, o conjunto verdade 
é A; 
b) Contradição se p(x) é falsa para qualquer x ∈ A, ou seja, o conjunto falsidade é A. 
 
Exemplos: 
Suponha o conjunto universo N. Então: 
a) A fórmula n!<10 não é uma tautologia nem contradição. De fato, por exemplo: 
Para n = 0, a fórmula é verdadeira 
Para n = 4, a fórmula é falsa 
 
b) A fórmula n + 1> n é uma tautologia. De fato, o conjunto verdade é o conjunto 
universo N; 
 
c) A fórmula “2n é ímpar” é uma contradição. De fato, o conjunto falsidade é o 
próprio conjunto universo N. 
 
Quantificador 
Para uma determinada proposição p(x), é desejável quantificar os valores de x que devem 
ser considerados. Os seguintes quantificadores são usados em Lógica (suponha uma 
proposição p(x)): 
a) Quantificador universal, simbolizado por ∀, o qual, associado a uma proposição 
p(x), é denotado alternativamente como segue: 
(∀ x ∈ A) (p(x)) (∀ x∈A)p(x) ∀x∈A, p(x) 
 
b) Quantificador existencial, simbolizado por ∃, o qual associado a uma proposição 
p(x), é denotado alternativamente como segue: 
(∃x ∈A)(p(x)) (∃x ∈A) p(x) ∃x ∈A,p(x) 
 
Quando é claro sobre qual conjunto de valores a proposição está definida, uma expressão 
quantificada (∀x∈A) p(x) (respectivamente, (∃x∈A)p(x)) pode ser simplesmente 
denotada como segue, respectivamente: 
(∀x)(p(x)) (∀x)p(x) ∀x,p(x) 
(∃x)(p(x)) (∃x)p(x) ∃x, p(x) 
 17
 
Uma leitura de uma proposição quantificada (∀x∈A)p(x) (respectivamente, 
(∃x∈A)p(x)), é como segue, respectivamente: 
“qualquer x, p(x)” ou “para todo x, p(x)” 
“existe pelo menos um x tal que p(x)” ou “existe x tal que p(x)” 
 
Como a leitura induz, o valor verdade de uma proposição quantificada é como segue: 
a) (∀ x∈A)p(x) é verdadeira, se p(x) for verdadeira para todos os elementos de A; 
b) (∃x ∈A) p(x) é verdadeira, se p(x) for verdadeira para pelo menos um elemento de A. 
 
Definição: Quantificador Universal, Quantificador Existencial 
Seja p(x) uma proposição lógica sobre um conjunto A. Então: 
a) Quantificador Universal: a proposição (∀ x∈A)p(x) é: 
- verdadeira, se o conjunto verdade for igual ao conjunto A; 
- falsa, caso contrário. 
 
b) Quantificador Existencial: a proposição (∃x ∈A) p(x) é: 
- verdadeira, se o conjunto verdade for não-vazio; 
- falsa, caso contrário. 
 
 
Exemplos: 
Procure justificar o valor verdade de cada uma das seguintes proposições quantificadas: 
a) (∀ n∈ N)(n <1) é falsa 
(∃n ∈ N)(n<1) é verdadeira 
 
b) (∀ n∈ N)(n! <10) é falsa 
(∃n ∈ N)(n!<10) é verdadeira 
 
c) (∀ n∈ N)(n+1>n) é verdadeira 
(∃n ∈ N)(n+1>n) é verdadeira 
 
d) (∀ n∈ N)(2n é par) é verdadeira 
(∃n ∈ N)(2n é par) é verdadeira 
 
A noção de uma proposição p(x) sobre um conjunto pode ser generalizada, resultando em 
uma proposição p a qual descreve alguma propriedade de elementos x1 ∈ A1, x2 ∈ A2, ..., 
xn ∈ An. 
Tal proposição é usualmente denotada por: 
 
p(x1, x2, ...,xn). 
 
Cada um dos elementos x1, x2, ...,xn pode ser individualmente quantificado. Neste caso, a 
ordem dos quantificadores existencial e universal pode alterar o valor verdade da 
proposição. 
 
Por exemplo, para o conjunto universo N, vale: 
 
(∀ n) (∃m)(n <m) é verdadeira 
(∃m)(∀n)(n<m) é falsa 
 18
 
De fato: 
a) Para (∀ n) (∃m)(n <m), dado qualquer valor n, é possível encontrar (existe) pelo 
menos um m que satisfaz a desigualdade. 
Por exemplo, basta tomar m= n+1. Assim, para qualquer número natural n, vale a 
proposição n<n+1, que é verdadeira; 
 
b) A proposição (∃m)(∀n)(n<m) afirma que existe um número natural maior que 
qualquer outro. Sabe-se que tal número natural não existe. Portanto, a proposição 
é falsa. 
 
 
 
Obs.: Existe pelo menos um x Existe um único 
É comum quantificar existencialmente de forma única, ou seja, de tal forma que existe 
um elemento e este é único. Portanto, não é uma quantificação existencial usual na qual 
pode existir mais de um. Tal quantificador é usualmente simbolizado por ∃!. 
 
Exemplo: 
 (∃!n ∈ N)(n<1) é verdadeira 
 
 (∃!n ∈ N)(n!<10) é falsa 
 
 (∃!n ∈ N)(n+1>n) é falsa 
 
 (∃!n ∈ N)(2n é par) é falsa. 
 
Prova-se que o quantificador ∃! pode equivalentemente ser representado usando os 
quantificadores universal e existencial e os conetivos usuais: 
 
(∃! x) p(x) ⇔ (∃x)p(x) ∧ (∀x)(∀y)(p(x)∧p(y) → x=y)) 
 
Negação de ProposiçõesQuantificadas 
A negação de uma proposição quantificada é intuitiva. 
Suponha a seguinte proposição quantificada: 
(∀ x∈A)p(x) 
cujo valor verdade é: 
 
 (∀ x∈A)p(x) é verdadeira, se p(x) for verdadeira para todos os elementos de 
A. 
A negação significa que não é verdadeira para todos os elementos de A, ou seja, que 
existe pelo menos um x tal que não é fato que p(x), e portanto: 
 
(∃x ∈A) ¬p(x) 
 
Logo, 
¬((∀ x∈A)p(x)) ⇔ (∃x) ¬p(x) 
 
A negação de uma proposição quantificada universalmente (respectivamente, 
existencialmente) é a negação da proposição quantificada existencialmente 
(respectivamente, universalmente). 
 19
Exemplos: 
a) ¬((∀ n∈ N)(n <1)) ⇔ (∃n ∈ N) (n≥1)⇔V 
¬((∃n ∈ N)(n<1) ) ⇔ (∀ n∈ N)(n ≥1) ⇔ F 
 
b) ¬((∀ n∈ N)(n! <10)) ⇔ (∃n ∈ N)(n! ≥10)⇔ V 
¬((∃n ∈ N)(n!<10)) ⇔ (∀ n∈ N)(n!≥10)⇔ F 
 
c) ¬((∀ n∈ N)(n+1>n)) ⇔ (∃n ∈ N)(n +1≤n) ⇔ F 
¬((∃n ∈ N)(n+1>n)) ⇔ (∀ n∈ N)(n+1≤n) ⇔ F 
 
d) ¬((∀ n∈ N)(2n é par)) ⇔ (∃n ∈ N) (2n não é par) ⇔ F 
¬((∃n ∈ N)(2n é par)) ⇔ é verdadeira (∀ n∈ N)(2n não é par) ⇔ F. 
 
 
3 – Álgebra de Conjuntos 
� Operações Não Reversíveis e Reversíveis 
As operações sobre conjuntos são classificadas em reversíveis e não reversíveis. 
Embora as não reversíveis sejam as mais usuais, as reversíveis são especialmente 
importantes para Computação e Informática. 
As seguintes operações são definidas sobre conjuntos: 
a) Não Reversíveis 
- União; 
- Intersecção; 
b) Reversíveis 
- Complemento; 
- Conjunto das Partes; 
- Produto Cartesiano; 
- União Disjunta. 
Adicionalmente, é introduzida a operação de diferença, do tipo não reversível, a qual é 
derivada a partir da composição das operações complemento e intersecção. 
 
 
3.1 Operações Não Reversíveis 
 São as operações mais comuns. 
 
� União: A união de dois conjuntos A e B é constituída de todos os elementos que 
pertencem a A ou a B. 
 
 xBA {=∪ ׀ }BxAx ∈∨∈ ( )BA união 
 
Relacionando com a Lógica, a união corresponde à noção de disjunção. Ou seja, A ∪ B 
considera todos os elementos que pertencem ao conjunto A ou ao conjunto B. 
 
 
 20
Propriedades: 
Sejam os conjuntos A, B e C. 
1) AA =∪φ (Elemento Neutro) 
2) AAA =∪ (Idempotência) 
3) ABBA ∪=∪ (Comutativa) 
4) ( ) )( CBACBA ∪∪=∪∪ (Associativa) 
5) UUA =∪ (Conjunto universo) 
 
Exemplos: 
a) Suponha os conjuntos: 
Dígitos = {0,1,2,3,4,5,6,7,8,9} 
Vogais = {a, e, i ,o,u} 
Dígitos ∪ Vogais = {0,1,2,3,4,5,6,7,8,9,a,e,i,o,u} 
 
b) Suponha os conjuntos A={x ∈ N x >2} e B = {x ∈ N  x2 = x} 
A ∪ B = {0,1,3,4,5,6,...} 
 
 
� Intersecção: A intersecção de dois conjuntos A e B é constituída de todos os 
elementos que pertencem a A e a B. 
 xBA {=∩ ׀ }BxAx ∈∧∈ ( )BA ointersecçã 
 
 Se φ=∩ BA , então A e B são ditos conjuntos disjuntos, conjuntos independentes ou 
conjuntos mutuamente exclusivos. 
Relacionando com a Lógica, a intersecção corresponde à noção de conjunção. Ou seja, 
A ∩ B considera todos os elementos que pertencem ao conjunto A e ao conjunto B. 
 
Propriedades: 
Sejam os conjuntos A, B e C. 
1) φφ =∩A (Elemento Neutro) 
2) AAA =∩ (Idempotência) 
3) ABBA ∩=∩ (Comutativa) 
4) ( ) )( CBACBA ∩∩=∩∩ (Associativa) 
5) AUA =∩ (Conjunto universo) 
 
Propriedades Distributivas 
1) ( ) ( ) ( )CABACBA ∪∩∪=∩∪ (da união em relação a intersecção) 
2) ( ) ( ) ( )CABACBA ∩∪∩=∪∩ (da intersecção em relação a união) 
 
Propriedade Absorção: 
A ∩(A ∪ B) = A 
A ∪(A ∩ B) = A 
 
 21
Exemplos: 
a) Suponha os conjuntos: 
Dígitos = {0,1,2,3,4,5,6,7,8,9} 
Vogais = {a, e, i ,o,u} 
Dígitos ∩ Vogais = ∅ 
 
b) Suponha os conjuntos A={x ∈ R x >2} e B = {x ∈ N  x2 = x} 
A ∩ B = ∅ 
 
3.2 Operações Reversíveis 
Entende-se por operação reversível uma operação a partir de cujo resultado é possível 
recuperar os operandos originais. 
 
� Conjunto Complementar. Seja A um subconjunto de um conjunto U 
(isto é, A⊆ U). O conjunto complementar de A em relação a U é formado pelos 
elementos de U que não pertencem a A. Representa-se por ACU (~A ou A’). 
Simbolicamente: xACU { = ׀ AxUx ∉∧∈ }. 
A operação de complemento é uma operação unária a qual é definida em relação a um 
conjunto universo. 
Relacionando com a Lógica, o complemento corresponde à noção de negação. Ou seja, 
considera todos os elementos do universo que não pertencem ao conjunto original. 
 
Exemplos: 
1) X = {1, 2, 3, 4, 5}, A = {1, 2}, AC X = {3, 4, 5} 
2) X = { Nx ∈ ׀ x é divisível por 5} 
A = { Nx ∈ ׀ x termina por 5} 
 ~A = NxACX ∈= { ׀ x termina por 0} 
 
 
Complemento, união e Intersecção 
Suponha que U é o conjunto universo. Então, para qualquer conjunto A ⊆ U, vale: 
A ∪ ~A = U 
A ∩ ~A = ∅ 
 
Observações: 
- a união de um conjunto com o seu complemento sempre resulta no conjunto universo 
(compare com o fato de que p ∨¬p é uma tautologia); 
- a intersecção de um conjunto com o seu complemento sempre resulta no conjunto vazio 
(compare com o fato de que p ∧¬p é uma contradição). 
 
Propriedades: 
- Duplo Complemento: para um dado conjunto A ⊆ U, vale: ~~A = A. 
Esta propriedade está diretamente relacionada com a dupla negação da Lógica: 
 22
 - para um conjunto A, considera-se todos os elementos x tais que x ∈ A; 
 - para o ~A, considera-se todos os elementos x tais que x ∉ A, ou seja, tais que 
¬(x ∈ A); 
 - consequentemente, para ~~A, considera-se todos os elementos x tais que 
¬¬(x ∈ A), ou seja, tais que x ∈ A. 
 
- DeMorgan: envolve as operações de união e intersecção: 
~(A ∪ B) = ~A ∩ ~B ¬(p ∨ q) ⇔¬p ∧ ¬q 
~(A ∩ B) = ~A ∪ ~B ¬(p ∧ q) ⇔¬p ∨ ¬q 
 
Essa propriedade permite concluir que a intersecção (respectivamente, a união) pode ser 
calculada em termos das operações de complemento e de união (respectivamente, de 
intersecção): 
A ∩ B = ~(~A ∪ ~B) 
A ∪ B = ~(~A ∩ ~B). 
 
 
� Diferença. A diferença de dois conjuntos A e B é constituída de todos os 
elementos que pertencem a A e não pertencem a B. 
 xBA {=− ׀ }BxAx ∉∧∈ 
ou 
 A – B = A ∩ ~B. 
Observação: Se φ=∩ BA , então ABA =− . 
Exemplos: 
a) Suponha os conjuntos: 
Dígitos = {0,1,2,3,4,5,6,7,8,9} 
Vogais = {a, e, i ,o,u} 
Dígitos - Vogais = Dígitos 
 
b) Suponha os conjuntos A={x ∈ N x >2} e B = {x ∈ N  x2 = x} 
A – B = {3, 4, 5, 6,...} 
B – A = {0,1}. 
 
� Produto Cartesiano. Sejam A e B conjuntos. O produto cartesiano de A por B é o 
conjunto formado por todos os pares ordenados ),( ba com a∈A e b∈B. 
A×B ={(a, b)׀ a∈A e b∈B} 
 É usual denotar um produto cartesiano de um conjunto com ele mesmo como 
A×A= 2A . 
 Um par ordenado no qual a primeira componente é x e a segunda é y é denotado na 
forma 
(x, y) ou 〉〈 yx , 
 23
e não deve ser confundido com o conjunto {x, y}: em um par ordenado a ordem é 
importante, pois são distinguidas as componentes. O conceito de par ordenado pode ser 
generalizado para n-upla ordenada denotada na forma 
( )nxxxx ,...,,, 321 ou 〉〈 nxxxx ,...,,, 321 
 
Exemplos: 
Sejam A = {a}, B = {a, b} e C = {0, 1, 2}. Então: 
a) )},( ),,{( baaaBA =× 
b) })2,( ),1,( ),0( ),2,( ),1,( ),0,{( bbb,aaaCB =× 
c) )},2( ),,1( ),,0( ),,2( ),,1( ),,0{( bbbaaaBC =× 
d) )},( ),,( ),,( ),,{(2 bbabbaaaB = 
e) ),...}3,( ),2,( ),1,( ),0,{( aaaaNA =× 
f) )}2),,(( ),1),,(( ),0),,(( ),2),,(( ),1),,(( ),0),,{(()( bababaaaaaaaCBA =×× 
g) ))}2,(,( )),1,(,( )),0,(,( )),2,(,( )),1,(,( )),0,(,{()( bababaaaaaaaCBA =×× 
h) φφ=×A 
 
 Relativamente ao exemplo anterior, observe que: 
- Os conjuntos BCCB ×× e são diferentes. Portanto, a operação produto cartesiano é 
não-comutativa. 
- Os conjuntos )( e )( CBACBA ×××× são diferentes, pois as componentes de cada par 
ordenado são distintas. Logo, a operação produto cartesiano é não-associativa. 
 
Propriedade da Distributividade: 
O produto cartesiano se distribui sobre a união e sobre a intersecção. 
a) Distributividade do produto cartesiano sobre a união. 
A x (B ∪ C) = (A x B) ∪ (A x C) 
b) Distributividade do produto cartesiano sobre a intersecção. 
A x (B ∩ C) = (A x B) ∩ (A x C) 
 
Reversibilidade: 
A reversibilidade do produto cartesiano pode ser obtida como: o primeiro operando 
(respectivamente, o segundo operando) é o conjunto constituído por todos os elementos 
da primeira (respectivamente, da segunda) componente dos pares do produto cartesiano. 
 
Exemplos: Reversibilidade do Produto Cartesiano 
a) Resultante: {(a,a), (a,b)} 
Operandos: {a} e {a,b} 
b) Resultante: {(a,a), (a,b), (b,a), (b,b)} 
Operandos: {a,b} e {a,b} 
c) Resultante: {((a,a),0), ((a,a),1), ((a,a), 2), ((a,b),0), ((a,b),1), ((a,b),2)} 
Operandos: {(a,a), (a,b)} e {0,1,2}. 
 
 24
� União Disjunta: tem por finalidade distinguir elementos com uma mesma 
identificação, ou seja, um tipo de união no qual é garantido que não existem 
elementos em comum. 
 
Sejam A e B conjuntos. A União Disjunta dos conjuntos A e B, denotada por: 
A + B 
é com segue: 
A + B = { (a, A) a ∈ A} ∪ {(b, B) b ∈ B} 
A + B = {(a, 0) a ∈ A} ∪ {(b,1)b ∈ B} 
A + B = {aA  a ∈ A} ∪ {bB b ∈ B}. 
Exemplos: 
a) Suponha os conjuntos Silva={João, Maria, José} e Souza={Pedro, Ana, José}. 
Então: 
Silva+Souza={<João, Silva>, <Maria,Silva>,<José, Silva>, <Pedro, Souza>, <Ana, 
Souza>, <José, Souza>}. 
 
b) Suponha os conjuntos 
D={0,1,2,...,9} 
V={a, e, i, o ,u} 
P={0,2,4,6,...} 
Então: 
D+V = {0D, 1D, 2D, ..., 9D, aV, eV, iV, oV, uV} 
D+P ={0D, 1D, 2D, …, 9D, 0P, 2P, 4P, ….}. 
 
c) Suponha os conjuntos A={x ∈ N x >2} e B = {x ∈ N  x2 = x}. Então: 
A + B = {0B, 1B, 3A, 4A, 5A, 6A,...}. 
 
d) Considere o conjunto A= {a, b, c}. Então: 
∅ + ∅ = ∅ 
A + ∅ = {(a, A), (b, A), (c, A)} 
A + A = {(a,0), (b,0), (c,0),(a,1),(b,1),(c,1)}. 
 
Exemplos: Reversibilidade da União Disjunta 
Para cada um dos itens abaixo, é apresentado o conjunto resultante de uma união 
disjunta e os correspondentes operandos originais: 
a) Resultante: {0D, 1D, 2D, ..., 9D, aV, eV, iV, oV, uV} 
Operandos: {0,1,2,...,9} e {a, e, i, o u} 
b) Resultante: {0D, 1D, 2D, ..., 9D, 0N, 1N, 2N, 3N, ...} 
Operandos: {0,1,2,...,9} e N 
c) Resultante: ∅ 
Operandos: ∅ e ∅ 
d) Resultante: {(a,0), (b,0)} 
Operandos: {a,b} e ∅ 
 
 
 25
Representação através do Diagrama de Venn. 
 
 
 
 
 União Intersecção Diferença 
 
3.3 Relação entre lógica e Álgebra de Conjuntos 
Atenção para a relação direta entre os conetivos lógicos e as operações sobre conjuntos: 
 
Conetivo Lógico Operação sobre Conjuntos 
Negação Complemento 
Disjunção União 
Conjunção Intersecção 
 
Adicionalmente, as relações lógicas introduzidas também podem ser associadas com as 
relações sobre conjuntos: 
 
Relação Lógica Relação sobre Conjuntos 
implicação Continência 
equivalência igualdade 
 
 
Observação: A equivalência (respectivamente, igualdade de conjuntos) pode ser definida 
em termos de uma dupla implicação (respectivamente, dupla continência, ou seja, a “ida” 
e a “volta”). 
 
 
Conetivo Lógico Operação sobre Conjuntos 
Idempotência: ∧ e ∨ Idempotência: intersecção e união 
Comutativa: ∧ e ∨ Comutativa: intersecção e união 
Associativa: ∧ e ∨ Associativa: intersecção e união 
Distributiva: ∧ sobre ∨ 
 ∨ sobre ∧ 
Distributiva: intersecção sobre união 
União sobre intersecção 
Dupla negação Duplo complemento 
DeMorgan DeMorgan 
Absorção Absorção 
 
 
 
 
 
A B 
 
 
A B 
 
 
A B 
 
 
 26
Propriedade Lógica Teoria dos Conjuntos 
Idempotência p ∧ p ⇔ p 
p ∨ p ⇔ p 
A ∩ A 
A ∪ A 
Comutativa p ∧ q ⇔ q ∧ p 
p ∨ q ⇔ q ∨ p 
A ∩ B = B ∩ A 
A ∪ B = B ∪ A 
Associativa p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r 
p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r 
A ∩ (B ∩ C) = (A ∩B) ∩ C 
A ∪ (B ∪ C) = (A ∪B) ∪ C 
Distributiva p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p∧ r) 
p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p∨ r) 
A ∩ (B ∪ C) = (A ∩B)∪ (A∩ C) 
A ∪ (B ∩ C) = (A ∪B)∩(A ∪ C) 
Negação/Complemento ¬¬ p ⇔ p 
p∧ ¬p ⇔ F 
p∨ ¬p ⇔ V 
~~A = A 
A ∩ ~A = ∅ 
A ∪ ~A = U 
DeMorgan ¬(p ∨ q) ⇔ ¬p ∧ ¬q 
¬(p ∧ q) ⇔ ¬p ∨ ¬q 
~(A ∪ B) = ~A ∩ ~B 
~(A ∩ B) = ~A ∪ ~B 
Elemento Neutro p ∧ V ⇔ p 
p ∨ F ⇔ p 
A ∩ U = A 
A ∪ ∅ = A 
Elemento absorvente p ∧ F ⇔ F 
p ∨ V ⇔ V 
A ∩ ∅ = ∅ 
A ∪ U = U 
Absorção p ∧ (p ∨ q) ⇔ p 
p ∨ (p ∧ q) ⇔ p 
A ∩ (A ∪ B) = A 
A ∪ (A ∩ B) = A