2 - Lógica-Algoritmos-e-Programação-de-Computadores_UIA2

Prévia do material em texto

LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE 
COMPUTADORES 
UNIDADE 2 | LÓGICA QUANTITATIVA DEMONSTRAÇÃO E 
INDUÇÃO 
 VERSÃO PARA IMPRESSÃO 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
2 
 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
3 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Este material é destinado exclusivamente aos alunos e professores do Centro Universitário IESB, contém 
informações e conteúdos protegidos e cuja divulgação é proibida por lei. O uso e/ou reprodução total ou 
parcial não autorizado deste conteúdo é proibido e está sujeito às penalidades cabíveis, civil e 
criminalmente. 
 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
4 
SUMÁRIO 
 
Aula 9 | Predicados ........................................................................................................................ 6 
9.1. Conceitos .......................................................................................................................................... 6 
9.2. Representação Simbólica .................................................................................................................. 8 
Aula 10 | Quantificadores .............................................................................................................. 9 
10.1. Conceitos ........................................................................................................................................ 9 
10.2. Existencial ..................................................................................................................................... 10 
10.3. Universal ....................................................................................................................................... 10 
10.4. Negação de Proposições com Quantificador ................................................................................. 11 
Exemplo 1 ..................................................................................................................................................... 11 
Exemplo 2 ..................................................................................................................................................... 12 
10.5. Expressões Equivalentes ............................................................................................................... 13 
Exemplo 3 ..................................................................................................................................................... 13 
10.6. Argumentos e Quantificadores ..................................................................................................... 13 
10.6.1. Regra da Instanciação Universal .............................................................................................. 13 
Exemplo 4 ..................................................................................................................................................... 13 
Modus Ponens Universal ............................................................................................................................... 13 
Modus Tollens Universal ............................................................................................................................... 14 
Aula 11 | Regras de Dedução: Particularização ............................................................................ 14 
11.1. Particularização Universal ............................................................................................................. 14 
Exemplo 1 ..................................................................................................................................................... 14 
Exemplo 2: .................................................................................................................................................... 15 
11.2. Particularização Existencial ........................................................................................................... 16 
Exemplo 3 ..................................................................................................................................................... 17 
Aula 12 | Regras de Dedução: Generalização ............................................................................... 18 
12.1. Generalização Universal................................................................................................................ 18 
12.2. Generalização Existencial .............................................................................................................. 19 
Exemplos ...................................................................................................................................................... 21 
Aula 13 | Demonstração ............................................................................................................... 22 
13.1. Conceitos ...................................................................................................................................... 22 
13.2. Raciocínio Dedutivo X Indutivo ..................................................................................................... 24 
Aula 14 | Técnica I ........................................................................................................................ 25 
14.1. Demonstração por Contraposição................................................................................................. 25 
14.2. Demonstração Exaustiva ............................................................................................................... 27 
Aula 15 | Técnica II ....................................................................................................................... 29 
15.1. Demonstração Direta .................................................................................................................... 29 
15.2. Demonstração por Absurdo .......................................................................................................... 30 
Aula 16 | Indução ......................................................................................................................... 32 
16.1. Conceitos ...................................................................................................................................... 32 
16.2. Princípios ...................................................................................................................................... 32 
16.3. Indução Matemática ..................................................................................................................... 33 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
5 
Referências ................................................................................................................................... 37 
Glossário ....................................................................................................................................... 37 
 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
6 
Aula 9 | PREDICADOS 
 
Prezado estudante, em nossa língua chamamos de predicado numa frase a tudo o que se declara sobre o 
sujeito sendo obrigatória a presença de um verbo ou de uma locução verbal. Numa oração quando se 
localiza o sujeito se localiza também o predicado. 
Trazendo esse conceito de predicado para o campo de atuação da lógica veremos como o cálculo de 
predicados é bem mais abrangente do que o cálculo proposicional e comoé útil para tirar conclusões onde a 
lógica de proposições tem suas limitações. Com isso em mente, vamos iniciar nossa primeira aula desta 
unidade. 
 
9.1. CONCEITOS 
Nosso curso até aqui cuidou de analisar como um argumento1 pode ser válido ou inválido quando 
entendido pela lógica dos conectivos “ou”, “ou...ou”, “se..., então” e o “se, somente se”, alem do 
modificador lógico “não”, porém essa linguagem não consegue traduzir de uma forma satisfatória 
argumentos mais complexos uma vez que, lhe falta ferramentas para descrever um ambiente com muitos 
objetos. 
Devido a essas limitações do calculo proposicional e da necessidade que se teve de se representar um 
argumento cuja complexidade extrapolava ao domínio do uso dos conectivos ou os tornavam 
excessivamente trabalhosos e que surgiu o calculo de predicados. 
O calculo de predicados ou lógica de primeira ordem, contem uma linguagem mais rica, pois além de conter 
elementos do calculo de proposições expande suas possibilidades por explorarem o uso dos quantificadores2. 
Observe os exemplos a seguir que mostram argumentos válidos, como já vistos, mas que não é possível 
justificá-los somente com o uso dos conectivos: 
P1: Todo homem é um ser racional. 
P2: Carlos é um homem. 
C: Logo, Carlos é um ser racional 
Q1: Todo vascaíno é feliz. 
Q2: Algumas pessoas são vascaínas. 
C: Algumas pessoas são felizes. 
Analisando os dois exemplos acima verificamos que a validade desses argumentos depende não somente 
dos conetivos, mas do significado das expressões “todo” e “alguns”. 
Mas o que vem a ser de fato um quantificador? 
Em nossas aulas trataremos de sentenças abertas e fechadas, vimos que não é uma proposição uma 
sentença do tipo: 
x +1 = 8 
 
1 Uma afirmação seguida de uma justificativa. 
2 Termos utilizados para quantificar elementos de um dado conjunto. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
7 
Já que a mesma, como assinalada acima não pode ser valorada como sendo ou verdadeiro (V) ou falso (F), 
porém podemos transformá-la numa proposição de duas formas: 
• Atribuindo um valor para a variável x. 
• Utilizando símbolos lógicos chamados de quantificadores. 
Quantificadores são símbolos que representam uma quantidade de elementos. Eles têm função de 
informar sobre determinada quantidade de elementos de uma situação qualquer. Em nosso estudo a cerca 
dos quantificadores centraremos nossa atenção nos: 
• Quantificador universal que é usado quando desejamos nos referir a todos os elementos de um 
dado conjunto. Palavras como: Todo, para todo, são quantificadores universais 
• Quantificador existencial faz referencia a existência de pelo menos um elemento pertencente a um 
dado conjunto e não a todos os elementos de um conjunto. Palavras como: algum, pelo menos um, 
são quantificadores existenciais. 
Importante! 
Cuidado com o quantificador pelo menos um. Ele quer significar no mínimo um elemento do 
conjunto considerado e não necessariamente um. 
Voltemos à sentença aberta x +1 = 8. Vejam como essa sentença aberta com o uso dos quantificadores 
podem ser valoradas como sendo ou verdadeiro (V) ou falso (F), tornando-se assim uma proposição: 
a. Para todo x, com x pertencendo ao conjunto dos números Naturais temos x +1 = 8. (Essa é uma 
sentença fechada é uma proposição falsa (F)) 
b. Existe pelo menos um x, com x pertencendo ao conjunto dos números Naturais tal que x +1 = 8. 
(Essa é uma sentença fechada é uma proposição verdadeira (V)) 
Ainda sobre os quantificadores vales destacar algumas de suas propriedades: 
• Todo P é Q, entende-se que P	⊂ Q (P está contido em Q ou P é subconjunto3 de Q). 
 
• Algum A é B entende-se como uma interseção ente A e B. 
 
• Nenhum C é D caracteriza dois conjuntos disjuntos não havendo interseção. 
 
3 Uma fração do todo. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
8 
 
 
Para saber um pouco mais sobre a parte introdutória da lógica 
de predicados assista ao vídeo a seguir. 
http://tinyurl.com/mv2utfe 
 
9.2. REPRESENTAÇÃO SIMBÓLICA 
Para tornar a estrutura de sentenças complexas mais simples de se manipular e de se entender 
apresentaremos os novos símbolos que darão corpo à linguagem da lógica de predicados ou lógica de 
primeira ordem que facilitarão sua compreensão, ressalvando que todos os conectivos do calculo de 
preposições continuam válidos. 
• Variáveis (x, y, z,...): Indicadas por letras minúsculas elas estabelecem fatos sobre os objetos, sem 
nomeá-los diretamente. As variáveis não são proposições simples apenas serão quando seguidas 
de um quantificador. 
• Quantificadores: Quantificador universal [∀ (lê-se para todo)] e quantificador existencial [ ∃ (lê-se 
existe, existe pelo menos um)]. 
• Predicados: Indicadas por letras maiúsculas os predicados trazem uma propriedade ou relação 
entre dois objetos num determinado universo. 
Veja algumas formar de usar essa simbologia: 
Quando tivermos a informação P(x) isso significará para nós que x tem a propriedade P. 
 Quando tivermos (∀x)P(x) isso significará para nós que a propriedade P vale para todo x, sem 
exceção. 
 Quando tivermos (∃x)P(x) isso significará para nós que algum x tem a propriedade P, ou ainda, 
que existe no mínimo um objeto do Universo considerado que tem a propriedade P. 
Exemplos: Escreva em linguagem simbólica as premissas e as conclusões abaixo: 
a. Todo amigo de Carlos é amigo de Jonas. 
Pedro não é amigo de Jonas. 
Logo, Pedro não é amigo de Carlos. 
Em linguagem simbólica temos: 
P1: (∀x) (P(x,c) � P(x,j)): Nesta fórmula x (todo) é a variável P(x,c) indica uma relação entre os 
amigos e Carlos e P(x,j) indica uma relação entre os amigos e Jonas. O (∀x) é o quantificador lógico. 
Como visto nas propriedades dos quantificadores este quantificador leva a uma implicação (��. 
P2: ~ P(p,j): Esta formula nos indica que não há amizade entre Pedro e Jonas. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
9 
Assim: 
P1: (∀x) (P(x,c) � P(x,j)) 
P2: ~ P(p,j) 
C:�� P(p,c) - Logo, Pedro não é amigo de Carlos 
b. Toda cobra é venenosa. 
Em linguagem simbólica temos: 
(∀x) (C(x) � V(x)) – Onde o x é a variável (toda) que traz a ideia de implicação: “Se é cobra, então é 
venenosa” que equivale a dizer semanticamente que para todo x, se x∈ C, então x∈ V. 
c. P1:Todos os humanos são racionais. 
P2: Alguns animais são humanos. 
C Portanto, alguns animais são racionais. 
Em linguagem simbólica temos: 
P1: (∀x) (P(x) � Q(x)) 
P2: (∃x) (R(x) ∧ P(x)) 
Como num argumento se as premissas forem verdadeiras a conclusão tem que ser verdadeira 
temos que em P2 pela conjunção R(x) e P(x) tem que ser verdadeiras o que necessariamente impõe 
que na condicional P1 Q(x) seja verdadeira o que nos leva a concluir que alguns animais são 
racionais. 
(∃x) (R(x) ∧ Q(x)) 
Detalhe neste argumento P, Q, R simbolizam as propriedades de: ser humano, ser racional e ser animal 
respectivamente. 
 
Saiba mais sobre a simbologia da lógica de predicados no endereço 
eletrônico no link a seguir. 
http://tinyurl.com/m9xqmxw 
 
Aula 10 | QUANTIFICADORES 
 
Dada a grande importância dos quantificadores na lógica de predicados ou como também é chamada 
“lógica de primeira ordem” cabe dedicar uma aula exclusivamente para analisar mais profundamente qual 
sua função, o que ele acarreta qual a forma de negá-lo bem, dentre outros. E assim iniciamos mais uma 
aula, desta vez abordando quantificadores. 
 
10.1. CONCEITOS 
Seja uma condição P(x), um quantificador tem a capacidade de transformar algo incerto como P(x) 
(impossível de ser valorada) numa sentença fechada,ou seja, numa proposição. Assim se antepormos à 
P(x) um quantificador do tipo ∃ ou ∀ será possível afirmar se P(x) é verdadeiro (V) ou falso (F). 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
10 
Para entendermos melhor esse conceito considere o conjunto A = {5, 7, 8, 9, 11, 13}. A partir de A podemos 
dizer que: 
• Qualquer que seja o elemento de A, ele é um número natural; 
• Existe elemento de A que é número ímpar; 
• Existe um único elemento de A que é par; 
• Não existe elemento em A que seja múltiplo de 6. 
Os quantificadores representaram expressões tais como: “qualquer que seja”, “existe”, “existe um único”, 
“não existe”, além de “todo”, “nenhum”, “algum”, dentre outros. 
Fundamentalmente há dois tipos de quantificadores: os existenciais e os universais. 
 
10.2. EXISTENCIAL 
O quantificador existencial se remete não à totalidade dos elementos de um dado conjunto, mas a uma 
fração do mesmo. 
Símbolo: ∃ (lê-se existe) 
Vale destacar que quando afirmamos que existe x em A que é maior que 5, não se quer afirmar que esse x é 
único. Voltando ao conjunto A = {5, 7, 8, 9, 11, 13}, podemos escrever as três últimas proposições usando a 
simbologia dos quantificadores existenciais. 
• x ∈ A / x é impar. 
• ∃! x ∈ A / x é par. 
• ∄ x ∈ A / x é múltiplo de 6. 
 
10.3. UNIVERSAL 
Um quantificador universal se refere a todos os elementos de um dado conjunto. 
Símbolo: ∀ (Lê-se para todo ou qualquer que seja) 
Se voltarmos ao conjunto A = {5, 7, 8, 9, 11, 13}, podemos escrever a proposição “Qualquer que seja o elemento de 
A, ele é um número natural” usando a simbologia dos quantificadores universais deste modo: 
• ∀ x ∈ A / x é natural. 
É importante assinalar que os quantificadores universais “qualquer que seja”, “todo”, dentre outros, mostram a 
relação de inclusão de um conjunto em outro. De maneira geral o termo que vem logo após o quantificador revela 
o conjunto que esta contido num conjunto maior que vem após a citação deste primeiro. 
Assim na proposição “Todo homem é um ser racional”, o conjunto que contem todos os homens está 
contido no conjunto que contem todos os seres racionais. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
11 
 
 
Amplie seu conhecimento sobre quantificadores assistindo ao vídeo 
a seguir. 
http://tinyurl.com/msqb58b 
 
10.4. NEGAÇÃO DE PROPOSIÇÕES COM QUANTIFICADOR 
Vimos como negar proposições compostas com seus respectivos conectivos. Agora vamos abordar o modo 
como uma proposição com quantificador pode ser negada. 
Seja a proposição: 
P: “Todo físico é louco”. 
Dizer que a negação desta proposição é: “Todo físico não é louco” ou “nenhum físico é louco” é um erro 
comum para os iniciantes no estudo da lógica. 
Para se negar o quantificador “todo” que implica que todos os elementos do conjunto considerado estão incluídos 
na análise do argumento, basta que pelo menos um elemento deste conjunto não esteja incluído, sendo assim 
necessariamente não seria preciso que nenhum estivesse incluído, mas pelo menos um. 
Desta forma vale para a negação dos modificadores universais a equivalência: 
~(∀ x) (p) ⇔ (∃ x) (~p) 
 A negação de “todo x tem a propriedade p” é equivalente a “existe pelo menos um x 
que não possui a propriedade p” ou “nem todo x tem a propriedade p”. 
EXEMPLO 1 
Negue a seguinte afirmação: 
“Todos os alunos deste colégio são inteligentes” 
Resposta: “Pelo menos um dos alunos deste colégio não é inteligente” ou “Nem todos os alunos deste 
colégio são inteligentes” . 
Seja agora a proposição: 
Q: “Alguns filósofos são ateus”. 
Mais uma vez seria um erro afirmar que a negação de Q seria: “alguns filósofos não são ateus”. A negação 
correta de Q é: “Nenhum filósofo é ateu” ou “Todo filósofo não é ateu”. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
12 
Desta forma vale para a negação dos modificadores existenciais a equivalência: 
~(∃ x) (p) ⇔ (∀ x) (~p) 
 A negação de “existe pelo menos um x que tem a propriedade p” é equivalente a 
“todo x não possui a propriedade p” ou “não existe (nenhum) x que tem a propriedade p”. 
EXEMPLO 2 
 
Negue a seguinte afirmação: 
“Existe algum homem que foi à Lua” 
 
Resposta: “Todos os homens não foram à Lua” ou “Nenhum homem foi à Lua . 
Outros exemplos da negação de proposições com quantificadores universais e existenciais. 
a. P: Para todo x, temos x - 1≥ 5 
• P: Existe x tal que x – 1 < 5 
b. P: Todos os políticos não são honestos. 
• P: Pelo menos um político é honesto 
c. P: Alguns peixes respiram ar. 
• P: Nenhum peixe respira ar. 
d. P: Existe pelo menos um dia no ano que neva. 
• P: Todo dia do ano não neva. 
P ~P 
Todo gato é pardo Pelo menos um gato não é pardo 
Existe pelo menos um Sol a brilhar Todo Sol não brilha 
∃	x, x = 1 ∀ x, x ≠ 1 
∀	x, x > 1 ∃	x, x ≤1 
∃	x, x < 1 ∀ x, x ≥ 1 
 
 
Para entender mais sobre a negação de um quantificador assista ao vídeo 
a seguir. 
http://tinyurl.com/kaol7k9 
 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
13 
10.5. EXPRESSÕES EQUIVALENTES 
Como já visto uma proposição P é equivalente a uma proposição Q quando P ↔ Q for uma tautologia4. 
Analisemos as proposições abaixo: 
P: ∀ numero real x, se x é inteiro, então x é racional. 
Q: ∀ numero inteiro x, x é racional. 
Observe que P e Q têm o mesmo significado (todos os inteiros são racionais), indicando que P ⇔ Q.									 
			∀ x ∈ U, se P(x) então Q(x) ⇔ ∀ x ∈ D, Q(x), onde D é um subconjunto de um universo maior U. No 
exemplo dado o 𝕀	 ⊂ ℝ. 
EXEMPLO 3 
• ∀ polígonos p, se p é um quadrado, então p é um retângulo ⇔ ∀ quadrados p, p é um 
retângulo. 
• ∃ x ∈ U tal que P(x) e Q(x) ⇔ ∃ x ∈ D tal que Q(x) Neste caso, D consiste de todos os 
elementos de U que fazem P(x) verdadeiro. 
 
10.6. ARGUMENTOS E QUANTIFICADORES 
Quando tratamos de regras de inferências mostramos uma série de possibilidades que favorecem a análise 
de um dado argumento. Na lógica de predicados também existem ferramentas que facilitam a análise de 
um dado argumento trataremos de algumas delas. 
 
10.6.1. REGRA DA INSTANCIAÇÃO UNIVERSAL 
É uma regra de inferência válida a partir de uma verdade geral sobre cada elemento de um dado conjunto 
que conduz a uma verdade sobre um subconjunto do mesmo, ou seja, se uma propriedade é verdadeira 
para cada objeto no domínio então a propriedade é verdadeira para um objeto em particular do domínio. 
EXEMPLO 4 
• Todos os seres humanos são mortais; 
• Sócrates é um ser humano; 
• Logo, Sócrates é mortal. 
Instanciação universal é a ferramenta fundamental do raciocínio dedutivo. 
MODUS PONENS UNIVERSAL 
Observe o argumento: 
• Se x faz com que P(x) seja verdadeiro, então x faz com que Q(x) seja verdadeiro. 
 
4 Fórmula proposicional sempre verdadeira. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
14 
• a faz com que P(a) seja verdadeiro; então a faz com que Q(a) seja verdadeiro; 
∀ x, se P(x) então Q(x); 
P(a) para a em particular; 
Logo:Q(a) 
MODUS TOLLENS UNIVERSAL 
Observe o argumento: 
• Se x faz com que P(x) seja verdadeiro, então x faz com que Q(x) seja verdadeiro. 
 a não faz com que Q(a) seja verdadeiro; então a não faz com que P(a) seja verdadeiro; 
∀ x, se P(x) então Q(x); 
~Q(a) para a em particular; 
Logo: ~P(a) 
 
Aula 11 | REGRAS DE DEDUÇÃO: PARTICULARIZAÇÃO 
 
11.1. PARTICULARIZAÇÃO UNIVERSAL 
Essa regra diz que podemos deduzir P(x), P(y), P(a), etc. de (∀x)(P(x)), retirando seu quantificador universal. 
A justificativaintuitiva para esta regra e que se o predicado (ou formula) P e verdadeiro para todos os 
elementos do domínio, então podemos nomear um elemento qualquer deste domínio por um nome 
arbitrário de variável ou por um símbolo de constante que P continuara sendo verdadeiro para esta nova 
variável ou constante. 
A particularização universal pode ser usada para demonstrar um dos silogismos5 clássicos da Lógica 
Aristotélica, que foi a primeira lógica sistematizada na historia da humanidade, pelo filosofo grego 
Aristóteles, que viveu de 384 a 322 a.C. 
Vamos entender melhor sobre a regra da particularização universal com os seguintes exemplos: 
EXEMPLO 1 
• Todos os seres humanos são mortais. 
• Sócrates e um ser humano. 
• Logo, Sócrates e mortal. 
Esse exemplo já clássico em nossas aulas, pode ser “semi-formalizado” pelo seguinte esquema: 
• Todos os A, sao B. 
• a e um A. 
 
5 Designa uma argumentação lógica perfeita composta de várias idéias. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
15 
• Logo, a e um B. 
Usando a idéia a teoria dos conjuntos podemos ilustrar o que está ocorrendo de um modo fácil de 
entender. 
 
EXEMPLO 2: 
• Todas as árvores fazem fotossíntese. 
• A mangueira é uma árvore. 
• Logo, a mangueira faz fotossíntese 
Assim 
 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
16 
Estes argumentos semi-formais podem, então, ser aplicados a uma enorme gama de casos. A formalização 
completa deste tipo de argumento, em termos da Lógica de Predicados, pode ser feita de acordo com a 
seguinte formula: 
(∀x)(A(x) → B(x)), A(a) ⊢ B(a) 
que pode facilmente ser demonstrado por: 
1. (∀x)(A(x) → B(x)) 
2. A(a) 
3. A(a) → B(a) [Particularização universal] 
4. B(a) [2, 3, modus ponens6] 
 
Sobre a particularização universal, saiba mais assistindo ao vídeo a seguir. 
http://tinyurl.com/mlaleqt 
 
11.2. PARTICULARIZAÇÃO EXISTENCIAL 
Essa regra diz que, a partir de (∀x)(P(x)), podemos deduzir P(y), P(z), P(a), P(b), etc., desde que y, z, a, b, etc. 
sejam essencialmente símbolos novos. A justificativa intuitiva para esta regra e que se P e verdadeira para 
algum elemento do domínio, então podemos dar um nome especifico para ele, mas não podemos supor 
nada mais a seu respeito, isto e, nada nos impede de dar um (novo) nome a este suposto elemento “x” que 
satisfaz P(x). 
Observe o argumento abaixo. 
• Todas as motos têm motor. 
• Existe alguma moto. 
• Logo, uma Suzuki tem motor. 
Formalizando este argumento temos: 
(∀𝑥)(A(x) → B(x)), (∃y)A(y) ⊢ B(a) 
Que pode facilmente ser demonstrado por: 
1. (∀x)(M(x) → MO(x)) Hipótese 1 
2. (∃y)M(y) Hipótese 2 
3. M(a) 2, particularização existencial 
4. M(a) → MO(a) Aplicando a particularização universal em 3 e 1 
5. MO(a) Aplicando o modus ponens em 3 e 4 
Um detalhe importante em relação a esta demonstração e que os passos 3 e 4 não podem ser trocados de 
ordem por causa da restrição de aplicação da regra de particularização existencial. Se assim o fosse, ou 
 
6 Em latim significa modo de afirmar afirmando. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
17 
seja, se particularização universal tivesse sido usada primeiro sobre a hipótese7 1, então não haveria 
nenhuma razão para supor que este termo a particular e o que tem a propriedade P, como na hipótese 2. 
Portanto o efeito básico da restrição de uso desta regra e que você e obrigado, primeiro, a olhar todas as 
hipóteses e, se quiser usar a particularização existencial em alguma delas, tem que fazer isso primeiro. 
EXEMPLO 3 
Seja o silogismo: 
• Todos os A são B. 
• Existe algum A. 
• Logo, um fulano e B. 
Onde “fulano” indica alguém que não conhecemos, mas que sabemos certamente que “é B”. 
Este argumento pode ser totalmente formalizado por: 
(∀x)(A(x) → B(x)), (y)A(y) ⊢B(a) 
Dessa forma sua demonstração é: 
1. (∀x)(A(x) → B(x)) Hipótese 
2. (∃y)A(y) Hipótese 
3. A(a) 2, particularização existencial 
4. A(a) → B(a) 1, particularização universal 
5. B(a) 3, 4, modus ponens 
 
Sobre a particularização existencial,saiba mais assistindo ao vídeo a 
seguir. 
http://tinyurl.com/n3lzrzy 
A tabela abaixo sintetiza toda a idéia por trás das regras de inferência na lógica de predicados no que se 
refere às deduções particularizadas. 
REGRAS DE INFERENCIAS-DEDUÇÕES PARTICULARIZADAS 
De Podemos Deduzir Nome - Abreviatura Restrições Sobre o Uso 
(∀x)P(x) P(t), onde t é uma 
variável ou um símbolo 
constante 
Particularização 
universal – pu 
Se t for uma variável, não 
deve estar dentro do escopo 
de um quantificador para t. 
(∃x)P(x) P(t), onde t é uma 
variável ou um símbolo 
constante não utilizado 
anteriormente na 
Particularização 
existencial – pe 
É necessário que seja a 
primeira regra a usar t. 
 
7 Uma possibilidade. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
18 
demonstração 
 
Não desanime e siga com o estudo! 
Aula 12 | REGRAS DE DEDUÇÃO: GENERALIZAÇÃO 
 
Inicia-se aqui sobre as Regras de Dedução8. 
 
12.1. GENERALIZAÇÃO UNIVERSAL 
No estudo da lógica de predicados chama-se de generalização universal a uma inferência válida que 
consiste em se inserir um quantificador universal no argumento. No entanto, isso precisa ser feito muito 
cuidadosamente. Esta inserção somente pode ser feita se estivermos seguros que a sentença aberta P(x) é 
verdadeira e que a variável x, usada nesta sentença, indica um elemento realmente arbitrário, isto é “x” 
pode realmente ser qualquer elemento do dominio. Neste caso então nada nos impede de afirmar (∀x) 
(P(x)). Porem se existir alguma pressuposição na demonstração de que “x” é algum elemento específico do 
dominio (por exemplo, P(x) foi obtido por particularização existencial) então não podemos generalizar P(x) 
para (∀x) (P(x)). 
Para exemplificar essa afirmação, vamos provar o seguinte argumento: 
(∀x)(P(x) → Q(x)), (∀y) P(y) ⊢	(∀x) (Q(x)) 
Através da seguinte demonstração: 
1. (∀x)(P(x) → Q(x)) Hipótese 
2. (∀y)(P(y)) Hipótese 
3. P(x) → Q(x) 1, pu 
4. P(x) 2, pu (note que nao existe restricao em pu sobre usar 
novamente um mesmo nome) 
5. Q(x) 3, 4, Modus Ponens 
6. (∀x)(Q(x)) 5, gu 
Observe que a utilização da generalização universal no passo 6 é correta, uma vez 
que “x” não era uma variável livre em nenhuma hipótese, nem a particularização 
existencial (pe) foi utilizada para se chegar até Q(x). 
A primeira restrição da generalização universal evita que a utilização de alguma variável livre nas hipóteses 
possa ser usada como base para inferir uma propriedade universal. A afirmação em alguma hipótese de 
uma sentença aberta P(x) com a variável “x” pode tanto indicar que exista pelo menos um elemento do 
domínio que satisfaça P(x) quanto indicar que todos os elementos do domínio satisfazem P(x), mas não da 
nenhuma informação adicional, portanto não pode ser usada comobase de uma generalização correta. 
A segunda restrição apenas evita que o formalismo desconsidere o significado por trás da operação de 
generalização, isto e, se nós chegamos a um P(x) numa demonstração com base numa particularização de 
um existencial, isto implica que estamos seguros que existe pelo menos um elemento do dominio no qual 
 
8Conclusão atingida. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
19 
vale P(x). Desta forma não faz nenhum mal em chamarmos este elemento de “x”, mas não podemos, dai, 
inferir que qualquer outro elemento do dominio também atenda a sentença P(x), logo e impossível 
generalizar este P(x) para (∀x)(P(x)). Do ponto de vista puramente formal isto e evitado pela restrição que 
obriga que P(x), para ser generalizado universalmente, não possa ter sido previamente demonstrado por 
uma particularização existencial. 
Para exemplificar o uso de regras hipotéticas no caso da lógica de predicados, vamos provar o seguinte 
argumento: 
P(x) → (∀x)(Q(x,y)) ⊢ (∀y) ( P(x) → (Q(x,y)) ) 
Demonstração: 
1. P(x) → (∀x)(Q(x,y)) Hipótese 
2. P(x) Hipótese 
3. (∀x)(Q(x,y)) 1, 2 modus ponens 
4. Q(x,y) 3 particularização universal 
5. P(x) → Q(x,y) 2-4 pc 
6. (∀y)( P(x) → Q(x,y) ) 5, generalização universal 
c.q.d.9 
 
Conheça um pouco mais sobre generalização universal no link a seguir. 
http://tinyurl.com/mfg22j3 
 
12.2. GENERALIZAÇÃO EXISTENCIAL 
Ainda dentro das regras de dedução temos a chamada regra da generalização existencial que permite a 
inserção de um quantificador existencial. De P(x) ou P(a), podemos deduzir (∃x)(P(x)). A justificativa 
intuitiva para esta regra e que se alguma coisa já foi nomeada como tendo a propriedade P, então 
podemos afirmar que existe algum outro objeto com a propriedade P, logo (∃x)(P(x)). 
Para exemplificar, vamos provar o argumento: 
(∀x)(P(x)) ⊢ (∃x)(P(x)) 
Demonstração: 
1. (∀x)(P(x)) Hipótese 
2. P(x) 1, particularização universal 
3. (∃x)(P(x)) 2, generalização existencial 
c.q.d. 
A restrição da generalização existencial tem uma base similar a da restrição empregada na particularização 
universal. Ela serve para evitar que, por exemplo, de formulas similares a P(a,y) possamos deduzir 
(∃y)(P(y,y)), o que não seria valido. Novamente é fácil mostrar um contra-exemplo que mostre isto, 
observe: 
 
9 Como queríamos demonstrar. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
20 
Vamos assumir que P(x,y) significa x < y no dominio dos números naturais, então P(a,y) pode ser verdade 
(para algum a e para algum y), enquanto que (∃y)(P(y,y)) e obviamente falsa, já que é impossível que y < y 
para qualquer y pertencente aos números naturais. 
 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
21 
EXEMPLOS 
a. Totó adora pular no sofá. 
Logo, Existe algo que adora pular no sofá. 
b. Os cachorros amam andar na rua. 
Logo, existe algum animal que ama andar na rua. 
c. Gatos amam abanar o rabo. 
Logo, algo ama abanar o rabo. 
d. Frutas caem no chão. 
Logo, alguma maça cai no chão. 
e. Os seres humanos vivem no Planeta Terra. 
Logo, existe algum Marcos que vive no Planeta Terra. 
 
Saiba mais sobre generalização existencial na lógica de predicados na 
pagina a seguir. 
http://tinyurl.com/knwvztm 
A tabela abaixo será útil para memorizar as regras de generalização universal e generalização existencial. 
REGRAS DE INFERENCIAS-DEDUÇÕES GENERALIZADAS 
De Podemos Deduzir Nome - Abreviatura Restrições Sobre o Uso 
P(t), onde t é 
uma variável 
(∀x)P(x) 
 
Generalização 
universal – gu 
1. A variável t não pode ter 
sido obtida através de uma 
pe. 
2. P(t) não pode ter sido 
deduzida de nenhuma 
hipótese na qual t é uma 
variável livre. 
3. P(t) não pode ter sido 
deduzida, através de pe, de 
uma fbf na qual t é uma 
variável livre 
P(t), onde t é 
uma variável ou 
um símbolo 
constante 
(∃x)P(x) Generalização 
existencial – ge 
Para ir de P(t) a (∃x)P(x), 
x não pode aparecer em 
P(t). 
 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
22 
Aula 13 | DEMONSTRAÇÃO 
 
Desde o inicio de nosso curso, “Fundamentos da Lógica”, temos tratado de afirmações cuja valoração pode ser 
apena ou verdadeira (V) ou falsa (F). Nesta última unidade abordaremos sobre dois modos de se verificar a 
veracidade de uma proposição, uma que utilizada um método mais forte chamada de dedução e outra que trata 
de um método um tanto mais fraco, mas que não deixa de ser importante chamada de indução. 
Trataremos inicialmente nesta aula e nas duas seguintes sobre a dedução por demonstração iluminados por 
alguns métodos bastante utilizados para se demonstrar a veracidade de algo e na ultima aula desta 
unidade trataremos da indução e de como utilizá-la. 
 
13.1. CONCEITOS 
Chamamos de demonstração a um raciocínio que torna evidente o caráter verídico de uma premissa, idéia 
ou teoria. Demonstração, portanto, é uma dedução destinada a provar a verdade de uma conclusão 
apoiando-se sobre premissas reconhecidas ou admitidas como verdadeiras. 
Na demonstração utilizam-se letras e outros sinais que constituem uma linguagem abstrata e simbólica, 
fazendo da linguagem demonstrativa uma linguagem perfeita, inequívoca em que cada signo corresponde a 
um só significado. 
Por se fundamentar na precisão, exatidão, eficácia e simplicidade a linguagem demonstrativa é utilizada em 
várias áreas do conhecimento humano tais como: nas ciências lógicas dedutivas (matemática e lógica), 
informática, robótica, etc. 
A demonstração, que por vezes é chamada de “prova” esta estreitamente ligada à 
Lógica, que possui um ramo que a tem por objeto de estudo. 
Quando tratamos de demonstrações alguns termos tem especial relevância em nosso estudo, são eles: as 
definições, os axiomas, os teoremas e as conjecturas 
 
Definições: Chamamos de definição um enunciado que descreve o significado de um 
termo de forma imutável e incontestável. Se no mundo das palavras os termos podem 
ser unívocos (um só significado), equívocos (ter dois ou mais significados diferentes) e 
análogos (termos com significados semelhantes), no estudo da lógica matemática 
prima-se pela clareza e precisão dos termos, uma vez que essa clareza e precisão será 
a base para se realizar uma demonstração irrefutável. 
Exemplos: 
a. Significado de linha, segundo Euclides: “Linha é o que tem comprimento e não tem largura”. 
b. Significado de átomo: “Unidade básica da matéria”. 
c. Significado de número: “Objeto matemático que representa uma quantidade”. 
 
Axiomas: Chamamos de axioma, também chamado de postulado a uma sentença que é 
assumida como verdadeira e universalmente inquestionável sem que haja necessidade 
de se provar sua veracidade, já que um axioma é uma proposição tida por óbvia. Os 
postulados são muitas vezes utilizados na construção de uma teoria ou como o ponto 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
23 
de partida para deduções e inferências. 
Exemplos: 
a. Pode-se traçar umaúnica linha reta entre dois pontos distintos. 
b. Todos os ângulos retos são iguais. 
c. Pode-se traçar um círculo com qualquer centro e com qualquer raio 
d. Para todo natural x, x = x. 
e. Para todos os números naturais x, y, e z, se x = y e y = z, então x = z. 
 
Teoremas: Chamamos de teorema a uma afirmação que não é obvia, mas que 
precisa ser provada, utilizando-se para isso outros teoremas já provados, bem 
como alguns axiomas. Esse termo foi elaborado por Euclides, filósofo grego que 
viveu no século III a.C, e significa exatamente afirmação que pode ser provada. 
Exemplos: 
a. Teorema de Pitágoras. (a2 = b2 + c2) 
 
Conheça um método de se provar o teorema de Pitágoras assistindo ao 
vídeo a seguir. 
http://tinyurl.com/m4ftesf 
b. Teorema fundamental da Álgebra (Toda equação polinomial p(x) = 0, de grau n onde n ≥ 1, admite 
pelo menos uma raiz complexa) 
 
Para saber mais sobre teorema fundamental da álgebra assista ao vídeo: 
http://tinyurl.com/lrz9uuo 
c. Teorema de Tales. (Quando duas retas transversais cortam um feixe de retas paralelas, as medidas 
dos segmentos delimitados nas transversais são proporcionais) 
d. Teorema Fundamental da Trigonometria (sen2 (x) + cos2 (x) = 1) 
 
Conjecturas: Chamamos de conjecturas a uma proposição que não foi provada 
nem refutada, por isso toda conjectura é uma hipótese que se assume verdadeira, 
mas que precisa de demonstração. 
Exemplos: 
1. Conjectura dos primos gêmeos. (Esta conjectura diz que existem infinitos números primos gêmeos.) 
Um par de primos é chamado de primos gêmeos se eles são dois números primos “p” 
e “q” tais que q = p + 2. (Exemplos: 5 e 7, 17 e 19). 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
24 
2. Conjectura de Goldbach (Essa conjectura diz que todo numero par maior ou igual a 4 é resultado da 
soma de dois números primos como nos casos: 4 = 2 + 2, 10 = 5 + 5, 21 = 19 + 2, etc.) 
Um número primo é aquele que no conjunto dos números naturais admite apenas 
dois divisores, o número 1 e ele mesmo. 
O esquema abaixo resume o que fico dito acima a cerca das demonstrações. 
 
 
13.2. RACIOCÍNIO DEDUTIVO X INDUTIVO 
Das várias formas de se desenvolver um raciocínio correto podemos destacar dois 
métodos: o método indutivo e o método dedutivo. 
O método indutivo é um tipo de raciocínio que assume o futuro como repetição de algo que ocorreu no 
passado. Esse método descreve em geral um tipo de raciocínio que tem em comum o fato de não 
garantirem a veracidade das conclusões obtidas. 
Exemplo. 
a. P1: O pato branco faz qua, qua. 
P2: O pato preto também faz qua, qua. 
C: Logo, todos os patos fazem qua, qua 
O raciocínio indutivo pode levar a erros graves ou no mínimo situações de graves perigos. Veja a situação: 
 “Meu amigo sempre nada naquele rio infestado de piranhas, mas nunca foi atacado 
por elas. Então, eu vou nadar nesse rio e não serei atacado.” 
O raciocínio acima é indutivo, pois parte de uma particularidade e se conclui algo geral, por mais temerário 
e pouco prudente que seja a conclusão. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
25 
Já o método dedutivo, é um modo de raciocinar cuja seqüência de premissas conduz de forma segura a 
uma verdade pura, assim partindo de algumas verdades anteriores temos a certeza de chegar a uma 
conclusão verdadeira. 
Dos vários métodos dedutivos que conduzem a uma demonstração incontestável. 
Apresentaremos e discutiremos quatro técnicas de demonstração muito utilizadas, a saber: 
• A demonstração por contraposição 
• A demonstração exaustiva 
• A demonstração direta 
• A demonstração por absurdo 
 
Mas isso fica para as próximas aulas. 
 
Aula 14 | TÉCNICA I 
 
14.1. DEMONSTRAÇÃO POR CONTRAPOSIÇÃO 
Ao estudarmos equivalência entre proposições compostas vimos que duas proposições “P” e “Q” são 
equivalentes quanto P ↔ Q for uma tautologia, ou seja, quando as tabelas-verdade de P e Q forem iguais. 
Um caso que foi tratado em nosso estudo e que retomaremos agora é a equivalência por contraposição. 
(p→ q) ⇔ (~q→ ~p) 
Assim se não “q implica em não p” (~q ⇒ ~p) for verdadeira, então “p ⇒ q” também será verdadeira. Desta 
forma para provarmos que a conjectura: “se p, então q”, basta provarmos que “se não q, então não p”. 
A técnica da demonstração por contraposição será uma possibilidade quando para se provar uma 
conjectura do tipo “P→ Q” a mesma não for atingida por uma demonstração direta. 
Vejamos alguns exemplos de demonstração por contraposição. 
a. Demonstre que, se n2 é par, então n é par. 
Importante: Um número inteiro n é dito par se 2 divide n, ou seja, se existe número 
inteiro k tal que n = 2k, portanto, n é múltiplo de 2 e número inteiro b é dito ímpar 
se 2 não divide b, nesse caso pode-se provar que existe um número inteiro k tal que 
b = 2k + 1. 
 
 
Para conhecer mais sobre a paridade numérica assista ao vídeo: 
http://tinyurl.com/mglayru 
 
 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
26 
Passo 1: Escreva a proposição em linguagem simbólica. 
p: n2 é par 
q: n é par 
Se n2 é par ⇒ n é par: (p → q) 
Passo 2: Escrever a contrapositiva. 
Contrapositiva: n é ímpar ⇒ n2 é ímpar. 
Hipótese (conjectura): n é ímpar. 
Tese (conclusão): n2 é ímpar. 
Passo 3: Demonstração 
Demonstração: Como n é ímpar, n = 2k + 1 para algum inteiro k. 
Logo, 
n2 = (2k + 1)2 = 4k2 + 4k + 1 
Colocando 2 em evidencia ficamos com: 
n2 = 2(2k2 + 2k) + 1 
Chamando (2k2 + 2k) de w, com ∈ 	𝕫, temos que 
n2 = 2w + 1 
Portanto, n2 é ímpar. 
b. Sejam n e m números inteiros para os quais n + m é par demonstre, então que n e m tem a 
mesma paridade. 
Passo 1: Escreva a proposição em linguagem simbólica. 
p: n + m é par 
q: n e m tem a mesma paridade 
Se n + m é par	⇒ n e m tem a mesma paridade: (p → q) 
Passo 2: Escrever a contrapositiva. 
Contrapositiva: n e m tem a paridade diferentes ⇒ n + m é ímpar. 
Hipótese (conjectura): n e m tem a paridade diferentes. 
Tese (conclusão): n + m é ímpar. 
Passo 3: Demonstração 
Importante: A soma de dois números pares ou de dois números ímpares resulta num 
número par. Mais a frente provaremos essa afirmação. 
Demonstração: Pela hipótese, um dos números é par, e o outro é ímpar. Apenas por motivo de 
simplicidade e sem prejuízo para a demonstração escolhemos n = 2k e m = 2w + 1, para k e w inteiros. 
Logo, 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
27 
n + m = 2k + 2	w + 1 
Colocando 2 em evidencia ficamos com: 
n + m = 2(k + w) + 1 
Chamando (k + w) de h, com h ∈ 	𝕫, temos que: 
n + m = 2 h + 1 
Portanto n + m é ímpar. 
 
14.2. DEMONSTRAÇÃO EXAUSTIVA 
Chama-se de demonstração por exaustão aquela que “testa” todas as possibilidades (finitas) da conjectura 
verificando a validade de todos os elementos da coleção. Para provar a falsidade da conjectura, basta achar 
um contra-exemplo. 
Veja os exemplos abaixo: 
a. Prove que se n é um número inteiro e 0 ≤ 𝑛	 ≤ 20	, então n! ≤ n2 (O fatorial de n é menor ou igual 
ao quadrado de n) 
Importante: Chamamos fatorial de um número natural n, representado por n! o produto de 
todos os inteiros positivos menores ou iguais a n. vale destacar que por definição 0! = 1 e 1! 
= 1. 
Exemplo: 
5! ( Lê-se cinco fatorial ou fatorial de cinco) = 5 . 4 . 3 . 2 . 1 = 120 
 
 
Conheça mais sobre o fatorial de um número natural assistindo ao vídeo 
no link a seguir. 
http://tinyurl.com/kceyep9 
A demonstração exige que todos os elementos do conjunto n sejam averiguados, então: 
• Para n = 0, temos 
0! ≤ 02 (verdadeiro) 
• Para n = 1, temos 
1! ≤ 12 (verdadeiro) 
• Para n = 2, temos 
2! ≤ 22 (verdadeiro), pois 2 . 1 ≤ 2 . 2• Para n = 3, temos 
3! ≤ 32 (verdadeiro), pois 3 . 2 . 1 ≤ 3 . 3 
• Para n = 4, temos 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
28 
4! ≤ 42 (falso), pois 4 . 3 . 2 . 1 ≤ 4 . 4 
Conclusão: a conjectura é falsa 
b. Prove que se um inteiro entre 1 e 20 é divisível por 6, então também é divisível por 3 . 
Demonstração: Como existe um número finito de casos, a conjectura pode ser provada simplesmente 
mostrando-se que é verdadeira para todos os inteiros entre 1 e 20. 
Números Divisível por 6 Divisível por 3 
1 Não Não 
2 Não Não 
3 Não Sim, pois 3/3 = 1 
4 Não Não 
5 Não Não 
6 Sim, pois 6/6 = 1 Sim, pois 6/3 = 2 
7 Não Não 
8 Não Não 
9 Não Sim, pois 9/3 = 3 
10 Não Não 
11 Não Não 
12 Sim, pois 12/6 = 2 Sim, pois 12/3 = 4 
13 Não Não 
14 Não Não 
15 Não Sim, pois 15/3 = 5 
16 Não Não 
17 Não Não 
18 Sim, pois 18/6 = 3 Sim, pois 18/3 = 6 
19 Não Não 
20 Não Não 
Dessa forma, esgotado todas as possibilidades, temos que os números 6, 12 e 18 são divisíveis por 6 e 
também é divisível por 3. Logo todos os números inteiros entre 1 e 20 que são divisíveis por 6 são também 
divisíveis por 3. 
 Conclusão: A conjectura é verdadeira. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
29 
 
Aula 15 | TÉCNICA II 
 
15.1. DEMONSTRAÇÃO DIRETA 
Dos modos de se realizar uma demonstração a chamada, demonstração direta, é a forma mais simples de 
se realizar uma prova e a mais obvia. Para esta demonstração mostra-se que todas as situações que 
satisfazem a hipótese P também satisfazem a tese Q. uma vez feito isso temos que a sentença “ se P, 
então Q” é verdadeira, pois ela não possui contra exemplos. Resumidamente, para demonstrar que P ⇒ Q 
assumimos que P é verdadeiro, e através de uma série de etapas, cada uma seguinte das anteriores 
podemos concluir Q. 
Vejamos alguns exemplos que se aplica a demonstração direta. 
a. Provemos que, se n e m são números pares, então n + m também é par, ou seja, a soma de dois 
números pares resulta num numero par. 
Passo 1: Escrever a proposição composta em linguagem simbólica. 
p: n e m são números pares. 
q: n + m também é par. 
p → q 
Conjectura: n e m são números pares. (Dado assumido como sendo verdade) 
Tese: n + m também é par. 
Passo 2: Realizar a demonstração. 
Como n e m são pares, então 3, n = 2k e m = 2w, onde k e w são números inteiros. 
Logo, 
n + m = 2k + 2	w = 2(k +	w) 
Assim como n + m é múltiplo de 2, então n + m é par. 
b. Provemos que, se n e m são números ímpares, então n + m também é par, ou seja, a soma de dois 
números impares resulta num numero par. 
Passo 1: Escrever a proposição composta em linguagem simbólica. 
p: n e m são números ímpares. 
q: n + m também é par. 
p → q 
Conjectura: n e m são números ímpares. (Dado assumido como sendo verdade) 
Tese: n + m também é par. 
Passo 2: Realizar a demonstração. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
30 
Como n e m são pares, então 3, n = 2k + 1 e m = 2w	+ 1, onde k e w são números inteiros. 
Logo, 
n + m = 2k + 1 + 2	w	+ 1 = 2(k +	w	+ 1) 
Assim como n + m é múltiplo de 2, então n + m é par. 
c. Demonstre que o quadrado de um número ímpar é um número ímpar. 
Passo 1: Escrever a proposição composta em linguagem simbólica. (Observe que a 
proposição acima está implicitamente indicando uma condicional cujo sentido é: “Se n é 
ímpar, então n2 é um número ímpar) 
p: n é ímpar. 
q: n2 é ímpar. 
p → q 
Conjectura: n é ímpar. (Dado assumido como sendo verdade) 
Tese: n2 é ímpar. 
Passo 2: Realizar a demonstração. 
Como n é ímpar, então temos que n = 2k + 1 para qualquer k pertencente ao conjunto dos 
números inteiros. 
Assim, 
n2 = (2k + 1)2 = 4k2 + 4k + 1 
Colocando 2 em evidencia ficamos com: 
n2= 2(2k2 + 2k) + 1 
Chamando (2k2 + 2k) de w ficamos com 
n2 = 2	w	+ 1 
Portanto, n2 é ímpar. 
 
 
Acesse o link a seguir e aprenda mais sobre o método da demonstração 
direta. 
http://tinyurl.com/lekjeqd 
 
15.2. DEMONSTRAÇÃO POR ABSURDO 
Uma demonstração por absurdo consiste em se demonstrar que a falsidade da afirmação produziria um 
absurdo. Mais precisamente, no caso de uma implicação H ⇒ T, uma demonstração por absurdo consiste 
em, supondo a validade de H, mostrar que a não validade de T produz um resultado contraditório ou 
absurdo. Dizendo de outro modo: o objetivo é mostrar que a combinação da validade da hipótese H com a 
não validade da tese T produz um resultado absurdo. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
31 
Um exemplo clássico do uso desse método foi realizado por Aristóteles para prova que √2 era um número 
irracional. 
Analisemos essa demonstração. 
Seja a = √2 prove que a é irracional. 
Passo 1: Escrever a proposição composta em linguagem simbólica. 
P: s =	√2 
Q: é irracional 
P ⇒ Q 
Passo 2: Demonstração 
Suponha, por absurdo, que √2 é racional. Portanto, seria possível encontrar números 
inteiros a, b, com b ≠ 0, tais que √2 poderia ser representado como uma fração irredutível :
;
 
. A partir disto, podemos afirmar que: 
√2 = :
;
, 
Elevando esta igualdade ao quadrado temos 
(√2)2 = <:
;
=
>
 
2 = :
?
;?
 
Daí 
2b2 = a2 
Já demonstramos que o quadrado de um número par é um numero par, logo a2 é par. Como 
a é par, a = 2k, para algum k inteiro, daí temos que: 
2b2 = (2k)2 = 4k2 (÷ 2) 
b2 = 2k2 
Disto concluímos que b também é par. Mas isto é uma contradição, pois se a e b são pares, a fração 
irredutível :
;
 poderia ser reduzida, um absurdo, pois :
;
 já era uma fração irredutível. 
Exemplo 2: Demonstre que existem infinitos números primos. 
Vamos supor que Hipótese: “existe uma quantidade finita de números primos” seja verdadeira. 
Vejamos até onde ela nos leva. Por esta hipótese, há apenas 
n números primos, onde n é inteiro. Podemos colocar os primos em ordem p1, p2, . . . , pn em 
ordem, de tal forma que: 
p1 < p2 < . . . < pn. 
Com isto, teríamos que pn é o maior primo de todos. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
32 
Considere o número p1 · p2 · . . . · pn + 1. Ele não é divisível por nenhum dos primos p1, p2, . . . , pn, portanto 
ele também é primo e, além disso, é maior do que todos os demais números primos, incluindo pn. Mas isto 
contradiz a afirmação de que pn é o maior primo de todos, o que é um absurdo! 
Portanto, existem infinitos números primos. 
 
 
Aprofunde seus conhecimentos sobre o método da demonstração por 
absurdo pelo vídeo a seguir. 
http://tinyurl.com/lbozfqc 
 
Aula 16 | INDUÇÃO 
 
16.1. CONCEITOS 
 
O termo indução é utilizado para designar qualquer processo de raciocínio que 
nos conduza de premissas empíricas a conclusões empíricas, que, apesar de 
apoiadas pelas premissas, não são dedutivamente deriváveis delas. 
 
Desta forma induzir é passar de algum conjunto de hipóteses para uma conclusão 
que é compatível com essas hipóteses mas não podem ser deduzidas delas. 
Por exemplo, seria natural induzir do estudo dos mamíferos que não há mamíferos que nasçam em ovos e 
que em todos eles as fêmeas amamentam seus filhotes. Contudo apenas a segunda das conclusões é 
verdadeira, pois os ornitorrincos e os equidnas são ovíparos. 
 
16.2. PRINCÍPIOS 
Dado um subconjunto S do conjunto dos números naturais ℕ, tal que 1 pertence a S e sempre que uma 
numero n pertence a S, o número n + 1 também pertence a S, assim temos que S = ℕ. 
Esta simples propriedade fornece uma das mais poderosas técnicas de demonstração em matemática, 
assim chamada de demonstração por indução. 
Usando a notação P(n) para dizer que o inteiropositivo n tem a propriedade P 
precisamos provar as seguintes proposições: 
1. P(1) - (1 tem a propriedade P) 
2. Para qualquer inteiro positivo k, P(k) →P(k+1) – Se qualquer número tem a propriedade P, o 
próximo também tem. 
Se pudermos provar ambas as proposições 1 e 2, então P(n) é válida para qualquer inteiro positivo n. O 
fundamento para argumentos desse tipo é o primeiro princípio de indução matemática. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
33 
Primeiro Princípio de Indução 
1. P(1) 
2. (∀k) [P(k) verdade → P(k+1) verdade 
O primeiro princípio de indução matemática é um condicional, com uma conclusão na forma 
“P(n) é verdade para todo inteiro positivo n”. 
 
16.3. INDUÇÃO MATEMÁTICA 
Nas ciências naturais, utiliza-se a indução empírica. Ou seja, a partir de um grande número de observações 
particulares selecionadas adequadamente, formulam-se leis que devem reger determinados fenômenos. 
Foi desse modo que por volta do século XVII, o físico Galileu Galilei, ao introduzir o método experimental, 
chegou à conclusão de que quando dois corpos de massas diferentes, desprezando a resistência do ar, são 
abandonados da mesma altura, ambos alcançam o solo no mesmo instante. 
A validade de um teorema matemático, no entanto, se estabelece de forma completamente diferente. 
Verificar que certa afirmação vale para um grande número de casos particulares (como se faz nas ciências 
naturais) não permitirá concluir que esta afirmação é válida. O princípio da indução completa (ou método 
da recorrência) é utilizado para provar que a proposição vale para todos os casos (ou seja, na verdade há 
uma proposição para cada caso, freqüentemente um número infinito de casos). 
Para entendermos como devemos proceder para realizar uma demonstração indução válida retomemos ao 
primeiro principio da indução: 
1. P(1) 
2. (∀k) [P(k) verdade → P(k+1) verdade 
Para mostrar que a conclusão dessa condicional é verdadeira, precisamos provar que as hipóteses 1 e 2 
também o são. 
Para provar a proposição 1, basta mostrar que o número 1 tem a propriedade P, o que pode ser trivial . 
Esse primeiro passo é chamado de “base da Indução”. 
A proposição 2 é um condicional que tem que ser válido para todo k (Passo da Indução). 
Para provar essa condicional, suponha que P(k) (Hipótese da Indução) é verdade para um inteiro positivo k 
e mostre que, baseado nesta hipótese, que p(k+1) é verdade. 
Resumo 
1. Passo 1 – Prove a base da indução P(1) (ou o menor inteiro positivo em questão. 
2. Passo 2 – Suponha P(k) 
3. Passo 3 – Prove P(k+1) 
 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
34 
Observe os exemplos de demonstrações por indução nos casos abaixo: 
a. Demonstre que, para qualquer n ∈ 	ℕ, 2n > n. 
Passo 1. Base da indução: 
Para n = 1 temos que P(1) = 21=2, então 2>1 (verdadeira) 
Passo 2. Hipótese da indução: 
Supondo que para algum k inteiro positivo, P(k): 2k > k é verdadeira. 
Passo 3. Passo da indução: 
Provar que para P(k+1): 2k+1> k+1 é verdadeira. 
Demonstração: Como P(k): 2k > k e P(k+1): 2k+1> k+1, então, à esquerda da desigualdade 
temos que: 
2k+1= 2k.21 
Pela hipótese de indução 2k > k. Multiplicando ambos os membros dessa desigualdade por 
2, temos que: 
2k.21 > k.2 
Agora como 
k.2=k+k, e k+k ≥ k+1, 
Concluímos que: 
2k+1> k+1 
 
 
Tire suas dúvidas sobre este exemplo assistindo ao vídeo no link a seguir. 
http://tinyurl.com/lhdo4d3 
 
Importante: O primeiro passo de uma demonstração por indução não é necessariamente 
obrigado ser P(1). Podemos começar por P(0) ou por outro valor. 
a. Prove que n2 > 3n, para n ≥4. 
Nesse caso, é melhor começar a base da indução em P(4). 
Passo 1. Base da indução 
P(4): 42> 3(4) é verdadeira 
Passo 2. Hipótese da indução 
k2 >3k, para k ≥4 
Passo 3. Queremos mostrar que: 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
35 
 (k+1)2 > 3(k+1) 
Como 
(k+1)2 = k2+ 2k + 1 > 3k + 2k +1 (pela hipótese da indução) ≥ 3k + 8 + 1 (pois k ≥ 4) > 3k + 3 = 
3(k+1) 
Portanto P(k+1): (k+1)2 > 3(k+1) 
Em algumas situações, ao tentarmos fazer uma demonstração por indução, na passagem de n para n + 1, 
sentimos necessidade de admitir que a proposição valha não apenas para n e sim para todos os números 
naturais menores do que ou iguais a n. 
A justificativa de um raciocínio desse tipo se encontra no: Segundo Princípio da 
Indução ou Princípio da Indução Forte. 
 
Seja P(n) uma proposição sobre A={n ϵ IN; n ≥ a, a nϵ IN}, o princípio da indução forte pode 
ser definido como segue: 
a. P(a) é verdadeira. 
b. Para todo n tal que a ≤ n≤ k vale P(n)→P(k+1). 
c. Então para qualquer n ϵ A, P(n) é verdadeira. 
Para provar que todo número natural n, pertencente ao conjunto A, tem determinada propriedade, usando 
a indução forte em n, devemos: 
• Mostrar que P(a) é verdadeira (base de indução). 
• Supor que para todo n tal que a ≤ n≤ k vale P(n) (hipótese de indução). 
• Mostrar que P(k+1) usando o fato de que para todo n tal que a ≤ n≤ k vale P(n) (passo de indução). 
Exemplo: Prove que: “Todo número natural maior ou igual a 2 pode ser decomposto num produto de 
números primos”. 
Prova (por indução forte em n): Seja n ≥ 2. 
Base de indução: Para n=2 existe uma decomposição trivial em números primos já que 2 é , ele próprio um 
número primo. 
Hipótese de indução: Suponha que a afirmação seja verdadeira para n=2,3,4,...,k 
Passo de indução: Seja n=k+1. 
Se k+1 é um número primo a decomposição é trivial já que k+1 é , ele próprio um número primo. 
Suponha que k+1 não é primo, então existem a e b ϵ IN tal que k+1=a.b 
Como: 
a < k + 1 e b ≤ k + 1. 
Pela hipótese de indução a e b podem ser decompostos num produto de números primos e como k + 1 = 
a.b então k+1 pode ser decomposto num produto de números primos. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
36 
 
Conclusão: Portanto todo número n ϵ IN, n ≥ 2 pode ser decomposto num produto de números primos. 
 
Aprenda mais sobre este assunto assistindo ao vídeo do link a seguir. 
http://tinyurl.com/n5wmgtw 
 
 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
37 
REFERÊNCIAS 
 
ALENCAR FILHO, Edgard de. Iniciação à lógica matemática. São Paulo: Nobel, 2002. 
 
GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação: um Tratamento Moderno 
de Matemática Discreta. 5. ed. Rio de Janeiro: LTC, 2008. 
 
JÚNIOR, Nilo. Raciocínio Lógico. INEC Concursos, s/d. 
 
PAIVA, Manoel. Matemática 1. Vol 1. São Paulo: Moderna, 1995. 
 
QUILELLI, Paulo. Raciocínio Lógico CESPE. Rio de Janeiro: Quileditora, 2009. 
 
SILVA, Flávio Soares Corrêa da; FINGER, Marcelo; MELO, Ana Cristina Vieira de. Lógica para Computação. 
São Paulo: Thomson Learning, 2006. 
Complementar 
ABE, Jair Minoro e SCALZITTI, Alexandre e SILVA FILHO, João Inácio da. Introdução a lógica para a ciência 
da computação. 2. ed. São Paulo: Arte & Ciência, 2002. 
 
HUTH, Michael e RYAN, Mark. Lógica em Ciência da Computação: modelagem e argumentação sobre 
sistemas, 2. ed. Rio de Janeiro: LTC, 2008. 
 
KELLER, Vicente e BASTOS, Cleverson Leite. Aprendendo lógica. 18. ed. Petrópolis,RJ: Vozes, 2009. 
 
SMULLYAN, Raymond M. Lógica de Primeira Ordem. São Paulo: [s.n.]; [S.l.]: UNESP: Discurso Editorial; [S.l.: 
s.n.], 2002, 2009. 
 
SOUZA, João Nunes de. Lógica para ciência da computação: fundamentos de linguagem, semântica e 
sistemas de dedução. 2. ed. Rio de Janeiro: Elsevier, 2002. 
 
GLOSSÁRIO 
 
Argumento: Uma afirmação seguida de uma justificativa. 
c.q.d.: Como queríamos demonstrar.Dedução: Conclusão atingida. 
Empírica: É um fato que se apoia somente em experiências e observações 
Hipótese: Uma possibilidade. 
Modus Ponens: Em latim significa modo de afirmar afirmando. 
Múltiplo: Diz-se do número que é exatamente divisível por outro sem deixar resto, ou daquele que contém 
outro uma porção exata de vezes. 
Números primos: No conjunto dos números reais número primo é aquele divisível por 1 e por ele mesmo. 
 LÓGICA, ALGORITMOS E PROGRAMAÇÃO DE COMPUTADORES | UNIDADE 2 | 
Copyright © 2019 Centro Universitário IESB. Todos os direitos reservados. 
38 
Ovíparos: Ovíparos são aqueles cujo embrião se desenvolve dentro de um ovo em ambiente externo sem 
ligação com o corpo da mãe. 
Paridade: Refere-se aos números pares e impares 
Premissas: Equivalente à proposição 
Quantificadores: Termos utilizados para quantificar elementos de um dado conjunto. 
Silogismo: Designa uma argumentação lógica perfeita composta de várias idéias. 
Subconjunto: Uma fração do todo. 
Tautologia: Fórmula proposicional sempre verdadeira.