Lógica para Computação

LUCIANA CONCEIÇÃO DIAS CAMPOSUFJF

EADDCC003-2011 .1

Lógica para Computação

O aprendizado da Lógica auxilia os estudantes no raciocínio, na compreensão de conceitos básicos, na verificação formal de programas e melhor os prepara para o entendimento do conteúdo de tópicos mais avançados.

Este material constitui uma INTRODUÇÃO À LÓGICA ELEMENTAR CLÁSSICA, procurando alcançar os objetivos gerais e específicos propostos pela disciplina Lógica para Computação.

Raciocínio Lógico

Proposição: É toda expressão, isto é, todo conjunto de palavras ou

símbolos, que possui um significado ao qual podemos atribuir um valor lógico.

Valor Lógico: É um valor atribuído a uma proposição lógica. Diz-se que o valor lógico de uma proposição é

“verdade” (representado por V) se a proposição é verdadeira e “falsidade” (representado por F) se a proposição é falsa.

Proposições Lógicas

Proposição: É toda expressão, isto é, todo conjunto de palavras ou

símbolos, que possui um significado ao qual podemos atribuir um valor lógico.

Proposições Lógicas

Princípio da não contradição e do 3o excluído :1. Princípio da não contradição

• Uma proposição não pode ser verdadeira e falsa ao mesmo tempo.

2. Princípio do 3o excluído• Toda proposição ou é verdadeira ou é falsa, isto

é, verifica-se sempre um destes casos e nunca um terceiro.

Assim, esses princípios afirmam que:• Toda proposição tem um, e um só, dos

valores: V ou F

c) e d) NÂO são exemplos de Proposições Lógicas-Porque Não são declarações e portanto não é possível atribuir um valor lógico para o seu significado.

a) e b) são exemplos de Proposições Lógicas- Porque elas têm sentido completo e é possível atribuir um valor lógico para o seu significado.

Proposições Lógicas

Exemplos:

a) A Lua é um satélite.

b) 2+3 = 5

c) Recife

d) Quem descobriu o Brasil?

a) e b) são exemplos de Proposições Lógicas

c) e d) NÂO são exemplos de Proposições Lógicas

Sentença Lógica e Proposição Lógica

Sentença Lógica é a maneira de expressar uma Proposição Lógica.

Portanto:Uma Proposição Lógica pode vir

representada por diferentes sentenças

Sentença Lógica e Proposição Lógica

Exemplos de sentenças lógicas:a) Dante escreveu Os Lusíadas.b) Não é verdade que Dante não escreveu

Os Lusíadas.Na letra a) a frase apresenta uma afirmação. Que tem o mesmo significado da letra b) onde a frase apresenta uma dupla negação.Logo, as duas sentenças lógicas representam a mesma proposição lógica.

Portanto ATENÇÃO:

Negar duas vezes é o mesmo que Afirmar.

Então:• Proposição é a idéia.• Sentença é a forma de se expressar essa idéia.

Representação de Proposição Lógica

Existem 3 maneiras de se representar uma Proposição Lógica:1. Linguagem Natural

• Carlos é Careca2. Forma Simbólica

• As proposições são designadas pelas letras latinas.

• Geralmente: p, q, r, s, etc.

Portanto p = Carlos é Careca

Representação de Proposição Lógica

Existem 3 maneiras de se representar uma Proposição Lógica:3. Diagrama/Gráfico Lógico:

• Seja A o conjunto dos carecas• Então a proposição p = Carlos é

careca é representada no diagrama:

pA Portanto

ATENÇÃO:Quem está no interior de A é careca.Já quem está fora de A não é careca.

Proposição simples X Proposição composta

Proposição SimplesChama-se proposição simples ou fórmula

atômica aquela que não contém nenhuma outra proposição como parte integrante de si mesma.

Geralmente utiliza-se letras latinas minúsculas para designar as proposições simples.

Exemplo:q: Pedro é estudanter: o número 25 é quadrado perfeito

p q

Proposição simples X Proposição composta

Proposição CompostaChama-se proposição composta ou fórmula

molecular aquela formada pela combinação de duas ou mais proposições.

Geralmente utiliza-se letras latinas maiúsculas para designar as proposições compostas.

Exemplo:Carlos é careca e Pedro é estudante

ProposiçãoSimples

S Proposição

Composta

Portanto:Uma proposição composta é a ligação ou

conexão de duas ou mais proposições simples com o objetivo de transmitir uma idéia ou fornecer um significado ao qual se atribui um valor lógico.

Proposição Composta

Valor Lógica de uma Proposição CompostaO valor lógico de qualquer proposição composta

depende unicamente dos valores lógicos das proposições simples componentes, ficando por eles univocamente determinado.

Geralmente, utiliza-se a tabela-verdade para verificar todos os possíveis valores lógicos de uma proposição composta.

Pelo princípio do terceiro excluído, sabemos que uma proposição simples é verdadeira ou falsa:

Tabela Verdade ou Tabela de Verdade

p

V

F

Valor Lógica de uma Proposição CompostaSe uma proposição é composta por n

proposições simples então teremos 2n atribuições possíveis.

Exemplo:O sol é uma estrela e a neve é branca.

Tabela Verdade ou Tabela de Verdade

p q

n = 2 então tem-se 22 = 4 atribuições

possíveis:

p q

V V 1ª combinação possível

V F 2ª combinação possível

F V 3ª combinação possível

F F 4ª combinação possível

Operações Lógicas são operações realizadas sobre proposições, obedecendo a regras de um cálculo denominado Cálculo Proposicional.

As proposições simples (também chamadas de fórmulas atômicas) podem ser combinadas entre si e, para representar tais combinações usaremos os conectivos lógicos.

Portanto, os conectivos lógicos são responsáveis pela formação de proposições a partir de proposições.

Operações Lógicas

As proposições podem ser conectadas através dos

seguintes conectivos :1. Negação (não ou NOT): ~ ou ! ou ¬2. Conjunção (“e” ou AND): ∧3. Disjunção (“ou” ou OR): ∨4. Disjunção Exclusiva (“ou exclusivo” ou

XOR): 5. Condicional ( “implica” ou “se-então”): →6. Bi-condicional ( “se e somente se”):

Conectivos Lógicos

1. Negação (não ou NOT): ~ ou ! ou ¬

Conectivos Lógicos

Seja A o conjunto de estudantes.

A

Seja a proposiçãop: Pedro é estudante.pEntão, a negação de p é dado por ~p: Pedro não é estudante.

~p

p ~p

A tabela verdade é dada por:Se p for verdadeiro, então ~p é

falso

FV

FV

F V

Se p for falso, então ~p é verdadeiro F V

2. Conjunção (“e” ou AND): ∧

Conectivos Lógicos

Sejam as proposições simples:p: O sol é uma estrela.q: Roma é um país.

A conjunção dessas proposições forma a seguinte proposição composta:R: O sol é uma estrela e Roma é um país.R = p ∧ q

O valor da conjunção é dado pela tabela verdade:

p q p ∧ q

A representação da conjunção por diagrama lógico:

p qA B

R

Interseção de A e B:

A ∩ B

A região em que as duas proposições são verdadeiras é na interseção dos conjuntos A e B.

V

V V

V V 1ª combinação.

12 34

2. Conjunção (“e” ou AND): ∧

Conectivos Lógicos

Sejam as proposições simples:p: O sol é uma estrela.q: Roma é um país.

A conjunção dessas proposições forma a seguinte proposição composta:R: O sol é uma estrela e Roma é um país.R = p ∧ q

O valor da conjunção é dado pela tabela verdade:

p q p ∧ q

A representação da conjunção por diagrama lógico:

p qA B

R

Interseção de A e B:

A ∩ B

V

V V

V V 1ª combinação.

V F V F 2ª combinação.

No conjunto A apenas p é verdadeiro. Como está fora da região de interseção, a conjunção é falsa.

F12 3

4

2. Conjunção (“e” ou AND): ∧

Conectivos Lógicos

Sejam as proposições simples:p: O sol é uma estrela.q: Roma é um país.

A conjunção dessas proposições forma a seguinte proposição composta:R: O sol é uma estrela e Roma é um país.R = p ∧ q

O valor da conjunção é dado pela tabela verdade:

p q p ∧ q

A representação da conjunção por diagrama lógico:

p qA B

R

Interseção de A e B:

A ∩ B

V

V V

V V 1ª combinação.

V F V F 2ª combinação.FVF

F 3ª combinação.VNo conjunto B apenas q é verdadeiro. Fora da região de interseção, a conjunção é falsa.

F12 34

2. Conjunção (“e” ou AND): ∧

Conectivos Lógicos

Sejam as proposições simples:p: O sol é uma estrela.q: Roma é um país.

A conjunção dessas proposições forma a seguinte proposição composta:R: O sol é uma estrela e Roma é um país.R = p ∧ q

O valor da conjunção é dado pela tabela verdade:

p q p ∧ q

A representação da conjunção por diagrama lógico:

p qA B

R

Interseção de A e B:

A ∩ B

V

V V

V V 1ª combinação.

V F V F 2ª combinação.FVF

F 3ª combinação.V F

Fora dos conjuntos A e B as proposições p e q são falsas. Fora da interseção, a conjunção é falsa.

F

F F

F F 4ª combinação.4

12 3

p qA B

A representação da disjunção por diagrama lógico:

R

União de A e B:A B

p q

3. Disjunção (“ou” ou OR): ∨

Conectivos Lógicos

Sejam as proposições simples:p: O enxofre é verde.q: 7 é um número primo.

A disjunção dessas proposições forma a seguinte proposição composta:R: O enxofre é verde ou 7 é um número primo.R = p ∨ q

O valor da disjunção é dado pela tabela verdade:

p q p ∨ q

A região onde as duas proposições são verdadeiras está dentro da união dos conjuntos A e B.

VV V 1ª combinação.

V V12 3

4

p qA B

A representação da disjunção por diagrama lógico:

R

União de A e B:A B

p q

3. Disjunção (“ou” ou OR): ∨

Conectivos Lógicos

Sejam as proposições simples:p: O enxofre é verde.q: 7 é um número primo.

A disjunção dessas proposições forma a seguinte proposição composta:R: O enxofre é verde ou 7 é um número primo.R = p ∨ q

O valor da disjunção é dado pela tabela verdade:

p q p ∨ q

VV V 1ª combinação.

V VV F V F 2ª combinação.

No conjunto A apenas p é verdadeiro. Como está dentro da região de união, a disjunção é verdadeira.

V12 3

4

p qA B

A representação da disjunção por diagrama lógico:

R

União de A e B:A B

p q

3. Disjunção (“ou” ou OR): ∨

Conectivos Lógicos

Sejam as proposições simples:p: O enxofre é verde.q: 7 é um número primo.

A disjunção dessas proposições forma a seguinte proposição composta:R: O enxofre é verde ou 7 é um número primo.R = p ∨ q

O valor da disjunção é dado pela tabela verdade:

p q p ∨ q

VV V 1ª combinação.

V VV F V F 2ª combinação.VVF

F 3ª combinação.VNo conjunto B apenas q é verdadeiro. Dentro da união a disjunção é verdadeira.

V12 34

p qA B

A representação da disjunção por diagrama lógico:

R

União de A e B:A B

p q

3. Disjunção (“ou” ou OR): ∨

Conectivos Lógicos

Sejam as proposições simples:p: O enxofre é verde.q: 7 é um número primo.

A disjunção dessas proposições forma a seguinte proposição composta:R: O enxofre é verde ou 7 é um número primo.R = p ∨ q

O valor da disjunção é dado pela tabela verdade:

p q p ∨ q

VV V 1ª combinação.

V VV F V F 2ª combinação.VVF

F 3ª combinação.V V

Fora dos conjuntos A e B as proposições p e q são falsas. Fora da união, a disjunção é falsa.

F

FF

F F 4ª combinação.

12 34

p qA B

A representação da disjunção exclusiva por diagrama lógico:

R

Não inclui a interseção entre os

conjuntos A e B

Rp q

4. Disjunção Exclusiva (“ou exclusivo” ou XOR):

Conectivos Lógicos

Sejam as proposições simples:p: O cachorro é fêmea.q: O cachorro é macho.

A disjunção exclusiva dessas proposições forma a seguinte proposição composta:R: ou o cachorro é fêmea ou o cachorro é macho.R = p q

O valor da disjunção exclusiva é dado pela tabela verdade:p q p q

No ou exclusivo ou o elemento pertence ao conjunto A ou ao B. Nunca pertence aos dois conjuntos ao mesmo tempo.

FV V 1ª combinação.

V V12 3

4

p qA B

A representação da disjunção exclusiva por diagrama lógico:

R

Não inclui a interseção entre os

conjuntos A e B

Rp q

4. Disjunção Exclusiva (“ou exclusivo” ou XOR):

Conectivos Lógicos

Sejam as proposições simples:p: O cachorro é fêmea.q: O cachorro é macho.

A disjunção exclusiva dessas proposições forma a seguinte proposição composta:R: ou o cachorro é fêmea ou o cachorro é macho.R = p q

O valor da disjunção exclusiva é dado pela tabela verdade:p q p q

FV V 1ª combinação.

V V12 3

4

V F V F 2ª combinação.

No conjunto A apenas p é verdadeiro. Como apenas um elemento é verdadeiro, a disjunção exclusiva é verdadeira.

V

p qA B

A representação da disjunção exclusiva por diagrama lógico:

R

Não inclui a interseção entre os

conjuntos A e B

Rp q

4. Disjunção Exclusiva (“ou exclusivo” ou XOR):

Conectivos Lógicos

Sejam as proposições simples:p: O cachorro é fêmea.q: O cachorro é macho.

A disjunção exclusiva dessas proposições forma a seguinte proposição composta:R: ou o cachorro é fêmea ou o cachorro é macho.R = p q

O valor da disjunção exclusiva é dado pela tabela verdade:p q p q

FV V 1ª combinação.

V V12 3

4

V F V F 2ª combinação.VVF

F 3ª combinação.VNo conjunto B apenas q é verdadeiro. Portanto a disjunção exclusiva é verdadeira.

V

p qA B

A representação da disjunção exclusiva por diagrama lógico:

R

Não inclui a interseção entre os

conjuntos A e B

Rp q

4. Disjunção Exclusiva (“ou exclusivo” ou XOR):

Conectivos Lógicos

Sejam as proposições simples:p: O cachorro é fêmea.q: O cachorro é macho.

A disjunção exclusiva dessas proposições forma a seguinte proposição composta:R: ou o cachorro é fêmea ou o cachorro é macho.R = p q

O valor da disjunção exclusiva é dado pela tabela verdade:p q p q

FV V 1ª combinação.

V V12 3

4

V F V F 2ª combinação.VVF

F 3ª combinação.V V

Fora dos conjuntos A e B as proposições p e q são falsas. Assim, a disjunção exclusiva é falsa.

F

FF

F F 4ª combinação.

5. Condicional ( “implica” ou “se-então”): →

Conectivos Lógicos

Sejam as proposições simples:p: Pedro estuda.q: Pedro foi aprovado.

A condicional dessas proposições forma a seguinte proposição composta:R: Se Pedro estudar então ele será aprovado.R = p → q

O valor da condicional é dado pela tabela verdade:

p q p → q

• p é dito antecedente da condicional.• q é dito conseqüente da condicional.

10 caso: Pedro estudou e foi aprovado.

V V

A condicional obriga que Se Pedro estudar ele terá que ser aprovado, então podemos concluir que a condicional é verdadeira.

V

Isto é, se é verdade que Pedro estudou, então necessariamente é verdade que ele será aprovado.

5. Condicional ( “implica” ou “se-então”): →

Conectivos Lógicos

Sejam as proposições simples:p: Pedro estuda.q: Pedro foi aprovado.

A condicional dessas proposições forma a seguinte proposição composta:R: Se Pedro estudar então ele será aprovado.R = p → q

O valor da condicional é dado pela tabela verdade:

p q p → q

• p é dito antecedente da condicional.• q é dito conseqüente da condicional.

V V V

20 caso: Pedro estudou e não foi aprovado.

V F

A condicional afirma que o fato de Pedro ter estudado é condição suficiente para que se torne um resultado necessário que ele seja aprovado. Caso isso não ocorra, a condicional é falsa.

F

5. Condicional ( “implica” ou “se-então”): →

Conectivos Lógicos

Sejam as proposições simples:p: Pedro estuda.q: Pedro foi aprovado.

A condicional dessas proposições forma a seguinte proposição composta:R: Se Pedro estudar então ele será aprovado.R = p → q

O valor da condicional é dado pela tabela verdade:

p q p → q

• p é dito antecedente da condicional.• q é dito conseqüente da condicional.

V V V

V F F

30 caso: Pedro não estudou e foi aprovado.

F V

A condição suficiente para q é p, nada é dito em relação a ~p. Por isso, a condicional é verdadeira.

V

5. Condicional ( “implica” ou “se-então”): →

Conectivos Lógicos

Sejam as proposições simples:p: Pedro estuda.q: Pedro foi aprovado.

A condicional dessas proposições forma a seguinte proposição composta:R: Se Pedro estudar então ele será aprovado.R = p → q

O valor da condicional é dado pela tabela verdade:

p q p → q

• p é dito antecedente da condicional.• q é dito conseqüente da condicional.

V V V

V F F

F V V

40 caso: Pedro não estudou e não foi aprovado.

F F

Como a condição é fundamentada em p e não em ~p, a condicional é verdadeira.

V

A representação da condicional por diagrama lógico:

p qA BR

q

Não é válida a região onde o conseqüente é falso.

5. Condicional ( “implica” ou “se-então”): →

Conectivos Lógicos

Sejam as proposições simples:p: Pedro estuda.q: Pedro foi aprovado.

A condicional dessas proposições forma a seguinte proposição composta:R: Se Pedro estudar então ele será aprovado.R = p → q

O valor da condicional é dado pela tabela verdade:

p q p → q

• p é dito antecedente da condicional.• q é dito conseqüente da condicional.

V V V

V F F

F V V

F F V

12 34

5. Bi-condicional ( “se e somente se”):

Conectivos Lógicos

Sejam as proposições simples:p: Tales é filho de Wilson.q: Tales é neto de Pedro.

O valor da bi-condicional é dado pela tabela verdade:

p q p q

• p é dito condição necessária e suficiente para q.• q é dito condição necessária e suficiente para p.Portanto, a bi-condicional será verdadeira quando antecedente e conseqüente forem ambos verdadeiros, ou quando forem ambos falsos. Logo, a bi-condicional será falsa somente quando os valores lógicos das duas proposições que a compõem forem diferentes.

A bi-condicional dessas proposições forma a seguinte proposição composta:R: Tales é filho de Wilson se e somente se ele for neto de Pedro.R = p q

V V V

V F F

F V F

F F V

5. Bi-condicional ( “se e somente se”):

Conectivos Lógicos

Sejam as proposições simples:p: Tales é filho de Wilson.q: Tales é neto de Pedro.

O valor da bi-condicional é dado pela tabela verdade:

p q p q

A bi-condicional dessas proposições forma a seguinte proposição composta:R: Tales é filho de Wilson se e somente se ele for neto de Pedro.R = p q

V V V

V F F

F V F

F F V

A representação da bi-condicional por diagrama lógico:

p qA BR

Não são válidas as regiões onde o antecedente ou o conseqüente é

falso.