Tabela Verdade e Lógica

Prévia do material em texto

Tabela Verdade e Lógica
Apresentação
Nesta Unidade de Aprendizagem, estudaremos a análise de proposições e a representação de 
tabela verdade de proposições simples e compostas, utilizando os conectivos e, ou e não, que serão 
aplicados no desenvolvimento de algoritmos. 
Bons estudos.
Ao final desta Unidade de Aprendizagem, você deve apresentar os seguintes aprendizados:
Construir a tabela verdade dos conectivos lógicos e, ou e não.•
Usar os conectivos e, ou e não na avaliação de proposições.•
Avaliar proposições simples e compostas.•
Laiane
Desafio
Considerando que q e r representam proposições básicas e que as expressões q v r e ~(q v r) são 
proposições compostas, em que as proposições representam:
q : Marlene trouxe sanduíche para o lanche. 
r : Antônio trouxe refrigerante para o lanche.
a) Baseado nas atribuições acima para q e r, pode-se concluir que ~( q v r) v ( q v r) é sempre (V) 
verdadeiro, não importando se Marlene trouxe ou não sanduíche e Antônio trouxe ou não 
refrigerante para o lanche? Responda sim ou não e justifique sua resposta comprovando-a com a 
construção da tabela verdade para a proposição ~( q v r) v ( q v r).
b) Baseado nas atribuições acima, pode-se dizer que ~(q ^ r) é equivalente a (~q v ~r) para todas as 
valorações possíveis para a tabela verdade para Marlene e Antônio. Responda sim ou não e 
justifique sua resposta comprovando-a com a construção da tabela verdade para as duas 
proposições.
Laiane
PADRÃO DE RESPOSTA ESPERADO: a) Sim, é correto concluir que a proposição ~( q v r) v ( q v r) é sempre (V) verdadeira, não importando a valoração atribuída às proposições q e r.Quantidade de linhas da tabela verdade: 2n = 22 = 4 linhas.Todos os valores encontrados das 4 linhas das preposições deram V-Verdadeiro.b) Sim, as duas proposições são equivalentes, conforme mostra as tabelas verdade abaixo, as duas deram a mesma valoração. A proposição (~q v ~r) é a negação da proposição ~(q ^ r).Quantidade de linhas da tabela verdade: 2n = 22 = 4 linhas.q     r     q^r    ~(q^r)V    V      V         FV    F      F         VF    V      F         VF    F      F         V_______//_________q     r    ~q    ~r    (~qv~r)V    V     F      F         FV    F     F      V         VF    V     V      F         VF    F     V      V         V As duas tabelas verdade deram as mesmas valorações: F, V, V e V.
Infográfico
O esquema mostra os principais temas abordados nesta Unidade. 
Conteúdo do livro
Para a construção de algoritmos e de programas eficientes e eficazes, precisamos compreender os 
operadores lógicos, além de construir e analisar a tabela verdade para que possamos desenvolver 
algoritmos que avaliam as expressões lógicas de forma correta.
Para auxiliar no estudo do conteúdo proposto, acompanhe o Capítulo 4 da obra Matemática 
Discreta de Seymour Lipschutz e Marc Lipson. O livro servirá como base para esta Unidade de 
Aprendizagem. No capítulo selecionado, serão apresentados a tabela verdade e os operadores 
lógicos aplicados em pseudolinguagem.
Boa leitura!
Laiane
Laiane
Laiane
Terceira edição
Seymour Lipschutz e Marc Lipson
Problema 
 Resolvido
A AJUDA PERFEITA PARA SEUS ESTUDOS!
Mais de 450 problemas resolvidos
 Explicações claras e concisas de todos os conceitos
 Inclui conjuntos, teoria dos grafos, álgebra Booleana, 
cálculo proposicional, máquinas de Turing e muito mais!
Matemática 
Discreta
L767m Lipschutz, Seymour. 
 Matemática discreta [recurso eletrônico] / Seymour 
 Lipschutz, Marc Lars Lipson ; tradução técnica: Adonai
 Schlup Sant’anna. – 3. ed. – Dados eletrônicos. – Porto 
 Alegre : Bookman, 2013.
 (Coleção Schaum)
 Editado também como livro impresso em 2013.
 ISBN 978-85-65837-78-1
 1. Matemática. 2. Matemática discreta. I. Lipson, Marc 
 Lars. II. Título.
CDU 51
Catalogação na publicação: Ana Paula M. Magnus – CRB 10/2052
SEYMOUR LIPSCHUTZ é docente do Departamento de Matemática da Temple University e lecionou no Polytechnic 
Institute of Brooklyn. Obteve seu Ph.D. no Courant Institute of Mathematical Sciences da New York University, em 
1960. É um dos autores mais prolíficos da Coleção Schaum e escreveu também Probability: Finite Mathematics, 2.ed.; 
Beginning Linear Algebra; Set Theory; Essential Computer Mathematics e Álgebra Linear, 2.ed. (publicado pela Book-
man Editora).
MARC LARS LIPSON é docente do Departamento de Matemática da University of Virginia e lecionou na University 
of Georgia. Obteve seu Ph.D. em finanças na University of Michigan, em 1994. É também coautor com Seymour Lips-
chutz de 2000 Solved Problems in Discrete Mathematics e de Álgebra Linear, 3.ed. (publicado pela Bookman Editora).
Lógica e Cálculo Proposicional
Capítulo 4
4.1 INTRODUÇÃO
Muitos algoritmos e demonstrações usam expressões lógicas como:
“SE p ENTÃO q” ou “SE p1 e p2, ENTÃO q1 OU q2”
Logo, é necessário conhecer os casos nos quais essas expressões são VERDADEIRAS ou FALSAS, ou seja, saber 
o “valor verdade” de tais expressões. Discutimos essas questões neste capítulo.†
Também investigamos o valor verdade de afirmações quantificadas, as quais são expressões que empregam os 
quantificadores lógicos “para todo” e “existe”.‡
4.2 PROPOSIÇÕES E SENTENÇAS COMPOSTAS
Uma proposição (ou sentença) é uma afirmação declarativa que é verdadeira ou falsa, mas não ambas. Considere, 
por exemplo, os seis itens a seguir:
 (i) Gelo flutua na água. (iii) 2 + 2 = 4 (v) Aonde você está indo?
 (ii) A China é na Europa. (iv) 2 + 2 = 5 (vi) Faça seu tema de casa.
Os quatro primeiros são proposições. Os dois últimos não. Além disso, (i) e (iii) são verdadeiras, mas (ii) e (iv) são 
falsas.
Proposições compostas
Muitas proposições são compostas, isto é, formadas por subproposições e vários conectivos discutidos a seguir. 
Tais sentanças são chamadas de proposições compostas. Uma proposição é denominada primitiva se não puder ser 
decomposta em proposições mais simples, ou seja, se não for composta.
Por exemplo, as proposições acima, de (i) a (iv), são primitivas. Por outro lado, as duas proposições a seguir 
são compostas:
“Rosas são vermelhas e violetas são azuis.” e “John é esperto ou ele estuda todas as noites.”
† N. de T.: É importante observar que os autores estão seguindo uma abordagem meramente intuitiva para o cálculo proposi-
cional clássico. Do ponto de vista da lógica matemática, o objetivo do cálculo proposicional não é estabelecer o “valor verdade” 
de expressões.
‡ N. de T.: Normalmente o estudo de quantificadores se faz no cálculo de predicados de primeira ordem e não no cálculo pro-
posicional.
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
MATEMÁTICA DISCRETA70
A propriedade fundamental de uma proposição composta é que seu valor verdade é completamente determi-
nado pelos valores verdade de suas subproposições, junto com a maneira como elas são conectadas para 
formar as proposições compostas. A seção a seguir explora alguns desses conectivos.
4.3 OPERAÇÕES LÓGICAS BÁSICAS
Esta seção discute as três operações lógicas básicas de conjunção, disjunção e negação, as quais correspondem, 
respectivamente, às palavras “e”, “ou” e “não”.
Conjunção, p ∧ q
Quaisquer duas proposições podem ser combinadas pela palavra “e” para formar uma proposição composta chama-
da de conjunção das proposições originais. Simbolicamente,
p ∧ q
que se lê “p e q”, denota a conjunção de p e q. Como p ∧ q é uma proposição, ela tem um valor verdade que depen-
de apenas dos valores verdade de p e q. Especificamente:
Definição 4.1: Se p e q são verdadeiras, então p ∧ q é verdadeira; caso contrário, p ∧ q é falsa.
O valor verdade de p ∧ q pode ser definido equivalentemente pela tabela na Fig. 4-1(a). Aqui a primeira linha 
é uma maneira abreviada de dizer que se p é verdadeira e q é verdadeira, então p ∧ q é verdadeira. A segunda linha 
diz que se p é verdadeira e q é falsa, então p ∧ q é falsa. E assim por diante. Observe que há quatro linhas corres-
pondentes às quatro possíveis combinações de V e F para as duassubproposições p e q. Note que p ∧ q é verdadei-
ra apenas quando p e q são ambas verdadeiras.
p e q p ou q não p
Figura 4-1
Exemplo 4.1 Considere as quatro proposições a seguir:
 (i) Gelo flutua na água e 2 + 2 = 4. (iii) China é na Europa e 2 + 2 = 4.
 (ii) Gelo flutua na água e 2 + 2 = 5. (iv) China é na Europa e 2 + 2 = 5.
Apenas a primeira é verdadeira. As outras são falsas, pois pelo menos uma de suas subproposições é falsa.
Disjunção, p ∨ q
Duas proposições quaisquer podem ser combinadas pela palavra “ou” para formar uma proposição composta cha-
mada de disjunção das proposições originais. Simbolicamente,
p ∨ q
que se lê “p ou q”, denota a disjunção de p e q. O valor verdade de p ∨ q depende apenas dos valores verdade de p 
e q como se segue.
Laiane
Laiane
Laiane
Laiane
Laiane
CAPÍTULO 4 • LÓGICA E CÁLCULO PROPOSICIONAL 71
Definição 4.2: Se p e q são falsas, então p ∨ q é falsa; caso contrário, p ∨ q é verdadeira.
O valor verdade de p ∨ q pode ser definido equivalentemente pela tabela na Fig. 4-1(b). Observe que p ∨ q é 
falsa apenas no quarto caso, quando p e q são ambas falsas.
Exemplo 4.2 Considere as quatro sentenças a seguir:
 (i) Gelo flutua na água ou 2 + 2 = 4. (iii) China é na Europa ou 2 + 2 = 4.
 (ii) Gelo flutua na água ou 2 + 2 = 5. (iv) China é na Europa ou 2 + 2 = 5.
Apenas a última sentença (iv) é falsa. As outras são verdadeiras, uma vez que pelo menos uma de suas subsentenças 
é verdadeira.
Observação: A palavra “ou” é comumente usada de duas maneiras distintas em português. Às vezes, é empregada 
no sentido de “p ou q, ou ambas”, ou seja, pelo menos uma das duas alternativas acontece; e, às vezes, é usada no 
sentido de “p ou q, mas não ambas”, isto é, somente uma das alternativas ocorre. Por exemplo, a afirmação “Ele irá 
para Harvard ou Yale” utiliza “ou” no último sentido, chamado eventualmente de disjunção exclusiva. A menos que 
seja estabelecido o contrário, “ou” deve ser empregado no primeiro sentido. Essa discussão aponta para a precisão 
conquistada em nossa linguagem simbólica: p ∨ q é definida por sua tabela verdade e sempre significa “p e/ou q”.
Negação, ¬ p
Dada qualquer sentença p, outra sentença, chamada de negação de p, pode ser formada escrevendo-se “Não é ver-
dade que . . .” ou “É falso que . . .” antes de p ou, se possível, inserindo em p a palavra “não”. Simbolicamente, a 
negação de p, que se lê “não p ”, é denotada por
¬ p
O valor verdade de ¬ p depende do valor verdade de p como se segue:
Definição 4.3: Se p é verdadeira, então ¬ p é falsa; e se p é falsa, então ¬ p é verdadeira.
O valor verdade de ¬ p pode ser definido equivalentemente pela tabela da Fig. 4-1(c). Assim, o valor verdade 
da negação de p é sempre o oposto do valor verdade de p.
Exemplo 4.3 Considere as seis sentenças a seguir:
(a1) Gelo flutua na água. (a2) É falso que gelo flutua na água. (a3) Gelo não flutua na água.
(b1) 2 + 2 = 5 (b2) É falso que 2 + 2 = 5. (b3) 2 + 2 �= 5
Então, tanto (a2) quanto (a3) são a negação de (a1); e tanto (b2) quanto (b3) são a negação de (b1). Como (a1) é 
verdadeira, (a2) e (a3) são falsas; e como (b1) é falsa, (b2) e (b3) são verdadeiras.
Observação: A notação lógica para os conectivos “e”, “ou” e “não” não é completamente padronizada. Por exem-
plo, alguns textos usam:
 
ou
ou 
4.4 PROPOSIÇÕES E TABELAS VERDADE
Seja P( p, q, . . .) uma expressão construída a partir de variáveis lógicas p, q, . . ., que assumem o valor VERDA-
DEIRO (V) OU FALSO (F), e a partir dos conectivos lógicos ∧, ∨ e ¬ (bem como outros discutidos adiante). Tal 
expressão é chamada de proposição.
A principal propriedade de uma proposição P( p, q, . . .) é que seu valor verdade depende exclusivamente dos 
valores verdade de suas variáveis, ou seja, o valor verdade de uma proposição é determinado, uma vez que o valor 
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
MATEMÁTICA DISCRETA72
verdade de cada uma de suas variáveis seja conhecido. Uma maneira concisa e simples para mostrar essa relação é 
por meio de uma tabela verdade. Descrevemos abaixo um modo de obter tal tabela verdade.
Considere, por exemplo, a proposição ¬(p ∧ ¬q). A Fig. 4-2(a) indica como a tabela verdade de ¬(p ∧ ¬q) é 
construída. Observe que as primeiras colunas da tabela são para as variáveis p, q, . . e que há linhas suficientes para 
permitir todas as possíveis combinações de V e F para essas variáveis. (Para duas variáveis, como acima, quatro 
linhas são necessárias; para três variáveis, oito linhas são necessárias; e, no caso geral, para n variáveis, 2n linhas 
são necessárias.) Existe, assim, uma coluna para cada estágio “elementar” da construção da proposição, sendo que 
o valor verdade em cada passo é determinado a partir dos estágios anteriores, pela definição dos conectivos 
∧, ∨ e ¬. Finalmente, obtemos o valor verdade da proposição, o qual aparece na última coluna.
A tabela verdade finalizada da proposição ¬(p ∧ ¬q) é mostrada na Fig. 4-2(b). Ela consiste precisamente nas 
colunas da Fig. 4-2(a) que aparecem sob as variáveis e sob a proposição; as outras colunas foram meramente usa-
das na construção da tabela verdade.
Figura 4-2
Observação: Para evitar um número excessivo de parênteses, às vezes adotamos uma ordem de precedência para 
os conectivos lógicos. Especificamente,
¬ precede ∧, o qual tem precedência sobre ∨
Por exemplo, ¬ p ∧ q significa (¬ p) ∧ q e não ¬(p ∧ q).
Método alternativo para construir uma tabela verdade
Outra maneira para construir a tabela verdade para ¬(p ∧ ¬q) é a seguinte:
(a) Primeiro, construímos a tabela verdade mostrada na Fig. 4-3. Ou seja, primeiro listamos todas as variáveis e as 
combinações de seus valores verdade. Há também uma linha final rotulada “passo”. Em seguida, a proposição 
é escrita na linha do topo e à direita de suas variáveis, com espaço suficiente de modo a existir uma coluna sob 
cada variável e sob cada operação lógica na proposição. Por último, (Passo 1), os valores verdade das variáveis 
são colocados na tabela sob as variáveis na proposição.
(b) Agora valores verdade adicionais são colocados na tabela verdade, coluna por coluna, sob cada operação lógi-
ca, como mostrado na Fig. 4-4. Também indicamos o passo no qual cada coluna de valores verdade é colocado 
na tabela.
A tabela verdade da proposição, portanto, consiste nas colunas originais sob as variáveis e do último passo, ou 
seja, a última coluna é colocada dentro da tabela.
Passo
Figura 4-3
Laiane
Laiane
Laiane
Laiane
basicamente foca em todos os elementos, inclusive os sinais v, ∧  e ¬.
CAPÍTULO 4 • LÓGICA E CÁLCULO PROPOSICIONAL 73
Passo Passo Passo
Figura 4-4
4.5 TAUTOLOGIAS E CONTRADIÇÕES
Algumas proposições P( p, q, . . .) contêm apenas V na última coluna de suas tabelas verdade ou, em outras pala-
vras, são verdadeiras para quaisquer valores verdade de suas variáveis. Tais proposições são chamadas de tautolo-
gias. Analogamente, uma proposição P( p, q, . . .) é dita uma contradição se tiver apenas F na última coluna de sua 
tabela verdade ou, em outras palavras, se for falsa para quaisquer valores verdade de suas variáveis. Por exemplo, 
a proposição “p ou não p ”, isto é, p ∨ ¬ p, é uma tautologia, e a proposição “p e não p”, isto é, p ∧ ¬ p, é uma 
contradição. Isso é verificado, examinando suas tabelas verdade na Fig. 4-5. (As tabelas verdade têm somente duas 
linhas, uma vez que cada proposição conta apenas com uma variável p.)
Figura 4-5
Observe que a negação de uma tautologia é uma contradição, pois é sempre falsa. E a negação de uma contradição 
é uma tautologia, uma vez que é sempre verdadeira.
Agora seja P( p, q, . . .) uma tautologia, e sejam P1( p, q, . . .), P2( p, q, . . .), . . . proposições quaisquer. Como 
P( p, q, . . .) não depende dos valores verdade em particular de suas variáveis p, q, . . ., podemos substituir P1 por p, 
P2 por q, . . . na tautologia P( p, q, . . .) e ainda teremos uma tautologia. Em outros termos:
Teorema 4.1 (Princípio de Substituição):Se P( p, q, . . .) é uma tautologia, então P( P1, P2, . . .) é uma tautologia 
para quaisquer proposições P1, P2, . . ..
4.6 EQUIVALÊNCIA LÓGICA
Duas proposições P(p, q, . . .) e Q(p, q, . . .) são logicamente equivalentes ou, simplesmente, equivalentes ou 
iguais, e se escreve
P(p, q, . . .) ≡ Q(p, q, . . .)
se tiverem tabelas verdade idênticas. Considere, por exemplo, as tabelas verdade de ¬(p ∧ q) e ¬p ∨ ¬q que apa-
recem na Fig. 4-6. Observe que ambas as tabelas verdade são a mesma, isto é, as duas proposições são falsas no 
primeiro caso e verdadeiras nos outros três casos. Consequentemente, podemos escrever
¬(p ∧ q) ≡ ¬p ∨ ¬q
Em outras palavras, as proposições são logicamente equivalentes.
Observação: Sejam p a sentença “Rosas são vermelhas” e q a sentença “Violetas são azuis”. Seja S a declaração:
“Não é verdade que rosas são vermelhas e violetas são azuis.”
Então S pode ser escrita na forma ¬(p ∧ q). Contudo, como observado acima, ¬(p ∧ q) ≡ ¬p ∨ ¬q. Consequente-
mente, S tem o mesmo significado da declaração:
“Rosas não são vermelhas ou violetas não são azuis.”
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
MATEMÁTICA DISCRETA74
Figura 4-6
4.7 ÁLGEBRA DE PROPOSIÇÕES
Proposições satisfazem várias leis que são listadas na Tabela 4-1. (Nessa tabela, V e F são restritos aos valores 
verdade “Verdadeiro” e “Falso”, respectivamente.) Estabelecemos esse resultado formalmente.
Teorema 4.2: Proposições satisfazem as leis da Tabela 4-1.
(Observe a semelhança entre a Tabela 4-1 e a Tabela 1-1 sobre conjuntos.)
Tabela 4-1 Leis da álgebra de proposições
Idempotência (1a) p ∨ p ≡ p (1b) p ∧ p ≡ p
Associatividade (2a) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (2b) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Comutatividade (3a) p ∨ q ≡ q ∨ p (3b) p ∧ q ≡ q ∧ p
Distributividade (4a) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (4b) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Identidade
(5a) p ∨ F ≡ p (5b) p ∧ V ≡ p
(6a) p ∨ V ≡ V (6b) p ∧ F ≡ F
Involução (7) ¬¬p ≡ p
Complementaridade
(8a) p ∨ ¬p ≡ V (8b) p ∧ ¬p ≡ V
(9a) ¬V ≡ F (9b) ¬F ≡ V
Leis de DeMorgan (10a) ¬( p ∨ q) ≡ ¬p ∧¬q (10b) ¬( p ∧ q) ≡ ¬p ∨¬q
4.8 SENTENÇAS CONDICIONAIS E BICONDICIONAIS
Muitas sentenças, especialmente em matemática, são da forma “Se p então q”. Tais sentenças são chamadas de 
condicionais e são denotadas por
p → q
A condicional p → q é frequentemente lida como “p implica q” ou “p somente se q”.
Outra sentença comum é da forma “p se, e somente se, q”. Tais sentenças são conhecidas como bicondicionais 
e são denotadas por
p ↔ q
Os valores verdade de p → q e p ↔ q são definidos pelas tabelas na Fig. 4-7(a) e (b). Note que:
(a) A condicional p → q é falsa apenas quando a primeira parte p é verdadeira e a segunda parte q é falsa. Logo, 
quando p é falsa, a condicional p → q é verdadeira, independentemente do valor verdade de q.
(b) A bicondicional p ↔ q é verdadeira sempre que p e q têm os mesmos valores verdade e falsa nos demais casos.
Laiane
Laiane
Laiane
Laiane
CAPÍTULO 4 • LÓGICA E CÁLCULO PROPOSICIONAL 75
A tabela verdade de ¬p ∧ q aparece na Fig. 4-7(c). Observe que a tabela verdade de ¬p ∨ q e p → q são idên-
ticas, ou seja, são ambas falsas apenas no segundo caso. Consequentemente, p → q é logicamente equivalente 
a ¬p ∨ q; ou seja,
p → q ≡ ¬p ∨ q
Em outras palavras, a sentença condicional “Se p então q” é logicamente equivalente à sentença “Não p ou q”, 
a qual envolve apenas os conectivos ∨ e ¬ e, assim, já faz parte de nossa linguagem. Podemos considerar p → q 
como uma abreviação para uma sentença recorrente.
Figura 4-7
4.9 ARGUMENTOS
Um argumento (ou inferência) é uma afirmação na qual um dado conjunto de proposições P1, P2, . . . , Pn, chama-
das de premissas, implica (tem como consequência) outra proposição Q, chamada de conclusão. Tal argumento é 
denotado por
P1, P2, . . . , Pn � Q
A noção de “argumento lógico” ou “argumento válido” é formalizada como se segue:
Definição 4.4: Um argumento P1, P2, . . . , Pn � Q é dito válido se Q é verdadeira se todas as premissas P1, P2, . . ., 
Pn são verdadeiras.
Um argumento que não é válido é chamado de falácia.
Exemplo 4.4
(a) O seguinte argumento é válido:
p, p → q � q (Modus Ponens)
A demonstração dessa regra segue da tabela verdade da Fig. 4-7(a). Especificamente, p e p → q são simulta-
neamente verdadeiras apenas no Caso (linha) 1 e, nesse caso, q é verdadeira.
(b) O argumento a seguir é uma falácia:
p → q, q � p
p → q e q são ambas verdadeiras no Caso (linha) 3 da tabela verdade da Fig. 4-7(a), mas, nesse caso, p é falsa.
Agora, as proposições P1, P2, . . . , Pn são simultaneamente verdadeiras se, e somente se, a proposição 
P1 ∧ P2 ∧ . . . Pn é verdadeira. Assim, o argumento P1, P2, . . . , Pn � Q é válido se, e somente se, Q é verdadeira 
sempre que P1 ∧ P2 ∧ . . . ∧ Pn for verdadeira ou, equivalentemente, se a proposição (P1 ∧ P2 ∧ . . . ∧ Pn) → Q 
for uma tautologia. Estabelecemos esse resultado formalmente.
Teorema 4.3: O argumento P1, P2, . . . , Pn � Q é válido se, e somente se, a proposição (P1 ∧ P2 . . . ∧ Pn) → Q é 
uma tautologia.
Aplicamos esse teorema no exemplo a seguir.
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
MATEMÁTICA DISCRETA76
Exemplo 4.5 Um princípio fundamental de raciocínio lógico diz:
“Se p implica q e q implica r, então p implica r”
p
V
V
V
V
F
F
F
F
q
V
V
F
F
V
V
F
F
r
V
F
V
F
V
F
V
F
V
V
V
V
F
F
F
F
1
V
V
F
F
V
V
V
V
2
V
V
F
F
V
V
F
F
1
V
F
F
F
V
F
V
V
3
V
V
F
F
V
V
F
F
1
V
F
V
V
V
F
V
V
2
V
F
V
F
V
F
V
F
1
V
V
V
V
V
V
V
V
4
V
V
V
V
F
F
F
F
1
V
F
V
F
V
V
V
V
2
V
F
V
F
V
F
V
F
1
�( p → q) ∧ (q → r)� → ( p → r)
Passo
Figura 4-8
Ou seja, o argumento a seguir é válido:
p → q, q → r � p → r (Lei do Silogismo)
Esse fato é verificado pela tabela verdade na Fig. 4-8, a qual mostra que a seguinte proposição é uma tautologia:
[(p → q) ∧ (q → r)] → (p → r)
De forma equivalente, o argumento é válido, uma vez que as premissas p → q e q → r são simultaneamente verda-
deiras apenas nos Casos (linhas) 1, 5, 7 e 8 e, nesses casos, a conclusão também é verdadeira. (Observe que a tabe-
la verdade demandou 23 = 8 linhas, pois há três variáveis p, q e r.)
Agora aplicamos a teoria acima sobre argumentos envolvendo sentenças específicas. Enfatizamos que a vali-
dade de um argumento não depende dos valores verdade nem do conteúdo das sentenças que surgem no argumento, 
mas da forma particular da inferência. Isso é ilustrado no exemplo a seguir.
Exemplo 4.6 Considere o seguinte argumento:
S1: Se um homem é solteiro, ele é infeliz.
S2: Se um homem é infeliz, ele morre cedo.
S: Solteiros morrem cedo.
Aqui a sentença S abaixo da linha denota a conclusão do argumento, e as sentenças S1 e S2 acima da linha corres-
pondem às premissas. Afirmamos que o argumento S1, S2, � S é válido, pois ele é da forma
p → q, q → r � p → r
onde p é “Ele é solteiro”, q é “Ele é infeliz” e r é “Ele morre cedo”; e pelo Exemplo 4.5 essa inferência (Lei do 
Silogismo) é válida.
4.10 FUNÇÕES PROPOSICIONAIS, QUANTIFICADORES
Seja A um dado conjunto. Uma função proposicional (ou sentença aberta ou condição) definida sobre A é uma 
expressão
p(x)
que tem a propriedade de que p(a) é verdadeira ou falsa para cada a ∈ A. Ou seja, p(x) se torna uma sentença (com 
um valor verdade) sempre que a variável x é substituída por qualquer elemento a ∈ A. O conjunto A é chamado de 
Laiane
Laiane
Laiane
Laiane
Laiane
CAPÍTULO 4 • LÓGICA E CÁLCULO PROPOSICIONAL 77
domínio de p(x), e o conjunto Tp de todos os elementos de A para os quais p(a) é verdadeira é chamado de conjun-
to verdade de p(x). Em outras palavras,
Tp = {x | x ∈ A, p(x) é verdadeira} ou Tp = {x | p(x)}
Frequentemente, quando A é algum conjunto de números, a condição p(x) tem a forma de uma equação ou desi-
gualdade envolvendo a variável x.
Exemplo 4.7 Encontre o conjuntoverdade para cada função proposicional p(x) definida sobre o conjunto N dos 
inteiros positivos.
(a) Seja p(x) a fórmula “x + 2 > 7”. Seu conjunto verdade é {6, 7, 8, . . .}, consistindo de todos os inteiros maiores 
do que 5.
(b) Seja p(x) a fórmula “x + 5 1”. Seu conjunto verdade é N. Ou seja, p(x) é verdadeira para todo elemento de N.
Observação: O exemplo acima mostra que se p(x) é uma função proposicional definida sobre um conjunto A, 
então p(x) poderia ser verdadeira para todo x ∈ A, para algum (ou alguns) x ∈ A, ou para nenhum x ∈ A. As duas 
subseções a seguir discutem quantificadores relacionados com tais funções proposicionais.
Quantificador universal
Seja p(x) uma função proposicional definida sobre um conjunto A. Considere a expressão
 (∀x ∈ A)p(x) ou ∀x p(x) (4.1)
a qual se lê “Para todo x em A, p(x) é uma sentença verdadeira” ou, simplesmente, “Para todo x, p(x)”. O símbolo
∀
que se lê “para todo” é chamado de quantificador universal. A sentença (4.1) é equivalente à afirmação
 Tp = {x | x ∈ A, p(x)} = A (4.2)
ou seja, à afirmação de que o conjunto verdade de p(x) é o conjunto todo A.
A expressão p(x) em si é uma sentença aberta ou condição e, portanto, não tem valor verdade. Contudo, ∀x 
p(x), isto é, p(x) precedida pelo quantificador ∀, tem um valor verdade que segue da equivalência entre (4.1) e (4.2). 
Especificamente:
Q1: Se {x | x ∈ A, p(x)} = A, então ∀x p(x) é verdadeira; caso contrário, ∀x p(x) é falsa.
Exemplo 4.8
(a) A proposição (∀n ∈ N)(n + 4 > 3) é verdadeira, pois {n | n + 4 > 3} = {1, 2, 3, . . .} = N.
(b) A proposição (∀n ∈ N)(n + 2 > 8) é falsa, pois {n | n + 2 > 8} = {7, 8, . . .} �= N.
(c) O símbolo ∀ pode ser usado para definir a interseção de uma coleção indexada {Ai | i ∈ I} de conjuntos Ai 
como se segue:
∩(Ai | i ∈ I) = {x | ∀i ∈ I, x ∈ Ai}
Quantificador existencial
Seja p(x) uma função proposicional definida sobre um conjunto A. Considere a expressão
 (∃x ∈ A)p(x) ou ∃x, p(x) (4.3)
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
MATEMÁTICA DISCRETA78
que se lê “Existe um x em A tal que p(x) é uma sentença verdadeira” ou, simplesmente, “Para algum x, p(x)”. O 
símbolo
∃
o qual se lê “existe” ou “para algum” ou “para pelo menos um” é chamado de quantificador existencial. A sentença 
(4.3) é equivalente à sentença
 Tp = {x | x ∈ A, p(x)} �= ∅ (4.4)
isto é, à afirmação de que o conjunto verdade de p(x) não é vazio. Consequentemente, ∃x p(x), ou seja, p(x) 
precedida pelo quantificador ∃, tem um valor verdade. Especificamente:
Q2: Se {x | p(x)} �= ∅, então ∃x p(x) é verdadeira; caso contrário, ∃x p(x) é falsa.
Exemplo 4.9
(a) A proposição (∃n ∈ N)(n + 4 8”
“Existe um inteiro positivo n tal que n + 2 �> 8”
(b) As sentenças a seguir também são negações uma da outra:
“Existe uma pessoa (viva) com 150 anos de idade”
“Toda pessoa viva não tem 150 anos de idade”
Observação: A expressão ¬p(x) tem o significado óbvio:
“A sentença ¬p(a) é verdadeira quando p(a) é falsa, e vice-versa”
Anteriormente, ¬ foi usado como uma operação sobre sentenças; aqui ¬ é usado como uma operação sobre fun-
ções proposicionais. Analogamente, p(x) ∧ q(x), que se lê “p(x) e q(x)”, é definida por:
“A sentença p(a) ∧ q(a) é verdadeira quando p(a) e q(a) são verdadeiras”
Analogamente, p(x) ∨ q(x), que se lê “p(x) e q(x)”, é definida por:
“A sentença p(a) ∨ q(a) é verdadeira quando p(a) ou q(a) é verdadeira”
Assim, em termos de conjuntos verdade:
 (i) ¬p(x) é o complemento de p(x).
 (ii) p(x) ∧ q(x) é a interseção entre p(x) e q(x).
 (iii) p(x) ∨ q(x) é a união de p(x) com q(x).
Podemos também mostrar que as leis para proposições valem igualmente para funções proposicionais. Por 
exemplo, temos as Leis de DeMorgan:
¬(p(x) ∧ q(x)) ≡ ¬p(x) ∨ ¬q(x) e ¬(p(x) ∨ q(x)) ≡ ¬p(x) ∧ ¬q(x)
Contraexemplo
O Teorema 4.6 nos diz que para mostrar que uma sentença ∀x, p(x) é falsa, é equivalente mostrar que ∃ x¬p(x) é 
verdadeira ou, em outros termos, que existe um elemento x0 com a propriedade de que p(x0) é falsa. Tal elemento 
x0 é chamado de contraexemplo da afirmação ∀x, p(x).
Exemplo 4.11
(a) Considere a sentença ∀x ∈ R, |x| �= 0. Ela é falsa, pois 0 é um contraexemplo, ou seja, |0| �= 0 não é verdadeira.
(b) Considere a sentença ∀x ∈ R, x2 ≥ x. Ela não é verdadeira, uma vez que, por exemplo, é um contraexemplo. 
Especificamente, não é verdadeira, isto é, 
(c) Considere a sentença ∀x ∈ N, x2 ≥ x. Ela é verdadeira, onde N é o conjunto de inteiros positivos. Em outras 
palavras, não existe inteiro positivo n para o qual n2com mais de uma variável podem ser negadas aplicando sucessivamente os Teoremas 4.5 
e 4.6. Assim, cada ∀ é mudado para ∃ e cada ∃ é mudado para ∀, à medida que o símbolo de negação ¬ passa pela 
sentença, da esquerda para a direita. Por exemplo,
 ¬[∀x∃y∃z, p(x, y, z)] ≡ ∃x¬[∃y∃z, p(x, y, z)] ≡ ¬∃z∀y[∃z, p(x, y, z) 
 ≡ ∃x∀y∀z, ¬p(x, y, z) 
Naturalmente, não colocamos todos os passos quando negamos tais sentenças quantificadas.
Exemplo 4.13
(a) Considere a sentença quantificada:
“Todo estudante cursa pelo menos uma disciplina na qual o docente é um professor assistente.”
Sua negação é a sentença:
“Existe um estudante tal que, em toda disciplina cursada, o docente não é um professor assistente.”
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
Laiane
CAPÍTULO 4 • LÓGICA E CÁLCULO PROPOSICIONAL 81
(b) A definição formal de que L é o limite de uma sequência a1, a2, . . . segue abaixo:
∀ ∈ > 0, ∃ n0 ∈ N, ∀n > n0, temos | an − L| 0, ∀n0 ∈ N, ∃n > n0 tal que | an − L| ≥ ∈
Problemas Resolvidos
Proposições e tabelas verdade
 4.1 Seja p a sentença “Está frio” e seja q “Está chovendo”. Dê uma sentença verbal que descreva cada uma das 
sentenças a seguir: (a) ¬p; (b) p ∧ q; (c) p ∨ q; (d) q ∨ ¬p.
Em cada caso, traduza ∧, ∨ e ∼ como “e”, “ou” e “É falso que” ou “não”, respectivamente, e então simplifique a 
sentença em português.
(a) Não está frio. (c) Está frio ou está chovendo.
(b) Está frio e chovendo. (d) Está chovendo ou não está frio.
 4.2 Encontre a tabela verdade de ¬p ∧ q.
Construa a tabela verdade de ¬p ∧ q como na Fig. 4-9(a).
Figura 4-9
 4.3 Verifique que a proposição p ∨ ¬(p ∧ q) é uma tautologia.
Construa a tabela verdade de p ∨ ¬(p ∧ q) como mostrado na Fig. 4-9(b). Como o valor verdade de p ∨ ¬(p ∧ q) 
é V para todos os valores de p e q, a proposição é uma tautologia.
 4.4 Mostre que as proposições ¬(p ∧ q) e ¬p ∨ ¬q são logicamente equivalentes.
Construa as tabelas verdade para ¬(p ∧ q) e ¬p ∨ ¬q, como na Fig. 4-10. Como as tabelas verdade são as mesmas 
(ambas as proposições são falsas no primeiro caso e verdadeiras nos outros três casos), as proposições ¬(p ∧ q) e ¬p ∨ 
¬q são logicamente equivalentes e podemos escrever
¬(p ∧ q) ≡ ¬p ∨ ¬q
Figura 4-10
Laiane
Encerra aqui o trecho do livro disponibilizado para 
esta Unidade de Aprendizagem. Na Biblioteca Virtual 
da Instituição, você encontra a obra na íntegra. 
Dica do professor
Conhecer e aplicar os conectivos lógicos, assim como a construção da tabela verdade, é muito 
importante para o desenvolvimento de algoritmos, a fim de que eles possam executar de forma 
correta as operações e expressões definidas pelo programador.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
 
https://fast.player.liquidplatform.com/pApiv2/embed/cee29914fad5b594d8f5918df1e801fd/8bad992d3a99ea7220e8b3370a7b5930
Exercícios
1) A proposição é submetida a uma avaliação e tem por objetivo modelar o raciocínio humano. 
As sentenças a serem avaliadas podem ser consideradas como exclamativas, interrogativas 
ou imperativas, mas a lógica proposicional utiliza somente as frases ou sentenças 
declarativas, denominadas de proposição, que podem afirmar ou negar alguma coisa; a 
proposição possui um valor de verdade, que pode assumir como verdadeiro ou falso. As 
proposições podem ser simples ou compostas, necessitando, nas compostas, dos conectivos 
lógicos (e, ou, não) para serem avaliadas. Considerando os conceitos apresentados acima, 
assinale a alternativa que contempla uma proposição.
A) Vá trabalhar!
B) Joana é professora de nível superior.
C) 16 + 17.
D) Qual a sua cor preferida?
E) Compre aquele chapéu.
2) A construção da tabela verdade é muito importante, pois permite representar e avaliar as 
proposições com a aplicação dos seus conectivos lógicos, verificando se a proposição é 
verdadeira ou é falsa.
Considere para o problema as letras w, x, f e g que representam as proposições, e os 
símbolos ~(não), ^(e) e v(ou) como operadores lógicos. Avalie as alternativas apresentadas a 
seguir.
I. Dado falso para a proposição w e x, pode-se dizer que a proposição (~ w) v ((~ x) v w) 
também é F - falsa. 
II. Dado verdadeiro para a proposição f e g, pode-se dizer que a proposição (~f) ^ (~ g) ^ f é F 
- falsa. 
III. Dado verdadeiro para a proposição w e falso para a proposição g e x, pode-se dizer que a 
proposição ( w v x ) ^ ( ( g v w ) ^ (~ x) ) é F - falsa.
Assinale apenas a alternativa correta.
A) I e II.
Laiane
Laiane
É uma sentença de exclamação.
Laiane
É uma sentença declarativa e completa, pode ser avaliada como verdadeira ou falsa.
Laiane
Não é uma proposição, pois não tem como analisar se é verdadeiro ou falso, não está completa.
Laiane
É uma sentença interrogativa.
Laiane
É uma sentença imperativa.
Laiane
A alternativa I está incorreta. Pela tabela do "ou", temos: (~ w) v ((~ x) v w) (~ F) v ((~F) v F) V v (V v F) V v V V ( resultado da proposição é VERDADEIRO)
B) II.
C) I, II e III.
D) II e III.
E) I e III.
3) A cola não autorizada é um problema existente em muitas salas de aula, e a pessoa mais 
prejudicada nesse processo é o aluno. Com a cola, os dados para a análise do professor são 
distorcidos, pois ele verifica, com base nos dados da avaliação, onde estão os pontos ainda não 
desenvolvidos pela turma, para, assim, preparar estratégias que desenvolvam as habilidades que 
ainda apresentaram dificuldades.
Considere o problema da cola representado nas sentenças abaixo:
a) Colar é proibido, mas muitos alunos colam. 
b) Colar não é proibido e faz bem ao aprendizado.
As sentenças acima podem ser representadas através de proposições e conectivos lógicos. 
Considere também que m, x e n representem as proposições listadas na tabela a seguir:
Com base nas proposições acima, os conectivos estudados e considerando a notação introduzida 
na Unidade de Aprendizagem, analise e julgue as alternativas apresentadas abaixo:
I - A sentença aa pode ser corretamente representada por m ^ (~ n). 
II - A sentença b pode ser corretamente representada por (~ m) ^ (~ x). 
III - A sentença a pode ser corretamente representada por m ^ n. 
IV - A sentença b pode ser corretamente representada por (~ m) v ( x). 
Assinale a alternativa correta.
A) I e II.
B) I e III.
C) I, II e III.
D) II e III.
Laiane
Laiane
Laiane
Laiane
Pela tabela do "e", temos: (~f) ^ (~ g) ^ f (~V) ^ (~V ) ^ V F ^ F ^ V F (resultado da proposição é FALSO)
Laiane
A alternativa III está incorreta. Pela tabela do "ou" e do "e", temos: ( w v x ) ^ ( ( g v w ) ^ (~ x) ) (V v F ) ^ ( ( F v V) ^ ( ~ F ) ) V ^ ( V ^ V ) V ^ V V (resultado da proposição é VERDADEIRO)
Laiane
Na alternativa I, a representação correta seria m ^ n utilizando o conectivo “e”. A alternativa II está correta. A negação da proposição x que representa “Colar não faz bem ao aprendizado” será “Colar faz bem ao aprendizado”. A alternativa III está correta, é uma proposição composta com o conectivo “e”. Na alternativa IV, a representação correta seria (~m) ^ (~ x), utilizando o conectivo “e” e a negação da proposição x.
E) III e IV.
4) A tabela verdade é uma forma de representarmos e avaliarmos expressões lógicas, as quais 
são utilizadas na programação de algoritmos para avaliar sentenças. Conforme o resultado, 
poderá ser tomada uma decisão, e, assim, um comando ou um conjunto de comandos 
diferentes podem ser executados em situações nas quais a expressão é verdadeira ou falsa. 
Para a avaliação das expressões, deve-se observar os parênteses apresentados na expressão, 
priorizando a sua resolução.
Considerando a tabela verdade dos conectivos e, ou e não, resolva as seguintes expressões 
lógicas:
I – não V ou (V e (V ou F)) 
II – ((V e V) e não V) ou (não V ou não F) 
III – V e F ou não F
Assinale a alternativa que representa corretamente o resultado das expressões lógicas acima 
apresentadas.
A) V, V, V.
B) F, F, F.
C) V,F, F.
D) V, V, F.
E) F, F, V.
Para a construção da tabela verdade, devemos calcular o número de linhas necessárias para a 
construção da tabela em questão. O número de linhas é calculado pela representação e 2 na base n 
(2n), em que n representa o número de preposições do problema.
A proposição a ser avaliada será ( p ^ q ) v (~r ); assim, teremos três preposições: p, q e r. Aplicando 
2n, teremos 23, que é representado por 2 x 2 x 2 = 8, ou seja, 8 linhas são necessárias para a 
construção da tabela verdade para a proposição ( p ^ q ) v (~r ).
Para facilitar a resolução da expressão, a tabela construída abaixo normalmente é necessária. 
Considerando os conectivos lógicos usuais ~, ^ e v e as proposições lógicas p, q e r, analise e 
preencha a tabela apresentada para 23 proposições, nas quais a coluna correspondente à 
proposição (p ^ q) v (~r ) conterá somente os valores V para Verdadeiro e F para Falso.
5) 
Laiane
Laiane
Todas as sentenças são verdadeiras.Sentença I:não V ou (V e (V ou F))F ou (V e V)F ou VVSentença II:((V e V) e não V) ou (não V ou não F)(V e F) ou (F ou V)F ou VVSentença III:V e F ou não FV e F ou VF ou VV
Para auxiliar e facilitar a avaliação da expressão, quebre em partes; primeiro, deverão ser 
resolvidas as expressões entre os parênteses mais internos. A ordem para o problema proposto 
será:
Análise 1 – resolva (p ^q) 
Análise 2 – resolva (~r) 
Análise 3 – resolva Resultado Análise 1 V Resultado da Análise 2. Assim, teremos o resultado da 
expressão (p ^ q) v (~r) que será preenchido na tabela a seguir.
Considerando a valoração de cima para baixo e na sequência, defina a tabela verdade apresentada 
acima para a proposição (p ^ q) v (~r) e assinale a alternativa correta de valoração.
A) V-V-F-V-F-V-F-V.
B) V-V-V-V-V-V-V-V.
C) F-F-F-F-F-F-F-V.
D) F-F-V-F-V-F-V-F.
E) F-F-F-V-V-F-V-F.
Laiane
Na prática
A lógica é muito aplicada na arquitetura de computadores, área em que são projetados circuitos 
eletrônicos na construção de programas resolvendo problemas e também aplicando a inteligência 
artificial. Utilizamos a lógica no nosso cotidiano, tomamos decisões, fizemos análises e inferimos se 
é verdadeiro ou falso. Utilizamos argumentos para defender o nosso ponto de vista.
Por exemplo, se ouvimos a mãe de Pedro, seu amigo, dizer que "Se Pedro for aprovado no 
vestibular, ele terá um carro". E não seria nada estranho se ouvirmos alguém dizer que Pedro foi 
aprovado no vestibular, já que se sabe que ele já possui o carro. Essa é a conclusão que a maioria 
das pessoas chegaria, pois, se Pedro tem um carro, então Pedro teve aprovação no vestibular.
VEREMOS UM EXEMPLO PRÁTICO PARA PEDRO APÓS INGRESSAR NA UNIVERSIDADE!
Quando Pedro ingressa na universidade, toma conhecimento das regras de aprovação nas 
disciplinas. Por exemplo, para aprovação, ele deverá ter média acima ou igual a 7 e frequência 
maior ou igual a 75%; caso contrário, estará reprovado. Se Pedro frequentar todas as aulas, mas for 
mal na avaliação e sua nota ficar abaixo de 7, ele poderá ter 100% de frequência e estará reprovado 
mesmo assim. Se ele tirar nota 10 nas avaliações, mas não comparecer às aulas, estará reprovado, 
pois temos o operador “e”, que deve ter as duas proposições para fazer a aprovação (p: media maior 
ou igual a 7; q: frequência maior ou igual a 75%) verdadeiras para que ele seja verdadeiro 
(aprovado). Assim como essa, temos milhares de situações em que avaliamos expressões e temos o 
resultado como verdadeiro ou falso.
Criando a tabela verdade para Pedro, tem-se:
22 = 4 linhas na tabela verdade
em que:
p: média de Pedro deve ser maior ou igual a 7
q: frequência de Pedro deve ser maior ou igual a 75%
 
Analisando a tabela verdade, percebe-se que a proposição somente será verdadeira (APROVADO) 
quando a proposição q e a proposição p forem verdadeiras. Se uma for falsa, ou as duas, ele será 
falso, OU SEJA, será reprovado.
V e V = V
V e F = F
F e V = F
F e F = F
Assim, Pedro somente terá aprovação se tiver média maior ou igual a 7 e frequência maior ou igual 
a 75%.
JÁ IMAGINOU SE O CONECTIVO FOSSE “OU”, O QUE MUDARIA PARA PEDRO? 
EM QUAIS SITUAÇÕES PEDRO ESTARIA APROVADO OU REPROVADO?
Saiba +
Para ampliar o seu conhecimento a respeito desse assunto, veja abaixo as sugestões do professor:
Raciocínio lógico (proposição e tabela verdade) - lógica 
proposicional.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Raciocínio lógico (proposição e tabela verdade) - conectivos e, 
ou.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Raciocínio lógico (proposição e tabela verdade) - conectivos 
disjunção exclusiva e condicional.
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
Raciocínio lógico (proposição e tabela verdade) - negação de 
preposição e tabela verdade.
https://www.youtube.com/embed/GlVa3RA9tKI
https://www.youtube.com/embed/DwfCk1lguTQ
https://www.youtube.com/embed/rjr-RqFM3uc
Aponte a câmera para o código e acesse o link do conteúdo ou clique no código para acessar.
https://www.youtube.com/embed/6E9P-eVOVFA