Lógica Formal

Matemática Discreta

Prof° Marcelo Maraschin de Souza

 Implicação

As proposições podem ser combinadas na forma “se

proposição 1, então proposição 2”

• Essa proposição composta é denotada por →

• Seja proposição 1 dada por A e proposição 2 dada por
B, reescrevemos A→ B, onde A é o antecedente e B é
o consequente.
• Esse conectivo lógico leva o nome de implicação ou
condicional.
 Implicação

• Por convenção, A→ B é verdadeira se A for falsa,

independentemente do valor lógico de B.

Exemplo: Se Fulano foi até a loja de esportes então foi até

a casa de sua avó.
 Implicação

• Tabela-Verdade

A B A→ 𝑩

V V V

V F F

F V V

F F V
 Bicondicional

As proposições podem ser combinadas na forma

“proposição 1 se, e somente se, proposição 2”

• Essa proposição composta é denotada por ↔

• Seja proposição 1 dada por A e proposição 2 dada por
B, reescrevemos A ↔ B
• Esse conectivo lógico leva o nome de bicondicional
• É uma abreviação de (A→ B) ^ (B → 𝐴).
 Bicondicional

Tabela-Verdade

A B A→ 𝑩 B→𝑨 (A→ 𝑩)^(B → 𝑨)

V V V V V

V F F V F

F V V F F

F F V V V
Precedência dos Operadores
Para construir uma tabela-verdade, será necessário resolver todas
as possíveis combinações de valores lógicos das proposições
existentes;

A resolução de um sistema formal deve seguir uma ordem, assim

como acontece nas equações matemáticas:

1. (), {}
2. ‘
3. ˅, ^
4. →
5. ↔
Precedência dos Operadores
1. (), {}
2. ‘
3. ˅, ^, ˅
4. →
5. ↔

Equação Original Certo Errado

A’ v B (A)’ v B (A v B)’
AvB→C (A v B) → C A v (B → C)
A^B→C↔D ((A ^ B) → C) ↔ D A ^ (B → (C ↔ D))
 Expressões em Português
Português Conectivo Lógico Expressão Lógica
Não A.
É falso que A... Negação A’
Não é verdade que A...
E; mas; também; além disso Conjunção A^B
Ou Disjunção AvB
Ou A, Ou B. Disjunção exclusiva A⊕B
Se A, então B.
A implica B.
A, logo B.
A só se B; A somente se B. Condicional A→B
B segue A
A é uma condição suficiente para B; basta A para B.
B é uma condição necessária para A.
A se e somente se B.
Bicondicional A↔B
A é condição necessária e suficiente para B.
 Exemplos:

“O fogo é uma condição necessária para a fumaça”.

De que outra maneira podemos escrever?

“Se houver fumaça, então haverá fogo.”

Antecedente e consequente?
Negações corretas e incorretas

Proposições Correta Incorreta

É falso que vá chover amanhã.
Vai chover amanhã.
Não vai chover amanhã
É falso que Pedro seja alto e magro. Pedro é baixo e gordo.
Pedro é alto e magro. Pedro não é alto ou não é magro. (Pode ser que Pedro não tenha
Pedro é baixo ou gordo. apenas 1 das propriedades)
É falso que o rio seja raso ou esteja
O rio não é raso ou não está
O rio é raso ou está poluído.
poluído.
poluído. O rio não é raso e não está poluído.
(Ambas devem ser falsas!)
O rio é fundo e não está poluído.
 Negação
Quais das proposições a seguir representa P’ se P é a
proposição: “Julia gosta de manteiga, mas detesta creme”?

A) Julia detesta manteiga e creme;

B) Julia não gosta de manteiga nem de creme;
C) Julia não gosta de manteiga mas adora creme;
D) Julia não gosta de manteiga ou adora creme.

Faça a tabela-verdade.
 Fórmula Bem Formulada
Uma cadeia, no qual obedece as regras de sintaxe, como
(𝐴 → 𝐵)^(𝐵 → 𝐴)
é denominada uma fórmula bem formulada (fbf).

Exemplo de fórmula mal formulada,

((𝐴′ → 𝐵𝐶

Letras maiúsculas do final do alfabeto (P,Q,R,S,...) serão

utilizadas para representar fbf’s.
Exemplo: (𝐴^𝐵)^𝐶 → (𝐵 ∨ 𝐶′) pode ser representada por

𝑃→𝑄
 Exercícios
1) Faça a tabela-verdade para cada uma das fbf:

a) 𝐴 ∨ 𝐵′ → (𝐴 ∨ 𝐵)′

b) (𝐴 → 𝐵) ↔ (𝐵^𝐵′)

c) 𝐴 ∨ 𝐴′ → 𝐵 ∧ 𝐵′

d) 𝐴 ∧ 𝐵′ → 𝐶 ′ ′

e) (𝐴 → 𝐵) ↔ (𝐵′ → 𝐴′)
 Tautologia
Uma fbf como a do item E), que assume apenas o valor V,
é denominada tautologia.

Ou seja, é verdadeira independentemente dos valores

lógicos atribuídos às proposições.

Exemplo: A v A’

“Hoje vai ter sol ou hoje não vai ter sol”.

Tautologia
É dita tautológico todo sistema lógico cuja tabela-verdade resulta apenas
em valores Verdadeiros:
A ^ B ↔ B ^ A: (comutatividade)

A B A^B B^A ↔
V V V V V
F V F F V
V F F F V
F F F F V
 Contradição
Uma fbf como a do item C), cujo valor lógico é sempre
falso, é denominada contradição.

Ou seja, é falsa independentemente dos valores lógicos

atribuídos às proposições.

Exemplo: A ∧ A′

“Hoje é terça-feira e hoje não é terça-feira”.

 Contradição
É dita contradição todo sistema lógico cuja tabela-verdade resulta apenas
em valores Falsos:
(A → B) ^ (A ^ B’)

A B A→B A ^ B’ (A → B) ^ (A ^ B’)
V V V F F
F V V F F
V F F V F
F F V F F
 Contingências

Todo e qualquer sistema lógico que não seja Tautologia ou

Contradição, será considerado contingência.
 Equivalência
Seja P e Q duas fbf’s e suponha que a fbf 𝑃 ↔ 𝑄 seja uma
tautologia. Se fizermos uma tabela-verdade observamos que os
valores lógicos de P e Q seriam iguais em todas as linhas.

Exemplo:
P Q P↔Q
V V V
F F V
F F V
V V V
 Equivalência
Então, dizemos que P e Q são equivalentes, denotamos por
𝑃 ⟺ 𝑄.

Ou seja, 𝑃 ⟺ 𝑄 se, e somente se, 𝑃 ↔ 𝑄 é uma tautologia.

Logo, o item 1-E) é uma equivalência, segue

(𝐴 → 𝐵) ⇔ (𝐵′ → 𝐴′)

Quando uma fbf é equivalente a outra, elas podem ser

substituídas uma pela outra.
 Algumas Equivalências Tautológicas
• Comutatividade:
𝐴∨𝐵 ⇔𝐵∨𝐴
𝐴∧𝐵 ⇔𝐵∧𝐴
• Associatividade:
(𝐴 ∨ 𝐵) ∨ 𝐶 ⇔ 𝐴 ∨ (𝐵 ∨ 𝐶)
(𝐴 ∧ 𝐵) ∧ 𝐶 ⇔ 𝐴 ∧ (𝐵 ∧ 𝐶)
• Distributividade:
𝐴 ∨ (𝐵 ∧ 𝐶) ⇔ (𝐴 ∨ 𝐵) ∧ (𝐴 ∨ 𝐶)
𝐴 ∧ (𝐵 ∨ 𝐶) ⇔ (𝐴 ∧ 𝐵) ∨ (𝐴 ∧ 𝐶)
• Elementos neutros:
𝐴∨0 ⇔𝐴
𝐴∧1 ⇔𝐴
 Algumas Equivalências Tautológicas
Tabela-verdade elemento neutro B):
A 1 A^1 A^1↔A

V V V V

F V F V

• Complementares
𝐴 ∨ 𝐴′ ⇔ 1
𝐴 ∧ 𝐴′ ⇔ 0
Leis de De Morgan
O matemático inglês Augusto De Morgan (1806 – 1871) foi o primeiro a enunciar
algumas equivalências lógicas (e de conjuntos). Estas equivalências convertem
operações lógicas E em OU e vice-versa e são amplamente utilizadas na construção
de sistemas lógicos:

(A v B)’  A’ ^ B’

(A ^ B)’  A’ v B’
Leis de De Morgan

Na prática, não importa o número de proposições. Ex.:

(A v B v C v D)’  A’ ^ B’ ^ C’ ^ D’

(A ^ B ^ C ^ D ^ E)’  A’ v B’ v C’ v D’ v E’
 Questões Poscomp (1/7)
Poscomp[2013, q11]: Considere as sentenças a
seguir:
P: Pedro faz as tarefas todos os dias.
Q: Pedro terá boas notas no final do ano.
Assinale a alternativa que apresenta, corretamente, a tradução em
linguagem simbólica da negação da sentença composta a seguir:
“Se Pedro faz as tarefas todos os dias, então Pedro terá boas notas
no final do ano.”
1. P → Q
2. P ↔ Q
3. P ^ ~Q
4. ~P ^ ~Q
5. ~P ^ Q
 Questões Poscomp (2/7)
Poscomp[2013, q13]: Admita que um novo conectivo binário, rotulado pelo
símbolo ↕, seja definido pela tabela-verdade ao lado. Com base nessa
definição e nas operações usuais com os conectivos v, ^ e ~, considere as
afirmativas a seguir.
I. P ↕ Q é equivalente a Q ↕ P. P Q P↕Q

II. (P ↕ Q) v (Q ↕ P) não é uma contingência. V V F

III. (Q ↕ P) ^ (P ↕ Q) é uma contradição. V F V

IV. ~[(Q ↕ P) ^ (P ↕ Q)] é uma tautologia. F V F

Assinale a alternativa correta. F F F

a) Somente as afirmativas I e II são corretas.

b) Somente as afirmativas I e IV são corretas.
c) Somente as afirmativas III e IV são corretas.
d) Somente as afirmativas I, II e III são corretas.
e) Somente as afirmativas II, III e IV são corretas.
Questões Poscomp (3/7)
Questões Poscomp (4/7)
Questões Poscomp (5/7)
Questões Poscomp (6/7)
Questões Poscomp (7/7)
LÓGICA PROPOSICIONAL
 Argumentos Válidos
Um argumento pode ser representado em forma simbólica como

𝑃1 ∧ 𝑃2 ∧ 𝑃3 ∧ ⋯ ∧ 𝑃𝑛 → 𝑄

Onde 𝑃1 , 𝑃2 , 𝑃3 … são proposições dadas, chamadas de

hipóteses do argumento, e Q é a conclusão.

Em geral, 𝑃𝑖 𝑒 𝑄 representam fbf’s.

Quando que deve ser considerado um argumento válido?

 Argumentos Válidos
Quando deve ser considerado um argumento válido?

Q é uma conclusão lógica de 𝑃1 , … , 𝑃𝑛 sempre que a verdade das

proposições 𝑃1 , … , 𝑃𝑛 implica na verdade de Q.

Considere o argumento (contra-exemplo):

“Dilma Rousseff é a presidente do Brasil. Florianópolis é a capital
de Santa Catarina. Portanto, o dia tem 24 horas”.
𝐴∧𝐵 →𝐶

Duas hipóteses e a conclusão, mas nesse caso não consideramos

o argumento válido, pois a conclusão é um fato verdadeiro isolado
das hipóteses.
 Argumentos Válidos
Um argumento válido deveria ser intrinsicamente verdadeiro,
sendo assim, segue definição.

Definição: A fbf proposicional

𝑃1 ∧ 𝑃2 ∧ 𝑃3 ∧ ⋯ ∧ 𝑃𝑛 → 𝑄
é um argumento válido quando for um tautologia.

Obs: no último exemplo o argumento (𝐴 ∧ 𝐵 → 𝐶) não é uma

tautologia, por isso não era um argumento válido.
 Argumentos Válidos
Exemplo 1)
“Se Dilma Rousseff for presidente do Brasil, então Michel Temer é o
vice-presidente. Dilma Rousseff é presidente do Brasil. Portanto,
Michel Temer é o vice-presidente do Brasil”.

Duas hipóteses:
1. Se Dilma Rousseff for presidente do Brasil, então Michel Temer é
o vice-presidente
2. Dilma Rousseff é presidente do Brasil.
Conclusão:
Michel Temer é o vice-presidente do Brasil.
Representação simbólica: 𝐴 → 𝐵 ∧ 𝐴 → 𝐵, que é uma tautologia.
Ex. 2: Validade de Argumentos
Argumento: P1 ^ P2 → Q
P1: “Se está chovendo, então há nuvens.”
P2: “Está chovendo.”
Q: “Há nuvens.”
Proposições:
A: Está chovendo.
B: Há nuvens
Dedução/validação:
P1: A → B
Válido?
P2: A
Q: B
Ex. 3: Validade de Argumentos
Argumento: P1 ^ P2 → Q
P1: “Se está chovendo, então há nuvens.”
P2: “Há nuvens.”
Q: “Está chovendo.”
Proposições:
A: Está chovendo.
B: Há nuvens
Dedução/validação:
P1: A → B
P2: B Válido?

Q: A
 Regra de Dedução
Sequência de demonstração:

Hipóteses: 𝑷𝟏 , 𝑷𝟐 , … , 𝑷𝒏
Fbf’s: fbf1, fbf2,...
Conclusão: Q.
 Lógica Proposicional
Existem, basicamente, dois tipos de regra de dedução:
equivalências e inferências.

Equivalências permitem que as fbf’s sejam reescritas mantendo o

valor lógico.

Inferências permitem a dedução de novas fbf’s a partir de fbf’s

anteriores.
Regras de Equivalência
 Regras de Equivalência
Exemplo: suponha o argumento proposicional
(𝐴′ ∨ 𝐵′) ∨ 𝐶
então uma sequência de demonstração ficaria,

1. (𝐴′ ∨ 𝐵′) ∨ 𝐶 (hipótese)

2. 𝐴 ∧ 𝐵 ′ ∨ 𝐶 1, 𝐷𝑒 𝑀𝑜𝑟𝑔𝑎𝑛
3. 𝐴 ∧ 𝐵 → 𝐶 (2, condicional)
Regras de Inferência
 Regras de Inferência
Se uma ou mais fbf’s contidas na primeira coluna das regras de
inferência, fazem parte de uma sequência da demonstração, então
podemos substituí-las pela fbf contida na segunda coluna.

As regras de inferência não funcionam em ambas direções.

Exemplo: suponha 𝐴 → (𝐵^𝐶) e A duas hipóteses de um argumento,

uma sequência de demonstração seria:
1. 𝑨 → (𝑩^𝑪) (hipótese)
2. A (hipótese)
3. B^C (1,2, modus ponens)
(exemplo Dilma)
 Regras de Inferência
Exemplo: dê o próximo passo da demonstração e justifique.

1. (𝑨^𝑩′) → 𝑪 (hipótese)
2. C’ (hipótese)
3. ?
Exemplo 1: Demonstração
Argumento: P1 ^ P2 → Q
P1: “Se está chovendo, então há nuvens.”
P2: “Está chovendo.”
Q: “Há nuvens.”
Proposições:
A: Está chovendo.
B: Há nuvens
Dedução/validação:
P1: A → B
Válido?
P2: A
Q: B
Argumento original: Validade?
P1: A → B 1. A → B (hip, V)
P2: A 2. A (hip, V)
Foi possível chegar à
Q: B mesma conclusão 3. B (mp, 1 ,2)

O argumento é
válido!
Exemplo 2
Argumento: P1 ^ P2 → Q
P1: “Se está chovendo, então há nuvens.”
P2: “Há nuvens.”
Q: “Está chovendo.”
Proposições:
A: Está chovendo.
B: Há nuvens
Dedução/validação:
P1: A → B
Vamos tentar deduzir?? Não, pois
P2: B não é tautologia, logo, não é um
argumento válido.
Q: A
 Exemplo de Demonstração Completa
Usando lógica proposicional, prove que o argumento é válido.
𝐴 ∧ 𝐵 → 𝐶 ∧ 𝐴 ∧ 𝐵 → 𝐷 ∨ 𝐶′ ∧ 𝐵 → 𝐷

Exercício 1: provar a validade de:

𝐴 → 𝐵 ∨ 𝐶 ∧ 𝐵′ ∧ 𝐶 ′ → 𝐴′

Exercício 2: provar a validade de:

𝐴′ ∧ 𝐵 ∧ 𝐵 → 𝐴 ∨ 𝐶 →𝐶
 Método Dedutivo
Suponha que o argumento que queremos provar tenha a forma

𝑃1 ∧ 𝑃2 ∧ 𝑃3 ∧ ⋯ ∧ 𝑃𝑛 → (𝑅 → 𝑆)
onde a conclusão é uma implicação.

Ao invés de usar 𝑃1 , … , 𝑃𝑛 como hipótese e 𝑅 → 𝑆 de conclusão, o

método dedutivo nos permite adicionar R como hipótese,

𝑃1 ∧ 𝑃2 ∧ 𝑃3 ∧ ⋯ ∧ 𝑃𝑛 ∧ 𝑅 → 𝑆
 Exemplo
Use lógica proposicional para provar

𝐴→ 𝐴→𝐵 → (𝐴 → 𝐵)

𝐴 → 𝐵 ∧ 𝐵 → 𝐶 → (𝐴 → 𝐶) (silogismo hipotético)
 Exercícios
Use lógica proposicional para provar

1. 𝐴′ ∨ 𝐵 ∧ 𝐵 → 𝐶 → 𝐴 → 𝐶

2. 𝐴 → 𝐵 ∧ 𝐶′ ∨ 𝐴 ∧ 𝐶 → 𝐵
 Argumentos Verbais
Exemplo 1) Considere o argumento “Se as taxas de juros caírem,
o mercado imobiliário vai melhorar. A taxa federal de descontos
vai cair ou o mercado imobiliário não vai melhorar. As taxas de
juros vão cair. Portanto, a taxa federal de descontos vai cair.

Resolução:
J: A taxa de juros vai cair.
I: O mercado imobiliário vai melhorar.
F: A taxa federal de descontos vai cair.

O argumento fica: 𝐽 → 𝐼 ∧ 𝐹 ∨ 𝐼 ′ ∧ 𝐽 → 𝐹, basta provar se o

argumento é válido.
 Argumentos Verbais

Exemplo 2) “Meu cliente é canhoto mas, se o diário não tiver

sumido, então meu cliente não é canhoto; portanto o diário
sumiu.”

Exemplo 3) “Se segurança é um problema, então o controle será

aumentado. Se segurança não é um problema, então os
negócios na Internet irão aumentar. Portanto, se o controle não
for aumentado, os negócios na Internet crescerão.”