Livro - Fundamentos de Matematica para a Informatica

Prévia do material em texto

FUNDAMENTOS DE MATEMÁTICA 
PARA INFORMÁTICA
Giulliana Martins de Souza
Te
cn
o
lo
g
ia
F
U
N
D
A
M
E
N
T
O
S
 D
E
 M
A
T
E
M
Á
T
IC
A
 
P
A
R
A
 I
N
F
O
R
M
Á
T
IC
A
G
iu
lli
an
a 
M
ar
tin
s 
d
e 
S
ou
za
Fundamentos de 
Matemática para 
Informática
Giulliana Martins de Souza
Curitiba
2021
Ficha Catalográfica elaborada pela Editora Fael.
S729f Souza, Giulliana Martins de
Fundamentos de matemática para informática / Giulliana Martins 
de Souza. – Curitiba: Fael, 2021.
190 p.: il.
ISBN 978-65-86557-39-8
1. Computação matemática I. Título
CDD 005.131
Direitos desta edição reservados à Fael.
É proibida a reprodução total ou parcial desta obra sem autorização expressa da Fael.
FAEL
Direção Acadêmica Francisco Carlos Sardo
Coordenação Editorial Angela Krainski Dallabona
Revisão Editora Coletânea
Projeto Gráfico Sandro Niemicz
Imagem da Capa Shutterstock.com/local_doctor
Arte-Final Evelyn Caroline Betim Araujo
Sumário
Carta ao Aluno | 7
1. Teoria de conjuntos | 9
2. Proposições lógicas e suas operações | 29
3. Tabelas verdade | 43
4. Tautologias, contradições, contingências 
e implicações lógicas | 55
5. Equivalências lógicas | 67
6. Argumentos: regras de inferência | 87
7. Sentenças abertas e operações | 105
8. Quantificadores  |  117
9. Álgebra de Boole e Mapa de Karnaugh | 131
10. Circuitos e Portas Lógicas | 147
Gabarito | 167
Referências | 187
Dedico este livro aos meus pais 
Cleonice e Rubens, que priorizaram 
meu estudo e educação; à Tia Helena 
(Colégio Pio X) que me ensinou a amar a 
matemática; ao professor Carlos Magno 
(PUC-PR), com suas aulas fascinantes 
de lógica matemática; e à Tia Neide (in 
memoriam), que me deu o melhor livro 
de matemática aplicada para iniciantes: O 
Homem que calculava, de Malba Tahan.
Prezado(a) aluno(a),
Muito se fala da dificuldade em aprender matemática, prin-
cipalmente pelas formas de ensino e traumas originados no pas-
sado. Mas a ciência da matemática utiliza métodos precisos e 
exatos para demonstrar e comprovar a veracidade dos fatos que 
apresentam uma relação ou um encadeamento lógico entre si.
Quando você estuda matemática, aprendendo suas aplica-
ções no mundo real, ela se torna muito mais útil e simples. Um 
grande exemplo vem da informática, cuja estrutura é formada 
pela matemática, em que a aplicação destes conceitos juntamente 
com outras áreas formou o que hoje chamamos de Tecnologia da 
Informação (TI).
Esta obra vai apresentar os conceitos, as soluções e a utili-
zação da lógica matemática na informática, de uma forma fácil, 
didática e sequencial, de forma a melhorar o aprendizado. Com 
essa base, você vai compreender a essência da lógica matemática 
e sua aplicação em várias áreas da TI.
Carta ao Aluno
1
Teoria de conjuntos
Teoria de conjuntos é a base introdutória para muitas áreas 
da matemática e da computação, como compiladores, progra-
mação, banco de dados, dentre outros. Segundo a Enciclopédia 
Britânica (S.d.), Georg Ferdinand Ludwig Philipp Cantor foi o 
matemático que estabeleceu a teoria de conjuntos. Nasceu em 3 
de março de 1845, em São Petersburgo, Rússia, e faleceu no dia 
6 de janeiro de 1918, em Halle, Alemanha. Sua tese de doutorado 
foi sobre teoria dos números e suas descobertas influenciaram o 
século XX.
Neste capítulo, vamos apresentar os conceitos de teoria de 
conjuntos, suas regras e leis. Tais conceitos são inicialmente 
apresentados nos ensinos fundamental e médio, sendo de suma 
importância para o aprendizado de lógica matemática.
Fundamentos de Matemática para Informática
– 10 –
Ao fim deste capítulo você será capaz de:
 2 definir conjuntos;
 2 relacionar conjuntos;
 2 utilizar operadores entre conjuntos;
 2 apresentar diagramas de conjuntos.
1.1 Conjuntos
Segundo Lipschutz (1991), conjunto é, intuitivamente, uma lista, 
coleção ou classe de objetos bem definidos.
Um conjunto é formado por elementos, e os itens que o formam podem 
ser representados por expressões ou condições, enumeração e combinação 
destas, segundo Ferreira (2001), Alencar Filho (1980) e Lewis (1991).
Exemplos de conjuntos:
 2 as letras do alfabeto
 2 as cores do arco-íris
 2 os rios brasileiros
 2 as cores da bandeira nacional
 2 os meses do ano
A representação de conjuntos é feita por:
 2 letras maiúsculas para os conjuntos, A, B, C, D, ... Z.
 2 letras minúsculas para os elementos. a, b, c, d, ... z.
Os elementos também podem ser representados por números, pala-
vras e expressões numéricas.
Exemplos:
A = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, y, w, o, p, q r, s, t, u, v, x, z };
B= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
C = {sábado, domingo};
– 11 –
Teoria de conjuntos
D = {x | x é ímpar};
E = {y | y é negativo};
K = {z | em que z é uma capital do Brasil}.
1.1.1 Relação de pertinência
A relação de pertinência configura a condição de objeto do conjunto, 
ou seja, se o elemento faz parte ou não de determinado conjunto. Utili-
zamos o símbolo E ou ∈ (pertence) se o elemento pertence ao conjunto, 
e o símbolo Ɇ ou ∉ (não pertence) para indicar que o elemento não per-
tence (não faz parte) do conjunto. Segundo Alencar Filho, essa notação 
é devida ao matemático italiano Giuseppe Peano (1858 - 1922) (FER-
REIRA, 2001).
Exemplos:
1 ∈ ao conjunto dos números positivos;
1 ∉ ao alfabeto;
A = {a, b, c, d, e}, 1 ∉ a A, b ∈ a A.
1.1.2 Notação
A representação de um conjunto é formada pela letra maiúscula 
representando o nome do conjunto, seguida do símbolo igual (=) e cha-
ves ({}) indicando o início e o fim, e tendo seus elementos enumerados e 
separados por vírgulas (,).
Exemplos:
Conjunto das vogais. A = {a, e, i, o, u};
Cores da bandeira do Brasil. B = {verde, amarelo, azul e branco};
Conjunto dos números naturais pares. C = {x E N | x é par}.
Um conjunto também pode ser formado por outros conjuntos, e a 
notação segue o mesmo padrão: D = { {a, b}, {x | x é um planeta}, {10, 20, 
..., 100}. Da mesma forma, um conjunto pode ser formado por conjuntos 
e elementos: F = {a, {k | k pertence a tabela periódica}, {9, 7, 5, 4, 0}}.
Fundamentos de Matemática para Informática
– 12 –
1.1.3 Conjunto unitário
O conjunto unitário é formado por um único elemento.
Exemplos:
E = {1}; composto por um único elemento cujo valor é 1;
F = {a}; composto somente pela letra A;
G = {x é inteiro | x2 – 6x + 9}. Só existe uma solução para essa equa-
ção, cujo valor é 3 e pode ter a notação G = {3}.
1.1.4 Conjunto vazio
Não tem nenhum elemento, representado pelo símbolo ø ou {}.
Exemplo:
G ={ø}; vazio, não contém nenhum elemento.
K = {};
L = {z | z2 < 0}.
1.1.5 Conjuntos finitos e infinitos
Um conjunto é finito quando apresenta um número limitado de ele-
mentos.
Exemplos:
H = {0, 1};
I = {todos os números pares entre 0 e 100};
M = {a, b, c, ..., z}, conjunto finito seguindo a sequência do alfabeto 
de a – z;
N = {x1, x2, ..., xn}, conjunto finito com n elementos;
O conjunto vazio {} é sempre finito.
Um conjunto é infinito quando possui uma quantidade ilimitada 
de elementos.
– 13 –
Teoria de conjuntos
Exemplos:
J = {todos os números pares reais};
K = {x E R | x é ímpar};
L = {0, 1, 2, ...};
P = {x1, x2, ...}.
1.1.6 Conjunto universo (U)
Todos os conjuntos fazem parte de um mesmo conjunto de dados 
chamado de U, e todos os elementos dos conjuntos existentes pertencem 
também a este conjunto universal.
1.2 Diagramas de Euler-Venn
Leonard Paul Euler (1707-1783), matemático e físico suíço, introdu-
ziu a representação gráfica das relações e operações entre conjuntos com 
os diagramas formados por curvas fechadas (círculos) que representam 
esses conjuntos. Os elementos que estão dentro do círculo pertencem ao 
conjunto, e os que estão fora, não. Estes diagramas foram posteriormente 
ampliados por John Venn (1834– 1923), matemático inglês, e atualmente 
são denominados Diagramas de Venn ou Diagramas de Euler-Venn (LIPS-
CHUTZ, 1991; SOUZA, 2002; VEEN, 1880). Os símbolos na Figura 1.1 
representam os conjuntos A eB. O retângulo representa o conjunto uni-
verso U. Os círculos dentro do retângulo representam os conjuntos que 
fazem parte do universo U.
Figura 1.1 – Diagrama de Euler-Venn
Fonte: elaborada pelo autor.
Fundamentos de Matemática para Informática
– 14 –
Utilizando os diagramas fica mais facilitada a visualização dos con-
juntos e suas relações.
1.3 Relações entre conjuntos 
e suas propriedades
Agora que você conhece as características e tipos de conjuntos, vamos 
ampliar o conhecimento sobre estes e suas relações, que são de: igualdade, 
subconjuntos, potência, disjuntos, universo e comparáveis, referenciados 
por Ferreira (2001), Alencar Filho (2003), Lewis (1918), Rangel (2005) e 
Souza (2002) e definidos a seguir.
1.3.1 Igualdade
Os conjuntos podem ser considerados iguais se tiverem os mesmos 
elementos entre si, e são representados pelo símbolo de igual (=), em que 
A = B, demonstrando que o conjunto A é exatamente igual ao conjunto B.
Dado o conjunto M = {x, y, z, k, w} e o conjunto N = {w, k, z, y, 
x}, então M = N, pois têm os mesmos elementos, independentemente da 
ordem em que os elementos aparecem nos conjuntos.
Exemplo: Temos os conjuntos O = {x | x2 -3x = -2}, P = {1, 2, 1, 2} e Q 
= {2, 1}. Podemos afirmar que O = P = Q, não importando se os conjuntos são 
representados de forma diferente ou com elementos repetidos. Ver Figura 1.2.
Figura 1.2 – Igualdade de conjuntos
O
1, 2
P
1, 2, 1, 2
Q
2, 1
Fonte: elaborada pelo autor.
Se os conjuntos não forem iguais, então a representação da negação 
da igualdade (desigualdade) dos conjuntos é O ≠ P. Neste caso, o conjunto 
O é diferente do conjunto P.
– 15 –
Teoria de conjuntos
Propriedades da igualdade de conjuntos:
P1) Reflexiva: A = A. Cada elemento é relacionado consigo 
mesmo.
P2) Simétrica: A = B e B = A. Cada elemento relacionado com 
um outro, o segundo é relacionado com o primeiro.
P3) Transitiva: A = B, B = C então A = C. Cada elemento rela-
cionado com um segundo, o segundo é relacionado com um 
terceiro, então o primeiro é relacionado com o terceiro.
1.3.2 Subconjuntos
A relação de subconjunto existe quando um conjunto T faz parte de outro 
conjunto Y. Neste caso, todos os elementos de T existem em Y. Esta relação é 
representada pelo símbolo está contido (⊂ ou ⊆). Observe o exemplo:
T = {a, e, i, o, u} e Y = {x | x está no alfabeto}. T ⊂ Y, então o con-
junto T está contido em Y. Ver Figura 1.3.
Figura 1.3 – Subconjuntos
Y Alfabeto
T
a e i o u
Fonte: elaborada pelo autor.
A representação dos conjuntos acima pode ser feita utilizando o sím-
bolo contém (⊃ ou ⊇). Desta forma, Y ⊇ T.
Existem formas de representação quando um conjunto não está con-
tido (⊄ ou ⊈) em outro, ou quando não contém outro conjunto (⊅, ⊉).
Exemplos:
 2 V = {a, b, c};
Fundamentos de Matemática para Informática
– 16 –
 2 X = {1, 2, 3, 4};
 2 V não está contido em X, V ⊄ X.
 2 X não contém V, X ⊅ V.
Propriedades da relação está contido (⊂):
A relação de inclusão de conjuntos segue as seguintes propriedades:
P1) Reflexiva: A ⊂ A. Um conjunto sempre está contido nele 
mesmo.
P2) Transitiva: A ⊂ B e B ⊂ C, então A ⊂ C. Se A está contido 
em B e B está contido em C, então A está contido em C.
P3) Antissimétrica: A ⊂ B, B ⊂ A, então A = B.
 Importante
Um conjunto vazio sempre está contido em qualquer conjunto.
Qualquer conjunto sempre está contido no conjunto universo (U).
1.3.3 Conjunto potência
Todos os conjuntos derivados de um conjunto-base são chamados de 
conjunto potência.
Segundo Lipschutz (1991), se um conjunto P é finito, e supondo que 
P tenha n elementos, então o conjunto potência de P terá 2n elementos. 
Desta forma, podemos dizer que um conjunto potência P é a classe dos 
subconjuntos de P, sendo representada por 2p.
Exemplos:
 2 P = {1, 2, 3}, neste caso 2p sendo 23 = 8;
 2 2p = { {1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3}, ø };
Representam subconjuntos de P.
 2 Q = {x, y}, 2q = { {x}, {y}, {x, y}, {ø} }.
 2 Representam subconjuntos de Q.
– 17 –
Teoria de conjuntos
1.3.4 Conjuntos disjuntos
São considerados disjuntos os conjuntos cujos elementos que per-
tencem a um conjunto A não existem em um conjunto B. Neste caso, não 
existem elementos em comum nos conjuntos.
Exemplos:
 2 Seja R o conjunto dos números inteiros negativos e S o conjunto 
dos números inteiros positivos, R é disjunto de S.
 2 T = {a, b, c} e V {1, 2, 3}; os conjuntos T e V são disjuntos.
 2 X = {1, 2, 3} e Y= {3, 4, 5}; X e Y não são disjuntos, pois têm 
o elemento 3 em comum.
1.3.5 Conjuntos comparáveis
Os conjuntos são considerados comparáveis quando A ⊂ B ou B ⊂ A. 
Um deve estar contido no outro.
Exemplos:
 2 K = {a, b} e L {a, 1, 2} não são comparáveis, por K não estar 
contido em L e vice-versa;
 2 M = {1, 2} e N = {1, 2, 3, 4, 5} são comparáveis, pois M está 
contido em N.
1.4 Operações fundamentais
União, interseção, diferença e complemento são operações entre con-
juntos que podem ser combinadas e gerar outros conjuntos, referenciados 
por Ferreira (2001), Alencar Filho (2003), Lewis (1918), Rangel (2005) e 
Souza (2002) e definidos a seguir:
1.4.1 União (U)
É formado pela junção de conjuntos presentes nesta operação. Todos os 
elementos de um conjunto se unem a todos os elementos de outro conjunto.
Fundamentos de Matemática para Informática
– 18 –
Exemplos:
 2 X = {a, b, c}
 2 Y = {10, 11, 12}
 2 K = {verde, amarelo, azul, branco}
 2 X ∪ Y = {a, b, c, 10, 11, 12} (Figura 1.4);
 2 X ∪ K = {a, b, c, verde, amarelo, azul, branco};
 2 Y ∪ X ∪ K = {a, b, c, verde, amarelo, azul, branco, 10, 11, 12}. 
Observe que a ordem dos elementos não muda o resultado da 
operação.
Figura 1.4 – União de conjuntos
X
a b c
 
10 
11 
12
X ∪ Y
a 
10 
11 12 
c c
Fonte: elaborada pelo autor.
 Importante
Propriedades da União:
Conjuntos A, B e C quaisquer.
P1) A ∪ {} = A; União com o conjunto vazio é sempre o próprio conjunto;
P2) A ∪ U = U; União com o conjunto universo é sempre o conjunto U;
P3) A ∪ A´= U; União com o complementar é sempre o conjunto U; 
o conjunto complementar de A é determinado pelos elementos de um 
conjunto universo que não pertençam a A.
P4) A ∪ A = A; Idempotente; a união de um conjunto qualquer A com 
ele mesmo é igual a A.
– 19 –
Teoria de conjuntos
P5) A ∪ B = B ∪ A; Comutativa; a união de um conjunto A com um con-
junto B é igual à união de um conjunto B com um conjunto A.
P6) (A ∪ B) ∪ C = A ∪ (B ∪ C); Associativa; a união de três conjuntos A, 
B, e C pode ser feita de diversas formas – conjunto A com conjunto B e 
posteriormente com o conjunto C, ou o conjunto B com o conjunto C e 
posteriormente com o conjunto A.
P7) A e B são ambos subconjuntos de A ∪ B, então A ⊂ (A ∪ B) e B ⊂ 
(A ∪ B).
1.4.2 Interseção (∩)
Há interseção entre conjuntos quando os elementos existem tanto em 
um conjunto quanto no outro; quando não existe elemento em comum entre 
dois ou mais conjuntos, a interseção entre conjuntos é um conjunto vazio.
Exemplo:
A = {x | x pertence aos números inteiros positivos.
B = {a}, C = {50, 60, 100, d}
A ∩ B = {}, a interseção dos conjuntos A e B não contém elementos 
em comum, resultando em um conjunto vazio.
A ∩ C = {50, 60, 100} (Figura 1.5).
A ∩ B ∩ C = {}, a interseção dos conjuntos A, B e C não contém 
elementos em comum, resultando em um conjunto vazio.
Figura 1.5 – Interseção de conjuntos
Números 
inteiros 
positivos
d
50 
60 
100
Fonte: elaborada pelo autor.
Fundamentos de Matemática para Informática
– 20 –
 Importante
Propriedades da Interseção:
Conjuntos A, B e C, quaisquer.
P1) A ∩ {} = {}; a interseção com o conjunto vazio é sempre um con-
junto vazio.
P2) A ∩ U = U; a interseção com o conjunto universo resulta sempre no 
conjunto universo.
P3) A ∩ A´ = {}; interseção com o complementar é sempre vazio.
P4) A ∩ A = A, Idempotente; a interseção de um conjunto qualquer A 
com ele mesmo é igual a A.
P5) A ∩ B = B ∩ A, Comutativa; a interseção de um conjunto A com um 
conjunto B é igual a interseção deum conjunto B com um conjunto A.
P6) (A ∩ B) ∩ C = A ∩ (B ∩ C): Associativa. A combinação da interseção 
de três conjuntos A, B e C pode ser feita de diversas formas: conjunto 
A com conjunto B e posteriormente com o conjunto C, ou o conjunto B 
com o conjunto C e posteriormente com o conjunto A.
1.4.3 Diferença (-)
A diferença entre conjuntos ocorre quando todos os elementos que 
pertencem a um conjunto, não existem no outro. Ver Figura 1.6.
Figura 1.6 – Diferença de conjuntos
A C
Fonte: elaborada pelo autor.
– 21 –
Teoria de conjuntos
Exemplos:
 2 D = {x, y, z, 1, 2};
 2 E = {1, 2, 3, 4, 5, 6, 7};
 2 D – E = {x, y, z};
 2 E – D = {3, 4, 5, 6, 7}.
 Importante
Propriedades da diferença:
P1) A – {} = A; conjunto A menos o conjunto vazio é o próprio con-
junto A.
P2) {} – A = {}; conjunto vazio menos o conjunto A é o próprio conjunto 
vazio.
P3) Não é comutativa. Não existe a combinação entre os conjuntos na 
diferença, pois alteraria o resultado.
P4) A – U = {}; conjunto A menos o conjunto universo resulta em con-
junto vazio, pelos elementos que cada conjunto possui.
P5) U – A = A’; conjunto universo menos conjunto A resulta no con-
junto A’.
P6) A – A = {}; conjunto A menos o conjunto A resulta em conjunto vazio.
P7) A – A’= A; conjunto A menos o seu complemento resulta no con-
junto A, pois o complemento de A possui elementos que não existem 
no conjunto A.
P8) (A – B)’= A’ U B. O complemento da diferença entre conjunto A e B 
é igual ao complemento do conjunto A em união ao conjunto B, respei-
tando o conceito já visto de complemento de um conjunto.
P9) A – B = B’ – A’. A diferença do conjunto A pelo conjunto B é igual à 
diferença entre complemento do conjunto B e complemento do conjunto 
A, respeitando o conceito já visto de complemento de um conjunto.
Fundamentos de Matemática para Informática
– 22 –
1.4.4 Complemento (‘)
O complemento de um conjunto é determinado pelos elementos de 
um conjunto universo que não pertençam a este conjunto.
Podem ser considerados o complemento de um conjunto C qualquer 
todos os elementos que não estão em C; é a diferença entre o conjunto 
universal U e o conjunto C.
Exemplos:
 2 C = {a, b, c};
 2 U = {as letras do alfabeto};
O complemento de C, representado por C´ = ∪ – C. Ver Figura 1.7.
Figura 1.7 – Complemento de conjuntos
U
a b 
c
C
Fonte: elaborada pelo autor.
1.5 Diagramas lineares
Além dos diagramas de Euler-Venn, outra forma de representar os 
conjuntos é por meio dos diagramas lineares. Formados por uma linha reta 
vertical, horizontal ou diagonal, indicam se um conjunto é subconjunto de 
outro. A leitura deste diagrama é sempre visualizada de baixo para cima 
(Quadro 1.1).
– 23 –
Teoria de conjuntos
Quadro 1.1 – Diagramas lineares
Conjuntos Representação
Se A está contido em B 
B
A
Se A está contido em B, e B está contido em C
C
A
B
Seja A = {a}, B ={b} e C = {a, b}; os con-
juntos A e B estão contidos no conjunto C. A
C
B
Se X = {x}, Y = {x, y}, Z = {x, y, z} e W = 
{x, y, w}; o conjunto Y contém o conjunto X 
mais o elemento y. O conjunto Z contém o 
conjunto Y mais o elemento z. O conjunto W 
contém o conjunto Y mais o elemento w.
Z
Y
X
W
Fonte: adaptado de Lipschutz (1991).
De forma intuitiva, os diagramas lineares facilitam o entendimento 
dos conjuntos e suas relações.
1.6 Conjuntos numéricos
Existem vários tipos de conjuntos numéricos, e iremos conhecer 
alguns a seguir (GERSTING, 1995; LIPSCHUTZ, 1991):
Fundamentos de Matemática para Informática
– 24 –
1.6.1 Conjunto dos números naturais (N)
O conjunto dos números naturais é representado pela letra N e reúne 
os números positivos que usamos para contar (incluindo o zero). É infinito 
e formado pelos subconjuntos que são não nulos, números primos, pares e 
ímpares, conforme apresentado no Quadro 1.2 a seguir.
Quadro 1.2 – Números naturais N
Subconjuntos Descrição
N* Números naturais, sem o zero
Np = {0, 2, 4, 6, 8..., 2n, ...} Números naturais pares
Ni = {1, 3, 5, 7, 9..., 2n+1, ...} Números naturais ímpares
P = {2, 3, 5, 7, 11, 13, ...} Números naturais primos
Fonte: elaborado pelo autor.
1.6.2 Conjunto dos números inteiros (Z)
O conjunto dos números inteiros é representado pela letra Z. É for-
mado pelos os elementos dos números naturais (N) e os números negati-
vos. É formado pelos subconjuntos inteiros não nulos, inteiros não negati-
vos, inteiros positivos não nulos, inteiros não positivos, inteiros negativos 
não nulos. Apresentados no Quadro 1.3.
Quadro 1.3 – Números inteiros Z
Subconjuntos Descrição
Z* = {..., –4, –3, –2, –1, 1, 2, 
3, 4, ...} ou Z* = Z – {0} Números inteiros não nulos
Z+ = {0, 1, 2, 3, 4, 5, ...} ou Z+ = N Números inteiros não negativos
Z*+ = {1, 2, 3, 4, 5, ...} Números inteiros posi-tivos não nulos
Z – = {..., –5, –4, –3, –2, –1, 0} Números inteiros não positivos
Z*– = {..., –5, –4, –3, –2, –1} Números inteiros nega-tivos, sem o zero.
Fonte: elaborado pelo autor.
– 25 –
Teoria de conjuntos
1.6.3 Conjunto dos números racionais (Q)
O conjunto dos números racionais é representado pela letra Q e é 
formado por todos os números que podem ser escritos na forma de fração, 
x/y, sendo x e y números inteiros e y≠0. Com os seguintes subconjuntos 
racionais: não nulos, não negativos, positivos, não positivos e negativos. 
Ver Quadro 1.4.
Q = {0, ±1, ±1/2, ±1/3, ..., ±2, ±2/3, ±2/5, ..., ±3, ±3/2, ±3/4, ...}.
Quadro 1.4 – Números racionais Q
Subconjuntos Descrição
Q* Números racionais não-nulos, formado pelos números racionais sem o zero.
Q+ Números racionais não-negativos, formado pelos números racionais positivos e o zero.
Q*+ Números racionais positivos, formado pelos números racionais positivos, sem o zero.
Q- Números racionais não-positivos, formado pelos números racionais negativos e o zero.
Q*- Números racionais negativos, formado núme-ros racionais negativos, sem o zero.
Fonte: elaborado pelo autor.
Dízimas periódicas são números racionais. São representados pelo 
resultado da fração, cujos números decimais se repetem após a vírgula. 
Por exemplo: 1/3 – o resultado é representado por 0,3333333... .
1.6.4 Conjunto dos números irracionais (I)
O conjunto dos números irracionais é representado por I e é formado 
por números decimais não exatos com uma representação infinita e não 
periódica. Por exemplo: 3,141592... ou 1,203040...
1.6.5 Conjunto dos números reais (R)
O conjunto dos números reais é representado por R e é formado pelos 
números racionais (Q) e irracionais (I). Desta forma, temos: R = Q ∪ I. 
Fundamentos de Matemática para Informática
– 26 –
Além disso, N, Z, Q e I são subconjuntos de R, conforme apresentado no 
Quadro 1.5 a seguir.
Quadro 1.5 – Números reais R
Subconjuntos Descrição
R*= {x ∈ R│x ≠ 0} Números reais não nulos
R+ = {x ∈ R│x ≥ 0} Números reais não negativos
R*+ = {x ∈ R│x > 0} Números reais positivos
R– = {x ∈ R│x ≤ 0} Números reais não positivos
R*– = {x ∈ R│x < 0} Números reais negativos
Fonte: elaborado pelo autor.
 Dica
Propriedades dos conjuntos numéricos:
P1) O conjunto (N) dos números naturais é um subconjunto dos núme-
ros inteiros: Z (N ⊂ Z).
P2) O conjunto (Z) dos números inteiros é um subconjunto dos núme-
ros racionais: (Z ⊂ Q).
P3) O conjunto (Q) dos números racionais é um subconjunto dos núme-
ros reais (R): (Q ⊂ R)
P4) O conjunto (I) dos números irracionais é um subconjunto dos núme-
ros reais (R): (I ⊂ R)
P5) Os conjuntos dos números naturais (N), inteiros (Z), racionais (Q) e 
irracionais (I) são subconjuntos dos números reais (R).
Atividades
1. Dê exemplos de 2 conjuntos finitos e 2 conjuntos infinitos, 
seguindo a notação apresentada.
– 27 –
Teoria de conjuntos
2. Quais são as relações entre conjuntos? Exemplifique.
3. Quais são as operações fundamentais em conjuntos? Exem-
plifique.
4. Demonstre, no diagrama de Venn, as relações entre os conjuntos 
numéricos N, Z, Q, I e R.
5. Demonstre, em diagramas lineares, as relações entre os conjun-
tos numéricos N, Z, Q, I e R.
Neste capítulo,vamos apresentar os conceitos e os diferen-
tes tipos de lógica: lógica matemática, operadores de proposição, 
negação conjunta e disjunta e o conceito inicial de tabelas ver-
dade. A teoria de conjuntos, sua definição e suas leis embasam 
fortemente o tema que passaremos a tratar e ajudam a compreen-
der os demais capítulos deste livro.
Ao fim deste capítulo, você será capaz de:
 2 compreender lógica;
 2 compreender proposições;
 2 utilizar operadores de proposição.
Proposições lógicas 
e suas operações
2
Fundamentos de Matemática para Informática
– 30 –
2.1 Lógica
A lógica está presente no dia a dia de todos. É a forma de pensa-
mento, raciocínio de um indivíduo ou de um grupo de pessoas. Observe 
as seguintes situações:
 2 Meu voo parte às 19h, devo estar no aeroporto às 18h; para isso, 
tenho que sair de casa às 17h.
 2 O carro precisa de troca de óleo, tenho que levá-lo à oficina.
 2 A comida do cachorro acabou, precisamos comprar ração.
Em todas as situações temos uma ação derivada de uma tarefa ou 
condição que precisa ser executada. Esse tipo de pensamento é um exem-
plo de raciocínio lógico.
A definição de lógica começou na Grécia, com Platão e os sofistas, 
mas teve sua real contribuição com Aristóteles (384-322 a.C.), seguida por 
Kant, na criação do silogismo.
Um silogismo é uma regra de inferência que deduz uma proposição 
categórica – a conclusão – com base em duas outras, chamadas premissas. 
Cada uma das premissas contém um termo comum com a conclusão – o 
termo maior e o termo menor, respectivamente; e um termo comum com 
a outra premissa – o termo médio (BIANCONI, 2012). O silogismo nos 
permite concluir determinada condição tomando como base as premissas. 
Estas podem ser: maior, menor e conclusão.
Segundo Kant (BIANCONI, 2012), cada premissa apresenta termos 
que são: menor (existente na premissa, sendo o sujeito da conclusão); 
médio (existente em ambas as premissas, mas não na conclusão; responsá-
vel por fazer a ligação entre as duas premissas); e o termo maior (existente 
na premissa maior; é o predicado da conclusão).
Utilizando o exemplo clássico da literatura (filosófica e matemática):
1. todo homem é mortal. – premissa maior (universal)
2. Sócrates é homem. – premissa menor (particular)
3. Sócrates é mortal. – conclusão
– 31 –
Proposições lógicas e suas operações
 Importante
Os termos são:
maior: mortal;
menor: Sócrates;
médio: homem.
Sócrates é o sujeito da conclusão; homem é o termo médio que aparece 
em ambas as premissas; a conclusão é a sentença 3, onde a ligação entre 
as premissas é feita. Podemos também dizer: “Todo homem é mortal. 
Sócrates é homem, logo Sócrates é mortal”.
Segundo o dicionário Michaelis ([S.d]), existem vários tipos de 
lógica, iniciando pela aristotélica. Há também as lógicas: booleana, das 
proposições, dialética, difusa, formal, matemática, modal, polivalente, 
sentencial, simbólica e transcendental.
A lógica formal é a lógica aristotélica.
 2 Lógica booleana: criada por George Boole (1815 – 1864), mate-
mático britânico, é uma estrutura que organiza as operações 
lógicas (álgebra de boole), influenciando desde programação até 
videogames (MOREIRA, 2007).
 2 Lógica das proposições: pertence à lógica formal e se trata do 
cálculo proporcional, também conhecida como lógica senten-
cial. Algo declarado por meio de termos, palavras ou símbolos 
cujo conteúdo será verdadeiro ou falso (LIMA, [S.d.]).
 2 Lógica dialética: criada pelo filósofo alemão Georg Hegel 
(1770-1831), permite que seja gerada uma síntese com base na 
afirmação (tese) à negação (antítese), com o objetivo de indicar 
categorias racionais válidas, fazendo que a análise seja feita com 
base em vários pontos que formam a tese e a antítese.
 2 Lógica fuzzy: também conhecida como difusa, é diferente da 
matemática cartesiana (que aceita somente valores: verdadeiro 
Fundamentos de Matemática para Informática
– 32 –
ou falso). Permite a utilização de valores que podem estar entre 
determinada faixa, de forma que possam ser aceitos ou negados. 
Por exemplo: o que torna um copo meio cheio ou meio vazio?
2.2 Lógica matemática
A matemática precisa de uma linguagem ou notação formal para que 
possa ser identificada e aplicada. Na lógica matemática não seria dife-
rente; portanto, vamos apresentar conceitos importantes.
Na matemática básica temos a seguinte expressão: 2 + 2 = 4, em 
que + e = são os operadores, 2, 2 são os operandos, e 4 é o resultado da 
expressão. Esse cálculo é bastante conhecido e utilizado com frequência. 
A lógica matemática segue regras semelhantes, sendo que os operadores 
são chamados de conectivos e os operandos são chamados de proposições.
2.2.1 Proposições e conectivos
Vamos começar a apresentar a forma de linguagem da lógica mate-
mática. De forma simples, a compreensão destes conceitos é muito impor-
tante para o entendimento dos próximos capítulos.
Proposição, pela própria definição da palavra, é o ato ou o efeito de 
propor. Mas propor o quê? De certa forma, pode-se descrever proposição 
como um conjunto de palavras que expressam uma ideia, que mostram um 
pensamento, que demonstram fatos ou apresentam opiniões que forma-
mos a respeito de determinados assuntos. Por exemplo:
 2 Os peixes vivem no mar.
 2 A capital do Brasil é Brasília.
 2 Fernando de Noronha é uma reserva marinha brasileira.
Quando falamos em opiniões ou ideias expressas, não necessaria-
mente indicamos se está certo ou errado, se é verdadeiro ou falso, são 
somente pensamentos.
Na lógica matemática, se estas ideias formam proposições, devem ter 
valores que só podem ser verdadeiro (V) OU falso (F).
– 33 –
Proposições lógicas e suas operações
 Importante
Pode existir alguma proposição que seja, ao mesmo tempo, verdadeira 
e falsa? Não, de forma alguma. O raciocínio lógico-matemático, como 
um todo, está embasado nos princípios da identidade, não contradição 
e terceiro excluído:
A lógica matemática adota como regras fundamentais do pensamento 
os seguintes axiomas:
(I) Princípio da não contradição: uma proposição não pode ser verda-
deira e falsa ao mesmo tempo.
(II) Princípio do terceiro excluído: toda proposição ou é verdadeira ou 
é falsa, isto é, verifica-se sempre um destes casos e nunca um terceiro 
(FILHO, 2003).
2.2.1.1 Classificação das proposições
Segundo Alencar (FILHO, 2003), as proposições podem ser classifi-
cadas em:
 2 Simples (atômicas) – não contêm nenhuma outra proposição; 
são desacompanhadas, desta forma pode ter seu valor verdadeiro 
ou falso. As proposições simples são geralmente designadas 
pelas letras p, q, r, ...
Exemplos de proposições simples:
 2 A lua é um satélite da terra.
 2 H2O é a forma química da água.
 2 A cor do céu é verde.
 2 Nenhum mamífero vive no mar.
 2 Compostas (moleculares) – formadas pela combinação de duas 
ou mais proposições, são conectadas entre si. Também são cha-
madas de fórmulas proposicionais e são representadas pelas 
letras maiúsculas P, R, S, ...
Fundamentos de Matemática para Informática
– 34 –
Exemplos de proposições compostas:
 2 O mar é verde e os lagos também.
 2 Golden é raça de cachorro ou siamês é raça de gato.
 2 Pedro leva a bebida e Jorge leva a sobremesa.
 2 Maria passou em medicina e José em matemática.
 Dica
O valor lógico de uma proposição pode ser representado por VL(p) ou 
V(p), portanto V(p) = V quer dizer que o valor lógico de p é verdade, e 
V(p) = F indica que o valor lógico da proposição p é falso (FILHO, 2002).
A representação tanto das proposições simples quanto das compostas 
são chamadas de letras proposicionais.
O valor lógico de uma proposição simples (assim como de proposi-
ções compostas) pode ser somente verdadeiro (V) ou falso (F), mas nas 
proposições compostas devemos levar em consideração os valores lógicos 
das proposições simples componentes e dos itens que as estão ligando.
2.3 Conectivos
Conectivos (Tabela 2.1) são símbolos ou palavras usados para ligar 
proposições simples e formar proposições compostas,ou alterar seu valor 
no caso da negação da proposição (LIPSCHUTZ, 1991).
Tabela 2.1 – Conectivos
Símbolo Partícula Nome
~ não Negação
∧ e Conjunção
∨ ou Disjunção
⩣ ou exclusivo Disjunção exclusiva
→ se então Condicional
↔ se e somente se Bicondicional
Fonte: elaborada pelo autor.
– 35 –
Proposições lógicas e suas operações
Também são utilizados parênteses ( ) para modificar a precedência 
ou definir quais operações serão executadas antes, e, desta forma, obter o 
valor lógico correto.
2.4 Operações lógicas sobre proposições.
Temos proposições, valores lógicos e conectivos, agora vamos 
ver como executar operações sobre as proposições – operações que 
seguem regras do cálculo proposicional, semelhante ao da aritmética 
sobre números.
Existem várias formas de representação das operações lógicas: des-
critivas (é explicada por extenso cada operação com seus resultados), 
tabela verdade (forma de tabela que será detalhadamente apresentada no 
próximo capítulo).
As operações a seguir são chamadas de operações lógicas fundamentais.
2.4.1 Conjunção (E) (∧)
Chama-se conjunção quando duas ou mais proposições estão ligadas 
pela letra E ou o símbolo ∧.
O resultado lógico será verdadeiro somente quando as duas propo-
sições forem verdadeiras, nos demais casos o resultado será falso, como 
demonstrado na Tabela 2.2, a seguir.
Tabela 2.2 – Conjunção
V ∧ V = V
V ∧ F = F
F ∧ V = F
F ∧ F = F 
Fonte: elaborada pelo autor.
Fundamentos de Matemática para Informática
– 36 –
Por exemplo:
Apresentando as proposições: p, q e r, temos:
 2 p: A lua é um satélite natural da terra.
 2 q: Marte é um planeta.
 2 r: Todos os animais marinhos são mamíferos.
As proposições verdadeiras são p e q, portanto V(p) = V e V(q) = V, 
ao passo que r é falsa V(r) = F. Utilizando a tabela verdade (Tabela 2.3) 
para representação, o resultado da operação lógica p ∧ q é verdadeiro.
Tabela 2.3 – Tabela verdade conjunção
p q p ∧ q
V V V
V F F
F V F
F F F
Fonte: elaborada pelo autor.
Mas, para p ∧ r, o resultado da operação é falso, pois V(p) é verda-
deiro, mas V(r) é falso; a conjunção de V ∧ F resulta em falsidade.
Tabela 2.4 – Tabela verdade conjunção
p r p ∧ r
V V V
V F F
F V F
F F F
Fonte: elaborada pelo autor.
Aplicando o conectivo em proposições compostas, tal como P = p ∧ 
q ∧ r, a resolução ocorre na ordem que aparecem, primeiro p ∧ q, depois o 
resultado destas duas proposições será aplicado com r. Temos o resultado 
de p ∧ q igual a verdadeiro; ao se aplicar V ∧ r, como r é falso, temos o 
resultado final uma falsidade, afinal V ∧ F = F.
– 37 –
Proposições lógicas e suas operações
2.4.2 Disjunção (OU) (∨)
A operação lógica de disjunção é aplicada utilizando a palavra OU, e 
pode também ser representada pelo símbolo ∨. O resultado lógico vai ser 
verdadeiro sempre que qualquer uma das proposições forem verdadeiras, 
e será falso somente quando as duas proposições forem falsas (Tabela 2.5).
Tabela 2.5 – Operação disjunção
V ∨ V = V
V ∨ F = V
F ∨ V = V
F ∨ F = F 
Fonte: elaborada pelo autor.
Por exemplo:
Apresentando as proposições: p, q e r, temos:
 2 p: 2 + 2 = 5.
 2 q: A água entra em ebulição a 100 graus Celsius.
 2 r: Um metro tem 100 centímetros.
A proposição p tem seu V(p) falso, ao passo que as demais (q, r) são 
verdadeiras, V(q) e V(r ) = V.
O resultado de p ∨ q é verdadeiro conforme a Tabela verdade 2.6, 
pois mesmo V(p) = F, V(q) = V.
Tabela 2.6 – Tabela verdade disjunção
p q p ∨ q
V V V
V F V
F V V
F F F
Fonte: elaborada pelo autor.
Fundamentos de Matemática para Informática
– 38 –
O resultado de p ∨ r também é verdadeiro conforme a Tabela ver-
dade 6, pois mesmo V(p) = falso, v(r) é verdadeiro. Mas o resultado de q 
∨ q é falso, pois ambas são falsas. A disjunção segue a ordem de prece-
dência, de modo que as operações são feitas de acordo com a ordem que 
aparecem. Seja P= p ∨ q ∨ r, o resultado é verdadeiro, pois F ou V ou V 
se resolve da seguinte forma: primeiro p ∨ q = verdadeiro, depois V ou r, 
que é verdade.
2.4.3 Disjunção exclusiva (OU exclusivo) (∨)
A disjunção exclusiva irá retornar um resultado verdadeiro quando 
os valores das proposições forem diferentes, ou seja, quando um for ver-
dade, e o outro, falsidade. Quando os valores lógicos das proposições 
forem os mesmos, o resultado da operação lógica é falso. Observe a 
Tabela 2.7.
Tabela 2.7 – Disjunção exclusiva
V ∨ V = F
V ∨ F = V
F ∨ V = V
F ∨ F = F 
Fonte: elaborada pelo autor.
Por exemplo:
Apresentando as premissas: p, q e r, temos:
 2 p: O sol é uma estrela.
 2 q: A Terra é um satélite.
 2 r: O mar tem água salgada.
A proposição q é falsa (V(q) = F), ao passo que as demais V(p) e V(r) 
são verdadeiras. O resultado de p ∨ q será verdadeiro, pois o valor lógico 
V ∨ F é igual a V.
– 39 –
Proposições lógicas e suas operações
Tabela 2.8 – Disjunção exclusiva
p q p ∨ q
V V F
V F V
F V V
F F F
Fonte: elaborada pelo autor.
As operações com disjunção exclusiva seguem a mesma forma de 
precedência de conjunção e disjunção, portando o valor lógico de P = p ∨ 
q ∨ r é V ∨ F ∨ V e resulta em uma F.
2.4.4 Condicional (Se então) (→)
O Conectivo → (implicação) também chamado de “se então” é ope-
rador cujo resultado lógico é falso somente quando a primeira proposição 
do operador (antecedente) for verdadeira, e a segunda (consequente) for 
falsa. Portanto, uma verdade jamais poderá implicar numa falsidade; nos 
demais casos, o resultado é sempre a verdade (Tabela 2.9).
É representada por: p → q, em que lê-se:
 2 Se p então q,
 2 p é condição suficiente para q
 2 q é condição necessária para p. (LIPSCHUTZ, 1991)
Tabela 2.9 – Condicional
V → V = V
V → F = F
F → V = V
F → F = V 
Fonte: elaborada pelo autor.
Fundamentos de Matemática para Informática
– 40 –
Por exemplo:
Apresentando as proposições: p, q e r, temos:
 2 p: O gelo é frio.
 2 q: O calor é frio.
 2 r: O calor é quente.
A proposição q é falsa V(q) = F, ao passo que as demais (p, r) são 
verdadeiras (V(p) = V, V(r ) =V). O resultado de p → q será falso, pois o 
valor lógico V → F é igual a F.
p q p → q
V V V
V F F
F V V
F F V
A precedência da condicional segue a mesma forma das anteriores, o 
que vem primeiro é resolvido antes, o resultado de P = p → q → r é V(p) 
→ V(q) → V(r), desta forma V(V) → V(F) → V(V). Resolvendo a primeira 
parte, temos F → V, cujo resultado é Verdadeiro.
2.4.5 Bicondicional (Se e somente se) (↔)
No caso da bicondicional, se os valores lógicos das proposições em 
questão forem iguais, o resultado é verdadeiro; caso contrário, o resultado 
é falso (Tabela 2.10). Na operação com ↔, sendo p ↔ q, lê-se p bicondi-
cional q, se e somente se p, então q, p é condição suficiente e necessária 
para q (FILHO, 2003).
Tabela 2.10 – Operador lógico bicondicional
V ↔ V = V
V ↔ F = F
F ↔ V = F
F ↔ F = V 
Fonte: elaborada pelo autor.
– 41 –
Proposições lógicas e suas operações
Por exemplo:
Apresentando as proposições: p, q e r, temos:
 2 p: A raiz quadrada de 25 é 5.
 2 q: Cachorros são mamíferos.
 2 r: Seres humanos são imortais.
A proposição r é falsa (V(r) = F), ao passo que as demais (p, q) são 
verdadeiras (V(p) = V, V(q) = V). O resultado de p ↔ q será verdadeiro, 
pois o valor lógico V ↔ V é igual a V (Tabela 2.11).
Tabela 2.11 – Operador bicondicional
p q p ↔ q
V V V
V F F
F V F
F F V
Fonte: elaborada pelo autor.
2.4.6 Negação (Não) (~)
Ao aplicar a operação de negação de uma proposição, seu valor 
lógico será alterado. Se este valor for verdadeiro, o resultado desta ope-
ração é falso, e se o valor for falso, o resultado da operação de negação 
será verdadeiro. Para negar uma proposição é simples: deve-se colocar a 
palavra não ou o símbolo ~ no início da proposição (LIPSCHUTZ, 1991).
 2 ~V = F
 2 ~F = V
Por exemplo:
Apresentando a proposição p:
p: O sapo é um anfíbio.
Fundamentos de Matemática para Informática
– 42 –
A premissa p é verdadeira, V(p) = V. O resultado de ~p será falso, 
pois o valor lógico da negação de uma verdade gera uma falsidade.
p ~p
V F
F VNeste capítulo foram apresentados os temas de proposições, conec-
tivos e a operações básicas em lógica matemática. Agora, exercite seu 
conhecimento resolvendo os exercícios a seguir.
Atividades
1. Descreva e dê exemplos de proposições, conectivos.
2. Dadas as seguintes proposições, diga o valor lógico resultante das 
operações de E, OU, OU exclusivo, condicional, bicondicional.
a) Via Láctea é uma galáxia.
b) Zero é um número negativo.
3. Mostre a tabela verdade de todos os conectivos apresentados nas 
proposições anteriores.
4. Os valores das proposições podem ser diferentes de Verdadeiro 
ou Falso? Explique.
Tabela verdade é uma forma de representação dos possí-
veis valores e resultados de proposições. É bastante utilizada para 
demonstrar valores e resultados de operações em lógica matemática.
Ao fim deste capítulo, você será capaz de:
 2 aprofundar o conhecimento sobre tabelas verdade;
 2 construir tabelas verdade;
 2 calcular operações com proposições compostas.
Tabelas verdade
3
Fundamentos de Matemática para Informática
– 44 –
3.1 Tabela verdade
Tabela verdade é uma forma gráfica muito simples para fazer o cál-
culo com operadores. Tivemos o primeiro contato com este tema no capítulo 
anterior, mas agora vamos aprender passo a passo como criá-las. Com as 
tabelas verdade das operações fundamentais podemos estender e criar tabelas 
correspondentes para calcular o resultado de qualquer proposição composta.
Com efeito, toda proposição simples tem dois valores lógicos: V e F, 
que se excluem. Portanto, para uma proposição composta P (p1, p2, ..., n) 
com n proposições simples componentes, p1, p2, ..., pn, há tantas possibi-
lidades de atribuição de valores lógicos V e F a tais componentes quantos 
são os arranjos com repetição n a n dos dois elementos V e F, isto é, A2,n 
=2n, segundo ensina a analise combinatória (FILHO, 2003).
A quantidade de linhas da tabela verdade será sempre 2n, em que n é 
a quantidade de proposições. Sendo somente p, uma única proposição, a 
quantidade de linhas é 21 = 2, se for p e q (duas), 22 = 4, se for p, q, r e s, 
24 = 16, e assim sucessivamente
A estrutura da tabela verdade é composta por colunas, nas quais ficam 
as proposições e conectivos (operadores e operandos), e nas linhas ficam 
os valores lógicos e suas combinações (LIPSCHUTZ, 1991).
A ordem e a quantidade de V e F a serem colocadas, por coluna, para 
as proposições, segue esta regra:
A quantidade de linhas é definida pela fórmula 2n, em que n é a quan-
tidade de proposições. Para a primeira coluna, calcula-se x = 2n/2.
Exemplo 1
Para uma tabela com 2 proposições, temos:
 2 x = 22/2;
 2 x = 4/2;
 2 x = 2.
O resultado x apresenta quantos valores verdadeiros e falsos devem 
aparecer em ordem na coluna da primeira proposição. Veja a tabela a 
– 45 –
Tabelas verdade
seguir: p está na primeira coluna e x = 2, ou seja, deve-se preencher a 
tabela com 2 Vs e depois com 2 Fs.
 p q
V
V
F
F
Da segunda coluna em diante, basta executar x/2 = 1. Neste caso, os 
valores V e F vão se alternar uma única vez.
p q
V V
V F
F V
F F
Exemplo 2
Faremos agora para três proposições – p, q, r. Como temos 3 propo-
sições 23 = 8, x = 8/2 = 4, os valores V e F para a primeira proposição vão 
se alternar de 4 em 4 – primeiro 4 Vs seguidos de 4 Fs.
P q r
V
V
V
V
F
F
F
F
Fundamentos de Matemática para Informática
– 46 –
Para o próximo passo, preencher a coluna da proposição q. Temos 
x/2 = 4/2 = 2, portanto os valores V e F para a segunda proposição vão se 
alternar de 2 em 2 – primeiro 2 Vs seguidos de 2 Fs.
P q r
V V
V V
V F
V F
F V
F V
F F
F F
Para o próximo passo, vamos preencher a coluna da proposição q. 
Temos x/2 = 2/2 = 2, portanto os valores V e F para a terceira proposição 
vão se alternar de 2 em 2 – primeiro 2 Vs seguidos de 2 Fs.
P q r
V V V
V V F
V F V
V F F
F V V
F V F
F F V
F F F
O exemplo mais simples é o 
da operação fundamental de nega-
ção (Tabela 3.1):
Tabela 3.1 – Tabela verdade negação
p ~p
V F
F V
Fonte: elaborada pelo autor.
– 47 –
Tabelas verdade
Na primeira linha, p e ~p; depois, por coluna, coloca-se os valores 
lógicos começando sempre por V, depois F, e assim sucessivamente.
Vamos ver outro exemplo, para a proposição p ∧ q:
Tabela 3.2 – Exemplo para a proposição p∧q
1 2 3 Descrição
p q p ∧ q primeiro as proposições simples, depois as proposi-ções compostas (proposições com os conectivos)
V V V Depois os valores lógicos e suas com-binações; neste caso, V, V e V
V F F Neste caso, V, F e F
F V F F, V e F
F F F F, F e F, assim temos os possíveis valores lógicos, sua combinação e o resultado da operação conjunção ∧
Fonte: elaborada pelo autor.
Vamos ver mais alguns exemplos para compreender melhor e fixar 
o aprendizado.
 Importante
A ordem de precedência entre os conectivos é: resolver as operações 
que estão dentro de parênteses primeiro, depois a negação, seguida 
pela conjunção, depois disjunção e disjunção exclusiva, em penúltimo a 
condicional e por último a bicondicional (Tabela 3.3).
Tabela 3.3 – Ordem de precedência
1 () Parênteses
2 ~ Negação
3 ∧ Conjunção
4 ∨ Disjunção
5 V Disjunção exclusiva
6 → Condicional
7 ↔ Bicondicional
Fundamentos de Matemática para Informática
– 48 –
Exemplo 1
Para este caso, vamos utilizar um exemplo do clássico do livro de Filho 
(2003) e fazer várias soluções de uma tabela verdade para P(p, q) = ~ (p ∧ ~q).
São duas proposições p e q, logo, a tabela verdade terá 22 = 4 linhas 
de valores lógicos.
Solução 1.
Crie as colunas para cada preposição (p, q), depois crie uma coluna 
para a próxima operação que precisa ser resolvida, no caso, a Negação 
(1), que está dentro dos parênteses; em seguida, a conjunção dentro dos 
parênteses (2), e, finalmente, a negação (Tabela 3.4).
Tabela 3.4 – Tabela verdade Solução 1
1 2 3
p q ~q p ∧ ~q ~ (p ∧~q)
V V F F V
V F V V F
F V F F V
F F V F V
Fonte: elaborada pelo autor.
Solução 2
Crie as colunas para cada preposição (p, q), depois uma coluna para 
cada proposição e outra para cada conectivo (Tabela 3.5).
Tabela 3.5 – Tabela verdade Solução 2
4 1 3 2 1
p q ~ (p ∧ ~ q)
V V V V F F V
V F F V V V F
F V V F F F V
F F V F F V F
Fonte: elaborada pelo autor.
– 49 –
Tabelas verdade
Solução 3
Crie as colunas para cada preposição (p, q), depois uma coluna para 
proposição e outra para cada conectivo (Tabela 3.6).
Tabela 3.6 – Tabela verdade Solução 3
4 1 3 2 1
~ (p ∧ ~ q)
V V F F V
F V V V F
V F F F V
V F F V F
Fonte: elaborada pelo autor.
 Dica
A tabela ajuda a relembrar o resultado das operações fundamentais em 
lógica matemática (Tabela 3.7). Fixando esses resultados, fica mais fácil 
e rápido fazer a tabela verdade.
Tabela 3.7 – Resumo operações fundamentais para tabela verdade
p Q ~p p ∧ q p ∨ q p ∨ q p → q p ↔ q
V V F V V F V V
V F F F V V F F
F V V F V V V F
F F V F F F V V
Fonte: elaborado pelo autor.
Exemplo 2:
Sendo P uma proposição composta por p e q, 2 proposições, a quan-
tidade de linhas da tabela verdade é 22 = 4.
P(p, q) = ~q ∧ q ↔ p ∨ ~p
Fundamentos de Matemática para Informática
– 50 –
Solução 1
1 2 3 4 5
p q ~q ~p ~q ∧ q P ∨ ~p ~q ∧ q ↔ p ∨ ~p
V V F F F V F
V F V F F V F
F V F V F V F
F F V V F V F
Solução 2
P(p, q) = ~q ∧ q ↔ p ∨ ~p
P q ~q ∧ q ↔ p ∨ ~p
V V F F V F V V F
V F V F F F V V F
F V F F V F F V V
F F V F F F F V V
Solução 3
P(p, q) = ~q ∧ q ↔ p ∨ ~p
~q ∧ q ↔ p ∨ ~p
F F V F V V F
V F F F V V F
F F V F F V V
V F F F F V V
Exemplo 3:
Sendo P uma proposição composta por p, q, r, 3 proposições, a quan-
tidade de linhas da tabela verdade é 23 = 8.
P(p, q, r) = p → ~ (q ∨ r ∧ ( ~r ))
– 51 –
Tabelas verdade
Solução 1
P q r r q ∨ r (q ∨ r ∧ ( ~r ) ~(q ∨ r ∧ ( ~r )) p → ~ (q ∨ r ∧ ( ~r ))
V V V F V F V V
V V F V V V F F
V F V F V F V V
V F F V F F V V
F V V F V F V V
F V F V V V F V
F F V F V F V V
F F F V F F V V
Solução 2
p q r p → ~ (q ∨ r ∧ (~ r ))
V V V V V V V V V F F V
V V F V F F V V F V V F
V F V V V V F V V F F V
V F F V V V F F F F V F
F V V F V V V V V F F V
F V F FV F V V F V V F
F F V F V V F V V F F V
F F F F V V F F F F V F
Solução 3
P → ~ (q ∨ r ∧ (~ r ))
V V V V V V F F V
V F F V V F V V F
V V V F V V F F V
Fundamentos de Matemática para Informática
– 52 –
P → ~ (q ∨ r ∧ (~ r ))
V V V F F F F V F
F V V V V V F F V
F V F V V F V V F
F V V F V V F F V
F V V F F F F V F
3.2 Símbolos de conectivos
Neste capítulo foram apresentados os símbolos mais comuns para 
conectivos, mas você pode encontrar os símbolos da tabela 3.8, que tam-
bém representam negação, conjunção ou condicional:
Tabela 3.8 – Símbolos adicionais para conectivos
~ ˥ Negação
∧ . (ou) & Conjunção
→ ͻ Condicional
Fonte: elaborada pelo autor.
Dadas as proposições compostas:
 2 p ∧ q e p . q e p & q, representam conjunção
 2 ~p e ˥p representam negação
 2 p → q e p ͻ q representam condicional
Atividades
1. Construa a tabela verdade (duas soluções) para as seguintes 
proposições:
a) ~ p ∨ q → r ↔ p ∧q.
b) ~ (p ∨ q →) r ↔ p ∧q.
– 53 –
Tabelas verdade
c) ~ (p ∨ q → r) ↔ (p ∧q).
d) ~ p ↔ q → r ∨ p ∨ p ∧ q.
e) ~p Ʌ q → ~p ∨ ~q
f) p → ~q ∨ ~p ∨ ~q
g) p (→ ~q) ∨ ~p ∨ ~q
Os resultados das proposições compostas podem ser clas-
sificados em 3 tipos: tautologias, contradições e contingências. 
Além disso, veremos a implicação lógica e suas regras.
Ao fim deste capítulo você será capaz de:
 2 conhecer e diferenciar tautologias, contradições e con-
tingências;
 2 conhecer o princípio da substituição para tautologias e 
contradições;
 2 definir implicações lógicas.
A partir deste capítulo começaremos a integração com os 
capítulos anteriores. Os conceitos apresentados são muito impor-
tantes para a utilização das técnicas que serão abordadas nos pró-
ximos capítulos.
Tautologias, 
contradições, 
contingências e 
implicações lógicas
4
Fundamentos de Matemática para Informática
– 56 –
4.1 Tautologia
Quando todos os valores da coluna final de uma tabela verdade são 
verdadeiros (valor lógico V), a proposição composta é uma tautologia. 
Na literatura, pode ser também chamada de proposições tautológicas ou 
proposições logicamente verdadeiras.
Em outros termos, tautologia é toda proposição composta P(p, q, r) 
cujo valor lógico é sempre V (verdade), quaisquer que sejam os valores das 
proposições simples componentes p, q, r,... (ALENCAR FILHO, 2003).
A seguir, apresentaremos alguns exemplos clássicos de tautologia 
(ALENCAR FILHO, 2003):
Exemplo 1
~(p ∧ ~P): o princípio da não contradição (uma proposi-
ção não pode ser verdade ou falsidade ao mesmo tempo) é tau-
tológico, pois a coluna final da proposição é verdadeira:
p ~ (p ∧ ~ p)
V V V F F V
F V F F V F
Exemplo 2
p ∨ ~p: princípio do terceiro excluído (uma pro-
posição ou é verdade ou falsidade):
p p ∨ ~ p
V V V F V
F F V V F
Exemplo 3
((p → q) → r) → (p → (q → r))
– 57 –
Tautologias, contradições, contingências e implicações lógicas
p q r ((p → q) → r) → (p → (q → r))
V V V F V V V V V V V V V V
V V F F V V F F V V F V F F
V F V F F F V V V V V F V V
V F F F F F V F V V V F V F
F V V V V V V V V F V V V V
F V F V V V F F V F V V F F
F F V V V F V V V F V F V V
F F F V V F F F V F V F V F
O exemplo 3 tem todos os valores na coluna final V (verdadeiro). 
portanto é uma tautologia.
4.2 Contradição
A contradição é exatamente o oposto da tautologia: ocorre quando 
todos os valores da coluna final de uma tabela verdade são falsos (valor 
lógico F); essas proposições são também chamadas de proposições con-
traválidas ou proposições logicamente falsas (MORTARI, 2001).
Exemplo 1
p ∧ ~p
p p ∧ ~ p)
V V F F V
F F F V F
A coluna resultado apresenta somente valores F (falsos), caracteri-
zando uma contradição.
Exemplo 2
~(p ∧ r → ~q ∨ r)
Fundamentos de Matemática para Informática
– 58 –
p q r ~ (p ∧ r → ~ q ∨ r)
V V V F V V V V F V V V
V V F F V F F V F V F F
V F V F V V V V V F V V
V F F F V F F V V F V F
F V V F F F V V F V V V
F V F F F F F V F V F F
F F V F F F V V V F V V
F F F F F F F V V F V F
Observe que a negação de uma tautologia é sempre uma contradição, 
e vice-versa.
4.3 Contingência
As proposições compostas são chamadas de contingência quando não 
são nem tautologias, nem contradições, portanto são proposições cujos 
valores na coluna final da tabela verdade podem ser lógicos ∨ ou F; são 
também denominadas proposições contingentes ou proposições indeter-
minadas (MENDELSON, 1997).
Exemplo 1
P (p, q, r): p ∨ q ∧r
p q r p ∨ q ∧ r
V V V V V V V V
V V F V V V F F
V F V V V F V V
V F F V V F F F
F V V F V V F V
F V F F V V F F
F F V F F F F V
F F F F F F F F
– 59 –
Tautologias, contradições, contingências e implicações lógicas
A coluna resultado tem valores ∨ (verdadeiro) e F (falso), portanto é 
uma contingência.
Exemplo 2
P (p, q): p → (~q ∨ p)
p q p → (~ q ∨ p)
V V V V F V V V
V F V V V F V V
F V F V F V F F
F F F F V F V F
Neste caso, também a coluna final de uma tabela verdade tem valores 
∨ (verdadeiro) e F (falso), caracterizando-se uma contingência.
4.4 Princípio da substituição
O princípio da substituição se caracteriza por trocar uma proposição 
qualquer em uma tautologia ou contradição, mantendo seu valor lógico.
Segundo Mendelson (1997), se P (p, q, r, ...) é uma tautologia, então 
P (P0, Q0, R0, ...) também é uma tautologia, independentemente de quais 
sejam as proposições P0, Q0, R0, ...
Para melhorar a compreensão, veja os exemplos a seguir.
4.4.1 Substituição em uma tautologia
Exemplo 1
P (p, q): p ∨ ~p ∨ q
p q p ∨ ~ p ∨ q
V V V V F V V V
V F V V V V V F
Fundamentos de Matemática para Informática
– 60 –
p q p ∨ ~ p ∨ q
F V F V F F V V
F F F V V F V F
A proposição composta P (p, q): p ∨ ~p ∨ q é uma tautologia; com 
base nela, escolha uma sentença lógica qualquer, independentemente de 
seu valor lógico. A proposição escolhida para essa substituição é:
Q (s, u) = s ∧ u.
s u s ∧ u
V V V V V
V F V F F
F V F F V
F F F F F
Agora, na proposição inicial P, substitua qualquer proposição simples 
pela sentença escolhida Q. A nova sentença também é uma tautologia.
P (p, q): p ∨ ~p ∨ q, – Proposição original.
Q (s, u) = s ∧ u – Proposição escolhida para substituição.
Substituindo Q pela proposição simples p:
 2 P (Q0, q): Q0 ∨ ~Q0 ∨ q,
 2 P (Q0, q): = (s ∧ u) ∨ ~( s ∧ u) ∨ q,
S u q (s ∧ u) ∨ ~ (s ∧ u) ∨ q
V V V V V V V F V V V V V
V V F V V V V F V V V F F
V F V V F F V V V F F V V
V F F V F F V V V F F V F
F V V F F V V V F F V V V
F V F F F V V V F F V V F
– 61 –
Tautologias, contradições, contingências e implicações lógicas
S u q (s ∧ u) ∨ ~ (s ∧ u) ∨ q
F F V F F F V V F F F V V
F F F F F F V V F F F V F
Exemplo 2
A proposição composta P (p, q, r) = ((p → q) → r) → (p → (q → r)) 
é uma tautologia; com base nela, escolha uma sentença lógica qualquer, 
independentemente de seu valor lógico. A proposição escolhida para essa 
substituição é Q (s, u) = s ∨ u. Agora, na proposição inicial P, substitua 
qualquer proposição simples pela sentença escolhida Q. A nova sentença 
também é uma tautologia.
P (p, q, r) = ((p → q) → r) → (p → (q → r)), – Proposição original.
Q (s, u) = s ∨ u – Proposição escolhida para substituição.
s u s ∨ u
V V V V V
V F V V F
F V F V V
F F F V F
Substituindo Q pela proposição simples s:
 2 P (p, q, r) = ((p → q) → Q) → (p → (q → Q)),
 2 P (p, q, r) = ((p → q) → (s ∨ u)) → (p → (q → (s ∨ u))),
A tabela verdade demonstra a substituição e a veracidade da regra.
p q s u (((p → q) → (s ∨ u)) → (p → (q → (s ∨ u)))
V V V V V V V V V V V V V V V V V V V
V V V F V V V V V V F V V V V V V V F
V V F V V V V V F V V V V V V V F V V
V V F F V V V F F F F V V F V F F F F
V F V V V F F V V V V V V V F V V V V
Fundamentos de Matemática para Informática
– 62 –
p q s u (((p → q) → (s ∨ u)) → (p → (q → (s ∨ u)))
V F V F V F F V V V F V V V F V V V F
V F F V V F F V F V V V V V F V F V V
V F F F V F F V F F F V V V F V F F F
F V V V F V V V V V V V F V V V V V V
F V V F F V V V V V F V F V V V V V F
F V F V F V V V F V V V F V V F F V V
F V F F F V V F F F F V F V V V F F F
F F V V F V F V V V V V F V F V V V V
F FV F F V F V V V F V F V F V V V F
F F F V F V F V F V V V F V F V F V V
F F F F F V F F F F F V F V F V F F F
4.4.2 Substituição em uma contradição
Assim como o princípio da substituição é válido para tautologias, é 
também válido para contradições, e as regras de substituições são as mes-
mas (ALENCAR FILHO, 2003).
Exemplo 1
P: p ↔ ~p; Proposição original
p p ↔ ~ p
V V F F V
F F F V F
Q: p ∨ q Proposição escolhida para substituição:
p q p ∨ q
V V V V V
V F V V F
F V F V V
F F F F F
– 63 –
Tautologias, contradições, contingências e implicações lógicas
Substituindo Q pela proposição simples p:
 2 P: Q0 ↔ ~Q0
 2 P: (p ∨ q) ↔ ~( p ∨ q)
p q (p ∨ q) ↔ ~ (p ∨ q)
V V V V V F F V V V
V F V V F F F V V F
F V F V V F F F V V
F F F F F F V F F F
4.5 Implicação Lógica
As proposições compostas podem ser consideradas independen-
tes ou dependentes, de acordo com a combinação dos valores em sua 
tabela verdade.
Duas proposições são consideradas independentes quando em suas 
tabelas verdade ocorrem as quatro alternativas, como apresentado na 
tabela a seguir: (VV, VF, FV, FF) (CHISWELL; WILFRID, 2007):
p q
V V
V F
F V
F F
E são consideradas dependentes quando em suas tabelas verdade 
uma ou mais alternativas (VV, VF, FV, FF) não ocorrem. Quando 
duas alternativas não ocorrem, a relação é chamada de relação dupla 
( MORTARI, 2001).
Uma proposição P (p, q, r, …) implica logicamente uma proposição 
Q (p, q, r, …) se Q (p, q, r, … ) é verdadeira todas as vezes que P (p, q, r, 
… ) é verdadeira (LEWIS, 1918).
Fundamentos de Matemática para Informática
– 64 –
A implicação de proposições é representada com o símbolo ⟹. Uma 
proposição P implica – ou implica logicamente – uma proposição Q, se e 
somente se P ⟹ Q é tautológica.
 Importante
Não confundir: Os símbolos → e ⇒ representam situações diferentes. 
Condicional → indica uma operação entre proposições, dando origem 
a uma nova proposição, já a implicação ⇒ indica uma relação entre 
duas proposições.
Exemplo 1
A proposição p ∧ q e ∨ (verdade) na primeira linha, e nesta linha as 
proposições p ∨ q e p ↔ q também são V(verdadeiras), desta forma cada 
uma das proposições implicam nas demais.
Então p ∧ q => p ∨ q e p ∧ q => p ↔ q
p q p∧q p˅q p↔q
V V V V V
V F F V F
F V F V F
F F F F V
Fonte: Alencar Filho (2003).
Exemplo 2
Então ( p → q) ∧ p ⇒ p → q
p q p→q (p→q)∧P
V V V V
V F F F
F V V F
F F V F
Fonte: Alencar Filho (2003).
– 65 –
Tautologias, contradições, contingências e implicações lógicas
A proposição (p → q) ∧ p é ∨ (verdadeira) somente na primeira 
linha, e nesta linha a proposição q é ∨ (verdadeira), assim, existe a impli-
cação lógica.
Exemplo 3
P ↔ ~q Não implica em p ↔ q
p q ~q p↔~q p→q
V V F F V
V F V V F
F V F V V
F F V F V
Fonte: Alencar Filho (2003).
A proposição (p → ~q) é ∨ (verdade) na segunda linha, e nesta linha 
a proposição p → q é F (falsa), portanto não há implicação lógica.
4.5.1 Propriedades da implicação lógica
A implicação lógica apresenta 2 propriedades – reflexiva e transitiva 
– apresentadas a seguir (ALMEIDA FILHO, 2003):
Reflexiva (R): indica que qualquer proposição composta P implica 
nela mesma.
P (p, q, r, … ) ⇒ P (p, q, r, … )
Transitiva (T): para uma proposição composta P implicando em outra 
proposição composta Q, e Q implicando em uma proposição composta R; 
consequentemente, P também implica em R.
Se P (p, q, r, … ) ⇒ Q (p, q, r, … ) e
Q (p, q, r, … ) ⇒ R (p, q, r, … ), então:
P (p, q, r, … ) ⇒ R (p, q, r, … )
Fundamentos de Matemática para Informática
– 66 –
Atividades
Construa a tabela verdade para as seguintes proposições
1. Dadas as proposições a seguir, demonstre, usando tabela ver-
dade, se são: tautologia, contradição ou contingência.
a) (p → q) ∧ p → q.
b) (p ∨ q) → p ∧ q.
c) ~ (p ∨ q → r) ↔ (p ∧q).
2. Demonstre se as proposições a seguir apresentam implicação 
ou não.
a) (p ∨ q) => ~p.
b) ( p → q ) ∧ (q → r) => (p → r).
Equivalências lógicas nos permitem substituir qualquer pro-
posição pela sua equivalente, de forma que o resultado das ope-
rações sobre as proposições não seja alterado. Isso permite sua 
simplificação, cálculo e aplicação em diversas áreas, tais como 
circuitos lógicos e arquitetura de computadores. Apresentaremos 
maiores detalhes nos capítulos específicos de circuitos lógicos.
Ao fim deste capítulo você será capaz de:
 2 definir equivalência lógica;
 2 conhecer equivalências lógicas notáveis;
 2 conhecer e aplicar as propriedades das equivalências 
lógicas;
 2 aplicar o método dedutivo;
 2 avaliar as formas normais.
Equivalências lógicas
5
Fundamentos de Matemática para Informática
– 68 –
Vamos utilizar muitos conceitos dos capítulos anteriores, por isso é 
bastante importante que não haja dúvidas para consolidar o aprendizado 
deste capítulo.
5.1 Equivalências lógicas
Duas proposições p e q são logicamente equivalentes se o resultado 
de suas tabelas verdade forem iguais, portanto as colunas com os valores 
lógicos de P(p, q, ...) e Q(p, q, ...) são iguais. Desta forma, podemos trocar 
uma proposição P(p, q, ...) por qualquer outra que lhe seja equivalente 
(LIPSCHUTZ, 1991; ALENCAR FILHO, 1980).
Para a representação de equivalência lógica utiliza-se o símbolo ⇔. 
= ou ≡, assim P(p, q, ...) ≡ Q(p, q, ...), P(p, q, ...) = Q(p, q, ...) ou P(p, q, 
...) ⇔ Q(p, q, ...) são equivalentes.
A equivalência é validada quando, ao aplicar o operador lógico bicon-
dicional entre as proposições, o resultado é uma tautologia.
 Importante
Não confundir o símbolo da equivalência ⇔ com o operador lógico ↔, 
eles representam condições diferentes e podem ser encontrados errone-
amente na literatura como apresentando o mesmo significado.
5.2 Propriedades
As equivalências lógicas apresentam as mesmas propriedades das 
implicações lógica, reflexiva, simétrica e transitiva, a saber (ALENCAR 
FILHO, 2003; MENDELSON, 1997):
 2 Reflexiva: P (p, q, ...) ⇔ P (p, q, ...)
 2 P ⇔ P
 2 Simétrica: P (p, q, ...) ⇔ Q (p, q, ...) então Q (p, q, ...) ⇔ P (p, q, ...)
 2 P ⇔ Q
– 69 –
Equivalências lógicas
 2 Q ⇔ P
 2 Transitiva: P (p, q, ...) ⇔ Q (p, q, ...) e Q (p, q, ...) ⇔ R (p, q, ...)
Então P (p, q, ...) ⇔ R (p, q, ...)
 2 P ⇔ Q
 2 Q ⇔ R
 2 P ⇔ R
5.3 Equivalências notáveis
Algumas equivalências lógicas são consideradas notáveis, apare-
cendo com frequência nas demonstrações e cálculos em lógica matemá-
tica, podendo ser substituídos ou substituir para formular hipóteses.
Vamos apresentar e demonstrar as equivalências notáveis utili-
zando tabelas verdade; as equivalências são válidas para quaisquer pro-
posições, sejam elas simples ou compostas (ALENCAR FILHO, 2003; 
 MENDELSON, 1997).
5.3.1 Identidade
p ∧ t ⇔ p: qualquer proposição conjunção a uma tautologia resulta 
sempre na própria proposição.
p T p ∧ t ↔ p
V V V V V V V
F V F F V V F
p ∧ c ⇔ c: qualquer proposição conjunção a uma contradição sempre 
resulta em uma contradição.
p c p ∧ c ↔ c
V F V F F V F
F F F F F V F
Fundamentos de Matemática para Informática
– 70 –
p ∨ t ⇔ t: a disjunção de uma proposição com uma tautologia resulta 
sempre em uma tautologia.
p t p ∨ t ↔ t
V V V V V V V
F V F V V V V
p ∨ c ⇔ p: a disjunção de uma proposição com uma contradição 
resulta sempre na própria proposição.
p c p ∨ c ↔ p
V F V V F V V
F F F F F V F
5.3.2 Regra de Clavius
~p → p ⇔ p: a negação de uma proposição condicional a ela mesma 
resulta sempre na própria proposição.
p ~ p → p ↔ p
V F V V V V V
F V F F F V F
5.3.3 Idempotência
p ⇔ p ∧ p: uma proposição sempre equivale à conjunção com ela mesma.
p p ↔ p ∧ p
V V V V V V
F F V F F F
p ⇔ p ∨ p: uma proposição sempre equivale à disjunção com ela mesma.
p p ↔ p ∨ p
V V V V V V
F F V F F F
– 71 –
Equivalências lógicas
5.3.4 Dupla negação
p ⇔ ~~p: uma proposição equivale à negação da sua negação.
p ↔ ~ ~ p
V V V F V
F V F F F
5.3.5 Comutativa
p ∧ q ⇔ q ∧ p: a conjunção de duas proposições p e q equivalem à 
conjunção de q e p. Desta forma, a ordem da conjunção das proposições 
não altera o resultado.p q p ∧ q ↔ q ∧ p
V V V V V V V V V
V F V F F V F F V
F V F F V V V F F
F F F F F V F F F
p ∨ q ⇔ q ∨ p: a disjunção de duas proposições p e q equivale à 
disjunção de q e p. Desta forma, a ordem da disjunção das proposições 
não altera o resultado.
p q p ∨ q ↔ q ∨ p
V V V V V V V V V
V F V V F V F V V
F V F V V V V V F
F F F F F V F F F
5.3.6 Leis de Morgan
~(p ∧ q) ⇔ ~p ∨ ~q: a negação da conjunção de duas proposições p 
e q equivale àdisjunção da negação individual das proposições p, q.
Fundamentos de Matemática para Informática
– 72 –
p q ~ (p ∧ q ) ↔ ~ q ∨ ~ p
V V F V V V V F V F F V
V F V V F F V V F V F V
F V V F F V V F V V V F
F F V F F F V V F V V F
~ (p ∨ q) ⇔ ~p ∧ ~q: a negação da disjunção de duas proposições p 
e q equivale à conjunção da negação individual das proposições p, q.
p q ~ (p ∨ q ) ↔ ~ q ∧ ~ p
V V F V V V V F V F F V
V F F V V F V V F F F V
F V F F V V V F V F V F
F F V F F F V V F V V F
5.3.7 Associativa
(p ∧q) ∧r ⇔ p ∧(q ∧r): a partir da conjunção de 3 proposições quais-
quer p, q e r, executar primeiro a conjunção (p e q) e aplicar o resultado a 
r equivale à execução de (q e r) primeiro e aplicar o resultado a p.
p Q r (p ∧ q) ∧ r ↔ p ∧ (q ∧ r)
V V V V V V V V V V V V V V
V V F V V V F F V V V V F F
V F V V F F F V V V F F F V
V F F V F F F F V V F F F F
F V V F F V F V V F F V F V
F V F F F V F F V F F V F F
F F V F F F F V V F F F F V
F F F F F F F F V F F F F F
– 73 –
Equivalências lógicas
(p ∨ q) ∨ r ⇔ p ∨ (q ∨ r): a partir da disjunção de 3 proposições quais-
quer p, q e r, executar primeiro a disjunção (p ou q) e aplicar o resultado a 
r equivale à execução de (q ou r) primeiro e aplicar o resultado a p.
p q r (p ∨ q) ∨ r ↔ p ∨ (q ∨ r)
V V V V V V V V V V V V V V
V V F V V V V F V V V V V F
V F V V V F V V V V V F V V
V F F V V F V F V V V F F F
F V V F V V V V V F V V V V
F V F F V V V F V F V V V F
F F V F F F V V V F V F V V
F F F F F F F F V F F F F F
5.3.8 Distributiva
p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r): sendo a proposição composta p ∧ (q ∨ 
r), podemos distribuí-la da seguinte forma: (p ∧ q) disjunção (p ∧ r), sendo 
o resultado destas últimas é equivalente.
p q r p ∧ (q ∨ r) ↔ (p ∧ q) ∨ (p ∧ r)
V V V V V V V V V V V V V V F V
V V F V V V V F V V V V V V F F
V F V V V F V V V V F F V V V V
V F F V F F F F V V F F F V F F
F V V F F V V V V F F V F F F V
F V F F F V V F V F F V F F F F
F F V F F F V V V F F F F F F V
F F F F F F F F V F F F F F F F
p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r): sendo a proposição composta p ∨ (q 
∧ r), podemos distribuí-las da seguinte forma: ( p ∨ q) conjunção (p ∨ r), 
sendo o resultado destas equivalente.
Fundamentos de Matemática para Informática
– 74 –
p q r p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p ∨ r)
V V V V V V V V V V V V V V V V
V V F V V V F F V V V V V V V F
V F V V V F F V V V V F V V V V
V F F V V F F F V V V F V V V F
F V V F V V V V V F V V V F V V
F V F F F V F F V F V V F F F F
F F V F F F F V V F F F F F V V
F F F F F F F F V F F F F F F F
5.3.9 Absorção
p ∧ ( p ∨ q) ⇔ p: uma proposição composta p ∧ (p ∨ q) é equivalente 
à própria proposição.
p q p ∧ (p ∨ q) ↔ p
V V V V V V V V V
V F V V V V F V V
F V F F F V V F F
F F F F F F F F F
p ∨ (p ∧ q) ⇔ p: uma proposição composta p ∨ (p ∧ q) é equivalente 
à própria proposição.
 p q p ∨ (p ∧ q) ↔ p
V V V V V V V V V
V F V V V F F V V
F V F F F F V F F
F F F F F F F F F
5.3.10 Contradição
~p ∧ p ⇔ c: a conjunção de uma proposição com a negação dela 
mesma é uma contradição.
– 75 –
Equivalências lógicas
p ~ p ∧ p ↔ c
V F V F V V F
F V F F F V F
5.3.11 Tautologia
~p ∨ p ⇔ t: a negação de uma proposição disjunção dela mesma é 
uma tautologia.
p ~ p ∨ p ↔ t
V F V V V V V
F V F V F V V
5.3.12 Equivalências notáveis 
associadas à condicional
Proposições condicionais têm três condicionais associadas – recí-
proca, contrária e contrapositiva (MENDELSON, 1997).
Recíproca de: p > q é q > p.
Contrária ou inversa de: p > q é ~p > ~q.
Contrapositiva de: p → q é ~q > ~p.
Que apresentam as seguintes propriedades:
 2 A condicional p→ q e a contrapositiva ~ q→ ~ p são equivalentes.
 2 A recíproca q→ p e a inversa ~ p → ~ q são equivalentes.
Temos também as seguintes equivalências lógicas associadas à 
condicional:
p → q ⇔ ~p ∨ q: uma proposição p condicional q equivale à negação 
de p disjunção q.
p q p → q ↔ ~ p ∨ q
V V V V V V F V V V
Fundamentos de Matemática para Informática
– 76 –
p q p → q ↔ ~ p ∨ q
V F V F F V F V F F
F V F V V V V F V V
F F F V F V V V V F
~(p → q) ⇔ p ∧ ~q: a negação de uma condicional de p e q equivale 
a p conjunção à negação de q.
p q ~ (p → q) ↔ p ∧ ~ q
V V F V V V V V F F V
V F V V F F V V V V F
F V F F V V V F F F V
F F F F V F V F F V F
5.3.13 Equivalência contrária
A equivalência contrária corresponde:
p → q ⇔ ~q → ~p: p condicional q equivale à negação de q, condi-
cional ànegação de p.
p q p → q ↔ ~ q → ~ p
V V V V V V F V V F V
V F V F F V V F F F V
F V F V V V F V V V F
F F F V F V V F V V F
5.3.14 Equivalência contrapositiva
A equivalência contrapositiva satisfaz:
p → q ⇔ ~q → ~p: a condicional entre p e q equivale a:
p q p → q ↔ ~ q → ~ p
V V V V V V F V V F V
– 77 –
Equivalências lógicas
p q p → q ↔ ~ q → ~ p
V F V F F V V F F F V
F V F V V V F V V V F
F F F V F V V F V V F
5.3.15 Equivalências notáveis associadas à bicondicional
Vamos ver agora algumas equivalências lógicas associadas à bicondi-
cional (LIPSCHUTZ, 1991; MENDELSON, 1997).
p ↔ q ⇔ (p → q) ∧ (q → p): a proposição p bicondicional q equivale 
à conjunção de p condicional q ( p → q) e à condicional de (q → p).
p q p ↔ q ↔ (p → q) ∧ (q → p)
V V V V V V V V V V V V V
V F V F F V V F F F F V V
F V F F V V F V V F V F F
F F F V F V F V F V F V F
p ↔ q ⇔ ( p ∧ q) ∨ ( ~p ∧ ~q): a proposição p bicondicional q tam-
bém equivale à disjunção entre p conjunção q ( p ∧ q) e a negação de p, 
conjunção com a negação de q ( -p ∧ -q).
p q p ↔ q ↔ (p ∧ q) ∨ (~ p ∧ ~ q)
V V V V V V V V V V F V F F V
V F V F F V V F F F F V F V F
F V F F V V F F V F V F F F V
F F F V F V F F F V V F V V F
~( p ↔ q ) ⇔ ( p ∧ ~q) ∨ ( ~p ∧ q): a negação da bicondicional entre 
p e q equivale a p conjunção com a negação de q ( p ∧ ~q), disjunção da 
negação de p conjunção q ( ~p ∧ q).
p q ~ p ↔ q ↔ (p ∧ ~ q) ∨ (~ p ∧ q)
V V F V F V V V F F V F F V F V
Fundamentos de Matemática para Informática
– 78 –
p q ~ p ↔ q ↔ (p ∧ ~ q) ∨ (~ p ∧ q)
V F F V V F V V V V F V F V F F
F V V F V V V F F F V V V F V V
F F V F V F V F F V F V V F F F
5.3.16 Exportação/importação
p ∧ q → r ⇔ p → ( q → r): a regra de exportação/importação, em que a 
conjunção de p e q condicional a r equivale a p condicional, q condicional r):
p q r p ∧ q → r ↔ p → (q → r)
V V V V V V V V V V V V V V
V V F V V V F F V V F V F F
V F V V F F V V V V V F V V
V F F V F F V F V V V F V F
F V V F F V V V V F V V V V
F V F F F V V F V F V V F F
F F V F F F V V V F V F V V
F F F F F F V F V F V F V F
5.3.17 Método de demonstração por absurdo
E, para finalizar a apresentação das equivalências notáveis, temos:
(p ∧~ q → c) ⇔ (p → q): a conjunção de p com a negação de q, con-
dicional a uma contradição, equivale a p condicional q).
p q (p ∧ ~ q → c ↔ (p → q)
V V V F F V V F V V V V
V F V V V F F F V V F F
F V F F F V V F V F V V
F F F F V F V F V F V F
– 79 –
Equivalências lógicas
5.4 Método dedutivo
Até agora apresentamos a forma de demonstração utilizando tabelas 
verdade. Este é um método simples e muito útil, mas quando existe um 
número grande de proposições ou proposições muito complexas, a tabela 
verdade fica extensa, difícil, além de não gerar nenhum conhecimento novo.
O método dedutivo é um processo cujas conclusões encontradas 
estão nas premissas analisadas, e utiliza o raciocínio lógico e a dedução. 
Para encontrar esse resultado, o argumento é feito do maior para o menor, 
ou seja, de uma premissa geral em direção a outra – particular ou singular.
É possível trabalhar as proposições utilizando hipóteses da 
seguinte forma:
 2 substituir as proposições por equivalentes até chegara uma 
tautologia;
 2 substituir a primeira premissa por equivalentes até chegar à 
segunda premissa;
 2 substituir a segunda premissa por equivalentes até chegar à pri-
meira premissa.
Caso o resultado, utilizando o método dedutivo, seja uma contradição 
(C) ao invés de uma tautologia (T), a proposição não é válida.
Exemplo 1
Demonstrar a simplificação pelo método dedutivo:
p ∧ q => p
p ∧ q => p Substituindo pelas equivalências até chegar a uma tautologia, tem-se:
⇔ ~ (p ∧ q) ∨ p
⇔ (~p ∨ ~q) ∨ p
⇔ (p ∨ p) ∨ ~q
⇔ T ∨ ~q
⇔ T
Fundamentos de Matemática para Informática
– 80 –
Exemplo 2
Demonstrar a adição pelo método dedutivo:
p => p ∨ q
p => p ∨ q Substituindo pelas equivalências até chegar a uma tautologia, tem-se:
⇔ ~p ∨ (p ∨ q)
⇔ (~p ∨ p) ∨ q
⇔ T ∨ q
⇔ T
Exemplo 3
Demonstrar a seguinte implicação lógica pelo método dedutivo:
p → q => p ∧ r → q
p → q => p ∧ r → q Substituindo pelas equivalências até chegar a uma tautologia, tem-se:
⇔ (p → q) => (p ∧ r → q)
⇔ ~ (~p ∨ q) ∨ (~ (p ∧ r) ∨ q)
⇔ (~~p ∧ ~q) ∨ ((~ p ∨ ~r) ∨ q)
⇔ ~ (p ∧~q) ∨ ((~p ∨ q) ∨ ~r)
⇔ (p ∧~q) ∨ ~ (p ∧ ~q)) ∨ ~r
⇔ T ∨ ~r
⇔ T 
Exemplo 4
Demonstrar a proposição pelo método dedutivo:
(p → q) ∧ (p → ~q) ⇔ ~p
– 81 –
Equivalências lógicas
(p → q) ∧ (p → ~q)
Substituindo a primeira premissa 
pelas equivalências lógicas até chegar 
à segunda premissa, tem-se:
⇔ (~p ∨ q) ∧ (~p ∨ ~q)
⇔ ~p ∨ (q ∧~q)
⇔ ~p ∨ C
⇔ ~p
Exemplo 5
Demonstrar a implicação lógica pelo método dedutivo:
p => ~p → q
p => ~p → q Substituindo pelas equivalências até chegar a uma tautologia, tem-se:
⇔ ~p ∨ (~p → q)
⇔ ~p ∨ (~~p ∨ q)
⇔ ~p ∨ (p ∨ q)
⇔ ~ (p ∨ p) ∨ q)
⇔ T ∨ q
⇔ T
5.5 Redução no número de conectivos
A redução de conectivos é bastante utilizada em arquitetura de com-
putadores e circuitos lógicos.
5.5.1 Conectivos de Scheffer
Devido à ocorrência frequente de determinadas operações no cálculo 
proposicional, foram criados dois operadores derivados, denominados de 
conectivos de Scheffer.
Fundamentos de Matemática para Informática
– 82 –
O conectivo ↑, negação conjunta (não p e não q) representa: conjun-
ção da negação entre as proposições, ou seja, p ↑ q ⇔ ~p ∧ ~q, demons-
trada pela tabela verdade a seguir (DAGHLIAN, 1997; IOAN, 2002):
p q p ↑ q
V V F
V F F
F V F
F F V
O conectivo ↓, negação disjunta (não p ou não q) representa: conjun-
ção da negação entre as proposições, ou seja, p ↓ q ⇔ ~p ∨ ~q, demons-
trada pela tabela verdade a seguir:
p q p ↓ q
V V F
V F V
F V V
F F V
Segundo Alencar Filho (2003), podemos reduzir os conectivos fun-
damentais em pares de conectivos, sem alterar a linguagem da lógica.
 2 ~ e ∨ (negação e disjunção);
 2 ~ e ∧ (negação e conjunção);
 2 ~ e → (negação e condicional).
Conjunção (∧), condicional (→) e bicondicional (↔) podem ser 
representadas por negação (~) e disjunção (∨):
Exemplo 1
p ∧ q ⇔ ~~p ∧ ~~q
⇔ ~(~p ∨ ~q)
Exemplo 2
p → q ⇔ ~p ∨ q
– 83 –
Equivalências lógicas
Exemplo 3
p ↔ q ⇔ (p → q) ∧ (q → p)
⇔ ~(~(~p ∨ q ) ∨ ~(~q ∨ p))
Disjunção (∨), condicional (→) e bicondicional (↔) podem ser repre-
sentadas por negação (~) e conjunção (∧):
Exemplo 1
p ∨ q ⇔ ~~p ∨ ~~q
⇔ ~(~p ∧ ~q)
Exemplo 2
p → q ⇔ ~p ∨ q
⇔ ~( p∧ ~q)
Exemplo 3
p ↔ q ⇔ (p → q) ∧ (q → p)
⇔ ~(p ∧ ~q ) ∧ ~(~p ∧q)
Conjunção (∧), disjunção (∨) e bicondicional (↔) podem ser repre-
sentadas por negação (~) e condicional (→):
Exemplo 1
p ∧ q ⇔ ~(~p ∨ ~q)
⇔ ~(p → ~q)
Exemplo 2
p ∨ q ⇔ ~~p ∨ q
⇔ ~ p → q
Exemplo 3
p ↔ q ⇔ (p → q) ∧ (q → p)
Fundamentos de Matemática para Informática
– 84 –
⇔ (p → q ) ∧ (q → p)
⇔ ((p → q) ∧ ~(q → p))
 Importante
Segundo Lipschutz (1991) e Mendelson (1997):
Os conectivos disjunção (∨) e condicional (→) não são representados 
por negação (~) e bicondicional (↔).
O conectivo disjunção (∨) pode ser representado unicamente pela equi-
valência: p ∨ q ⇔ (p → q) → q. Todos os conectivos podem ser represen-
tados por ↑ e ↓.
5.6 Forma normal das proposições
Segundo Mendelson [8], uma proposição está na forma normal (FN) 
se é formada apenas pelos conectivos: ~, ∧ e ∨. Isso acontece pela elimi-
nação de conectivos → e ↔ (caso existam nas proposições), substituindo 
pelas proposições equivalentes que apresentem somente: ~, ∧ e ∨.
5.6.1 Forma normal conjuntiva (FNC)
Uma proposição está na forma normal conjuntiva quando atende às 
seguintes condições (ALENCAR FILHO, 2003):
 2 contém somente os conectivos ~, ∨ e ∧;
 2 não aparece a dupla negação, portanto ~ não aparece repetido 
~~ e não tem alcance sobre ∧ e V, incidindo diretamente sobre 
letras proposicionais;
 2 a disjunção (∨) não tem alcance sobre a conjunção (∧), desta 
forma não há componentes tais como p ∨ (p ∧ r));
Alencar Filho (2003) apresenta as seguintes transformações para 
determinar a FNC:
– 85 –
Equivalências lógicas
 2 Eliminando os conectivos → e ↔ pela substituição de:
p → q por ~p ∨ q
p ↔ q por (~p ∨ q) ∧ (p ∨ ~q)
 2 Eliminando as negações repetidas e parênteses precedidos de ~ 
pela regra de Morgan;
 2 Substituindo p ∨ (q ∧ r) e (p ∧ q) ∨ r por suas respectivas equi-
valentes, (p ∨ q) ∧ (p ∨ r) e (p ∨ r) ∧ (q ∨ r).
5.6.2 Forma normal disjuntiva (FND)
Uma proposição está na forma normal conjuntiva quando atende às 
seguintes condições (ALENCAR FILHO, 2003; MENDELSON, 1997):
 2 contém somente os conectivos ~, ∨ e ∧;
 2 não aparece a dupla negação, portanto ~ não se repete ~~ e 
a negação não tem alcance sobre ∧ e ∨, incidindo diretamente 
sobre letras proposicionais;
 2 a conjunção (∧) não tem alcance sobre a disjunção (∨), desta 
forma não há componentes tais como p ∧ (p ∨ r));
Alencar Filho (2003) apresenta as seguintes transformações para 
determinar a FND:
 2 Eliminando os conectivos → e ↔ pela substituição de:
p → q por ~p ∨ q
p ↔ q por (~p ∨ q) ∧ (p ∨ ~q)
 2 Eliminando as negações repetidas e parênteses precedidos de ~ 
pela regra de Morgan;
 2 Substituindo p ∧ (q ∨ r) e (p ∨ q) ∧ r por suas respectivas equi-
valentes, (p ∧ q) ∨ (p ∧ r) e (p ∧ r) ∨ (q ∧ r).
5.6.3 Princípio da dualidade
Considerando uma proposição P em sua forma normal (FN), a dual 
de P é a proposição obtida trocando-se cada símbolo ∧ por ∨ e ∨ por ∨ 
(ALENCAR FILHO, 2003; MENDELSON, 1997; LIPSCHUTZ, 1991).
Fundamentos de Matemática para Informática
– 86 –
Por exemplo: a dual de (p ∧ q) ∨ r é (p ∨ q) ∧ r.
Se P e Q são proposições equivalentes em FN, então suas respectivas 
duais PD e QD também são.
Pelo princípio da dualidade, a proposição p ∧ (p ∨ q) ⇔ p é equiva-
lente a p ∨ (p ∧ q) ⇔ p, da mesma forma (p ∧ ~p) ∨ q ⇔ q é equivalente 
a (p ∨ ~p) ∧ q ⇔ q.
Atividades
1. Utilizando o método dedutivo, demonstre as implicações lógicas 
a seguir:
a) p ∧ q => p ∨ q.
b) Silogismo disjuntivo: (p ∨ q) ~p => q.
c) Modus ponens: (p → q) ∧ p => q.
d) Modus tollens: (p → q) ∧ q => ~p.
2. Utilizando o método dedutivo, demonstre as equivalências lógi-
cas a seguir:
a) p → q ⇔ ((p ↓ p) ↓ q) ↓ ((p ↓ p) ↓ q).
b) p → q ⇔ p ∨ q → q.
c) Redução a absurdo: p → q ⇔ p ∧ ~q → c.
d) Exportação/importação: p ∧ q → r ⇔ p → (q → r).
3. Determine a forma normal conjuntiva para a proposição p ↔ q 
∨ ~r.
4. Determine a forma normal disjuntiva para a proposição ~ (((p ∨ 
q) ∧ ~q) ∨ (q ∧ r)).
5. Simplifique as proposições:
a) ~ (p ∨ q) ∨ (~p ∧q).
b) ~ (~p → ~q).
Neste capítulo, abordaremos a lógica de argumentação, que 
é o ato de concluir algo com base em duas ou mais informações 
conhecidas, analisando a validade dos raciocínios e das inferências.
Ao fim deste capítulo, você será capaz de:
 2 definir argumentos;
 2 conhecer e aplicar regras de inferência;
 2 validar os argumentos;
 2 compreender falácias.
A partir deste capítulo, vamos integrar e utilizar vários con-
ceitos dos capítulos anteriores deste livro.
Argumentos: regras 
de inferência
6
Fundamentos de Matemática para Informática
– 88 –
6.1 Método dedutivo
O método dedutivo teve sua definição a partir do filósofo grego Aristó-
teles. Dedução é uma linguagem por meio da qual certas coisas, sendo supos-
tas, têm por consequência