nocoes

Prévia do material em texto

1
Noções e Notação
Matemática & Autômatos
Prof. Celso A. W. Santos
53A3 :: Aspectos Teóricos da Computação
celso.santos@docente.unip.br
25/02/2021
2
Aula de hoje...
� Rever alguns conceitos matemáticos importantes...
. Conjuntos, Relações e Funções
. Grafos
� Rever os conceitos de alfabetos, cadeias e linguagens...
� Rever Lógica Booleana
� Se der tempo:
. Autômatos Finitos e Linguagens Regulares
2
Aula de hoje...
� Rever alguns conceitos matemáticos importantes...
. Conjuntos, Relações e Funções
. Grafos
� Rever os conceitos de alfabetos, cadeias e linguagens...
� Rever Lógica Booleana
� Se der tempo:
. Autômatos Finitos e Linguagens Regulares
2
Aula de hoje...
� Rever alguns conceitos matemáticos importantes...
. Conjuntos, Relações e Funções
. Grafos
� Rever os conceitos de alfabetos, cadeias e linguagens...
� Rever Lógica Booleana
� Se der tempo:
. Autômatos Finitos e Linguagens Regulares
2
Aula de hoje...
� Rever alguns conceitos matemáticos importantes...
. Conjuntos, Relações e Funções
. Grafos
� Rever os conceitos de alfabetos, cadeias e linguagens...
� Rever Lógica Booleana
� Se der tempo:
. Autômatos Finitos e Linguagens Regulares
2
Aula de hoje...
� Rever alguns conceitos matemáticos importantes...
. Conjuntos, Relações e Funções
. Grafos
� Rever os conceitos de alfabetos, cadeias e linguagens...
� Rever Lógica Booleana
� Se der tempo:
. Autômatos Finitos e Linguagens Regulares
2
Aula de hoje...
� Rever alguns conceitos matemáticos importantes...
. Conjuntos, Relações e Funções
. Grafos
� Rever os conceitos de alfabetos, cadeias e linguagens...
� Rever Lógica Booleana
� Se der tempo:
. Autômatos Finitos e Linguagens Regulares
2
Aula de hoje...
� Rever alguns conceitos matemáticos importantes...
. Conjuntos, Relações e Funções
. Grafos
� Rever os conceitos de alfabetos, cadeias e linguagens...
� Rever Lógica Booleana
� Se der tempo:
. Autômatos Finitos e Linguagens Regulares
3
0.1 Noções Matemáticas e Terminologia
4
Conjuntos
Definição: Um conjunto é um agrupamento
de objetos representado como uma unidade.
� Conjuntos contém qualquer tipo de objetos, incluindo números,
símbolos, até outros conjuntos.
� Os objetos dentro de um conjunto são os seus elementos ou
membros.
� Notação clássica para descrição formal de conjuntos: { }
. Exemplo #1: S = {7, 21, 37} é o conjunto que contém os elementos
7, 21 e 57.
. Exemplo #2: Quais são os elementos do conjunto C = {0, a, b{2}}?
� Utilizamos os símbolos ∈ e 6∈ para indicar pertencimento e
não-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não se
preocupam com repetição de elementos.
� O conjunto {7, 7, 21, 57} é idêntico ao conjunto {21, 7, 57}.
4
Conjuntos
Definição: Um conjunto é um agrupamento
de objetos representado como uma unidade.
� Conjuntos contém qualquer tipo de objetos, incluindo números,
símbolos, até outros conjuntos.
� Os objetos dentro de um conjunto são os seus elementos ou
membros.
� Notação clássica para descrição formal de conjuntos: { }
. Exemplo #1: S = {7, 21, 37} é o conjunto que contém os elementos
7, 21 e 57.
. Exemplo #2: Quais são os elementos do conjunto C = {0, a, b{2}}?
� Utilizamos os símbolos ∈ e 6∈ para indicar pertencimento e
não-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não se
preocupam com repetição de elementos.
� O conjunto {7, 7, 21, 57} é idêntico ao conjunto {21, 7, 57}.
4
Conjuntos
Definição: Um conjunto é um agrupamento
de objetos representado como uma unidade.
� Conjuntos contém qualquer tipo de objetos, incluindo números,
símbolos, até outros conjuntos.
� Os objetos dentro de um conjunto são os seus elementos ou
membros.
� Notação clássica para descrição formal de conjuntos: { }
. Exemplo #1: S = {7, 21, 37} é o conjunto que contém os elementos
7, 21 e 57.
. Exemplo #2: Quais são os elementos do conjunto C = {0, a, b{2}}?
� Utilizamos os símbolos ∈ e 6∈ para indicar pertencimento e
não-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não se
preocupam com repetição de elementos.
� O conjunto {7, 7, 21, 57} é idêntico ao conjunto {21, 7, 57}.
4
Conjuntos
Definição: Um conjunto é um agrupamento
de objetos representado como uma unidade.
� Conjuntos contém qualquer tipo de objetos, incluindo números,
símbolos, até outros conjuntos.
� Os objetos dentro de um conjunto são os seus elementos ou
membros.
� Notação clássica para descrição formal de conjuntos: { }
. Exemplo #1: S = {7, 21, 37} é o conjunto que contém os elementos
7, 21 e 57.
. Exemplo #2: Quais são os elementos do conjunto C = {0, a, b{2}}?
� Utilizamos os símbolos ∈ e 6∈ para indicar pertencimento e
não-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não se
preocupam com repetição de elementos.
� O conjunto {7, 7, 21, 57} é idêntico ao conjunto {21, 7, 57}.
4
Conjuntos
Definição: Um conjunto é um agrupamento
de objetos representado como uma unidade.
� Conjuntos contém qualquer tipo de objetos, incluindo números,
símbolos, até outros conjuntos.
� Os objetos dentro de um conjunto são os seus elementos ou
membros.
� Notação clássica para descrição formal de conjuntos: { }
. Exemplo #1: S = {7, 21, 37} é o conjunto que contém os elementos
7, 21 e 57.
. Exemplo #2: Quais são os elementos do conjunto C = {0, a, b{2}}?
� Utilizamos os símbolos ∈ e 6∈ para indicar pertencimento e
não-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não se
preocupam com repetição de elementos.
� O conjunto {7, 7, 21, 57} é idêntico ao conjunto {21, 7, 57}.
4
Conjuntos
Definição: Um conjunto é um agrupamento
de objetos representado como uma unidade.
� Conjuntos contém qualquer tipo de objetos, incluindo números,
símbolos, até outros conjuntos.
� Os objetos dentro de um conjunto são os seus elementos ou
membros.
� Notação clássica para descrição formal de conjuntos: { }
. Exemplo #1: S = {7, 21, 37} é o conjunto que contém os elementos
7, 21 e 57.
. Exemplo #2: Quais são os elementos do conjunto C = {0, a, b{2}}?
� Utilizamos os símbolos ∈ e 6∈ para indicar pertencimento e
não-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não se
preocupam com repetição de elementos.
� O conjunto {7, 7, 21, 57} é idêntico ao conjunto {21, 7, 57}.
4
Conjuntos
Definição: Um conjunto é um agrupamento
de objetos representado como uma unidade.
� Conjuntos contém qualquer tipo de objetos, incluindo números,
símbolos, até outros conjuntos.
� Os objetos dentro de um conjunto são os seus elementos ou
membros.
� Notação clássica para descrição formal de conjuntos: { }
. Exemplo #1: S = {7, 21, 37} é o conjunto que contém os elementos
7, 21 e 57.
. Exemplo #2: Quais são os elementos do conjunto C = {0, a, b{2}}?
� Utilizamos os símbolos ∈ e 6∈ para indicar pertencimento e
não-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não se
preocupam com repetição de elementos.
� O conjunto {7, 7, 21, 57} é idêntico ao conjunto {21, 7, 57}.
4
Conjuntos
Definição: Um conjunto é um agrupamento
de objetos representado como uma unidade.
� Conjuntos contém qualquer tipo de objetos, incluindo números,
símbolos, até outros conjuntos.
� Os objetos dentro de um conjunto são os seus elementos ou
membros.
� Notação clássica para descrição formal de conjuntos: { }
. Exemplo #1: S = {7, 21, 37} é o conjunto que contém os elementos
7, 21 e 57.
. Exemplo #2: Quais são os elementos do conjunto C = {0, a, b{2}}?
� Utilizamos os símbolos ∈ e 6∈ para indicar pertencimento e
não-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuemordenação em seus elementos e não se
preocupam com repetição de elementos.
� O conjunto {7, 7, 21, 57} é idêntico ao conjunto {21, 7, 57}.
4
Conjuntos
Definição: Um conjunto é um agrupamento
de objetos representado como uma unidade.
� Conjuntos contém qualquer tipo de objetos, incluindo números,
símbolos, até outros conjuntos.
� Os objetos dentro de um conjunto são os seus elementos ou
membros.
� Notação clássica para descrição formal de conjuntos: { }
. Exemplo #1: S = {7, 21, 37} é o conjunto que contém os elementos
7, 21 e 57.
. Exemplo #2: Quais são os elementos do conjunto C = {0, a, b{2}}?
� Utilizamos os símbolos ∈ e 6∈ para indicar pertencimento e
não-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} /∈ S
� Conjuntos não possuem ordenação em seus elementos e não se
preocupam com repetição de elementos.
� O conjunto {7, 7, 21, 57} é idêntico ao conjunto {21, 7, 57}.
4
Conjuntos
Definição: Um conjunto é um agrupamento
de objetos representado como uma unidade.
� Conjuntos contém qualquer tipo de objetos, incluindo números,
símbolos, até outros conjuntos.
� Os objetos dentro de um conjunto são os seus elementos ou
membros.
� Notação clássica para descrição formal de conjuntos: { }
. Exemplo #1: S = {7, 21, 37} é o conjunto que contém os elementos
7, 21 e 57.
. Exemplo #2: Quais são os elementos do conjunto C = {0, a, b{2}}?
� Utilizamos os símbolos ∈ e 6∈ para indicar pertencimento e
não-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7}/∈S
� Conjuntos não possuem ordenação em seus elementos e não se
preocupam com repetição de elementos.
� O conjunto {7, 7, 21, 57} é idêntico ao conjunto {21, 7, 57}.
4
Conjuntos
Definição: Um conjunto é um agrupamento
de objetos representado como uma unidade.
� Conjuntos contém qualquer tipo de objetos, incluindo números,
símbolos, até outros conjuntos.
� Os objetos dentro de um conjunto são os seus elementos ou
membros.
� Notação clássica para descrição formal de conjuntos: { }
. Exemplo #1: S = {7, 21, 37} é o conjunto que contém os elementos
7, 21 e 57.
. Exemplo #2: Quais são os elementos do conjunto C = {0, a, b{2}}?
� Utilizamos os símbolos ∈ e 6∈ para indicar pertencimento e
não-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7}/∈S
� Conjuntos não possuem ordenação em seus elementos e não se
preocupam com repetição de elementos.
� O conjunto {7, 7, 21, 57} é idêntico ao conjunto {21, 7, 57}.
5
Conjuntos
� Dois conjuntos são iguais se e somente se seus elementos são iguais.
� Dados dois conjuntos A e B, dizemos que A é um subconjunto de
B, denotado A ⊆ B, se todo membro de A é também um membro
de B.
� Notação matemática
∀x (x ∈ A =⇒ x ∈ B)
� Um subconjunto A é dito ser próprio se A ⊆ B e A 6= B.
� Sobre o número de elementos (cardinalidade) de conjuntos:
. Um conjunto com zero elementos é chamado de conjunto vazio.
Pode ser denotado por {} ou pelo símbolo ∅.
. Um conjunto com um único elemento é chamado de singleton.
. Um conjunto pode ter tamanho infinito. Quando assim, descrevemos
o conjunto utilizando alguma regra. Por exemplo, o conjunto
(infinito) de números naturais é escrito como:
N = {1, 2, 3, . . .}
5
Conjuntos
� Dois conjuntos são iguais se e somente se seus elementos são iguais.
� Dados dois conjuntos A e B, dizemos que A é um subconjunto de
B, denotado A ⊆ B, se todo membro de A é também um membro
de B.
� Notação matemática
∀x (x ∈ A =⇒ x ∈ B)
� Um subconjunto A é dito ser próprio se A ⊆ B e A 6= B.
� Sobre o número de elementos (cardinalidade) de conjuntos:
. Um conjunto com zero elementos é chamado de conjunto vazio.
Pode ser denotado por {} ou pelo símbolo ∅.
. Um conjunto com um único elemento é chamado de singleton.
. Um conjunto pode ter tamanho infinito. Quando assim, descrevemos
o conjunto utilizando alguma regra. Por exemplo, o conjunto
(infinito) de números naturais é escrito como:
N = {1, 2, 3, . . .}
5
Conjuntos
� Dois conjuntos são iguais se e somente se seus elementos são iguais.
� Dados dois conjuntos A e B, dizemos que A é um subconjunto de
B, denotado A ⊆ B, se todo membro de A é também um membro
de B.
� Notação matemática
∀x (x ∈ A =⇒ x ∈ B)
� Um subconjunto A é dito ser próprio se A ⊆ B e A 6= B.
� Sobre o número de elementos (cardinalidade) de conjuntos:
. Um conjunto com zero elementos é chamado de conjunto vazio.
Pode ser denotado por {} ou pelo símbolo ∅.
. Um conjunto com um único elemento é chamado de singleton.
. Um conjunto pode ter tamanho infinito. Quando assim, descrevemos
o conjunto utilizando alguma regra. Por exemplo, o conjunto
(infinito) de números naturais é escrito como:
N = {1, 2, 3, . . .}
5
Conjuntos
� Dois conjuntos são iguais se e somente se seus elementos são iguais.
� Dados dois conjuntos A e B, dizemos que A é um subconjunto de
B, denotado A ⊆ B, se todo membro de A é também um membro
de B.
� Notação matemática
∀x (x ∈ A =⇒ x ∈ B)
� Um subconjunto A é dito ser próprio se A ⊆ B e A 6= B.
� Sobre o número de elementos (cardinalidade) de conjuntos:
. Um conjunto com zero elementos é chamado de conjunto vazio.
Pode ser denotado por {} ou pelo símbolo ∅.
. Um conjunto com um único elemento é chamado de singleton.
. Um conjunto pode ter tamanho infinito. Quando assim, descrevemos
o conjunto utilizando alguma regra. Por exemplo, o conjunto
(infinito) de números naturais é escrito como:
N = {1, 2, 3, . . .}
5
Conjuntos
� Dois conjuntos são iguais se e somente se seus elementos são iguais.
� Dados dois conjuntos A e B, dizemos que A é um subconjunto de
B, denotado A ⊆ B, se todo membro de A é também um membro
de B.
� Notação matemática
∀x (x ∈ A =⇒ x ∈ B)
� Um subconjunto A é dito ser próprio se A ⊆ B e A 6= B.
� Sobre o número de elementos (cardinalidade) de conjuntos:
. Um conjunto com zero elementos é chamado de conjunto vazio.
Pode ser denotado por {} ou pelo símbolo ∅.
. Um conjunto com um único elemento é chamado de singleton.
. Um conjunto pode ter tamanho infinito. Quando assim, descrevemos
o conjunto utilizando alguma regra. Por exemplo, o conjunto
(infinito) de números naturais é escrito como:
N = {1, 2, 3, . . .}
5
Conjuntos
� Dois conjuntos são iguais se e somente se seus elementos são iguais.
� Dados dois conjuntos A e B, dizemos que A é um subconjunto de
B, denotado A ⊆ B, se todo membro de A é também um membro
de B.
� Notação matemática
∀x (x ∈ A =⇒ x ∈ B)
� Um subconjunto A é dito ser próprio se A ⊆ B e A 6= B.
� Sobre o número de elementos (cardinalidade) de conjuntos:
. Um conjunto com zero elementos é chamado de conjunto vazio.
Pode ser denotado por {} ou pelo símbolo ∅.
. Um conjunto com um único elemento é chamado de singleton.
. Um conjunto pode ter tamanho infinito. Quando assim, descrevemos
o conjunto utilizando alguma regra. Por exemplo, o conjunto
(infinito) de números naturais é escrito como:
N = {1, 2, 3, . . .}
5
Conjuntos
� Dois conjuntos são iguais se e somente se seus elementos são iguais.
� Dados dois conjuntos A e B, dizemos que A é um subconjunto de
B, denotado A ⊆ B, se todo membro de A é também um membro
de B.
� Notação matemática
∀x (x ∈ A =⇒ x ∈ B)
� Um subconjunto A é dito ser próprio se A ⊆ B e A 6= B.
� Sobre o número de elementos (cardinalidade) de conjuntos:
. Um conjunto com zero elementos é chamado de conjunto vazio.
Pode ser denotado por {} ou pelo símbolo ∅.
. Um conjunto com um único elemento é chamado de singleton.
. Um conjunto pode ter tamanho infinito. Quando assim, descrevemos
o conjunto utilizando alguma regra. Por exemplo, o conjunto
(infinito) de números naturais é escrito como:
N = {1, 2, 3, . . .}
5
Conjuntos
� Dois conjuntos são iguais se e somente se seus elementos são iguais.
� Dados dois conjuntos A e B, dizemos que A é um subconjunto de
B, denotado A ⊆ B, se todo membro de A é também um membro
de B.
� Notação matemática
∀x (x ∈ A =⇒ x ∈ B)
� Um subconjunto A é dito ser próprio se A ⊆ B e A 6= B.
� Sobre o número de elementos (cardinalidade) de conjuntos:
. Um conjunto comzero elementos é chamado de conjunto vazio.
Pode ser denotado por {} ou pelo símbolo ∅.
. Um conjunto com um único elemento é chamado de singleton.
. Um conjunto pode ter tamanho infinito. Quando assim, descrevemos
o conjunto utilizando alguma regra. Por exemplo, o conjunto
(infinito) de números naturais é escrito como:
N = {1, 2, 3, . . .}
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
Start-t
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
Start-t
total
transportar
teste
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
Start-l
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
Start-l
lápis
leite
leão
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
Start-t
total
transportar
teste
Start-l
lápis
leite
leão
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
End-e
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
End-e
coiote
peste
elege
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
Start-t End-e
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
Start-t
teste
End-e
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
Start-t
total
transportar
teste
End-e
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
Start-t
total
transportar
teste
Start-lEnd-e
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
Start-t
total
transportar
teste
Start-l
leite
End-e
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar um
conceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
Start-t
total
transportar
teste
Start-l
lápisleite
leão
End-e
7
Operações em Conjuntos
� Dados dois conjuntos A e B
. A união de A e B, denotado por A ∪B, é o conjunto obtido
combinando todos os elementos de A e de B em um único conjunto.
. A interseção de A e B, denotada por A ∩B, é o conjunto que
contém os elementos que pertencem a A e a B.
. O complemento de um conjunto A, denotado por Ā, é o conjunto
que contém todos os elementos∗ que não estão em A.
∗Dentro de um mesmo domínio
7
Operações em Conjuntos
� Dados dois conjuntos A e B
. A união de A e B, denotado por A ∪B, é o conjunto obtido
combinando todos os elementos de A e de B em um único conjunto.
. A interseção de A e B, denotada por A ∩B, é o conjunto que
contém os elementos que pertencem a A e a B.
. O complemento de um conjunto A, denotado por Ā, é o conjunto
que contém todos os elementos∗ que não estão em A.
∗Dentro de um mesmo domínio
7
Operações em Conjuntos
� Dados dois conjuntos A e B
. A união de A e B, denotado por A ∪B, é o conjunto obtido
combinando todos os elementos de A e de B em um único conjunto.
. A interseção de A e B, denotada por A ∩B, é o conjunto que
contém os elementos que pertencem a A e a B.
. O complemento de um conjunto A, denotado por Ā, é o conjunto
que contém todos os elementos∗ que não estão em A.
∗Dentro de um mesmo domínio
7
Operações em Conjuntos
� Dados dois conjuntos A e B
. A união de A e B, denotado por A ∪B, é o conjunto obtido
combinando todos os elementos de A e de B em um único conjunto.
. A interseção de A e B, denotada por A ∩B, é o conjunto que
contém os elementos que pertencem a A e a B.
. O complemento de um conjunto A, denotado por Ā, é o conjunto
que contém todos os elementos∗ que não estão em A.
∗Dentro de um mesmo domínio
7
Operações em Conjuntos
� Dados dois conjuntos A e B
. A união de A e B, denotado por A ∪B, é o conjunto obtido
combinando todos os elementos de A e de B em um único conjunto.
. A interseção de A e B, denotada por A ∩B, é o conjunto que
contém os elementos que pertencem a A e a B.
. O complemento de um conjunto A, denotado por Ā, é o conjunto
que contém todos os elementos∗ que não estão em A.
∗Dentro de um mesmo domínio
8
Funções
� Dados dois conjuntos A e B, o produto cartesiano A×B é o
conjunto contendo todos os pares ordenados, cujo primeiro elemento
é um membro do conjunto A e o segundo elemento é um membro
do conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produto
cartesiano entre A e B é:
A×B = {(1, x), (1, y), (1, z),
(2, x), (2, y), (2, z)}
� Vamos pegar um tipo específico de subconjunto do produto
cartesiano. Seja f ⊆ A×B o seguinte conjunto:
f = {(1, x), (2, z)}.
� Esse conjunto f tem algumas propriedades:
. Todo elemento de A possui um par em f .
. Não existe nenhum elemento em A que possui dois pares diferentes
em f .
8
Funções
� Dados dois conjuntos A e B, o produto cartesiano A×B é o
conjunto contendo todos os pares ordenados, cujo primeiro elemento
é um membro do conjunto A e o segundo elemento é um membro
do conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produto
cartesiano entre A e B é:
A×B = {(1, x), (1, y), (1, z),
(2, x), (2, y), (2, z)}
� Vamos pegar um tipo específico de subconjunto do produto
cartesiano. Seja f ⊆ A×B o seguinte conjunto:
f = {(1, x), (2, z)}.
� Esse conjunto f tem algumas propriedades:
. Todo elemento de A possui um par em f .
. Não existe nenhum elemento em A que possui dois pares diferentes
em f .
8
Funções
� Dados dois conjuntos A e B, o produto cartesiano A×B é o
conjunto contendo todos os pares ordenados, cujo primeiro elemento
é um membro do conjunto A e o segundo elemento é um membro
do conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produto
cartesiano entre A e B é:
A×B = {(1, x), (1, y), (1, z),
(2, x), (2, y), (2, z)}
� Vamos pegar um tipo específico de subconjunto do produto
cartesiano. Seja f ⊆ A×B o seguinte conjunto:
f = {(1, x), (2, z)}.
� Esse conjunto f tem algumas propriedades:
. Todo elemento de A possui um par em f .
. Não existe nenhum elemento em A que possui dois pares diferentes
em f .
8
Funções
� Dados dois conjuntos A e B, o produto cartesiano A×B é o
conjunto contendo todos os pares ordenados, cujo primeiro elemento
é um membro do conjunto A e o segundo elemento é um membro
do conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produto
cartesiano entre A e B é:
A×B = {(1, x), (1, y), (1, z),
(2, x), (2, y), (2, z)}
� Vamos pegar um tipo específico de subconjunto do produto
cartesiano. Seja f ⊆ A×B o seguinte conjunto:
f = {(1, x), (2, z)}.
� Esse conjunto f tem algumas propriedades:
. Todoelemento de A possui um par em f .
. Não existe nenhum elemento em A que possui dois pares diferentes
em f .
8
Funções
� Dados dois conjuntos A e B, o produto cartesiano A×B é o
conjunto contendo todos os pares ordenados, cujo primeiro elemento
é um membro do conjunto A e o segundo elemento é um membro
do conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produto
cartesiano entre A e B é:
A×B = {(1, x), (1, y), (1, z),
(2, x), (2, y), (2, z)}
� Vamos pegar um tipo específico de subconjunto do produto
cartesiano. Seja f ⊆ A×B o seguinte conjunto:
f = {(1, x), (2, z)}.
� Esse conjunto f tem algumas propriedades:
. Todo elemento de A possui um par em f .
. Não existe nenhum elemento em A que possui dois pares diferentes
em f .
8
Funções
� Dados dois conjuntos A e B, o produto cartesiano A×B é o
conjunto contendo todos os pares ordenados, cujo primeiro elemento
é um membro do conjunto A e o segundo elemento é um membro
do conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produto
cartesiano entre A e B é:
A×B = {(1, x), (1, y), (1, z),
(2, x), (2, y), (2, z)}
� Vamos pegar um tipo específico de subconjunto do produto
cartesiano. Seja f ⊆ A×B o seguinte conjunto:
f = {(1, x), (2, z)}.
� Esse conjunto f tem algumas propriedades:
. Todo elemento de A possui um par em f .
. Não existe nenhum elemento em A que possui dois pares diferentes
em f .
8
Funções
� Dados dois conjuntos A e B, o produto cartesiano A×B é o
conjunto contendo todos os pares ordenados, cujo primeiro elemento
é um membro do conjunto A e o segundo elemento é um membro
do conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produto
cartesiano entre A e B é:
A×B = {(1, x), (1, y), (1, z),
(2, x), (2, y), (2, z)}
� Vamos pegar um tipo específico de subconjunto do produto
cartesiano. Seja f ⊆ A×B o seguinte conjunto:
f = {(1, x), (2, z)}.
� Esse conjunto f tem algumas propriedades:
. Todo elemento de A possui um par em f .
. Não existe nenhum elemento em A que possui dois pares diferentes
em f .
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada por
f : A→ B.
. Dizemos que A é o domínio de f .
. B é o contradomínio.
. A imagem de f é o conjunto de valores b ∈ B tal que existe
(a, b) ∈ f
. Para um par (a, b) ∈ f , podemos escrever f(a) = b.
� Exemplos
1 f : {0, 1, 2, 3, 4} → {0, 1, 2, 3, 4}
n f(n)
0 1
1 2
2 3
3 4
4 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada por
f : A→ B.
. Dizemos que A é o domínio de f .
. B é o contradomínio.
. A imagem de f é o conjunto de valores b ∈ B tal que existe
(a, b) ∈ f
. Para um par (a, b) ∈ f , podemos escrever f(a) = b.
� Exemplos
1 f : {0, 1, 2, 3, 4} → {0, 1, 2, 3, 4}
n f(n)
0 1
1 2
2 3
3 4
4 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada por
f : A→ B.
. Dizemos que A é o domínio de f .
. B é o contradomínio.
. A imagem de f é o conjunto de valores b ∈ B tal que existe
(a, b) ∈ f
. Para um par (a, b) ∈ f , podemos escrever f(a) = b.
� Exemplos
1 f : {0, 1, 2, 3, 4} → {0, 1, 2, 3, 4}
n f(n)
0 1
1 2
2 3
3 4
4 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada por
f : A→ B.
. Dizemos que A é o domínio de f .
. B é o contradomínio.
. A imagem de f é o conjunto de valores b ∈ B tal que existe
(a, b) ∈ f
. Para um par (a, b) ∈ f , podemos escrever f(a) = b.
� Exemplos
1 f : {0, 1, 2, 3, 4} → {0, 1, 2, 3, 4}
n f(n)
0 1
1 2
2 3
3 4
4 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada por
f : A→ B.
. Dizemos que A é o domínio de f .
. B é o contradomínio.
. A imagem de f é o conjunto de valores b ∈ B tal que existe
(a, b) ∈ f
. Para um par (a, b) ∈ f , podemos escrever f(a) = b.
� Exemplos
1 f : {0, 1, 2, 3, 4} → {0, 1, 2, 3, 4}
n f(n)
0 1
1 2
2 3
3 4
4 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada por
f : A→ B.
. Dizemos que A é o domínio de f .
. B é o contradomínio.
. A imagem de f é o conjunto de valores b ∈ B tal que existe
(a, b) ∈ f
. Para um par (a, b) ∈ f , podemos escrever f(a) = b.
� Exemplos
1 f : {0, 1, 2, 3, 4} → {0, 1, 2, 3, 4}
n f(n)
0 1
1 2
2 3
3 4
4 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada por
f : A→ B.
. Dizemos que A é o domínio de f .
. B é o contradomínio.
. A imagem de f é o conjunto de valores b ∈ B tal que existe
(a, b) ∈ f
. Para um par (a, b) ∈ f , podemos escrever f(a) = b.
� Exemplos
1 f : {0, 1, 2, 3, 4} → {0, 1, 2, 3, 4}
n f(n)
0 1
1 2
2 3
3 4
4 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada por
f : A→ B.
. Dizemos que A é o domínio de f .
. B é o contradomínio.
. A imagem de f é o conjunto de valores b ∈ B tal que existe
(a, b) ∈ f
. Para um par (a, b) ∈ f , podemos escrever f(a) = b.
� Exemplos
1 f : {0, 1, 2, 3, 4} → {0, 1, 2, 3, 4}
n f(n)
0 1
1 2
2 3
3 4
4 0
10
Funções
� Mais exemplos
2 g : Z4 × Z4 → Z4
g 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 1
– Qual é o domínio da função g?
– Qual é o contradomínio da função g?
– Qual é o valor de g(1, 2)?
– Alguém consegue enxergar o que a função g calcula?
3 Vamos tentar definir uma função Ganha, cujo domínio e
contradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos
2 g : Z4 × Z4 → Z4
g 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 1
– Qual é o domínio da função g?
– Qual é o contradomínio da função g?
– Qual é o valor de g(1, 2)?
– Alguém consegue enxergar o que a função g calcula?
3 Vamos tentar definir uma função Ganha, cujo domínio e
contradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos
2 g : Z4 × Z4 → Z4
g 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 1
– Qual é o domínio da função g?
– Qual é o contradomínio da função g?
– Qual é o valor de g(1, 2)?
– Alguém consegue enxergar o que a função g calcula?
3 Vamos tentar definir uma função Ganha, cujo domínio e
contradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos
2 g : Z4 × Z4 → Z4
g 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 1
– Qual é o domínio da função g?
– Qual é o contradomínio da função g?
– Qual é o valor de g(1, 2)?
– Alguém consegue enxergar o que a função g calcula?
3 Vamos tentar definir uma função Ganha, cujo domínio e
contradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos
2 g : Z4 × Z4 → Z4
g 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 1
– Qual é o domínio da função g? Z4 × Z4
– Qual é o contradomínio da função g?
– Qual é o valor de g(1, 2)?
– Alguém consegue enxergar o que a função g calcula?
3 Vamos tentar definir uma função Ganha, cujo domínio e
contradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos
2 g : Z4 × Z4 → Z4
g 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 1
– Qual é o domínio da função g? Z4 × Z4
– Qual é o contradomínio da função g?
– Qual é o valor de g(1, 2)?
– Alguém consegue enxergar o que a função g calcula?
3 Vamos tentar definir uma função Ganha, cujo domínio e
contradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos
2 g : Z4 × Z4 → Z4
g 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 1
– Qual é o domínio da função g? Z4 × Z4
– Qual é o contradomínio da função g? Z4
– Qual é o valor de g(1, 2)?
– Alguém consegue enxergar o que a função g calcula?
3 Vamos tentar definir uma função Ganha, cujo domínio e
contradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos
2 g : Z4 × Z4 → Z4
g 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 1
– Qual é o domínio da função g? Z4 × Z4
– Qual é o contradomínio da função g? Z4
– Qual é o valor de g(1, 2)?
– Alguém consegue enxergar o que a função g calcula?
3 Vamos tentar definir uma função Ganha, cujo domínio e
contradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos
2 g : Z4 × Z4 → Z4
g 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 1
– Qual é o domínio da função g? Z4 × Z4
– Qual é o contradomínioda função g? Z4
– Qual é o valor de g(1, 2)?
– Alguém consegue enxergar o que a função g calcula?
3 Vamos tentar definir uma função Ganha, cujo domínio e
contradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos
2 g : Z4 × Z4 → Z4
g 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 1
– Qual é o domínio da função g? Z4 × Z4
– Qual é o contradomínio da função g? Z4
– Qual é o valor de g(1, 2)?
– Alguém consegue enxergar o que a função g calcula?
3 Vamos tentar definir uma função Ganha, cujo domínio e
contradomínio são o conjunto {Pedra, Papel, Tesoura}.
11
Funções
� Mais exemplos:
Ganha Pedra Papel Tesoura
Pedra
Papel
Tesoura
Pedra
Papel
Tesoura
� Funções cujo domínio e contradomínio são o mesmo conjunto
podem ser visualizadas usando grafos!
11
Funções
� Mais exemplos:
Ganha Pedra Papel Tesoura
Pedra
Papel
Tesoura
Pedra
Papel
Tesoura
� Funções cujo domínio e contradomínio são o mesmo conjunto
podem ser visualizadas usando grafos!
11
Funções
� Mais exemplos:
Ganha Pedra Papel Tesoura
Pedra
Papel
Tesoura
Pedra
Papel
Tesoura
� Funções cujo domínio e contradomínio são o mesmo conjunto
podem ser visualizadas usando grafos!
11
Funções
� Mais exemplos:
Ganha Pedra Papel Tesoura
Pedra
Papel
Tesoura
Pedra
Papel
Tesoura
� Funções cujo domínio e contradomínio são o mesmo conjunto
podem ser visualizadas usando grafos!
11
Funções
� Mais exemplos:
Ganha Pedra Papel Tesoura
Pedra
Papel
Tesoura
Pedra
Papel
Tesoura
� Funções cujo domínio e contradomínio são o mesmo conjunto
podem ser visualizadas usando grafos!
12
0.2 Grafos
13
Grafos
� Um grafo G = (V, E) é uma estrutura de dados composta por dois
conjuntos: V , um conjunto de vértices, e E, um conjunto de arestas.
1
2
3 4
5
� Um grafo é direcionado se existe uma ordem nos pares de vértices
que definem as arestas.
13
Grafos
� Um grafo G = (V, E) é uma estrutura de dados composta por dois
conjuntos: V , um conjunto de vértices, e E, um conjunto de arestas.
1
2
3 4
5
� Um grafo é direcionado se existe uma ordem nos pares de vértices
que definem as arestas.
13
Grafos
� Um grafo G = (V, E) é uma estrutura de dados composta por dois
conjuntos: V , um conjunto de vértices, e E, um conjunto de arestas.
1
2
3 4
5
� Um grafo é direcionado se existe uma ordem nos pares de vértices
que definem as arestas.
13
Grafos
� Um grafo G = (V, E) é uma estrutura de dados composta por dois
conjuntos: V , um conjunto de vértices, e E, um conjunto de arestas.
1
2
3 4
5
� Um grafo é direcionado se existe uma ordem nos pares de vértices
que definem as arestas.
13
Grafos
� Um grafo G = (V, E) é uma estrutura de dados composta por dois
conjuntos: V , um conjunto de vértices, e E, um conjunto de arestas.
1
2
3 4
5
� Um grafo é direcionado se existe uma ordem nos pares de vértices
que definem as arestas.
14
Mais definições :: Grafos
� O grau de um vértice é o número de vezes que este vértice é
extremo de arestas.
� Um caminho em um grafo G é uma sequência de vértices
conectados por arestas, sem repetição de vértices.
� Um ciclo no grafo é um caminho fechado, onde o último e o
primeiro vértice são o mesmo.
� Um grafo é conexo se existe um caminho entre todo par de vértices
de G.
� Uma árvore é um grafo conexo sem ciclos.
14
Mais definições :: Grafos
� O grau de um vértice é o número de vezes que este vértice é
extremo de arestas.
� Um caminho em um grafo G é uma sequência de vértices
conectados por arestas, sem repetição de vértices.
� Um ciclo no grafo é um caminho fechado, onde o último e o
primeiro vértice são o mesmo.
� Um grafo é conexo se existe um caminho entre todo par de vértices
de G.
� Uma árvore é um grafo conexo sem ciclos.
14
Mais definições :: Grafos
� O grau de um vértice é o número de vezes que este vértice é
extremo de arestas.
� Um caminho em um grafo G é uma sequência de vértices
conectados por arestas, sem repetição de vértices.
� Um ciclo no grafo é um caminho fechado, onde o último e o
primeiro vértice são o mesmo.
� Um grafo é conexo se existe um caminho entre todo par de vértices
de G.
� Uma árvore é um grafo conexo sem ciclos.
14
Mais definições :: Grafos
� O grau de um vértice é o número de vezes que este vértice é
extremo de arestas.
� Um caminho em um grafo G é uma sequência de vértices
conectados por arestas, sem repetição de vértices.
� Um ciclo no grafo é um caminho fechado, onde o último e o
primeiro vértice são o mesmo.
� Um grafo é conexo se existe um caminho entre todo par de vértices
de G.
� Uma árvore é um grafo conexo sem ciclos.
14
Mais definições :: Grafos
� O grau de um vértice é o número de vezes que este vértice é
extremo de arestas.
� Um caminho em um grafo G é uma sequência de vértices
conectados por arestas, sem repetição de vértices.
� Um ciclo no grafo é um caminho fechado, onde o último e o
primeiro vértice são o mesmo.
� Um grafo é conexo se existe um caminho entre todo par de vértices
de G.
� Uma árvore é um grafo conexo sem ciclos.
15
0.3 Alfabetos, Cadeias e Linguagens
16
Alfabetos
� “Cadeias”, ou strings, de caracteres são fundamentais na ciência da
computação.
� Não somente porque elas são um tipo de dados presente na maioria
das linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modelado
utilizando strings de caracteres!
� Um alfabeto é um conjunto finito não vazio de símbolos; estes
símbolos podem ser “qualquer coisa”.
� Usualmente, denotamos um alfabeto com a letra grega sigma
maiúsculo: Σ
� Exemplos de alfabetos:
. Σ1 = {0, 1}
. Σ2 = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}
. Σ3 = {0, 1, x, y, z}
16
Alfabetos
� “Cadeias”, ou strings, de caracteres são fundamentais na ciência da
computação.
� Não somente porque elas são um tipo de dados presente na maioria
das linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modelado
utilizando strings de caracteres!
� Um alfabeto é um conjunto finito não vazio de símbolos; estes
símbolos podem ser “qualquer coisa”.
� Usualmente, denotamos um alfabeto com a letra grega sigma
maiúsculo: Σ
� Exemplos de alfabetos:
. Σ1 = {0, 1}
. Σ2 = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}
. Σ3 = {0, 1, x, y, z}
16
Alfabetos
� “Cadeias”, ou strings, de caracteres são fundamentais na ciência da
computação.
� Não somente porque elas são um tipo de dados presente na maioria
das linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modelado
utilizando strings de caracteres!
� Um alfabeto é um conjunto finito não vazio de símbolos; estes
símbolos podem ser “qualquer coisa”.
� Usualmente, denotamos um alfabeto com a letra grega sigma
maiúsculo: Σ
� Exemplos de alfabetos:
. Σ1 = {0, 1}
. Σ2 = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}
. Σ3 = {0, 1, x, y, z}
16
Alfabetos
� “Cadeias”, ou strings, de caracteres são fundamentais na ciência da
computação.
� Não somente porque elas são um tipo de dados presente na maioria
das linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modelado
utilizando strings de caracteres!
� Um alfabeto é um conjunto finito não vazio de símbolos; estes
símbolos podem ser “qualquer coisa”.
� Usualmente, denotamos um alfabeto com a letra grega sigma
maiúsculo: Σ
� Exemplos de alfabetos:
. Σ1 = {0, 1}
. Σ2 = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}
. Σ3 = {0, 1, x, y, z}
16
Alfabetos
� “Cadeias”, ou strings, de caracteres são fundamentais na ciência da
computação.
� Não somente porque elas são um tipo de dados presente na maioria
das linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modelado
utilizando strings de caracteres!
� Um alfabeto é um conjunto finito não vazio de símbolos; estessímbolos podem ser “qualquer coisa”.
� Usualmente, denotamos um alfabeto com a letra grega sigma
maiúsculo: Σ
� Exemplos de alfabetos:
. Σ1 = {0, 1}
. Σ2 = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}
. Σ3 = {0, 1, x, y, z}
16
Alfabetos
� “Cadeias”, ou strings, de caracteres são fundamentais na ciência da
computação.
� Não somente porque elas são um tipo de dados presente na maioria
das linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modelado
utilizando strings de caracteres!
� Um alfabeto é um conjunto finito não vazio de símbolos; estes
símbolos podem ser “qualquer coisa”.
� Usualmente, denotamos um alfabeto com a letra grega sigma
maiúsculo: Σ
� Exemplos de alfabetos:
. Σ1 = {0, 1}
. Σ2 = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}
. Σ3 = {0, 1, x, y, z}
16
Alfabetos
� “Cadeias”, ou strings, de caracteres são fundamentais na ciência da
computação.
� Não somente porque elas são um tipo de dados presente na maioria
das linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modelado
utilizando strings de caracteres!
� Um alfabeto é um conjunto finito não vazio de símbolos; estes
símbolos podem ser “qualquer coisa”.
� Usualmente, denotamos um alfabeto com a letra grega sigma
maiúsculo: Σ
� Exemplos de alfabetos:
. Σ1 = {0, 1}
. Σ2 = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}
. Σ3 = {0, 1, x, y, z}
16
Alfabetos
� “Cadeias”, ou strings, de caracteres são fundamentais na ciência da
computação.
� Não somente porque elas são um tipo de dados presente na maioria
das linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modelado
utilizando strings de caracteres!
� Um alfabeto é um conjunto finito não vazio de símbolos; estes
símbolos podem ser “qualquer coisa”.
� Usualmente, denotamos um alfabeto com a letra grega sigma
maiúsculo: Σ
� Exemplos de alfabetos:
. Σ1 = {0, 1}
. Σ2 = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}
. Σ3 = {0, 1, x, y, z}
16
Alfabetos
� “Cadeias”, ou strings, de caracteres são fundamentais na ciência da
computação.
� Não somente porque elas são um tipo de dados presente na maioria
das linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modelado
utilizando strings de caracteres!
� Um alfabeto é um conjunto finito não vazio de símbolos; estes
símbolos podem ser “qualquer coisa”.
� Usualmente, denotamos um alfabeto com a letra grega sigma
maiúsculo: Σ
� Exemplos de alfabetos:
. Σ1 = {0, 1}
. Σ2 = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}
. Σ3 = {0, 1, x, y, z}
17
Cadeias
� Uma string sobre um alfabeto Σ é uma sequência finita de símbolos
do alfabeto.
� Se Σ1 = {0, 1} é um alfabeto, então:
. 01001 é uma string sobre Σ1;
. 000000000000 é outra string sobre Σ1;
. 1 é outra string sobre Σ1; mas
. 12 não é string sobre Σ1.
� O comprimento de uma string w sobre um alfabeto Σ, denotado
|w|, é o número de símbolos que w contém.
� Se o comprimento de uma string w é n, podemos escrever
w = w1w2w3 . . . wn, onde todo wi ∈ Σ.
� A string vazia é uma string de comprimento 0 e é denotada por ε.
17
Cadeias
� Uma string sobre um alfabeto Σ é uma sequência finita de símbolos
do alfabeto.
� Se Σ1 = {0, 1} é um alfabeto, então:
. 01001 é uma string sobre Σ1;
. 000000000000 é outra string sobre Σ1;
. 1 é outra string sobre Σ1; mas
. 12 não é string sobre Σ1.
� O comprimento de uma string w sobre um alfabeto Σ, denotado
|w|, é o número de símbolos que w contém.
� Se o comprimento de uma string w é n, podemos escrever
w = w1w2w3 . . . wn, onde todo wi ∈ Σ.
� A string vazia é uma string de comprimento 0 e é denotada por ε.
17
Cadeias
� Uma string sobre um alfabeto Σ é uma sequência finita de símbolos
do alfabeto.
� Se Σ1 = {0, 1} é um alfabeto, então:
. 01001 é uma string sobre Σ1;
. 000000000000 é outra string sobre Σ1;
. 1 é outra string sobre Σ1; mas
. 12 não é string sobre Σ1.
� O comprimento de uma string w sobre um alfabeto Σ, denotado
|w|, é o número de símbolos que w contém.
� Se o comprimento de uma string w é n, podemos escrever
w = w1w2w3 . . . wn, onde todo wi ∈ Σ.
� A string vazia é uma string de comprimento 0 e é denotada por ε.
17
Cadeias
� Uma string sobre um alfabeto Σ é uma sequência finita de símbolos
do alfabeto.
� Se Σ1 = {0, 1} é um alfabeto, então:
. 01001 é uma string sobre Σ1;
. 000000000000 é outra string sobre Σ1;
. 1 é outra string sobre Σ1; mas
. 12 não é string sobre Σ1.
� O comprimento de uma string w sobre um alfabeto Σ, denotado
|w|, é o número de símbolos que w contém.
� Se o comprimento de uma string w é n, podemos escrever
w = w1w2w3 . . . wn, onde todo wi ∈ Σ.
� A string vazia é uma string de comprimento 0 e é denotada por ε.
17
Cadeias
� Uma string sobre um alfabeto Σ é uma sequência finita de símbolos
do alfabeto.
� Se Σ1 = {0, 1} é um alfabeto, então:
. 01001 é uma string sobre Σ1;
. 000000000000 é outra string sobre Σ1;
. 1 é outra string sobre Σ1; mas
. 12 não é string sobre Σ1.
� O comprimento de uma string w sobre um alfabeto Σ, denotado
|w|, é o número de símbolos que w contém.
� Se o comprimento de uma string w é n, podemos escrever
w = w1w2w3 . . . wn, onde todo wi ∈ Σ.
� A string vazia é uma string de comprimento 0 e é denotada por ε.
18
Operações em Cadeias
� O reverso de uma string w, denotado por wR, é a string obtida ao
escrever w em ordem contrária. Ou seja, se w = w1w2w3 . . . wn,
então wR = wnwn−1wn−2 . . . w1.
. 12345R = 54321
. 010100R = 001010
. exemploR = olpmexe
� A concatenação de duas strings x e y (de comprimentos m e n) é
a string xy, obtida ao anexar y no final de x:
xy = x1x2 . . . xmy1y2 . . . yn.
� A ordem lexicográfica de strings sobre um alfabeto é uma
ordenação de todas as strings em ordem “alfabética”. Por exemplo, a
ordenação lexicográfica de todas as strings sobre o alfabeto {0, 1} é
(ε, 0, 1, 00, 01, 10, 11, 000, . . .).
� Uma string x é prefixo de outra string y se existe uma string z tal
que xz = y.
18
Operações em Cadeias
� O reverso de uma string w, denotado por wR, é a string obtida ao
escrever w em ordem contrária. Ou seja, se w = w1w2w3 . . . wn,
então wR = wnwn−1wn−2 . . . w1.
. 12345R = 54321
. 010100R = 001010
. exemploR = olpmexe
� A concatenação de duas strings x e y (de comprimentos m e n) é
a string xy, obtida ao anexar y no final de x:
xy = x1x2 . . . xmy1y2 . . . yn.
� A ordem lexicográfica de strings sobre um alfabeto é uma
ordenação de todas as strings em ordem “alfabética”. Por exemplo, a
ordenação lexicográfica de todas as strings sobre o alfabeto {0, 1} é
(ε, 0, 1, 00, 01, 10, 11, 000, . . .).
� Uma string x é prefixo de outra string y se existe uma string z tal
que xz = y.
18
Operações em Cadeias
� O reverso de uma string w, denotado por wR, é a string obtida ao
escrever w em ordem contrária. Ou seja, se w = w1w2w3 . . . wn,
então wR = wnwn−1wn−2 . . . w1.
. 12345R = 54321
. 010100R = 001010
. exemploR = olpmexe
� A concatenação de duas strings x e y (de comprimentos m e n) é
a string xy, obtida ao anexar y no final de x:
xy = x1x2 . . . xmy1y2 . . . yn.
� A ordem lexicográfica de strings sobre um alfabeto é uma
ordenação de todas as strings em ordem “alfabética”. Por exemplo, a
ordenação lexicográfica de todas as strings sobre o alfabeto {0, 1} é
(ε, 0, 1, 00, 01, 10, 11, 000, . . .).
� Uma string x é prefixo de outra string y se existe uma string z tal
que xz = y.
18
Operações em Cadeias
� O reverso de uma string w, denotado por wR, é a string obtida ao
escrever w em ordem contrária. Ou seja, se w = w1w2w3 . . . wn,
então wR = wnwn−1wn−2 . . . w1.
. 12345R = 54321
. 010100R = 001010
. exemploR = olpmexe
� A concatenação de duas strings x e y (de comprimentos m e n) é
a string xy, obtida ao anexar y no final de x:
xy= x1x2 . . . xmy1y2 . . . yn.
� A ordem lexicográfica de strings sobre um alfabeto é uma
ordenação de todas as strings em ordem “alfabética”. Por exemplo, a
ordenação lexicográfica de todas as strings sobre o alfabeto {0, 1} é
(ε, 0, 1, 00, 01, 10, 11, 000, . . .).
� Uma string x é prefixo de outra string y se existe uma string z tal
que xz = y.
18
Operações em Cadeias
� O reverso de uma string w, denotado por wR, é a string obtida ao
escrever w em ordem contrária. Ou seja, se w = w1w2w3 . . . wn,
então wR = wnwn−1wn−2 . . . w1.
. 12345R = 54321
. 010100R = 001010
. exemploR = olpmexe
� A concatenação de duas strings x e y (de comprimentos m e n) é
a string xy, obtida ao anexar y no final de x:
xy = x1x2 . . . xmy1y2 . . . yn.
� A ordem lexicográfica de strings sobre um alfabeto é uma
ordenação de todas as strings em ordem “alfabética”. Por exemplo, a
ordenação lexicográfica de todas as strings sobre o alfabeto {0, 1} é
(ε, 0, 1, 00, 01, 10, 11, 000, . . .).
� Uma string x é prefixo de outra string y se existe uma string z tal
que xz = y.
18
Operações em Cadeias
� O reverso de uma string w, denotado por wR, é a string obtida ao
escrever w em ordem contrária. Ou seja, se w = w1w2w3 . . . wn,
então wR = wnwn−1wn−2 . . . w1.
. 12345R = 54321
. 010100R = 001010
. exemploR = olpmexe
� A concatenação de duas strings x e y (de comprimentos m e n) é
a string xy, obtida ao anexar y no final de x:
xy = x1x2 . . . xmy1y2 . . . yn.
� A ordem lexicográfica de strings sobre um alfabeto é uma
ordenação de todas as strings em ordem “alfabética”. Por exemplo, a
ordenação lexicográfica de todas as strings sobre o alfabeto {0, 1} é
(ε, 0, 1, 00, 01, 10, 11, 000, . . .).
� Uma string x é prefixo de outra string y se existe uma string z tal
que xz = y.
18
Operações em Cadeias
� O reverso de uma string w, denotado por wR, é a string obtida ao
escrever w em ordem contrária. Ou seja, se w = w1w2w3 . . . wn,
então wR = wnwn−1wn−2 . . . w1.
. 12345R = 54321
. 010100R = 001010
. exemploR = olpmexe
� A concatenação de duas strings x e y (de comprimentos m e n) é
a string xy, obtida ao anexar y no final de x:
xy = x1x2 . . . xmy1y2 . . . yn.
� A ordem lexicográfica de strings sobre um alfabeto é uma
ordenação de todas as strings em ordem “alfabética”. Por exemplo, a
ordenação lexicográfica de todas as strings sobre o alfabeto {0, 1} é
(ε, 0, 1, 00, 01, 10, 11, 000, . . .).
� Uma string x é prefixo de outra string y se existe uma string z tal
que xz = y.
19
Linguagens
� Uma linguagem é um conjunto de strings sobre um alfabeto Σ.
� Podemos utilizar alfabetos, strings e linguagens para definir
problemas computacionais!
� Vamos ver um exemplo prático.
1
2
3 4
5
� Quais os símbolos/caracteres que vocês acham interessantes e
necessários para definir esse grafo?
� Σ = {(, ), |, 1, 2, 3, 4, 5,�, ,}
� G = (1, 2, 3, 4, 5|(1, 3), (1, 4), (2, 5), (2, 4), (3, 5)�)
� L = {G : G é uma string sobre Σ e modela um grafo.}
19
Linguagens
� Uma linguagem é um conjunto de strings sobre um alfabeto Σ.
� Podemos utilizar alfabetos, strings e linguagens para definir
problemas computacionais!
� Vamos ver um exemplo prático.
1
2
3 4
5
� Quais os símbolos/caracteres que vocês acham interessantes e
necessários para definir esse grafo?
� Σ = {(, ), |, 1, 2, 3, 4, 5,�, ,}
� G = (1, 2, 3, 4, 5|(1, 3), (1, 4), (2, 5), (2, 4), (3, 5)�)
� L = {G : G é uma string sobre Σ e modela um grafo.}
19
Linguagens
� Uma linguagem é um conjunto de strings sobre um alfabeto Σ.
� Podemos utilizar alfabetos, strings e linguagens para definir
problemas computacionais!
� Vamos ver um exemplo prático.
1
2
3 4
5
� Quais os símbolos/caracteres que vocês acham interessantes e
necessários para definir esse grafo?
� Σ = {(, ), |, 1, 2, 3, 4, 5,�, ,}
� G = (1, 2, 3, 4, 5|(1, 3), (1, 4), (2, 5), (2, 4), (3, 5)�)
� L = {G : G é uma string sobre Σ e modela um grafo.}
19
Linguagens
� Uma linguagem é um conjunto de strings sobre um alfabeto Σ.
� Podemos utilizar alfabetos, strings e linguagens para definir
problemas computacionais!
� Vamos ver um exemplo prático.
1
2
3 4
5
� Quais os símbolos/caracteres que vocês acham interessantes e
necessários para definir esse grafo?
� Σ = {(, ), |, 1, 2, 3, 4, 5,�, ,}
� G = (1, 2, 3, 4, 5|(1, 3), (1, 4), (2, 5), (2, 4), (3, 5)�)
� L = {G : G é uma string sobre Σ e modela um grafo.}
19
Linguagens
� Uma linguagem é um conjunto de strings sobre um alfabeto Σ.
� Podemos utilizar alfabetos, strings e linguagens para definir
problemas computacionais!
� Vamos ver um exemplo prático.
1
2
3 4
5
� Quais os símbolos/caracteres que vocês acham interessantes e
necessários para definir esse grafo?
� Σ = {(, ), |, 1, 2, 3, 4, 5,�, ,}
� G = (1, 2, 3, 4, 5|(1, 3), (1, 4), (2, 5), (2, 4), (3, 5)�)
� L = {G : G é uma string sobre Σ e modela um grafo.}
19
Linguagens
� Uma linguagem é um conjunto de strings sobre um alfabeto Σ.
� Podemos utilizar alfabetos, strings e linguagens para definir
problemas computacionais!
� Vamos ver um exemplo prático.
1
2
3 4
5
� Quais os símbolos/caracteres que vocês acham interessantes e
necessários para definir esse grafo?
� Σ = {(, ), |, 1, 2, 3, 4, 5,�, ,}
� G = (1, 2, 3, 4, 5|(1, 3), (1, 4), (2, 5), (2, 4), (3, 5)�)
� L = {G : G é uma string sobre Σ e modela um grafo.}
19
Linguagens
� Uma linguagem é um conjunto de strings sobre um alfabeto Σ.
� Podemos utilizar alfabetos, strings e linguagens para definir
problemas computacionais!
� Vamos ver um exemplo prático.
1
2
3 4
5
� Quais os símbolos/caracteres que vocês acham interessantes e
necessários para definir esse grafo?
� Σ = {(, ), |, 1, 2, 3, 4, 5,�, ,}
� G = (1, 2, 3, 4, 5|(1, 3), (1, 4), (2, 5), (2, 4), (3, 5)�)
� L = {G : G é uma string sobre Σ e modela um grafo.}
19
Linguagens
� Uma linguagem é um conjunto de strings sobre um alfabeto Σ.
� Podemos utilizar alfabetos, strings e linguagens para definir
problemas computacionais!
� Vamos ver um exemplo prático.
1
2
3 4
5
� Quais os símbolos/caracteres que vocês acham interessantes e
necessários para definir esse grafo?
� Σ = {(, ), |, 1, 2, 3, 4, 5,�, ,}
� G = (1, 2, 3, 4, 5|(1, 3), (1, 4), (2, 5), (2, 4), (3, 5)�)
� L = {G : G é uma string sobre Σ e modela um grafo.}
20
0.4 Lógica Booleana
21
Lógica Booleana
� Lógica Booleana é um sistema matemático construído em cima de
dois valores: True e False.
� Todas as operações retornam somente estes dois valores booleanos.
� Para simplificar, podemos denotar True = 1 e False = 0.
� As operações booleanas são:
. Negação (NOT): ¬
. Conjunção (AND): ∧
. Disjunção (OR): ∨
Tabela Lógica do AND
0 ∨ 0 = 0
0 ∨ 1 = 1
1 ∨ 0 = 1
1 ∨ 1 = 1
Tabela Lógica do OR
0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1
Tabela Lógica do NOT
¬0 = 1
¬1 = 0
21
Lógica Booleana
� Lógica Booleana é um sistema matemático construído em cima de
dois valores: True e False.
� Todas as operações retornam somente estes dois valores booleanos.
� Para simplificar, podemos denotar True = 1 e False = 0.
� As operações booleanas são:
. Negação (NOT): ¬
. Conjunção (AND): ∧
. Disjunção (OR): ∨
Tabela Lógica do AND
0 ∨ 0 = 0
0 ∨ 1 = 1
1 ∨ 0 = 1
1 ∨ 1 = 1
Tabela Lógica do OR
0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1
Tabela Lógica do NOT
¬0 = 1
¬1 = 0
21
Lógica Booleana
� Lógica Booleana é um sistema matemático construído em cima de
dois valores: True e False.
� Todas as operações retornam somente estes dois valores booleanos.
� Para simplificar, podemos denotar True = 1 e False = 0.
� As operações booleanas são:
. Negação (NOT): ¬
. Conjunção (AND): ∧
. Disjunção (OR): ∨
Tabela Lógica do AND
0 ∨ 0 = 0
0 ∨ 1 = 1
1 ∨ 0 = 1
1 ∨ 1 = 1
Tabela Lógica do OR
0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1
Tabela Lógica do NOT
¬0 = 1
¬1 = 0
21
Lógica Booleana
� Lógica Booleana é um sistema matemático construído em cima de
dois valores: True e False.
� Todas as operações retornam somente estes dois valores booleanos.
� Para simplificar, podemos denotar True = 1 e False= 0.
� As operações booleanas são:
. Negação (NOT): ¬
. Conjunção (AND): ∧
. Disjunção (OR): ∨
Tabela Lógica do AND
0 ∨ 0 = 0
0 ∨ 1 = 1
1 ∨ 0 = 1
1 ∨ 1 = 1
Tabela Lógica do OR
0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1
Tabela Lógica do NOT
¬0 = 1
¬1 = 0
21
Lógica Booleana
� Lógica Booleana é um sistema matemático construído em cima de
dois valores: True e False.
� Todas as operações retornam somente estes dois valores booleanos.
� Para simplificar, podemos denotar True = 1 e False = 0.
� As operações booleanas são:
. Negação (NOT): ¬
. Conjunção (AND): ∧
. Disjunção (OR): ∨
Tabela Lógica do AND
0 ∨ 0 = 0
0 ∨ 1 = 1
1 ∨ 0 = 1
1 ∨ 1 = 1
Tabela Lógica do OR
0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1
Tabela Lógica do NOT
¬0 = 1
¬1 = 0
21
Lógica Booleana
� Lógica Booleana é um sistema matemático construído em cima de
dois valores: True e False.
� Todas as operações retornam somente estes dois valores booleanos.
� Para simplificar, podemos denotar True = 1 e False = 0.
� As operações booleanas são:
. Negação (NOT): ¬
. Conjunção (AND): ∧
. Disjunção (OR): ∨
Tabela Lógica do AND
0 ∨ 0 = 0
0 ∨ 1 = 1
1 ∨ 0 = 1
1 ∨ 1 = 1
Tabela Lógica do OR
0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1
Tabela Lógica do NOT
¬0 = 1
¬1 = 0
21
Lógica Booleana
� Lógica Booleana é um sistema matemático construído em cima de
dois valores: True e False.
� Todas as operações retornam somente estes dois valores booleanos.
� Para simplificar, podemos denotar True = 1 e False = 0.
� As operações booleanas são:
. Negação (NOT): ¬
. Conjunção (AND): ∧
. Disjunção (OR): ∨
Tabela Lógica do AND
0 ∨ 0 = 0
0 ∨ 1 = 1
1 ∨ 0 = 1
1 ∨ 1 = 1
Tabela Lógica do OR
0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1
Tabela Lógica do NOT
¬0 = 1
¬1 = 0
21
Lógica Booleana
� Lógica Booleana é um sistema matemático construído em cima de
dois valores: True e False.
� Todas as operações retornam somente estes dois valores booleanos.
� Para simplificar, podemos denotar True = 1 e False = 0.
� As operações booleanas são:
. Negação (NOT): ¬
. Conjunção (AND): ∧
. Disjunção (OR): ∨
Tabela Lógica do AND
0 ∨ 0 = 0
0 ∨ 1 = 1
1 ∨ 0 = 1
1 ∨ 1 = 1
Tabela Lógica do OR
0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1
Tabela Lógica do NOT
¬0 = 1
¬1 = 0
21
Lógica Booleana
� Lógica Booleana é um sistema matemático construído em cima de
dois valores: True e False.
� Todas as operações retornam somente estes dois valores booleanos.
� Para simplificar, podemos denotar True = 1 e False = 0.
� As operações booleanas são:
. Negação (NOT): ¬
. Conjunção (AND): ∧
. Disjunção (OR): ∨
Tabela Lógica do AND
0 ∨ 0 = 0
0 ∨ 1 = 1
1 ∨ 0 = 1
1 ∨ 1 = 1
Tabela Lógica do OR
0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1
Tabela Lógica do NOT
¬0 = 1
¬1 = 0
21
Lógica Booleana
� Lógica Booleana é um sistema matemático construído em cima de
dois valores: True e False.
� Todas as operações retornam somente estes dois valores booleanos.
� Para simplificar, podemos denotar True = 1 e False = 0.
� As operações booleanas são:
. Negação (NOT): ¬
. Conjunção (AND): ∧
. Disjunção (OR): ∨
Tabela Lógica do AND
0 ∨ 0 = 0
0 ∨ 1 = 1
1 ∨ 0 = 1
1 ∨ 1 = 1
Tabela Lógica do OR
0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1
Tabela Lógica do NOT
¬0 = 1
¬1 = 0
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógica do XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”...
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógica do XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”...
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógica do XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”...
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógica do XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”...
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógica do XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”...
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógica do XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”...
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógica do XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”...
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógica do XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”...
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógica do XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”...
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógicado XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”... na verdade só duas!
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógica do XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”... na verdade só duas!
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógica do XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”... na verdade só duas!
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógica do XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”... na verdade só duas!
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
22
Lógica Booleana
� Mais algumas operações booleanas:
. “Ou exclusivo” (⊕)
. Implicação ( =⇒ )
. Igualdade (⇐⇒ )
Tabela Lógica do XOR
0⊕ 0 = 0
0⊕ 1 = 1
1⊕ 0 = 1
1⊕ 1 = 0
Tabela Lógica da Implicação
0 =⇒ 0 = 1
0 =⇒ 1 = 1
1 =⇒ 0 = 0
1 =⇒ 1 = 1
Tabela Lógica da Igualdade
0 ⇐⇒ 0 = 1
0 ⇐⇒ 1 = 0
1 ⇐⇒ 0 = 0
1 ⇐⇒ 1 = 1
� No fundo no fundo, todas as operações podem ser escritas utilizando
as três operações “básicas”... na verdade só duas!
. P ∨Q = ¬(¬P ∧ ¬Q)
. P =⇒ Q = ¬P ∨Q
. P ⇐⇒ Q = (P =⇒ Q) ∧ (Q =⇒ P )
. P ⊕Q = ¬(P ⇐⇒ Q)
23
Dúvidas?
24
Bom feriado :)
	0.1 Noções Matemáticas e Terminologia
	0.2 Grafos
	0.3 Alfabetos, Cadeias e Linguagens
	0.4 Lógica Booleana
	Dúvidas?
	Bom feriado :)