Introdução à Computação Aula 08 - Algoritmos (Lógica de Programação, Álgebra Booleana)

# Introdução à Computação #

Aula 08 – ALGORITMOS

(Lógica de Programação, Álgebra Booleana)

Prof. Leinylson Fontinele Pereira

Na aula anterior...

ALGORITMOS# Sistemas de Numeração

# Aritmética Binária

11:01I.C.C.: Aula 08 – ALGORITMOS (Lógica de Programação, Álgebra Booleana)

Introdução

11:01 3I.C.C.: Aula 08 – ALGORITMOS (Lógica de Programação, Álgebra Booleana)

O que vamos aprender?

ALGORITMOS# Lógica de Programação

# Álgebra Booleana


Vamos começar?


Histórico

11:01

Gottfried Wilhelm Leibniz (1646-1716)

“A única maneira de garantir aconsistência de nossos raciocínios étorná-los tão tangíveis quanto os dosmatemáticos…”.

“Se duas pessoas discordarem, bastacalcular quem está certo”.

(The Art of Discovery, 1685)

I.C.C.: Aula 08 – ALGORITMOS (Lógica de Programação, Álgebra Booleana)

Leibniz

11:01

Primeiro a propor o sistema binário;

Criador do Cálculo (paralelamente a Newton);

Os princípios da lógica de Leibniz (e de toda sua filosofia) eram:

# (i) Todas as nossas idéias são formadas a partir de um pequeno número deidéias simples, que formam o alfabeto do pensamento humano;

# (ii) Idéias complexas procedem dessas idéias simples por uma combinaçãouniforme e simétrica, análoga à multiplicação aritmética.


Ideias de Leibniz

11:01

Com relação ao princípio (i), o número de ideias simples é bem maior do queLeibniz pensou;

Quanto a (ii), a lógica pode, de fato, ser situada em uma operação decombinação simétrica, mas tal operação é análoga também à adição, e não só àmultiplicação;

A Lógica Formal que surgiria no início do século XX exige também, no mínimo,negação unária e variáveis quantificadas sobre algum universo de discurso;

Leibniz não publicou nada em Lógica Formal durante sua vida; a maior partedo que ele escreveu no assunto consiste de rascunhos e trabalhos nãoterminados.


Histórico

11:01

George Boole (1815-1864)

Considerado um dosfundadores da Ciência daComputação


Ideias de Boole

11:01

Usar símbolos algébricos como x, y, z, p, q, r para denotar palavras, frases, ouproposições;

O que Boole estava pensando era em criar um sistema algébrico com operaçõescomo adição e multiplicação e métodos de resolução de equações;

A Álgebra de Boole exigia a formulação de uma linguagem simbólica dopensamento;

Resolver uma equação em tal linguagem não levaria a uma resposta numérica, massim a uma conclusão lógica.

Sua álgebra seria a “álgebra do pensamento”


Álgebra Booleana

11:01

Álgebra “Tradicional”:

# Variáveis representam números reais;

# Operadores são aplicados às variáveis e o resultado é um número real;

Álgebra Booleana:

# Variáveis representam apenas 0 ou 1

# Operadores retornam apenas 0 ou 1


Álgebra Booleana

11:01

x = jovem e y = faz Ciência da Computação;

Então (1 − 𝑥) iria então representar a operação de selecionar todas as coisasno mundo exceto jovens, isto é, todas as coisas que não são jovens;

(𝑥𝑦) representaria o conjunto dos jovens que fazem Ciência da Computação;

(1 − 𝑥) (1 − 𝑦) seria todas as coisas que não são jovens nem fazemCiência da Computação;

(𝑥 + 𝑦) seria o conjunto das coisas que são jovens ou que fazem Ciência daComputação.


Operações Booleanas Básicas


Operações Booleanas Básicas


Representação Diagramática


Operações Booleanas Derivadas


Definição da Álgebra de Boole

11:01

Conjunto de elementos B

Operações binárias:{. , +}

Operações unárias: { ` }, também pode ser utilizado o ‾

Regras de prioridade: ` , . , +

O conjunto B contém pelo menos dois elementos𝑎, 𝑏 sendo 𝑎 ≠ 𝑏


Álgebra de Boole de Dois Valores

11:01

O conjunto 𝐵 = {1, 0} e as operações lógicas OR, AND e NOT satisfazem osaxiomas da álgebra booleana?# AND (E)

• Símbolo: . ou nenhum

# OR (OU)

• Símbolo: +

# NOT (COMPLEMENTO)

• Símbolo: ` ou ‾

# Também são encontrados na literatura os seguintes símbolos:

AND (&, ^); OR , v); NOT(~, !)


Avaliando Equações Booleanas

11:01

Ex: “Eu irei almoçar se Maria ou João forem e se Célia não for.”

Suponha que F represente o meu comparecimento ao almoço# 1 significa presença, 0 indica ausência

Do mesmo modo# 𝑚 significa a presença de Maria, 𝑗 a de João e 𝑐 a de Célia

F = (m OR j) AND NOT(c)

F = (m + j) c’


Lógica Proposicional


A Lógica


Lógica


Origem da Lógica


Argumento Lógico


Argumento Lógico


Argumento

Se eu estudar, aprenderei PremissasEu estudei

Logo, eu aprendi Conclusão

Inferência Lógica


Inferência Lógica


Inferência Lógica


Princípios Lógicos


Lógica Proposicional


Proposições


O Que São Proposições?


Não São Proposições


Orações exclamativasQuero mais café!Bom dia!

Orações interrogativasICC é uma boa disciplina?Será que o Brasil ganha?

Orações imperativasCompre batom.Baixe o material da aula.

Sentenças abertas7 − 2𝑥 > 2Ele é um bom lutador.𝑥 − 2 = 5

ParadoxosSou mentiroso.Essa sentença é falsa.“A frase dentro desta aspa éuma mentira”

Frases sem verboA vida de Francisco.O rei do camarote.

A Linguagem da Lógica Proposicional


Letras Sentenciais


Proposições Simples (Atômicas)


Proposições Simples


Proposições Simples


Proposições Compostas (Molecular)


Proposições Compostas


Proposições Compostas (Molecular)


Conectivos Lógicos


Operador de Negação














Operador de Conjunção




























Operador de Disjunção




























Disjunção Exclusiva


Operador de Disjunção Exclusiva


















Operador de Condicional


Operador de Condicional


Operador Bicondicional










Mais exemplos


Mais exemplos


Mais exemplos


Mais exemplos


Mais exemplos


Uso dos Parênteses ( e )


Tabela Verdade de uma Proposição Composta


Ordem de Precedência dos Operadores


Construindo a Tabela Verdade










Tautologia


Tautologia


Tautologia


Tautologia


p (pq) é sempre verdadeira (uma tautologia) independentemente dos

valores verdade das subproposições envolvidas (p e q):

“se bananas são laranjas então bananas são laranjas ou bananas são bananas”

“se 2 = 2, então 2 = 2 ou 3 + 1 = 5”

Contradição


Contradição


Contradição


Contradição


Por exemplo, a fórmula (pq) (pq) configura uma contradição:

p q q (p q) (p q) (p q) (p q)

F F V V F F

F V F V F F

V F V F V F

V V F V F F

Contradição


Proposição falsa

“2 + 2 = 5”

Contradição

“2 + 2 = 5 𝑒 2 + 2 ≠ 5”

Contingência


Contingência


Contingência


Equivalência Lógica


Se duas proposições 𝑝, 𝑞 têm a mesma tabela verdade então 𝑝 é logicamente equivalente a 𝑞.

pq



Equivalência lógica entre proposições (pq) e pq

p q p q (p q ) (p q ) p q

F F V V F V V

F V V F F V V

V F F V F V V

V V F F V F F



Proposições verdadeiras, mas não logicamente equivalentes:

“2 + 5 = 7” 𝑒 “3 − 1 = 2”

Proposições verdadeiras e logicamente equivalentes:

“2 + 5 = 7 𝑜𝑢 3 − 1 = 2” 𝑒 “3 − 1 = 2 𝑜𝑢 2 + 5 = 7”

Regras Hipotéticas


Raciocínio hipotético: raciocínio baseado em hipóteses

# Uma suposição feita a fim de mostrar que uma conclusão segue da suposição

Regras Hipotéticas


Postulados e Teoremas


Atividade


Transcreva as sentenças para a linguagem do cálculo proposicional

Atividade


(1) Está chovendo.

(2) Não está chovendo.

(3) Está chovendo ou nevando.

(4) Está chovendo e nevando.

(5) Está chovendo, mas não está nevando

Atividade


(6) Não é o caso que está chovendo e nevando.

(7) Se não está chovendo, então está nevando.

(8) Não é o caso que se está nevando então está chovendo.

(9) Está chovendo somente se não está nevando.

(10) Está chovendo se e somente se não está nevando.

Atividade


(11) Não é o caso que está chovendo ou nevando.

(12) Se está nevando e chovendo, então está nevando.

(13) Se não está chovendo, então não é o caso que está nevando e chovendo.

(14) Ou está chovendo, ou está nevando e chovendo.

(15) Ou está chovendo e nevando, ou está nevando mas não está chovendo.

Atividade


A: Alice vai à festa.

B: Beatriz vai à festa.

C: Cláudia vai à festa.

D: Débora vai à festa.

Atividade


(16) Alice não vai à festa.

(17) Alice vai à festa, mas Beatriz não.

(18) Se Alice for à festa, entao Beatriz também irá.

(19) Alice vai à festa, se Beatriz também for.

(20) Alice vai à festa somente se Beatriz for.

Atividade


(21) Alice vai à festa se e somente se Beatriz for.

(22) Nem Alice nem Beatriz vão à festa.

(23) Não é o caso que Alice e Beatriz ambas irão à festa.

(24) Ou Alice vai à festa, ou Beatriz não vai.

(25) Alice não vai à festa, se Beatriz for.

Atividade


(26) Ou Alice vai à festa, ou Beatriz e Cláudia vão.

(27) Se Alice for à festa, então Beatriz e Débora também irão.

(28) Alice não vai à festa, mas Beatriz e Cláudia irão.

(29) Se Cláudia for à festa, então, se Alice não for à festa, Beatriz vai.

(30) Se nem Cláudia nem Beatriz forem à festa, então Alice irá.

Atividade


(31) Cláudia vai à festa somente se Alice e Beatriz não forem.

(32) Cláudia e Débora vão à festa, apesar de Alice e Beatriz não irem.

(33) Se Cláudia ou Beatriz forem à festa, então Alice vai à festa e Beatriz não vai.

(34) Cláudia e Beatriz vão à festa se e somente se Alice ou Débora forem.

(35) Se Débora for à festa, então Cláudia ou Alice irão, e se Débora não for, entãoAlice e Beatriz irão.

Material: https://sites.google.com/site/leinylsonuespi

11:01

Aula baseada no material de

Introdução ao Computador, Bernardo Gonçalves

Lógica Computacional, Prof. Rodrigo Baluz

Proposições simples, compostas e Princípios da lógicaproposicional, Fábio Reccanello

Toda a Matemática, Gustavo ViegasI.C.C.: Aula 08 – ALGORITMOS (Lógica de Programação, Álgebra Booleana)

Nesta aula aprendemos...

ALGORITMOS# Lógica de Programação

# Álgebra Booleana


Na próxima aula veremos...

ALGORITMOS# Simulando Operações com Portas Lógicas

# Aula Prática


Alguma Dúvida?

11:01

Até a próxima aula...

[email protected]

Education

Introdução à Computação Aula 08 - Algoritmos (Lógica de Programação, Álgebra Booleana)