Apostila Logica

URI – Universidade Regional IntegradaCampus de Erechim

Curso de Ciência da Computação

Apostila de Lógica para a Computação

Prof. Neilor Tonin

Erechim, 4 de Agosto de 2008

Apostila de Lógica para a computação 2

Plano de ensino da disciplina: 35-324 Lógica para a ComputaçãoDepartamento: 03 Engenharias e Ciência da ComputaçãoCarga horária: 60 horas Créditos: 04

EMENTA:

Álgebra booleana. Proposições. Operações Lógicas sobre Proposições. Construção de Tabelas-Verdade. Tautologia, Contradições e Contingências. Implicação Lógica. Álgebra das Proposições. Método Dedutivo. Argumentos , Regras de Inferência. Validade mediante Regras de Inferência. Cálculo de Predicados.

OBJETIVOS:

Formalização de idéias complexas de forma mais simples. Propicia um novo ou melhor entendimento das questões relacionadas com toda a Ciência da Computação. Auxilia no desenvolvimento de aplicações e solução de problemas reais que envolvem aplicação da computação.

RELAÇÃO DOS CONTEÚDOS:

1. Proposições – Conectivos: • Valores lógicos; Proposições Simples e Proposições Compostas; Conectivos; Tabela-Verdade.

2. Operações Lógicas sobre Proposições:• Negação; Conjunção; Disjunção; Disjunção Exclusiva; Condicional; Bicondicional;

3. Construção de Tabelas-Verdade: • Tabela-Verdade de uma proposição composta; Número de Linhas; Construção de uma T.V.; Valor lógico

4. Tautologia, Contradições e Contingências: • Tautologia; Princípio de substituição; Contradição; Contingência.

5. Implicação Lógica: • Definição; Propriedades; Tautologia e equivalência Lógica; • Proposições associadas a uma condicional; • Negação conjunta de duas proposições; Negação disjunta de duas proposições;

6. Álgebra das Proposições7. Método Dedutivo: Formas normais; Princípio da dualidade;

8. Argumentos , Regras de Inferência: • Definição; Validade; Critério; Condicional Associada; Argumentos Válidos; • Regras de Inferência; Validade mediante as Regras de Inferência

9. Cálculo de Predicados: • Quantificadores e Variáveis; Predicados e nomes próprios; Regras de formação; • Regras de inferência para o quantificador universal; • Regras de inferência para o quantificador existencial; • Teoremas e regras de equivalência do quantificador; • Identidade.

BIBLIOGRAFIA BÁSICA (LIVROS TEXTOS):Sérates, Jonofon. Raciocínio Lógico. 8 ed – Brasília:Editora Jonofon LTDA, 1998. Nolt, J; Rohatyn, D. Lógica. Coleção Schaum, McGraw-Hill, Inc., 1991.

BIBLIOGRAFIA COMPLEMENTAR (LIVROS REFERENCIADOS):James L. Hein. Discrete Structures, Logic and Computability; Jones & Bartlett 1995.H. B. Enderton. A mathematical introduction to logic, Academic Press, 2ed. 2001. D. M. Gabbay. Elementary Logics: a procedural perspective, Prentice Hall, 1998. Alencar Filho, Edgar de. Iniciação à Lógica Matemática. 8 ed. São Paulo: Ed. Nobel, 1976. Mendelson, B. Introduction to Mathematical Logic. Princeton, NJ, Van Nostrand, 1964.

Cálculo da média semestral: (P1*4 + P2*4 + T*2 ) / 10onde: P1 = Primeira prova P2 = Segunda prova T = Trabalho


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 34. 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 planetac) 9-12d) 9e) 8*7 = 56f) O gato da meninag) Um bom livro de matemáticah) 3 + 5 <> 5 + 3i) 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

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=8b) 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 é parh) 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 é estudanteR: O número 25 é um quadrado perfeito

Proposições compostas

P: Zenóbio é careca e Pedro é estudanteQ: Zenóbio é careca ou Pedro é estudanteR: 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 2Q: O triângulo ABC é retângulo ou o triângulo ABC é isóscelesR: Não está chovendoS: Se Jorge é engenheiro, então sabe matemáticaT: 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).

PVF

V P

F


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 linhas2 elementos: 22 linhas = 4 linhas3 elementos: 2 3linhas = 8 linhas4 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, exprime-se que p é verdadeiro escrevendo: 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ções simples:p: O Sol é verdeq: um hexágono tem 6 ladosr: 2 é um número ímpars: um triângulo tem 4 lados

Temos:V(p)=F V(q)=V V(r) =F V(s) =F


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 . qV V VV F FF V FF F F

ou seja, pelas igualdades:

V . V = V, V . F = F, F . V, F . F = F e(p ^ q) = V (p) ^ V (q)

Exemplos:


(1) {p: A neveé branca V q: 25V }

p . q: A neve é branca e 2 < 5 (V) V (p . q) = V(p) . V(q) = V . V = V

(2) {p:O enxofre é verdeF

q:7 é umnúmero primoV } 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 + qV V VV F VF V VF F F

V (p + q) = V (p) + V (q)

Exemplos:

(1) {p: Parisé a capital da FrançaV 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õesescreveuos LusíadasV 22=3F }

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 professorQ: Mário é alagoano ou gaúcho

Na proposição P se está a indicar que uma pelo menos 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.


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 qIII. p é condição suficiente para qIV. 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 horasp: 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


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 qii. q é condição necessária e suficiente para piii. 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 pq e qp são verdades, temos falsidade nos casos:pq sendo v(p)= V e V(q) = F e,qp 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 eii) 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) ~pb) p.qc) p+qd) q <-> pe) p -> ~qf) q v ~pg) ~p ^ ~qh) ~~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+qb) q->pc) pv~qd) q<->~pe) ~p->qf) (~p.q)->p


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) ->pb) (p.~q) ->~pc) ~p . ~qd) p+~qe) ~(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 = 6b) Não é verdade que 2 + 2 = 7 se e somente se 4 + 4 = 9c) DANTE escreveu os Lusíadas ou 5 + 7 < 2d) Não é verdade que 1 + 1 = 3 ou 20 = 1e) É 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) = Vb) V(q→p) = V e V(q) = Fc) V(q+p) = F e V(q) = Fd) V(q+p) = V e V(q) = V

15) Considerando V(p) = F , V(x) = F e V(y) = Va) 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 Vb) (p+r)+(s → q), onde q tem valor Fc) ((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.


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.(~qp)). ~((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 ) → pd) (p → r ) ⊕ pe) (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 Tautologiab) Última coluna da tab. - verdade apresenta somente F(s)Fórmula contra-válidaContradiçãoc) Ú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 ⊕ be) 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:


Exercícios:

19) Verificar as implicações.a) p ⇒ p + qb) p . q ⇒ pc) (p + q) . ~p ⇒ qd) (p ↔ q) . p ⇒ qe) (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)


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 ├ qb) p→q, q ├ pc) 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 26 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,SA, CS ├ 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 P2) S A P3) C S P4) 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


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.pr 3.qr 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 (SF), 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. pq 2. qp 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. pq 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 pq.

Ex. Prove o argumento anterior.Premissas: I: Joelho Inchado C: Continuar correndo S: Joelho irá sarar em uma semanaA: 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 ├ ~p1. p q p2. ~q p3. p H4. q 1,3 MP5. q . ~q 2,4 .I6. ~p 3,5 RAA


Exercícios para compreensão e fixação das regras de inferência:

MP (→ E)a) ~p→q, ~p ├ qb) ~p→(q→r), ~p, q ├ r

~Ec) t→ ~~p, p→~q, t ├ ~qd) ~p → ~~q, ~~~p ├ q

. Ie) p→ q, r→s, p, r ├ q . s

. Ef) p→ (q . r), p ├ p . qg) p . q ├ q . ph) (p . q) → (r . s), ~~p, q ├ si) p ├ p . pj) ~p . q → u, ~~~p, s→q, x→r.s, x ├ uk) s → ((p.q)→~~r), p.q, t.s ├ r.t

+ Il) p ├ (p+q) . (p+r)m) p, ~~(p→q) ├ q+ ~qn) p, ~~(p→q) ├ (r.s)+qo) p ├ p+p

+ Ep) 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.tr) p+p, p→(q.r) ├ r

↔ Is) p→q, (p→q) → (q→p) ├ p ↔ qt) p ↔ q ├ q ↔ pu) s→(r→p), a.s, p→r ├ (p↔r) + qv) ~~(p↔x), ~~(q→x), x.p→k, p+q, k↔u ├ u

↔ Ew) 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 → ~ab) p → q, q→r ├ p→rc) p ├ (p→q) → qd) (p.q)→r ├ p→ (q→r)e) p + q ├ q + pf) (p.q) + (p.r) ├ p. (q+r)

RAA ( ~I)g) p→q, ~q ├ ~ph) p ↔ ~q ├ ~(p.q)i) ~p →p ├ pj) s→~~v ├ ~v → ~sk) (~s.v)→~p, p, v ├ sl) ~(~p.~q), ~p ├ qm) ~p + ~q ├ ~(p . q)n) p→q ├ ~p+qo) ~ ( p . q) ├ ~p + ~q

Exercícios complementaresa) (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 é verdadeirap As premissas deste argumento são verdadeirass 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.


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 provasNã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çaFó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 ~α.


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


Exemplo de simplificação utilizando as regras de equivalência

Expressão: x.a . y.ba.x

a) Resolução forma convencional (recomendado):

x.a . y.ba.xx.a . y.ba.x = α.β+ ~β = α + ~β

y.b a.xbya.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.ba.xxa . yba.xa. ba. yx.bx. ya.xa.b . V a. b . xx a.b . x. yy x. yy a.b . x.yx. y x.yx. y = a. b. x.ya. b. x. ya. b. x. ya. b. x. ya. y . b.xb. xb. xb.x = a. b.x. ya.b. x. ya. b. x. ya. b. x. yx. b . a.ya.y a.ya. y = a. b. x. ya. b. x. ya. b. x. ya. b. x. yx. y .a.ba.b a.ba.b = a.b. x. ya. b. x. ya.b. x. ya. b. x. ya. x . b.yb.y b.yb. y = a.b.x.ya.b.x. ya. b. x.ya. b. x. y

• Segundo passo: Simplificar através de Mapa Karnaugh

00 01 11 1000 . . . .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

bya.x


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. bb

2. a. bb

3. b.aa

4. b.aa

5. a. bb

6. a. bb

7. b.aa

8. b. aa

9. b. aa

10. a. bb

11. x . yy

12. a. xx

13. a. yy

14. x. yx

15. y. xx

16. y. xx

17. y. xx

18. a.bba

19. a.ba . y . x

20. x.a. y.bx.a

21. y. xx.y

22. y. xx. y. z

23. y.x x.y y

24. a.ba.c. b

25. b.a c.bb.c

26. y. xx.x

27. y. xx.y. z

28. x.y x.y y

29. a.ba.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.xx.y y . x

35. xx.y y . x yx y . x

36. y.xx . x y.xx y . x

37. y.x x.y y . x

38. y.x x.y y . x y.xx.y y.x

39. y.x x.y y . x y.xx.y y. x

40. p r p

41. p r p

42. p r p.r

43. p.rr p.r

44. p r p

45. p.r p.q. r p p.r

46. p.rr p.r p p

47. p.rr 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.rr p.r

53. p r p

54. p.rr p.r p p

55. p.q r p.r


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 feita em 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


MinimizaçãoA 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 10 0 01 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)


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 101

Figura 4


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~cb) ã~b~c+a~b~c+a~bc+abc+ab~c+ãb~cc) bac+a~bc+ãbc+ab~c+ãb~cd) ã~b~c+a~b~c+a~bc+abc+ãb~c


É 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~dc) ã~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


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 completab) a expressão simplificadac) 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.zb) a.b.c + a.b.c + a.b.c + a.b.c

a) 00 01 11 10 b) 00 01 11 1000 001 11110

5) Dê a expressão simplificada para os seguintes mapas de karnaugh:

a) 00 01 11 10 b) 00 01 11 1000 0 1 1 1 00 0 0 0 001 0 0 0 1 01 1 1 1 111 0 0 0 1 11 1 1 1 110 0 1 0 1 10 0 1 0 0

c) 00 01 11 10 d) 00 01 11 1000 0 1 1 0 00 1 1 0 101 0 0 0 0 01 0 1 0 011 1 0 0 1 11 0 1 1 010 0 1 1 0 10 1 0 0 1


e) 00 01 11 10 f) 00 01 11 1000 0 1 0 0 00 1 1 0 101 0 1 1 1 01 1 1 0 011 1 1 1 0 11 1 1 1 110 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 1a3 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 wxyz0000000100100011010001010110011110001001101010111100110111101111

0000100011000100011011101010001000111011111101110101110110010001

9) É possível reprojetar o circuito do problema acima (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=


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 Z0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 1 0 0 10 1 0 0 0 0 0 2 0 1 00 0 1 0 0 0 0 3 0 1 10 0 0 1 0 0 0 4 1 0 00 0 0 0 1 0 0 5 1 0 10 0 0 0 0 1 0 6 1 1 00 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.htmlhttp://www.eece.unm.edu/faculty/devries/Net/Homework/boolean.html

http://fiddle.visc.vt.edu/courses/ee2504/combinational/logic_01.html

http://www.eece.unm.edu/faculty/devries/Net/Homework/boolean.html


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ÍDASD1 D2 D3 D4 D5 D6 D7 Decimal X Y Z0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 1 0 0 10 1 0 0 0 0 0 2 0 1 00 0 1 0 0 0 0 3 0 1 10 0 0 1 0 0 0 4 1 0 00 0 0 0 1 0 0 5 1 0 10 0 0 0 0 1 0 6 1 1 00 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 L70 0 0 1 1 1 1 1 10 0 1 1 10 1 0 1 1 1 1 10 1 1 1 1 1 1 11 0 0 1 1 1 11 0 1 1 1 1 1 11 1 0 1 1 1 1 1 11 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= L7=

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).


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 10 0 1 1 10 1 0 1 10 1 1 1 11 0 0 1 11 0 1 1 11 1 01 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

L1L2L3

L4L5L6

- 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


a.b.c.a b.a b.a c.a b.ab.ab.ac.av

a.b.b.a c.aa.ba.ba.ca.ba.c

b.a. b.a b.a b.a

a.ba.ba.ba.ba.b

b.a. b.c b.c a.b a.bb.cb.c a.b

v

y.xx.y y . x x.y y . xx.y

xx.y y . x yx y . x x y . x x y . xx y . xx.xx.yxx.y

x

y.xx . x y.xx y . xx . xv . xxxx

y.x x.y y . xy.x x.y . y . xy.x f.xx.y

y.x x.y y . x y.xx.y y.xx.y y.x . x.y y.xx.y y.xv

y.x x.y y . x y.xx.y y. xy.x y.x . x.y y.xy.x y.x y. xV y. xv

p r p pr p pr pp . r p p p r p pr p

pr pp . rprp

p r p.r pr pr pr prp . rprpr

p.rr p.r p.r r pr p.r rprp.r.rprFprpr

p r p pr p pr pp . rpp

p.r p.q. r p p.r p.r pq . r p p.r p.r p. rq. r p p.r p.r rq. r p p.rprr p p.rV p.rF p.rpr

p.rr p.r p p p.rr p.r p p prr p.r p pV p pF p pp p

v p.r r p.r p p p.rr p.r p pr p.r p pr p pr . p pr p

p.q r p.r p.qr pr p.qr prp.qrrpp.qVp

v

p r p pr . ppr . pp. pr.pp .r . pr.pFr.p

p r p pr . ppr . pp. pr. pp .r . ppr. p p.rp p.rpr

p.rr p.r p.r r prprr prV prV. pr F. pr pr

p r p.r pr . p.rpr . p.r pr . pr p.r . p.r p. pp .r .r . pr.r Fp p. rr. pFpr. p p

p r p pr . ppr . pp. pr. pp .r . pFr. pFr. p

p.rr p.r p p p.rr p.r p pr p pr p pr p . pr p . pr. p p.pr . p . pr. p pr. ppr. ppr

p.q r p.r p.qr p.r p.q .r p.r p.q .r p.r p.q .r . p.r p.q .r . p.r pq .r . pr p.qr . p.r p.rq . r . pr p.q.p.r p.r.r p. r. p p.r .rq .r . pq.r .r ...p.r p. rq . r . pq.r p.rp.rq .r p.rp.rq .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)

Documents

Apostila Logica