Introdução a lógica

Prévia do material em texto

ÍNDICE
UNIDADE I - TEORIA ELEMENTAR DOS CONJUNTOS
CAPÍTULO 1 - CONJUNTOS DEFINIÇÕES E OPERAÇÕES
1.1 – INTRODUÇÃO	5
1.2 - RELAÇÕES DE PERTINÊNCIA E INCLUSÃO 	5
1.3 - OUTRAS FORMAS DE NOTAÇÃO DE CONJUNTOS	5
EXERCÍCIOS 01. 		6 
1.4 - OPERAÇÕES COM CONJUNTOS. 		6 
1.5 - PROPRIEDADES DAS OPERAÇÕES		7
1.6 - OUTRAS PROPRIEDADES	7
EXERCÍCIOS 02		7
1.7 - PRODUTO CARTESIANO		8
1.8 – RELAÇÃO		8
1.9 - NUMERAL DE UM CONJUNTO		8
EXERCÍCIOS 3.		9
UNIDADE II - A LÓGICA DAS PROPOSIÇÕES
CAPÍTULO 2 - PROPOSIÇÕES E CONECTIVOS	
2.1 - SENTENÇAS E EXPRESSÕES		10
2.2 - OS PRINCÍPIOS OU AXIOMAS DA LÓGICA MATEMÁTICA	10
2.3 - PROPOSIÇÕES SIMPLES E COMPOSTAS	11
2.4 - OS CONECTIVOS 		11
EXERCÍCIOS 04		12
CAPÍTULO 3 - ÁLGEBRA DAS PROPOSIÇÕES
3.1 - TABELA VERDADE		13
3.2 - TABELAS INICIAIS		13
EXERCÍCIOS 05		13
3.3 - OUTRAS TABELAS VERDADES		14
3.4 - PONTUAÇÃO DE PROPOSIÇÕES COMPOSTAS	16
EXERCÍCIOS 06		17
CAPÍTULO 4 - TAUTOLOGIAS E CONTRADIÇÕES
4.1 – DEFINIÇÕES		19
EXERCÍCIOS 7		19
4.2 - IMPLICAÇÃO E EQUIVALÊNCIA LÓGICAS	20
4.3 - PROPOSIÇÕES ASSOCIADAS A UMA CONDICIONAL	20
EXERCÍCIOS 08 		21
4.4 – EXPRESSANDO OS CONECTIVOS (, ( E ( EM FUNÇÃO DE ~, ( E (.	21
4.5 - USANDO SOFTWARES PARA CONSTRUÇÃO DE TABELAS VERDADE	21
EXERCÍCIOS 09		21
UNIDADE 3 - ÁLGEBRA DE BOOLE	
CAPÍTULO 5 - PORTAS LÓGICAS
5.1 - AS MÁQUINAS QUE CALCULAM		22
5.2 - A LÓGICA BINÁRIA OU ÁLGEBRA BOOLEANA	22
5.3 - PRINCÍPIOS BÁSICOS DA ÁLGEBRA BOOLEANA	23
EXERCÍCIO 10		23
5.4 - TABELAS OPERACIONAIS 		23
EXERCÍCIOS 11		24
5.5 - SIMPLIFICAÇÃO DE EXPRESSÕES		24
EXERCÍCIOS 12		24
5.6 - PORTAS LÓGICAS		24
5.7 - TABELAS DAS OPERAÇÕES LÓGICAS		25
5.8 - ALGUNS EXEMPLOS		25
EXERCÍCIOS 13		25
UNIDADE 4 - MÉTODOS DE RACIOCÍNIO
CAPÍTULO 6 - DEDUÇÃO E INFERÊNCIA LÓGICA
6.1 – INTRODUÇÃO		27
6.2 - MÉTODO DEDUTIVO 		27
EXERCÍCIOS 14		28
6.3 - REGRAS DE INFERÊNCIA		28
6.4 - ARGUMENTOS BÁSICOS VÁLIDOS		29
6.5 - DEMONSTRAÇÕES USANDO AS REGRAS DE INFERÊNCIAS	29
EXERCÍCIOS 15	29							 
INTRODUÇÃO À ÁLGEBRA
PREÂMBULO
	 PREÂMBULO
             A Lógica é uma ciência com características matemáticas mas, fortemente ligada à Filosofia. Ela cuida das regras do bem pensar, ou do pensar correto, sendo, portanto, um instrumento do pensar. Aristóteles, filósofo grego (384?-322a.C) em sua obra Órganon, distribuida em 8 volumes, foi o seu principal organizador.
          Através da Lógica pode-se avaliar a validade ou não de raciocínios que têm por base premissas iniciais.
          Vejamos um exemplo:
Raciocínio I - (1ª premissa) Todo homem é mortal - (2ª premissa) Sócrates é mortal.
                  Conclusão: Sócrates é mortal.
Raciocínio II- (1ª premissa) Todo homem é mortal - (2ª premissa) Sócrates é homem.
                  Conclusão: Sócrates é mortal.
          À primeira vista, todos os dois raciocínios parecem verdadeiros. Entretanto, o primeiro é falso, pois: Sócrates pode perfeitamente ser o gatinho da minha vizinha. Já, o segundo raciocínio é universamente verdadeiro.
          No decorrer deste curso veremos como, a partir de uma lógica formal, podemos analisar a veracidade ou não de um conjunto de premissas e a correspondente conclusão.
	 George Boole (1815-1864), em seu livro A Análise Matemática da Lógica estruturou os princípios matemáticos da lógica formal, que, em sua homenagem foi denominada Álgebra Booleana.  No século XX, Claude Shannon aplicou pela primeira vez a álgebra booleana em interruptores de onde se originaram os atuais computadores. 
 
UNIDADE I – TEORIA ELEMENTAR DOS CONJUNTOS
CAPÍTULO 1 – CONJUNTOS DEFINIÇÕES E OPERAÇÕES
1.1 – INTRODUÇÃO
 A noção de conjunto é intuitiva. Esta noção está associada a uma coleção de elementos, que, em geral, apresentam uma propriedade comum.
Exemplos: conjuntos das vogais, conjunto dos números reais, conjunto dos números inteiros maiores que 5 e menores que 9.
Um conjunto é indicado, em geral, por uma letra maiúscula e seus elementos relacionados entre duas chaves. Assim, se A é o conjunto das vogais indica-se: A = {a, e, i, o, u}. 
A idéia de conjunto pode ser estendida para
(i) Conjunto unitário: 
 Conjunto das consoantes contidas na palavra areia: {r}. 
(ii) Conjunto vazio: 
 Conjunto dos números inteiros compreendidos entre 7 e 8. 
Como não existe nenhum inteiro compreendido entre 7 e 8, indicamos { } ou (.
Obs. {(} é um conjunto unitário cujo elemento é (.
(iii) Conjunto infinito:
 O conjunto infinito tem, como o próprio número indica, infinitos elementos. Um exemplo bem simples de conjunto infinito é o conjunto dos números naturais N = {0, 1, 2, 3, ...}.
(iv) Conjuntos discretos e densos: 
 Usados principalmente para conjuntos numéricos. 
Um conjunto é dito discreto quando, estabelecida a ordem de seus elementos, entre dois elementos sucessivos não existe outro elemento.
O conjunto dos números naturais é um conjunto discreto, pois, por exemplo, entre o 4 e o 5 não existe nenhum outro número natural. Os conjuntos dos números racionais e dos números reais são densos. Pois, quaisquer que sejam dois elementos escolhidos sempre existem infinitos números entre eles.
Veja, por exemplo: escolhidos os racionais 1/3 e 1/2 podemos escrevê-los nas formas 10/30 e 15/30. Entre eles temos 11/30, 12/30, ..., 14/30. Se escolhido um denominador maior, maior quantidade de racionais teremos entre 1/3 e 1/2.
1.2 – RELAÇÕES DE PERTINÊNCIA E INCLUSÃO 
Seja A um conjunto. Se x é um elemento do conjunto A, indicamos x ( A, que se lê: o elemento x pertence ao conjunto A. Caso contrário, se y não é elemento do conjunto A, indica-se 
y ( A.
É importante notar que os símbolos ( e ( somente podem ser usados quando se relacionam elemento e conjunto.
	Consideremos então os conjuntos A = {a, b, c, d, e}, B = {b, c, d} e C = {c, e, f}. Como pode ser notado todo elemento de B pertence ao conjunto A. O mesmo não acontece com os conjuntos C e A. No caso dos conjuntos A e B, indica-se A ( B ou B ( A, que se lê, respectivamente A contém B e B está contido em A. Nestas condições, o conjunto B é um subconjunto de A.
Para os conjuntos A e C, escreve C ( A que se lê, C não está contido em A.
Quando se relaciona um conjunto com ele mesmo usa A ( A ou A ( A. A é um subconjunto próprio de A.
Convém notar que o conjunto vazio está contido em todo conjunto. Isto é ( ( A. O conjunto vazio é subconjunto de qualquer conjunto.
1.3 – OUTRAS FORMAS DE NOTAÇÃO DE CONJUNTOS
	Já foi visto anteriormente que um conjunto pode ser indicado escrevendo seus elementos entre duas chaves. Esta forma de notação é denominada LISTAGEM.
Pode-se também representar um conjunto indicando a propriedade comum a seus elementos.
Nesta forma de notação indicamos A = {x | P(x)}, que se lê “A é conjunto dos elementos “x” tais que P é a propriedade comum”.
Temos, por exemplo: A = {x | x é vogal}, que se lê A é o conjunto dos elementos x tais que x é vogal. “x” é uma variável que pode assumir diversos valores. 
Assim, se x = a, e, i, o, u, x ( A e se x = b, x ( A.
Uma terceira forma, chamada “diagrama de Venn”, consiste em circundar os elementos por linhas.
 
	
 
EXERCÍCIOS 01.
1 – Use o símbolo adequado a cada uma das seguintes sentenças abaixo, sendo definidos os conjuntos: A = {a, e, i, o , u}, B = {2, 3, 4, 5}, C = {e, u}, D = {x | 1 < x < 7} e D = {b, c}
(a) B______D (b) D_____A (c) ______ C (d) e ____ C (e) x ____ A.
2 – Represente o conjunto B usando a propriedade comum a seus elementos.
3 – Escreva, sob forma de listagem, o conjunto D.
4 – É falso ou verdadeiro que (a) ( ( { ( , p, q}? (b) {3} ( {1, 2, 3, {3}}?
Justifique suas respostas. 
Para o item (b) o sinal ( pode ser ou não substituído por (? Justifique sua resposta.
1.4 – OPERAÇÕES COM CONJUNTOS.
	Uma operação é um processo escolhido a partir do qual, dados dois elementos quaisquer se pode obter um terceiro elemento de mesma natureza.
	Já é do domíniopúblico operações como adição e multiplicação de números inteiros, que são representadas pelos sinais + e X (ou .) respectivamente.
	Assim, ao indicarmos 3 + 4, significa que escolhemos um processo que irá resultar no inteiro 7 e se indicarmos 3 . 4, o processo escolhido permite obter o resultado 12.
	Generalizando indicamos (a ( b) ( c, para representar uma operação ( que, tomados os elementos “a” e “b”, teremos como resultado o elemento (de mesma natureza) “c”.
	Para conjuntos são definidas as operações:
(i) UNIÃO 
	Indicada pelo símbolo (, e definida por A ( B = {x | x ( A ou x ( B}. 
Como será visto no estudo das sentenças, o conectivo “ou”, simbolizado por (, é usado para indicar que um elemento pertence a A ( B quando pertencer somente ao conjunto A, somente ao conjunto B ou a ambos os conjuntos.
	Temos por exemplo: A = {1, 2, 3, 4} e B = {3, 4, 5, 6} ( A ( B = {1, 2, 3, 4, 5, 6}.
(ii) INTERSEÇÃO
	Indicada por (, esta operação é definida por A ( B = {x | x ( A e x ( B}. 
	O conectivo e, indicado por (, é usado para indicar que x ( (A ( B) se, e somente se, x pertencer aos dois conjuntos ao mesmo tempo.
Exemplos: 
(1) A = {1, 2, 3, 4}, B = {3, 4, 5, 6} ( A ( B = {3, 4}
(2) A = {1, 2, 3, 4}, B = {5, 6, 7, 8} ( A ( B = 
(iii) DIFERENÇA	
	Indicada pelo sinal -, denota-se a diferença entre o conjunto A e o conjunto B por A – B.
	Esta operação é definida por A – B = {x | x ( A e x ( B}.
	
	Se B é um subconjunto de A, pode-se escrever A – B = CB,A que se lê complementar de B em relação a A.
Exemplo: A = {1, 2, 3, 4}, B = {3, 4, 5, 6} ( A - B = {1, 2} e B – A = {5, 6}.
Usando diagramas podemos indicar
	
	
	
	
 1.5 – PROPRIEDADES DAS OPERAÇÕES
	Sejam ( e ( duas operações definidas em um conjunto A e x, y e z elementos desse conjunto.
(i) Se, para todo x e y de A, x ( y = y ( x, a operação ( é dita comutativa.
(ii) Se, para todos x, y, z de A, x ( (y ( z) = (x ( y) ( z, a operação ( é dita associativa.
(iii) Se em A existe um elemento n, tal que, ( x ( A, se tem x ( n = n ( x = x, “n” é o elemento neutro para a operação (.
(iv) Se em A, para cada elemento x de A, existir um elemento y, tal que x ( y = y ( x = n, então a operação admite inverso ou simétrico. “x” é o inverso de “y” e “y” é o inverso de x para a operação (.
(v) Se para todos x, y, z de A, x ( (y ( z) = (x ( y) ( (x ( z) então a operação ( é distributiva em relação a (.
	Com relação às operações com conjuntos temos:
(i) x ( (A ( B) ( (x ( ou x ( B) ( (x ( B ou x ( A) ( x ( (B ( A) ( A ( B = B ( A.
 x ( (A ( B) ( (x ( e x ( B) ( (x ( B e x ( A) ( x ( (B ( A) ( A ( B = B ( A.
Portanto, as operações união e interseção são comutativas.
Deixamos como exercício a demonstração dos itens a seguir.
(ii) A ( (B ( C) = (A ( B) ( C e A ( (B ( C) = (A ( B) ( C. Associatividade.
(iii) A ( (B ( C) = (A ( B) ( (A ( C) e A ( (B ( C) = (A ( B) ( (A ( C). Distributividade.
(iv) O conjunto vazio é o elemento neutro da operação união.
 Se A, B, C são subconjuntos de um conjunto U, então U é o elemento neutro da operação interseção. O conjunto U é chamado conjunto universo.
(v) As operações união e interseção não admitem inverso ou simétrico.
1.6 – OUTRAS PROPRIEDADES
	Sejam 
 U = conjunto universo, 
 = conjunto vazio, 
 A = complementar de A em relação a U. 
Além das propriedades acima, tem-se:
(vi) A ( A = A e A ( A = A. Idempotente.
(vii) A ( (A ( B) = A e A ( (A ( B) = A. Absorção.
(viii) (A ( B) = A ( B e (A ( B) = A ( B. Regras de De Morgan.
(ix) A = A.
(x) A ( A = U e A ( A = 
(xi) A ( U = U e A ( = 
EXERCÍCIOS 02
1. Demonstre as propriedades ii, iii, vi, vii, viii, ix, x e xi relativas às operações com conjuntos.
2. Sejam A = {x|x ( N e 3 < x < 10}, B = {y|y ( N e 4 < y < 12} e C = {z|z ( N e 10 < z < 15} três conjuntos. Considere ainda os conjuntos: vazio e universo U = {w | w ( N e 0 < w < 20}
Determine: 
(a) A (b) (A ( B) ( C (c) (A ( B) ( C (d) A – B (e) (A ( B) ( C (f) (A ( B) ( C
(g) (B – C) ( A (h) (B – C) ( A (i) (A ( B) ( C (i) (A ( B) ( C
3. Represente os conjunto A, B , C, U em diagramas. Mostre neste diagrama os resultados obtidos no exercício 2.
1.7 – PRODUTO CARTESIANO
	Sejam A e B dois conjuntos. Define-se o produto A X B como sendo o conjunto dos pares da forma (x, y) tais que x ( A e y ( B.
		Isto é A X B = {(x, y) | x ( e y ( B}.
Se A = B, então A X B = B X A. O mesmo não acontece quando A for diferente de B. Isto é, o produto cartesiano não é comutativo.
Exemplo: Sejam A = {1, 2, 3} e B = {3, 4} dois conjuntos.
Pela definição temos: A X B = {(1, 3), (1, 4), (2, 3), (2, 4), (3, 3), (3, 4)} e
B X A = {(3, 1), (3, 2), (3,3), (4, 1), (4, 2), (4, 3)}.
Como pode ser observado pelo exemplo acima A X B ( B X A.
1.8 – RELAÇÃO
	Chama-se relação ao processo de escolha de pares de um produto cartesiano.
Indica-se, uma relação entre os elementos “a” e “b” do par (a, b) por a ( b.
Seja por exemplo a ( b ( a + b = 5, onde (a, b) são os pares do produto A X B obtido no exemplo do item anterior.
Esta relação define o conjunto ( = {(1, 4), (2, 3)}.
Uma relação ( pode ser:
(i) Simétrica, se a ( b ( b ( a.
(ii) Reflexiva, se a ( a.
(iii) Transitiva se a ( b e b ( c ( a ( c.
Uma relação simétrica, reflexiva e transitiva é denominada relação de equivalência, enquanto que uma relação não simétrica, não reflexiva e transitiva é denominada relação de ordem.
Tomando, por exemplo, o conjunto de alunos de uma classe e ( a relação “mesma altura que”, podemos concluir facilmente que, se A, B, C são alunos desta classe:
(1) A ( B ( B ( A, pois se A tem a mesma altura que B, B terá a mesma altura que A.
(2) A ( A, pois A tem a mesma altura que ele mesmo.
(3) A ( B e B ( C ( A ( C. As alturas dos três são iguais.
Assim, a relação “mesma altura que” permite ordenar os alunos por altura. Esta é então uma relação de ordem.
Seja agora a relação ( = “irmão de”.
Esta relação é simétrica, não reflexiva e transitiva.
Se considerarmos a relação ( = “primo de” ela será simétrica, não reflexiva e não transitiva.
Com relação à transitividade, A e C podem ser irmãos.
1.9 – NUMERAL DE UM CONJUNTO
	Simbolizado por n(A) o numeral do conjunto A é igual ao número de elementos desse conjunto A.
Exemplo: se A = {a, b, c, d, e} então n(A) = 5 pois A o conjunto A tem cinco elementos.
Para a união de conjuntos temos:
(1) n(A ( B) = n(A) + n(B) – n(A ( B), pois em n(A) e n(B) os elementos comuns (pertencentes à interseção) estão computados duas vezes; e
(2) n(A ( B ( C) = n(A) + n(B) + n(C) – n(A ( B) – n(A ( C) – n(B ( C) + n(A ( B ( C).
EXERCÍCIO RESOLVIDO:
Em um concurso onde foram aplicadas apenas provas de Português e Matemática e, para que o candidato seja classificado ele deve ser aprovado nas duas disciplinas. Após a correção das provas verificou-se que 100 candidatos foram aprovados em Matemática e 130 foram aprovados em Português, mas apenas 80 foram classificados. Quantos candidatos participaram do concurso?
Solução: n(M) = 100 (aprovados em Matemática); n(P) = 130 (aprovados em Português) e n(M ( P) = 80.
Assim, n(M ( P) = 100 + 130 – 80 = 150 candidatos.
EXERCÍCIOS 3.
1. Dez pessoas se reuniram para, ao final de um ano, registrarem uma firma. Ficou combinado que cada um deveria aplicar uma certa importância em caderneta de poupança em compra de ações, podendo se assim o desejasse aplicar uma parte em poupança e outra em ações.
O responsável pelo controle ao selecionar os recibos das aplicações verificou-se que haviam 8 aplicações em poupança e 6 aplicações em ações. Quantas, da dez pessoas, dividiram suas aplicações?
2. Em uma classe do terceiro do segundo grau 10 alunos foram aprovados sem necessidade de uma prova final. Ao fazer o controle para a realização da prova final verificou-se que:
(a) somente será necessário aplicar provas de Matemática, Física e Química.
(b) 18 alunosdeverão fazer prova final de Matemática.
(c) 19 alunos deverão fazer prova final de Física.
(d) 15 alunos deverão fazer prova final de Química.
(e) 10 alunos deverão fazer prova final de Matemática e Física.
(f) 9 alunos deverão fazer prova final de Matemática e Química.
(g) 6 alunos deverão fazer prova final de Física e Química.
(h) 4 alunos deverão fazer prova final de Física, Química e Matemática.
Qual é o número de alunos dessa classe?
3. Em uma cidade com 41.520 habitantes são publicados dois jornais A e B. Se 8.050 lêem o jornal A, 13.200 lêem o jornal e 1230 lêem os dois jornais, quantos habitantes da cidade não lêem nenhum dos dois jornais?
4. Certa região, com 15000 lavradores, 
(a) 7000 plantam tomate;
(b) 4800 plantam alface;
(c) 5600 plantam batata.
(d) 2100 plantam tomate e alface;
(e) 1500 plantam tomate e batata;
(f) 1400 plantam alface e batata;
(g) 800 plantam tomate, alface e batata.
Responda:
(1) quantos plantam pelo menos uma das três espécies?
(2) quantos não plantam nenhuma das três espécies?
(3) quantos plantam tomate e alface mas não plantam batatas?
(4) quantos plantam apenas batata?
5. Em uma cidade com 45000 habitantes, 12.000 são brasileiros, 10.000 são franceses, 5.000 são ingleses e os demais são espanhóis. Quantos são espanhóis?
UNIDADE II – A LÓGICA DAS PROPOSIÇÕES
CAPÍTULO 2 – PROPOSIÇÕES E CONECTIVOS	
2.1 – SENTENÇAS E EXPRESSÕES
	Consideremos as indicações abaixo:
(1) O Brasil é pentacampeão;
(2) Chove;
(3) 3 + 7 = 12
(4) x2 + 5 = 9
(5) Fulano é aluno da UNIPAC.
(6) x + 2
(7) Vermelho.
Observando as cinco primeiras notamos que estas têm um sentido completo (existe um verbo) enquanto que as duas últimas não exprimem nenhum pensamento com sentido completo. 
Às cinco primeiras chamamos de sentenças e as duas últimas chamamos de expressões.
Assim, definimos:
Definição 1 – Sentença é um conjunto de palavras ou símbolos que exprimem um pensamento com sentido completo. 
Uma sentença é dita fechada quando admite um único julgamento FALSO (F) como em (3) ou VERDADEIRO (v) como em (1). As sentenças fechadas são chamadas de proposições.
Na indicação (4), x é uma variável que pode assumir diversos valores. Existem valores que tornam a sentença verdadeira e existem valores que tornam a sentença falsa. Para x = 2 e x = - 2 a sentença é verdadeira e para quaisquer outros valores, a sentença é falsa.
O mesmo ocorre com a indicação (5). A sentença será verdadeira dependendo do valor atribuído à variável “fulano”.
Sentenças como estas, que admitem um julgamento falso ou verdadeiro dependente do valor atribuído à variável, são chamadas de sentenças abertas.
Definição 2 – Expressões são frases que não apresentam um sentido completo. Isto é, não permitem julgamentos.
	São exemplos de expressões as indicadas nos itens 6 e 7.
2.2 – OS PRINCÍPIOS OU AXIOMAS DA LÓGICA MATEMÁTICA	
	Para o estudo das proposições, a Lógica Matemática, toma como princípios:
AXIOMA Nº 1 – PRINCÍPIO DA NÃO CONTRADIÇÃO	
 “Uma proposição não pode ser, ao mesmo tempo, falsa e verdadeira.”
AXIOMA Nº 2 – PRINCÍPIO DO TERCEIRO EXCLUÍDO
 “Toda proposição ou é verdadeira ou é falsa. Não verificando nunca uma terceira opção.”
Vejamos alguns exemplos:
As proposições: (1) p: o número 21 é ímpar; (2) q: o inteiro 3 é menor que o inteiro 5, são verdadeiras.
As proposições: (3) r: 5 está compreendido entre 9 e 15; (4) s: A Terra ilumina o Sol, são falsas.
	De acordo com os princípios acima, uma proposição, admite um e apenas um dos valores VERDADEIRO (V) ou FALSO (F). O julgamento F ou V da proposição é denominado valor lógico da proposição.
	Se “p” é uma proposição indicaremos V(p) o valor lógico da proposição “p”. Assim, V(p) = V se p for verdadeira ou V(p) = F se p for falsa.
Considerando as proposições dos exemplos acima teremos: 
V(p) = V(q) = V e V(r) = V(s) = F.
2.3 – PROPOSIÇÕES SIMPLES E COMPOSTAS
	Uma proposição pode ser simples (também denominada atômica) ou composta (também denominada molecular).
As proposições simples apresentam apenas uma afirmação. Podemos considerá-las como frases formadas por apenas uma oração. Representaremos as proposições simples por letras latinas minúsculas.
Como exemplo: 
(1) p: eu sou estudioso; (2) q: Maria é bonita: (3) r: 3 + 4 > 12.
As proposições compostas apresentam mais de uma proposição simples em sua formação. Podemos considerá-las como um período composto de várias orações. Indicaremos as proposições compostas por letras latinas maiúsculas.
Se P é uma proposição composta das proposições simples p, q, r, ..., escrevemos P(p, q, r,...)
Exemplos:
(4) P: Paulo é estudioso e Maria é bonita.
P é a composta das proposições simples p: Paulo é estudioso e q: Maria é bonita.
(5) Q: Maria é bonita ou estudiosa.
Q é a composta das proposições simples p: Maria é bonita e q: Maria é estudiosa.
(6) R: Se x = 2 então x2 + 1 = 5.
R é a composta das proposições simples p: x = 2 e q: x2 + 1 = 5.
(7) S: a > b se e somente se b < a.
S é a composta das proposições simples p: a > b e q: b < a.
2.4 – OS CONECTIVOS 
	Para se formar novas proposições a partir de proposições dadas são usadas palavras ou termos a quem chamamos de conectivos.
Na Lógica Matemática, os conectivos usados são:
- Negação: indicado pelo símbolo ~.
 	Assim, se p : A Lua é um satélite da Terra, então ~p significa “A Lua não é um satélite da Terra” ou “não é verdade que a Lua é um satélite da Terra”.
- Conjunção: “e” simbolizado por (.
 Sejam as proposições simples p: Chove e q: faz frio. A proposição composta P(p,q) formada a partir do conectivo ( é P: p ( q que significa “chove e faz frio”.
- Disjunção: “ou” simbolizado por (.
	Se p: 3 + 4 > 5 e q: 3 – 1 = 2, a composta P(p, q) formada ao usar o conectivo ( é P: p ( q, que se lê P: 3 + 4 > 5 ou 3 – 1 = 2.
Na disjunção as duas proposições não são contraditórias.
- Disjunção exclusiva: “ou” simbolizado por ( 
Na disjunção exclusiva, as duas proposições não podem ocorrer ao mesmo tempo.
Tomando por exemplo, as proposições p: x é par e q: x é impar, x pode ser par ou ímpar, mas p não pode ser par e ímpar ao mesmo tempo.
Escrevemos P(p, q) = p ( q.
- Condicional: se...então... simbolizado por (.
	Temos por exemplo: p: A e B são dois ângulos opostos pelo vértice e q: A e B são iguais.
A composta usando a condicional é P(p, q) = p ( q, que significa “se A e B são dois ângulos opostos pelo vértice então A e B são iguais.”
- Bicondicional: ...se e somente se... simbolizado por (.
	Sejam p: chove e q: faz frio. A composta usando a bicondicional é P(q, q) = p ( q, significando: chove se e somente se faz frio.
EXERCÍCIOS 04
1. Determine o valor lógico de cada uma das seguintes proposições:
a) Santiago é a capital do México. b) Brasília é a capital do Brasil.
c) Cristóvão Colombo foi o descobridor do Brasil. d) (a + b)3 = a3 + b3.
e) A soma dos ângulos internos de um triângulo é 180º.
f) Os lados opostos de um paralelogramo são iguais.
g) 3 + 4 < 9 h) 1/3 > 1/4.
2. Considere as proposições p: Todo homem é mortal e q: Sócrates é mortal.
Represente simbolicamente as proposições:
a) Se todo homem é mortal então Sócrates é mortal.
b) Todo homem é mortal ou Sócrates é mortal.
c) Sócrates é mortal se e somente se todo homem é mortal.
d) Todo homem é mortal ou Sócrates é mortal.
e) Não é verdade que Sócrates é mortal.
f) Não é verdade que (Sócrates é mortal ou todos os homens são mortais).
3. Considere as proposições p: Pedro é italiano e q: Pedro é brasileiro.
Represente simbolicamente as proposições:
a) Pedro é italiano ou Pedro é brasileiro. (cuidado).
b) Pedro é italiano e Pedro é brasileiro.
c) Pedro é italiano e Pedro não é brasileiro.
d) Não é verdade que (Pedro é italiano e Pedro não é brasileiro).
4. Sejam as proposições p: 19 é um número primo e q: 12 é um númeropar. Traduza em palavras as sentenças: 
a) p ( q b) p ( q c) p ( q d) p ( q e) p ( q
f) ~( p ( q) g) ~p ( q h) ~(p ( q) i) ~~p j) ~(~p ( ~q).
5. Sejam as proposições p: 2 < x < 7 e q: x2 + 1 < 50. Traduza em palavras as sentenças: 
a) p ( q b) p ( q c) p ( q d) p ( q e) p ( q
f) ~( p ( q) g) ~p ( q h) ~(p ( q) i) ~~p j) ~(~p ( ~q).
k)~(p v q) ( (p ( ~q)
CAPÍTULO 3 – ÁLGEBRA DAS PROPOSIÇÕES
3.1 – TABELA VERDADE
	Toda proposição derivada de proposições simples tem seu valor lógico que depende exclusivamente dos valores lógicos das proposições primitivas.
Para obter os valores lógicos de uma proposição derivada recorremos a um algoritmo denominado tabela verdade no qual figuram todos as possíveis combinações dos valores lógicos das proposições primitivas.
Tal algoritmo é construído conforme abaixo:
 Para uma proposição Para duas proposições Para três proposições
	
	
O número de linhas é determinado pelo número de arranjos com repetição de dois elementos tomados “n” a “n” onde “n” é o número de proposições combinadas, que é (AR)2n = 2n.
Para 4 proposições, a tabela verdade terá 24 = 16 linhas.
 
3.2 – TABELAS INICIAIS 
		Vejamos como são as tabelas das proposições: ~p, p ( q, p ( q, p ( q, p ( q.
 
 
		
Analisando as tabelas observa-se que:
- Negação: se V(p) = V então V(~p) = F e se V(p) = F então V(~p) = V.
- Disjunção: V(p ( q) = F se e somente se V(p) = F e v(q) = F.
- Disjunção exclusiva: V(p ( q) = F quando V(p) = V(q).
- Conjunção: V(p ( q) = V somente quando V(p) = V(q) = V.
- Condicional: V(p ( q) = F somente quando V(p) = V e V(q) = F.
- Bicondicional: V(p ( q) = V quando V(p) = V(q).
EXERCÍCIOS 05
1. Dê o valor lógico das seguintes proposições:
a. A Lua é um satélite da Terra e o planeta Vênus gira em torno da Terra.
b. Uma estrela tem luz própria ou o sol é um planeta.
c. Se 3 é par então 3 + 1 é impar.
d. Se 3 é par então 5 é par.
e. 4 + 3 = 5 se e somente se 4 = 2 + 2.
f. Santos Dumont inventou o avião ou Cabral descobriu o caminho para as Índias.
2. Dê o valor lógico das seguintes proposições:
a. p ( q, se V(p) = F e V(q) = F.		b. p ( q, se V(p) = F e V(q) = F.
c. p ( q, se V(p) = F e V(q) = F.		d. p ( q, se V(p) = F e V(q) = F.
e. p ( q, se V(p) = V e V(q) = F.		f. p ( q, se V(p) = V e V(q) = F.
g. p ( q, se V(p) = V e V(q) = F.		h. p ( q, se V(p) = V e V(q) = F
I. p ( q, se V(p) = F e V(q) = V.		j. p ( q, se V(p) = F e V(q) = V.
k. p ( q, se V(p) = F e V(q) = V.		l. p ( q, se V(p) = F e V(q) = V.
m. p ( q, se V(p) = V e V(q) = V.		n. p ( q, se V(p) = V e V(q) = V.
p. p ( q, se V(p) = V e V(q) = V.		q. ~p se V(p) = F.
3.3 – OUTRAS TABELAS VERDADES
	No item anterior foram construídas as tabelas verdades de proposições compostas formadas por duas proposições simples ligadas pelos conectivos “ou”, “e”, “se então”, “se e somente se” e a negação “não”.
Estas proposições compostas podem ser combinadas para formação de proposições mais complexas, como por exemplo: ~(p ( q) ( (p ( ~q).
Vejamos a tabela verdade para a proposição acima. Como foram usadas duas proposições simples p e q, devemos usar 22 = 4 linhas, que correspondem a todas as possibilidades de combinações de V e F das duas proposições.
1º processo:
Nas duas primeiras colunas indicam-se as combinações dos valores lógicos de p e q.
Na terceira coluna calculam-se os valores lógicos de (p ( q).
Na quarta coluna calculam-se os valores lógicos de ~(p ( q).
Como são necessários os valores lógicos de ~q para obter p ( ~q, na quinta coluna calculam-se os valores lógicos de ~q.
Na sexta coluna calculam-se os valores lógicos de p ( ~q, e finalmente, na sétima coluna calculam-se os valores de ~(p ( q) ( (p ( ~q).
2º processo	
	Este processo consiste em construir as duas primeiras colunas para os valores lógicos das proposições simples envolvidas e, à direita, uma coluna para cada proposição e para cada conectivo que figura na proposição composta. 
Observando a ordem das operações lógicas envolvidas calculam-se os valores lógicos relativos a cada coluna.
É aconselhável deixar uma linha no final da tabela para numerar a seqüência dos cálculos a serem feitos.
Para o mesmo exemplo anterior, devemos criar 11 tabelas pois temos duas proposições simples e 8 proposições e conectivos figurando na proposição composta.
 
Na tabela acima foi observada a ordem:
1 – obtido a partir dos valores lógicos de p e q.		2 – negação de q.
3 – cálculo de p ( q						4 – cálculo de ~(p ( q) a partir de 3.
5 – cálculo de (p ( ~q) 
6 – cálculo de ~(p ( q) ( (p ( ~q) a partir de 4 e 5.
A coluna 6 mostra os valores lógicos de ~(p ( q) ( (p ( ~q).
Para simplificação pode-se eliminar as duas primeiras colunas pois os valores lógicos de p e q irão figurar nas demais colunas.
Exercícios resolvidos
1. Construir a tabela verdade da proposição (p (~q) ( ((~p ( r) ( ~q)
1º processo.
Ordem dos cálculos:
1, 2, 3 – valores lógicos de p, q e r.
4, 5 – negações de p e q
6 – operação com as colunas 1 e 5
7 – operação com as colunas 4 e 3
8 – operação com as colunas 7 e 5
9 – operação com as colunas 6 e 8.
2º processo: (p (~q) ( ((~p ( r) ( ~q)
 
Ordem dos cálculos:
1, 2, 3, 4, 5 – valores lógicos de p, q e r.
6, 7 e 8 – negações de 2, 4 e 3, respectivamente.
9 – resultado de 1 com 6.
10 – resultado de 8 com 5.
11 – resultado de 10 com 7
12 – resultado de 11 com 9.
2. Sejam p, q e r três proposições tais que V(p)= F, V(q) = V e V(r) = F. 
Determine o valor lógico da sentença P(p, q, r) se P = (p (~q) ( ~(q ( (r ( ~p)).
Solução: neste caso pede-se apenas para determinar o valor lógico para V(p)= F, V(q) = V e V(r) = F.
Não há, assim, necessidade de se construir toda a tabela.
Usaremos o segundo processo para resolver a questão.
São necessárias 12 colunas pois temos 5 proposições, 3 negações, 1 condicional, 1 bicondicional, 1 conjunção e uma disjunção.
 
Ordem dos cálculos:
1, 2, 3, 4, 5 – valores lógicos de p, q e r.
6, 7 – negações de q e p.
8 – resultado de 1 e 6.
9 – resultado de 5 e 7.
10 – resultado de 4 e 9.
11 – negação de 10
12 – resultado de 8 e 11.
Assim, o valor lógico de P(p, q, r), para P(FVF), é F como pode ser visto na coluna 12.
3. Sejam as proposições p: 3 + 1 = 4, q: 2 > 3, r: 1 ( 0 e s: 23 = 8.
Determine o valor lógico de (p (~q) ( ~(q ( (s ( ~r)).
Solução: neste exercício, devemos inicialmente verificar o valor lógico das sentenças dadas.
V(p) = V pois 3 + 1 = 4 é verdadeiro.
V(q) = F pois 2 > 3 não é verdadeiro.
V(r) = V pois 1 ( 0 é verdadeiro.
V(s) = V pois 23 = 8 é verdadeiro.
Serão necessárias 12 colunas: p, q, q, r, s, três negações, uma condicional, uma bicondicional, uma conjunção e uma disjunção.
 
Ordem dos cálculos:
1, 2, 3, 4, 5 – proposições p, q, q, s, r.
6, 7 – negações de 2 e 5, respectivamente.
8 – resultado de 1 e 6.
9 – resultado de 4 e 7.
10 – resultado de 3 e 9.
11 – negação de 10.
12 – resultado de 11 e 8.
Portanto, V(VFVV) = V.
3.4 – PONTUAÇÃO DE PROPOSIÇÕES COMPOSTAS
	Conforme ocorre em expressões algébrica, o uso de parênteses permite identificar a ordem dos cálculos a serem feitos. Ao usar diversos pares de parênteses deve-se iniciar os cálculos a partir do último parêntese que se abre e do primeiro parêntese que se fecha a contar da direita.
Entretanto, caso não ocorra dupla interpretação, os parênteses podem ser eliminado. Em tal situação, convenciona-se a ordem (1) ~, (2) ( e (, (3) ( e (4) (.
Tomando por exemplo a proposição p ( q ( ~r ( p, a aplicação de parênteses leva a
p ( ((q ( (~r)) ( p).
3.5 – USANDO SOFTWARES PARA CONSTRUÇÃO DE TABELAS VERDADE
	Os dois principais programas que trabalhamcom planilhas de cálculos são o Excel do pacote Office da Microsoft e o StarCalc do pacote do Star Office da Sun Micro Systems. A vantagem do segundo em relação ao primeiro está na gratuidade do programa (até versão 5.2) e no uso para cálculo com matrizes.
	Iremos descrever aqui, como usar o StarCalc, porém os procedimentos são idênticos para os dois.
(1) Para inicializar o StarCalc, use o caminho: botão INICIAR, Opção PROGRAMAS, Star Office – v, Star Office – v. (v é a versão instalada).
(2) Ao abrir a página inicial serão exibidos os ícones dos programas constantes do Desktop (página inicial do Windows) e a seguir uma janela onde você faz as opções sobre os programas para uso da Internet. Marque a opção “sem modificações” e clique em OK.
Dependendo da configuração, na parte inferior da página, será exibido um quadro onde são fornecidas dicas sobre o uso do programa. Clique no botão marcado com “X” para fechar este quadro e assim, ser possível o trabalho em tela cheia.
(3) A seguir, clique no menu Fichero (Arquivo), desloque o ponteiro do mouse até a opção Novo. A seguir, desloque o ponteiro do mouse até a opção “Folha de Cálculo” e clique nessa opção.
Será então aberta uma folha dividida em retângulo. Tal folha é chamada de planilha e cada retângulo é uma célula. A posição da célula é identificada por uma letra (coluna) e um número (linha).
Assim, a célula C5, é o retângulo posicionado na coluna C e na linha 5.
	Para construir tabelas verdades devemos indicar nas células um dos julgamentos VERDADEIRO ou FALSO por extenso.
Os comandos para os cálculos são: = NÃO(p), = OU(p; q); = E(p; q) onde p e q são as células onde estão registrados os valores VERDADEIRO ou FALSO.
	Vejamos como criar uma tabela verdade no StarCalc (ou no Excel). Tomemos por exemplo, a tabela verdade de p ( ~q.
Serão indicadas as células a serem usadas para facilitar as referências. 
(4) Nas células B2, B3, B4, B5 digite os valores lógicos de p (VERDADEIRO, VERDADEIRO, FALSO, FALSO);
(5) Nas células C2, C3, C4, C5 digite os valores lógicos de q (VERDADEIRO, FALSO, VERDADEIRO, FALSO);
(6) Na célula D2 digite =NÃO( e a seguir clique na célula C2. Digite ) para fechar o parêntese e completar =NÃO(C2). Assim, você terá o valor lógico de ~q.
Pressione ENTER.
(7) Clique na célula D2 para seleciona-la. No canto inferior direito da célula será exibido um pequeno quadrado em negrito. Posicione o ponteiro do mouse sobre o quadrado e, mantendo pressionado o botão esquerdo do mouse, arraste o ponteiro até a célula D5.
Isto fará copiar a fórmula para as demais células.
Nas células D2, D3, D4, D5 serão exibidos os valores lógicos de ~q (FALSO, VERDADEIRO, FALSO, VERDADEIRO).
(8) Na célula E2 digite =OU( , clique na célula B2, digite (;) sem os parênteses, clique na célula D2, digite ) para fechar o parênteses. Pressione a tecla ENTER.
Proceda como em (4) para obter os valores lógicos de p ( ~q.
	É importante observar que os conectivos (, ( e ( não são aplicáveis no Excel e no StarCalc. Para construir tabelas com estes conectivos use as equivalências, cujas justificativas serão vistas no capítulo 4.
(1) p ( q ( ~p ( q 
(2) p ( q ( (~p ( q) ( (~q ( p).
(3) p ( q ( (p ( ~q) ( (q ( ~p).
EXERCÍCIOS 06
1. Construa as tabelas verdade das seguintes proposições
a) ~p ( (q ( p) b) ~p ( (q ( p) c) ~p ( (q ( p)
d) ~p ( (q ( p) d) ~p ( (q ( p) e) p ( (~q ( p) 
f) p ( (~q ( p) f) (p ( q) ( (~p ( q) g) (p ( q) ( (~p ( q)
h) (p ( q) ( (~q ( p) i) ~(p ( q) ( ~(p ( q)	 j) ~(p ( q) ( ~(p ( q)
k) ~p ( (p ( (q ( ~p)) l) p ( ~(p ( ~(q ( ~p)) m) ~(~p ( q).
2. Construa as tabelas verdade das seguintes proposições
a) ~(p ( q) b) ~p ( ~q.
Que conclusão pode-se tirar a respeito das duas proposições.
3. Construa as tabelas verdade das seguintes proposições
a) ~(p ( q) b) ~p ( ~q.
Que conclusão pode-se tirar a respeito das duas proposições.
4. A partir das conclusões tiradas nos exercícios 2 e 3, negue as proposições:
a) Maria é bonita e Maria é estudiosa.
b) Maria é bonita ou Maria é estudiosa.
c) Maria não é bonita e Maria não é estudiosa.
d) Maria não é bonita ou Maria não é estudiosa.
e) Maria não é bonita ou Maria é estudiosa.
f) Maria é bonita e Maria não é estudiosa.
g) Maria é bonita ou Maria não é estudiosa.
5. Construa as tabelas verdade das seguintes proposições.
a) ~(~p ( q) ( (r ( s) b) ~(p ( q) ( ~(r ( q)	
c) ~(p ( q) ( ~((p ( ~r) ( (~q ( s)) d) ~(p ( q) ( ~((p ( ~r) ( (~q ( s))
6. Considere as proposições p, q, r, s tais que V(p) = V(s) = F e V(q) = V(r) = V.
Determine o valor lógico das seguintes proposições compostas:
a) ~p ( (q ( p)	 b) ~(p ( q) ( ~(p ( ~r) c) ~(p ( q) ( ((p ( ~r) ( (~q ( s)).
7. Considere as proposições p: A lua tem luz própria; q: A Unipac ministra curso superior; r: Pedro Álvares Cabral descobriu o Brasil; s: Santos Dumont inventou a lâmpada.
Determine o valor lógico das proposições: 
a) (p ( q) ( (r ( s). b) (p ( q) ( (r ( s). c) ~(p ( q) ( ((p ( ~r) ( (~q ( s)).
d) ~(p ( q) ( ~(p ( ~r) ( (~q ( s) e) ~(s ( q) ( ~(p ( ~r)
8. Escreva as proposições sob forma simbólica, construa a tabela verdade e, a partir do resultado encontrado decida o que Antônio deve fazer.
a) Antônio irá passear se e somente se Carlos for jogar futebol e Marina for assistir televisão.
b) Marina irá assistir televisão se Luis ou Paula trouxer um filme romântico.
c) Paulo irá trazer o filme, mas Carlos não vai jogar futebol.
 
CAPÍTULO 4 – TAUTOLOGIAS E CONTRADIÇÕES
4.1 – DEFINIÇÕES
	Vejamos as tabelas verdades das seguintes proposições 
(1) P(p, q) = (p ( q) ( (q ( p) 
(2) P(p, q) = ~(p ( q) ( (p ( q)
(3) P(p, q) = ~p ( (p ( ~q)
(4) P(p, q) = ~(p (q) ( (p ( q).
(1) 
(2) 
(3) 
(4) 
Nas duas primeiras tabelas, quaisquer que sejam os valores lógicos de p e q, V(P) = V e nas duas últimas, quaisquer que sejam os valores lógicos de p e q, V(P) = F.
As duas primeiras proposições são chamadas de TAUTOLOGIA e as duas últimas de CONTRADIÇÃO.
Definição 1 – Chama-se TAUTOLOGIA à proposição composta P(p, q, r, ...) tal que V(P) = V, quaisquer que sejam os valores lógicos das proposições simples envolvidas.
	As tautologias são também chamadas de “proposições logicamente verdadeiras”.
Definição 2 – Chama-se CONTRADIÇÃO à proposição composta P(p, q, r, ...) tal que V(P) = F, quaisquer que sejam os valores lógicos das proposições simples envolvidas.
	As contradições são também chamadas de “proposições logicamente falsas” ou “contraválidas”.
Definição 3 – As proposições que apresentem valores lógicos V e F são chamadas de CONTINGÊNCIAS.
EXERCÍCIOS 7
1. Dadas as proposições abaixo, verifique quais são tautologias, quais são contradições e quais são contingências. 
a) (p ( q) ( ((p ( q) ( (q ( r)) b) ((p ( q) ( p) ( q c) (p ( q) ( (p ( ~q)
d) p ( (p ( q) ( r e) ~(~p ( q) ( (p ( q) f) p ( (q ((q (p)
g) (p ( q) ( ~(p ( q) h) (q ( p) ( (p ( q) i) (p ( q) ( ((p ( r) ( (q ( r))
4.2 – IMPLICAÇÃO E EQUIVALÊNCIA LÓGICAS
	Sejam P(p, q, r, ...) e Q(p, q, r...) duas proposições. 
Definição 1: Uma proposição P implica na proposição Q se e somente se a tabela verdade de 
P ( Q for uma tautologia. 
	Para indicar que a proposição P implica na proposição Q usa-se P ( Q.
	A implicação lógica goza das seguintes propriedades:
P1 – Reflexiva. Isto é P ( P.
P2 – Transitividade. Isto é P ( Q e Q ( S então P ( S.
 	A transitividade pode ser estendida a qualquer série de proposições: P ( R e R ( S e S ( ...
( X então P ( X.
Definição 2: Uma proposição P é logicamente equivalente a outra proposição Q se e somente se a tabela verdade de P ( Q for uma tautologia.Para indicar que a proposição P é equivalente à proposição Q usa-se P ( Q.
	A equivalência lógica goza das seguintes propriedades:
P1 – P e Q são equivalentes se forem ambas tautologias ou ambas contradições.
P2 – Reflexiva. Isto é P ( P.
P3 – Simétrica. Isto é, se P ( Q então Q ( P.
P4 – Transitividade. Isto é se P ( Q e Q ( R então P ( R.
	Provemos algumas equivalências lógicas.
Sejam p e q duas proposições, c uma contradição e t uma tautologia.
(1) c ( p ( p (2) t ( p ( p (3) c ( p ( c (4) t ( p ( t
As colunas 8, 9, 10 e 11 mostram que t ( p ( p, c ( p ( c e t ( p ( t são tautologias. Portanto, as equivalências (1), (2), (3) e (4) são verdadeiras.
 (5) p ( q ( p (6) p ( q ( q (7) p ( p ( q (8) q ( p ( q
As colunas 5, 6, 7 e 8 mostram que p ( q ( p, p ( q ( q, p ( p ( q e q ( p ( q são tautologias. Portanto as implicações (5), (6), (7) e (8) são verdadeira.
4.3 – PROPOSIÇÕES ASSOCIADAS A UMA CONDICIONAL
	A partir da condicional p ( q podemos obter as condicionais 
(1) q ( p, denominada proposição recíproca de p ( q;
(2) ~p ( ~q, denominada proposição contrária de p ( q; e
(3) ~q ( ~p, denominada proposição contrapositiva de p ( q ou recíproca da proposição ~p ( ~q.
	Em geral, na proposição p ( q, p é chamada de hipótese e q de tese.
	Por exemplo: se A e B são ângulos opostos pelo vértice então eles são iguais. Nesta proposição “A e B são ângulos opostos pelo vértice” é a hipótese e “eles são iguais é a tese”.
A hipótese é uma proposição que se supõe verdadeira enquanto que a tese é uma proposição que se quer provar.
	Vejamos a equivalência entre as proposições: p ( q, q ( p, ~p ( ~q e ~q ( ~p.
	Observando a tabela nota-se, pelas colunas 5 e 8 que (p ( q) ( (~q ( ~p).
	A equivalência entre p ( q e ~q ( ~p estabelece um procedimento para demonstrar teoremas condicionais como, “se a + b = c então a = c – b” , onde a + b = c é a hipótese e a = c – b é a tese.
	Para provar a propriedade podemos usar a contrapositiva ou a negação da tese. Se a negação da tese levar a concluir a negação da hipótese então a propriedade estará demonstrada.
Negando a tese, a ( c – b. Somando b a ambos os membros, a desigualdade permanece. Assim,
a + b ( c – b + b ( a + b ( c. O que contraria a hipótese. Portanto a propriedade é verdadeira.
EXERCÍCIOS 08 
1. Mostre que:
a) p ( q ( p ( q b) p ( q ( q ( p c) p ( q ( p d) p ( q ( q
e) (p ( q) ( (q ( p) f) ~(p ( ~q) ( ~p ( q.
2. Dadas as proposições p: 5 > 3 e q: 2 + 2 ( 5.
(a) Escreva a recíproca, a contrária e a contrapositiva da proposição p ( q, sob forma simbólica
(b) Escreva, por extenso, a proposição p ( q, sua recíproca, sua contrária e sua contrapositiva.
4.4 – EXPRESSANDO OS CONECTIVOS (, ( E ( EM FUNÇÃO DE ~, ( E (.
	Na álgebra das proposições se P(p, q, r, ...) ( Q(p, q, r...), pode-se substituir P(p, q, r, ...) por Q(p, q, r...). Em alguns programas, como Excel e Starcalc podem-se construir tabelas verdade, entretanto, nem todos os conectivos poderão ser usados. Assim, é importante saber substituir conectivos por outros.
	Vejamos as possíveis substituições:
(1) p ( q pode ser substituído por ~p ( q pois ~p ( q ( p ( q.
(2) p ( q pode ser substituído por (~p ( q) ( (~q ( p).
(3) p ( q que equivale a ~(p ( q) pode ser substituída por (p ( ~q) ( (q ( ~p).
	A comprovação destas correspondências pode ser feita através das tabelas verdades.
(1) 
	
(2)
(3) 
	Observando as duas últimas colunas das tabelas verifica-se a igualdade dos valores lógicos das duas proposições.
EXERCÍCIOS 09
1. Construa as tabelas das proposições ~p, p ( q, p ( q, p ( q, p ( q, p ( q.
2. Construa as tabelas das proposições dadas nos exercícios nº 2 página 12, nº 1 página 13, nºs 6 e 7 página 18.
UNIDADE 3 – ÁLGEBRA DE BOOLE	
CAPÍTULO 5 – PORTAS LÓGICAS
5.1 – AS MÁQUINAS QUE CALCULAM	
	A história do computador pode ser dividida em três fases básicas:
1ª fase – o ábaco – data do ano 500 a.C. – usado para registro e contagem de valores, bem como realização de operações simples como adição e subtração. Consistia essencialmente de várias fileiras com seis peças. Em cada uma dessas fileiras, uma das peças apresentava-se separada das demais. O processo usado na contagem ou nas operações tinha por base o complemento dos dígitos 1, 2, 3, 4, e 5 em relação a 10. Por exemplo para registrar o número 8, movia-se a peça separada para indicar 5 e separavam-se 3 das outras cinco peças agrupadas.
2ª fase – contador mecânico de rodas e engrenagens dentadas – segundo consta, data de 1642, inventada pelo francês Blaise Pascal, matemático e filósofo. Cada roda continha dez dentes. Ao completar uma volta, um dos dentes, mais longo que os demais fazia girar um dente da roda seguinte. Este processo é ainda usado nos marcadores de quilometragem dos automóveis.
3ª fase – dispositivos eletromecânico – no final do século XIX foi inventado o motor elétrico e com ele foi possível fazer funcionar os sistemas mecânicos por meio de motores. 
4ª fase – dispositivos eletrônicos – com a invenção da válvula em 1906, as máquinas de calcular puderam se tornar mais leves pois utilizavam apenas sinais elétricos para o seu funcionamento, associando o 0 à não passagem de uma corrente e o 1 à passagem da corrente. Assim, passou a ser usado um sistema binário no lugar de um sistema decimal. As válvulas, que implicavam em construção de circuitos que ocupam um grande espaço, foram sendo substituídas por novas invenções como dispositivos transistorizados até chegar aos nossos dias onde são usados os denominados circuitos integrados que, ocupando pequeno espaço tornou possível a construção de microcomputadores.
5.2 – A LÓGICA BINÁRIA OU ÁLGEBRA BOOLEANA
	Se considerarmos um circuito elétrico com uma fonte, chaves liga-desliga e lâmpadas, são possíveis diversas combinações entre estes elementos e assim efetuarmos operações binárias. Isto é operações onde a lâmpada será acesa ou não.
Vejamos alguns exemplos:
(1) 
	
(2) 
(3) 
	Como será visto posteriormente, os circuitos acima apresentam propriedades e operações semelhantes às propriedades da teoria dos conjuntos e à lógica das proposições.
	Podemos então definir: “lógica binária ou álgebra booleana é um sistema que opera com dois valores tendo como resultado um destes valores”.
	Na álgebra booleana como na álgebra comum trabalhamos com variáveis e operações. Na álgebra comum o número de variáveis é infinito e as operações são as já conhecidas: adição, subtração, multiplicação, divisão, potenciação, radiciação e potenciação. Na álgebra booleana usam-se apenas duas variáveis que podem ser ABERTO e FECHADO ou FALSO e VERDADEIRO.
	Em geral, atribuem-se os dígitos 1 a FECHADO (ou VERDADEIRO) e 0 a ABERTO (ou falso).
As operações fundamentais usadas na álgebra booleana são denominadas:
(1) NOT – não – que para a variável A, se indica A ou A’.
	Esta operação equivale ao complementar do conjunto A na teoria dos conjuntos e à ~p na álgebra das proposições.
(2) AND – e – que, para as variáveis A e B, se indica A AND B ou A.B.
	Esta operação equivale à interseção de conjuntos na teoria dos conjuntos e à p ( q na álgebra das proposições. 
(3) OR – ou - que, para as variáveis A e B, se indica A OR B ou A + B.
	Esta operação equivale à união de conjuntos na teoria dos conjuntos e à p ( q na álgebra das proposições.
5.3 – PRINCÍPIOS BÁSICOS DA ÁLGEBRA BOOLEANA
	Considerando que as variáveis A, B e C podem assumir um dos valores 0 ou 1, a Álgebra Booleana tem por base os seguintes princípios:
EXERCÍCIO 10
1. Construa uma tabela com as propriedades de 1 a 12 da tabela anterior fazendo a correspondência entre a álgebra das proposições e a teoria dos conjuntos.
2. Construa um diagrama para o circuito correspondente às operações:
A + (B.C); A.(B + C); (B + C)’ e (B.C)’.
5.4 – TABELAS OPERACIONAIS 
	Semelhante às tabelas verdade daLógica das Proposições, podemos construir as tabelas operacionais para a álgebra booleana. Nestas últimas os valores lógicos são os dígitos 0 e 1.
Estas tabelas são construídas com base nos princípios indicados no item 1.3.
 TABELA NOT (‘) TABELAS OR (+) e AND (.)
 TABELA A.(C’ + B + D’)
 
EXERCÍCIOS 11
1. Construa as tabelas das seguintes expressões booleanas
a) A + A’ b) A.A’ c) (A + B)’ d) (A.B)’ e) A’.B’ f) A’ + B’.
g) A.B.C + A.B’.C’ + A’.B’.C’ h) (A + B).(A + C)’ i) (A.B + A.B’)’
2. Demonstre, mediante a construção de tabelas, as propriedades 1 a 6, 9 a 11 da tabela do item 1.3.
5.5 – SIMPLIFICAÇÃO DE EXPRESSÕES
	Dependendo da expressão booleana, os circuitos correspondentes podem ser bastante complexos . Usando as propriedades descritas na tabela do item 1.3, pode-se, às vezes, simplificar tais expressões e, em conseqüência, obter circuitos mais simples.
Por exemplo: a expressão X = [(A’ + B).B]’ pode ser transformada em X = A + B.
Temos: X = [(A’ + B).B’]’ ( [A’.B’ + B.B’]’ (P6) 
[A’.B’ + B.B’]’ ( [A’.B’ + 0]’ (P10)
[A’.B’ + 0]’ ( [A’.B’]’ P(3)
[A’.B’]’ ( (A’)’ + (B’)’ P(11)
(A’)’ + (B’)’ ( A + B (P9).
Pela transitividade da equivalência, conclui-se que [(A’ + B).B]’ ( A + B.
EXERCÍCIOS 12
1. Simplifique cada uma das expressões abaixo
a) A.B’ + B’.A + C.D.E + C’.D.E + E.C’.D
b) A.B.C.(A.B.C + A.B.C + A.B.C)
c) A.B + A.B + A.C + A.C
d) (A.B.C).(D.E).(F.G.H).(A.B.C)
e) A.C’ + C.A.B + C’.A.B + A.C
f) (A.C + B.C).A.(A + A.B) + C.C + A.B
g) A.B + B.A
h) (A + B).(A + B’)
i) (A + 1).B.B’ + A + C.C.0 + C
j) (A + 1).(B.0) + D.D + 1.
2. Considere os valores binários: A = 1011, B = 0101 e C = 1111.
Determine o valor de X, se:
a) X = A + B’.C 
b) X = (A’.B) + C’ 
c) X = (A + B’)’ + A.C’
d) X = (A +B’)’ + (A + C’)’.
5.6 – PORTAS LÓGICAS
	Os hardwares de um computador são conjuntos de circuitos eletrônicos simples combinados. Circuitos estes destinados a receber um sinal de entrada (0 ou 1) ou combinação desses sinais, com os quais são realizadas operações ou funções lógicas e, a partir dessa entrada produzir um sinal de saída. 
	Os circuitos simples são denominados portas lógicas. Esquematizando temos:
	
 
	
A tabela a seguir mostra as portas lógicas, o simbolismo matemático e a representação gráfica das mesmas.
	Podemos associar diversas portas lógicas para que, dada uma entrada a mesma combine com um conjunto registrador de origem e assim obter um registrador de origem. Veja o exemplo abaixo.
	O sinal indica que não há contato entre os ramos do circuito.
 	O registrador de origem fornece um determinado sinal que combinado com o sinal da entrada resultará no sinal registrado no destino.
5.7 – TABELAS DAS OPERAÇÕES LÓGICAS
	
	A lógica das proposições utiliza os valores lógicos VERDADEIRO (V) e FALSO (F). Nas portas lógicas estes valores são equivalentes a 1 e 0, respectivamente. Assim, as tabelas das operações com as proposições e as tabelas operacionais com as portas lógicas se correspondem.
Temos então:
5.8 – ALGUNS EXEMPLOS
	Sejam calcular a saída X da operação X = A + (B.C)’ para A = 01101, B = 10011 e C = 11000.
1º passo: B.C = (1,0,0,1,1).(1,1,0,0,0) = (1,0,0,0,0) 
2º passo: (B.C)’ = (0,1,1,1,1)
3º passo A + (B.C)’ = (0,1,1,0,1) + (0,1,1,1,1) = (0,1,1,1,1).
Como pode ser observado A + (B.C)’ equivale à (B.C)’ para os valores dados.	
A representação gráfica da operação acima é:
 
EXERCÍCIOS 13
1. Considere os valores A = 1110001, B = 0011100, C = 1010101 e D = 0101011
Calcule o valor de X, se 
a) X = (A + B).(C + D) b) X = (A.B) + (C.D) c) X = A.B’ + C’.D
d) X = (A’ + B).(C1 + D’)’ e) X = A.B.C.D f) X = (A.B)’ + (C’D)
g) X = (A’ + B)’	 h) X = A’ ( (B.C)’ i) X = (A ( B)’ . (C ( D’)
2. Faça a representação gráfica das operações do exercício anterior.
3. Para cada uma das representações abaixo, determinar o valor da saída X.
	
 
UNIDADE 4 – MÉTODOS DE RACIOCÍNIO
CAPÍTULO 6 – DEDUÇÃO E INFERÊNCIA LÓGICA
6.1 – INTRODUÇÃO	
	Dedução e a indução são formas de raciocinarmos ou mesmo de argumentar, isto é, são formas de reflexão. O raciocínio pode ser algo ordenado, coerente, lógico e pode ser dedutivo ou indutivo.
Os argumentos dedutivos como os indutivos são fundamentados em premissas. A dedução e a indução são processos que se completam.
Consideremos as seguintes seqüências de raciocínio:
         i) Todo homem é mortal.
            Sócrates é mortal.
            Então, Sócrates é homem.
        ii) Seja o trinômio: n2 + n + 17. Se fizermos n = 0, 1, 2, 3, 4 e 5, obtemos: 17, 19, 23, 29, 37, 47. Todos esses resultados são números primos. Poder-se-ia dai concluir que para todo n ( N, n2 + n + 17 é um número primo.
        As duas conclusões são evidentemente falsas pois 
(i)  "Sócrates pode ser um gatinho" que é mortal mas não é homem e, 
(ii) para n = 17, n2 + n + 17 = 17*19 que não é primo. A sentença é verdadeira para n < 16.
Entretanto, raciocínio como estes, desde que seguidas algumas regras, poderão ser válidos.
No exemplo (i) partimos de uma afirmação geral para se chegar a uma afirmação particular. Um raciocínio desse tipo é chamado de DEDUÇÃO. No exemplo (ii) de algumas situações particulares tentou-se chegar a uma afirmação que poderia ser válida para todas as situações. Este tipo de raciocínio é denominado INDUÇÃO.
6.2 – MÉTODO DEDUTIVO 
	O método dedutivo considerado como o procedimento ideal da ciência goza de grande prestígio desde a época de Aristóteles. As idéias de que as explicações científicas devem ter uma forma de dedução lógica, teve ampla aceitação. Este método tradicionalmente é definido como um conjunto de proposições particulares contidas em verdades universais. O ponto de partida é a premissa antecedente que tem valor universal (ou pelo menos assim se admite), e o ponto de chegada é a conseqüente. A conseqüente contém ou afirma um conhecimento particular ou menos geral contido explicitamente na primeira. Daí que uma definição simplista do método dedutivo pode ser endossada como segue: "método dedutivo é aquele que vai do conhecimento geral para o particular".
Na álgebra das proposições, o método dedutivo consiste em demonstrar implicações (H ( T) e equivalências lógicas (H ( T que equivale provar H ( T e T ( H). 
Podemos aplicar, na implicação, o processo direto que consiste em aceitar a hipótese, usando propriedades ou equivalências lógicas, comprovar a tese ou o processo indireto que consiste em negar a tese. Neste processo se a negação da tese implicar na negação da hipótese, a proposição será verdadeira. Este segundo método é denominado, redução ao absurdo.
Nas demonstrações é aconselhável converter os conectivos “se então”, “se e somente se” e “ou exclusivo” nos conectivos “e” e “ou”, pois isto facilita as conversões de proposições em proposições equivalentes.
Lembrando tais conversões temos:
(1) p ( q ( ~p ( q 
(2) p ( q ( (p ( q) ( (q ( p) ( (~p ( q) ( (~q ( p)
(3) p ( q ( ~(p ( q) ( ~((~p ( q) ( (~q ( p)) ( ~(~p ( q) ( ~(~q ( p) ( (p ( ~q) ( (q ( ~p)
Além dessas equivalências podemos usar as equivalências e implicações abaixo, já provadas por tabelas verdade,
(4) c ( p ( p (5) t ( p ( p (6) c ( p ( c (7) t ( p ( t
(8) p ( q ( p (9) p ( q ( q (10) p ( p ( q (11) q ( p ( q.
Vejamos algumas aplicações:
(1) Demonstrar que (p ( q) ( p ( q. 
Demonstração: 
(p ( q) ( p ( p ( (p ( q) (comutatividade do conectivo ()
p ( (p ( q) ( p ( (~p ( q) (1)
p ( (~p ( q) ( (p ( ~p) ( (p ( q) (distributividade)
(p ( ~p) ( (p ( q) ( C ( (p ( q) [(p ( ~p) é uma contradição]
C ( (p ( q) ( p ( q (5)
p ( q ( q (10).
(2) Demonstrar que (p ( q) ( ~q ( ~p
Demonstração:
(p ( q) ( ~q ( (~p ( q) ( ~q (1)(~p ( q) ( ~q ( (~p ( ~q) ( (q ( ~q) (distributividade)
(~p ( ~q) ( (q ( ~q) ( (~p ( ~q) ( C [(q ( ~q) é uma contradição]
(~p ( ~q) ( C ( C ( (~p ( ~q) (comutatividade)
C ( (~p ( ~q) ( (~p ( ~q) (5)
(~p ( ~q) ( ~p (9).
(3) Demonstrar que (p ( q) ( ~p ( q.
Demonstração:
(p ( q) ( ~p ( (p ( ~p) ( (q ( ~p) (distributividade)
(p ( ~p) ( (q ( ~p) ( C ( (q ( ~p) [(p ( ~p) é uma contradição]
C ( (q ( ~p) ( (q ( ~p) (5)
q ( ~p ( ~p (10).
EXERCÍCIOS 14
1. Demonstre as equivalências e implicações
a) p ( q ( (p ( ~q) ( c b) p ( q ( (p ( q) ( q 
c) (p ( q) ( (p ( ~q) ( ~p d) (p ( q) ( r ( p ( (q ( r) 
e) (p ( r) ( (q ( r) ( (p ( q) ( r f) (p ( q) ( (p ( r) ( (p ( q) ( r
6.3 – REGRAS DE INFERÊNCIA
	Sejam P1, P2, P3, ... Pn, e Q proposições tais que (P1 ( P2 ( P3 ( … ( Pn) ( Q, isto é 
(P1 ( P2 ( P3 ( … ( Pn) ( Q é uma tautologia, dizemos que (P1 ( P2 ( P3 ( … ( Pn) é um argumento que tem como conseqüência a proposição Q. As proposições P1, P2, P3, ... Pn são denominadas premissas e Q é denominada conclusão.
	Um argumento de premissas P1, P2, P3, ..., Pn e conclusão Q é indicado por
 P1, P2, P3, ..., Pn	 Q, 
que se lê: 
(1) P1, P2, P3, ..., Pn acarretam Q; ou
(2) Q decorre de P1, P2, P3, ..., Pn; ou
(3) Q se deduz de P1, P2, P3, ..., Pn; ou
(4) Q se infere de P1, P2, P3, ..., Pn; ou 
(5) de P1, P2, P3, ..., Pn se conclui Q.
Definição 1: Um argumento P1, P2, P3, ..., Pn Q é válido se e somente se a conclusão Q é verdadeira todas as vezes que as premissas P1, P2, P3, ..., Pn são verdadeiras.
Definição 2: Um argumento não válido é denominado sofisma.
6.4 – ARGUMENTOS BÁSICOS VÁLIDOS
	Apresentamos abaixo uma relação dos principais argumentos válidos usados também chamadas regras de inferências. Tais argumentos já forma demonstrados através de tabelas verdade ou por dedução.
 
6.5 – DEMONSTRAÇÕES USANDO AS REGRAS DE INFERÊNCIAS
	Para demonstrar a validade de um argumento podemos utilizar tabelas verdades. Entretanto, à medida que aumento o número de proposições, o método de tabelas pode-se tornar bastante trabalhoso. O uso das regras de inferências podem tornar estas demonstrações bem mais simples.
Na verificação da validade de um argumento é comum utilizar o algoritmo abaixo, que mostraremos usando um exemplo.
Seja demonstrar a validade de p ( (q ( r), p ( q, p r
Inicialmente escrevemos as premissas em coluna:
	(1) p ( (q ( r) P1
	(2) p ( q P2
	(3) p P3
Separamos as premissas por um traço horizontal.
A seguir, considerando as premissas dadas, aplicam-se as regras de inferência até obter a premissa que se quer concluir.
Dando continuidade temos:
	(1) p ( (q ( r) P1
	(2) p ( q P2
	(3) p P3
 (4) q ( r (P1 e P3) aplicando MP
 (5) q (P2 e P3) aplicando MP
 (6) r (4 e 5) aplicando MP.
Não se pode esquecer que o argumento pode ser demonstrado a partir da tabela verdade
[(p ( (q ( r)) ( (p ( q) ( p] ( r.
EXERCÍCIOS 15
1. Verificar a validade dos seguintes argumentos
a) p ( q, p ( r q b) p ( q, p ( r ( s p ( s.
c) p ( (q ( r), p ( q, p r d) p ( q ( r, (r ( q) ( (p ( s ( t)), p ( s s ( t
2. Demonstrar a validade do argumento
P1: Se Pedro tem a mesma altura que João então João tem a mesma altura que Luis.
P2: Se Pedro tem a mesma altura que Luis então Pedro tem a mesma altura que Antônio.
P3: Ou Pedro tem a mesma altura que João ou a altura de Pedro é 1,80 m.
P4: Se a altura de Pedro é 1,80 m então a altura de Pedro mais 0,20 m = 2,00 m.
P5: Mas a altura de Pedro mais 0,20 não é igual a 2,00m.
Portanto: Pedro tem a mesma altura que Antônio.
3. Verificar a validade do argumento:
x = y ( x = z, x ( y ( x < z, x > z ( y > z, y ( z ( x ( z y > z.
4. Verificar a validade dos seguintes argumentos:
a) (p ( q) ( r, r ( s, t ( ~u, t, ~s ( u ~(p ( q)
b) p ( q, q ( r, s ( t, p ( s r ( t
c) p ( q, ~r ( (s ( t), r ( (p ( s), ~r q ( t
d) p ( q, (p ( r) ( (s ( q), (p ( q) ( r, ~s q
e) p ( q, q ( r, r ( s, ~s, p ( t t
f) r ( (p ( q), r, ~p q
g) p ( ~q, ~~q, ~p ( r r
h) p ( q, ~q, , ~p (~r r.
INTRODUÇÃO À LÓGICA
CIÊNCIA DA COMPUTAÇÃO
PROF. CESÁRIO JOSÉ FERREIRA
A
No diagrama, os elementos “a”, “e”, “i”, “o” e “u” pertencem ao conjunto A. O elemento b não pertence ao conjunto A.
b
e
a
u
i
o
B
A
A ( B
B - A
A ( B
A - B
p�
q�
r�
�
V�
V�
V�
�
V�
V�
F�
�
V�
F�
V�
�
V�
F�
F�
�
F�
V�
V�
�
F�
V�
F�
�
F�
F�
V�
�
F�
F�
F�
�
P�
�
V�
�
F�
�
P�
q�
�
V�
V�
�
V�
F�
�
F�
V�
�
F�
F�
�
p�
q�
p ( q�
p ( q�
p ( q�
p ( q�
p ( q�
�
V�
V�
V�
F�
V�
V�
V�
�
V�
F�
V�
V�
F�
F�
F�
�
F�
V�
V�
V�
F�
V�
F�
�
F�
F�
F�
F�
F�
V�
V�
�
p�
~p�
�
V�
F�
�
F�
V�
�
p�
q�
p ( q�
~(p ( q)�
~q�
p ( ~q�
~(p ( q) ( (p ( ~q)�
�
V�
V�
V�
F�
F�
F�
V�
�
V�
F�
V�
F�
V�
V�
V�
�
F�
V�
V�
F�
F�
F�
V�
�
F�
F�
F�
V�
V�
F�
F�
�
1�
2�
3�
4�
5�
6�
7�
�
p�
q�
~�
(p�
(�
q)�
(�
(p�
(�
~�
q)�
�
V�
V�
F�
V�
V�
V�
V�
V�
F�
F�
V�
�
V�
F�
F�
V�
V�
F�
V�
V�
V�
V�
F�
�
F�
V�
F�
F�
V�
V�
V�
F�
F�
F�
V�
�
F�
F�
V�
F�
F�
F�
F�
F�
F�
V�
F�
�
�
�
4�
1�
3�
1�
6�
1�
5�
2�
1�
�
p�
q�
r�
~p�
~q�
p (~q�
~p ( r�
((~p ( r) ( ~q)�
(p (~q) ( ((~p ( r) ( ~q)�
�
V�
V�
V�
F�
F�
F�
V�
F�
V�
�
V�
V�
F�
F�
F�
F�
F�
F�
V�
�
V�
F�
V�
F�
V�
V�
V�
V�
V�
�
V�
F�
F�
F�
V�
V�
F�
F�
F�
�
F�
V�
V�
V�
F�
V�
V�
F�
F�
�
F�
V�
F�
V�
F�
V�
V�
F�
F�
�
F�
F�
V�
V�
V�
V�
V�
V�
V�
�
F�
F�
F�
V�
V�
V�
V�
V�
V�
�
1�
2�
3�
4�
5�
6�
7�
8�
9�
�
(p�
(�
~�
q)�
(�
((~�
p�
(�
r)�
(�
~�
q)�
�
V�
F�
F�
V�
V�
F�
V�
V�
V�
F�
F�
V�
�
V�
F�
F�
V�
V�
F�
V�
F�
F�
F�
F�
V�
�
V�
V�
V�
F�
V�
F�
V�
V�
V�
V�
V�
F�
�
V�
V�
V�
F�
V�
F�
V�
F�
F�
F�
V�
F�
�
F�
V�
F�
V�
F�
V�
F�
V�
V�
F�
F�
V�
�
F�
V�
F�
V�
F�
V�
F�
V�
F�
F�
F�
V�
�
F�
V�
V�
F�
F�
V�
F�
V�
V�
V�
V�
F�
�
F�
V�
V�
F�
F�
V�
F�
V�
F�
V�
V�
F�
�
1�
9�
6�
2�
12�
8�
3�
10�
5�
11�
7�
4�
�
(p�
(�
~�
q)�
(�
~�
(q�
(�
(r�
(�
~�
p))�
�
F�
V�
F�
V�
F�
F�
V�
V�
F�
F�
V�
F�
�
1�
8�
6�
3�
12�
11�
4�
10�
5�
9�
7�
2�
�
(p�
(�
~�
q)�
(�
~�
(q�
(�
(s�
(�
~�
r)�
�
V�
V�
V�
F�
V�
V�
F�
F�
V�
F�
F�
V�
�
1�
8�
6�
2�
12�
11�
3�
10�
4�
9�
7�
5�
�
p�
q�
p ( q�
q ( p�
(p ( q) ( (q ( p)�
�
V�
V�
V�
V�
V�
�
V�
F�
F�
F�
V�
�
F�
V�
F�
F�
V�
�
F�
F�
F�
F�
V�
�
p�
q�
p ( q�
~(p ( q)�
p ( q�
~(p ( q) ( (p ( q)�
�
V�
V�
V�
F�
V�
V�
�
V�
F�
V�
F�
F�
V�
�
F�
V�
V�
F�
F�
V�
�
F�
F�
F�
V�
V�
V�
�
p�
q�
~p�
~q�
p ( ~q�
~p ( (p ( ~q)�
�
V�
V�
F�
F�
F�
F�
�
V�
F�
F�
V�
V�
F�
�
F�
V�
V�
F�
F�
F�
�
F�
F�
V�
V�
F�
F�
�
p�
q�
p (q�
~(p (q)�
p ( q�
~(p (q) ( (p ( q)�
�
V�
V�
V�
F�
V�
F�
�
V�
F�
F�
V�
F�
F�
�
F�
V�
F�
V�
F�
F�
�
F�
F�
V�
F�
V�
F�
�
c�
t�
p�
c ( p�
t ( p�
c ( p�
t ( p�
c ( p ( p�
t ( p ( p�
c ( p ( c�
t ( p ( t�
�
F�
V�
V�
V�
V�
F�
V�
V�
V�
V�
V�
�
F�
V�
F�
F�
F�
F�
V�
V�
V�
V�
V�
�
1�
2�
3�
4�
5�
6�
7�
8�
9�
10�
11�
�
p�
q�
p ( q�
p ( q�
p ( q ( p�
p ( q ( q�
p ( p ( q�
q ( p ( q�
�
V�
V�
V�
V�
V�
V�
V�
V�
�
V�
F�
F�
V�
V�
V�
V�
V�
�
F�
V�
F�
V�
V�
V�
V�
V�
�
F�
F�
F�
F�
V�
V�
V�
V�
�
1�
2�
3�
4�
5�
6�
7�
8�
�
p�
q�
~p�
~q�
p ( q�
q ( p�
~p ( ~q�
~q ( ~p�
�
V�
V�
F�
F�
V�
V�
V�
V�
�
V�
F�
F�
V�
F�
V�
V�
F�
�
F�
V�
V�
F�
V�
F�
F�
V�
�
F�
F�
V�
V�
V�
V�
V�
V�
�
1�
2�
3�
4�
5�
6�
7�
8�
�
p�
q�
~p�
~p ( q�
p ( q�
�
V�
V�
F�
V�
V�
�
V�
F�
F�
F�
F�
�
F�
V�
V�
V�
V�
�
F�
F�
V�
V�
V�
�
p�
q�
~p�
~q�
~p ( q�
~q ( p�
(~p ( q) ( (~q ( p)�
p ( q�
�
V�
V�
F�
F�
V�
V�
V�
V�
�
V�
F�
F�
V�
F�
V�
F�
F�
�
F�
V�
V�
F�
V�
F�
F�
F�
�
F�
F�
V�
V�
V�
V�
V�
V�
�
p�
q�
~p�
~q�
~p(q�
p(~q�
(~p(q) ( ( p(~q)�
p ( q�
�
V�
V�
F�
F�
F�
F�
F�
F�
�
V�
F�
F�
V�
F�
V�
V�
V�
�
F�
V�
V�
F�
V�
F�V�
V�
�
F�
F�
V�
V�
F�
F�
F�
F�
�
O circuito permite dois resultados: (i) chave aberta ( lâmpada apagada e (ii) chave fechada ( lâmpada acesa.
fonte
(
Operações possíveis: 
A e B abertas ( lâmpada apagada
A aberta e B fechada ( lâmpada apagada
A fechada e B aberta ( lâmpada apagada
A e B fechadas ( lâmpada acesa.
fonte
(
A
B
Operações possíveis: 
A e B abertas ( lâmpada apagada
A aberta e B fechada ( lâmpada acesa
A fechada e B aberta ( lâmpada acesa
A e B fechadas ( lâmpada acesa.
fonte
A
B
(
1�
A + B = B + A�
A.B = B.A�
Comutatividade�
�
2�
A + (B + C) = (A + B) + C�
A.(B.C) = (A.B).C�
Associatividade�
�
3�
A + 0 = A�
A.1 = A�
Neutro�
�
4�
A + A = A�
A.A = A�
Idempotência�
�
5�
A + 1 = 1�
A.0 = 0�
elemento absorvente�
�
6 �
A + (B.C) = (A + B).(A + C)�
A.(B + C) = (A.B + A.C)�
Distributividade�
�
7�
Se A = 0 então A’ = 1�
Se A = 0 então A’ = 1�
Operação NOT�
�
8�
Se A = 1 então A’ = 0�
Se A = 1 então A’ = 0�
Operação NOT�
�
9�
(A’)’ = A�
(A’)’ = A�
Involução�
�
10�
A + A’ = 1�
A.A’ = 0�
Simétrico�
�
11�
(A + B)’ = A’.B’�
(A.B)’ = A’+ B’�
De Morgan�
�
12�
A + (A.B) = A�
A.(A + B) = A�
Absorção�
�
A�
B�
A + B�
A.B�
�
1�
1�
1�
1�
�
1�
0�
1�
0�
�
0�
1�
1�
0�
�
0�
0�
0�
0�
�
A�
A’�
�
1�
0�
�
0�
1�
�
A�
B�
C�
D�
C’�
D’�
C’ + B�
C’+B+D’�
A.(C’+B+D’)�
�
1�
1�
1�
1�
0�
0�
1�
1�
1�
�
1�
1�
1�
0�
0�
1�
1�
1�
1�
�
1�
1�
0�
1�
1�
0�
1�
1�
1�
�
1�
1�
0�
0�
1�
1�
1�
1�
1�
�
1�
0�
1�
1�
0�
0�
0�
0�
0�
�
1�
0�
1�
0�
0�
1�
0�
1�
1�
�
1�
0�
0�
1�
1�
0�
1�
1�
1�
�
1�
0�
0�
0�
1�
1�
1�
1�
1�
�
0�
1�
1�
1�
0�
0�
1�
1�
0�
�
0�
1�
1�
0�
0�
1�
1�
1�
0�
�
0�
1�
0�
1�
1�
0�
1�
1�
0�
�
0�
1�
0�
0�
1�
1�
1�
1�
0�
�
0�
0�
1�
1�
0�
0�
0�
0�
0�
�
0�
0�
1�
0�
0�
1�
0�
1�
0�
�
0�
0�
0�
1�
1�
0�
1�
1�
0�
�
0�
0�
0�
0�
1�
1�
1�
1�
0�
�
1
E1
E2
porta lógica
1
+
0
S
saída
Exemplo
entradas
En
(A(B)
XOR (ou exclusivo)
.
.
.
�PAGE �
�PAGE �2�