Embed Size (px)
Citation preview
1
Noções e NotaçãoMatemática & Autômatos
Prof. Celso A. W. Santos
53A3 :: Aspectos Teóricos da Computação
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 agrupamentode 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 oumembros.
� 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 enão-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não sepreocupam 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 agrupamentode 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 oumembros.
� 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 enão-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não sepreocupam 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 agrupamentode 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 oumembros.
� 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 enão-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não sepreocupam 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 agrupamentode 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 oumembros.
� 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 enão-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não sepreocupam 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 agrupamentode 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 oumembros.
� 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 enão-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não sepreocupam 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 agrupamentode 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 oumembros.
� 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 enão-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não sepreocupam 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 agrupamentode 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 oumembros.
� 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 enão-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não sepreocupam 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 agrupamentode 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 oumembros.
� 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 enão-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} ? S
� Conjuntos não possuem ordenação em seus elementos e não sepreocupam 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 agrupamentode 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 oumembros.
� 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 enão-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7} /∈ S
� Conjuntos não possuem ordenação em seus elementos e não sepreocupam 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 agrupamentode 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 oumembros.
� 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 enão-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7}/∈S
� Conjuntos não possuem ordenação em seus elementos e não sepreocupam 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 agrupamentode 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 oumembros.
� 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 enão-pertencimento, respectivamente.
. Exemplos: 7 ∈ S; 8 6∈ S; {7}/∈S
� Conjuntos não possuem ordenação em seus elementos e não sepreocupam 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 membrode 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, descrevemoso 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 membrode 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, descrevemoso 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 membrode 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, descrevemoso 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 membrode 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, descrevemoso 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 membrode 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, descrevemoso 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 membrode 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, descrevemoso 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 membrode 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, descrevemoso 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 membrode 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, descrevemoso 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 umconceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar umconceito teórico.
� Para conjuntos, usamos uma figura chamada Diagrama de Venn
6
Representando Conjuntos
� Na matemática, muitas vezes uma imagem ajuda a elucidar umconceito 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 umconceito 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 umconceito 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 umconceito 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 umconceito 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 umconceito 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 umconceito 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 umconceito 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 umconceito 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 umconceito 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 umconceito 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 umconceito 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 umconceito 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 obtidocombinando 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 quecontém os elementos que pertencem a A e a B.
. O complemento de um conjunto A, denotado por A, é o conjuntoque 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 obtidocombinando 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 quecontém os elementos que pertencem a A e a B.
. O complemento de um conjunto A, denotado por A, é o conjuntoque 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 obtidocombinando 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 quecontém os elementos que pertencem a A e a B.
. O complemento de um conjunto A, denotado por A, é o conjuntoque 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 obtidocombinando 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 quecontém os elementos que pertencem a A e a B.
. O complemento de um conjunto A, denotado por A, é o conjuntoque 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 obtidocombinando 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 quecontém os elementos que pertencem a A e a B.
. O complemento de um conjunto A, denotado por A, é o conjuntoque 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 é oconjunto contendo todos os pares ordenados, cujo primeiro elementoé um membro do conjunto A e o segundo elemento é um membrodo conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produtocartesiano 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 produtocartesiano. 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 é oconjunto contendo todos os pares ordenados, cujo primeiro elementoé um membro do conjunto A e o segundo elemento é um membrodo conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produtocartesiano 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 produtocartesiano. 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 é oconjunto contendo todos os pares ordenados, cujo primeiro elementoé um membro do conjunto A e o segundo elemento é um membrodo conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produtocartesiano 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 produtocartesiano. 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 é oconjunto contendo todos os pares ordenados, cujo primeiro elementoé um membro do conjunto A e o segundo elemento é um membrodo conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produtocartesiano 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 produtocartesiano. 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 é oconjunto contendo todos os pares ordenados, cujo primeiro elementoé um membro do conjunto A e o segundo elemento é um membrodo conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produtocartesiano 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 produtocartesiano. 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 é oconjunto contendo todos os pares ordenados, cujo primeiro elementoé um membro do conjunto A e o segundo elemento é um membrodo conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produtocartesiano 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 produtocartesiano. 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 é oconjunto contendo todos os pares ordenados, cujo primeiro elementoé um membro do conjunto A e o segundo elemento é um membrodo conjunto B
� Por exemplo, sejam A = {1, 2} e B = {x, y, z}. Então, o produtocartesiano 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 produtocartesiano. 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 porf : 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 11 22 33 44 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada porf : 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 11 22 33 44 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada porf : 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 11 22 33 44 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada porf : 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 11 22 33 44 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada porf : 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 11 22 33 44 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada porf : 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 11 22 33 44 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada porf : 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 11 22 33 44 0
9
Funções
� Nesse caso, chamamos f de uma função de A em B, denotada porf : 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 11 22 33 44 0
10
Funções
� Mais exemplos2 g : Z4 × Z4 → Z4
g 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 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 econtradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos2 g : Z4 × Z4 → Z4
g 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 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 econtradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos2 g : Z4 × Z4 → Z4
g 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 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 econtradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos2 g : Z4 × Z4 → Z4
g 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 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 econtradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos2 g : Z4 × Z4 → Z4
g 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 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 econtradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos2 g : Z4 × Z4 → Z4
g 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 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 econtradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos2 g : Z4 × Z4 → Z4
g 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 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 econtradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos2 g : Z4 × Z4 → Z4
g 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 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 econtradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos2 g : Z4 × Z4 → Z4
g 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 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 econtradomínio são o conjunto {Pedra, Papel, Tesoura}.
10
Funções
� Mais exemplos2 g : Z4 × Z4 → Z4
g 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 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 econtradomínio são o conjunto {Pedra, Papel, Tesoura}.
11
Funções
� Mais exemplos:
Ganha Pedra Papel TesouraPedraPapel
Tesoura
Pedra
Papel
Tesoura
� Funções cujo domínio e contradomínio são o mesmo conjuntopodem ser visualizadas usando grafos!
11
Funções
� Mais exemplos:
Ganha Pedra Papel TesouraPedraPapel
Tesoura
Pedra
Papel
Tesoura
� Funções cujo domínio e contradomínio são o mesmo conjuntopodem ser visualizadas usando grafos!
11
Funções
� Mais exemplos:
Ganha Pedra Papel TesouraPedraPapel
Tesoura
Pedra
Papel
Tesoura
� Funções cujo domínio e contradomínio são o mesmo conjuntopodem ser visualizadas usando grafos!
11
Funções
� Mais exemplos:
Ganha Pedra Papel TesouraPedraPapel
Tesoura
Pedra
Papel
Tesoura
� Funções cujo domínio e contradomínio são o mesmo conjuntopodem ser visualizadas usando grafos!
11
Funções
� Mais exemplos:
Ganha Pedra Papel TesouraPedraPapel
Tesoura
Pedra
Papel
Tesoura
� Funções cujo domínio e contradomínio são o mesmo conjuntopodem ser visualizadas usando grafos!
12
0.2 Grafos
13
Grafos
� Um grafo G = (V, E) é uma estrutura de dados composta por doisconjuntos: 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érticesque definem as arestas.
13
Grafos
� Um grafo G = (V, E) é uma estrutura de dados composta por doisconjuntos: 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érticesque definem as arestas.
13
Grafos
� Um grafo G = (V, E) é uma estrutura de dados composta por doisconjuntos: 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érticesque definem as arestas.
13
Grafos
� Um grafo G = (V, E) é uma estrutura de dados composta por doisconjuntos: 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érticesque definem as arestas.
13
Grafos
� Um grafo G = (V, E) é uma estrutura de dados composta por doisconjuntos: 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érticesque 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érticesconectados por arestas, sem repetição de vértices.
� Um ciclo no grafo é um caminho fechado, onde o último e oprimeiro vértice são o mesmo.
� Um grafo é conexo se existe um caminho entre todo par de vérticesde 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érticesconectados por arestas, sem repetição de vértices.
� Um ciclo no grafo é um caminho fechado, onde o último e oprimeiro vértice são o mesmo.
� Um grafo é conexo se existe um caminho entre todo par de vérticesde 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érticesconectados por arestas, sem repetição de vértices.
� Um ciclo no grafo é um caminho fechado, onde o último e oprimeiro vértice são o mesmo.
� Um grafo é conexo se existe um caminho entre todo par de vérticesde 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érticesconectados por arestas, sem repetição de vértices.
� Um ciclo no grafo é um caminho fechado, onde o último e oprimeiro vértice são o mesmo.
� Um grafo é conexo se existe um caminho entre todo par de vérticesde 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érticesconectados por arestas, sem repetição de vértices.
� Um ciclo no grafo é um caminho fechado, onde o último e oprimeiro vértice são o mesmo.
� Um grafo é conexo se existe um caminho entre todo par de vérticesde 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 dacomputação.
� Não somente porque elas são um tipo de dados presente na maioriadas linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modeladoutilizando 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 sigmamaiú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 dacomputação.
� Não somente porque elas são um tipo de dados presente na maioriadas linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modeladoutilizando 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 sigmamaiú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 dacomputação.
� Não somente porque elas são um tipo de dados presente na maioriadas linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modeladoutilizando 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 sigmamaiú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 dacomputação.
� Não somente porque elas são um tipo de dados presente na maioriadas linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modeladoutilizando 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 sigmamaiú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 dacomputação.
� Não somente porque elas são um tipo de dados presente na maioriadas linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modeladoutilizando 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 sigmamaiú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 dacomputação.
� Não somente porque elas são um tipo de dados presente na maioriadas linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modeladoutilizando 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 sigmamaiú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 dacomputação.
� Não somente porque elas são um tipo de dados presente na maioriadas linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modeladoutilizando 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 sigmamaiú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 dacomputação.
� Não somente porque elas são um tipo de dados presente na maioriadas linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modeladoutilizando 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 sigmamaiú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 dacomputação.
� Não somente porque elas são um tipo de dados presente na maioriadas linguagens de programação. Muito pelo contrário!
� Na verdade, todo problema computacional pode ser modeladoutilizando 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 sigmamaiú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ímbolosdo 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 escreverw = 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ímbolosdo 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 escreverw = 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ímbolosdo 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 escreverw = 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ímbolosdo 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 escreverw = 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ímbolosdo 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 escreverw = 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 aoescrever 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 é umaordenação de todas as strings em ordem “alfabética”. Por exemplo, aordenaçã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 talque xz = y.
18
Operações em Cadeias
� O reverso de uma string w, denotado por wR, é a string obtida aoescrever 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 é umaordenação de todas as strings em ordem “alfabética”. Por exemplo, aordenaçã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 talque xz = y.
18
Operações em Cadeias
� O reverso de uma string w, denotado por wR, é a string obtida aoescrever 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 é umaordenação de todas as strings em ordem “alfabética”. Por exemplo, aordenaçã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 talque xz = y.
18
Operações em Cadeias
� O reverso de uma string w, denotado por wR, é a string obtida aoescrever 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 é umaordenação de todas as strings em ordem “alfabética”. Por exemplo, aordenaçã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 talque xz = y.
18
Operações em Cadeias
� O reverso de uma string w, denotado por wR, é a string obtida aoescrever 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 é umaordenação de todas as strings em ordem “alfabética”. Por exemplo, aordenaçã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 talque xz = y.
18
Operações em Cadeias
� O reverso de uma string w, denotado por wR, é a string obtida aoescrever 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 é umaordenação de todas as strings em ordem “alfabética”. Por exemplo, aordenaçã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 talque xz = y.
18
Operações em Cadeias
� O reverso de uma string w, denotado por wR, é a string obtida aoescrever 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 é umaordenação de todas as strings em ordem “alfabética”. Por exemplo, aordenaçã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 talque 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 enecessá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 enecessá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 enecessá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 enecessá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 enecessá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 enecessá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 enecessá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 enecessá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 dedois 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 dedois 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 dedois 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 dedois 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 dedois 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 dedois 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 dedois 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 dedois 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 dedois 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 dedois 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 utilizandoas 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 utilizandoas 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 utilizandoas 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 utilizandoas 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 utilizandoas 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 utilizandoas 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 utilizandoas 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 utilizandoas 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 utilizandoas 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 utilizandoas 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 utilizandoas 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 utilizandoas 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 utilizandoas 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 utilizandoas 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 :)
