LÓGICA PARA COMPUTAÇÃO

Prof.ª Me. Edvania Gimenes de Oliveira Godoy

1
 LÓGICA PARA COMPUTAÇÃO

1. Lógica Matemática.

2. Teoria dos Conjuntos.

3. Relações.

4. Funções.

5. Aplicações à Computação.

2
 Lógica Matemática
• Lógica:
Lógica é a ciência do raciocínio.

• A Lógica provê regras e técnicas para

determinar se um dado argumento é válido.

• Lógica Matemática é o uso da lógica formal

para estudar o raciocínio matemático.
3
 Lógica Proposicional

• Proposição:
É toda expressão que encerra um pensamento
de sentido completo e pode ser classificada
como V (verdadeira) ou F (falsa).

Valor lógico de uma proposição: Se p é uma

proposição, então V(p)=V ou V(p)=F.

4
 Lógica Proposicional

Exemplos de proposições:

• O Sol gira em torno da Terra.

• -1 < 0.

• O morcego é um mamífero e o pinguim uma ave.

• As nuvens são feitas de algodão.

• O 27º dígito da expansão decimal de 5 é 8.

5
 Lógica Proposicional

Não são proposições:

• Onde fica este endereço?

• Parabéns!

• Faça a pesquisa.

6
 Princípios Básicos das Proposições

I. Princípio da não contradição:

Uma proposição não pode ser verdadeira e falsa
simultaneamente.

II. Princípio do terceiro excluído:

Toda proposição ou é verdadeira ou é falsa; não
existe um terceiro valor lógico.

7
 Proposições simples e compostas

• “A impressora está ligada.” (prop. simples)

• “A impressora está ligada e está com tinta

suficiente para a impressão.” (prop. composta)

• “Se a impressora está ligada, então vou

imprimir o documento.” (prop. composta)

8
 Notações

• Proposições simples: 𝑝, 𝑞, 𝑟, 𝑠, …

• Proposições compostas: 𝑃, 𝑄, 𝑅, 𝑆, …

9
Conectivos Lógicos

10
 Conectivos Lógicos

p, q proposições

11
 Negação
• Negação de uma proposição p: ∼p
• Lê-se: “não p”
• Pode-se prefixar a proposição p por: “não é verdade
que” (ou equivalente).

Exemplo:
p: Carlos é mecânico.
∼ p: Carlos não é mecânico.
∼ p: Não é verdade que Carlos é mecânico.

12
 Tabela Verdade

Descreve os valores lógicos de uma proposição em

termos das combinações dos valores lógicos das
proposições componentes e dos conetivos usados.

Disponível em : www.colegioweb.com.br
13
Tabela Verdade para a Negação

14
 Conjunção
• 𝑝 ∧ 𝑞 : “𝑝 e 𝑞”. (∧ ∶ and)
• Reflete noção de simultaneidade.

Valor Lógico da conjunção:

• Verdadeira, apenas quando p e q são

simultaneamente verdadeiras.

• Falsa, em qualquer outro caso.

15
 Conjunção

Exemplos:

1. Windows é um sistema operacional e Pascal uma

linguagem de programação. (Valor verdade: V)

2. Windows é um editor de textos e Pascal uma

linguagem de programação. (Valor verdade: F)

16
Tabela Verdade da Conjunção

17
 Disjunção
• 𝑝 ∨ 𝑞 : 𝑝 ou 𝑞. (∨ ∶ or)
• Reflete noção de “pelo menos uma”.

Valor Lógico da disjunção:

• Verdadeira, quando pelo menos uma das
proposições é verdadeira.
• Falsa, apenas quando 𝑝 e 𝑞 são
simultaneamente falsas.
18
Tabela Verdade da Disjunção

19
 Disjunção

Exemplos:

1. Windows é um sistema operacional ou

Pascal é uma planilha eletrônica. (Valor
verdade: V)

2. Windows é um editor de textos ou Pascal é

uma planilha eletrônica. (Valor verdade: F)
20
 Disjunção Exclusiva
𝑝 ∨ 𝑞 : 𝑝 ou 𝑞, mas não ambos.
Exemplo: “Irei de ônibus ou bicicleta.”

Tabela Verdade da Disjunção Exclusiva

𝒑 𝒒 𝒑∨𝒒

V V F

V F V

F V V

F F F
21
 Condicional
• Condicional de duas proposições p e q :
𝑝⟶𝑞
Lê-se: “se 𝑝, então 𝑞”.

p: hipótese ou antecedente.
q: conclusão ou consequente.
p é condição suficiente para q.
q é condição necessária para p.

Valor Lógico de 𝑝 → 𝑞:
• Falsa, quando p é verdadeira e q é falsa.
• Verdadeira, nos outros casos.
22
 Tabela Verdade da Condicional

Ex: Se Ana passar no concurso, então fará uma festa.

23
 Bicondicional
• Bicondicional de duas proposições 𝑝 e 𝑞 :

𝑝⟷𝑞

Lê-se: “𝑝 se, e somente se, 𝑞”.

p é condição necessária e suficiente para q.

q é condição necessária e suficiente para p.

• Reflete a noção de condição nos dois sentidos.

• Falsa, quando V(p) ≠ V(q).
• Verdadeira, caso contrário.
24
 Tabela Verdade da Bicondicional

Ex: Ana fará uma festa se, e somente se, passar no

concurso.
25
 Fórmula bem formulada
• Fórmula bem formulada (fbf): é uma cadeia que
forma uma expressão válida.

Exemplos:

1) 𝑝 ∨ 𝑞 ∧ 𝑟 → 𝑟 ∧ (¬𝑝 ↔ 𝑞) fbf

2) ¬𝑝 → (↔ 𝑟 ∨ ¬ não é fbf

26
Ordem de precedência para conectivos
lógicos:
1 ( ) Parênteses internos
2 ∼ Negação
3 ∧ Conjunção
4 ∨ Disjunção
5 ⟶ Condicional
6 ⟷ Bicondicional
27
 Exemplos:

1) ∼ 𝑝 ∧ 𝑞 significa (∼ 𝑝) ∧ 𝑞 e não ∼ 𝑝 ∧ 𝑞 .
Aqui o conectivo principal (último a ser
aplicado) é ∧.

2) 𝑝 ∨ 𝑞 ⟶ 𝑟 significa 𝑝 ∨ 𝑞 ⟶ 𝑟.
Aqui o conectivo principal é ⟶.

3) 𝑝 ∧ (𝑞 ⟷ 𝑟) ∨ (𝑝 ⟶∼ 𝑞)
Aqui o conectivo principal é ∨.
(Observemos a necessidade dos parênteses para
estabelecer a ordem).
28
 Tabela Verdade para
Proposições Compostas
Exemplos: Construir a tabela verdade de:
1) ( 𝑝 ∨∼ 𝑞) ⟶ 𝑝

29
 Tabela Verdade para
Proposições Compostas
• Tabela verdade de ( 𝑝 ∨∼ 𝑞) ⟶ 𝑝:

30
 Tabela Verdade para
Proposições Compostas

2) ∼ (𝑝 ⟶∼ 𝑞)

31
 Tautologias
• Proposição que é sempre verdadeira,
independente dos valores de seus
componentes.
Exemplo: 𝒑 ∨∼ 𝒑

32
 Contradições
• Proposição que é sempre falsa em todas
as situações possíveis.
Exemplo: 𝒑 ∧ ¬𝒑

33
 Contingências
Uma proposição composta que não é nem
uma tautologia, nem uma contradição, é
denominada contingência.
Exemplo: (𝒒 ⟶ 𝒑) ⟶ (𝒑 ⟶ 𝒒)

34
 Equivalências Lógicas

As proposições P e Q são logicamente

equivalentes ( 𝑃 ≡ 𝑄 ou 𝑃 ⟺ 𝑄 ) se, e
somente se, 𝑷 ↔ 𝑸 for tautologia.

35
 Equivalências Lógicas
• Exemplo:
Verificar que (𝑝 → 𝑞) ≡ (¬𝑞 ⟶ ¬𝑝).
(𝒑 → 𝒒) ⟷ (¬𝒒 ⟶ ¬𝒑)
V V V V F V F
V F F V V F F
F V V V F V V
F V F V V V V
1 4 1 6 2 5 3

36
 Equivalências Lógicas

Logo, um condicional (𝑝 → 𝑞) é logicamente

igual à sua contrapositiva (¬𝑞 → ¬𝑝).
Assim, a proposição condicional

“Se está calor, então é verão”

é equivalente a:

“Se não é verão, então não está calor ”.

37
Equivalências Lógicas Importantes

38
 Equivalências Lógicas
• Leis de Implicação:
1. (𝒑 ⟶ 𝒒) ≡ (∼ 𝒒 ⟶∼ 𝒑)

“Se as regras existem, então tem que ser cumpridas”.

p q
≡

“Se as regras não são cumpridas, então não existem”.

39
 Equivalências Lógicas
2. (𝒑 ⟶ 𝒒) ≡ ∼ 𝒑 ∨ 𝒒

“Se as regras existem, então tem que ser cumpridas”.

“As regras não existem ou tem que ser cumpridas”.

40
 Equivalências Lógicas
3. ∼ 𝒑 ⟶ 𝒒 ≡ 𝒑 ∧∼ 𝒒
(Negação de uma condicional)

“Não é verdade que se as regras existem, então

tem que ser cumpridas”.
≡

“As regras existem e não tem que ser

cumpridas”.

41
 Implicações Lógicas

Dizemos que 𝑝 implica logicamente 𝑞

(𝑝 ⟹ 𝑞)

se 𝑝 ⟶ 𝑞 é uma tautologia.

42
 Implicações Lógicas

𝑝∧𝑞

43
 Implicações Lógicas
1. “Se chover, o desfile será cancelado.
O desfile não foi cancelado.
Logo, não choveu.”

Aplicação da regra Modus Tollens

[ 𝑝 ⟶ 𝑞 ∧∼ 𝑞 ⟹ ∼ 𝑝]

44
 Implicações Lógicas
2. Abacaxis são peixes solitários ou polinômios
verdes são felizes.
Mas abacaxis não são peixes solitários!
Logo, polinômios verdes são felizes.

Aplicação da regra de inferência Silogismo

Disjuntivo:
𝑝 ∨ 𝑞 ∧∼ 𝑝 ⟹ 𝑞.

Observamos que no cálculo proposicional o que

dever ser considerado é a forma do enunciado e não
o significado que esta alcança no mundo real.
45
Argumentos

46
 Argumento Válido
𝑃1 ∧ 𝑃2 ∧ 𝑃3 ∧ ⋯ ∧ 𝑃𝑛 ⟹ 𝑄.

Exemplo:
Se é cobra, tem asas. (Premissa 𝑃1 ) (F)
A sucuri é uma cobra. (Premissa 𝑃2 ) (V)
Logo, a sucuri tem asas. (Conclusão Q) (F)

𝑝 ⟶ 𝑞, 𝑝 ⊢ 𝑞 (𝑀𝑜𝑑𝑢𝑠 𝑃𝑜𝑛𝑒𝑛𝑠)

Argumento válido com uma das premissas falsa e conclusão

falsa.

47
 Argumento Válido
• Argumento inválido: a conclusão não decorre
das premissas.

Exemplo:

Todos os cavalos são vertebrados. (premissa V)

Todos os cavalos são mamíferos. (premissa V)
Portanto, todos os vertebrados são mamíferos.
(conclusão F)

48
 Método Dedutivo
• Podemos verificar a validade de um
argumento usando tabela verdade, ou pelo
método dedutivo.

• Método para obter a conclusão de um

argumento a partir das premissas e de
uma cadeia de equivalências e inferências
que atuam sobre as hipóteses, criando
novas proposições até que se obtenha a
tese, provando o resultado.

49
 Método Dedutivo
Exemplos:
1) Prove que ¬𝐴 ∧ 𝐴 ∨ 𝐵 ⟹ 𝐵 usando o
método dedutivo:

1. ¬𝐀 Hipótese 1
2. 𝐀∨𝐁 Hipótese 2
3. 𝐁 1, 2, Silogismo Disjuntivo

50
 Método Dedutivo
2) Use o método dedutivo para provar que
(∼ 𝑝 → 𝑞) ∧ (𝑞 → 𝑟) ∧∼ 𝑟 ⇒ 𝑝.

1. ∼𝑝→𝑞 Hipótese 1
2. 𝑞→𝑟 Hipótese 2
3. ∼𝑟 Hipótese 3
4. ∼𝑞 2, 3, Modus Tollens
5. ∼ (∼ 𝑝) 1, 4, Modus Tollens
6. 𝒑 5, Dupla negação

51
 QUANTIFICADORES E PREDICADOS

• Lógica Proposicional: insuficiente para

simbolizar qualquer tipo de expressão.

Exemplo: “Todo número é positivo”

é uma proposição verdadeira sobre os inteiros

positivos, mas não pode ser simbolizada
usando apenas letras de proposição,
parênteses e conectivos lógicos.
"𝑥 > 0" ⟶ 𝑠𝑒𝑛𝑡𝑒𝑛ç𝑎 𝑎𝑏𝑒𝑟𝑡𝑎.
52
 Predicados
𝑃 𝑥 : representa alguma propriedade ou predicado
associado a uma variável 𝑥.
Exemplos:

Afirmação Variáveis Predicado Valor verdade

𝑥 é divisível por 2 𝑥 𝑃 𝑥 é a propriedade 𝑃 13 é F
que 𝑥 é divisível por 2. 𝑃 38 é V
𝑥>𝑦 𝑥, 𝑦 𝑄(𝑥, 𝑦) é a propriedade 𝑄 9, 4 é V
que 𝑥 é maior que 𝑦 𝑄(11, 30) é F.
𝑥 é mãe de 𝑦 𝑥, 𝑦 𝑅 𝑥, 𝑦 é a propriedade
que 𝑥 é mãe de 𝑦.

53
 Quantificadores
• Quantificador universal: ∀
• Lê-se: “para todo” , “para qualquer”
∀𝑥 𝑃(𝑥)
Exemplo: 𝑈 = universo dos seres vivos.
𝑃 𝑥 : 𝑥 é 𝑚𝑎𝑚í𝑓𝑒𝑟𝑜.
(∀𝑥)𝑃(𝑥)
“Para todo 𝑥, 𝑥 é um mamífero”.
Ou: Todo ser vivo é um mamífero. (F)
54
 Quantificadores
• Quantificador Existencial: ∃
• Lê-se: “existe um”; “existe algum”; “há pelo
menos um”; “para algum”.
∃𝑥 𝑃(𝑥)
Considerando o exemplo anterior,
(∃𝑥)𝑃(𝑥):
Existe um 𝑥 tal que 𝑥 é mamífero,
Ou:
Existe um ser vivo que é mamífero. (V)
55
 Quantificadores
Exemplo:
Domínio: universo das pessoas.
𝑇 𝑥 = 𝑥 é 𝑡ã𝑜 𝑟á𝑝𝑖𝑑𝑜 𝑞𝑢𝑎𝑛𝑡𝑜 𝑢𝑚𝑎 𝑡𝑎𝑟𝑡𝑎𝑟𝑢𝑔𝑎.
𝑉 𝑥 = 𝑥 é 𝑣𝑒𝑙𝑜𝑧.
𝐶 𝑥 = 𝑥 é 𝑐𝑖𝑐𝑙𝑖𝑠𝑡𝑎.

a) Todos os ciclistas são velozes.

∀𝑥 𝐶 𝑥 ⟶ 𝑉 𝑥 .

b) Alguns ciclistas velozes são tão rápidos quanto

uma tartaruga.
∃𝑥 𝐶 𝑥 ∧ 𝑉 𝑥 ∧ 𝑇(𝑥) .

56
 Quantificadores

c) ∀𝑥 𝑉 𝑥 ⟶ 𝑇 𝑥 ∧∼ 𝐶 𝑥 .
Toda pessoa que é veloz é mais rápida que
uma tartaruga e não é ciclista.

57
 Negação de sentenças
quantificadas

∼ ∀𝒙 𝑷 𝒙 ≡ (∃𝒙)(∼ 𝑷(𝒙))

∼ ∃𝒙 𝑷 𝒙 ≡ (∀𝒙)(∼ 𝑷(𝒙))

58
 Negação de
sentenças quantificadas
Exemplos:

1. “Existem funcionários não cadastrados.”

Negação:
“Todos os funcionários estão cadastrados.”

59
 Negação de
sentenças quantificadas
“Todos aplicativos são práticos e eficientes”
∀𝑥 𝐴 𝑥 ⟶ 𝑃 𝑥 ∧ 𝐸(𝑥)
Negação:
“Nem todos os aplicativos são práticos e
eficientes” ∼ [ ∀𝑥 𝐴 𝑥 ⟶ 𝑃 𝑥 ∧ 𝐸(𝑥) ]
ou
“Existem aplicativos que não são práticos ou
não são eficientes.”
∃𝑥 𝐴 𝑥 ∧ (∼ 𝑃 𝑥 ∨∼ 𝐸(𝑥)

60
 LÓGICA PARA COMPUTAÇÃO

Prof.ª Me. Edvania Gimenes de Oliveira Godoy

61