Instituto Federal de Educação, Ciência e
Tecnologia de São Paulo - IFSP
Campus de Caraguatatuba
10 Semestre de 2013
Matemática Discreta 1 – MD 1
Prof. Lineu Mialaret
Aula 7: Proposições (2)
Matemática Discreta 1
Aula 7 - 1/43
©Prof. Lineu Mialaret
Introdução
 As proposições (simples ou compostas) possuem valores
lógicos (ou valores verdade) Verdadeiro (V) ou Falso (F):
 As operações realizadas sobre as proposições também
possuem valores lógicos.
 A Tabela Verdade – TV é uma ferramenta útil para
avaliar o valor verdade resultante da aplicação dos
operadores lógicos sobre as proposições:
 Ela mostra o resultado das operações lógicas, supondo os
diferentes valores verdade para as proposições.
Matemática Discreta 1
Aula 7 - 2/43
©Prof. Lineu Mialaret
TV - Resumo (1)
Matemática Discreta 1
Aula 7 - 3/43
©Prof. Lineu Mialaret
TV - Resumo (2)
Matemática Discreta 1
Aula 7 - 4/43
©Prof. Lineu Mialaret
Sintaxe (1)
 A Matemática é uma ferramenta para modelagem e
abstração do “mundo real”, e a Lógica Matemática pode
se constituir numa das linguagens pela qual se descreve
fatos e idéias sobre este mundo.
 Assim como a Língua Portuguesa é uma linguagem e que
portanto, possui uma gramática e formas de escrever
corretamente uma frase que expresse alguma fato ou idéia,
a Lógica Matemática também possui uma linguagem, com
seus elementos e gramática, a qual se chama de Cálculo
Proposicional.
 A
sintaxe do Cálculo Proposicional especifica os
símbolos e os modos de combiná-los para formar uma
expressão válida da linguagem, a qual pode ser
chamada de “fórmula bem formada ou fórmula bem
formulada” (fbf).
Matemática Discreta 1
Aula 7 - 5/43
©Prof. Lineu Mialaret
Sintaxe (2)
 Elementos Válidos:
 Letras maiúsculas do alfabeto tais como A, B, C, ..., são
usadas para representar proposições ou fórmulas
proposicionais.
 Opcionalmente letras minúsculas do alfabeto, tais como p,
q, r, ... , podem ser usadas para representar proposições.
 Operadores Lógicos:
 Para o conectivo de conjunção, usa-se o símbolo ∧.
 Para o conectivo de disjunção, usa-se o símbolo ∨.
 Para o conectivo de condicional, usa-se o símbolo →.
 Para o conectivo de bicondicional, usa-se o símbolo ↔.
 Para o conectivo de negação, usa-se o símbolo ¬.
 Adicionalmente:
 Parênteses ( , ).
Matemática Discreta 1
Aula 7 - 6/43
©Prof. Lineu Mialaret
Sintaxe (3)
 Há algumas regras para verificar se uma cadeia de letras
de proposição (uma expressão
considerada uma expressão válida:
proposicional)
é
 Uma letra proposicional sozinha é gramaticalmente correta
ou uma fórmula bem formada (fbf).
 Se qualquer expressão proposicional A (tal como p ∨ q) é
bem formada, então também o é sua negação ¬A (ou seja,
¬(p ∨ q) neste caso).
 Se A e B são expressões ou fórmulas bem formadas, então
também o são (A ∧ B), (A ∨ B) e (A → B).
 Exemplos:
 ¬((p ∨ q) → r)
fbf?
 p)) ∧ ∧ → qr
fbf?
Matemática Discreta 1
Aula 7 - 7/43
©Prof. Lineu Mialaret
Sintaxe (4)
 Assim como na aritmética, as operações lógicas devem
ser realizadas segundo uma ordem de prioridade imposta
pelos operadores (conectivos) lógicos.
 A ordem de prioridade é:
 1 Negação
 2 Conjunção
 3 Disjunção
 4 Condicional
 5 Bicondicional
 Exemplo:
Matemática Discreta 1
Aula 7 - 8/43
©Prof. Lineu Mialaret
Sintaxe (5)
 Uma outra forma de definir ordens de prioridade na
expressão é com o uso de parênteses.
 Neste caso, as expressões “mais internas” aos parênteses
devem ser analisadas primeiro.
 Exemplo:
 ¬p ∧ (q → r)
 Numa fórmula bem formada (fbf) com vários operadores
lógicos envolvidos, o último operador a ser aplicado é o
denominado operador ou conectivo principal da
expressão.
 Exemplo:
 A ∧ ¬(B → C)
 ((A ∨ B) ∧ C) → (B ∨ ¬(C))
Matemática Discreta 1
Aula 7 - 9/43
©Prof. Lineu Mialaret
Análise de Expressões Lógicas (1)
 Para análise de uma expressão lógica e construção da
Tabela Verdade deve-se:
 Respeitar a ordem de prioridade das operações definida
pelos parênteses.
 Respeitar a ordem de prioridade das operações definida
pelos operadores.
 Calcular os valores verdade da expressão, supondo todas
combinações de valores verdade para as proposições
simples.
Matemática Discreta 1
Aula 7 - 10/43
©Prof. Lineu Mialaret
Análise de Expressões Lógicas (2)
 Observações:
 As colunas da Tabela Verdade estão dispostas de acordo
com a ordem de prioridade das operações, pois isso auxilia
na organização dos cálculos.
 A
última coluna
proposicional.
é
reservada
para
a
expressão
 O número de linhas da Tabela Verdade é igual a 2 elevado
ao número de proposições simples (n) que compõe a
expressão proposicional (ou seja, = 2n).
Matemática Discreta 1
Aula 7 - 11/43
©Prof. Lineu Mialaret
Análise de Expressões Lógicas (3)
 Calcular a Tabela Verdade da seguinte expressão
proposicional:
 (p ∧ ¬q) ↔ r
Matemática Discreta 1
Aula 7 - 12/43
©Prof. Lineu Mialaret
Análise de Expressões Lógicas (3)
 Calcular a Tabela Verdade da seguinte expressão
proposicional:
 (p ∧ ¬q) ↔ r
¬
Matemática Discreta 1
Aula 7 - 13/43
¬
©Prof. Lineu Mialaret
Análise de Expressões Lógicas (4)
 Resumo:
 Dada uma expressão proposicional, a Tabela Verdade
permite verificar o “comportamento” desta expressão em
diferentes circunstâncias.
 Etapas importantes para construção da Tabela Verdade  Identificar as proposições simples (definir uma coluna da
tabela para cada uma).
 Identificar a ordem de prioridade das operações lógicas na
expressão (subexpressões).
 Calcular cada subexpressão (em diferentes colunas da
tabela).
 Calcular o valor verdade da expressão lógica para cada
configuração de valores verdade das proposições simples.
Matemática Discreta 1
Aula 7 - 14/43
©Prof. Lineu Mialaret
Análise de Expressões Lógicas (5)
 Montar a Tabela Verdade das seguintes expressões
proposicionais:
 ¬(p ∧ ¬q)
 ¬q → (p ∨ ¬r )
Matemática Discreta 1
Aula 7 - 15/43
©Prof. Lineu Mialaret
Análise de Expressões Lógicas (3)
 Montar a Tabela Verdade das seguintes expressões
proposicionais em português:
 Se o cavalo estiver descansado e a armadura for forte,
então o cavaleiro vencerá.
 O cavalo estará descansado se, e somente se, a
armadura for leve e o cavaleiro vencer.
 Se o cavaleiro não perder, então o cavaleiro vencerá, ou,
o cavaleiro perderá.
 O cavaleiro vencerá se a armadura for forte, ou, o cavalo
estará descansado se a armadura for leve.
 Observação:
 Nas expressões em forma discursiva (linguagem natural),
a vírgula pode ser utilizada para separar subexpressões,
como fazem os parênteses na notação matemática.
Matemática Discreta 1
Aula 7 - 16/43
©Prof. Lineu Mialaret
Tautologia (1)
 Tautologia é toda expressão proposicional cujo valor
verdade é sempre verdadeiro, independentemente dos
valores verdade das proposições simples que a compõe.
 Seja a seguinte expressão proposicional:
 (p ∧ ¬p) → (q ∨ p)
 Diz-se que a expressão proposicional acima é uma
Tautologia se, independente dos valores verdade
associados às proposições p e q, o resultado lógico da
expressão sempre será Verdadeiro (V).
Matemática Discreta 1
Aula 7 - 17/43
©Prof. Lineu Mialaret
Tautologia (2)
 Contradição é toda expressão proposicional cujo valor
verdade é sempre falso, independentemente dos valores
lógicos das proposições simples que a compõe.
 Seja a seguinte expressão proposicional:
 (p ∧ ¬p) ↔ (¬p ∧ q)
 Diz-se que a expressão proposicional acima é uma
Contradição se, independente dos valores verdade
associado às proposições p e q, o resultado lógico da
expressão sempre será Falso (F).
Matemática Discreta 1
Aula 7 - 18/43
©Prof. Lineu Mialaret
Tautologia (3)
 Contingência é uma expressão proposicional que pode
assumir o valor lógico Verdadeiro ou Falso.
 Exercícios: Verifique se as expressões proposicionais a
seguir são tautologias, contradições ou contingências (Dica:
montar a tabela verdade e observar a última coluna).
 p → (q →p)
 p → (q → (p ∨ q))
 ¬p ∨ (p ∧ q)
 ¬(p ∧ ¬p)
Matemática Discreta 1
Aula 7 - 19/43
©Prof. Lineu Mialaret
Implicação Lógica (1)
 Dadas as proposições p e q, diz-se que ocorre uma
implicação lógica (ou uma relação de implicação) entre
as proposições p e q quando a proposição condicional
p → q é uma tautologia.
 Notação:
 pq
 onde se lê
 p implica (logicamente) q
– ou
 se p, então q.
Matemática Discreta 1
Aula 7 - 20/43
©Prof. Lineu Mialaret
Implicação Lógica (2)
 Observação:
 Os símbolos  e  têm significados diferentes.
 O símbolo  entre duas proposições dadas indica
que há uma relação, ou seja, que a proposição
condicional associada é uma tautologia.
 Enquanto que o símbolo  realiza uma operação entre
as proposições, dando origem a uma nova proposição
p  q, que pode conter valores lógicos V ou F.
Matemática Discreta 1
Aula 7 - 21/43
©Prof. Lineu Mialaret
Implicação Lógica (3)
 Exemplo: Verificar se a expressão abaixo é uma
implicação lógica.
 (p ∧ q)  (p ∨ q)
Matemática Discreta 1
Aula 7 - 22/43
©Prof. Lineu Mialaret
Implicação Lógica (4)
 Exemplo:
 (p ∧ q)  (p ∨ q)
 Obs.: Para verificar se a expressão proposicional acima é
uma implicação lógica  Monta-se a tabela verdade da expressão
 Substitui-se o símbolo  por →.
Matemática Discreta 1
Aula 7 - 23/43
©Prof. Lineu Mialaret
Equivalência Lógica (1)
 Dadas as proposições p e q, diz-se que ocorre uma
equivalência lógica entre p e q quando suas tabelas
verdades forem idênticas.
 De
forma intuitiva, isto significa que proposições
logicamente equivalentes transmitem a mesma informação
(valor lógico), a partir das mesmas proposições
componentes.
 A proposição p é logicamente equivalente à proposição
q ou seja, p  q, sempre que a proposição bicondicional
p ↔ q for uma tautologia.
 Notação:
 p  q.
Matemática Discreta 1
Aula 7 - 24/43
©Prof. Lineu Mialaret
Equivalência Lógica (2)
 Exemplo:
 ¬(p  q) ↔ (p ∧ ¬q)
Matemática Discreta 1
Aula 7 - 25/43
©Prof. Lineu Mialaret
Equivalência Lógica (3)
 Exemplo:
 ¬(p  q) ↔ (p ∧ ¬q)
 Logo, pode-se dizer que há uma equivalência lógica
entre as expressões ¬(p  q) e (p ∧ ¬q), simbolizada
abaixo:
 ¬(p  q)  (p ∧ ¬q)
Matemática Discreta 1
Aula 7 - 26/43
©Prof. Lineu Mialaret
Equivalência Lógica (4)
 Exercício: Verifique se as expressões a seguir são
implicações, equivalências ou contingências. (Dica:
substituir os símbolos  e  por → e ↔ respectivamente, e
montar a tabela verdade, analisando a última coluna) .
 ¬(p ∨ ¬q)  ¬p ∧ q
 p ∧ ¬q  ¬(p  q)
 (p  q) ∧ ¬p  ¬q
 p ↔ ¬q  q  p
Matemática Discreta 1
Aula 7 - 27/43
©Prof. Lineu Mialaret
Equivalência Lógica (5)
 As relações de equivalência podem ser comparadas
com a relação de igualdade (operador =):
 Assim, dada uma expressão lógica composta por duas
subexpressões lógicas, se uma das subexpressões for
substituída por uma outra subexpressão equivalente,
então a nova expressão tem o mesmo sentido (valor
verdade ou valor lógico) que a expressão original.
 Exemplo:
 Já se viu que ¬(p  q)  (p ∧ ¬q).
 Seja a expressão r  (p ∧ ¬q).
 Pode-se dizer que o seu significado é o mesmo que
 ¬(p  q)  r.
Matemática Discreta 1
Aula 7 - 28/43
©Prof. Lineu Mialaret
Equivalência Lógica (6)
 Dada a proposição condicional p  q, ela tem
associadas três outras proposições, as quais contém p e
q:
 Recíproca do Condicional:
q  p.
 Contrapositiva:
¬q  ¬p.
 Recíproca do Contrapositivo ou Inversa: ¬p  ¬q.
 Obs.:
 Condicional e Contrapositiva são logicamente equivalentes.
– p  q  ¬q  ¬p
 Recíproca e Inversa são logicamente equivalentes.
– q  p  ¬p  ¬q
Matemática Discreta 1
Aula 7 - 29/43
©Prof. Lineu Mialaret
Equivalência Lógica (7)
 Outro Exemplo:
 p: T é um triângulo equilátero.
 q: T é um triângulo isósceles (dois lados iguais).
 p  q (condicional): Se T é equilátero, então T é isósceles.
É o mesmo que dizer ~q  ~p (contrapositiva)
 Se T não é isósceles, então T não é equilátero.
 q  p (recíproca): Se T é isósceles, então T é equilátero.
É o mesmo que dizer: ~p  ~q (contrária)
 Se T não é equilátero, então T não é isósceles.
Matemática Discreta 1
Aula 7 - 30/43
©Prof. Lineu Mialaret
Equivalência Lógica (8)
 Exemplo:
 p: O céu está nublado.
 q: Vai chover.
 Condicional:
 p  q: Se o céu está nublado, então vai chover.
 Recíproca:
 q p : Se vai chover, então o céu está nublado.
 Contrapositiva:
 ¬q  ¬p: Se não vai chover, então o céu não está nublado.
 Inversa:
 ¬p  ¬q: Se o céu não está nublado, então não vai chover.
Matemática Discreta 1
Aula 7 - 31/43
©Prof. Lineu Mialaret
Equivalência Lógica (9)
 Devido sua importância e uso freqüente, algumas
equivalências lógicas são consideradas como Leis do
Cálculo Proposicional.
 (L1) Comutatividade na disjunção:
p ∨ q  q ∨ p
 (L2) Comutatividade na conjunção:
p ∧ q  q ∧ p
 (L3) Associatividade na disjunção:
 p ∨ (q ∨ r )  (p ∨ q) ∨ r
 (L4) Associatividade na conjunção:
 p ∧ (q ∧ r )  (p ∧ q) ∧ r
 (L5) Idempotência na disjunção:
p ∨ p  p
Matemática Discreta 1
Aula 7 - 32/43
©Prof. Lineu Mialaret
Equivalência Lógica (10)
 (L6) Idempotência na conjunção:
p ∧ p  p
 (L7) Distributividade com relação a disjunção:
 p ∨ (q ∧ r )  (p ∨ q) ∧ (p ∨ r )
 (L8) Distributividade com relação a conjunção:
 p ∧ (q ∨ r )  (p ∧ q) ∨ (p ∧ r )
 (L9) Lei de De Morgan para disjunção:
 ¬(p ∨ q)  ¬p ∧ ¬q
 (L10) Lei de De Morgan para conjunção:
 ¬(p ∧ q)  ¬p ∨ ¬q
 (L11) Dupla negação:
 ¬¬p  p
Matemática Discreta 1
Aula 7 - 33/43
©Prof. Lineu Mialaret
Equivalência Lógica (11)
 (L12) Lei de Passagem:
 p  q  ¬(p ∧ ¬q)
 (L12a) Lei de Equivalência:
 p ↔ q  (p  q) ∧ (q  p)
 Considerando V uma proposição verdadeira e F uma
proposição falsa, algumas proposições podem ser
simplificadas diretamente, como por exemplo:
 (L13):
 p ∨ ¬p  V
 (L14):
 p ∧ ¬p  F
 (L15):
p ∧ V  p
Matemática Discreta 1
Aula 7 - 34/43
©Prof. Lineu Mialaret
Equivalência Lógica (12)
 (L16):
p ∨ F  p
 (L17):
p ∨ V  V
 (L18):
p ∧ F  F
Matemática Discreta 1
Aula 7 - 35/43
©Prof. Lineu Mialaret
Equivalência Lógica (13)
 Resumo:
Matemática Discreta 1
Aula 7 - 36/43
©Prof. Lineu Mialaret
Equivalência Lógica (14)
 Com o conhecimento destas leis, a equivalência entre
proposições podem ser verificada, utilizando apenas as
leis do cálculo proposicional, sem fazer uso das Tabelas
Verdade:
 Uma outra utilidade importante destas leis é simplificar
longas proposições, reduzindo-as
equivalentes mais simples.
Matemática Discreta 1
Aula 7 - 37/43
em
proposições
©Prof. Lineu Mialaret
Equivalência Lógica (15)
 Exemplo:
 Simplificar (p ∨ q) ∧ ¬p.
 (p ∨ q) ∧ ¬p =
(L2)
 ¬p ∧ (p ∨ q) =
(L8)
 (¬p ∧ p) ∨ (¬p ∧ q) = (L14)
 F ∨ (¬p ∧ q ) =
(L16)
 (¬p ∧ q )
p∧qq∧p
p ∧ (q ∨ r )  (p ∧ q) ∨ (p ∧ r )
p ∧ ¬p  F
p∨Fp
 Logo
 (p ∨ q) ∧ ¬p  (¬p ∧ q)
 Obs.:
 Simplificar significa chegar-se numa expressão lógica
mais simples (com menos proposições ou conectivos)
Matemática Discreta 1
Aula 7 - 38/43
©Prof. Lineu Mialaret
Equivalência Lógica (16)
 Exemplo:
 Mostrar que p ∧ (¬p ∨ q)  p ∧ q.
 p ∧ (¬p ∨ q) =
 (p ∧ ¬p) ∨ (p ∧ q) =
 F ∨ (p ∧ q) =
(L8) p ∧ (q ∨ r )  (p ∧ q) ∨ (p ∧ r )
(L14) p ∧ ¬p  F
(L16) p ∨ F  p
p ∧ q =
 Logo
 p ∧ (¬p ∨ q)  p ∧ q.
 Obs.:
 Mostrar neste caso significa que a partir da primeira
expressão proposicional p ∧ (¬p ∨ q), chega-se na
segunda expressão proposiconal p ∧ q ou vice-versa.
Matemática Discreta 1
Aula 7 - 39/43
©Prof. Lineu Mialaret
Equivalência Lógica (17)
 Exemplo:
 Seja a expressão proposicional p ∨ q:
 “O rio é raso ou o rio é poluído”.
 Qual é o significado da expressão ¬(p ∨ q) ?
 Pela lei de De Morgan para disjunção,
 ¬(p ∨ q)  ¬p ∧ ¬q
 Logo, ¬(p ∨ q):
 “O rio não é raso e nem poluído”.
 Obs.:
 Note que
¬(p ∨ q) não é equivalente a: “O rio não é raso OU
não é poluído”.
Matemática Discreta 1
Aula 7 - 40/43
©Prof. Lineu Mialaret
Equivalência Lógica (18)
 Exercício:
 Mostrar as seguintes equivalências abaixo,
 ¬(p ∨ ¬q)  ¬p ∧ q
 p  q  ¬p ∨ q
 Simplificar,
 p ∨ (p ∧ q)
 Fazer a negação da frase,
 “Joaquim é alto e é magro”.
Matemática Discreta 1
Aula 7 - 41/43
©Prof. Lineu Mialaret
Equivalência Lógica (19)
 Exercício:
 Como negar (p  q) ?
 Ou
 ¬(p  q)  ?
Matemática Discreta 1
Aula 7 - 42/43
©Prof. Lineu Mialaret
Equivalência Lógica (20)
 Exercício:
 Como negar (p ↔ q) ?
 Ou
 ¬(p ↔ q)  ?
Matemática Discreta 1
Aula 7 - 43/43
©Prof. Lineu Mialaret