8401c5c7bdf721b3e5480376db960690708797a3a1ba21c7abb75f96fe8b98f94345cd80df992f1b23d895a04d8462f39b8941adb908df6cdb97383899d809bb

Prévia do material em texto

LÓGICA PARA 
COMPUTAÇÃO
Professora Me. Edvania Gimenes de Oliveira Godoy
GRADUAÇÃO
Unicesumar
C397 CENTRO UNIVERSITÁRIO DE MARINGÁ. Núcleo de Educação a 
Distância; GODOY, Edvania Gimenes de Oliveira.
Lógica para Computação. Edvania Gimenes de Oliveira Godoy. 
Maringá-Pr.: UniCesumar, 2016. Reimpresso em 2021.
 184 p.
“Graduação - EaD”.
1. Lógica. 2. Computação. 3. Matemática. 4. EaD. I. Título.
ISBN 978-85-459-0245-4
CDD - 22 ed. 511.3
CIP - NBR 12899 - AACR/2
Ficha catalográfica elaborada pelo bibliotecário 
João Vivaldo de Souza - CRB-8 - 6828
Impresso por:
Reitor
Wilson de Matos Silva
Vice-Reitor
Wilson de Matos Silva Filho
Pró-Reitor Executivo de EAD
William Victor Kendrick de Matos Silva
Pró-Reitor de Ensino de EAD
Janes Fidélis Tomelin
Presidente da Mantenedora
Cláudio Ferdinandi
NEAD - Núcleo de Educação a Distância
Diretoria Executiva
Chrystiano Minco�
James Prestes
Tiago Stachon 
Diretoria de Graduação e Pós-graduação 
Kátia Coelho
Diretoria de Permanência 
Leonardo Spaine
Diretoria de Design Educacional
Débora Leite
Head de Produção de Conteúdos
Celso Luiz Braga de Souza Filho
Head de Curadoria e Inovação
Tania Cristiane Yoshie Fukushima
Gerência de Produção de Conteúdo
Diogo Ribeiro Garcia
Gerência de Projetos Especiais
Daniel Fuverki Hey
Gerência de Processos Acadêmicos
Taessa Penha Shiraishi Vieira
Gerência de Curadoria
Carolina Abdalla Normann de Freitas
Supervisão de Produção de Conteúdo
Nádila Toledo
Coordenador de Conteúdo
Fabiana de Lima
Designer Educacional
Paulo Victor Souza e Silva
Projeto Gráfico
Jaime de Marchi Junior
José Jhonny Coelho
Arte Capa
Arthur Cantareli Silva
Ilustração Capa
Bruno Pardinho
Editoração
Bruna Marconato
Daniel Fuverki Hey
Qualidade Textual
Hellyery Agda
Keren Pardini
Em um mundo global e dinâmico, nós trabalhamos 
com princípios éticos e profissionalismo, não so-
mente para oferecer uma educação de qualidade, 
mas, acima de tudo, para gerar uma conversão in-
tegral das pessoas ao conhecimento. Baseamo-nos 
em 4 pilares: intelectual, profissional, emocional e 
espiritual.
Iniciamos a Unicesumar em 1990, com dois cursos 
de graduação e 180 alunos. Hoje, temos mais de 
100 mil estudantes espalhados em todo o Brasil: 
nos quatro campi presenciais (Maringá, Curitiba, 
Ponta Grossa e Londrina) e em mais de 300 polos 
EAD no país, com dezenas de cursos de graduação e 
pós-graduação. Produzimos e revisamos 500 livros 
e distribuímos mais de 500 mil exemplares por 
ano. Somos reconhecidos pelo MEC como uma 
instituição de excelência, com IGC 4 em 7 anos 
consecutivos. Estamos entre os 10 maiores grupos 
educacionais do Brasil.
A rapidez do mundo moderno exige dos educa-
dores soluções inteligentes para as necessidades 
de todos. Para continuar relevante, a instituição 
de educação precisa ter pelo menos três virtudes: 
inovação, coragem e compromisso com a quali-
dade. Por isso, desenvolvemos, para os cursos de 
Engenharia, metodologias ativas, as quais visam 
reunir o melhor do ensino presencial e a distância.
Tudo isso para honrarmos a nossa missão que é 
promover a educação de qualidade nas diferentes 
áreas do conhecimento, formando profissionais 
cidadãos que contribuam para o desenvolvimento 
de uma sociedade justa e solidária.
Vamos juntos!
Seja bem-vindo(a), caro(a) acadêmico(a)! Você está 
iniciando um processo de transformação, pois quando 
investimos em nossa formação, seja ela pessoal ou 
profissional, nos transformamos e, consequentemente, 
transformamos também a sociedade na qual estamos 
inseridos. De que forma o fazemos? Criando oportu-
nidades e/ou estabelecendo mudanças capazes de 
alcançar um nível de desenvolvimento compatível com 
os desafios que surgem no mundo contemporâneo. 
O Centro Universitário Cesumar mediante o Núcleo de 
Educação a Distância, o(a) acompanhará durante todo 
este processo, pois conforme Freire (1996): “Os homens 
se educam juntos, na transformação do mundo”.
Os materiais produzidos oferecem linguagem dialógica 
e encontram-se integrados à proposta pedagógica, con-
tribuindo no processo educacional, complementando 
sua formação profissional, desenvolvendo competên-
cias e habilidades, e aplicando conceitos teóricos em 
situação de realidade, de maneira a inseri-lo no mercado 
de trabalho. Ou seja, estes materiais têm como principal 
objetivo “provocar uma aproximação entre você e o 
conteúdo”, desta forma possibilita o desenvolvimento 
da autonomia em busca dos conhecimentos necessá-
rios para a sua formação pessoal e profissional.
Portanto, nossa distância nesse processo de cresci-
mento e construção do conhecimento deve ser apenas 
geográfica. Utilize os diversos recursos pedagógicos 
que o Centro Universitário Cesumar lhe possibilita. 
Ou seja, acesse regularmente o Studeo, que é o seu 
Ambiente Virtual de Aprendizagem, interaja nos fóruns 
e enquetes, assista às aulas ao vivo e participe das dis-
cussões. Além disso, lembre-se que existe uma equipe 
de professores e tutores que se encontra disponível para 
sanar suas dúvidas e auxiliá-lo(a) em seu processo de 
aprendizagem, possibilitando-lhe trilhar com tranqui-
lidade e segurança sua trajetória acadêmica.
Professora Me. Edvania Gimenes de Oliveira Godoy
Possui mestrado em Matemática pela Universidade Estadual de Maringá 
(2001). Atualmente é professora assistente da Fundação Faculdade de 
Filosofia Ciências e Letras de Mandaguari.
A
U
TO
R
A
SEJA BEM-VINDO(A)!
APRESENTAÇÃO
LÓGICA PARA COMPUTAÇÃOAPRESENTAÇÃO
LÓGICA PARA COMPUTAÇÃO
Prezados acadêmicos, é com satisfação que apresento a vocês o livro para a disciplina Lógica
para Computação. Esta disciplina está baseada no que chamamos de Matemática Discreta,
que é uma parte da Matemática que trata de situações em que as estruturas matemáticas são
baseadas em conjuntos contáveis, finitos ou infinitos. Dessa forma, os conteúdos abordados na
Matemática Discreta aplicam-se perfeitamente ao ambiente computacional, visto que a maioria
dos conceitos computacionais pertencem ao domı́nio discreto.
Os objetivos principais da disciplina são desenvolver o racioćınio lógico-matemático e oferecer
instrumentos para que vocês desenvolvam um vocabulário preciso, com recursos para notação
matemática e abstrações. Assim, será posśıvel aplicar os conceitos de Matemática discreta
como uma ferramenta para investigações e aplicações na área de Computação.
Este livro está dividido em cinco unidades. A primeira trata de noções de Lógica Matemática,
que é básica para qualquer estudo em computação e informática. O principal objetivo dessa
unidade será introduzir, resumidamente, os principais conceitos e a terminologia de lógica
matemática. Veremos como utilizar a notação simbólica para as lógicas proposicional e de
predicados para simbolizar argumentos, bem como determinar sua validade por meio das re-
gras de inferência.
A segunda unidade é dedicada ao estudo da Teoria dos Conjuntos. O conceito de conjunto é
fundamental, pois praticamente todos os conceitos desenvolvidos em computação são baseados
em conjuntos ou construções sobre conjuntos. Com as noções primitivas de conjunto e per-
tinência, que são aceitas sem definição, iniciaremos o estudo de conjuntos definindo elementos,
subconjuntos e tipos de conjuntos, bem como suas representações por descrição, propriedade
ou diagrama. Em seguida, estudaremos as operações sobre conjuntos, que são agrupadas em
não reverśıveis (união e interseção) e reverśıveis (complemento, conjunto das partes e produto
cartesiano). Será estabelecida também a relação entre álgebra de conjuntos e lógica.
As unidades III e IV são dedicadas ao estudo de relações e funções, respectivamente. Relações
são muito usadas em todas as áreas teóricas e práticas da computação. Além do conceito formal
de relação, diversos conceitos correlatos serão estudados: relação dual, composição de relações
e tiposde relações. Veremos como representar relações por meio de diagramas, matrizes ou
grafos, e para o caso de uma ordem parcial de tarefas relacionadas por pré-requisitos, discu-
tiremos sobre a representação em diagrama PERT.
1
APRESENTAÇÃO
LÓGICA PARA COMPUTAÇÃO
Prezados acadêmicos, é com satisfação que apresento a vocês o livro para a disciplina Lógica
para Computação. Esta disciplina está baseada no que chamamos de Matemática Discreta,
que é uma parte da Matemática que trata de situações em que as estruturas matemáticas são
baseadas em conjuntos contáveis, finitos ou infinitos. Dessa forma, os conteúdos abordados na
Matemática Discreta aplicam-se perfeitamente ao ambiente computacional, visto que a maioria
dos conceitos computacionais pertencem ao domı́nio discreto.
Os objetivos principais da disciplina são desenvolver o racioćınio lógico-matemático e oferecer
instrumentos para que vocês desenvolvam um vocabulário preciso, com recursos para notação
matemática e abstrações. Assim, será posśıvel aplicar os conceitos de Matemática discreta
como uma ferramenta para investigações e aplicações na área de Computação.
Este livro está dividido em cinco unidades. A primeira trata de noções de Lógica Matemática,
que é básica para qualquer estudo em computação e informática. O principal objetivo dessa
unidade será introduzir, resumidamente, os principais conceitos e a terminologia de lógica
matemática. Veremos como utilizar a notação simbólica para as lógicas proposicional e de
predicados para simbolizar argumentos, bem como determinar sua validade por meio das re-
gras de inferência.
A segunda unidade é dedicada ao estudo da Teoria dos Conjuntos. O conceito de conjunto é
fundamental, pois praticamente todos os conceitos desenvolvidos em computação são baseados
em conjuntos ou construções sobre conjuntos. Com as noções primitivas de conjunto e per-
tinência, que são aceitas sem definição, iniciaremos o estudo de conjuntos definindo elementos,
subconjuntos e tipos de conjuntos, bem como suas representações por descrição, propriedade
ou diagrama. Em seguida, estudaremos as operações sobre conjuntos, que são agrupadas em
não reverśıveis (união e interseção) e reverśıveis (complemento, conjunto das partes e produto
cartesiano). Será estabelecida também a relação entre álgebra de conjuntos e lógica.
As unidades III e IV são dedicadas ao estudo de relações e funções, respectivamente. Relações
são muito usadas em todas as áreas teóricas e práticas da computação. Além do conceito formal
de relação, diversos conceitos correlatos serão estudados: relação dual, composição de relações
e tipos de relações. Veremos como representar relações por meio de diagramas, matrizes ou
grafos, e para o caso de uma ordem parcial de tarefas relacionadas por pré-requisitos, discu-
tiremos sobre a representação em diagrama PERT.
1
Uma função é um caso particular de relação binária e, assim como as relações, descreve 
diversas situações reais. Abordaremos o conceito de função, destacando seu domı́nio, imagem e 
repre-sentação gráfica, bem como as propriedades de funções e as definições de funções 
compostas e inversas.
Por fim, na unidade V, faremos uma retomada das unidades anteriores apresentando 
aplicações na área de Computação. Sobre lógica proposicional e teoria dos conjuntos, veremos 
aplicações em linguagens de programação conhecidas como procedurais (no caso, linguagem 
Pascal). Sobre lógica de predicados, apresentaremos uma linguagem de programação 
conhecida como declar-ativa (Prolog), em que os programas reúnem uma série de dados e 
regras e as usam para gerar conclusões. O item Relações será retomado no estudo de caminho 
cŕıtico em um diagrama Pert, para determinar o tempo mı́nimo de conclusão de uma 
sequência de atividades ordenadas em uma tarefa a ser realizada. Também em bancos de 
dados relacional, que é um banco de dados cujos dados são conjuntos (representados como 
tabelas) que são relacionados com outros conjuntos (tabelas), veremos a aplicação dos 
conceitos de conjuntos e relações. E, finalmente, será destacada a aplicação dos conceitos de 
relações e funções em autômatos finitos.
Gostaria de destacar que não pretendemos realizar estudo detalhado de conceitos espećıficos 
de computação, mas apenas dar uma noção sobre a forte relação entre a matemática estudada 
com outras disciplinas do curso.
Em cada unidade, são propostas atividades sobre o conteúdo estudado. A realização dessas 
atividades é muito importante para a fixação dos conceitos e verificação de aprendizagem.
Desejo a todos um bom estudo!
2
APRESENTAÇÃO
SUMÁRIO
09
UNIDADE I
LÓGICA MATEMÁTICA
15 Introdução 
16 Lógica Proposicional 
16 Proposições e Valores Lógicos 
17 Conectivos Lógicos 
25 Tabela-Verdade 
26 Tautologias e Contradições 
28 Equivalências Lógicas 
31 Implicações Lógicas 
32 Método Dedutivo 
35 Quantificadores e Predicados 
38 Negação de Sentenças Quantificadas 
39 Considerações Finais 
SUMÁRIO
UNIDADE II
TEORIA DOS CONJUNTOS
47 Introdução
47 Conceitos Primitivos 
48 Descricão de Conjuntos 
50 Igualdade de Conjuntos 
50 Tipos de Conjuntos 
51 Subconjuntos 
53 Conjunto das Partes 
54 Diagramas de Venn-Euler 
58 Produto Cartesiano 
59 Relação Entre Lógica e Álgebra dos Conjuntos 
60 Princípio da Inclusão e Exclusão 
64 Considerações Finais 
UNIDADE III
RELAÇÕES
73 Introdução
73 Relação Binária 
76 Tipos de Relações Binárias 
77 Propriedades das Relações 
78 Representação das Relações 
SUMÁRIO
11
82 Relação de Ordem 
85 Diagrama de Hasse 
87 Diagrama PERT 
89 Relações Duais 
89 Composição de Relações 
91 Consideração Finais 
UNIDADE IV
FUNÇÕES
101 Introdução
101 Funções 
103 Domínio, Contradomínio e Imagem de uma Função 
105 Igualdade de Funções 
105 Gráfico de Funções 
108 Função Piso e Função Teto 
109 Propriedades de Funções 
112 Função Composta 
114 Funções Inversas 
115 Técnicas para Obtenção da Inversa de uma Função 
117 Considerações Finais 
SUMÁRIO
UNIDADE V
APLICAÇÕES À COMPUTAÇÃO
125 Introdução
125 Álgebra dos Conjuntos nas Linguagens de Programação 
132 PROLOG 
139 Caminho Crítico no Diagrama PERT 
144 Autômatos Finitos 
150 Relações e Banco de Dados 
159 Considerações Finais 
165 CONCLUSÃO
167 REFERÊNCIAS 
169 GABARITO
U
N
ID
A
D
E I
Professora Me. Edvania Gimenes de Oliveira Godoy
LÓGICA MATEMÁTICA
Objetivos de Aprendizagem
 ■ Desenvolver o raciocínio lógico matemático.
 ■ Usar os símbolos formais da lógica proposicional.
 ■ Encontrar o valor-verdade de expressões em lógica proposicional.
 ■ Reconhecer tautologias e contradições.
 ■ Usar a lógica proposicional para provar a validade de um argumento 
na língua portuguesa.
 ■ Identificar/reconhecer símbolos quantificados.
 ■ Determinar o valor-verdade de uma proposição predicativa em uma 
dada interpretação.
 ■ Representar sentenças da língua portuguesa usando a lógica de 
predicativos.
 ■ Determinar a negação de sentenças quantificadas.
Plano de Estudo
A seguir, apresentam-se os tópicos que você estudará nesta unidade:
 ■ Lógica Proposicional.
 ■ Conectivos Lógicos
 ■ Tabelas- Verdade
 ■ Tautologias e Contradições
 ■ Equivalências Lógicas
 ■ Implicações Lógicas
 ■ Método Dedutivo
 ■ Quantificadores e Predicados
 ■ Negação de Sentenças Quantificadas
INTRODUÇÃO
Introdução
A lógica formal fornece base para o modo de pensar organizado e cuidadoso que caracteri-
za qualquer atividade racional. Ela é considerada base de todo racioćınio matemático e do
racioćınio automatizado, tendo aplicações diretas em Ciência da Computação, em grau variado
de complexidade. Considera-se que o estudo da Lógica teve ińıcio na Grécia Antiga, sendo
sistematizado por Aristóteles(384a.C.-322a.C.), com a formulação de leis gerais de encadea-
mentos de conceitos e júızos que levariam à descoberta de novas verdades (Lógica Clássica).
Entretanto, os argumentos formulados em linguagem natural como em português, por exemplo,
são muitas vezes de dif́ıcil avaliação, devido a ambiguidades nas frases e construções confusas.
Os matemáticos da atualidade entenderam então que, para uma matéria ser estudada com o
caráter cient́ıfico necessário, era preciso introduzir-se uma linguagem simbólica.
A Lógica Simbólica ou Lógica Matemática utiliza śımbolos de origem matemática para for-
mular os argumentos. Nessa lógica, as várias relações entre proposições são representadas por
fórmulas cujos significados estão livres de ambiguidades tão comuns à linguagem corrente, e
essas fórmulas podem ser “operadas” segundo um conjunto de regras de transformação for-
mal. Outra vantagem de seu uso refere-se à facilidade de entendimento e brevidade para obter
resultados.
O moderno desenvolvimento da Lógica iniciou-se com a obra de George Boole (1815-1864)-
“Álgebra Booleana”- e de Augustus De Morgan (1806-1871), e foi consolidado pelo filósofo
e matemático alemão Gottlob Frege (1848-1895) - “Regras de Demonstração Matemática.”
Como a Lógica Simbólica tem sua própria linguagem técnica, é um instrumento poderoso para
a análise e a dedução dos argumentos, especialmente com o uso do computador. Na computação,
ela é utilizada para representar problemas e para obter suas soluções. O algoritmo, que seria
o conjunto finito de instruções a serem executadas para obter a solução de um problema, é
constrúıdo com base na lógica matemática.
Nessa unidade vamos estudar os principais conceitos e a terminologia da lógica matemática,
que envolve proposições, conectivos, tabelas-verdade e tautologias para chegar a conclusões a
partir de proposições dadas, bem como o estudo dos quantificadores e predicados. Os conteúdos
estudados serão utilizados em disciplinas futuras e fornecerão ferramentas para investigações e
aplicações precisas em sua área de atuação.
2 Introdução
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
15
LÓGICA MATEMÁTICA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
IU N I D A D E16
Lógica Proposicional
Proposições e Valores Lógicos
Proposição é uma sentença declarativa que é verdadeira ou falsa, mas não ambas. Dito de outra
maneira, proposição é toda expressão que encerra um pensamento de sentido completo e pode
ser classificada como V (verdadeira) ou F (falsa).
Exemplos:
1. 17 é um número par.
2. O gato é um mamı́fero.
3. O 136◦ d́ıgito da expansão decimal de
√
11 é 2.
4. Está chovendo agora.
5. Todo quadrado é um retângulo.
6. 100 + 100 = 300
Observamos que todas essas sentenças são proposições, pois: (2) e (5) são verdadeiras e (1)
é falsa; a veracidade ou falsidade de (4) depende do momento em que a proposição é feita; e
apesar de não sabermos o valor do d́ıgito solicitado na afirmação (3), ele será igual a 2 ou não
será 2, ou seja, a sentença será verdadeira ou falsa.
3
Como exemplos de frases que não são proposições, podemos citar:
1. Feliz aniversário!!! (Sentença exclamativa)
2. Onde está a chave? (Sentença interrogativa)
3. Vire à esquerda. (Sentença imperativa)
4. x+y = 6. (sentença aberta; pode ser verdadeira ou falsa dependendo dos valores de x e y)
O valor lógico de uma proposicã̧o se refere a um dos dois posśıveis júızos que atribuiremos
a uma proposição: verdadeiro, denotado por V (ou 1), ou falso, denotado por F (ou 0).
Prinćıpios Básicos das Proposições:
I) Prinćıpio da não contradição: Uma proposição não pode ser verdadeira e falsa simultane-
amente.
II) Prinćıpio do terceiro exclúıdo: Toda proposição ou é verdadeira ou é falsa; não existe
um terceiro valor lógico.
Classificação das Proposições:
As proposições podem ser classificadas em simples e compostas:
Proposições simples: aquelas que vêm sozinhas, desacompanhadas de outras proposições.
Exemplos:
* A impressora está ligada.
* O novo papa é argentino.
Proposições compostas: aquelas formadas pela combinação de proposições simples.
Exemplos:
* João é médico e Pedro é dentista.
* Se fizer sol, então irei ao clube.
Conectivos Lógicos
Proposições simples podem ser combinadas para for-
mar proposições mais complexas: as proposições com-
postas. As palavras ou śımbolos usados para formar
novas proposições a partir de proposições dadas são
chamados de conectivos.
4
Introdução
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
17
©shutterstock
Os conectivos fundamentais da Lógica Matemática são:
Conectivo Śımbolo
1) não; não é verdade que ∼ Negação ou modificador
2) e ∧ Conjunção
3) ou ∨ Disjunção
4) se ... então → Condicional
5) se, e somente se ↔ Bicondicional
Dadas as proposições simples p e q, podemos com o uso de conectivos formar novas proposições
a partir de p e q. Assim temos:
1) A negação de p ∼ p não p
2) A conjunção de p e q p ∧ q p e q
3) A disjunção de p e q p ∨ q p ou q
4) A condicional de p e q p → q se p, então q
5) A bicondicional de p e q p ↔ q p se, e somente se, q
Exemplo:
Dadas as proposições p: 2 é um número par e q: 6 é múltiplo de 3, faça as traduções para
a linguagem corrente para as seguintes proposições:
a) ∼ p 2 não é um número par. (ou: 2 é um número ı́mpar.)
b) ∼ p ∨ q 2 não é par ou 6 é múltiplo de 3.
c) ∼ q → p Se 6 não é múltiplo de 3, então 2 é par.
d) ∼ p ↔ q 2 é ı́mpar se, e somente se, 6 é múltiplo de 3.
e) ∼ (p ∧ ∼ q) Não é verdade que 2 é par e 6 não é um múltiplo de 3.
# SAIBA MAIS #:
Alguns dos conectivos apresentados podem ser denotados por outros śımbolos ou expressões.
Consideremos p, q proposições:
Conectivo lógico Śımbolo
Negação ¬p; p′
Conjunção p.q
Disjunção p+ q
5
Os conectivos fundamentais da Lógica Matemática são:
Conectivo Śımbolo
1) não; não é verdade que ∼ Negação ou modificador
2) e ∧ Conjunção
3) ou ∨ Disjunção
4) se ... então → Condicional
5) se, e somente se ↔ Bicondicional
Dadas as proposições simples p e q, podemos com o uso de conectivos formar novas proposições
a partir de p e q. Assim temos:
1) A negação de p ∼ p não p
2) A conjunção de p e q p ∧ q p e q
3) A disjunção de p e q p ∨ q p ou q
4) A condicional de p e q p → q se p, então q
5) A bicondicional de p e q p ↔ q p se, e somente se, q
Exemplo:
Dadas as proposições p: 2 é um número par e q: 6 é múltiplo de 3, faça as traduções para
a linguagem corrente para as seguintes proposições:
a) ∼ p 2 não é um número par. (ou: 2 é um número ı́mpar.)
b) ∼ p ∨ q 2 não é par ou 6 é múltiplo de 3.
c) ∼ q → p Se 6 não é múltiplo de 3, então 2 é par.
d) ∼ p ↔ q 2 é ı́mpar se, e somente se, 6 é múltiplo de 3.
e) ∼ (p ∧ ∼ q) Não é verdade que 2 é par e 6 não é um múltiplo de 3.
# SAIBA MAIS #:
Alguns dos conectivos apresentados podem ser denotados por outros śımbolos ou expressões.
Consideremos p, q proposições:
Conectivo lógico Śımbolo
Negação ¬p; p′
Conjunção p.q
Disjunção p+ q
5
LÓGICA MATEMÁTICA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
IU N I D A D E18
A linguagem Pascal (assim como a maioria das linguagens de programação) possui os
seguintes conectivos lógicos:
not Negação
and Conjunção
or Disjunção
<= Condicional
= Bicondicional
Fonte: Menezes (2013).
# FIM SAIBA MAIS#
O valor lógico de uma proposição composta (verdadeiro ou falso) depende do valor lógico das
proposições simplesque a compõem e da maneira como elas são combinadas pelos conectivos.
Conhecendo-se os valores lógicos de duas proposições p e q, vamos definir os valores lógicos
das proposições: ∼ p; p ∧ q; p ∨ q; p → q e p ↔ q.
1. Negação (∼)
Dada uma proposição p, a negação de p será indicada por ∼ p (Lê-se ”não p”). O valor
verdade da proposição ∼ p será o oposto do valor verdade de p.
Em resumo:
Negação: se V(p) = V então V(∼ p) = F e se V(p) = F então V(∼ p).
Essas possibilidades para os valores lógicos podem ser colocadas em uma tabela, denomi-
nada tabela-verdade. Uma tabela verdade é uma tabela que contém as proposições nas colunas
e as possibilidades de valores-verdade nas linhas. É comum expressar os resultados de uma
proposição composta por meio de tabelas- verdade, que permitem analisar seus valores-verdade.
Tabela-verdade para a negação de p:
p ∼ p
V F
F V
6
Introdução
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
19
A linguagem Pascal (assim como a maioria das linguagens de programação) possui os
seguintes conectivos lógicos:
not Negação
and Conjunção
or Disjunção
<= Condicional
= Bicondicional
Fonte: Menezes (2013).
# FIM SAIBA MAIS#
O valor lógico de uma proposição composta (verdadeiro ou falso) depende do valor lógico das
proposições simples que a compõem e da maneira como elas são combinadas pelos conectivos.
Conhecendo-se os valores lógicos de duas proposições p e q, vamos definir os valores lógicos
das proposições: ∼ p; p ∧ q; p ∨ q; p → q e p ↔ q.
1. Negação (∼)
Dada uma proposição p, a negação de p será indicada por ∼ p (Lê-se ”não p”). O valor
verdade da proposição ∼ p será o oposto do valor verdade de p.
Em resumo:
Negação: se V(p) = V então V(∼ p) = F e se V(p) = F então V(∼ p).
Essas possibilidades para os valores lógicos podem ser colocadas em uma tabela, denomi-
nada tabela-verdade. Uma tabela verdade é uma tabela que contém as proposições nas colunas
e as possibilidades de valores-verdade nas linhas. É comum expressar os resultados de uma
proposição composta por meio de tabelas- verdade, que permitem analisar seus valores-verdade.
Tabela-verdade para a negação de p:
p ∼ p
V F
F V
6
AlinguagemPascal(assimcomoamaioriadaslinguagensdeprogramação)possuios
seguintesconectivosĺogicos:
notNegação
andConjunção
orDisjunção
<=Condicional
=Bicondicional
Fonte:Menezes(2013).
#FIMSAIBAMAIS#
Ovalorĺogicodeumaproposi̧cãocomposta(verdadeirooufalso)dependedovalorĺogicodas
proposi̧cõessimplesqueacompõemedamaneiracomoelass̃aocombinadaspelosconectivos.
Conhecendo-seosvaloresĺogicosdeduasproposi̧cõespeq,vamosdefinirosvaloresĺogicos
dasproposi̧cões:∼p;p∧q;p∨q;p→qep↔q.
1.Negação(∼)
Dadaumaproposi̧cãop,anegaçãodepseŕaindicadapor∼p(Lê-se”nãop”).Ovalor
verdadedaproposi̧cão∼pseŕaoopostodovalorverdadedep.
Emresumo:
Negação:seV(p)=Vent̃aoV(∼p)=FeseV(p)=Fent̃aoV(∼p).
Essaspossibilidadesparaosvaloresĺogicospodemsercolocadasemumatabela,denomi-
nadatabela-verdade.Umatabelaverdadeéumatabelaquecont́emasproposi̧cõesnascolunas
easpossibilidadesdevalores-verdadenaslinhas.Écomumexpressarosresultadosdeuma
proposi̧cãocompostapormeiodetabelas-verdade,quepermitemanalisarseusvalores-verdade.
Tabela-verdadeparaanegaçãodep:
p∼p
VF
FV
6
A linguagem Pascal (assim como a maioria das linguagens de programação) possui os
seguintes conectivos lógicos:
not Negação
and Conjunção
or Disjunção
<= Condicional
= Bicondicional
Fonte: Menezes (2013).
# FIM SAIBA MAIS#
O valor lógico de uma proposição composta (verdadeiro ou falso) depende do valor lógico das
proposições simples que a compõem e da maneira como elas são combinadas pelos conectivos.
Conhecendo-se os valores lógicos de duas proposições p e q, vamos definir os valores lógicos
das proposições: ∼ p; p ∧ q; p ∨ q; p → q e p ↔ q.
1. Negação (∼)
Dada uma proposição p, a negação de p será indicada por ∼ p (Lê-se ”não p”). O valor
verdade da proposição ∼ p será o oposto do valor verdade de p.
Em resumo:
Negação: se V(p) = V então V(∼ p) = F e se V(p) = F então V(∼ p).
Essas possibilidades para os valores lógicos podem ser colocadas em uma tabela, denomi-
nada tabela-verdade. Uma tabela verdade é uma tabela que contém as proposições nas colunas
e as possibilidades de valores-verdade nas linhas. É comum expressar os resultados de uma
proposição composta por meio de tabelas- verdade, que permitem analisar seus valores-verdade.
Tabela-verdade para a negação de p:
p ∼ p
V F
F V
6
LÓGICA MATEMÁTICA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
IU N I D A D E20
2. Conjunção (∧)
O operador conjunção “∧” representa intuitivamente o papel análogo ao conectivo “e” da
Ĺıngua Portuguesa. Por exemplo, se p: “7 < 0” e q: “11 é ı́mpar”, então p ∧ q é a proposição
“7 < 0 e 11 é ı́mpar”. Neste caso, sabemos que (p ∧ q) é falsa, pois falha a proposição q.
Dadas duas proposições p e q, chama-se “conjunção de p e q” a proposição “p ∧ q” (lê-se p
e q). A conjunção p∧ q será verdadeira quando p e q forem ambas verdadeiras e será falsa nos
outros casos.
Em resumo: V(p ∧ q) = V somente quando V(p) = V(q) = V.
Tabela-verdade para a conjunção p ∧ q
p q p ∧ q
V V V
V F F
F V F
F F F
3) Disjunção (∨)
Dadas duas proposições p e q, chama-se “disjunção de p e q” a proposição “p ∨ q” (lê-se
p ou q). A disjunção p ∨ q será verdadeira se pelo menos uma das proposições (p ou q) for
verdadeira e será falsa apenas no caso em que as duas (p e q) forem falsas.
Em resumo: V(p ∨ q) = F somente quando V(p) = V(q) = F.
Exemplos:
a) Se p: 3 + 4 > 5 e q: 3 + 1 = 2, a composta P(p, q) formada ao usar o conectivo “∨” é
P:p ∨ q, que se lê P: 3 + 4 > 5 ou 3 + 1 = 2.
b) A frase: “O aluno tem celular ou notebook” é uma disjunção de duas proposições simples:
[O aluno tem celular] ∨ [O aluno tem notebook].
O concetivo ∨ também é chamado de “ou inclusivo”, pois ele admite as duas frases ver-
dadeiras. A frase do exemplo acima é verdadeira se o aluno tiver somente celular, somente
notebook, ou celular e notebook.
Em resumo: V(p ∨ q) = F somente quando V(p) = V(q) = F.
7
2. Conjunção (∧)
O operador conjunção “∧” representa intuitivamente o papel análogo ao conectivo “e” da
Ĺıngua Portuguesa. Por exemplo, se p: “7 < 0” e q: “11 é ı́mpar”, então p ∧ q é a proposição
“7 < 0 e 11 é ı́mpar”. Neste caso, sabemos que (p ∧ q) é falsa, pois falha a proposição q.
Dadas duas proposições p e q, chama-se “conjunção de p e q” a proposição “p ∧ q” (lê-se p
e q). A conjunção p∧ q será verdadeira quando p e q forem ambas verdadeiras e será falsa nos
outros casos.
Em resumo: V(p ∧ q) = V somente quando V(p) = V(q) = V.
Tabela-verdade para a conjunção p ∧ q
p q p ∧ q
V V V
V F F
F V F
F F F
3) Disjunção (∨)
Dadas duas proposições p e q, chama-se “disjunção de p e q” a proposição “p ∨ q” (lê-se
p ou q). A disjunção p ∨ q será verdadeira se pelo menos uma das proposições (p ou q) for
verdadeira e será falsa apenas no caso em que as duas (p e q) forem falsas.
Em resumo: V(p ∨ q) = F somente quando V(p) = V(q) = F.
Exemplos:
a) Se p: 3 + 4 > 5 e q: 3 + 1 = 2, a composta P(p, q) formada ao usar o conectivo “∨” é
P:p ∨ q, que se lê P: 3 + 4 > 5 ou 3 + 1 = 2.
b) A frase: “O aluno tem celular ou notebook” é uma disjunção de duas proposições simples:
[O aluno tem celular] ∨ [O aluno tem notebook].
O concetivo ∨ também é chamado de “ou inclusivo”, pois ele admite as duas frases ver-
dadeiras. A frase do exemplo acima é verdadeira se o aluno tiver somente celular, somente
notebook, ou celular e notebook.
Em resumo: V(p ∨ q) = F somente quando V(p) = V(q) = F.
7
Tabela-verdade para a disjunção p ∨ q.
p q p ∨ q
V V V
V F VF V V
F F F
3.1) Disjunção Exclusiva: (∨)
Chama-se disjunção exclusiva de duas proposições p e q a proposição representada por “p ∨
q” ou p⊕q, que se lê: “ou p ou q” ou “p ou q, mas não ambos”, cujo valor lógico é a verdade (V)
somente quando p é verdadeira ou q é verdadeira, mas não quando p e q são ambas verdadeiras,
e a falsidade (F) quando p e q são ambas verdadeiras ou ambas falsas.
Em resumo: V( p∨q ) = F quando V(p) = V(q).
Na disjunção exclusiva, as duas proposições não podem ocorrer ao mesmo tempo.
Exemplos:
a) p: x é par ; q: x é ı́mpar. x pode ser par ou ı́mpar, mas x não pode ser par e ı́mpar ao
mesmo tempo. A composta “p ou q” é simbolizada por P(p, q) = (p∨q).
b) Arnaldo é alagoano ou pernambucano.
c) O documento foi enviado por malote ou pelo correio.
Tabela-verdade da disjunção exclusiva p∨q.
p q p∨q
V V F
V F V
F V V
F F F
4. Condicional (−→)
Sejam p e q proposições. A proposição “se p, então q” , que será denotada por p → q,
é chamada de condicional ou implicação. A proposição p → q assume o valor falso somente
8
Introdução
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
21
quando p for verdadeira e q for falsa.
Resumindo: V(p → q) = F somente quando V(p) = V e V(q) = F.
Ilustremos inicialmente uma interpretação do conectivo → através da sentença:
“Se Ana conseguir o emprego, então fará uma festa.”
Definindo-se:
p: “Ana consegue o emprego” e q: “ Ana faz uma festa”, então (p → q) representa a
promessa de Ana.
Vamos analisar quando a promessa será cumprida:
1) Digamos que ela consiga a vaga de emprego (p é V). Pode acontecer que ela faça a festa
(q é V), cumprindo a promessa (p → q é V). Por outro lado, Ana pode não fazer a festa,
descumprindo a promessa (p → q é F).
2) Digamos que Ana não consiga o emprego (p é F). Neste caso, independente de fazer ou
não uma festa (q é V ou F), a promessa não será descumprida (p → q é V).
Observamos que a única possibilidade de p → q ser falsa é quando p é V e q é F.
Tabela-verdade da condicional p → q.
p q p → q
V V V
V F F
F V V
F F V
Na condicional p → q, a proposição p é chamada de hipótese, premissa ou antecedente,
enquanto a proposição q é denominada tese, conclusão ou consequente.
Em Português, o uso do condicional estabelece uma relação de causa e efeito entre a hipótese
e a conclusão. Entretanto, na condicional lógica p → q, não é necessário existir uma relação
causal entre a hipótese p e a tese q.
Por exemplo, a condicional:
“Se laranjas são azuis então 2 é par”
é destitúıda de “sentido” na ĺıngua portuguesa, mas como a hipótese é falsa, temos que a
condicional é verdadeira, mesmo não existindo relação de causa e efeito entre as proposições
envolvidas.
9
quando p for verdadeira e q for falsa.
Resumindo: V(p → q) = F somente quando V(p) = V e V(q) = F.
Ilustremos inicialmente uma interpretação do conectivo → através da sentença:
“Se Ana conseguir o emprego, então fará uma festa.”
Definindo-se:
p: “Ana consegue o emprego” e q: “ Ana faz uma festa”, então (p → q) representa a
promessa de Ana.
Vamos analisar quando a promessa será cumprida:
1) Digamos que ela consiga a vaga de emprego (p é V). Pode acontecer que ela faça a festa
(q é V), cumprindo a promessa (p → q é V). Por outro lado, Ana pode não fazer a festa,
descumprindo a promessa (p → q é F).
2) Digamos que Ana não consiga o emprego (p é F). Neste caso, independente de fazer ou
não uma festa (q é V ou F), a promessa não será descumprida (p → q é V).
Observamos que a única possibilidade de p → q ser falsa é quando p é V e q é F.
Tabela-verdade da condicional p → q.
p q p → q
V V V
V F F
F V V
F F V
Na condicional p → q, a proposição p é chamada de hipótese, premissa ou antecedente,
enquanto a proposição q é denominada tese, conclusão ou consequente.
Em Português, o uso do condicional estabelece uma relação de causa e efeito entre a hipótese
e a conclusão. Entretanto, na condicional lógica p → q, não é necessário existir uma relação
causal entre a hipótese p e a tese q.
Por exemplo, a condicional:
“Se laranjas são azuis então 2 é par”
é destitúıda de “sentido” na ĺıngua portuguesa, mas como a hipótese é falsa, temos que a
condicional é verdadeira, mesmo não existindo relação de causa e efeito entre as proposições
envolvidas.
9
LÓGICA MATEMÁTICA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
IU N I D A D E22
Proposições Associadas a uma Condicional:
Consideremos as proposições:
p: O quadrilátero Q é um quadrado.
q: O quadrilátero Q é um retângulo.
e a condicional
p → q : “Se o quadrilátero Q é um quadrado, então é um retângulo.”
Temos as seguintes proposições associadas à condicional p → q :
• Contrapositiva ∼ q →∼ p : “Se o quadrilátero Q não é um retângulo, então Q não é um
quadrado.”
• Rećıproca q → p : “Se o quadrilátero Q é um retângulo, então é um quadrado.”
• Inversa ∼ p →∼ q : “Se o quadrilátero Q não é um quadrado, então Q não é um
retângulo.”
5. Bicondicional (↔)
Se p e q são duas proposições, a proposição “p, se e somente se q”, que será indicada por
“p ↔ q” é chamada de bicondicional. A proposição bicondicional será verdadeira quando p e q
forem ambas verdadeiras ou ambas falsas, e será falsa nos demais casos.
Resumindo: V (p ↔ q) = V quando V(p) = V(q).
Tabela-verdade da bicondicional p ↔ q.
p q p ↔ q
V V V
V F F
F V F
F F V
A bicondicional p ↔ q também se lê de uma das seguintes maneiras:
• p é condição necessária e suficiente para q.
• q é condição necessária e suficiente para p.
10
Introdução
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
23
Exemplo:
“Respiro se, e somente se, estou vivo”.
Percebemos pelo exemplo que respirar é condição necessária e suficiente para estar vivo,
assim como estar vivo é condição necessária e suficiente para respirar.
Prioridades de Operações Lógicas
Em uma operação que usa dois ou mais operadores lógicos, como p∧ r∨ q → r, a ordem em
que eles aparecem é muito importante. Em geral, usam-se parênteses para indicar a ordem e
agrupamento das operações lógicas. Mas assim como na Álgebra, existe uma convenção sobre
a ordem de precedência para os conectivos, que estabelecem uma ordem de aplicação, mesmo
na ausência de parênteses.
OPERADOR PRIORIDADE
∼ 1
∧ 2
∨ 3
→ 4
↔ 5
Exemplo:
Seja a sentença em linguagem natural:
“Você não pode andar de montanha russa se você tiver menos do que 1,20 metros de altura, a
menos que você tenha 16 anos de idade.”
Podemos fazer a tradução dessa sentença em proposições compostas da seguinte maneira.
Consideremos as primitivas:
• q: Você pode andar de montanha russa.
• r: Você tem menos do que 1,20 m de altura.
• s: Você tem mais de 16 anos de idade.
Então, a sentença em linguagem natural pode ser traduzida em proposições lógicas como:
r∧ ∼ s →∼ q, ou ainda ∼ r ∨ s → q, que devem ser consideradas como [(r ∧ (∼ s)) → (∼ q)],
ou ainda ((∼ r) ∨ s) → q.
11
LÓGICA MATEMÁTICA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
IU N I D A D E24
Tabela-Verdade
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
25
Tabelas-Verdade
Dadas várias proposições simples p, q, r, s, ..., podemos combiná-las para formar novas proposições
compostas. O valor-verdade dessas novas proposições fica completamente determinado pelos
valores das proposições componentes e pela natureza dos conectivos envolvidos. Uma maneira
de determinar o valor lógico de proposições compostasé pela construção de tabelas-verdade.
Exemplos:
1) Construir a tabela-verdade da proposição ∼ (p ∧ q).
Observemos que como existem duas proposições simples envolvidas, p e q, então existem 4
possibilidades de combinar os valores-verdade de p e q: VV; VF; FV e FF. Dessa forma, a
tabela-verdade terá 22 = 4 linhas.
p q p ∧ q ∼ (p ∧ q)
V V V F
V F F V
F V F V
F F F V
1 1 2 3
2) Construir a tabela-verdade da proposição (p∨ ∼ q) → q.
p q ∼ q p∨ ∼ q (p∨ ∼ q) → q
V V F V V
V F V V F
F V F F V
F F V V F
12
Tabela-Verdade
# REFLITA#
Número de linhas de uma tabela-verdade
“A tabela-verdade de uma proposição composta com
n proposições simples componentes contém 2n linhas”.
Fonte: a autora.
#FIM REFLITA#
Um outro modo de se construir a tabela-verdade de uma proposição composta é dada a
seguir, onde colocamos todos os elementos envolvidos na proposição composta e numeramos as
etapas; a solução será a última etapa:
3) Encontrar a tabela-verdade da proposição composta S = (p∨ ∼ q) → (p ∧ q ↔ r).
p q r (p ∨ ∼ q) → (p ∧ q ↔ r)
V V V V V F V V V V V V
V V F V V F F V V V F F
V F V V V V F V F F F V
V F F V V V V V F F V F
F V V F F F V F F V F V
F V F F F F V F F V V F
F F V F V V F F F F F V
F F F F V V V F F F V F
1 1 1 1 3 2 6 1 4 1 5 1
4) Construir a tabela-verdade de (p ∧ q)∨ ∼ (p → q).
(p ∧ q) ∨ ∼ (p → q)
V V V V F V V V
V F F V V V F F
F F V F F F V V
F F F F F F V F
1 2 1 5 4 1 3 1
Tautologias e Contradições
Uma tautologia é uma proposição composta que é sempre verdadeira, quaisquer que sejam os
valores lógicos das proposições simples que a compõem, ou seja, a coluna de resultado de sua
13
# REFLITA#
Número de linhas de uma tabela-verdade
“A tabela-verdade de uma proposição composta com
n proposições simples componentes contém 2n linhas”.
Fonte: a autora.
#FIM REFLITA#
Um outro modo de se construir a tabela-verdade de uma proposição composta é dada a
seguir, onde colocamos todos os elementos envolvidos na proposição composta e numeramos as
etapas; a solução será a última etapa:
3) Encontrar a tabela-verdade da proposição composta S = (p∨ ∼ q) → (p ∧ q ↔ r).
p q r (p ∨ ∼ q) → (p ∧ q ↔ r)
V V V V V F V V V V V V
V V F V V F F V V V F F
V F V V V V F V F F F V
V F F V V V V V F F V F
F V V F F F V F F V F V
F V F F F F V F F V V F
F F V F V V F F F F F V
F F F F V V V F F F V F
1 1 1 1 3 2 6 1 4 1 5 1
4) Construir a tabela-verdade de (p ∧ q)∨ ∼ (p → q).
(p ∧ q) ∨ ∼ (p → q)
V V V V F V V V
V F F V V V F F
F F V F F F V V
F F F F F F V F
1 2 1 5 4 1 3 1
Tautologias e Contradições
Uma tautologia é uma proposição composta que é sempre verdadeira, quaisquer que sejam os
valores lógicos das proposições simples que a compõem, ou seja, a coluna de resultado de sua
13
# REFLITA#
Número de linhas de uma tabela-verdade
“A tabela-verdade de uma proposição composta com
n proposições simples componentes contém 2n linhas”.
Fonte: a autora.
#FIM REFLITA#
Um outro modo de se construir a tabela-verdade de uma proposição composta é dada a
seguir, onde colocamos todos os elementos envolvidos na proposição composta e numeramos as
etapas; a solução será a última etapa:
3) Encontrar a tabela-verdade da proposição composta S = (p∨ ∼ q) → (p ∧ q ↔ r).
p q r (p ∨ ∼ q) → (p ∧ q ↔ r)
V V V V V F V V V V V V
V V F V V F F V V V F F
V F V V V V F V F F F V
V F F V V V V V F F V F
F V V F F F V F F V F V
F V F F F F V F F V V F
F F V F V V F F F F F V
F F F F V V V F F F V F
1 1 1 1 3 2 6 1 4 1 5 1
4) Construir a tabela-verdade de (p ∧ q)∨ ∼ (p → q).
(p ∧ q) ∨ ∼ (p → q)
V V V V F V V V
V F F V V V F F
F F V F F F V V
F F F F F F V F
1 2 1 5 4 1 3 1
Tautologias e Contradições
Uma tautologia é uma proposição composta que é sempre verdadeira, quaisquer que sejam os
valores lógicos das proposições simples que a compõem, ou seja, a coluna de resultado de sua
13
LÓGICA MATEMÁTICA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
IU N I D A D E26
tabela-verdade contém somente valores lógicos verdadeiros (V). Por outro lado, uma proposição
composta que é sempre falsa é chamada de contradição. Uma proposição composta que não é
uma tautologia nem uma contradição é denominada contingência.
Exemplos:
1) A proposição composta p ∧ q → q é uma tautologia.
p ∧ q → q
V V V V V
V F F V F
F F V V V
F F F V F
1 2 1 3 1
2) A proposição composta (p ∧ q)∧ ∼ (p ∨ q) é uma contradição.
(p ∧ q) ∧ ∼ (p ∨ q)
V V V F F V V V
V F F F V V V F
F F V F V F V V
F F F F V F F F
1 2 1 5 4 1 3 1
3) A proposição composta q →∼ q é uma contingência.
q → ∼ q
V F F
F V V
As tautologias e contradições têm fundamental importância em métodos de prova, e é através
das tautologias que podemos simplificar expressões lógicas.
# REFLITA #
A Lógica é a anatomia do pensamento. (John Locke)
# FIM REFLITA #
14
tabela-verdade contém somente valores lógicos verdadeiros (V). Por outro lado, uma proposição
composta que é sempre falsa é chamada de contradição. Uma proposição composta que não é
uma tautologia nem uma contradição é denominada contingência.
Exemplos:
1) A proposição composta p ∧ q → q é uma tautologia.
p ∧ q → q
V V V V V
V F F V F
F F V V V
F F F V F
1 2 1 3 1
2) A proposição composta (p ∧ q)∧ ∼ (p ∨ q) é uma contradição.
(p ∧ q) ∧ ∼ (p ∨ q)
V V V F F V V V
V F F F V V V F
F F V F V F V V
F F F F V F F F
1 2 1 5 4 1 3 1
3) A proposição composta q →∼ q é uma contingência.
q → ∼ q
V F F
F V V
As tautologias e contradições têm fundamental importância em métodos de prova, e é através
das tautologias que podemos simplificar expressões lógicas.
# REFLITA #
A Lógica é a anatomia do pensamento. (John Locke)
# FIM REFLITA #
14
tabela-verdade contém somente valores lógicos verdadeiros (V). Por outro lado, uma proposição
composta que é sempre falsa é chamada de contradição. Uma proposição composta que não é
uma tautologia nem uma contradição é denominada contingência.
Exemplos:
1) A proposição composta p ∧ q → q é uma tautologia.
p ∧ q → q
V V V V V
V F F V F
F F V V V
F F F V F
1 2 1 3 1
2) A proposição composta (p ∧ q)∧ ∼ (p ∨ q) é uma contradição.
(p ∧ q) ∧ ∼ (p ∨ q)
V V V F F V V V
V F F F V V V F
F F V F V F V V
F F F F V F F F
1 2 1 5 4 1 3 1
3) A proposição composta q →∼ q é uma contingência.
q → ∼ q
V F F
F V V
As tautologias e contradições têm fundamental importância em métodos de prova, e é através
das tautologias que podemos simplificar expressões lógicas.
# REFLITA #
A Lógica é a anatomia do pensamento. (John Locke)
# FIM REFLITA #
14
Tautologias e Contradições
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
27
Equivalências Lógicas
Duas proposições compostas P e Q são chamadas logicamente equivalentes se suas tabelas
-verdade são idênticas, ou melhor, se, e somente se, P ↔ Q for tautologia.
Notações: P ≡ Q ou P ⇔ Q.
Podemos verificar que duas proposições são logicamente equivalentes por meio da construção
de suas tabelas-verdade.
Exemplos:
1) Verificar que p ≡∼ (∼ p).
p ∼ p ∼ (∼ p) p↔∼ (∼ p)
V F V V
F V F V
1 2 3 4
2) Verificar que p → q ⇔∼ p ∨ q.
p q ∼ p p → q ∼ p ∨ q p → q ↔∼ p ∨ q
V V F V V V
V F F F F V
F V V V V V
F F V V V V
1 1 2 3 4 5
15
Equivalências Lógicas
LÓGICA MATEMÁTICA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
IU N I D A D E28
Equivalências Lógicas Importantes
p, q, r proposições
Notações V: tautologia
F: contradição
Propriedade Equivalência Lógica
p ∧ V ≡ p
p ∨ F ≡ p
Identidades p ↔ V ≡ p
p∨F ≡ p
Dominação p ∨ V ≡ V
p ∧ F ≡ F
Leis da idempotência p ∨ p ≡ p
p ∧ p ≡ p
Dupla negação ∼ (∼ p) ≡ p
p ∨ q ≡ q ∨ p
Comutativa p ∧ q ≡ q ∧ p
p↔ q ≡ q ↔ p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Associativa (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(p ↔ q) ↔ r ≡ p ↔ (q ↔ r)
Negação ou Inversa p∨ ∼ p ≡ V
p∧ ∼ p ≡ F
Leis da implicação (p → q) ≡ (∼ p ∨ q) ≡∼ (p∧ ∼ q)
∼ (p → q) ≡ (p∧ ∼ q)
Leis da equivalência (p ↔ q) ≡ (p → q) ∧ (q → p)
∼ (p ↔ q) ≡ (p ↔∼ q) ≡ (∼ p ↔ q)
Distributiva p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Leis de De Morgan ∼ (p ∨ q) ≡∼ p∧ ∼ q
∼ (p ∧ q) ≡∼ p∨ ∼ q
Absorção p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p
Lei da contrapositiva (p → q) ≡ (∼ q) → (∼ p)
Lei da redução ao absurdo p → q ≡ (p∧ ∼ q) → F
Para estudos desenvolvidos em técnicas digitais, as diversas portas lógicas são expressas em
termos de ∼ e ∧. É importante então expressar qualquer um dos conectivos usando somente ∼
e ∧.
16
Equivalência Lógicas
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
29
LÓGICA MATEMÁTICA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
IU N I D A D E30
Exerćıcio: Prove, usando tabela-verdade, a equivalência dos conectivos estudados com as
expressões que envolvem somente ∼ e ∧:
a) Disjunção: p ∨ q ≡∼ (∼ p∧ ∼ q).
b) Condicional: p → q ≡∼ (p∧ ∼ q)
c) Bicondicional: p ↔ q ≡∼ (∼ (p ∧ q)∧ ∼ (∼ p∧ ∼ q))
Conectivos Lógicos e Programação
De acordo com Gersting (2004, p.9), podemos exemplificar uma aplicação da Lógica Matemática
na computação:
Os conectivos lógicos E (AND), OU (OR) e NÃO (NOT)(correspondendo,
respectivamente, a ∧,∨ e ∼) estão dispońıveis em muitas linguagens de
programação, assim como em calculadoras gráficas programáveis. Esses
conectivos, de acordo com as tabelas-verdade que definimos, agem em
combinações de expressões verdadeiras ou falsas para produzir um valor
lógico final. Tais valores lógicos fornecem a capacidade de tomada de decisão
fundamental ao fluxo de controle em programas de computadores. Assim, em
uma ramificação condicional de um programa, se o valor lógico da expressão
condicional for verdadeiro, o programa executará a seguir um trecho de seu
código; se o valor for falso, o programa executará um trecho diferente de
seu código. Se a expressão condicional for substitúıda por outra expressão
equivalente mais simples, o valor lógico da expressão, e portanto, o fluxo de
controle do programa, não será afetado, mas o novo código será mais fácil de
ser entendido e poderá ser executado mais rapidamente.
Exemplo: Vejamos o seguinte comando na linguagem de programação Pascal:
if(( x > y) and not ((x > y) and (z < 1000)))
then Faça isso (um procedimento)
else Faça aquilo (outro procedimento).
Aqui a expressão condicional tem a forma A∧ ∼ (A ∧ B), em que A: x > y e B: z < 1000.
Essa expressão pode ser simplificada utilizando uma condicional simplificada:
A∧ ∼ (A ∧ B) ≡ A ∧ (∼ A∨ ∼ B) (Leis de De Morgan)
≡ (A∧ ∼ A) ∨ (A∧ ∼ B) (distribuitividade)
≡ F ∨ (A∧ ∼ B) (F denota contradição)
≡ (A∧ ∼ B) ∨ F (comutatividade)
≡ (A∧ ∼ B) (identidade)
17
Exerćıcio: Prove, usando tabela-verdade, a equivalência dos conectivos estudados com as
expressões que envolvem somente ∼ e ∧:
a) Disjunção: p ∨ q ≡∼ (∼ p∧ ∼ q).
b) Condicional: p → q ≡∼ (p∧ ∼ q)
c) Bicondicional: p ↔ q ≡∼ (∼ (p ∧ q)∧ ∼ (∼ p∧ ∼ q))
Conectivos Lógicos e Programação
De acordo com Gersting (2004, p.9), podemos exemplificar uma aplicação da Lógica Matemática
na computação:
Os conectivos lógicos E (AND), OU (OR) e NÃO (NOT)(correspondendo,
respectivamente, a ∧,∨ e ∼) estão dispońıveis em muitas linguagens de
programação, assim como em calculadoras gráficas programáveis. Esses
conectivos, de acordo com as tabelas-verdade que definimos, agem em
combinações de expressões verdadeiras ou falsas para produzir um valor
lógico final. Tais valores lógicos fornecem a capacidade de tomada de decisão
fundamental ao fluxo de controle em programas de computadores. Assim, em
uma ramificação condicional de um programa, se o valor lógico da expressão
condicional for verdadeiro, o programa executará a seguir um trecho de seu
código; se o valor for falso, o programa executará um trecho diferente de
seu código. Se a expressão condicional for substitúıda por outra expressão
equivalente mais simples, o valor lógico da expressão, e portanto, o fluxo de
controle do programa, não será afetado, mas o novo código será mais fácil de
ser entendido e poderá ser executado mais rapidamente.
Exemplo: Vejamos o seguinte comando na linguagem de programação Pascal:
if(( x > y) and not ((x > y) and (z < 1000)))
then Faça isso (um procedimento)
else Faça aquilo (outro procedimento).
Aqui a expressão condicional tem a forma A∧ ∼ (A ∧ B), em que A: x > y e B: z < 1000.
Essa expressão pode ser simplificada utilizando uma condicional simplificada:
A∧ ∼ (A ∧ B) ≡ A ∧ (∼ A∨ ∼ B) (Leis de De Morgan)
≡ (A∧ ∼ A) ∨ (A∧ ∼ B) (distribuitividade)
≡ F ∨ (A∧ ∼ B) (F denota contradição)
≡ (A∧ ∼ B) ∨ F (comutatividade)
≡ (A∧ ∼ B) (identidade)
17
Implicações Lógicas
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
31
O comando pode então ser reescrito como:
if ((x > y) and not (z < 1000))
then Faça isso (um procedimento)
else Faça aquilo (outro procedimento).
Implicações Lógicas
Sejam p e q duas proposições. Dizemos que p implica logicamente q se p → q é uma tautologia.
Denotaremos que p implica logicamente em q por “p ⇒ q”.
As implicações lógicas também podem ser chamadas de “inferências lógicas”. As regras de
inferência são, na verdade, formas válidas de racioćınio, isto é, são formas que nos permitem
concluir o consequente, uma vez que consideremos o antecedente verdadeiro; em termos textu-
ais, costumamos utilizar o termo “logo” (ou seus sinônimos: portanto, em consequência, etc.)
para caracterizar as Regras de Inferência; a expressão p ⇒ q pode então ser lida: “p; logo, q”.
Listamos a seguir algumas regras de inferência importantes, sendo p, q e r proposições quais-
quer:
Regras de Inferência
1. p ⇒ p ∨ q Lei de adição
2. p ∧ q ⇒ p Leis de simplificação
p ∧ q ⇒ q
3. (p → q) ∧ p ⇒ q Modus Ponens
4. (p → q)∧ ∼ q ⇒∼ p Modus Tollens
5. (p ∨ q)∧ ∼ p ⇒ q Silogismo disjuntivo
6. (p → q) ∧ (q → r) ⇒ (p → r) Silogismo hipotético
7. p → F ⇒∼ p Demonstração por absurdo
18
LÓGICA MATEMÁTICA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
IU N I D A D E32
Exemplo:
“Se é gato, então mia. É gato, portanto mia.”
Essa frase exemplifica a regra de inferência Modus Ponens (p → q) ∧ p ⇒ q.
Provemos sua veracidade:
p q p → q (p → q) ∧ p [(p → q) ∧ p] → q
V V V V V
V F F F V
F V V F V
F F V F V
Exerćıcio: Verificar cada uma das inferências acima usando tabela-verdade.
Método Dedutivo
Argumentos
Um argumento é uma sequência de proposições na qual uma delas deriva das demais.
Usualmente, a proposição derivada é chamada conclusão, e as demais, premissas. Dito de
outra maneira, chama-se argumento a afirmação de que de um dado conjunto de proposições
P1, P2, ...Pn, chamadas premissas, decorre uma proposição Q, chamada conclusão.
Exemplo:
19
Método Dedutivo
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
33
Exemplo:
“Se é gato, então mia. É gato, portanto mia.”
Essa frase exemplifica a regra de inferência Modus Ponens (p → q) ∧ p ⇒ q.
Provemos sua veracidade:
p q p → q (p → q) ∧ p [(p → q) ∧ p] → q
V V V V V
V F F F V
F V V F V
F F V F V
Exerćıcio: Verificar cada uma das inferências acima usando tabela-verdade.
Método Dedutivo
Argumentos
Um argumento é uma sequência de proposições na qual uma delas deriva das demais.
Usualmente, a proposição derivada é chamada conclusão,e as demais, premissas. Dito de
outra maneira, chama-se argumento a afirmação de que de um dado conjunto de proposições
P1, P2, ...Pn, chamadas premissas, decorre uma proposição Q, chamada conclusão.
Exemplo:
19
Todo aluno de Engenharia de Software precisa estudar Lógica. (premissa)
Leonardo é aluno de Engenharia de Software. (premissa)
Logo, Leonardo precisa estudar Lógica. (conclusão)
Um argumento é considerado válido se a conjunção das hipóteses implica na tese. As pre-
missas são consideradas provas evidentes da verdade da conclusão.
Exemplos:
1) Se é mamı́fero, então é vertebrado.
A baleia é um mamı́fero.
Logo, a baleia é um vertebrado.
Argumento válido, em que as premissas e a conclusão são verdadeiras.
2) Fernando Collor foi presidente do Brasil.
Se é presidente do Brasil, então sofre impeachemnt.
Logo, Collor sofreu impeachment no mandato como presidente.
Argumento válido, com uma das premissas falsa, mas conclusão verdadeira.
3) Se é cobra, tem asas.
A sucuri é uma cobra.
Logo, a sucuri tem asas.
Argumento válido com uma das premissas falsa, e conclusão falsa.
Se a conclusão não decorre das premissas, dizemos que o argumento é inválido ou sofisma.
Exemplos:
1) Se o número é múltiplo de 4, então é múltiplo de 2. O número é múltiplo de 2. Logo,
também é múltiplo de 4.
2) Se é pássaro, é mortal.
Eu sou mortal. Portanto, eu sou um pássaro.
A validade do argumento depende exclusivamente do relacionamento lógico entre as premissas
e a conclusão. A Lógica não se ocupa de verificar se as premissas são verdadeiras; o objetivo da
Lógica é verificar se o argumento é estruturado de forma tal que, independentemente dos valores
lógicos das proposições simples envolvidas, a veracidade das premissas implica na veracidade
da conclusão.
20
Todo aluno de Engenharia de Software precisa estudar Lógica. (premissa)
Leonardo é aluno de Engenharia de Software. (premissa)
Logo, Leonardo precisa estudar Lógica. (conclusão)
Um argumento é considerado válido se a conjunção das hipóteses implica na tese. As pre-
missas são consideradas provas evidentes da verdade da conclusão.
Exemplos:
1) Se é mamı́fero, então é vertebrado.
A baleia é um mamı́fero.
Logo, a baleia é um vertebrado.
Argumento válido, em que as premissas e a conclusão são verdadeiras.
2) Fernando Collor foi presidente do Brasil.
Se é presidente do Brasil, então sofre impeachemnt.
Logo, Collor sofreu impeachment no mandato como presidente.
Argumento válido, com uma das premissas falsa, mas conclusão verdadeira.
3) Se é cobra, tem asas.
A sucuri é uma cobra.
Logo, a sucuri tem asas.
Argumento válido com uma das premissas falsa, e conclusão falsa.
Se a conclusão não decorre das premissas, dizemos que o argumento é inválido ou sofisma.
Exemplos:
1) Se o número é múltiplo de 4, então é múltiplo de 2. O número é múltiplo de 2. Logo,
também é múltiplo de 4.
2) Se é pássaro, é mortal.
Eu sou mortal. Portanto, eu sou um pássaro.
A validade do argumento depende exclusivamente do relacionamento lógico entre as premissas
e a conclusão. A Lógica não se ocupa de verificar se as premissas são verdadeiras; o objetivo da
Lógica é verificar se o argumento é estruturado de forma tal que, independentemente dos valores
lógicos das proposições simples envolvidas, a veracidade das premissas implica na veracidade
da conclusão.
20
Todo aluno de Engenharia de Software precisa estudar Lógica. (premissa)
Leonardo é aluno de Engenharia de Software. (premissa)
Logo, Leonardo precisa estudar Lógica. (conclusão)
Um argumento é considerado válido se a conjunção das hipóteses implica na tese. As pre-
missas são consideradas provas evidentes da verdade da conclusão.
Exemplos:
1) Se é mamı́fero, então é vertebrado.
A baleia é um mamı́fero.
Logo, a baleia é um vertebrado.
Argumento válido, em que as premissas e a conclusão são verdadeiras.
2) Fernando Collor foi presidente do Brasil.
Se é presidente do Brasil, então sofre impeachemnt.
Logo, Collor sofreu impeachment no mandato como presidente.
Argumento válido, com uma das premissas falsa, mas conclusão verdadeira.
3) Se é cobra, tem asas.
A sucuri é uma cobra.
Logo, a sucuri tem asas.
Argumento válido com uma das premissas falsa, e conclusão falsa.
Se a conclusão não decorre das premissas, dizemos que o argumento é inválido ou sofisma.
Exemplos:
1) Se o número é múltiplo de 4, então é múltiplo de 2. O número é múltiplo de 2. Logo,
também é múltiplo de 4.
2) Se é pássaro, é mortal.
Eu sou mortal. Portanto, eu sou um pássaro.
A validade do argumento depende exclusivamente do relacionamento lógico entre as premissas
e a conclusão. A Lógica não se ocupa de verificar se as premissas são verdadeiras; o objetivo da
Lógica é verificar se o argumento é estruturado de forma tal que, independentemente dos valores
lógicos das proposições simples envolvidas, a veracidade das premissas implica na veracidade
da conclusão.
20
Todo aluno de Engenharia de Software precisa estudar Lógica. (premissa)
Leonardo é aluno de Engenharia de Software. (premissa)
Logo, Leonardo precisa estudar Lógica. (conclusão)
Um argumento é considerado válido se a conjunção das hipóteses implica na tese. As pre-
missas são consideradas provas evidentes da verdade da conclusão.
Exemplos:
1) Se é mamı́fero, então é vertebrado.
A baleia é um mamı́fero.
Logo, a baleia é um vertebrado.
Argumento válido, em que as premissas e a conclusão são verdadeiras.
2) Fernando Collor foi presidente do Brasil.
Se é presidente do Brasil, então sofre impeachemnt.
Logo, Collor sofreu impeachment no mandato como presidente.
Argumento válido, com uma das premissas falsa, mas conclusão verdadeira.
3) Se é cobra, tem asas.
A sucuri é uma cobra.
Logo, a sucuri tem asas.
Argumento válido com uma das premissas falsa, e conclusão falsa.
Se a conclusão não decorre das premissas, dizemos que o argumento é inválido ou sofisma.
Exemplos:
1) Se o número é múltiplo de 4, então é múltiplo de 2. O número é múltiplo de 2. Logo,
também é múltiplo de 4.
2) Se é pássaro, é mortal.
Eu sou mortal. Portanto, eu sou um pássaro.
A validade do argumento depende exclusivamente do relacionamento lógico entre as premissas
e a conclusão. A Lógica não se ocupa de verificar se as premissas são verdadeiras; o objetivo da
Lógica é verificar se o argumento é estruturado de forma tal que, independentemente dos valores
lógicos das proposições simples envolvidas, a veracidade das premissas implica na veracidade
da conclusão.
20
Exemplo:
“Se é gato, então mia. É gato, portanto mia.”
Essa frase exemplifica a regra de inferência Modus Ponens (p → q) ∧ p ⇒ q.
Provemos sua veracidade:
p q p → q (p → q) ∧ p [(p → q) ∧ p] → q
V V V V V
V F F F V
F V V F V
F F V F V
Exerćıcio: Verificar cada uma das inferências acima usando tabela-verdade.
Método Dedutivo
Argumentos
Um argumento é uma sequência de proposições na qual uma delas deriva das demais.
Usualmente, a proposição derivada é chamada conclusão, e as demais, premissas. Dito de
outra maneira, chama-se argumento a afirmação de que de um dado conjunto de proposições
P1, P2, ...Pn, chamadas premissas, decorre uma proposição Q, chamada conclusão.
Exemplo:
19
Todo aluno de Engenharia de Software precisa estudar Lógica. (premissa)
Leonardo é aluno de Engenharia de Software. (premissa)
Logo, Leonardo precisa estudar Lógica. (conclusão)
Um argumento é considerado válido se a conjunção das hipóteses implica na tese. As pre-
missas são consideradas provas evidentes da verdade da conclusão.
Exemplos:
1) Se é mamı́fero, então é vertebrado.
A baleia é um mamı́fero.
Logo, a baleia é um vertebrado.
Argumento válido, em que as premissas e a conclusão são verdadeiras.
2) FernandoCollor foi presidente do Brasil.
Se é presidente do Brasil, então sofre impeachemnt.
Logo, Collor sofreu impeachment no mandato como presidente.
Argumento válido, com uma das premissas falsa, mas conclusão verdadeira.
3) Se é cobra, tem asas.
A sucuri é uma cobra.
Logo, a sucuri tem asas.
Argumento válido com uma das premissas falsa, e conclusão falsa.
Se a conclusão não decorre das premissas, dizemos que o argumento é inválido ou sofisma.
Exemplos:
1) Se o número é múltiplo de 4, então é múltiplo de 2. O número é múltiplo de 2. Logo,
também é múltiplo de 4.
2) Se é pássaro, é mortal.
Eu sou mortal. Portanto, eu sou um pássaro.
A validade do argumento depende exclusivamente do relacionamento lógico entre as premissas
e a conclusão. A Lógica não se ocupa de verificar se as premissas são verdadeiras; o objetivo da
Lógica é verificar se o argumento é estruturado de forma tal que, independentemente dos valores
lógicos das proposições simples envolvidas, a veracidade das premissas implica na veracidade
da conclusão.
20
Para provar que um argumento é válido, devemos verificar que P1 ∧ P2 ∧ ... ∧ Pn → Q é
uma tautologia. Isso pode ser feito por meio das tabelas-verdade, mas o processo ficaria de-
masiadamente longo se um grande número de proposições simples estiver envolvido. Podemos
então recorrer ao método dedutivo, que consiste em obter a conclusão a partir das premissas
e de uma cadeia de equivalências e inferências que atuam sobre as hipóteses, criando novas
proposições até que se obtenha a tese, provando o resultado.
Exemplos: Verificar se os seguintes argumentos são válidos, usando o método dedutivo.
a) Se não terminar o trabalho, então durmo mais cedo. Se dormir mais cedo, descansarei.
Não descansei. Logo, terminei o trabalho.
Podemos reescrever o argumento acima na forma da lógica proposicional da seguinte forma:
∼ p → q (hipótese 1)
q → r (hipótese 2)
∼ r (hipótese 3)
p (Tese)
Onde:
p : Termino o trabalho.
q : Durmo mais cedo.
r : Descanso.
Devemos provar que (∼ p → q) ∧ (q → r)∧ ∼ r ⇒ p
1. ∼ p → q (hipótese)
2. q → r (hipótese)
3. ∼ r (hipótese)
4. ∼ q (2, 3, Modus Tollens)
5. ∼ (∼ p) (1, 4, Modus Tollens)
6. p (5, Dupla negação)
b) [Gersting, 2004, p.26] Se o programa é eficiente, ele executará rapidamente. Ou o pro-
grama é eficiente ou ele tem um erro. No entanto, o programa não executa rapidamente.
Portanto o programa tem um erro.
E: o programa é eficiente.
R: o programa executa rapidamente.
B: o programa tem um erro.
(E → R) ∧ (E ∨ B)∧ ∼ R ⇒ B
21
LÓGICA MATEMÁTICA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
IU N I D A D E34
Método Dedutivo
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
35
1. E → R (hipótese)
2. E ∨ B (hipótese)
3. ∼ R (hipótese)
4. ∼ E (1, 3, Modus Tollens)
5. B (2, 4, tautologia E ∨ B∧ ∼ E ⇒ B )
c) [Gersting, 2004, p.26] Rússia tinha um poder superior e, a França não era forte ou
Napoleão cometeu um erro. Napoleão não cometeu um erro, mas se o exército não tivesse
falhado, a França seria forte. Portanto, o exército falhou e a Rússia tinha um poder superior.
R: A Rússia tinha um poder superior.
F: A França era forte.
N: Napoleão cometeu um erro.
E: O exército falhou.
O argumento é portanto: [R ∧ (∼ F ∨N)]∧ ∼ N ∧ (∼ E → F ) ⇒ E ∧R.
1. R ∧ (∼ F ∨N) (hipótese)
2. ∼ N (hipótese)
3. ∼ E → F (hipótese)
4. R (1, Lei de simplificação )
5. ∼ F ∨N (1, Lei de simplificação)
6. ∼ F (5, 2, silogismo disjuntivo)
7. ∼ (∼ E) (3, 6, Modus Tollens)
8. E (7, dupla negação)
9. E ∧R (8, 4, conjunção)
Quantificadores e Predicados
A Lógica proposicional não é suficiente para simbolizar qualquer tipo de sentença, pois tem
uma possibilidade limitada de expressões.
Por exemplo:
• “Para todo x, y, x+ y > 3”
• “Existem crianças que não gostam de chocolate.”
• “Todo computador do Laboratório 2 está com v́ırus.”
22
1. E → R (hipótese)
2. E ∨ B (hipótese)
3. ∼ R (hipótese)
4. ∼ E (1, 3, Modus Tollens)
5. B (2, 4, tautologia E ∨ B∧ ∼ E ⇒ B )
c) [Gersting, 2004, p.26] Rússia tinha um poder superior e, a França não era forte ou
Napoleão cometeu um erro. Napoleão não cometeu um erro, mas se o exército não tivesse
falhado, a França seria forte. Portanto, o exército falhou e a Rússia tinha um poder superior.
R: A Rússia tinha um poder superior.
F: A França era forte.
N: Napoleão cometeu um erro.
E: O exército falhou.
O argumento é portanto: [R ∧ (∼ F ∨N)]∧ ∼ N ∧ (∼ E → F ) ⇒ E ∧R.
1. R ∧ (∼ F ∨N) (hipótese)
2. ∼ N (hipótese)
3. ∼ E → F (hipótese)
4. R (1, Lei de simplificação )
5. ∼ F ∨N (1, Lei de simplificação)
6. ∼ F (5, 2, silogismo disjuntivo)
7. ∼ (∼ E) (3, 6, Modus Tollens)
8. E (7, dupla negação)
9. E ∧R (8, 4, conjunção)
Quantificadores e Predicados
A Lógica proposicional não é suficiente para simbolizar qualquer tipo de sentença, pois tem
uma possibilidade limitada de expressões.
Por exemplo:
• “Para todo x, y, x+ y > 3”
• “Existem crianças que não gostam de chocolate.”
• “Todo computador do Laboratório 2 está com v́ırus.”
22
Não é posśıvel simbolizar tais sentenças adequadamente usando apenas variáveis proposi-
cionais, parênteses e conectivos lógicos, pois elas contêm elementos novos (“para todo”, “para
cada”, “para algum”) que são ligados ao conceito de predicados e quantificadores, que definire-
mos posteriormente.
Uma sentença aberta é uma expressão que depende de uma ou mais variáveis. O valor
verdade dessas sentenças só fica determinado quando os valores das variáveis forem identifica-
dos. (Logo, sentenças abertas não são proposições).
Uma sentença aberta também pode ser denominada proposição aberta ou função proposi-
cional.
Exemplos:
a) y + 2 é maior que 5.
b) x é um número ı́mpar.
c) O computador x do Laboratório 1 está funcionando adequadamente.
d) O quadrado de y é 81.
Observamos que a sentença do exemplo (a) será verdadeira se y for um número maior que
3, mas será falsa se y ≤ 3.
Chamamos conjunto universo (U) ou domı́nio de interpretação o conjunto de objetos dos
quais a variável pode ser escolhida. Para os exemplos acima, o conjunto universo do item (c)
são os computadores do Laboratório 1, e o conjunto universo para o item (d) são números
23
LÓGICA MATEMÁTICA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
IU N I D A D E36
inteiros.
Numa sentença aberta, a propriedade ou relacionamento entre objetos (ou variáveis) é
chamada predicado. Denotaremos um predicado qualquer associado a uma variável x por
P (x).
Por exemplo, na sentença “P (x) = x é número primo”, a propriedade da variável x é “ser
primo”. Temos que P(7) é verdadeira e P(18) é falsa, pois 7 é um número primo e 18 não.
Chama-seConjunto-Verdade (VP ) de uma sentença P (x) o conjunto de valores da variável
no Universo para os quais a sentença é verdadeira, ou seja,
VP = {a ∈ U | V [P (a)] = V }
Por exemplo, seja U = {0, 1, 2, 3, 4, 5, 6, 7} e a expressão “x é par” representada por P(x).
Temos então VP = {0, 2, 4, 6}.
Para predicados que envolvem mais variáveis, a ordem em que as variáveis aparecem é im-
portante. Por exemplo, se P(x,y) indica que x é predador de y, não podemos dizer que y é
predador de x (ou seja, que vale P(y,x)).
Uma outra maneira de transformar sentenças abertas em proposições é por meio da uti-
lização de quantificadores. Quantificadores são frases do tipo “para todo”, “para cada” ou
“para algum”, isto é, frases que dizem “quantos objetos” apresentam determinada propriedade.
A área da Lógica que estuda predicados e quantificadores é denominada de cálculo de
predicados.
Quantificador Universal: é simbolizado por “∀” e lê-se “para todo”, “para qualquer” ou“para cada”. Uma proposição do tipo “Para todo x, P (x) ” é simbolicamente representada por
(∀x)(P (x)).
Quantificador Existencial: simbolizado por “∃”, é lido como “existe um”; “há pelo menos
um”; “para ao menos um”; “para algum”. Uma proposição do tipo “Existe um x tal que P (x)”
pode ser escrita simbolicamente como (∃x)(P (x)).
Exemplos:
Simbolizar as proposições:
a) Para todo x, existe um y tal que x+ y < 0:
(∀x)(∃y)(x+ y < 0)
24
Método Dedutivo
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
37
b) Existe um x e existe um y tal que x.y é racional: (onde x.y indica o produto de x por y)
(∃x)(∃y)[(x.y) ∈ Q]
c) Para todo x, se x é negativo, então existe y positivo tal que x+ y = 0:
(∀x)[x < 0 → (∃y)(y > 0 ∧ x+ y = 0)]
d) Somente os médicos podem solicitar exames.
Indicando por M(x): x é médico e E(x): x pode solicitar exames, a sentença pode ser
reescrita como:
Para todo x, se x pode solicitar exames, então x é médico: (∀x)(E(x) → M(x)).
e) Todo dia que é ensolarado não é chuvoso.
Considerando os śımbolos predicados D(x): x é um dia; E(x): x é ensolarado e C(x): x é
chuvoso, então podemos reescrever a proposição como:
(∀x)[D(x) ∧ E(x) →∼ C(x)]
Negação de Sentenças Quantificadas
Consideremos a seguinte sentença: “Todos os insetos têm asas”. Sua negação será “Não é
verdade que todos os insetos têm asas”, ou “Alguns insetos não têm asas”, ou ainda, “Existem
insetos que não têm asas”.
A negação de “Existem crianças obesas” é “Nenhuma criança é obesa”, ou “Toda criança
não é obesa”, ou “Qualquer criança não é obesa.”
Resumindo:
∼ [(∀x)(P (x))] ≡ (∃x)(∼ P (x))
e
∼ [(∃x)(P (x))] ≡ (∀x)(∼ P (x))
Exemplo: Considere a sentença “Dados x, y ∈ R, se x < y, então x2 < y2.”
25
LÓGICA MATEMÁTICA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
IU N I D A D E38
Considerações Finais
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
39
a) Com o uso de śımbolos predicados e quantificadores apropriados, escrever simbolicamente
a sentença:
(∀x)(∀y)(x < y → x2 < y2).
b) Escrever, simbolicamente e em linguagem usual, a negação da sentença dada.
∼
(
(∀x)(∀y)(x < y → x2 < y2)
)
≡ (∃x) ∼
(
(∀y)(x < y → x2 < y2)
)
≡ (∃x)(∃y) ∼
(
(x < y → x2 < y2)
)
≡ (∃x)(∃y)
(
x < y∧ ∼ (x2 < y2)
)
≡ (∃x)(∃y)
(
x < y ∧ (x2 ≥ y2)
)
.
“Existem x e y, com x < y e (x2 ≥ y2)”.
Considerações Finais
O desenvolvimento de software é uma atividade de crescente importância na sociedade atual, e
a necessidade de soluções computadorizadas surgem nas mais diversas áreas do conhecimento
humano.
Ao iniciar o curso, o aluno é preparado para resolver pequenos problemas por meio da
programação e da estrutura de dados, para posteriormente tratar de problemas mais complexos,
o que exigirá maiores conhecimentos e habilidades. Para isso, o racioćınio lógico deve ser
desenvolvido, pois facilita a busca por uma solução que seja coerente, efetiva e eficaz, o que
geralmente não é tão simples.
Sendo a Lógica o estudo dos mecanismos do pensamento, é natural que ela ocupe um papel
de destaque na Computação, tendo aplicação em diversas áreas tais como banco de dados;
circuitos integrados; inteligência artificial; sistemas computacionais (hardware e software) e
sistemas distribúıdos. Como a Lógica possui uma linguagem simbólica própria, torna-se posśıvel
a utilização de recursos computacionais no tratamento de enunciados e argumentos, visto que
os computadores digitais se mostram bastante adequados à manipulação de śımbolos, enquanto
apresentam extrema dificuldade no tratamento de linguagem natural. Nesta unidade fizemos
estudo dos conectivos lógicos “e”, “ou” e “não”, oferecidos pela maioria das linguagens de
programação, e observamos que os valores-verdade de proposições compostas dependem dos
valores de seus componentes e dos conectivos usados. Também foi exemplificado como as
implicações e equivalências lógicas auxiliam na simplificação de expressões mais complexas,
permitindo que um código se torne mais simples de ser entendido e executado em menor tempo.
As linguagens de programação são constitúıdas em função da lógica de predicados, e a lógica
formal é essencial para o curso, dáı a importância do estudo dos tópicos dessa unidade.
26
Atividades de Autoestudo
1) Sabendo que p é uma proposição verdadeira, determine se as afirmações abaixo são ver-
dadeiras (V) ou falsas (F):
a) p ∧ q é verdadeira, qualquer que seja q;
b) p ∨ q é verdadeira, qualquer que seja q.
c) p ∧ q é verdadeira só se q for verdadeira.
d) p → q é falsa, qualquer que seja q.
e) p → q é verdadeira, quaisquer que sejam p e q.
f) p ↔ q é verdadeira só se q for verdadeira.
2) Sabendo que os valores lógicos das proposições p, q, r e s são respectivamente F, V, V e
F, determinar o valor lógico (V ou F) das seguintes proposições compostas:
a) (p ∧ (∼ q → q))∨ ∼ ((r ↔∼ q) → (q∧ ∼ r)).
b) (p ∧ q)∨ ∼ s →∼ (q ↔∼ r).
c) (p ∧ q −→ r) ∨ (∼ p ↔ q∨ ∼ r).
d) ∼ (r → (∼ r → s)).
3) Determine o valor lógico (V ou F) de cada uma das seguintes proposições, justificando a
resposta:
a) (p ↔ q)∧ ∼ r ; sabendo que V (p) = V e V (r) = V .
b) p ∧ q → p ∨ r ; sabendo que V (p) = V e V (r) = F .
c) (p →∼ q) ∧ (∼ p∧ ∼ r) ; sabendo que V (q) = F e V (r) = V .
4) Um conectivo muito muito importante para projetos de circuitos lógicos é o operador não
-e ou nand, que denotaremos por �, definido por p � q = ∼ (p ∧ q). De maneira análoga,
temos o operador não-ou ou nor, que denotaremos por �, definido por p � q = ∼ (p ∨ q).
Construa as tabelas-verdade dos operadores � e �.
5) Dê a negação das seguintes proposições:
a) Linux é um software livre e Pascal é uma linguagem de programacção.
b) Todos os homens são bons motoristas.
c) Se T é um trapézio, então T é um quadrilátero.
d) O processador é rápido, mas a impressora é lenta.
e) Se o processador é rápido, então a impressora é lenta.
f) Existem números pares que não são múltiplos de 2.
27
g) É suficiente cantar para estar vivo.
h) Toda solução de x2 − 6 = 0 é positiva.
i) Alguns inteiros são pares ou diviśıveis por 5.
j) Windows é um editor de textos e Pascal é uma planilha eletrônica.
6) Determine o valor-verdade (V) ou (F) de cada uma das seguintes proposições, con-
siderando R como conjunto universo:
a) (∀x)(∀y)(x+ 6 < y + 10).
b) (∀x)(∃y)(x.y não é par).
c) (∃x)(∀y)(x2 > y).
d) (∀x)(∃y)(x2 > y).
7) Use lógica proposicional para provar a validade dos seguintes argumentos, indicando as
proposições envolvidas:
a) (Gersting, 2004 p.23) “Se segurança é um problema, então o controle será aumentado. Se
segurança não é um problema, então os negócios na Internet irão aumentar. Portanto, se
o controle não for aumentado, os negócios na Internet crescerão.”
b) “Se o produto é bom, ganha o concurso. Se o produto não é bom, o ĺıder do grupo
é culpado. Se o produto ganha o concurso, a equipe fica contente. A equipe não está
contente. Logo, o ĺıder é culpado.”
Leitura Complementar
O que é Lógica? Aristóteles, na Grécia Antiga, foi um dos pioneiros da chamada lógica for-
mal, apresentando regras para que um racioćınio esteja encadeado corretamente, chegando a
conclusões verdadeiras a partir de premissas verdadeiras.
No entanto, no século XIX, alguns matemáticos e filósofos - dentre eles George Boole (1815-
1864), Augustus De Morgan (1806-1871), Gottlob Frege (1848-1925), Bertrand Russell (1872-
1970) e Alfred North Whitehead (1861-1947) - começaram a perceber que a lógica formal era
insuficiente para alcançar o rigor necessário no estudo da matemática, pois essa se apoiava
na linguagem natural