Aula 01 - Introducao a Logica Matematica

Prévia do material em texto

Aula 01
Introdução à Lógica Matemática
Disciplina: Fundamentos de Lógica e Algoritmos
Professora: Alba Lopes
alba.lopes@ifrn.edu.br
http://docente.ifrn.edu.br/albalopes
mailto:alba.lopes@ifrn.edu.br
http://docente.ifrn.edu.br/albalopes
Proposições
 Proposição – o que é isso?
 Uma proposição é uma declaração (afirmativa ou negativa) que é 
VERDADEIRA ou FALSA
 Quando ela é verdadeira, seu valor lógico é V
 Quando ela é falsa, seu valor lógico é F
 Uma pergunta é uma proposição?
 NÃO!
 Uma pergunta não possui valor lógico (verdadeiro ou falso)
Proposições
 ABERTAS ou FECHADAS
 Fechadas: valor lógico definido
 Dilma é Presidente do Brasil
 Natal é a capital da Paraíba
 Pedrinho é filho de Maria
 Abertas
 x + 1 = 4
Para x = 3, a proposição é verdadeira
Para qualquer outro valor de x ≠ 3, a proposição é falsa
Geralmente, as proposições são simbolizadas pelas letras: p, q, r, s, ...
Proposições Simples ou Compostas
 SIMPLES 
 Também chamada de atômica
 Não contem nenhuma outra proposição como parte integrante
 São simbolizadas pelas letras minúsculas: p, q, r, s, ...
 p : Carlos é careca
 q: Pedro é estudante
 COMPOSTA
 Também chamada de molécula
 Formada pela composição de duas ou mais proposições
 Simbolizadas pelas letras maiúsculas: P, Q, R, S, ...
 P: Carlos é careca e Pedro é estudante
 R: Se Carlos é careca, então é infeliz
Conectivos
 Palavras que são usadas para formar novas proposições
 P: O número 6 é par e o número 7 é ímpar
 Q: O triângulo ABC é retângulo ou é isósceles
 R: Não está chovendo
 S: Se Jorge é engenheiro, então sabe matemática
 T: O triângulo ABC é equilátero se e somente se é equitângulo
 Os conectivos usuais na Lógica Matemática são as palavras grifadas
 “e”, “ou”, “não”, “se...então”, “...se e somente se...”
Símbolos
Conectivo Símbolo Exemplo
não ~ ou ¬ ~p , ¬p
e ^ ou . p ^ q
Ou v ou + p v q
se...então  p  q
... se e somente se ...  p  q
Tradução para a linguagem 
natural
 Dadas as proposições:
 p : Carlos é careca
 q: Pedro é estudante
 Transformar em linguagem natural as seguintes fórmulas:
 ~p
 ~p v q
 p ^ ~q
 q  ~p
 ~p  ~q
Tradução para a linguagem 
natural
 Dadas as proposições:
 p : Carlos é careca
 q: Pedro é estudante
 Transformar em linguagem natural as seguintes fórmulas:
 ~p: Carlos não é careca
 ~p v q: Carlos não é careca ou Pedro é estudante
 p ^ ~q: Carlos é careca e Pedro não é estudante
 q  ~p: Se Pedro é estudante então Carlos não é careca
 ~p  ~q: Carlos não é cara se e somente se Pedro não é estudante
Exercícios
 Sejam as proposições
 p: Gosto de viajar 
 q: Visitei a Austrália.
 Escreva as sentenças verbais que estão representadas pelas 
proposições abaixo:
1. p  q : Gosto de viajar se e somente se Visitei a Austrália
2. ~q  ~p : Se não visitei a Australia então não gosto de viajar
3. (p ^~q)  ~p: 
1. Se Gosto de Viajar e não visitei Australia então Não gosto de viajar
4. q ^ ~p: Visitei a Australia e não gosto de viajar
5. ~p v ~q: Não gosto de viajar ou não visitei a Australia
6. (p v ~q) ^(~p  q)
Gosto de viajar ou não visitei a Australia e Se não gosto de viajar então visitei 
a Australia
Conectivos
 Negação
 A partir de uma proposição p podemos construir outra, 
denominada negação
 p: Dilma é presidente do Brasil
 ~p: Dilma não é presidente do Brasil
 q: João não é filho de Beto
 ~q: João é filho de Beto
 Tabela Verdade
p ~p
V F
F V
Tabela Verdade
 Toda proposição lógica é VERDADEIRA ou FALSA
 O valor lógico de qualquer proposição composta depende 
unicamente dos valores das proposições simples componentes
 Tabelas verdade são usadas para identificar o valor lógico de 
proposições compostas
 Coloca-se na tabela verdade todos os possíveis valores de 
atribuição às proposições simples componentes
Tabela Verdade
 p: Jorge é Engenheiro
 Os valores possíveis que essa proposição pode assumir são
p
V
F
Tabela Verdade
 p: Jorge é Engenheiro
 q: Jorge sabe matemática
 Os valores possíveis que essas proposições combinadas podem possuir 
são:
p q
V V
V F
F V
F F
Conectivos
 Conjunção (E)
 Símbolo: ^
 A partir de duas proposição p e q, podemos obter uma terceira, p ^ q
 A nova proposição só será verdadeira caso ambas sejam verdadeiras
 p: Jorge é Engenheiro
 q: Jorge sabe matemática
 p ^ q : Jorge é Engenheiro e Jorge sabe matemática
p q p ^ q
V V V
V F F
F V F
F F F
Conectivos
 Disjunção (ou)
 Símbolo: v
 A partir de duas proposição p e q, podemos obter uma terceira, p v q
 A nova proposição será verdadeira quando ao menos uma for verdadeira
 p: Jorge é Engenheiro
 q: Jorge sabe matemática
 p v q : Jorge é Engenheiro ou Jorge sabe matemática
p q p v q
V V V
V F V
F V V
F F F
Conectivos
 Condicional(Se...Então)
 Símbolo: 
 A partir de duas proposição p e q, podemos obter uma terceira, p  q (lê 
“se p então q”)
 A nova proposição será falsa quando p for V e q for F e será verdadeira nos 
demais casos.
 p é antecedente e q é consequente
 p: Jorge é Engenheiro
 q: Jorge sabe matemática
 p  q : Se Jorge é Engenheiro 
então Jorge sabe matemática
p q p  q
V V V
V F F
F V V
F F V
Conectivos
 Condicional (Se...Então)
 ATENÇÃO
 Uma condicional p q não afirma que o consequente se deduz ou é 
consequencia do antecendete. Por exemplo:
 p: 7 é um número ímpar 
 q: Brasília é uma cidade
 p  q: 7 é um número ímpar  Brasília é uma cidade
 não afirma DE MODO NENHUM que o fato de Brasília ser uma cidade 
se deduz do fato de 7 ser um número ímpar.
 O que uma condicional afirma é unicamente uma relação entre 
valores lógicos do antecedente e do consequente de acordo com a 
tabela verdade anterior.
Conectivos
 Bicondicional (...se e somente se...)
 Símbolo: 
 A partir de duas proposição p e q, podemos obter uma terceira, 
p  q (lê “p se e somente se q”)
 O valor lógico é verdade se ambas forem verdadeiras ou ambas 
foram falsas. Nos demais casos, o valor é falso.
 p: Jorge é Engenheiro
 q: Jorge sabe matemática
 p  q : Jorge é Engenheiro se e
somente se Jorge sabe matemática
p q P  q
V V V
V F F
F V F
F F V
Valor das proposições
 Sejam as proposições
 p : Carlos é careca (verdadeiro)
 q: Pedro é estudante (falso)
 Que valores lógicos as fórmulas abaixo possuem?
1. p  q
2. ~q  ~p
3. (p ^~q) v ~p
Valor das proposições
 Sejam as proposições
 p : Carlos é careca (verdadeiro)
 q: Pedro é estudante (falso)
 Que valores lógicos as fórmulas abaixo possuem?
1. p  q V  F = F
2. ~q  ~p ~F  ~V = V  F = F
3. (p ^~q) v ~p (V ^ ~F) v ~V = (V ^ V) v F = V v F = V
Exercícios
 Determine o valor lógico das proposições abaixo para 
p = F e q = F:
1. ~p V 6. q v ~p V
2. p ^q F 7. ~p ^ ~q V
3. p v q F 8. ~p v ~q V
4. ~~q F 9. ~~p F
5. p  ~q = V 10. (p ^ ~q)  p V 
Proposições Compostas
 Dadas várias proposições p, q, r, s, ... podemos combiná-las 
pelos conectivos lógicos vistos e construir proposições 
compostas tais como:
 P(p,q) = ~ p v ( p  q)
 Q(p,q) = (p~q) ^ q
 R(p, q, s) = (p  ~q v r ) ^ ~ q v ( p ~r)
 Com o emprego da tabela verdade das operações lógicas 
fundamentais é possível construir a tabela verdade de 
qualquer proposição composta
 O número de linhas da tabela verdade de uma proposição composta 
depende do número de proposições simples que a integram e é dado por 
2n
 Onde n é o número de proposições simples
 A tabela verdade de P(p,q) = ~ p v ( p  q) terá 22 = 4 linhas
 Já a de R(p, q, s) = (p  ~q v r ) ^ ~ q v ( p ~r) terá 23 = 8 linhas
Proposições Compostas
Proposições Compostas
 Exemplo:
 P(p,q) = ~ p v ( p  q)
 PASSO 1: Construir as colunas referentes às proposições simples constituintes
p q
V V
V F
F V
F F
Proposições Compostas
 Exemplo:
 P(p,q) = ~ p v ( p  q)
 PASSO 2: Construir as colunaspara as proposições compostas que são subconjunto da 
proposição total.
p q
V V
V F
F V
F F
~p
F
F
V
V
pq
V
F
V
V
Proposições Compostas
 Exemplo:
 P(p,q) = ~ p v ( p  q)
 PASSO 3: Construir para a proposição completa
p q
V V
V F
F V
F F
~p
F
F
V
V
pq
V
F
V
V
~ p v (pq)
Proposições Compostas
 Exemplo:
 P(p,q) = ~ p v ( p  q)
 PASSO 3: Construir para a proposição completa
p q
V V
V F
F V
F F
~p
F
F
V
V
pq
V
F
V
V
~ p v (pq)
V
F
V
V
Proposições Compostas
 Precedência de Operadores
 Assim como na Álgebra que estamos acostumados (+, -, *, /, ...) há também precedência 
nos conectivos lógicos
 Seguindo a ordem:
 1) ~
 2) ^ ou v
 3) 
 4) 
 Para a proposição composta : ~p  q  p ^ q
a ordem de realização das operação é: ( (~p)  q )  (p ^ q)
 É sempre conveniente a utilização dos parênteses para evitar ambiguidades ou erros.
Proposições Compostas
 A Tabela Verdade dessa proposição é:
~p  q  p ^ q
p q ~p ~p  q p ^ q ~p  q  p ^ q
V V F V V V
V F F V F F
F V V V F F
F F V F F V
Exercícios 1
 Construa a tabela verdade para as fórmulas abaixo:
1. p  q
2. ~q  ~p
3. (p ^~q)  ~p
4. q ^ ~p
5. ~p v ~q
6. (p v ~q) ^(~p  q)
Exercícios 2
 Construa a tabela verdade para as fórmulas abaixo:
1. (p v q) v r
2. (p v ~q) ^ r
3. (p ^ r) v ~q
4. (~p  q) v r
5. (p ^~q)  ~r
Tautologias
 Toda proposição composta cuja última coluna da sua tabela encerra 
somente a letra V
 Também chamadas proposições tautológicas ou proposições 
logicamente verdadeiras
“Toda proposição composta P (p, q, r,...) cujo valor lógico é 
sempre V (verdade), quaisquer que sejam os valores , lógicos 
das proposições simples componentes”
Tautologias
 Exemplos
 p v ~p
 A proposição (p v ~p) é também conhecida como “Princípio do Terceiro 
Excluído”
 Ou p é p ou é não p. Não há uma terceira opção
p ~p
V F
F V
p v ~p
V
V
Tautologias
 Exemplos
 ~( p ^ ~p)
 A proposição ~( p ^ ~p) é também conhecida como “Princípio da Não 
Contradição”
 Uma proposição verdadeira não pode ser falsa e uma proposição falsa não pode ser 
verdadeira.
p ~p
V F
F V
p ^ ~p
F
F
~ ( p ^ ~p)
V
V
Tautologias
 Exemplos
 p v ~ (p ^ q)
p q p ^ q ~(p ^q ) p v ~(p ^ q)
V V V F V
V F F V V
F V F V V
F F F V V
Contradição
 Toda proposição composta cuja última coluna da sua tabela encerra 
somente a letra F
 Também chamadas proposições contraválidas ou proposições 
logicamente falsas
“Toda proposição composta P (p, q, r,...) cujo valor lógico é 
sempre F (falso), quaisquer que sejam os valores , lógicos das 
proposições simples componentes”
Contradições
 Exemplos
 p ^ ~p
 Dizer que uma proposição pode ser simultaneamente verdadeira e falsa é 
sempre falsa
p ~p
V F
F V
p ^ ~p
F
F
Contradições
 Exemplos
 p  ~p
 (p ^q) ^ ~(p v q)
p ~p
V F
F V
p ~p
F
F
p q p ^ q (p v q) ~(p v q)
V V V V F
V F F V F
F V F V F
F F F F V
(p ^ q) ^ ~(p v q)
F
F
F
F
Contingências
 Toda proposição composta cuja última coluna da sua tabela possui pelo 
menos um V e um F.
 Também chamadas proposições contingentes ou proposições 
indeterminadas
“Toda proposição composta P (p, q, r,...) que não é tautologia 
nem contradição”
Contingências
 Exemplos
 p  ~p
 p v q  p
p ~p
V F
F V
p  ~p
F
V
p q p v q p v q  p
V V V V
V F V V
F V V F
F F F V
Exercícios
 Quais das proposições abaixo são tautologias, quais são 
contradições e quais são contingências?
1. (p ^ q) v (~p ^~q)
2. ~(p ^ ~p)
3. p  (q  p)
4. (p v q)  ((p ^ q) v (p ^~q) v (~p ^ q)
Referências
 TONIN, Neilor. Apostila de Lógica para Computação. 
Universidade Regional Integrada. Erechim, 2008.
 ALENCAR FILHO, Edgard. Iniciação à Lógica Matemática. 
São Paulo: Nobel,2002.