201981_203122_Apostila+de+logica

Prévia do material em texto

URI – Universidade Regional Integrada
Campus de Erechim
Curso de Ciência da Computação
Apostila de Lógica para a Computação
Prof. Neilor Tonin
Erechim, 8 de agosto de 2016
 Apostila de Lógica para a computação 2 
Cálculo Proposicional
 
1. Proposição:
Chama-se sentença ou proposição todo o conjunto de palavras ou símbolos que exprimem um pensamento de sentido
completo. Sentença ou proposição se distinguem do nome, o qual designa um objeto.
Exemplos de nomes:
 Pedro.
 O cão do menino.
 4 – 3
Exemplos de proposições:
1. A lua é um satélite da terra.
2. O filho do Presidente do Brasil, em 1970, era médico.
3. 3 x 5 = 5 x 3
4. Onde você mora?
5. Que belo jardim é o desta praça!
6. Escreva um verso.
7. Pedro estuda e trabalha.
8. Duas retas de um plano são paralelas ou incidentes.
9. Se Pedro estuda, então tem êxito na escola.
10. Vou ao cinema se e somente se conseguir dinheiro.
Na lógica, restringimo-nos a uma classe de proposições, que são as declarativas e que só aceitam dois valores: Verdadeiro
(V) ou r falso (F), um excluindo o outro. Assim, excluímos de nossas considerações:
- Proposições exclamativas, como a de nº 5.
- Proposições interrogativas, como a do nº 4.
- Proposições imperativas, como a do nº 6.
São declarativas as de números 1 até 3 e as de 7 até 10.
A lógica matemática adota como regras fundamentais os dois seguintes princípios ou axiomas:
( I ) PRINCÍPIO DA NÃO CONTRADIÇÃO: Uma proposição não pode ser verdadeira e falsa ao mesmo tempo.
( II ) PRINCÍPIO DO TERCEIRO EXCLUÍDO: Qualquer proposição é verdadeira ou é falsa, não podendo ser nada mais
do que isso.
Por exemplo, as proposições 1 e 3 são ambas verdadeiras, mas as 3 proposições seguintes são falsas:
• Vasco da Gama descobriu o Brasil.
• Dante escreveu os Lusíadas. Obs: Camões escreveu “Os Lusíadas”.
• ¾ é um número inteiro.
As proposições são geralmente designadas pelas letras latinas minúsculas p, q, r, s... (sem índices ou acentos).
Exercício:
1) Quais são os nomes e quais são as proposições?
a) O número 3 é maior que o número 5.
b) A terra é um planeta
c) 9-12
d) 9
e) 8*7 = 56
f) O gato da menina
g) Um bom livro de matemática
h) 3 + 5 <> 5 + 3
i) Se chover hoje, então a rua ficará molhada.
j) O sol brilha e queima as plantas.
k) Jorge é gaúcho ou é Catarinense.
l) Um triângulo é retângulo se e somente se tem um ângulo reto.
m) Triângulo equilátero.
n) Se um triângulo é retângulo, então, dois de seus lados são perpendiculares
 Apostila de Lógica para a computação 3 
1.1. Valores Lógicos das Proposições:
Diz-se que o valor lógico de uma proposição p é verdade quando p é verdadeiro e falsidade quando p é falso. Os valores
lógicos verdade e falsidade de uma proposição designam-se abreviadamente pelas letras V e F ou pelos símbolos 1 e 0,
respectivamente. Assim, o que os princípios da não-contradição e do terceiro excluído afirmam é que:
Toda proposição pode assumir um, e somente um, dos dois valores: F ou V ( 0 ou 1 respectivamente).
Exercício:
2) Dar os valores lógicos das proposições abaixo, isto é, atribua V ou F para cada uma delas.
a) 3+5=8
b) A lua é um satélite da terra.
c) Colombo descobriu o Brasil.
d) Pedro Álvares Cabral descobriu a Colômbia.
e) o número 11 é primo.
f) (8-3)2 = 82 - 32
g) Um número divisível por 2 é par
h) 1 e -1 são raízes da equação x2-1=0
1.2 – Proposições simples e Proposições compostas
As proposições podem se classificadas como simples ou compostas. A proposição simples é aquela que não contém
nenhuma outra proposição como parte integrante de si mesma. A proposição composta é formada pela combinação de duas
ou mais proposições simples através de um elemento de ligação denominada conectivo. Ex.:
Proposição simples
P : Zenóbio é careca.
Q: Pedro é estudante
R: O número 25 é um quadrado perfeito
Proposições compostas
P: Zenóbio é careca e Pedro é estudante
Q: Zenóbio é careca ou Pedro é estudante
R: Se Zenóbio é careca, então é feliz
As proposições compostas são também chamadas de fórmulas proposicionais. Constrói-se uma proposição composta a
partir de duas ou mais proposições simples e do uso de conectivos.
1.3 – Conectivos
Definição: Chamam-se conectivos as palavras usadas para formar proposições compostas a partir de proposições simples.
Temos 1 conectivo unário e 4 conectivos binários. Ex.:
P: O número 6 é par e o número 8 é o cubo do número 2
Q: O triângulo ABC é retângulo ou o triângulo ABC é isósceles
R: Não está chovendo
S: Se Jorge é engenheiro, então sabe matemática
T: O triângulo ABC é equilátero se e somente se é equiângulo (subentende .. o triângulo ABC...)
Podemos considerar como conectivos usuais da lógica as palavras grifadas, isto é:
E, Ou, Não, Se ... Então..., ... Se e somente se... (sse)
Exercício:
3) Dentre as proposições do exercício 1, quais são: a) Simples: b) Compostas:
1.4 – Tabela-Verdade
Construção das tabelas - verdades:
Segundo o princípio do terceiro excluído, toda proposição simples p é verdadeira ou é falsa, isto é, tem o valor lógico V 
(verdade) ou o valor lógico F (falsidade).
P
V
F
 V 
P
 F
 Apostila de Lógica para a computação 4 
 
O valor lógico de uma expressão composta depende unicamente dos valores lógicos das expressões simples que compõem a
mesma. Admitindo isso, recorre-se a um dispositivo denominado tabela – verdade para aplicar este conceito na prática. 
Na tabela – verdade figuram todos os possíveis valores lógicos da proposição correspondentes a todas as possíveis
atribuições de valores lógicos às proposições simples componentes. Assim, por exemplo, uma proposição composta cujas
proposições simples componentes são p e q pode ter as possíveis atribuições:
 p q
 1 V V
 2 V F
 3 F V
 4 F F
Neste caso, as combinações entre os elementos são: VV, VF, FV e FF. As tabelas - verdade são construídas como arranjos
dos elementos componentes, e como um elemento pode receber somente os valores V ou F, o tamanho de uma tabela é dado
pela quantidade de elementos combinados:
No caso de uma proposição composta com 3 elementos, teríamos 8 combinações possíveis:
VVV, VVF, VFV, VFF, FVV, FVF, FFV, FFF.
 p q r
 1 V V V
 2 V V F
 3 V F V
 4 V F F
 5 F V V
 6 F V F
 7 F F V
 8 F F F
Observação 1: a ordem das letras pode ser diferente e a combinação entre as letras também pode ser dirente da apresentada
acima. Deve-se somente tomar o cuidado de não repetir duas combinações (2 linhas c/ VVF, por exemplo). 
Observação 2: Para construirmos as tabelas – verdade podemos usar as seguintes regras. O número de linhas sempre
depende do número de elementos combinados, e como uma proposição pode assumir os valores V ou F, o número de linhas
de uma tabela – verdade é dado por 2n.
1 elemento : 2 l linhas = 2 linhas
2 elementos: 22 linhas = 4 linhas
3 elementos: 2 3linhas = 8 linhas
4 elementos: 2 4linhas = 16 linhas
Para construir a tabela inicia-se sempre atribuindo V, F,V, F,... para o elemento mais à direita da tabela, V, V, F, F,... para o
segundo elemento da direita para a esquerda, V, V, V, V, F, F, F, F, ... para o terceiro elemento à partir da esquerda e assim,
sucessivamente.
Exercício: construa uma tabela – verdade para 4 elementos: p, q, r, s.
1.5. Notação
O valor lógico para uma proposição simples p indica-se por V(p). Assim, se p é verdadeiro expressa-se: V(p) = V.
Analogamente, pode-se exprimir que a proposição p tem o valor falso utilizando-se V(p) = F.
Considerando, por exemplo, as seguintes proposiçõessimples:
p: O Sol é verde
q: um hexágono tem 6 lados
r: 2 é um número ímpar
s: um triângulo tem 4 lados
 
Temos:
V(p)=F V(q)=V V(r) =F V(s) =F
 Apostila de Lógica para a computação 5 
2. Operações lógicas sobre as Proposições
Quando pensamos, efetuamos muitas vezes certas operações sobre proposições, chamadas operações lógicas. Estas
obedecem a regras de um cálculo, denominado Cálculo Proposicional, semelhante ao da aritmética sobre números. Serão
apresentadas, a seguir, as operações lógicas fundamentais do cálculo proposicional.
2.1 Negação (~)
Definição: chama-se negação de uma proposição p a proposição representada por “não p”, cujo valor lógico é verdade
(V) quando p for Falso e falsidade (F) quando valor de p é verdadeiro. Assim, “não p” tem o valor oposto do valor de p. A
negação de p indica-se com a notação “~p”, e é lido como “não p”.
O valor lógico da negação de uma proposição é definido por uma tabela – verdade muito simples:
 p ~p
 1 V F
 2 F V
Ou seja: ~V = F, ~F = V e V (~P) = ~ V(P)
Exemplo:
(1) r: Roma é a capital da França (F) 
V (~r) = ~V(r) = ~F = V
Na linguagem comum a negação efetua-se, nos casos mais simples, antepondo o advérbio “não” ao verbo da proposição
dada. Assim, por exemplo, considerando a proposição:
 p : O Sol é uma estrela 
sua negação é :
 ~p : O Sol não é uma estrela
Outra maneira de efetuar a negação consiste em antepor à proposição dada expressões tais como “não é verdade que”, “é
falso que”. Assim, por exemplo, considerando a proposição:
 q : Carlos é mecânico
sua negação é :
 ~q : Não é verdade que Carlos é mecânico
Deve-se tomar um pouco de cuidado com a negação, porque, por exemplo a negação de “Todos os homens são elegantes” é
“Nem todos os homens são elegantes” e a de “Nenhum homem é elegante” é “Algum homem é elegante”.
2.2. Conjunção ( . , ^ )
Definição: chama-se conjunção de duas proposições p e q a proposição representada por “p e q”, cujo valor lógico é a
verdade (V) quando as proposições p e q são ambas verdadeiras a falsidade (F) nos demais casos.
Simbolicamente, a conjunção de duas proposições p e q indica-se com a notação: “p . q”, que se lê: “p e q”.
O valor lógico da conjunção de duas proposições é, portanto, definido pela seguinte tabela – verdade:
p q p . q
V V V
V F F
F V F
F F F
ou seja, pelas igualdades:
V . V = V, V . F = F, F . V, F . F = F e
(p ^ q) = V (p) ^ V (q)
 Apostila de Lógica para a computação 6 
Exemplos:
(1) {p : A neveé branca (V )q : 2<5(V ) }
 p . q: A neve é branca e 2 < 5 (V)
 V (p . q) = V(p) . V(q) = V . V = V
 
(2) {p :O enxofre é verde(F )q :7 é um número primo (V )}
 p ^ q : O enxofre é verde e 7 é um número primo (F)
 V (p ^ q) = V(p) ^ V (q) = F ^ V = F
 
2.3. Disjunção ( v , + )
Definição: chama-se disjunção de duas proposições p e q a proposição representada por “p ou q”, cujo valor lógico é a
verdade( V ) quando ao menos uma das proposições p e q é verdadeira e a falsidade (F) quando as proposições p e q são
ambas falsas.
Simbolicamente, a disjunção de duas proposições p e q indica-se com a notação: “p + q”, que se lê: “p ou q”.
O valor lógico da disjunção de duas proposições é, portanto definido pela seguinte tabela – verdade:
p q p + q
V V V
V F V
F V V
F F F
V (p + q) = V (p) + V (q)
Exemplos:
(1) {p : Parisé a capital da França (V )q :9−4=5(V ) }
 p + q: Paris é a capital da França ou 9 – 4 = 5 (V)
 V (p + q) = V(p) + V(q) = V + V = V
(2) {p :Camões escreveu os Lusíadas (V )2+2=3(F ) }
p + q : CAMÕES escreveu os Lusíadas ou 2 + 2 = 3 (V)
 V (p + q) = V(p) + V(q) = V + F = V
2.4. Disjunção Exclusiva ( , + )
Na linguagem comum a palavra “ou” tem dois sentidos. Assim, p. ex., consideremos as duas seguintes proposições
compostas:
P : Carlos é médico ou professor
Q: Mário é alagoano ou gaúcho
Na proposição P indica-se que ao menos uma das proposições: “Carlos é médico”, “Carlos é professor” é verdadeira,
podendo ser ambas verdadeiras: “Carlos é médico e professor”. Mas, na proposição Q, é óbvio que uma e somente uma das
proposições “Mário é alagoano”, “Mário é gaúcho” é verdadeira, pois, não é possível ocorrer “Mário é alagoano e gaúcho”.
Na proposição P diz-se que “ou” é inclusivo, enquanto que, na proposição Q, diz-se que “ou” é exclusivo.
 Apostila de Lógica para a computação 7 
Em Lógica Matemática usa-se habitualmente o símbolo “+” para “ou” inclusivo e os símbolos “+, ” para “ou” exclusivo.
Assim sendo, a proposição P é a disjunção inclusiva ou apenas disjunção das proposições simples “Carlos é médico”,
“Carlos é professor”, isto é:
P: Carlos é médico + Carlos é professor
A proposição Q é a disjunção exclusiva das proposições simples “Mário é alagoano”, “Mário é gaúcho”, isto é:
Q: Mário é alagoano  Mário é gaúcho
De um modo geral, chama-se disjunção exclusiva de duas proposições p e q a proposição representada simbolicamente por
“p  q”, que se lê: “ou p ou q” ou “p ou q, mas não ambos”, cujo valor lógico é verdade (V) somente quando p é
verdadeira ou q é verdadeira, mas não quando p e q são ambas verdadeiras, e falsidade(F) quando p e q são ambas
verdadeiras ou ambas falsas.
O valor lógico da disjunção exclusiva de duas proposições é definido pela seguinte tabela – verdade:
 p Q p  q 
 V V F
 V F V
 F V V
 F F F
2.5 Condicional ():
Definição: chama-se condicional uma proposição representada por “se p então q” cujo valor lógico é falsidade (F) quando
p é verdadeira e q é falsa e verdade (V) nos outros casos.
Simbolicamente, a condicional de duas proposições p e q indica-se com a notação “pq” e pode ser lida das seguintes
formas:
I. p implica q 
II. se p então q
III. p é condição suficiente para q
IV. q é condição necessária para p
Na condicional “pq” , diz-se que p é o antecedente e o q o conseqüente. O símbolo “” é chamado de implicação. 
Considere o seguinte exemplo:
João trabalha em uma estação meteorológica e faz a seguinte afirmação no dia 03 de março:
Se a umidade subir acima de 90 %, então choverá em menos de 24 horas
p: A umidade sobe acima de 90 % q: Choverá em menos de 24 horas.
Até o dia 05, embora a umidade estivesse a 95 % durante as últimas 48 horas, não choveu. Isso significa que a afirmação
feita anteriormente era falsa, ou seja:
V(p  q) : F | V(v  f): F
 Isso significa que sempre que o antecedente for verdadeiro, o conseqüente deve ser verdadeiro para que o resultado de
toda a proposição seja verdadeira. O condicional não afirma a veracidade do antecedente e do conseqüente, mas a relação
existente entre eles.
Ex2.: Se João é Engenheiro, então sabe matemática.
A tabela – verdade da condicional de duas proposições é, portanto:
 P q pq
 1 V V V
 2 V F F
 3 F V V
 4 F F V
 Apostila de Lógica para a computação 8 
2.6 Bicondicional (  ):
Definição: chama-se bicondicional uma proposição representada por “p se e somente se q” cujo valor lógico é verdade
(V) quando p e q são ambas, verdadeira ou falsas.
Simbolicamente, a bicondicional de duas proposições p e q indica-se com a notação “p  q” e pode ser lida das seguintes
formas:
i. p é condição necessária e suficiente para q
ii. q é condição necessária e suficiente para p
iii. p se e somente se q (será mais utilizado) podendo ter a abreviação “p sse q”.
A tabela – verdade da bicondicional de duas proposições é, portanto:P q P  q
 1 V V V
 2 V F F
 3 F V F
 4 F F V
Quando se tem uma bicondicional p  q, na verdade implicamos p  q, e q  p ao mesmo tempo, ou seja, só é verdade
quando as duas condicionais são verdadeiras.
Considerando que p  q só é verdade quando as duas condicionais pq e qp são verdades, temos falsidade nos casos:
pq sendo v(p)= V e V(q) = F e,
qp sendo v(q)= V e V(p) = F e,
correspondentes às linhas 2 e 3 da tabela verdade.
Ex: João é careca, sse João não tem cabelo. Isso na verdade implica:
i) Se joão é careca, então João não tem cabelo e
ii) Se João não tem cabelo, então João é careca.
Obrigatoriamente, as duas proposições simples que compõem cada uma das proposições condicionais i e ii devem ser:
ambas verdadeiras ou falsas, para a bicondicional ser verdadeira.
Exercícios:
4) Classifique cada uma das proposições compostas do exercício 1:
a) conjunção:
b) disjunção:
c) condicional:
d) bicondicional:
5) Seja p a proposição “Está frio” e q a proposição “Está chovendo”. Traduzir, para a linguagem corrente, as seguintes
proposições:
a) ~p
b) p.q
c) p+q
d) q <-> p
e) p -> ~q
f) q v ~p
g) ~p ^ ~q
h) ~~q
6) Seja p a proposição “Jorge é rico” e q a proposição “Carlos é feliz”. Traduzir, para a linguagem corrente, as seguintes
proposições:
a) p+q
b) q->p
c) pv~q
d) q<->~p
e) ~p->q
f) (~p.q)->p
 Apostila de Lógica para a computação 9 
7) Traduza para a linguagem comum, sabendo que p: os preços são altos e q: os estoques são grandes.
a) (p.q) ->p
b) (p.~q) ->~p
c) ~p . ~q
d) p+~q
e) ~(p.q)
f) ~(p+q)
g) ~(~p+~q)
8) Seja p a proposição “Jorge é alto” e q a proposição “Jorge é elegante”. Traduzir, para a linguagem simbólica, as
seguintes proposições:
a) Jorge é alto e elegante.
b) Jorge é alto mas não é elegante.
c) Não é verdade que Jorge é baixo ou elegante.
d) Jorge não é baixo e nem é elegante.
e) Jorge é alto, ou é baixo e elegante.
f) Não é verdade que Jorge é baixo ou que não é elegante. 
9) Determinar o valor lógico (V + F) de cada uma das seguintes proposições compostas:
a) Se 1 + 2 = 5, então 3 + 3 = 6
b) Não é verdade que 2 + 2 = 7 se e somente se 4 + 4 = 9
c) DANTE escreveu os Lusíadas ou 5 + 7 < 2
d) Não é verdade que 1 + 1 = 3 ou 20 = 1
e) É falso que , se Lisboa é a capital da França, então Brasília é a capital da Argentina.
 
10) Escrever simbolicamente para p: João é esperto, q: José é tolo.
a) João é esperto e José é tolo.
b) João é esperto ou José é tolo.
c) João é esperto e José não é tolo
11) Seja p: Vanda é aluna e q: Sílvia é professora.
Escreva simbolicamente: Vanda é aluna ou não é verdade que Sílvia seja professora e Vanda seja aluna.
12) Símbolo para: Vanda tem 5 anos ou se Vanda é bonita, então, é tagarela.
13) Dar os valores das proposições abaixo:
a) (8 > 2) . (4 <=4)
b) (6 < 10) . (6 > 3/2)
c) (6 < 2) + ((4-3) >=1)
d) (5 > 8)  (4>3)
e) (4 < 2) + (2<4)
f) (8-3= 5) -> (2 <= 2)
g) (8>10) -> (6-2 = 4)
h) (8>10) -> (6 < 5)
i) (4 < 2 ) <-> (8-2 = 15)
14) Dar o valor da proposição p nos casos adiantes:
a) V(pq) = V e V(q) = V
a) V(qp) = V e V(q) = F
b) V(q+p) = F e V(q) = F
c) V(q+p) = V e V(q) = V
15) Considerando V(p) = F , V(x) = F e V(y) = V
a) V(((p + q) . (x + y) )  p ) = 
b) V(x . y  p ) = 
c) V(p . y . p . x ) = 
16) Verificar se a informação dada é suficiente para determinar o valor da expressão:
a) (p  s)  r, onde r tem o valor V
b) (p+r)+(s  q), onde q tem valor F
c) ((p+q )  (q.p))  ((r.p)+q), onde o valor de q é V.
d) ((p  q)  p, onde o valor de q é V.
e) ((p  q  p) p+q, onde o valor de q é V.
f) (p+q  r.p+q), onde o valor de q é F.
 Apostila de Lógica para a computação 10 
3. Tabelas-verdades de proposições compostas:
Dadas várias proposições simples p,q,r,..., podemos combiná-las mediante o uso dos conectivos:
~, ., +, ,  
e construir proposições compostas, tais como: 
(p.(~qp)). ~((p~q)(q+p))
Com o emprego das tabelas-verdades das operações lógicas fundamentais é possível construir a tabela-verdade
correspondente a qualquer proposição composta dada. Logicamente, o valor-verdade final depende dos valores lógicos das
proposições componentes.
Exercício: 
17) Construir as tabelas-verdades:
a) (q.r) + m 
b) (q+r)  ((q+s)  (p+s))
c) (p  r )  p
d) (p  r )  p
e) (p  (q  r))  ((p  q)  (p  r ))
f) ~ (p + q)  (~~p + ~q)
4. Tautologia, contradição e contingência (indeterminada)
As fórmulas proposicionais podem apresentar os seguintes casos quanto às suas tabelas-verdades:
a) Última coluna da tabela-verdade apresenta somente V(s)  Fórmula tautológica  Tautologia
b) Última coluna da tab. - verdade apresenta somente F(s)Fórmula contra-válidaContradição
c) Última coluna da tabela-verdade apresenta V(s) e F(s)  Fórmula indeterminada 
Exercícios:
18) Verificar quais fórmulas são contradições, tautologias ou indeterminadas.
a) p  p+p 
b) (a  b)  ((b  c)  (a  c))
c) (a  b ) . (b  a)
d) ã  a  b
e) a. (ã + b)
f) ~(~p . q )  ~p + ~q
5. Implicação Lógica e Equivalência Lógica
5.1. Relação de implicação: uma proposição p implica uma proposição q se e somente se p  q for uma tautologia.
Obs.: o símbolo  é de operação lógica e o símbolo  é de relação.
Ex.: p . q  p  q uma vez que a operação condicional  gera uma tautologia.
Tabela-Verdade:
 Apostila de Lógica para a computação 11 
Exercícios:
19) Verificar as implicações.
a) p  p + q
b) p . q  p
c) (p + q) . ~p  q
d) (p  q) . p  q
e) (p  (q r))  q  (p  r)
 
5.2. Relação de Equivalência: uma proposição p é equivalente a uma proposição q se e somente se p  q for uma
tautologia.
Obs.: o símbolo  é de operação lógica e o símbolo  é de relação.
Ex.: “p  q” e “ ~p + q “ são proposições logicamente equivalentes pois possuem a mesma tabela-verdade. Então
dizemos:
p  q  ~p+q
Tabela-Verdade:
Exercício:
20)Verificar as equivalências.
a) ~(p.~p)  (p+~p)
b) p.(~p+q)  (p.q)
c) (p  (q  r))  q  (p r)
 Apostila de Lógica para a computação 12 
Argumentos
Chama-se de argumento toda a afirmação de que várias proposições (p1, p2, ..., pn) têm por conseqüência uma outra
proposição q. As proposições p1, p2, ..., pn são as premissas, e a proposição q é a conclusão do argumento. Um argumento
é escrito da seguinte forma: p, pq, qr ├ r onde:
p, pq, qr ├ r
Premissas conclusão
Validade de um argumento através da Tabela-verdade: Um argumento é valido quando para todas as linhas da tabela
verdade onde as premissas forem verdadeiras, a conclusão também é verdadeira.
Exemplo: comprove a validade dos seguintes argumentos:
a) p, pq ├ q
b) pq, q ├ p
c) p  q, q ├ p
Regras de Inferência
A utilização de tabelas-verdade permite validar qualquer argumento, mas o seu emprego torna-se cada vez mais trabalhoso
na medida que aumenta o número de proposições simples componentes dos argumentos. Para um argumento com 6
proposições (o que é bastante comum) por exemplo, é necessário construir uma Tabela Verdade com 2 6 linhas (64 linhas),
perspectiva nada animadora. Um método mais eficiente para demonstrar, verificar ou testar a validade de um dado
argumento, consiste em deduzir a conclusão Q a partir das premissas P1,P2, ...Pn, mediante o uso de certas Regras de
Inferência.
Existem 10 regras de inferência (eliminação e introdução) para cada um dos 5 operadores lógicos.
Vejamos o seguinte exemplo: 
C,SA, CS ├ A
a) provar pelo uso da T.V.
b) O argumento é válido porque pode ser derivável pelas regras de inferência. A derivaçãoé a seguinte:
1) C P
2) S  A P
3) C  S P
4) S 1,3 MP ( E)
5) A 2,4 MP ( E)
As três primeiras suposições da resolução têm um P ao lado, indicando que cada uma delas é uma premissa. Então,
deduzimos a conclusão ‘A’ em duas etapas de raciocínio. A primeira etapa é das linhas 1 e 3 para a linha 4. A Segunda
etapa é das linhas 2 e 4 para 5. 
Os números à direita denotam as linhas das quais 4 e 5 são derivadas. As duas etapas tem a mesma forma. Cada uma delas é
uma instância da primeira das 10 regras de inferência, denominada modus ponens que chamaremos ‘MP’.
a) Modus Ponens: do condicional () e seu antecedente, podemos inferir seu consequente .
Modus ponens é a regra de eliminação para condicional.
Ex.: Prove:
 ~P (Q R), ~P,Q ├ R
b) Eliminação da negação (~E): a partir de uma expressão ~~p, podemos inferir p.
Ex: Não é verdade que Getúlio Vargas não foi presidente.
Ex.: Prove:
Prove: ~P ~~Q, ~~~P ├ Q 
 Apostila de Lógica para a computação 13 
As 10 regras de Inferência
1. Modus Ponens: do condicional () e seu antecedente, podemos inferir seu consequente. Modus ponens é a regra de
eliminação para condicional.
2. Eliminação da negação (~E): a partir de uma expressão ~~, podemos inferir . Ex: Não é verdade que Getúlio
Vargas não foi presidente.
3. Introdução da conjunção (.I): a partir de duas expressões quaisquer  e , podemos inferir a conjunção das duas
expressões: 1.p 2.q 3. p.q 1,2 .I
4. Eliminação da conjunção (.E): De uma conjunção qualquer, podemos inferir qualquer um dos seus conjunctos: 1.p.q
2. q 1 .E 
5. Introdução da disjunção (+I): a partir de uma expressão qualquer , podemos inferir a disjunção de  com outra
fórmula proposicional (expressão) qualquer ( pode ser o primeiro ou o segundo disjuncto desta disjunção). 1.p 2.
p+q 1 +I
Ex: Hoje é sexta-feira. Se a afirmação for verdadeira, a afirmação: Hoje é Sexta-feira ou Sábado também é verdadeira.
6. Eliminação da disjunção (+E): De expressões quaisquer, na seqüência +,  e , podemos inferir a expressão
. 1. p+q 2.pr 3.qr 4. r 1,2,3 +E
Dessa forma, a partir das premissas: hoje é Sábado ou hoje é Domingo, se hoje é Sábado então é um fim de semana (SF),
se hoje é Domingo então é um fim de semana, segue se hoje é um fim de semana. Prove.
7. Introdução do bicondicional (I): de duas expressões quaisquer, na forma  e , podemos inferir a expressão
. 1. pq 2. qp 3. pq 1,2 I.
8. Eliminação do bicondicional (E): de uma expressão qualquer, na forma , podemos então inferir  ou
. 1. pq 2. pq 1, E.
As regras 9 e 10 diferem das 8 demais por empregarem raciocínio baseado em hipóteses. As hipóteses não são declaradas
como verdadeiras, elas são “artifícios lógicos”, as quais acolhemos temporariamente como um tipo especial de estratégia de
prova. Suponha que um corredor machucou o joelho, uma semana antes de um grande jogo, e temos que persuadí-lo a parar
de correr por alguns dias a fim de que o seu joelho sare. Afirmamos: “Se você continuar correndo, não poderá jogar na
próxima semana”. Sua resposta: “Me prove isso”.
Tem-se então as seguintes premissas:
a) Seu joelho está inchado. 
b) Se seu joelho está inchado e você continuar correndo, ele não irá sarar em uma semana.
c) Se seu joelho não sarar em uma semana, você não estará apto a jogar o próximo jogo.
9. Introdução da implicação ou Prova do condicional (I ou PC). Dada a derivação de q a partir de uma hipótese p,
podemos descartar a hipótese e inferir pq.
Ex. Prove o argumento anterior.
Premissas: I: Joelho Inchado C: Continuar correndo S: Joelho irá sarar em uma semana
A: Estará apto a jogar na próxima semana.
A partir dessas premissas, quer-se concluir que:
Se o jogador continuar correndo, não estará apto a jogar na próxima semana
10. Introdução da negação ou Redução ao absurdo (~I ou RAA). Dada a derivação de uma contradição a q.~q partir de
uma hipótese p, podemos descartar a hipótese e inferir ~p.
Dessa forma, se assumirmos p como hipótese e ao final temos q . ~q, concluimos o contrário da hipótese (~p) por RAA.
Ex. Prove: p q, ~q ├ ~p
1. p  q p
2. ~q p
3. p H
4. q 1,3 MP
5. q . ~q 2,4 .I
6. ~p 3,5 RAA
 Apostila de Lógica para a computação 14 
Exercícios para compreensão e fixação das regras de inferência:
MP ( E)
a) ~pq, ~p ├ q
b) ~p(qr), ~p, q ├ r
~E
c) t ~~p, p~q, t ├ ~q
d) ~p  ~~q, ~~~p ├ q
. I
e) p q, rs, p, r ├ q . s
. E
f) p (q . r), p ├ p . q
g) p . q ├ q . p
h) (p . q)  (r . s), ~~p, q ├ s
i) p ├ p . p
j) ~p . q  u, ~~~p, sq, xr.s, x ├ u
k) s  ((p.q)~~r), p.q, t.s ├ r.t
+ I
l) p ├ (p+q) . (p+r)
m) p, ~~(pq) ├ q+ ~q
n) p, ~~(pq) ├ (r.s)+q
o) p ├ p+p
+ E
p) Hoje é Sábado ou Domingo. 
Se hoje é Sábado, então é fim-de-semana. 
Se hoje é Domingo, então é fim-de-semana. 
Conclui-se que hoje é fim-de-semana.
q) (p+q).(p+r), ps, qs, pt,rt ├ s.t
r) p+p, p(q.r) ├ r
 I
s) pq, (pq)  (qp) ├ p  q
t) p  q ├ q  p
u) s(rp), a.s, pr ├ (pr) + q
v) ~~(px), ~~(qx), x.pk, p+q, ku ├ u
 E
w) Hoje é fim-de-semana se e somente se hoje for
Sábado ou Domingo. Hoje é Sábado. Então, hoje é
fim-de-semana.
Regras hipotéticas:
PC ( I)
a) i, (i.c)~s, ~s~a ├ c  ~a
b) p  q, qr ├ pr
c) p ├ (pq)  q
d) (p.q)r ├ p (qr)
e) p + q ├ q + p
f) (p.q) + (p.r) ├ p. (q+r)
RAA ( ~I)
g) pq, ~q ├ ~p
h) p  ~q ├ ~(p.q)
i) ~p p ├ p
j) s~~v ├ ~v  ~s
k) (~s.v)~p, p, v ├ s
l) ~(~p.~q), ~p ├ q
m) ~p + ~q ├ ~(p . q)
n) pq ├ ~p+q
o) ~ ( p . q) ├ ~p + ~q
Exercícios complementares
a) (g+n)  ~c ├ ~~c  ~(g+n)
1. Formalize e prove os seguintes argumentos usando as 10 regras de introdução e eliminação:
c A conclusão deste argumento é verdadeira
p As premissas deste argumento são verdadeiras
s Este argumento é correto 
v Este argumento é válido
a) Este argumento não é incorreto. Portanto, este argumento é correto.
b) Este argumento é correto. Portanto, este argumento não é incorreto.
c) Se este argumento for correto, então ele será válido. Ele não é válido.Portanto, ele não é correto.
d) Se este argumento for correto então ele não será inválido. Ele é correto. Daí, ele é válido.
e) Se este argumento for correto então ele não será inválido. Assim, se ele for inválido, então ele será incorreto.
f) Este argumento é correto e válido. Portanto, Ele é correto ou ele é inválido.
g) Este argumento não é, ambos, correto e inválido. Ele é correto. Portanto, ele é válido.
h) Este argumento é correto sse todas suas premissas forem verdadeiras. Suas premissas não são verdadeiras. Portanto, ele
é incorreto.
i) Se a conclusão deste argumento for não-verdadeira, então este argumento é incorreto. Assim sendo, não é o caso que
este argumento é correto e sua conclusão não-verdadeira.
j) Se este argumento for incorreto e válido, nem todas as suas premissas são verdadeiras. Todas as suas premissas são
verdadeiras. Ele é válido. Portanto, ele é correto.
k) Se este argumento for válido e todas as suas premissas forem verdadeiras, então ele será correto. Se ele for correto,
então sua conclusão é verdadeira. Todas suas premissas são verdadeiras. Portanto, se este argumento for válido então
sua conclusão será verdadeira.
l) Ou este argumento é incorreto ou, caso contrário ele é válido e todas suas premissas são verdadeiras. Então, ele é
incorreto ou válido.
 Apostila de Lógica para a computação 15 
Teoremas
Teorema se diferencia de argumento pelo fato de não ter nenhuma premissa, somente conclusão. Sua prova é então baseada
somente em hipóteses,que são descartadas por PC ou RAA.
Exemplos:
├ P  (P+Q)
├ P  ((P  Q)  Q) 
├ P  ~~P
├ P + ~P 
Vimos em uma aula anterior equivalência lógica. Quando a bicondicional entre duas expressões resultar em uma tautologia
dizemos que essas expressões são equivalentes. Através das regras de inferência podemos também provar a equivalência
lógica entre duas expressões.
Exemplo: para provar a equivalência entre as expressões: ~(P.Q) e ~P + ~Q representaríamos como na letra a):
├ ~(P.Q)  ~P + ~Q
├ ~(P+Q)  ~P . ~Q
Estratégias para provas
Não há uma forma única de se construir uma prova. Se um argumento pode ser provado, ele pode ser provado por diferentes trocas de
regra. Então, algumas estratégias ajudam, embora alguns problemas requeiram ainda, habilidade e engenhosidade.
Estratégias para prova.
Se a conclusão for Então faça
Fórmula atômica
Fórmula negada
Conjunção
Disjunção
Condicional
Bicondicional
Se nenhuma ação parece ser imediata, coloca-se como hipótese a negação da conclusão para RAA.
Se isso for bem - sucedido, então a conclusão pode ser obtida depois de RAA por ~E. 
Coloca-se como hipótese a conclusão, sem o símbolo da negação, para RAA. Se resultar uma
contradição, a conclusão pode ser obtida por RAA
Prove cada um dos conjunctos, separadamente e então faça a conjunção deles com .I.
- Tenta-se provar os condicionais necessários para +E caso tenha + nas premissas.
- Se não der certo pode-se usar como hipótese a negação da conclusão e tenta-se RAA.
- Pode-se também provar um dos seus disjunctos e aplicar +I.
Coloca-se como hipótese o seu antecedente e deriva-se o seu conseqüente por PC.
Use PC, duas vezes, para provar os dois condicionais necessários para se obter conclusão por I.
As 10 regras de Inferência (permitido utilizar em prova)
1. Modus Ponens: ( E) (MP) do condicional ( ) e seu antecedente (), podemos inferir seu conseqüente ().
2. Eliminação da negação (~E): a partir de uma expressão ~~, podemos inferir .
3. Introdução da conjunção (.I): a partir de duas expressões válidas quaisquer  e , inferimos conjunção das duas: ..
4. Eliminação da conjunção (.E): De uma conjunção qualquer ., podemos inferir  ou .
5. Introdução da disjunção (+I): a partir de uma expressão , podemos inferir a disjunção de  com qualquer expressão.
6. Eliminação da disjunção (+E): De expressões quaisquer, na seqüência +,  e , podemos inferir 
7. Introdução do bicondicional (I): de duas expressões quaisquer, na forma  e , podemos inferir  .
8. Eliminação do bicondicional (E): de uma expressão qualquer, na forma  , podemos então inferir  ou .
9. Introdução da implicação (I) (PC). Derivando  a partir de uma hipótese , descartamos a hip.  e inferimos .
10. Introdução da negação (~I ou RAA). Derivando +~ a partir de uma hipótese , descartar a hip. e inferimos ~.
 Apostila de Lógica para a computação 16 
Regras de Equivalência ou Álgebra das proposições
1. Lei da dupla negação: ¯¯α  α 
2. Idempotência: α⋅α  α | α+α  α
3. Comutatividade: α⋅β  β⋅α | α+β  β+α 
4. Associatividade:  
5. Distributivas:  
6. De Morgan (α⋅β)  α¯+β¯ | (α+β)  α¯⋅¯β
7. Eliminação da Condicional:  α¯+β 
8. Eliminação da Bicondicional:     α⋅β+α¯⋅¯β
9. Regras para Absorção:
a) α⋅β+β  β | (α+β)⋅β  β
b) α⋅β+β¯  α+β¯
c) α⋅α¯  F
d) α+α¯  V
e) α⋅V  α
f) α⋅F  F
g) α+V  V
h) α+F  α
Forma Normal Disjuntiva
Literais: São letras sentenciais ou negações de letras sentenciais: a, ã, p
Conjunção fundamental: conjunção de 2 ou mais literais sem repetir a letra sentencial: a.b, ã.c, ~b.c
Forma Normal Disjuntiva: Diz-se que uma expressão está na FND se:
a) é uma letra sentencial,
b) uma conjunção fundamental ou 
c) a disjunção de 2 ou mais conjunções fundamentais, nenhuma das quais incluída em outra.
Assinale as expressões que estão na FND:
( ) a.b.~c
( ) a.b + c
( ) a
( ) ã.b + ã.b
( ) a.~b.~c + a.b + a.~c
( ) a.b + c
( ) ã + ã.b
( ) a.b + c.~b
 Apostila de Lógica para a computação 17 
Exemplo de simplificação utilizando as regras de equivalência
Expressão: (x .a).( y .b)+a. x
a) Resolução forma convencional (recomendado):
(x .a).( y .b)+a. x
(x .a).( y .b)+a. x = α.β+ ~β = α + ~β
( y .b)+a .x
b¯+ y¯+a . x
b) Resolução segundo método (não recomendado):
• Primeiro passo: transformar a expressão para a Forma Normal Disjuntiva Completa ( F.N.D.C)
(x .a).( y .b)+a. x
( x¯+ a¯).( y¯+b¯)+a .x
a¯ . b¯+a¯ . y¯+ x¯ .b¯+ x¯ . y¯+a. x
a¯ . b¯ .(V )
a¯ . b¯ .(x+ x¯ )
a¯ . b¯ .(x .( y+ y¯)+ x¯ .( y+ y¯ ))
a¯ . b¯ .(x . y+x . y¯+ x¯ . y+ x¯ . y¯) = a¯ . b¯ .x . y+a¯ . b¯ .x . y¯+a¯ . b¯ . x¯ . y+a¯ . b¯ . x¯ . y¯
a¯ . y¯ .(b . x+b. x¯+b¯ .x+b¯ . x¯) = a¯ .b .x . y¯+a¯ .b . x¯ . y¯+a¯ . b¯ .x . y¯+a¯ . b¯ . x¯ . y¯
x¯ . b¯ .(a . y+a. y¯+a¯ . y+ a¯. y¯ ) = a . b¯ . x¯ . y+a . b¯ . x¯ . y¯+a¯ . b¯ . x¯ . y+a¯ . b¯ . x¯ . y¯
x¯ . y¯ .(a.b+a. b¯+ a¯.b+ a¯ .b¯) = a .b . x¯ . y¯+a . b¯ . x¯ . y¯+a¯ .b . x¯ . y¯+a¯ . b¯ . x¯ . y¯
a .x .(b . y+b. y¯+b¯ . y+ b¯. y¯ ) = a .b .x . y+a .b .x . y¯+a . b¯ .x . y+a . b¯ .x . y¯
• Segundo passo: Simplificar através de Mapa Karnaugh
 00 01 11 10
00 . . . .
01 . .
11 . . .
10 . . . .
Resultado:
Conclusão: 
Assim como neste exercício, existem várias situações em nossa vida que podemos optar por mais de
um caminho para chegar à resolução de um problema. Se a resolução está muito difícil, é provável que
haja um caminho mais fácil para resolver. Deve-se atentar a isso principalmente na programação, onde
um código otimizado resulta em tamanho menor, maior performance na execução e menos trabalho na
elaboração.
a b x y
 Apostila de Lógica para a computação 18 
Exercícios
Para cada uma das expressões abaixo:
a) utilizando as regras de equivalência, transforme a expressão para F.N.D. 
b) simplifique a expressão ao máximo
1. a .b+b
2. a .b¯+b
3. b .a+ a¯
4. b .a+a
5. a .b¯+b
6. a¯ .b¯+ b¯
7. b . a¯+ a¯
8. b . a¯+ a¯
9. b .a+a
10. a¯ .b+b
11. x . y+ y¯
12. a . x¯+x
13. a . y¯+ y¯
14. x¯ . y¯+ x¯
15. y . x¯+ x¯
16. y¯ . x+ x¯
17. y . x+x
18. a .b+b+a
19. a .b+a . y . x
20. x .a . y .b+x . a
21. y . x¯+x . y
22. y¯ . x+x . y¯ . z
23. y . x+x . y+ y
24. a .b+a .c .b
25. (b .a c .b)+b .c
26. y . x¯+x . x
27. y¯ . x+x . y . z
28. x . y+( x . y+ y )
29. a .b+a .a .b
30. (b .a .c .a )+b . a
31. (a .b .b .a)+c . a
32. (b . a . b . a)+(b .a)+(b . a )
33. (b . a . b . c)+(b .c)+(a . b)
34. ( y . x+x . y+ y) . x
35. (x+x . y+ y) . x+( y+x+ y) . x
36. ( y . x+x ). x+( y . x+x+ y ). x
37. y . x+( x . y+ y ). x
38. y . x+( x . y+ y ). x+( y . x+ x . y)+ y . x
39. y . x+( x . y+ y ). x+( y . x+ x . y)+ y . x¯
40. ( p→r )→ p
41. ( p→r )→ p¯
42. ( p→r )→ p . r
43. ( p . r→r )→ p . r
44. ( p¯→r )→ p¯
45. ( p . r→( p. q. r+ p))→ p . r
46. (( p . r→r )→( p . r→ p))→ p
47. (( p . r→r )→( p . r→ p))→ p
48. (( p . q→r ))→( p . r)
49. ( p→r )  p
50. ( p→r )  p¯
51. ( p→r )  p . r
52. ( p . r→r )  p . r
53. ( p¯→r )  p¯
54. (( p . r→r )→( p . r→ p))  p
55. (( p .q→r ))  p . r
 Apostila de Lógica para a computação 19 
Circuitos Lógicos
Um circuito lógico nada mais é do que a combinação de várias portas lógicas com o objetivo de realizar uma determinada
tarefa. O processador de um computador não deixa de ser um aglomerado de circuitos lógicos. 
Qualquer operação feitaem um computador, por mais complexa que seja, é derivada de combinação de tarefas lógicas e
aritméticas simples tais como somar bits, mover bits, etc. 
Pode-se implementar um circuito lógico simples em um circuito Integrado. Abaixo é apresentado o circuito MC54F/74F00
da Motorola, composto de várias portas NAND.
Uma ferramenta bastante simples que pode ser utilizada para projetar e testar circuitos lógicos é a Digital Works. Abaixo
são apresentadas as opções da ferramenta que aparecem na tela principal e os passos para projetar um pequeno circuito (1)
(2) (3)
21
3
VCC
GND
 Apostila de Lógica para a computação 20 
Minimização
A minimização consiste em determinar métodos para se encontrar um circuito mais simples (i.e. mais barato) equivalente a
uma expressão (circuito) dada.
Suponhamos uma determinada expressão. Existem várias formas de se minimizar essa expressão:
1- Utilizar as regras de equivalência para encontrar a FND mais simples que represente a expressão (função de verdade)
dada
2- Utilizar o método figurativo denominado mapas de Karnaugh (somente pode ser utilizado para simplificar expressões
que estão na FNDC.
Mapas de Karnaugh 
É conveniente sua utilização para problemas que envolvam no máximo 6 letras sentenciais.
Mapas de Karnaugh para 2 letras sentenciais
Neste caso o mapa é baseado na figura 1. Cada quadrado do mapa representa uma conjunção fundamental entre as letras
das linhas e colunas. 
Na fig.2 está sendo representado A.B + Ã.B 
Na fig.3 está sendo representado A.B + Ã.B + A.~B
A \ B 0 1 A \ B 0 1 A \ B 0 1
0 0 0
1 1 1
 Figura 1 Figura 2 Figura 3
O processo de simplificação consiste em juntar quadrados adjacentes de 2 em 2, tracando uma oval ao redor de cada par. O
literal que difere de um quadrado para outro deixa de existir. Neste caso, dois quadrados adjacentes representam uma única
letra sentencial. Veja o ex. da fig. 2.
Não deve-se deixar nenhum ponto “solto” no mapa, devendo cuidar para fazer o
menor número possível de ligações.
Para todos os tipos de mapas, quando se tem todos os quadrados preenchidos, a
simplificação resulta em V (Veja a representação de AB+ÃB+A~b+Ã~B na fig. 4) 
 
Mapas de Karnaugh para 3 letras sentenciais
Neste caso, o mapa pode ser montado como na figura 5 ou como na figura 6. 
Ex: Ã~B~C+ ÃB~C (figuras 5 e 6)
deve-se cuidar apenas o seguinte detalhe. Nesses mapas foi utilizada a rotulação 00,01,11,10 de forma que quando se passa
de um quadrado para o quadrado adjacente muda-se apenas um literal. 
Um ponto isolado no mapa representa a conjunção de 3 literais. Exemplo: ABC na figura 7.
Dois quadrados adjacentes diferem em apenas um literal. Isso significa que o literal que difere de um quadrado para outro
deixa de existir. Exemplo: Figura 8.
AB \ C 0 1
00
01
11
10
Figura 6
A \ BC 00 01 11 10
0
1
Figura 5
A \ B 0 1
0
1
Figura 4
 Apostila de Lógica para a computação 21 
Quatro
quadrados formando uma rede quadrada ou arranjados em linha representam um único literal. Figuras 9 e10.
Resolva:
a) ã~b~c+a~bc+abc+ab~c
b) ã~b~c+a~b~c+a~bc+abc+ab~c+ãb~c
c) bac+a~bc+ãbc+ab~c+ãb~c
d) ã~b~c+a~b~c+a~bc+abc+ãb~c
Mapas de Karnaugh para 4 letras sentenciais
É semelhante ao mapa de 3 letras sentenciais. Neste caso, uma linha inteira ou coluna inteira representa a conjunção de 2
letras sentenciais.
a) ab.~c.~d+ab~cd+abc+abcd b) ab~c.~d+a~b~c.~d+ãb~c.~d+~a~b~c~d
c) ã~b~cd+a~bcd+abcd+ab~cd d) ã~b~c.d+a~b~c.~d+a~bc.d+abc~d+ab~c~d+ãb~c~d
A \ BC 00 01 11 10
0
1
Figura 7
A \ BC 00 01 11 10
0
1
Figura 8
A \ BC 00 01 11 10
0
1
Figura 9
A \ BC 00 01 11 10
0
1
Figura 10
A \ BC 00 01 11 10
0
1
c)
A \ BC 00 01 11 10
0
1
d)
A \ BC 00 01 11 10
0
1
a)
A \ BC 00 01 11 10
0
1
b)
A \ BC 00 01 11 10
00
01
11
10
a)
A \ BC 00 01 11 10
00
01
11
10
b)
A \ BC 00 01 11 10
00
01
11
10
A \ BC 00 01 11 10
00
01
11
10
 Apostila de Lógica para a computação 22 
Exercícios de Lógica – 1a parte
1) Determine a forma sentencial (primitiva) equivalente ao circuito lógico abaixo:
 
2) Para uma tabela-verdade que utiliza as letras A, B e C cujo resultado é VVFFFVVV, determine:
a) a expressão na FND completa
b) a expressão simplificada
c) monte o circuito lógico equivalente à expressão simplificada.
3) Determine a FNDC para:
a) A+ Ã. +ACD 
b) AB + ~C
4) Utilizando os mapas de Karnaugh, simplifique:
a) w.x.y.z + w.x.y.z+ w.x.y.z + w.x.y.z + w.x.y.z + w.x.y.z
b) a.b.c + a.b.c + a.b.c + a.b.c
a) 00 01 11 10 b) 00 01 11 10
00 0
01 1
11
10
5) Dê a expressão simplificada para os seguintes mapas de karnaugh:
a) 00 01 11 10 b) 00 01 11 10
00 0 1 1 1 00 0 0 0 0
01 0 0 0 1 01 1 1 1 1
11 0 0 0 1 11 1 1 1 1
10 0 1 0 1 10 0 1 0 0
c) 00 01 11 10 d) 00 01 11 10
00 0 1 1 0 00 1 1 0 1
01 0 0 0 0 01 0 1 0 0
11 1 0 0 1 11 0 1 1 0
10 0 1 1 0 10 1 0 0 1
 Apostila de Lógica para a computação 23 
e) 00 01 11 10 f) 00 01 11 10
00 0 1 0 0 00 1 1 0 1
01 0 1 1 1 01 1 1 0 0
11 1 1 1 0 11 1 1 1 1
10 0 0 1 0 10 0 0 1 1
 
 Exercícios de Lógica – 2a parte (prática)
Construa os seguintes circuitos lógicos (utilize a ferramenta digital Works para conferir)
1) Um conselho municipal consiste de Presidente, secretário, tesoureiro e um vereador. São aprovados os projetos que
conseguirem a maioria simples dos votos ou o voto do presidente e mais 1. Construa um circuito lógico simplificado
que indique a aprovação do projeto.
2) Uma câmara municipal consiste de Prefeito, Presidente do Conselho da Cidade, Superintendente e três presidentes de
distrito. O voto de cada um tem peso 1. Um projeto que conseguir a maioria simples dos votos é aprovado, contanto
que não seja impugnado por nenhum dos presidentes dos distritos. Construa um circuito lógico simplificado que
indique a aprovação do projeto.
3) Seja um número inteiro não negativo menor do que 15 dado por sua representação binária a3a2a1a0. (por exemplo, se
o inteiro for 3, a3=a2=0 e a1=a0=1; enquanto se o inteiro for 9, a3=a0=1 e a2=a1=0. Construa a expressão e o circuito
lógico correspondente à condição de que o inteiro dado seja primo. Ex: 3: 
0 0 1 1
a3 a2 a1 a0
5) Projete um circuito para um sistema de alarme de uma casa. Uma vez que o sistema é ligado, ele soará um alarme
quando a porta da frente, porta de trás ou a janela dos fundos estiverem abertas. (somente uma janela está ligada no
alarme.) Considerando S como a expressão do circuito, S=?. Utilize as seguintes letras sentenciairs:
 A(alarme ligado ou desligado), D(porta da frente),B(porta de trás),J(janela aberta) e S(soa o alarme)
S=
6) Construa um circuito lógico que indique quando um número de 0 até 7 é divisível por 3. A entrada deve ser em número
binário.
7) Construa um circuito lógico que indique os pares de 0 até 7.
8) A tabela abaixo converte um número de 4 bits para o código “ gray code”. Construa os circuitos para fazer essa
conversão e utiliza os mapas de karnaugh para simplificar a soma-de-produtos resultante:
abcd wxyz
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0000
1000
1100
0100
0110
1110
1010
0010
0011
1011
1111
0111
0101
1101
1001
0001
9) É possível reprojetar o circuito do problemaacima (anterior) utilizando somente portas NAND e inversores (portas
NÃO)? Em caso afirmativo, projete o circuito e em caso negativo, explique o porquê.
W=
X=
Y=
Z=
 Apostila de Lógica para a computação 24 
10)Considerando um esquema de transformação de um número de OCTAL (base 8) para binário (base 2), onde há 7 LEDS
representando os números octais (de 0 até 7) sendo que por exemplo, para representar o número 4 deve-se deixar ligado
somente o LED do dígito 4 (D4) na entrada, construa um circuito lógico onde as 3 saidas (LEDS) representem (em
binário) o número colocado na entrada.
ENTRADAS SAÍDAS
D1 D2 D3 D4 D5 D6 D7 Decimal X Y Z
0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 0 0 1
0 1 0 0 0 0 0 2 0 1 0
0 0 1 0 0 0 0 3 0 1 1
0 0 0 1 0 0 0 4 1 0 0
0 0 0 0 1 0 0 5 1 0 1
0 0 0 0 0 1 0 6 1 1 0
0 0 0 0 0 0 1 7 1 1 1
13) Construa um circuito lógico para simular 2 sinaleiras de uma rua, uma em sentido contrário à outra, cada
uma contendo as 3 luzes (verde, amarela e vermelha) de forma que quando uma abre, a outra feche seguindo
a sequência:
Trabalho (em duplas e deve ser entregue até dia ______) 
--> Invente 3 exercícios semelhantes aos anteriores (parte prática) e resolva-os.
Endereços sugeridos para material extra:
http://fiddle.visc.vt.edu/courses/ee2504/combinational/logic_01.html
http://www.eece.unm.edu/faculty/devries/Net/Homework/boolean.html
 Apostila de Lógica para a computação 25 
Exercícios de Lógica -Parte prática – Resolução do 12 e 13
12) Considerando um esquema de transformação de um número de OCTAL (base 8) para binário (base 2),
onde há 7 LEDS representando os números octais (de 0 até 7) sendo que por exemplo, para representar o
número 4 deve-se deixar ligado somente o LED do dígito 4 (D4) na entrada, construa um circuito lógico onde as
3 saidas (LEDS) representem (em binário) o número colocado na entrada.
ENTRADAS SAÍDAS
D1 D2 D3 D4 D5 D6 D7 Decimal X Y Z
0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 1 0 0 1
0 1 0 0 0 0 0 2 0 1 0
0 0 1 0 0 0 0 3 0 1 1
0 0 0 1 0 0 0 4 1 0 0
0 0 0 0 1 0 0 5 1 0 1
0 0 0 0 0 1 0 6 1 1 0
0 0 0 0 0 0 1 7 1 1 1
 X = D4 + D5 + D6 + D7 : Na verdade o correto seria ~D1.~D2.~D3.D4.~D5.~D6.~D7 + ..., mas supõe-se que o usuário só escolha 1 dígito (D4) no
caso.
 Y = D2 + D3 + D6 + D7 
 Z = D1 + D3 + D5 + D7 
O exercício está resolvido. Apenas como curiosidade, poderia-se fazer aparecer o número em um mostrador
digital. Dessa forma, segundo o exemplo acima, um mostrador deveria mostrar o número 5. Para isso,
inicialmente teríamos que inserir um LED e desenhar todos os números de 1 a 7:
Em seguida devemos, para cada um dos números de 0 até 7, indicar quais leds deverão ser acesos: 
 
X Y Z L1 L2 L3 L4 L5 L6 L7
0 0 0 1 1 1 1 1 1
0 0 1 1 1
0 1 0 1 1 1 1 1
0 1 1 1 1 1 1 1
1 0 0 1 1 1 1
1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1
1 1 1 1 1 1
L1 L2 L3 L4 L5 L6 L7 
00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10
0 . . . 0 . . . . 0 . . . 0 . . . 0 . . 0 . 0 . .
1 . . . 1 . . 1 . . . . 1 . . 1 . 1 . . . 1 . . .
L1= 
L2=
L3= 
L4= 
L5= 
L6= 
Podemos agora, definir o circuito independente de cada uma das 
“partes” do LED, pois como exemplo, a parte “L1” ficará ligada quando 
tivermos um destes números: 0,2,3,5,6,7. O circuito para a “parte” do 
LED L1 então seria:
Devemos depois, simplificar o circuito da “parte” L1 através de mapa 
de karnaugh bem como os circuitos das outras partes (L2-L7).
 Apostila de Lógica para a computação 26 
L7= 
O circuito final é apresentado abaixo:
13) Construa um circuito lógico para simular 2 sinaleiras de uma rua, uma em sentido contrário à outra, cada
uma contendo as 3 luzes (verde, amarela e vermelha) de forma que quando uma abre, a outra feche seguindo
a sequência:
X Y Z L1 L2 L3 L4 L5 L6
0 0 0 1 1
0 0 1 1 1
0 1 0 1 1
0 1 1 1 1
1 0 0 1 1
1 0 1 1 1
1 1 0
1 1 1
Como são seis lâmpadas de sinaleira no total (considerando as 2 sinaleiras) devemos construir 6 circuitos
independentes. Como são 6 combinações de sinaleiras, precisamos de pelo menos 3 bits, que possibilita 8
combinações (0-7).
L1 L2 L3 L4 L5 L6 
00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10 00 01 11 10
0 . . . 0 0 . 0 . . 0 . 0 .
1 . 1 . 1 1 . . 1 1
L1= 
L2=
L3= 
L4= 
L5= 
L6= 
L1
L2
L3
L4
L5
L7
L6
L1
L2
L3
L4
L5
L6
- No estágio 1 teremos as lâmpadas 1 e 6 acesas (L1 e L6)
- No estágio 2 teremos as lâmpadas 1 e 5 acesas (L1 e L5)
- No estágio 3 teremos as lâmpadas 1 e 4 acesas (L1 e L4)
- No estágio 4 teremos as lâmpadas 3 e 4 acesas (L3 e L4)
- No estágio 5 teremos as lâmpadas 2 e 4 acesas (L2 e L4)
- No estágio 6 teremos as lâmpadas 1 e 4 acesas (L1 e L4)
Devemos agora construir os 6 circuitos: L1, L2, L3, L4, L5 e L6
 Apostila de Lógica para a computação 27 
(a .b .c .a )+(b . a)
(b . a)+(c . a)+b . a
b . a+b . a+c . a
v 
(a .b .b . a)+c . a
a .b+a . b+a . c
a .b+a .c
(b .a .b .a)+(b . a)+(b . a ) 
a .b+a . b+a . b+a .b
a .b
(b .a .b .c)+(b .c)+(a .b)
((a . b))+(b .c )+(b . c)+(a . b)
 v
( y . x+x . y+ y) . x
(x . y+ y) . x
x . y
 
(x+x . y+ y) . x+( y+x+ y) . x
(x+ y) . x+(x+ y) . x
(x+ y) . x
x . x+x . y
x+x . y 
x 
 
( y . x+x ). x+( y . x+x+ y ). x
(x ). x+(v ). x
x+x
x 
y . x+( x . y+ y ). x
y . x+( x . y) .( y) . x
y . x+ f . x
x . y
 
y . x+( x . y+ y ). x+( y . x+ x . y)+ y . x
x . y+( y . x) .(x . y)+ y . x
x . y+( y . x)
v
 
y . x+( x . y+ y ). x+( y . x+ x . y)+ y . x¯
y . x+( y . x) .(x . y)+ y . x¯
y . x+( y . x)+ y . x¯
V + y . x¯
v
 
( p→r )→ p
( p¯+r )→ p
( p¯+r )+ p
¯¯p . r¯+ p p
( p→r )→ p¯
( p¯+r )→ p¯
( p¯+r )+ p¯
¯¯p . r¯+ p¯
r¯+ p¯
 
( p→r )→( p . r )
( p¯+r )→ p¯+ r¯
( p¯+r )+ p¯+ r¯
¯¯p . r¯+ p¯+ r¯
p¯+ r¯
 
( p . r→r )→( p . r )
(( p . r )+r )→ p¯+ r¯
(( p . r )+r )+ p¯+ r¯
p . r . r¯+ p¯+ r¯
F+ p¯+ r¯
p¯+ r¯
( p¯→r )→ p¯
( ¯¯p+r )→ p¯
( p+r )+ p¯
p¯ . r¯+ p¯
p¯
 
( p . r→( p. q. r+ p))→ p . r
(( p . r )+(( p¯+ q¯). r+ p))→ p . r
( p . r )+( p¯ . r+ q¯ . r+ p)→ p . r
( p . r )+(r+ q¯ . r+ p)→ p . r
p¯+ r¯+(r+ p)→ p . r
V → p. r
F+ p . r
p¯+ r¯
 
(( p . r→r )→( p . r→ p))→ p
(( p . r+r )→( p . r+ p))→ p
( p¯+r¯+r )+( p . r+ p)→ p
(V )+( p)→ p
(F+ p)+ p
p¯+ p 
v
 
((( p . r )→r )→( p . r→ p))→ p
(( p . r+r )→( p . r+ p))→ p
(r→( p . r+ p))→ p
( r¯+ p)+ p
¯¯r . p¯+ p
r+ p
( p . q→r )→( p . r )
( p . q+r )→ p¯+ r¯
( p .q+r )+ p¯+ r¯
p .q+r+ r¯+ p¯
p .q+V + p¯ 
v
( p→r )  p
( p¯+r ). p+( p¯+r ). p¯
p¯ . p+r . p+ ¯¯p . r¯ . p¯
r . p+F
r . p
( p→r )  p¯
( p¯+r ). p¯+( p¯+r ). ¯¯p
p¯ . p¯+r . p¯+ ¯¯p . r¯ . p
p¯+r . p¯+ p . r¯
p¯+ p . r¯
p¯+ r¯
( p . r→r )  p . r
( p . r )+r  p¯+ r¯
p¯+ r¯+r  p¯+ r¯
V  p¯+ r¯
V .( p¯+r¯ )+F . ( p¯+ r¯ )
p¯+ r¯
( p→r )  p . r
( p¯+r ). p . r+( p¯+r) . p . r
( p¯+r ).( p¯+ r¯ )+ ¯¯p. r¯ . p . r
( p¯ . p¯+ p¯ . r¯ .+r . p¯+r . r¯ )+F
p¯+ p¯ . r¯+r . p¯+F
p¯+r . p¯ p¯
( p¯→r )  p¯
( ¯¯p+r ). p¯+( ¯¯p+r ). ¯¯p
p . p¯+r . p¯+ p¯ . r¯ . p
F+r . p¯+F
r . p¯
(( p . r→r )→( p . r→ p))  p
(( p . r+r )→( p . r+ p))  p
(r→ p)  p
r¯+ p  p
( r¯+ p). p+( r¯+ p). p¯
r¯ . p+ p . p+ ¯¯r . p¯ . p¯
r¯ .p+ p+r . p¯
p+r . p¯
p+r
(( p . q→r ))  p . r
(( p . q+r))  p . r
( p .q . r¯ )  p . r
( p .q . r¯ )  p . r
( p .q . r¯ ). p . r+( p . q . r¯ ) . p . r
(( p¯+ q¯). r¯ ) .( p¯+ r¯ )+( p.q+ ¯¯r ). p . r
( p¯ . r¯+ q¯. r¯ ).( p¯+ r¯ )+ p. q. p . r+ p . r . r
( p¯ . r¯ . p¯+ p¯ . r¯ . r¯+ q¯ . r¯ . p¯+q¯ . r¯ . r¯ )+...
p¯ . r¯+ p¯ . r¯+ q¯ . r¯ . p¯+ q¯ . r¯+ p . r
p¯ . r¯+q¯ . r¯+ p . r
p¯ . r¯+q¯ . r¯+ p . r
30)
31)
32)
33)
41)
42)
43)
44)
34)
35)
45)
36)
46)
37)
38)
39)
47)
40)
48)
55)
50)
51)
52)
53)
54)
49)
	Proposição simples
	Regras de Inferência
	1) C
	P
	2) S  A
	P
	3) C  S
	P
	4) S
	5) A
	As três primeiras suposições da resolução têm um P ao lado, indicando que cada uma delas é uma premissa. Então, deduzimos a conclusão ‘A’ em duas etapas de raciocínio. A primeira etapa é das linhas 1 e 3 para a linha 4. A Segunda etapa é das linhas 2 e 4 para 5.
	Os números à direita denotam as linhas das quais 4 e 5 são derivadas. As duas etapas tem a mesma forma. Cada uma delas é uma instância da primeira das 10 regras de inferência, denominada modus ponens que chamaremos ‘MP’.
	MP ( E)
	RAA ( ~I)
	Exercícios complementares
	As 10 regras de Inferência (permitido utilizar em prova)