Álgebra Booleana - Unicamp

1

Álgebra BooleanaProf. Celso A. W. Santos

J701 :: Lógica de Programação e Algoritmos

[email protected]

25/08/2020

2

O que já vimos até agora?

� O que é um algoritmo? Pra que eles servem? Pra que computadoresservem?

� O que são variáveis?

� Quais são os tipos de dados mais usados?

� Como identificamos variáveis em memória?

� Como estruturamos os nossos algoritmos?

2







2







2







2







3

Exemplo da soma

� Problema: Descreva um algoritmo para somar três números.

3

Exemplo da soma


Início

3

Exemplo da soma


Início x, y, z

3

Exemplo da soma


Início x, y, z

resultado← x + y + z

3

Exemplo da soma


Início x, y, z


resultado

3

Exemplo da soma


Início x, y, z


resultado Fim

3

Exemplo da soma


Início x, y, z


resultado Fim

E se pudéssemosusar apenas

duas variáveis?

4

Resolvendo o Ex. #1!

� Problema: Some três números usando apenas duas variáveis.

4



Início

4



Início a, b

4



Início a, b

ba

4



Início a, b a← a + b

ba

4




, ab, a

ba

4




, ab, aa← a + b

ba

4




, ab, aa← a + ba

ba

4




, ab, aa← a + ba

Fim

ba

5

Formalizando: Estrutura Sequencial

� Em pseudocódigo:

Entrada: Três números x, y e zSaída: O valor x + y + z

Declara variáveis a, ba← input do usuáriob← input do usuárioa← a + bb← input do usuárioa← a + bimprime a

Os nomes e funcionalidades dasvariáveis são “independentes”da entrada do programa!

Todo algoritmo segue amesma estrutura sequencial:(i) início;(ii) declaração de variáveis;(iii) processamento; e(iv) fim.

5







5







5







5







5







5







5







6

Entrada e Saída

� As informações de entrada do usuário serão armazenadas emvariáveis.

� Conforme vimos, variáveis possuem um nome e um tipo de dadoespecífico!

De agora em diante, todas as declarações de variáveis e operaçõesde entrada devem vir acompanhadas do tipo de dado!

� Nosso objetivo não é fazer códigos/programas/algoritmos ultraabrangentes, ou lidar com todos os tipos de dados possíveis deentrada, ou qualquer coisa do tipo. Nosso objetivo (nesta disciplina)é lidar com problemas computacionais específicos!

� O algoritmo é considerado correto quando ele dá uma respostacorreta para uma entrada correta!

. Se a entrada foi errada, a culpa é do usuário, não do programador!

6

Entrada e Saída







6

Entrada e Saída







6

Entrada e Saída







6

Entrada e Saída







6

Entrada e Saída







7

Agora com tipos de dados...



Declara variáveis a, b

a← input do usuáriob← input do usuárioa← a + bb← input do usuárioa← a + bimprime a



7

Agora com tipos de dados...



Declara variáveis a, b (inteiras)a← input (int) do usuáriob← input (int) do usuárioa← a + bb← input (int) do usuárioa← a + bimprime a



8

Alterando o Fluxo

� E se quisermos alterar o fluxo sequencial de um algoritmo?

Início NP1, NP2

NS = 3×NP 1+4×NP 27

NS ≥ 7.0?

“Aprovado :)”

sim

Fim

EX

nãoNF = NS+EX

2

NF ≥ 5.0?sim

“Reprovado D:”

não

8

Alterando o Fluxo


Início NP1, NP2

NS = 3×NP 1+4×NP 27

NS ≥ 7.0?

“Aprovado :)”

sim

Fim

EX

nãoNF = NS+EX

2

NF ≥ 5.0?sim

“Reprovado D:”

não

8

Alterando o Fluxo


Início NP1, NP2

NS = 3×NP 1+4×NP 27

NS ≥ 7.0?

“Aprovado :)”

sim

Fim

EX

nãoNF = NS+EX

2

NF ≥ 5.0?sim

“Reprovado D:”

não

Depende doresultado de umaoperação lógica!

9

Valores Booleanos

10

Um pouquinho de história...

� Como formalizar matematicamente “lógica dedutiva”?

George Boole (1815 – 1864)� Definiu a álgebra booleana: uma área da matemática que lida com

operações lógicas em valores binários.

� Imprescindível em linguagens de programação modernas, porque sótratamos com informações binárias!

10






10






10






11

O Tipo de Dado Booleano

� Dados Lógicos: valores booleanos True e False.

� Esses valores são associados a proposições (não necessariamentematemáticas!)

. “Todos os números são inteiros.”

. “Alguns números negativos são inteiros.”

. “Todo quadrado é um retângulo.”

. “O número 10 é maior que o número 20.”

. “Eu tenho 187cm de altura.”

. “Hoje vai chover.”

. “O valor na variável x é maior que o valor da variável y.”

� Dependendo da pessoa, do dia, ou dos valores das variáveis x e y, ovalor booleano das expressões pode mudar!

� A chave é que o valor booleano dessas expressões pode ser testado!

� Podemos controlar o fluxo de execução de um algoritmo dependendodo valor de expressões!

11














11














11




. “Todos os números são inteiros.” =⇒ False










11














11





. “Alguns números negativos são inteiros.” =⇒ True









11














11






. “Todo quadrado é um retângulo.” =⇒ True








11














11







. “O número 10 é maior que o número 20.” =⇒ False







11














11








. “Eu tenho 187cm de altura.” ???






11














11









. “Hoje vai chover.” ???





11














11










. “O valor na variável x é maior que o valor da variável y.” ???




11














11














11














12

Controle de Fluxo :: Exemplo #1

8. Desenhe um fluxograma que mostra o resultado da divisão dedois números. Lembre-se: não é possível dividir por zero.

Início

n1, n2 n2 = 0?

“Não é possíveldividir por zero!”

d← n1/n2 d

Fim

12



Início

n1, n2 n2 = 0?


d← n1/n2 d

Fim

sim

não

12



Início

n1, n2 n2 = 0?


d← n1/n2 d

Fim

True

False

13

Operadores e Resultados Booleanos

14

Resultados Booleanos: Comparações

� As principais operações matemáticas que retornam dados Booleanossão comparações lógicas.

. Maior ou igual (≥)

. Maior (>)

. Menor ou igual (≤)

. Menor (<)

. Igualdade (=)

. Desigualdade (6=)

� Exemplos didáticos:. É verdade que 10 > 20?. É verdade que 10 ≥ 10?. É verdade que 10 > 4?. É verdade que n1 = 0?. É verdade que ’10’ > ’4’?

14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)


14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)


14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)


14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)


14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)


14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)


14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)


14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)


14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)

� Exemplos didáticos:. É verdade que 10 > 20? =⇒ False. É verdade que 10 ≥ 10?. É verdade que 10 > 4?. É verdade que n1 = 0?. É verdade que ’10’ > ’4’?

14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)

� Exemplos didáticos:. É verdade que 10 > 20? =⇒ False. É verdade que 10 ≥ 10?. É verdade que 10 > 4?. É verdade que n1 = 0?. É verdade que ’10’ > ’4’?

14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)

� Exemplos didáticos:. É verdade que 10 > 20? =⇒ False. É verdade que 10 ≥ 10? =⇒ True. É verdade que 10 > 4?. É verdade que n1 = 0?. É verdade que ’10’ > ’4’?

14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)

� Exemplos didáticos:. É verdade que 10 > 20? =⇒ False. É verdade que 10 ≥ 10? =⇒ True. É verdade que 10 > 4?. É verdade que n1 = 0?. É verdade que ’10’ > ’4’?

14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)

� Exemplos didáticos:. É verdade que 10 > 20? =⇒ False. É verdade que 10 ≥ 10? =⇒ True. É verdade que 10 > 4? =⇒ True. É verdade que n1 = 0?. É verdade que ’10’ > ’4’?

14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)

� Exemplos didáticos:. É verdade que 10 > 20? =⇒ False. É verdade que 10 ≥ 10? =⇒ True. É verdade que 10 > 4? =⇒ True. É verdade que n1 = 0?. É verdade que ’10’ > ’4’?

14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)

� Exemplos didáticos:. É verdade que 10 > 20? =⇒ False. É verdade que 10 ≥ 10? =⇒ True. É verdade que 10 > 4? =⇒ True. É verdade que n1 = 0? Depende do que estiver em n1!. É verdade que ’10’ > ’4’?

14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)

� Exemplos didáticos:. É verdade que 10 > 20? =⇒ False. É verdade que 10 ≥ 10? =⇒ True. É verdade que 10 > 4? =⇒ True. É verdade que n1 = 0? Depende do que estiver em n1!. É verdade que ’10’ > ’4’?

14




. Maior (>)


. Menor (<)

. Igualdade (=)

. Desigualdade (6=)

� Exemplos didáticos:. É verdade que 10 > 20? =⇒ False. É verdade que 10 ≥ 10? =⇒ True. É verdade que 10 > 4? =⇒ True. É verdade que n1 = 0? Depende do que estiver em n1!. É verdade que ’10’ > ’4’? =⇒ False

15


� Existem outras operações!. Pertencimento (∈, in). Não pertencimento (6∈). Existência (∃). Não existência ( 6 ∃). Subconjunto (⊂). Superconjunto (⊃)

� Exemplos (não tão) didáticos:. ’na’ in ’banana’. ’bat’ in ’superman’. 3 ∈ {1, 2, 3, 4}. {1, 3} ⊂ números ímpares?. números primos ⊃ números ímpares?

15




15




15




15




15




15




15




15




15



� Exemplos (não tão) didáticos:. ’na’ in ’banana’ =⇒ True. ’bat’ in ’superman’. 3 ∈ {1, 2, 3, 4}. {1, 3} ⊂ números ímpares?. números primos ⊃ números ímpares?

15



� Exemplos (não tão) didáticos:. ’na’ in ’banana’ =⇒ True. ’bat’ in ’superman’. 3 ∈ {1, 2, 3, 4}. {1, 3} ⊂ números ímpares?. números primos ⊃ números ímpares?

15



� Exemplos (não tão) didáticos:. ’na’ in ’banana’ =⇒ True. ’bat’ in ’superman’ =⇒ False. 3 ∈ {1, 2, 3, 4}. {1, 3} ⊂ números ímpares?. números primos ⊃ números ímpares?

15



� Exemplos (não tão) didáticos:. ’na’ in ’banana’ =⇒ True. ’bat’ in ’superman’ =⇒ False. 3 ∈ {1, 2, 3, 4}. {1, 3} ⊂ números ímpares?. números primos ⊃ números ímpares?

15



� Exemplos (não tão) didáticos:. ’na’ in ’banana’ =⇒ True. ’bat’ in ’superman’ =⇒ False. 3 ∈ {1, 2, 3, 4} =⇒ True. {1, 3} ⊂ números ímpares?. números primos ⊃ números ímpares?

15



� Exemplos (não tão) didáticos:. ’na’ in ’banana’ =⇒ True. ’bat’ in ’superman’ =⇒ False. 3 ∈ {1, 2, 3, 4} =⇒ True. {1, 3} ⊂ números ímpares?. números primos ⊃ números ímpares?

15



� Exemplos (não tão) didáticos:. ’na’ in ’banana’ =⇒ True. ’bat’ in ’superman’ =⇒ False. 3 ∈ {1, 2, 3, 4} =⇒ True. {1, 3} ⊂ números ímpares? =⇒ True. números primos ⊃ números ímpares?

15



� Exemplos (não tão) didáticos:. ’na’ in ’banana’ =⇒ True. ’bat’ in ’superman’ =⇒ False. 3 ∈ {1, 2, 3, 4} =⇒ True. {1, 3} ⊂ números ímpares? =⇒ True. números primos ⊃ números ímpares?

15



� Exemplos (não tão) didáticos:. ’na’ in ’banana’ =⇒ True. ’bat’ in ’superman’ =⇒ False. 3 ∈ {1, 2, 3, 4} =⇒ True. {1, 3} ⊂ números ímpares? =⇒ True. números primos ⊃ números ímpares? =⇒ False

16

Operadores Booleanos

� Vamos olhar um pouco mais afundo na comparação “maior ou igual”.� Por que 10 ≥ 10 é True?� Porque, na verdade, estamos fazendo dois testes ao mesmo tempo:

1 Estamos perguntando se 10 é MAIOR do que 10...2 ... ou se 10 é IGUAL a 10

� A expressão 10 ≥ 10 é verdadeira porque a segunda afirmação éverdadeira, mesmo a primeira sendo falsa.

� George Boole formalizou um conjunto de operações lógicas quepodem ser realizadas sobre expressões (valores) Booleanos:

. Disjunção, o “ou” lógico

. Conjunção, o “e” lógico

. Negação, o “não” lógico

� Vamos olhar cada uma dessas separadamente...

16










16










16










16










16










16










16










16










16










16










16










16










16










17

Disjunção :: Operadores Booleanos

� A operação lógica da disjunção é denotada pelo operador ∨.

� Dadas duas expressões lógicas P e Q, a disjunção P ∨Q é Truequando pelo menos uma das expressões P ou Q é True.

� Exemplos:. P : O número x é maior que 10.

Q: O número x é igual a 10.P ∨Q: O número x é maior OU igual a 10.

. P : O aluno z joga futebol.Q: O aluno z joga handebol.P ∨Q: O aluno z joga futebol OU ele joga handebol.

17







17







17







17







17







17







17







17







18

Conjunção :: Operadores Booleanos

� A operação lógica da conjunção é denotada pelo operador ∧.

� Dadas duas expressões lógicas P e Q, a conjunção P ∧Q é Truequando P e Q são True simultaneamente.

� Exemplos:. P : O número x é primo.

Q: O número x é par.P ∧Q: O número x é primo E ele é par.

. P : O login inserido pelo usuário é “celso”Q: A senha inserida pelo usuário é “paprica1234”P ∧Q: O login é “celso” E a senha é “paprica1234”

18







18







18







18







18







18







18







18







19

Negação :: Operadores Booleanos

� A operação lógica da negação é denotada pelo operador ¬.� Dadas uma expressões lógica P , a negação de P é denotada por¬P . Isto é, se P é True, então ¬P é False (e vice-versa).

� Exemplos:. P : O número x é igual a 20.¬P : O número x NÃO é igual a 20.

. P : O usuário k é um administrador.¬P : O usuário k NÃO é um administrador.

. P : ’na’ pertence à ’banana’¬P : ’na’ NÃO pertence à ’banana’

19






19






20

Tabelas Verdade

� A melhor forma de visualizar as operações lógicas e os seusresultados é utilizando Tabelas Verdade

P Q P ∨QF F FF T TT F TT T T

Disjunção

P Q P ∧QF F FF T FT F FT T T

Conjunção

P ¬PF TT FNegação

20

Tabelas Verdade



Disjunção


Conjunção


20

Tabelas Verdade



Disjunção


Conjunção


20

Tabelas Verdade



Disjunção


Conjunção


21

Controlando Fluxo de Algoritmos

22

Controlando o fluxo

� Ideia principal: utilizar expressões lógicas para controlar o fluxo deexecução de um algoritmo.

� Exemplos (pequenos) de aplicações:. Divisão por 0!. Movimentação do jogador!

� Exemplos (grandes) de aplicações:. Login/senha!

“Se o login inserido for correto E a senha inserida for correta, entãoo usuário tem acesso ao site.”“Caso contrário, mostre uma tela de login.”

. Acesso privilegiado!“Se o usuário NÃO tem permissão para realizar a operação, nãopermita-o e mostre um aviso.”“Caso contrário, realize a operação.”

22

Controlando o fluxo






22

Controlando o fluxo






22

Controlando o fluxo






22

Controlando o fluxo






22

Controlando o fluxo






22

Controlando o fluxo






23

Dúvidas?

Documents

Álgebra Booleana - Unicamp