Cálculo proposicional

Última revisão em 3 de março de 2009

Proposição

Proposições são sentenças afirmativas declarativas que não sejam ambı́güas e que possuem
a propriedade de serem ou verdadeiras ou falsas, mas não ambas.
Exemplos:
. “Gatos têm quatro patas”
· “1 + 2 = 3”
. “A Terra é quadrada”
. “3 é um número primo”
Exemplos de sentenças que não são proposições:
. “O que estou dizendo agora é mentira”
. “Irá chover amanhã”
. “Onde está a chave ?”

Cálculo proposicional

É uma sub-área da lógica simbólica que estuda um conjunto formal de regras que permitem
a análise e manipulação de proposições. Algumas referências para este assunto são
• Garnier, R. and Taylor, J. (1992). Discrete Mathematics for New Technology. Adam Hilger.
• Mendelson, E. (1977). Álgebra Booleana e Circuitos de Chaveamento. Mcgraw-Hill.
• Ross, K. A. and Wright, C. R. B. (1992). Discrete Mathematics. Prentice Hall, 3rd edition.

Conectivos lógicos

Proposições simples podem ser concatenadas através de conectivos lógicos E, OU, NÃO
para formar novas proposições compostas.
Exemplos: Das proposições “Fulano está cansado” e “Ciclano está cozinhando”, pode-se
formas as proposições “Fulano está cansado E Ciclano está cozinhando”, ou “Fulano está
cansado OU Ciclano está cozinhando”, ou “Fulano NÃO está cansado”.

Notações

Proposições serão representadas por letras como x, y, z, p, q, etc. Em geral, as letras que
representam proposições simples são denominadas variáveis (lógicas).

1
Nina S. T. Hirata (DCC/IME-USP) — Notas de aula de MAC0329 (2003∼2010) 2

Proposições têm valor lógico ou V (VERDADEIRO) ou F (FALSO).

Utilizaremos os seguintes sı́mbolos para representar os conectivos lógicos:

Conectivo sı́mbolo
E ∧
OU ∨
NÃO ¬

Os conectivos implicação condicional (→) e bicondicional ↔

Em adição aos três conectivos vistos acima, é comum também a utilização dos condicionais SE-ENTÃO
(→) e SE-E-SOMENTE-SE (↔).
Para proposições x e y quaiquer, expressões do tipo “SE x ENTÃO y” são relativamente comuns,
especialmente na matemática. No contexto de cálculo proposicional devemos nos limitar aos valores
V e F . Nosso interesse é saber o valor da expressão x → y. Parece razoável pensar que se x é V e y
é V, então a expressão x → y é também V. Similarmente, se x é V e y é F, então x → y é F. Para
completar a definição, associa-se V para x → y quando x é F.
Uma outra forma de encarar este condicional é pensar que ao se partir de uma verdade sempre chega-se
a uma verdade. Então “partir de uma verdade e chegar a uma verdade” é verdadeiro enquanto “partir
de uma verdade e chegar a algo falso” é falso. Já quando partimos de algo falso pode-se chegar tanto
a uma verdade quanto a algo falso.

Representamos expressões do tipo “x se, e somente se, y” por x ↔ y. A expressão x ↔ y é verdadeira

quando x e y tomam o mesmo valor e é equivalente à expressão (x → y) ∧ (y → x).

Expressão lógica

As proposições podem ser representadas por expressões envolvendo várias variáveis como
em x ∧ y, (x ∧ y) ∨ ¬z, etc. As regras para a formação de expressões são:
(1) Qualquer variável (letra) representando uma proposição é uma expressão lógica
(2) Se p e q são expressões lógicas, então (¬p), (p ∧ q), (p ∨ q), (p → q) e (p ↔ q) são
expressões lógicas.
Exemplos: Alguns exemplos de expressões lógicas
(x → (y ∨ (z ∧ (¬x))))
(x ∧ y ∧ z) ∨ (¬x ∧ ¬y ∧ ¬z)
Os parênteses servem para explicitar as precedências (da mesma forma com que estamos
acostumados em relação às expressões aritméticas usuais).

Tabela-verdade

Da mesma forma que proposições simples podem ser ou verdadeiras ou falsas, proposições
compostas podem também ser ou verdadeiras ou falsas. O valor-verdade de uma expressão
que representa uma proposição composta depende dos valores-verdade das sub-expressões
que a compõem e também a forma pela qual elas foram compostas.
3 Cálculo proposicional

Tabelas-verdade são diagramas que explicitam a relação entre os valores-verdade de uma

expressão composta em termos dos valores-verdade das subexpressões e variáveis que a
compõem. Mostramos a seguir as tabelas-verdade para os conectivos lógicos ¬, ∧, e ∨.
Suponha que x e y são duas variáveis lógicas.

x y x∧y x y x∨y
x ¬x F F F F F F
F V F V F F V V
V F V F F V F V
V V V V V V

A tabela-verdade lista todas as possı́veis combinações de valores-verdade V e F para as

variáveis envolvidas na expressão cujo valor lógico deseja-se deduzir. Assim, quando a
expressão possui duas variáveis, sua tabela-verdade contém 4 linhas. Em geral, se uma
expressão possui n variáveis, sua tabela-verdade contém 2n linhas.
As tabelas-verdade dos condicionais SE-ENTÃO e SE-E-SOMENTE-SE são mostradas a
seguir.

x y x→y x y x↔y
F F V F F V
F V V F V F
V F F V F F
V V V V V V

Tanto → como ↔ podem ser expressos em termos dos demais conectivos. Por isso, eles
poderiam ser considerados não necessários. Porém, a sua utilização é comum devido a
conveniência para expressar certas proposições.

Exemplos de tabela-verdade
A tabela verdade da expressão (x ∨ (y ∧ z)) → y é mostrada a seguir

x y z y∧z x ∨ (y ∧ z) (x ∨ (y ∧ z)) → y
F F F F F V
F F V F F V
F V F F F V
F V V V V V
V F F F V F
V F V F V F
V V F F V V
V V V V V V

A mesma tabela pode ser expressa em formas mais concisas, como as mostradas a seguir. Os números
na última linha da tabela indicam a ordem na qual as respectivas colunas devem ser preenchidas.
Nina S. T. Hirata (DCC/IME-USP) — Notas de aula de MAC0329 (2003∼2010) 4

(x ∨ (y ∧ z)) → y x y z (x ∨ (y ∧ z)) → y
F F F F F V F F F F F F V
F F F F V V F F F V F F V
F F V F F V V F V F F F V
F V V V V V V F V V V V V
V V F F F F F V F F V F F
V V F F V F F V F V V F F
V V V F F V V V V F V F V
V V V F V V V V V V V F V
1 3 1 2 1 4 1 1 1 1 3 2 4

Exercı́cio: Faça a tabela-verdade para as expressões:

a) ¬(x ∧ y) c) ¬((x ∨ y) → z)
b) ¬(x ∨ y) → z d) y ∧ ¬(x ∨ y)

Tautologias e contradições

Uma expressão é uma tautologia se ela toma valor V para todas as possı́veis atribuições
de valor V e/ou F para as variáveis presentes nela.
Exemplo: As expressões x → x e x ∨ ¬x são tautologias.

Uma expressão é uma contradição se ela toma valor F para todas as possı́veis atribuições
de valor V e/ou F para as variáveis presentes nela.
Exemplo: Se a expressão x é uma tautologia, então ¬x é uma contradição. Similarmente,
se x é uma contradição, então ¬x é uma tautologia.

Exercı́cio: Para cada expressão abaixo, responda se ela é uma tautologia, uma contradição ou nen-
huma das duas.
a) x ∧ ¬x d) (x ∨ y) ∧ (¬x ∨ y) ∧ (x ∨ ¬y)
b) (x → y) → y) → y e) (x → (y → z)) ↔ ((x ∧ y) → z)
c) (x ∧ ¬y) ∨ (¬x ∧ y) f) ((x → y) ∨ (y → z)) → (x → (y ∨ z))

Implicação e equivalência lógica

Dizemos que uma expressão x implica logicamente uma expressão y se, e somente se,
cada atribuição de valor às variáveis que torna x verdadeira torna y verdadeira também.
Utilizamos a notação x ⇒ y para dizer que x implica logicamente y.
Teorema: Uma expressão x implica logicamente y se, e somente se, x → y é uma tautolo-
gia.
Prova: x implica logicamente y se, e somente se, sempre que x for verdadeira, y também
o for. Portanto, x implica logicamente y se, e somente se, nunca se dá o caso em que x é
verdadeira e y é falsa. Mas isto significa que a expressão x → y nunca é falsa, ou seja, que
x → y é uma tautologia.

Duas expressões são logicamente equivalentes se a tabela-verdade delas forem iguais.

Utilizamos a notação ⇔.
5 Cálculo proposicional

Teorema: x e y são logicamente equivalentes se, e somente se, x ↔ y é uma tautologia.

Equivalências lógicas

E1. Comutatividade

(a) x ∨ y ⇔ y ∨ x
(b) x ∧ y ⇔ y ∧ x

E2. Associatividade

(a) (x ∨ y) ∨ z ⇔ x ∨ (y ∨ z)
(b) (x ∧ y) ∧ z ⇔ x ∧ (y ∧ z)

E3. Distributividade

(a) x ∧ (y ∨ z) ⇔ (x ∧ y) ∨ (x ∧ z)
(b) x ∨ (y ∧ z) ⇔ (x ∨ y) ∧ (x ∨ z)

E4. Idempotência

(a) x ∨ x ⇔ x
(b) x ∧ x ⇔ x

E5. Leis de absorção

(a) x ∨ (x ∧ y) ⇔ x
(b) x ∧ (x ∨ y) ⇔ x
(c) (x ∧ y) ∨ ¬y ⇔ x ∨ ¬y
(d) (x ∨ y) ∧ ¬y ⇔ x ∧ ¬y

E6. Dupla negação

(a) ¬¬x ⇔ x

E7. Leis de De Morgan

(a) ¬(x ∨ y) ⇔ (¬x ∧ ¬y)

(b) ¬(x ∧ y) ⇔ (¬x ∨ ¬y)

E8. Tautologias e contradições

(a) (V ∧ x) ⇔ x
(b) (V ∨ x) ⇔ V
(c) (F ∧ x) ⇔ F
(d) (F ∨ x) ⇔ x

Exemplo: Vamos verificar a equivalência E7(a). Para isso montamos a tabela-verdade:

Nina S. T. Hirata (DCC/IME-USP) — Notas de aula de MAC0329 (2003∼2010) 6

x y ¬ (x ∨ y) ↔ (¬x ∧ ¬y)
F F V F V V V V
F V F V V V F F
V F F V V F F V
V V F V V F F F
1 1 3 2 4 2 3 2
Podemos ver que ¬(x ∨ y) ↔ (¬x ∧ ¬y) é uma tatutologia (coluna indicada por 4). Ou
ainda, podemos ver que o valor-verdade de ¬(x ∨ y) e (¬x ∧ ¬y) (colunas indicadas por 3)
são iguais para todas as linhas da tabela. Logo, ¬(x ∨ y) ⇔ (¬x ∧ ¬y).

Exercı́cio: Mostre as equivalências E3(a), E5(a), E5(d), E8(a) e E8(c).

Outras equivalências

E9. Contrapositivo

x → y ⇔ ¬y → ¬x

E10. Eliminação de condicionais

(a) x → y ⇔ ¬x ∨ y
(b) x → y ⇔ ¬(x ∧ ¬y)

E11. Eliminação de bicondicionais

(a) x ↔ y ⇔ (x ∧ y) ∨ (¬x ∧ ¬y)

(b) x ↔ y ⇔ (¬x ∨ y) ∧ (¬y ∨ x)

Exercı́cio: Mostre as equivalências E9, E10(a), E10(b), E11(a) e E11(b).

Exercı́cio: Mostre que

a) (x ∧ y) ∨ (x ∧ ¬y) ↔ x
b) (x → y) ↔ (¬y → ¬x)

Algumas implicações lógicas

I1. p ⇒ (p ∨ q)

I2. (p ∧ q) ⇒ p

I3. (p → C) ⇒ ¬p (C denota uma contradição)

I4. [p ∧ (p → q)] ⇒ q

I5. [(p → q) ∧ ¬q] ⇒ ¬p

7 Cálculo proposicional

I6. [(p ∨ q) ∧ ¬p] ⇒ q

I7. p ⇒ [q → (p ∧ q)]

I8. [(p ↔ q) ∧ (q ↔ r)] ⇒ (p ↔ r)

I9. [(p → q) ∧ (q → r)] ⇒ (p → r)

Exercı́cio: Mostre as implicações I1, I3, I4, I6, I8 e I9.

Nina S. T. Hirata (DCC/IME-USP) — Notas de aula de MAC0329 (2003∼2010) 8

Mais dois conectivos

Barra de Sheffer (Sheffer’s stroke): Significando “não ambos verdadeiro”, é definido

pela seguinte tabela-verdade

x y x|y
F F V
F V V
V F V
V V F

Negação conjunta (joint denial): Significando “nem um e nem outro”, é definido pela
seguinte tabela-verdade

x y x↓y
F F V
F V F
V F F
V V F

Exercı́cio: Mostre que ¬x ⇔ x|x e ¬x ⇔ x ↓ x.

Exercı́cio: Mostre que x ∨ y ⇔ (x|x)|(y|y) e x ∧ y ⇔ (x ↓ x) ↓ (y ↓ y).

Redundâncias ou Sistemas adequados de conectivos

Toda expressão determina uma função-verdade que pode ser expressa via tabelas-verdade.
n
Existem 2(2 ) funções-verdade de n variáveis já que existem 2n possı́veis atribuições de
valor-verdade para essas n variáveis e para cada uma dessas atribuições a função pode
tomar valor V ou F.
Teorema: Toda função-verdade pode ser expressa por uma expressão envolvendo apenas
os conectivos ∨, ∧ e ¬.
Um conjunto de conectivos é dito formar um sistema adequado de conectivos se toda
função-verdade pode ser expressa por expressões que envolvem apenas conectivos do con-
junto.
Os seguintes conjuntos são sistemas adequados de conectivos:
a) {∨, ∧, ¬}
b) {∨, ¬}
c) {∧, ¬}
d) {¬, →}
e) {|}
f) {↓}
9 Cálculo proposicional

Exemplo: As quatro funções-verdade com uma variável são :

f0 f1 f2 f3
x x ¬x x ∨ ¬x x ∧ ¬x
F F V V F
V V F V F

Exercı́cio: Liste todas as funções-verdade com duas variáveis.