Mapa de Karnaugh

Mapa de Karnaugh é um método de simplificação criado por Edward Veitch (1952) e aprimorado pelo Maurice Karnaugh. Chamamos esse diagrama de mapa, sendo um mapeamento a partir uma tabela verdade da função analisada, sendo usado na simplificação de equações lógicas para converter tabelas verdade no circuito lógico correspondente.

Mapa de Karnaugh para duas variáveis.

                                                      Figura 4

                                                     Figura 5

Depois de montado, diferencia-se os minitermos, considerando apenas os campos 1 como solução final, agrupando-os em pares, como na imagem a seguir:

                                                    Figura 6

Mapa de Karnaugh para três variáveis:

Utilizando a tabela verdade para este exemplo, onde A, B e C são entradas e F saída.

	A	B	C	F
0.	0	0	0	S0 = 0
1.	0	0	1	S1 = 1
2.	0	1	0	S2 = 0
3.	0	1	1	S3 = 1
4.	1	0	0	S4 = 1
5.	1	0	1	S5 = 1
6.	1	1	0	S6 = 1
7.	1	1	1	S7 = 0

Com as três expressões, o mapa apresenta a seguinte configuração:

                                            Figura 7

                                              Figura 8

Os campos com a cor amarela (P1) estão na coluna C, e a linha variável A (negado). Já os elementos da cor verde (P2) pertencem à C (negado) e linha da variável A. Os que apresentam a cor rosa (P3) são da coluna B (negado) e C. Por conta disso, a simplificação é:

__               __   __

 A  . C + A . C + B . C

Mapa de Karnaugh pode ser usado com mais variáveis, tendo sua finalidade precisa e diversificada.

Aula 12: ÁLGEBRA BOOLEANA, SUAS APLICAÇÕES E OPERADORES LÓGICOS

A álgebra de Boole é um sistema matemático que usa das propriedades essenciais dos operadores lógicos e forma uma estrutura que lida com as afirmações das operações. É formada por operadores, teoremas, regras e postulados. A álgebra Booleana possui variáveis que podem assumir os valores lógicos zero (0, associado ao Falso), e o um (1, associado ao verdadeiro).

 OPERADORES LÓGICOS

· E (AND) usa o operador "."

· OU (OR) usa o operador "+"

· NEGAÇÃO (NOT) usa o operador "-"

Leis:

1) Elementos de identidade

· A . 0 = 0

· A . 1 = 1

· A + 0 = A

· A + 1 = 1

2) associativa

· (A + B) + C = A + (B + C)

3) comutativa

· A . B = B . A

4) Idempotentes

· A . A = A

5) distributiva

· A . (B + C) = (A . B) + (A . C)

6) absorção

· A . (A + B) = A

7) De Morgan

· ~( A . B ) = ~A + ~B

· ~(A + B) = ~A . ~B

8) complementares

· A . ~A = 0

· A + ~A = 1

Demonstrações

Y = A . (A + B) Y = A	Y = A . A Y = A	Y = A + 1 Y = 1
Y = A . (B + C) Y = (A . B) + (A . C)	Y= A . 1 Y = 1

Tabela 7

                     

  
Figura 3

Exercícios:

APLICAÇÕES

LÓGICA EM BANCO DE DADOS

                 O impacto da lógica nos bancos de dados é um dos melhores exemplos da efetividade da mesma sobre a ciência da computação. A lógica de primeira ordem 4 reside no núcleo dos bancos de dados atuais, sendo utilizada desde as linguagens mais básicas como SQL até algumas mais complexas onde são utilizadas extensões da lógica de primeira ordem junto com a recursão. Há três motivos principais para sua utilização:

            1) - A lógica de primeira ordem possui variáveis sintáticas de fácil utilização.

            2) - Pode ser implementada usando relações algébricas, o que representa uma vantagem crucial quando tratamos de uma grande quantidade de dados.

            3) - Suas buscas podem demorar tempos constantes para qualquer tamanho do banco de dados se houver paralelismo suficiente.

            Uma busca que pode ser expressa em uma lógica de primeira ordem pode ser aberta em uma série de buscas menores, formando assim blocos fundamentais que podem ser usados na busca. Porém está abordagem não é satisfatória, pois pode ser muito lenta com o aumento do banco de dados. A abordagem utilizada na prática envolve relações algébricas. Em resumo, a lógica de primeira ordem e a relação algébrica expressam a mesma busca.

TEORIA DOS TIPOS NAS LINGUAGENS DE PROGRAMAÇÃO

            Nas décadas de 80 e 90, o estudo das linguagens de programação foi revolucionado por uma confluência de idéias da lógica matemática e filosófica e da teoria da computação: a Teoria dos Tipos.

            A Teoria dos Tipos, aplicada a um sistema de tipos, impõe restrições aos programas, prevenindo que ocorram vários erros, decorridos de falhas na interpretação dos valores, como, por exemplo, aplicar uma função a um número inteiro utilizando valores lógicos.

            Um sistema de tipo é definido da seguinte forma: Γ╟ e : τ, onde e é uma expressão, τ é seu tipo e Γ representa tipos das variáveis globais que podem ocorrer em e.

            Segundo o princípio das “proposições como tipos” há um isomorfismo entre proposições e tipos, com a propriedade que a dedução natural prova que uma proposição corresponde aos elementos de seu tipo associado. Esse princípio se estende aos conetivos lógicos e quantificadores, incluindo os de segunda ordem ou de ordem maior.

            Organizar linguagens de programação por estrutura de tipos possui vários benefícios, como evitar confusões de conceitos distintos, ocorrência de erros de interpretação, e aperfeiçoar a eficiência e a integridade do compilador.

Aula 11: QUANTIFICADORES

Existem símbolos que são capazes de quantificar elementos, chamados de quantificadores. São empregados no estudo da lógica e da álgebra.

            São classificados em dois tipos, quantificador universal e quantificador existencial.

Estes dois, representados por:

                ∀ - Para todo (refere-se a todos elementos de um conjunto)

                ∃ - Existe algum (refere-se à algum elemento existente no conjunto)

                ∃! – Existe um único (refere-se à somente um elemento do conjunto)

Exercícios

a)    (∀ x E R) (x<1234)

Resposta: Sentença falsa, pois o símbolo “para todo” não corresponde com a condição de x < 1234.

b)    (∃ x E R) (X<9124)

Resposta: Sentença verdadeira, pois o símbolo “existe algum” corresponde com a condição de x < 9124.

c)    (∃! x E R) (x=13)

Resposta: Sentença verdadeira, pois o símbolo “existe um único” corresponde com a condição de x = 13.

d)    (∃! x E R) (x>25)

Resposta: Sentença falsa, pois o símbolo “existe um único” não corresponde com a condição de x > 25.

e)    (∀ x E R) (x=10)

Resposta: Sentença falsa, pois o símbolo “para todo” não corresponde com a condição de x = 10.

Aula 10: ARGUMENTO VÁLIDO E CRITÉRIOS DE VALIDADE

Chama-se argumento toda a afirmação de que uma dada sequencia finita P1, P2, P3,...,Pn (n >=1) de proposições tem como consequência uma proposição final Q. P1, P2, P3,..., Pn: Premissas Q: conclusão do argumento.

CRITÉRIOS DE VALIDADE

            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. A validade ou não validade de um argumento depende apenas da sua forma e não de seu conteúdo ou da verdade e falsidade das proposições que o integram. Sendo que todo argumento válido tem uma forma válida.

Exercícios

a)    Toda baleia é um mamífero

Todo mamífero tem pulmões

Logo, toda baleia tem pulmões

Resposta: Argumento válido e conclusão verdadeira.

b)    Toda aranha tem seis pernas

Todo ser de seis pernas tem asas

Logo, toda aranha tem asas

Resposta: Argumento válido e conclusão falsa.

c)    Se eu ganhar na loteria, serei rico

Eu não ganhei na loteria

Logo, não sou rico

Resposta: Argumento não válido, a conclusão não é uma decorrência lógica de suas premissas.

d)    Ela toca piano ou violão

Ela toca piano

Logo, ela não toca violão

Resposta: Argumento inválido

e)    Se Matheus está no campo de futebol, então José está no trabalho e Leonardo deve estar jogando.

José não está no trabalho

Portanto, Matheus não está no campo de futebol.

p: Matheus está no campo de futebol, q: José está no trabalho e r: Leonardo está jogando.

Temos então, em sua linguagem simbólica, as premissas:

 [p → (q ^ r) ^ ~q]  ⇒ ~p, validando em tabela verdade.

P	Q	R	q ^ r	p → (q ^ r)	~q	~p
V	V	V	V	V	F	F
V	V	F	F	F	F	F
V	F	V	F	F	V	F
V	F	F	F	F	V	F
F	V	V	V	V	F	V
F	V	F	F	V	F	V
F	F	V	F	V	V	V
F	F	F	F	V	V	V

Resposta: Argumento válido de acordo com suas premissas.