A lógica booleana

A lógica booleana é um completo sistema de lógica operações. Foi nomeado após George Boole, que primeiro definiu um sistema algébrico de lógica em meados do século 19 . Lógica booleana tem muitas aplicações na eletrônica, hardware e software de computador, e é a base de eletrônica digital. Em 1938 , Claude Shannon mostrou como circuitos elétricos com relés eram um modelo para a lógica booleana. Esse fato logo provou enormemente consequente com o surgimento da eletrônica computador .

Usando o álgebra de conjuntos, este artigo contém uma introdução básica à conjuntos, operações booleanas, diagramas de Venn , tabelas de verdade, e aplicações booleana. O Álgebra booleana artigo discute um tipo de estrutura algébrica que satisfaz os axiomas da lógica booleana. A aritmética binária artigo discute o uso de binários em números de computadores sistemas.

Definir lógica contra a lógica booleana

Os conjuntos podem conter quaisquer elementos. Vamos primeiro começar por discutir lógica geral set, em seguida, limitar-nos a lógica booleana, onde elementos (ou "bits") contêm, cada um apenas dois valores possíveis, chamado vários nomes, como "verdadeiro" e "falso", "sim" e "não", "on" e "off", ou "1" e "0".

Condições

Diagrama de Venn, mostrando a intersecção de conjuntos "A e B" (em violeta / sombreado escuro), a união dos conjuntos de "A ou B" (todas as regiões coloridas / sombreadas), eo exclusivo OR caso "set A XOR B" ( todas as regiões coloridas, exceto as violetas / apenas as regiões levemente sombreadas). O "universo" é representado por toda a área dentro da moldura retangular.

Seja X um conjunto:

• Um elemento é um membro de um conjunto. Isto é indicado pela . Se não é um elemento do conjunto, este é indicado por .

• O universo é o conjunto X, por vezes, denotado por 1. Observe que este uso da palavra universo significa "todos os elementos que estão sendo considerados", que não são necessariamente o mesmo que "todos os elementos existem".

• O conjunto vazio ou nulo conjunto é o conjunto de nenhum elemento, indicado por e, por vezes, 0.

• Um operador unário aplica-se a um único conjunto. Há um operador unário, chamado lógico NOT. Ele funciona tomando o complementar.

• Um operador binário se aplica a dois conjuntos. Os operadores binários básicos são lógicos OR e AND. Eles executam o união e intersecção de conjuntos. Há também outros operadores binários derivados, tais como XOR (OU exclusivo).

• Um subconjunto é denotada por e significa que cada elemento no conjunto A está também em conjunto B.

• Um subconjunto apropriado é indicado por e significa que cada elemento no conjunto A está também em conjunto B e os dois conjuntos não são iguais.

• Um subconjunto é denotada por e significa que cada elemento no conjunto B também está no conjunto A.

• Um subconjunto adequado é denotada por e significa que cada elemento no conjunto B também está no conjunto A e os dois conjuntos não são iguais.

Exemplo

Vamos imaginar que conjunto A contém todos os números pares (múltiplos de dois) no "universo" (definido no exemplo à direita, como todos os números inteiros entre 0 e 30, inclusive) e definir B contém todos os múltiplos de três no "universo". Em seguida, a interseção dos dois conjuntos (todos os elementos em conjuntos A e B) seria todos os múltiplos de seis em "o universo".

O complemento de set A (nem tudo elementos em conjunto A) seria todos os números ímpares em "o universo".

Encadeamento operações em conjunto

Enquanto, no máximo, dois conjuntos são unidos em qualquer operação booleana, o novo conjunto formado por essa operação pode então ser juntado com outros conjuntos utilizando operações booleanas adicionais. Usando o exemplo anterior, podemos definir um novo conjunto C como o conjunto de todos os múltiplos de cinco "do universo". Assim, "conjuntos A e B e C" seria todos os múltiplos de 30 no "universo". Se for mais conveniente, podemos considerar definir AB para ser a intersecção de conjuntos A e B, ou o conjunto de todos os múltiplos de seis em "o universo". Então, podemos dizer que "define, B e C" são o conjunto de todos os múltiplos de 30 no "universo". Poderíamos, então, dar um passo mais longe, e chamar isso de definir ABC resultado.

Uso de parênteses

Enquanto qualquer número de ANDs lógicas (ou qualquer número de RUP lógicas) podem ser encadeadas sem ambiguidade, a combinação de operadores AND e OR e NOTs pode levar a casos ambíguos. Em tais casos, os parênteses pode ser usada para clarificar a ordem das operações. Como sempre, as operações dentro do par mais interior é realizado em primeiro lugar, seguido pelo par seguinte para fora, etc, até que todas as operações dentro de parênteses foram concluídos. Em seguida, todas as operações fora dos parênteses são executadas.

Aplicativo para valores binários

Neste exemplo nós usamos números naturais , enquanto na lógica booleana números binários são usados. O universo, por exemplo, pode conter apenas dois elementos, "0" e "1" (ou "verdadeiro" e "falso", "sim" e "não", "on" ou "off", etc.). Também se pode combinar valores binários em conjunto para obter palavras binárias, tais como, no caso de dois dígitos, "00", "01", "10" e "11". Aplicando a lógica conjunto com esses valores, poderíamos ter um conjunto de todos os valores, onde o primeiro dígito é "0" ("00" e "01") e do conjunto de todos os valores em que os primeiro e segundo dígitos são diferentes ("01" e "10"). A intersecção dos dois conjuntos seria, então, o elemento único, "01". Tal poderia ser demonstrado pela seguinte expressão booleana, onde "primeiro" é o primeiro dígito e "2" é o segundo dígito:

(NÃO 1º) AND (NOT 2º 1º)

Propriedades

Vamos definir símbolos para as duas operações binárias primárias como (/ Set intersecção E lógico) e (OR lógico / união de conjunto), e para a operação unário único / ~ (NOT lógico complemento / set). Também utilizaremos os valores 0 (FALSO lógico / o conjunto vazio) e 1 (lógico TRUE / o universo). As seguintes propriedades aplicam-se tanto a lógica booleana e lógica definida (embora apenas a notação para a lógica booleana é exibido aqui):

		associatividade
		comutatividade
		absorção
		distributividade
		complementos
		idempotency
		boundedness
		0 e 1 são complementos
		As leis de De Morgan
		involução

As três primeiras propriedades definem um estrutura; os primeiros cinco definir um Álgebra booleana. Os cinco restantes são uma consequência dos cinco primeiros.

Tabelas de verdade

Para a lógica booleana usando apenas dois valores, 0 e 1, o cruzamento e da União desses valores pode ser definida usando tabelas de verdade, como estes:

0 1 0 0 0 1 0 1

0 1 0 0 1 1 1 1

• Mais tabelas de verdade complexas envolvendo várias entradas, e outras operações booleanas, também pode ser criado.

• Tabelas de verdade têm aplicações em lógica , interpretação 0 como FALSE, 1 como TRUE, E como, como OR, e ¬ como NOT.

Outros notações

Os matemáticos e engenheiros costumam usar de mais (+) para OU e um sinal de produto ( ) De E. OR e E são um pouco análoga à adição e multiplicação em outras estruturas algébricas , e esta notação torna muito fácil chegar soma dos produtos formar para a álgebra normal. NÃO pode ser representado por uma linha traçada acima da expressão sendo negada ( ).

Programmers, muitas vezes, usar um símbolo pipe (|) para OU, um e comercial (&) para E, e um til (~) não para. Em muitas linguagens de programação , esses símbolos representam operações bit a bit. "||", "&&", E "!" são usados para variantes destas operações.

Outra notação usa "idônea" para E e "juntar-se" para OR. No entanto, isto pode conduzir a confusão, como o termo "juntar" também é geralmente utilizado para qualquer operação booleana que combina conjuntos juntos, que inclui tanto AND e OR.

Utilização matemática básica de termos booleanos

• No caso de equações simultâneas, eles estão conectados com uma lógica implícita E:

x + y = 2

E

x - y = 2

• O mesmo se aplica às desigualdades simultâneas:

x + y <2

E

x - y <2

• A maior ou sinal de igual ( ) E inferior ou igual a sinal ( ) Pode ser assumido como contendo uma lógica OR:

X <2

OR

X = 2

• O sinal de mais / menos ( ), Como no caso da solução a um problema de raiz quadrada, pode ser tomado como lógica OU:

WIDTH = 3

OR

WIDTH = -3

Uso da língua Inglês de termos booleanos

Cuidados devem ser tomados ao converter uma frase Inglês em uma expressão booleana formal. Muitas frases em inglês têm significados imprecisos, por exemplo, "Nem tudo que reluz é ouro", o que poderia significar que "nada que reluz é ouro" ou "algumas coisas que brilham não são de ouro".

AND e OR também podem ser utilizados alternadamente, em Inglês, em certos casos:

• "Eu sempre levar um guarda-chuva quando chove e neva."

• "Eu sempre levar um guarda-chuva quando chove ou neva."

Às vezes, as palavras inglesas AND e OR tem o sentido oposto em lógica booleana:

• "Dê-me todas as bagas vermelhas e azuis" normalmente significa "Dê-me todas as bagas que são vermelho ou azul". Um fraseado alternativo para padrão Inglês escrito: "Dê-me todas as bagas que são vermelhas, assim como todas as bagas que são azuis".

Observe também que a palavra OR em Inglês pode corresponder com qualquer lógica OR ou XOR lógico, dependendo do contexto:

• "Eu começo a suar quando a humidade ou a temperatura é alta." (OR lógico)

• "Você quer sorvete e doces? Você pode ter sorvete ou doces." (XOR lógico)

A combinação E / OU às vezes é usado em Inglês para especificar um OU lógico, quando apenas usando a palavra ou sozinho pode ter-se enganado no sentido de XOR lógico:

• "Eu estou tendo frango e / ou carne para o jantar." (OR lógico). Um fraseado alternativo para padrão Inglês escrito: "Eu estou tendo frango, ou carne, ou ambos, para o jantar."

• O uso do "e / ou" virgule é geralmente desfavorecidos em Inglês formal escrito. Tal uso pode apresentar imprecisão crítico em instrumentos jurídicos, os resultados da investigação, e especificações para os programas de computador ou circuitos eletrônicos.

Um caso em que este é um problema é quando as especificações para um programa de computador ou circuito eletrônico são fornecidos como um parágrafo descrevendo Inglês sua função. Por exemplo, a declaração: "o programa deve verificar que o requerente tenha marcado a caixa sexo masculino ou feminino", deve ser tomado como um XOR, e um cheque adicionados para garantir que um, e apenas um, a caixa está selecionada. Em outros casos, a interpretação do Inglês pode ser menos certo, eo autor da especificação pode ter de ser consultado para determinar a sua verdadeira intenção.

Aplicações

Design digital circuito eletrônico

A lógica booleana é usado também para projeto de circuito em engenharia elétrica ; aqui 0 e 1 pode representar os dois estados diferentes de um bits numa circuito digital, tipicamente alta e baixa Tensão. Circuitos são descritos por expressões contendo variáveis, e duas dessas expressões são iguais para todos os valores das variáveis se, e somente se, os circuitos correspondentes têm o mesmo comportamento de entrada-saída. Além disso, cada comportamento de entrada-saída possível pode ser modelada por uma expressão booleana apropriada.

Básico portas lógicas, tais como AND, OR e NOT portas pode ser usado sozinho, ou em conjunção com NAND, NOR, e portas XOR, para controlar electrónica digital e do circuito. Se estas portas são ligados em série ou em paralelo controla a precedência das operações.

Aplicações de banco de dados

Bancos de dados relacionais usar SQL, ou outras linguagens específicas de banco de dados, para efectuar consultas, que podem conter a lógica booleana. Para esta aplicação, cada registo de uma tabela pode ser considerado como um "elemento" de um "conjunto". Por exemplo, no SQL, estes Instruções SELECT são usados para recuperar dados de tabelas no banco de dados:

    SELECT * FROM empregados Onde LAST_NAME = 'Smith' E FIRST_NAME = 'João';

    SELECT * from employees where LAST_NAME = 'Smith' OR FIRST_NAME = 'João';

    SELECT * from employees where NÃO last_name = 'Smith';

Parênteses podem ser usados para especificar explicitamente a ordem em que ocorrem operações booleanas, quando várias operações estão presentes:

    SELECT * from employees where (NÃO last_name = 'Smith') AND (FIRST_NAME = 'John' OR FIRST_NAME = 'Mary');

Vários conjuntos de parênteses aninhados podem também ser utilizados, quando necessário.

Qualquer operação booleana (ou operações) que combina dois (ou mais) tabelas em conjunto é referido como uma associação, na terminologia de banco de dados relacional.

No campo de Registros médicos eletrônicos, alguns aplicativos de software utilizam a lógica booleana para consultar suas bases de dados do paciente, no que tem sido chamado Tecnologia de processamento de conceito.

Consultas do Search Engine

Consultas do Search Engine também empregar a lógica booleana. Para esta aplicação, cada página da Web no Internet pode ser considerado um "elemento" de um "set". Os exemplos a seguir usar uma sintaxe suportada pelo Google .

• De aspas são usados para combinar palavras separadas por espaços em branco em um único termo de pesquisa.
• Espaço em branco é usado para especificar E lógico, como é o operador padrão para unir termos de pesquisa:

    "Pesquisar prazo 1" "Pesquisar termo 2"

• A palavra-chave OR é usado para lógica OR:

    "Pesquisar prazo 1" ou "Procurar termo 2"

• O sinal negativo é usado para NOT lógico (AND NOT):

    "Pesquisar prazo 1" - "Pesquisar termo 2"