MD Aula01 LogicaProposicional

Lógica Proposicional
Área de Teoria DCC/UFMG
Matemática Discreta
2019/01
Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01 1 / 52

Lógica: Introdução
A lógica é o ramo da filosofia, matemática e ciência da comptuação que

trata das inferências válidas.
A lógica é a base do raciocı́nio matemático, e de todo o raciocı́nio
automatizado.
Ela estuda a preservação da verdade durante uma argumentação.

A lógica concerne técnicas que garantem que:
1. partindo de hipóteses verdadeiras,

2. atinjamos sempre conclusões também verdadeiras.
As regras da lógica dão significado preciso a afirmações matemáticas.

Elas são essenciais na construção de provas matemáticas.

Lógica: Introdução
Além de sua importância em matemática, a lógica tem aplicações em ciência

da computação nas áreas de:
1 desenho de circuitos, 4 prova automática de teoremas,

2 escrita de programas de 5 verificação da correção de
computador, programas,
3 inteligência artificial, 6 ...
A lógica se divide em várias sub-áreas:
lógica proposicional,
lógica de predicados,
lógica de ordem superior.
Nós vamos começar pelo estudo da lógica proposicional.

Lógica proposicional

Proposições
Uma proposição é uma sentença declarativa (ou seja, uma sentença que
estabelece um fato) que pode ser verdadeira ou falsa, mas não ambos.
Exemplo 1: As seguintes sentenças declarativas são proposições:
“Belo Horizonte é a capital de Minas Gerais.” (Proposição verdadeira)

“Londres é a capital da França.” (Proposição falsa)
“1 + 1 = 2.” (Proposição verdadeira)
“2 + 2 = 3.” (Proposição falsa)

Exemplo 2: As seguintes sentenças não são proposições:
“Que horas são?” (Não é uma sentença declarativa.)

“Estude com afinco para a prova.” (Não é uma sentença declarativa.)
“x + 2 = 3.” (Não é verdadeira nem falsa.)

Proposições
Nós usamos letras para denotar variáveis proposicionais, ou seja, variáveis

que representam proposições:
p, q, r , s, t, . . .
O valor de verdade de uma proposição pode ser:
verdadeiro, denotado por V (verdadeiro) ou T (true), ou

falso, denotado por F (falso ou false).
A área da lógica que lida com proposições é chamada de cálculo

proposicional ou lógica proposicional.

Proposições compostas
Proposições compostas podem ser criadas ao se combinarem proposições já

existentes.
A combinação de proposições é feita usando operadores lógicos ou
conectivos lógicos como:
negação (não),
conjunção (e),
disjunção (ou),
implicação (implica),
implicação dupla (implica duplamente).
Nós vamos agora estudar estes conectivos.

Proposições: Negação
Seja p uma proposição.

A negação de p, denotada por ¬p (ou também p), é a afirmação
“Não é o caso de que p.”
Lê-se a proposição ¬p como “não p”.

O valor de verdade de ¬p é o oposto do valor de verdade de p.
Tabela da verdade para a negação de uma proposição p:
Negação
p ¬p
T F
F T

Proposições: Negação
Exemplo 3: Seja a proposição
p: “O computador do Mário roda Linux.”
A negação ¬p é: “Não é o caso de que o computador do Mário rode Linux.”

Forma alternativa de negação ¬p: “O computador do Mário não roda Linux.”

q: “Luciana tem pelo menos 25 anos.”
A negação ¬q é: “Não é o caso de que Luciana tenha pelo menos 25 anos.”
Forma alternativa de negação ¬q: “Luciana não tem pelo menos 25 anos.”
Mais uma forma de negação ¬q: “Luciana tem menos de 25 anos.”


Conectivos lógicos: Conjunção
Sejam p e q proposições.
A conjunção de p e q, denotada por p ∧ q, é a afirmação
“p e q”.
A conjunção p ∧ q é verdadeira quando ambos p e q são verdadeiros, e é

falsa em caso contrário.
Tabela da verdade para a conjunção de duas proposições p e q:
Conjunção
p q p∧q
T T T
T F F
F T F
F F F

Conectivos lógicos: Conjunção
Exemplo 5: Sejam as proposições:
p : “Hoje é sábado”,
q : “Vou comer bolo”.
A conjunção p ∧ q é:
“Hoje é sábado e vou comer bolo.”

Às vezes em linguagem natural usamos “mas” para significar conjunção:
Exemplo 6: A proposição
“Hoje chove, mas vou sair”

é a conjunção p ∧ q das proposições
p : “Hoje chove”
q : “Hoje vou sair”.
Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01

11 / 52
Conectivos lógicos: Disjunção
A disjunção de p e q, denotada por p ∨ q, é a afirmação
“p ou q”.
A disjunção p ∨ q é verdadeira quando ao menos um entre p e q é

verdadeiro, e é falsa em caso contrário.
Tabela da verdade para a disjunção de duas proposições p e q:
Disjunção
p q p∨q
T T T
T F T
F T T
F F F

Conectivos lógicos: Disjunção
p : “O celular de Alice é azul”,

q : “O celular de Alice é novo”.
A disjunção p ∨ q é:
“O celular de Alice é azul ou o celular de Alice é novo.”
Alternativamente, p ∨ q é:
“O celular de Alice é azul ou é novo.”


Conectivos lógicos: “Ou inclusivo” versus “ou exclusivo”
A palavra “ou” tem dois significados diferentes em linguagem natural.
O conectivo “ou” da disjunção corresponde ao significado de ou inclusivo,
em que a disjunção é verdadeira se ao menos uma das proposições é
verdadeira.
Exemplo 8: A disjunção
“Você pode se matricular nesta disciplina se tiver cursado Cálculo ou

Programação”
significa que podem se matricular na disciplina:

alunos que cursaram apenas Cálculo,
alunos que cursaram apenas Programação,
alunos que cursaram ambos Cálculo e Programação.
Esta é uma disjunção inclusiva.

Conectivos lógicos: “Ou inclusivo” versus “ou exclusivo”
O outro significado de “ou” corresponde ao ou exclusivo, em que a

disjunção é verdadeira se exatamente uma das proposições é verdadeira.
Exemplo 9: Se você ler no cardápio de um restaurante a proposição
“O prato feito inclui um pedaço de carne ou um pedaço de frango.”
você entende que você pode:
escolher comer um pedaço de frango, mas não de carne,

escolher comer um pedaço de carne, mas não de frango,
mas você não pode escolher comer um pedaço de carne e um pedaço de
frango ao mesmo tempo.
Esta é uma disjunção exclusiva.


Conectivos lógicos: Ou exclusivo
O ou exclusivo de p e q, denotado por p ⊕ q, é a afirmação
“ou p ou q”.
O ou exclusivo p ⊕ q é verdadeiro quando exatamente um entre p e q é

verdadeiro, e é falso em caso contrário.
Tabela da verdade para o ou exclusivo de duas proposições p e q:
Ou exclusivo
p q p⊕q
T T F
T F T
F T T
F F F

Conectivos lógicos: Ou exclusivo
Exemplo 10: Sejam as proposições
p : “Eu vou à festa hoje”,

q : “Eu vou ficar em casa hoje”.
O ou exclusivo p ⊕ q é:
“Hoje ou eu vou à festa, ou eu vou ficar em casa.”


Conectivos lógicos: Proposições condicionais
A afirmação condicional ou implicação p → q é a afirmação
“se p, então q”.
A afirmação condicional p → q é falsa quando p é verdadeira e q é falsa, e a

afirmação é verdadeira caso contrário.
Na afirmação condicional p → q:
p é chamada de hipótese, antecedente, ou premissa,

q é chamada de conclusão ou consequente.

Tabela da verdade para a proposição condicional envolvendo duas

proposições p e q:
Implicação
p q p→q
T T T
T F F
F T T
F F T
A afirmação condicional p → q é falsa quando p é verdadeira e q é falsa, e a

afirmação é verdadeira caso contrário.

A implicação p → q pode ser entendida como uma promessa:
“Se você me garantir p, eu te garanto q.”
A promessa só é quebrada quando você me garantir p e eu não te garantir q

em troca.
A promessa é mantida quando você me garante p e eu te garanto q, ou
quando você não me garante p (e neste caso eu sou livre para te garantir q
ou não sem quebrar a promessa).
Exemplo 11: Considere a implicação abaixo.
“Se eu for eleito, eu vou abaixar os impostos”
A proposição condicional é falsa se eu for eleito e não abaixar os impostos.

Se eu não for eleito, eu posso abaixar os impostos ou não, sem assim quebrar
minha promessa. Logo, se eu não for eleito, a proposição condicional é
verdadeira independentemente de se eu abaixar os impostos ou não.

Na lógica proposicional, o valor de verdade da implicação p → q só depende

do valor de verdade de p e q, e não de seu significado.
Ao contrário do uso da implicação em linguagem natural, não existe
necessariamente uma noção de “causa e efeito” entre p e q.
A implicação lógica p → q apenas garante que:
“q é no mı́nimo tão verdadeiro quanto p.”
A implicação só é falsa se “q for menos verdadeiro que p”, ou seja, se p for
verdadeiro e q for falso.

Exemplo 12: Vamos analisar se as implicações abaixo são verdadeiras ou

falsas.
“Se o sol emite luz, então queijos são laticı́nios.”

Proposição verdadeira: premissa e conclusão verdadeiras.
“Se 2 + 2 = 3, então morangos são animais.”

Proposição verdadeira: premissa falsa e conclusão falsa.
“Se a semana tem 7 dias, então o Brasil fica na Europa.”

Proposição falsa: premissa verdadeira e conclusão falsa.
“Se π é racional, então o Atlântico é um oceano de Fanta Uva.”

Proposição verdadeira: premissa e conclusão falsas.


Proposições condicionais em linguagem natural
Implicações aparecem na matemática e na linguagem natural em diversas

formas.
A afirmação condicional p → q pode ser expressa como:
“se p, então q” “q a menos que ¬p”

“se p, q” “p implica q”
“q se p”
“p somente se q”
“q quando p”
“p é suficiente para q” “q sempre que p”
“q é necessário para p” “q segue de p”

Proposições condicionais em linguagem natural
p : “Está fazendo sol.”

q : “Eu vou ao clube.”
A implicação p → q pode ser escrita em linguagem natural como:
“Se estiver fazendo sol, eu vou ao clube.”

“Estar fazendo sol é condição suficiente para eu ir ao clube.”
“Eu vou ao clube a menos que não esteja fazendo sol.”
“O fato de eu ir ao clube segue do fato de estar fazendo sol.”
“Eu vou ao clube sempre que faz sol.”
“Faz sol somente se eu vou ao clube.”


Proposições condicionais: Conversa, contrapositiva e
inversa
Dada uma implicação p → q:
sua conversa é a implicação q → p,

sua contrapositiva é a implicação ¬q → ¬p,
sua inversa é a implicação ¬p → ¬q.

Proposições condicionais: Conversa, contrapositiva e
inversa
“O time da casa vence sempre que está chovendo.”

Esta implicação pode ser escrita como p → q, onde
p é a proposição “Está chovendo”, e
q é a proposição “O time da casa vence”.
A conversa q → p é a proposição
“Se o time da casa vence, está chovendo.”
A contrapositiva ¬q → ¬p é a proposição
“Se o time da casa não vence, então não está chovendo.”
A inversa ¬p → ¬q é a proposição
“Se não está chovendo, o time da casa não vence.”

Conectivos lógicos: Proposições bicondicionais
A afirmação bicondicional ou implicação dupla p ↔ q é a afirmação
“p se, e somente se, q”.
A afirmação bicondicional p ↔ q é verdadeira quando p e q têm o mesmo

valor de verdade, e é falsa em caso contrário.
Em linguagem natural é comum expressar p ↔ q como:
“p é necessário e suficiente para q.”

“p sse q.” Note que usamos “sse” com dois “s”.
(Em inglês, usa-se o “iff” com dois “f”.)

Conectivos lógicos: Proposições bicondicionais
Tabela da verdade para o ou exclusivo de duas proposições p e q:
Implicação dupla
p q p↔q
T T T
T F F
F T F
F F T
A proposição bicondicional p ↔ q é verdadeira sempre que ambos p → q e

q → p são verdadeiros, e ela é falsa em caso contrário.

Tabela da verdade de proposições compostas
Nós introduzimos a negação e os conectivos lógicos de disjunção, conjunção,

ou exclusivo, implicação e implicação dupla.
Nós podemos usar estes operadores para expressar proposições cada vez mais
complexas.
Para determinar o valor de verdade de proposições compostas, podemos usar

tabelas da verdade.
Exemplo 15: Tabela da verdade para a expressão (p ∨ ¬q) → (p ∧ q):
p q ¬q p ∨ ¬q p∧q (p ∨ ¬q) → (p ∧ q)
T T F T T T
T F T T F F
F T F F F T
F F T T F F


Ordem de precedência dos operadores lógicos
Em uma expressão composta, a ordem de aplicação dos operadores é:
1) negação: ¬
2) conjunção: ∧
3) disjunção: ∨
4) implicação: →
5) implicação dupla ↔
Exemplos:
1 p ∨ ¬q ∧ r equivale a p ∨ ((¬q) ∧ r ).
2 p →q∨r equivale a p → (q ∨ r ).

Operadores lógicos bit-a-bit
Computadores representam informação usando bits, que são dı́gitos binários

0 ou 1.
O bit 1 representa T (verdadeiro), e o bit 0 representa F (falso).
Conectivos lógicos podem ser utilizados para operar sobre variáveis

Booleanas, cujos valores são bits.
A conjunção é chamada de AND, a disjunção é chamada de OR, e o ou
exclusivo é chamado de XOR (exclusive or ).
Tabela da verdade para os operadores AND, OR e XOR.
x y x AND y x OR y x XOR y
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0

Operadores lógicos bit-a-bit
Uma string de bits é uma sequência de zero ou mais bits.
O comprimento de uma string é o número de bits nesta string.
Exemplos:
1 101 é uma string de bits de 2 0100111 é uma string de bits de
comprimento 3. comprimento 7,
Operadores binários podem ser aplicados bit a bit em duas strings de bits de
mesmo comprimento. O resultado é uma string de mesmo comprimento.
Exemplo 16:
0110
1101
resultado de AND bit a bit: 0100
resultado de OR bit a bit: 1111
resultado de XOR bit a bit: 1011

Aplicações da lógica
proposicional

Aplicações da lógica proposicional: Introdução
A lógica tem importantes aplicações na matemática, ciência da computação,

e diversas outras disciplinas:
1 tradução de sentenças em linguagem natural, frequentemente ambı́guas, para
uma linguagem precisa,
2 especificação de circuitos lógicos,
3 solução de quebra-cabeças (o que é essencial para inteligência artificial),
4 automatização do processo de construção de provas matemáticas,
5 ...
Nesta seção vamos exemplificar algumas destas aplicações práticas da lógica

proposicional.

Traduzindo sentenças em linguagem natural
Sentenças em linguagem natural são frequentemente ambı́guas, o que pode

causar problemas de comunicação.
Traduzir sentenças em linguagem natural para proposições compostas remove

a ambiguidade.
Uma vez traduzidas para proposições lógicas, estas sentenças podem ser
analisadas quanto ao seu valor de verdade.

Traduzindo sentenças em linguagem natural
Exemplo 17: Seja a sentença em linguagem natural:
“Você não pode andar na montanha russa se você for mais baixo que 1.50m
de altura, a menos que você tenha mais de 16 anos.”
Podemos traduzı́-la para uma proposição composta, usamos as seguintes

proposições:
p : “você pode andar na montanha russa”,

q : “você é mais baixo que 1.50 m”,
r : “você tem mais de 16 anos”.
A sentença em linguagem natural é, então, traduzida para:
(q ∧ ¬r ) → ¬p.

Especificação de sistemas
Traduzir sentenças de linguagem natural para linguagem lógica é parte
essencial da especificação de sistemas de hardware e software.
Exemplo 18: Expresse a especificação abaixo como uma proposição

composta.
“A resposta automática não pode ser enviada

quando o sistema de arquivos está cheio.”
Solução. Podemos traduzir a especificação para uma proposição composta,

usando as seguintes proposições:
r : “a reposta automática pode ser enviada”,
c : “o sistema de arquivos está cheio”.
A especificação fica, então, traduzida para:

c → ¬r .

Resolução de problemas e quebra-cabeças
Exemplo 19: Desafio retirado de www.brilliant.org:

Equivalência de proposições

Equivalência de proposições: Introdução
Um passo importante na resolução de muitos problemas é a substituição de

uma afirmação por outra com mesmo valor de verdade.
Nesta seção vamos estudar como determinar se duas proposições compostas

têm sempre o mesmo valor de verdade.

Equivalência de proposições: Introdução
Primeiro, vamos categorizar os tipos de expressões compostas:
uma tautologia é uma expressão sempre verdadeira independentemente o

valor de verdade das variáveis que nela aparecem;
uma contradição é uma expressão sempre falsa independentemente o valor de
verdade das variáveis que nela aparecem;
uma contingência é uma expressão que não é nem uma tautologia, nem uma
contradição.
Exemplo 20: A tabela da verdade abaixo mostra que (p ∧ ¬p) é uma

contradição, enquanto a expressão (p ∨ ¬p) é uma tautologia.
p ¬p p ∧ ¬p p ∨ ¬p
T F F T
F T F T


Equivalências lógicas
Duas proposições compostas p e q são logicamente equivalentes se p ↔ q
é uma tautologia.
A notação p ≡ q denota que p e q são logicamente equivalentes.
Uma maneira de determinar se p ≡ q é usando tabelas da verdade.
Exemplo 21: Mostre que p → q e ¬p ∨ q são logicamente equivalentes.
Solução.
Tabela da verdade para p → q e Como a coluna correspondente a

¬p ∨ q: p → q e a coluna correspondente a
p q ¬p ¬p ∨ q p→q ¬p ∨ q possuem sempre o mesmo
valor de verdade,
T T F T T (p → q) ↔ (¬p ∨ q) é uma
T F F F F tautologia.
F T T T T
F F T T T Logo p → q ≡ (¬p ∨ q).

Exemplo 22: Mostre que ¬(p ∨ q) e ¬p ∧ ¬q são logicamente equivalentes.
Solução. Tabela da verdade para ¬(p ∨ q) e ¬p ∧ ¬q:

p q p∨q ¬(p ∨ q) ¬p ¬q ¬p ∧ ¬q
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T
Uma vez que a coluna correspondente a ¬(p ∨ q) e a coluna correspondente
a ¬p ∧ ¬q possuem sempre o mesmo valor de verdade,
¬(p ∨ q) ↔ (¬p ∧ ¬q) é uma tautologia.
Logo, ¬(p ∨ q) ≡ ¬p ∧ ¬q.
A equivalência que demonstramos é Leis de De Morgan

uma das Leis de De Morgan: ¬(p ∨ q) ≡ ¬p ∧ ¬q
¬(p ∧ q) ≡ ¬p ∨ ¬q
Exemplo 23: Mostre que p ∨ (q ∧ r ) e (p ∨ q) ∧ (p ∨ r ) são logicamente
equivalentes.
Solução. Tabela da verdade para p ∨ (q ∧ r ) e (p ∨ q) ∧ (p ∨ r ):

p q r q∧r p ∨ (q ∧ r) p∨q p∨r (p ∨ q) ∧ (p ∨ r)
T T T T T T T T
T T F F T T T T
T F T F T T T T
T F F F T T T T
F T T T T T T T
F T F F F T F F
F F T F F F T F
F F F F F F F F
Como as colunas correspondentes a p ∨ (q ∧ r ) e (p ∨ q) ∧ (p ∨ r ) possuem

sempre o mesmo valor de verdade, p ∨ (q ∧ r ) ≡ (p ∨ q) ∧ (p ∨ r ).
A equivalência que demonstramos é a lei da distributividade da disjunção

sobre a conjunção.
Algumas equivalências lógicas importantes:
Nome Equivalência
p∧T ≡ p
Leis de identidade
p∨F ≡ p
p∧F ≡ F
Leis de dominância
p∨T ≡ T
p∧p ≡ p
Leis de idempotência
p∨p ≡ p
Lei da dupla negação ¬(¬p) ≡ p
p∧q ≡ q∧p
Leis de comutatividade
p∨q ≡ q∨p
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r )
Leis de associatividade
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r )
p ∧ (q ∨ r ) ≡ (p ∧ q) ∨ (p ∧ r )
Leis de distributividade
p ∨ (q ∧ r ) ≡ (p ∨ q) ∧ (p ∨ r )
¬(p ∧ q) ≡ ¬p ∨ ¬q
Leis de De Morgan
¬(p ∨ q) ≡ ¬p ∧ ¬q
p ∨ (p ∧ q) ≡ p
Leis de absorção
p ∧ (p ∨ q) ≡ p
p ∧ ¬p ≡ F
Leis da negação
p ∨ ¬p ≡ T

Equivalências lógicas envolvendo Equivalências lógicas envolvendo

proposições condicionais: proposições bicondicionais:
Equivalências Equivalências
p → q ≡ ¬p ∨ q p↔q ≡ (p → q) ∧ (q → p)
p → q ≡ ¬q → ¬p p↔q ≡ ¬p ↔ ¬q
p ∨ q ≡ ¬p → q p↔q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
p ∧ q ≡ ¬(p → ¬q) ¬(p ↔ q) ≡ p ↔ ¬q
¬(p → q) ≡ p ∧ ¬q
(p → q) ∧ (p → r ) ≡ p → (q ∧ r )
(p → r ) ∧ (q → r ) ≡ (p ∨ q) → r
(p → q) ∨ (p → r ) ≡ p → (q ∨ r )
(p → r ) ∨ (q → r ) ≡ (p ∧ q) → r

Usos das Leis de De Morgan
As duas equivalências lógicas conhecidas como Leis de De Morgan são
particularmente importantes.
A lei
¬(p ∨ q) ≡ ¬p ∧ ¬q
diz que a negação da disjunção é a conjunção das negações.
Exemplo 24: Use as Leis de De Morgan para negar a proposição:
“Júlia vai ao cinema ou Catarina vai ao cinema.”
Solução. Esta proposição pode ser escrita como p ∨ q, onde p é “Júlia vai
ao cinema” e q é “Catarina vai ao cinema”.
Pela lei de De Morgan, a negação é ¬(p ∨ q) ≡ ¬p ∧ ¬q, que se traduz em
“Júlia não vai ao cinema e Catarina não vai ao cinema.”

Usos das Leis de De Morgan
A lei de De Morgan
¬(p ∧ q) ≡ ¬p ∨ ¬q
diz que a negação da conjunção é a disjunção das negações.
Exemplo 25: Use as Leis de De Morgan para negar a proposição:
“Pedro comeu lasanha e bolo.”
Solução. Esta proposição pode ser escrita como p ∧ q, onde p é “Pedro

comeu lasanha” e q é “Pedro comeu bolo”.
Pelas Leis de De Morgan, a negação é ¬(p ∧ q) ≡ ¬p ∨ ¬q, que se traduz em
“Pedro não comeu lasanha ou ele não comeu bolo.”


Construindo novas equivalências lógicas
Como vimos, tabelas da verdade podem ser utilizadas para verificar

equivalências lógicas.
No geral, para expressões envolvendo n variáveis lógicas são necessárias 2n

linhas na tabela.
Para n grande, pode ser inconveniente construir a tabela da verdade.
Uma alternativa é utilizar equivalências lógicas já conhecidas para derivar

novas equivalências lógicas diretamente.

Exemplo 26: Mostre que ¬(p → q) e p ∧ ¬q são logicamente equivalentes.
Solução.
¬(p → q) ≡ ¬(¬p ∨ q) (pela tabela de equiv. de condicionais)

≡ ¬(¬p) ∧ ¬q (pelas Leis de De Morgan)
≡ p ∧ ¬q (pela lei da dupla negação)

Exemplo 27: Mostre que ¬(p ∨ (¬p ∧ q)) e ¬p ∧ ¬q são logicamente

equivalentes.
Solução.
¬(p ∨ (¬p ∧ q)) ≡ ¬p ∧ ¬(¬p ∧ q)) (pelas Leis de De Morgan)

≡ ¬p ∧ (¬(¬p) ∨ ¬q) (pelas Leis de De Morgan)
≡ ¬p ∧ (p ∨ ¬q) (pela lei da dupla negação)
≡ (¬p ∧ p) ∨ (¬p ∧ ¬q) (pela lei da distributividade)
≡ F ∨ (¬p ∧ ¬q) (porque ¬p ∧ p ≡ F )
≡ (¬p ∧ ¬q) ∨ F (pela lei da comutatividade)
≡ ¬p ∧ ¬q (pela lei de identidade)

Exemplo 28: Mostre que (p ∧ q) → (p ∨ q) é uma tautologia.
Solução.
(p ∧ q) → (p ∨ q) ≡ ¬(p ∧ q) ∨ (p ∨ q) (equivalência de condicionais)

≡ (¬p ∨ ¬q) ∨ (p ∨ q) (pela Leis de De Morgan)
≡ (¬p ∨ p) ∨ (¬q ∨ q) (comutatividade e associatividade)
≡ T ∨T (pela lei de negação)
≡T (pela lei de dominância)

MD Aula01 LogicaProposicional

Enviado por

Direitos autorais:

Formatos disponíveis

MD Aula01 LogicaProposicional

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

MD Aula01 LogicaProposicional

Enviado por

Direitos autorais:

Formatos disponíveis

Lógica Proposicional

Área de Teoria DCC/UFMG

Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01 1 / 52

A lógica é o ramo da filosofia, matemática e ciência da comptuação que

Ela estuda a preservação da verdade durante uma argumentação.

1. partindo de hipóteses verdadeiras,

As regras da lógica dão significado preciso a afirmações matemáticas.

Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01 2 / 52

Além de sua importância em matemática, a lógica tem aplicações em ciência

1 desenho de circuitos, 4 prova automática de teoremas,

A lógica se divide em várias sub-áreas:

Nós vamos começar pelo estudo da lógica proposicional.

Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01 3 / 52

Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01 4 / 52

Exemplo 1: As seguintes sentenças declarativas são proposições:

“Belo Horizonte é a capital de Minas Gerais.” (Proposição verdadeira)

“Que horas são?” (Não é uma sentença declarativa.)

Nós usamos letras para denotar variáveis proposicionais, ou seja, variáveis

O valor de verdade de uma proposição pode ser:

verdadeiro, denotado por V (verdadeiro) ou T (true), ou

A área da lógica que lida com proposições é chamada de cálculo

Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01 6 / 52

Proposições compostas podem ser criadas ao se combinarem proposições já

Nós vamos agora estudar estes conectivos.

Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01 7 / 52

Seja p uma proposição.

“Não é o caso de que p.”

Lê-se a proposição ¬p como “não p”.

Tabela da verdade para a negação de uma proposição p:

Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01 8 / 52

Exemplo 3: Seja a proposição

p: “O computador do Mário roda Linux.”

A negação ¬p é: “Não é o caso de que o computador do Mário rode Linux.”

Exemplo 4: Seja a proposição

q: “Luciana tem pelo menos 25 anos.”

Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01 9 / 52

A conjunção p ∧ q é verdadeira quando ambos p e q são verdadeiros, e é

Tabela da verdade para a conjunção de duas proposições p e q:

Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01 10 / 52

“Hoje chove, mas vou sair”

A disjunção p ∨ q é verdadeira quando ao menos um entre p e q é

Tabela da verdade para a disjunção de duas proposições p e q:

Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01 12 / 52

Exemplo 7: Sejam as proposições:

p : “O celular de Alice é azul”,

“O celular de Alice é azul ou o celular de Alice é novo.”

“O celular de Alice é azul ou é novo.”

Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01 13 / 52

“Você pode se matricular nesta disciplina se tiver cursado Cálculo ou

significa que podem se matricular na disciplina:

Esta é uma disjunção inclusiva.

O outro significado de “ou” corresponde ao ou exclusivo, em que a

Exemplo 9: Se você ler no cardápio de um restaurante a proposição

“O prato feito inclui um pedaço de carne ou um pedaço de frango.”

você entende que você pode:

escolher comer um pedaço de frango, mas não de carne,

Esta é uma disjunção exclusiva.

Matemática Discreta Lógica Proposicional Área de Teoria DCC/UFMG - 2019/01 15 / 52

O ou exclusivo p ⊕ q é verdadeiro quando exatamente um entre p e q é