Fundamentos de matemática:
Proposições, conectivos e tabelas-verdade
∗
Prof. Renato Mello, 06 de fevereiro de 2012
1 Denições
Uma proposição (ou sentença) é uma frase que pode ser apenas verdadeira ou falsa.
São exemplos de proposições:
1. A seleção brasileira é pentacampeã mundial.
2. Todo número primo é ímpar.
3.
5<
√
26.
4. Existe vida inteligente fora da Terra.
Todas as frases acima são proposições. As frases 1 e 3 são verdadeiras, a frase 2 é falsa
e a frase 4 é certamente verdadeira ou falsa, embora
a priori
seja impossível determinar
qual dos dois acontece.
Observe que o contexto importa.
Se no primeiro item o contexto trata da seleção
masculina de futebol, como é usual, a frase é verdadeira, mas o mesmo não vale para a
seleção de feminina, ou a de basquete.
Já as frases:
5. Quem faz aniversário hoje?
6. O que esta frase diz é mentira.
7. Ele não veio hoje.
8. x+1<12
não são proposições. A frase 5 é uma pergunta, portanto não tem sentido verdadeiro nem
falso. A frase 6 é um paradoxo, não pode ser verdadeira nem falsa. A frase 7 não tem
sentido completo, pois
ele
não está especicado, então não é verdadeira nem falsa.
mesmo vale para a frase 8, com relação a
O
x.
Chamamos de valor-verdade (ou valor lógico) de uma proposição a verdade (V)
se ela for verdadeira ou a falsidade (F) se ela for falsa.
1.1 Princípios da lógica matemática
1. Princípio da Não-Contradição: Uma proposição não pode ser verdadeira e falsa
ao mesmo tempo;
2. Princípio do Terceiro Excluído: Toda proposição é verdadeira ou falsa, isto é,
verica-se sempre um desses casos, não havendo outra possibilidade.
∗
Versão 1.01
1
2
2 Proposições compostas e conectivos
2 Proposições compostas e conectivos
Usando conectivos, é possível criar proposições maiores (ditas compostas) a partir
de menores, de modo que o valor da proposição obtida dependa apenas do valor das
proposições iniciais.
Os principais conectivos lógicos são não e, ou, se. . . então e se e somente se,
simbolizados respectivamente por
¬, ∧, ∨, →, ↔.
Exemplos de proposições compostas:
1. O número 6 é par e o número 7 é impar.
2. O número 6 é par ou o número 8 é impar.
3. Se Carlos é engenheiro então ele sabe matemática.
4. Um triângulo é eqüilátero se e somente se é eqüiângulo.
Quando uma proposição não é composta, ela é dita simples (não pode ser decomposta
em proposições menores).
2.1 Conectivos
2.1.1
Negação
∼), é um conectivo unário, isto é, age sobre uma
proposição p, a proposição ¬p tem o valor lógico oposto ao
p for falsa e falsa se p for verdadeira. Lê-se não p.
A negação, simbolizada por
única proposição. Dada uma
de
p,
ou seja, é verdadeira se
¬
(ou
A negação tem a seguinte tabela-verdade:
¬p
p
2.1.2
e
q,
V
∧,
cria uma proposição
a qual assume valor verdadeiro caso
menos uma for falsa. Lê-se p e
p
e
q
p∧q
a partir das proposições
sejam ambas verdadeiras e falso se pelo
q .
q
p∧q
F
F
F
F
V
F
V
F
F
V
V
V
p
2.1.3
F
F
Conjunção
A conjunção, simbolizada por
p
V
Disjunção
A disjunção, simbolizada por
∨, cria uma proposição p∨q a partir das proposições p e
q , a qual assume valor verdadeiro caso pelo menos uma das duas proposições verdadesiras
seja verdadeira e falso se forem ambas falsas. Lê-se p ou q .
3
2 Proposições compostas e conectivos
2.1.4
p
q
p∨q
F
F
F
F
V
V
V
F
V
V
V
V
→,
cria uma proposição
Condicional
O condicional, simbolizado por
verdadeiro a menos que
q
p → q que assume
p então q .
valor
verdadeira. Lê-se Se
q
p→q
F
F
V
F
V
V
V
F
F
V
V
V
p
2.1.5
p
seja falsa sendo
Bicondicional
O bicondicional, simbolizado por
verdadeiro se
peq
p se e somente se
↔,
cria uma proposição
tiverem o mesmo valor e falso se
peq
p↔q
que assume valor
tiverem valores diferentes. Lê-se
q .
p
q
p↔q
F
F
V
F
V
F
V
F
F
V
V
V
Observação. Precedência de operadores.
Os operadores em uma fórmula são calcu-
lados na seguinte ordem (da maior para a menor prioridade):
1. Negação;
2. Conjunção e disjunção;
3. Condicional e bicondicional.
Por isso, por exemplo, não há a necessidade de parênteses na fórmula
é equivalente à fórmula
(p ∧ (¬p)) → (q ∨ p).
p ∧ ¬p → q ∨ p,
que
Quando a prioridade é a mesma, calcula-se
da esquerda para a direita.
2.2 Tabelas-verdade
Conforme visto na seção anterior, as tabelas-verdade podem esclarecer a relação entre
o valor lógicos de uma proposição composta e os valores lógicos das proposições simples
que as compõem. Muitas vezes, usamos tabelas-verdade para estudar fórmulas que geram
proposições compostas por muitas proposições simples e muitos conectivos. Para isso,
n
precisamos de 2 linhas, em que n é o número de proposições simples que a compõem,
e de várias colunas se quisermos esclarecer etapas do cálculo proposicional. Considere a
proposição
(p ∨ q) ∧ ¬(p ∧ q).
4
2 Proposições compostas e conectivos
p
q
p∨q
p∧q
F
F
F
F
V
F
F
V
V
F
V
V
V
F
V
F
V
V
V
V
V
V
F
F
Veja que a tabela tem exatamente
Observação.
notado por
22 = 4
¬(p ∧ q) (p ∨ q) ∧ ¬(p ∧ q)
linhas.
A fórmula acima obtém o conectivo chamado disjunção exclusiva, de-
˙ ,
p∨q
o qual resulta em verdade se exatamente uma das proposições,
p
ou
q,
é
verdadeira, e em falsidade se ambas são falsas ou ambas são verdadeiras.
2.3 Tautologias, contradições e relações entre proposições
2.3.1
Tautologias
Uma tautologia é uma proposição composta que é sempre verdadeira, independente
dos valores lógicos das proposições simples que a compõem. Por exemplo, a proposição
composta
2.3.2
p ∧ ¬p → q ∨ p
é uma tautologia. (construir tabela-verdade)
Contradições
Uma contradição (ou proposição logicamente falsa) é uma proposição composta
que é sempre falsa, independente dos valores lógicos das proposições simples que a compõem. Por exemplo,
2.3.3
p ∧ ¬p.
(construir tabela-verdade)
Equivalência
A equivalência é uma relação entre duas proposições compostas. Dizemos que duas
proposições compostas
P
e
Q são equivalentes se P ↔ Q for uma tautologia.
Isso signica
que elas assumem os mesmos valores lógicos para as mesmas possibilidades de valores
dados às proposições simples que as compõem. Em outras palavras, as tabelas-verdade
de ambas têm os valores da última coluna idênticos. Representamos
Por exemplo,
2.3.4
p→q
e
¬q → ¬p
P ⇔ Q.
são equivalentes. (construir tabelas-verdade)
Implicação
A implicação é uma relação entre duas proposições compostas. Dadas duas propo-
P → Q for uma tautologia. Isso
signica que Q é verdadeira na tabela-verdade sempre que P for verdadeira, mas pode
ser verdadeira ou falsa em caso contrário. Representamos P ⇒ Q.
Por exemplo, (p → q) ∧ ¬q implica ¬p. (construir tabelas-verdade)
sições compostas
P
e
Q,
dizemos que
P
implica
Q
se