Noções e Notação Matemática & Autômatos

1

Noções e NotaçãoMatemá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 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 :)