Regras deMorgan explicadas

Question

Você poderia explicar o regras deMorgan tão simples quanto possível (por ex.para alguém com formação apenas em matemática no ensino secundário)?

Answer 1

Temos dois valores: T e F.

Podemos combinar esses valores de três maneiras: NOT, AND, e OR.

NOT é o mais simples:

• NOT T = F
• NOT F = T

Podemos escrever isso como um Tabela de verdade:

when given.. | results in...
============================
           T | F
           F | T

Para concisão

x | NOT x
=========
T | F
F | T

Imagine NOT Enquanto o complemento, isto é, transforma um valor no outro.

AND funciona em dois valores:

x y | x AND y
=============
T T | T
T F | F
F T | F
F F | F

AND é T Só quando ambos são argumentos (os valores de x e y na tabela de verdade) são T - e F por outro lado.

OR é T Quando pelo menos um de seus argumentos é T:

x y | x OR y
=============
T T | T
T F | T
F T | T
F F | F

Podemos definir combinações mais complexas. Por exemplo, podemos escrever uma tabela de verdade para x AND (y OR z), e a primeira linha está abaixo.

x y z | x AND (y OR z)
======================
T T T | ?

Uma vez que sabemos como avaliar x AND (y OR z), podemos preencher o resto da tabela.

Para Avalie A combinação, avalie as peças e trabalhe a partir daí. Os parênteses mostram quais partes avaliarem primeiro. O que você sabe da aritmética comum o ajudará a resolvê -lo. Diga que você tem 10 - (3 + 5). Primeiro você avalia a parte entre parênteses para obter

10 - 8

e avaliar isso como sempre para obter a resposta, 2.

Avaliando isso expressões funciona da mesma forma. Nós sabemos como OR Trabalha de cima, para que possamos expandir uma mesa um pouco:

x y z | y OR z | x AND (y OR z)
===============================
T T T | T      | ?

Agora é quase como se estivéssemos de volta ao x AND y tabela. Simplesmente substituímos o valor de y OR z e avaliar. Na primeira fila, temos

T AND (T OR T)

que é o mesmo que

T AND T

o que é simplesmente T.

Repetimos o mesmo processo para todos os 8 valores possíveis de x, y, e z (2 valores possíveis de x vezes 2 possíveis valores de y vezes 2 possíveis valores de z) para obter

x y z | y OR z | x AND (y OR z)
===============================
T T T | T      | T
T T F | T      | T
T F T | T      | T
T F F | F      | F
F T T | T      | F
F T F | T      | F
F F T | T      | F
F F F | F      | F

Algumas expressões podem ser mais complexas do que precisam. Por exemplo,

x | NOT (NOT x)
===============
T | T
F | F

Em outras palavras, NOT (NOT x) é equivalente para somente x.

As regras de Demorgan são truques úteis que nos permitem converter entre expressões equivalentes que se encaixam em certos padrões:

• NOT (x AND y) = (NOT x) OR (NOT y)
• NOT (x OR y) = (NOT x) AND (NOT y)

(Você pode pensar nisso como NOT distribui através do simples AND e OR expressões.)

Seu senso comum provavelmente já entende essas regras! Por exemplo, pense no pouco da sabedoria folclórica de que "você não pode estar em dois lugares ao mesmo tempo". Poderíamos fazê -lo se encaixar na primeira parte da primeira regra:

NOT (here AND there)

Aplicando a regra, isso é outra maneira de dizer "você não está aqui ou não está lá".

Exercício: Como você pode expressar a segunda regra em inglês simples?

Para a primeira regra, vejamos a tabela de verdade para a expressão no lado esquerdo do sinal igual.

x y | x AND y | NOT (x AND y)
=============================
T T | T       | F
T F | F       | T
F T | F       | T
F F | F       | T

Agora, o lado da areia:

x y | NOT X | NOT Y | (NOT x) or (NOT y)
========================================
T T | F     | F     | F
T F | F     | T     | T
F T | T     | F     | T
F F | T     | T     | T

Os valores finais são os mesmos nas duas tabelas. Isso prova que as expressões são equivalentes.

Exercício: Provar que as expressões NOT (x OR y) e (NOT x) AND (NOT y) são equivalentes.

Answer 2

Olhando para algumas das respostas, acho que posso explicar melhor usando condições que estão realmente relacionadas entre si.

A lei de Demorgan refere -se ao fato de que existem duas maneiras idênticas de escrever qualquer combinação de duas condições - especificamente, o AND combinação (ambas as condições devem ser verdadeiras) e o OR combinação (qualquer um pode ser verdadeiro). Exemplos são:

Parte 1 da lei de Demorgan

Declaração: Alice tem um irmão.
Condições: Alice tem um irmão OR Alice tem uma irmã.
Oposto: Alice é filho único (faz NOT tem um irmão).
Condições: Alice faz NOT tem um irmão, AND ela faz NOT tem uma irmã.

Em outras palavras: NOT [A OR B] = [NOT A] AND [NOT B]

Parte 2 da lei de Demorgan

Declaração: Bob é um motorista de carro.
Condições: Bob tem um carro AND Bob tem uma licença.
Oposto: Bob é NOT um motorista de carro.
Condições: Bob faz NOT Ter um carro, OR Bob faz NOT ter uma licença.

Em outras palavras: NOT [A AND B] = [NOT A] OR [NOT B].

Eu acho que isso seria um pouco menos confuso para uma criança de 12 anos. Certamente é menos confuso do que todo esse absurdo sobre as tabelas da verdade (mesmo estou ficando confuso olhando para tudo isso).

Answer 3

É apenas uma maneira de reafirmar as declarações da verdade, que podem fornecer maneiras mais simples de escrever condicionais para fazer a mesma coisa.

Em inglês simples:
Quando algo não é isso ou aquilo, também não é isso e não isso.
Quando algo não é isso e aquilo, também não é isso ou não.

Observação: Dada a imprecisão do idioma inglês na palavra 'ou' estou usando-a para significar um exemplo não exclusivo ou no exemplo anterior.

Por exemplo, o seguinte pseudo-código é equivalente:
Se não (a ou b) ...
Se (não a) e (não b) ....

Se não (a e b) ...
Se não (a) ou não (b) ...

Answer 4

Se você é um policial que procura bebedores menores de idade, pode fazer um dos seguintes, e a lei de De Morgan diz que eles representam a mesma coisa:

Formulação 1 (A e B)

Se eles estão debaixo o limite de idade e bebendo um alcoólicobebida, prenda -os.

Formulação 2 (não (não a ou não B))

Se eles estão sobreo limite de idade ou bebendo um não alcoólico bebida, deixe -os ir.

A propósito, este não é o meu exemplo. Até onde eu sei, fazia parte de um experimento científico em que a mesma regra foi expressa de maneiras diferentes para descobrir a diferença que fazia na capacidade das pessoas de entendê -las.

Answer 5

"Ele não tem carro ou ônibus." significa a mesma coisa que "ele não tem carro e não tem ônibus".

"Ele não tem um carro e um ônibus." Significa a mesma coisa que "ele não tem carro ou não tem ônibus, não tenho certeza de qual, talvez ele não tenha".

Claro, em inglês simples "ele não tem carro e ônibus". tem uma forte implicação de que ele tem pelo menos uma dessas duas coisas. Mas, estritamente falando, do ponto de vista da lógica, a afirmação também é verdadeira se ele não tiver nenhum deles.

Formalmente:

• não (carro ou ônibus) = (não carro) e (não ônibus)
• não (carro e ônibus) = (não carro) ou (não ônibus)

Em inglês, 'ou' tende a significar uma escolha, que você não tem as duas coisas. Na lógica, 'ou' sempre significa o mesmo que 'e/ou' em inglês.

Aqui está uma tabela de verdade que mostra como isso funciona:

Primeiro caso: não (cor ou barramento) = (não carro) e (não ônibus)

 c | b || c or b | not (c or b) || (not c) | (not b) | (not c) and (not b)
---+---++--------+--------------++---------+---------+--------------------
 T | T ||    T   |      F       ||    F    |    F    |        F
---+---++--------+--------------++---------+---------+--------------------
 T | F ||    T   |      F       ||    F    |    T    |        F
---+---++--------+--------------++---------+---------+--------------------
 F | T ||    T   |      F       ||    T    |    F    |        F
---+---++--------+--------------++---------+---------+--------------------
 F | F ||    F   |      T       ||    T    |    T    |        T
---+---++--------+--------------++---------+---------+--------------------

Segundo caso: não (carro e ônibus) = (não carro) ou (não ônibus)

 c | b || c and b | not (c and b) || (not c) | (not b) | (not c) or (not b)
---+---++---------+---------------++---------+---------+--------------------
 T | T ||    T    |       F       ||    F    |    F    |        F
---+---++---------+---------------++---------+---------+--------------------
 T | F ||    F    |       T       ||    F    |    T    |        T
---+---++---------+---------------++---------+---------+--------------------
 F | T ||    F    |       T       ||    T    |    F    |        T
---+---++---------+---------------++---------+---------+--------------------
 F | F ||    F    |       T       ||    T    |    T    |        T
---+---++---------+---------------++---------+---------+--------------------

Answer 6

Desenhe um diagrama simples de Venn, dois círculos que se cruzam. Coloque A na esquerda e B na direita. Agora (A e B) é obviamente a parte que se cruzam. Portanto, não (A e B) é tudo o que não está na parte intersectora, o resto dos dois círculos. Colorir isso em.

Desenhe outros dois círculos como antes, A e B, cruzando. Agora não (a) é tudo o que está no círculo certo (b), mas não na interseção, porque isso é obviamente um e B. colorir isso. Da mesma forma não (b) é tudo no círculo esquerdo, mas não na interseção, Porque isso é B e também A. Color isso.

Dois desenhos parecem iguais. Você provou que não (a e b) = não (a) ou não (b). Outro caso é deixado como um exercício para o aluno.

Answer 7

A Lei de DeMorgan permite declarar uma série de operações lógicas de diferentes maneiras.Aplica-se à lógica e à teoria dos conjuntos, onde na teoria dos conjuntos você usa complemento para não, interseção para e e união para ou.

A Lei de DeMorgan permite simplificar uma expressão lógica, realizando uma operação bastante semelhante à propriedade distributiva da multiplicação.

Então, se você tiver o seguinte em uma linguagem semelhante a C

if !(x || y || z) { /* do something */ }

É logicamente equivalente a:

if (!x && !y && !z)

Também funciona assim:

if !(x && !y && z)

torna-se em

if (!x || y || !z)

E você pode, é claro, fazer o sentido inverso.

A equivalência dessas afirmações é fácil de ver usando algo chamado tabela verdade.Em uma tabela verdade, você simplesmente apresenta suas variáveis ​​(x, y, z) e lista todas as combinações de entradas para essas variáveis.Você então tem colunas para cada predicado ou expressão lógica e determina, para as entradas fornecidas, o valor da expressão.Qualquer currículo universitário de ciência da computação, engenharia da computação ou engenharia elétrica provavelmente deixará você maluco com o número e o tamanho das tabelas verdade que você deve construir.

Então, por que aprendê-los?Acho que o maior motivo da computação é que ela pode melhorar a legibilidade de expressões lógicas maiores.Algumas pessoas não gostam de usar lógico não ! diante das expressões, pois acham que pode confundir alguém se perder.O impacto do uso da Lei de DeMorgan no nível de porta dos chips é útil, entretanto, porque certos tipos de portas são mais rápidos, mais baratos ou você já está usando um circuito integrado completo para eles, de modo que pode reduzir o número de pacotes de chips necessários para o resultado.

Answer 8

Não sei por que mantive isso todos esses anos, mas se mostrou útil em várias ocasiões. Obrigado ao Sr. Bailey, meu professor de matemática da 10ª série. Ele chamou de teorema de Demorgan.

!(A || B) <==> (!A && !B)
!(A && B) <==> (!A || !B)

Quando você move a negação para dentro ou para fora dos colchetes, o operador lógico (e, ou, ou) muda.