regole DeMorgan spiegate

Question

La prego di spiegare le regole DeMorgan nel modo più semplice possibile (ad esempio a qualcuno con solo un matematica della scuola secondaria di fondo)?

Answer 1

Abbiamo due valori: T e F

.

Si può combinare questi valori in tre modi:. NOT, AND, e OR

NOT è il più semplice:

• NOT T = F
• NOT F = T

Possiamo scrivere questo come un tavola di verità :

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

Per la concisione

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

Pensate NOT come il complemento , che è, si trasforma un valore dentro l'altro.

AND lavora su due valori:

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

AND è T solo quando sia la argomenti (i valori di x e y nella tabella di verità) sono T -. E F altrimenti

OR è T quando almeno uno dei suoi argomenti è T:

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

Possiamo definire le combinazioni più complesse. Per esempio, possiamo scrivere una tabella di verità per x AND (y OR z), e la prima fila è sotto.

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

Una volta che sappiamo come valutare x AND (y OR z), siamo in grado di riempire il resto della tabella.

Per valutare la combinazione, valutare i pezzi e lavorare da lì. Le parentesi indicano quali parti di valutare prima. Ciò che si sa da aritmetica ordinaria vi aiuterà a lavorare fuori. Diciamo che avete 10 - (3 + 5). In primo luogo si valuta la parte tra parentesi per ottenere

10 - 8

e valutare che come al solito per ottenere la risposta, 2.

valutazione di questi espressioni funziona in modo simile. Sappiamo come funziona OR dall'alto, in modo che possiamo espandere il nostro tavolo un po ':

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

Ora è quasi come se fossimo di nuovo al tavolo x AND y. Abbiamo semplicemente sostituire il valore di y OR z e valutare. In prima fila, abbiamo

T AND (T OR T)

, che è lo stesso di

T AND T

che è semplicemente T.

ripetere lo stesso processo per tutti i possibili valori di 8 x, y e z (2 valori possibili di volte x 2 possibili valori di volte y 2 valori possibili di z) per ottenere

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

Alcune espressioni può essere più complessa di quanto hanno bisogno di essere. Ad esempio,

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

In altre parole, NOT (NOT x) è equivalente per solo x.

regole di De Morgan sono trucchi pratici che ci permettono di conversione tra espressioni equivalenti che si adattano certi schemi:

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

(Si potrebbe pensare a questo come il modo distribuisce NOT attraverso semplici espressioni AND e OR).

Il tuo buon senso probabilmente già conosce queste regole! Ad esempio, si pensi alla po 'di saggezza popolare che "non si può essere in due posti contemporaneamente." Potremmo farlo entrare la prima parte della prima regola:

NOT (here AND there)

Applicando la regola, questo è un altro modo per dire "tu non sei qui o non ci sei".

Esercizio:? Come si potrebbe esprimere la seconda regola in un inglese semplice

Per la prima regola, diamo un'occhiata alla tabella di verità per l'espressione sul lato sinistro del segno di uguale.

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

Ora il lato destro:

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

I valori finali sono gli stessi in entrambe le tabelle. Ciò dimostra che le espressioni sono equivalenti.

Esercizio:. Dimostrare che le espressioni NOT (x OR y) e (NOT x) AND (NOT y) sono equivalenti

Answer 2

Guardando oltre alcune delle risposte, credo di poter spiegare meglio utilizzando le condizioni che in realtà sono legati gli uni agli altri.

La legge di DeMorgan si riferisce al fatto che ci sono due modi identici a scrivere una qualsiasi combinazione delle due condizioni - specificamente, la combinazione AND (entrambe le condizioni devono essere vere), e la combinazione OR (uno dei due può essere vero). Esempi sono:

Parte 1 della Legge di DeMorgan

Dichiarazione:. Alice ha un fratello
Condizioni:. Alice ha un fratello OR Alice ha una sorella
Di fronte: Alice è figlio unico (non NOT ha un fratello)
. Condizioni:. Alice non NOT ha un fratello, AND lei non NOT avere una sorella

In altre parole: NOT [A OR B] = [NOT A] AND [NOT B]

Parte 2 della Legge di DeMorgan

Dichiarazione: Bob è un automobilista
. Condizioni:. Bob ha una AND macchina Bob ha una licenza
Di fronte: Bob è NOT un automobilista
. Condizioni:. Bob ha NOT avete una macchina, OR Bob ha NOT dispone di una licenza

In altre parole:. NOT [A AND B] = [NOT A] OR [NOT B]

Credo che questo sarebbe un po 'meno confusione per un 12-year-old. E 'sicuramente meno confusione di tutte queste sciocchezze su tabelle di verità (anche mi sto confuso guardando tutti quelli).

Answer 3

E 'solo un modo per ribadire dichiarazioni di verità, che possono fornire modi più semplici di scrivere condizionali per fare la stessa cosa.

In parole povere:
Quando qualcosa non è questo o quello, non è anche questo e non quello.
Quando qualcosa non è questo e quello, non è anche questo o no che.

Nota. Data l'imprecisione della lingua inglese sulla parola 'o' Io lo utilizzo per significare una licenza non esclusiva o nell'esempio precedente

Ad esempio il seguente pseudo-codice è equivalente:
Se non (A o B) ...
SE (NON A) e (B NON) ....

SE NON (A e B) ...
SE NON (A) o meno (B) ...

Answer 4

Se sei un agente di polizia in cerca di bevitori minorenni, è possibile eseguire una delle seguenti operazioni, e la legge di De Morgan dice che ammontano alla stessa cosa:

FORMULAZIONE 1 (A e B)

  

Se sono in di età   limitare e bere un alcolica   bevanda, li arresta.

FORMULAZIONE 2 (NOT (NON UNA O NON B))

  

Se sono su   il limite di età o bere un    non alcolica bevande, lasciarli andare.

Questo, tra l'altro, non è il mio esempio. Per quanto ne so, era parte di un esperimento scientifico in cui la stessa regola è stata espressa in modi diversi per scoprire quanto di una differenza ha fatto nella capacità dei popoli di capirli.

Answer 5

"Lui non ha né una macchina o un autobus." significa la stessa cosa di "Non avere una macchina, e lui non ha un bus".

"Lui non ha una macchina e un autobus." significa la stessa cosa come "Lui o non avere una macchina, o non dispone di un autobus, non sono sicuro che, forse lui ha né".

Naturalmente, in parole povere "Non ha una macchina e un autobus." ha una forte implicazione che ha almeno una di queste due cose. Ma, a rigor di termini, da un punto di vista logico la dichiarazione è anche vero, se non ha nessuno dei due.

Formalmente:

• non (auto o in bus) = (non auto) e (non bus)
• non (auto e autobus) = (non auto) o (non bus)

In inglese, 'o' tende a significare una scelta, che non si dispone di entrambe le cose. Nella logica, 'o' significa sempre la stessa 'e / o' in inglese.

Ecco una tabella di verità che mostra come funziona questo:

Primo caso: non (cor o bus) = (non auto) e (non bus)

 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
---+---++--------+--------------++---------+---------+--------------------

Secondo caso: non (auto e autobus) = (non auto) o (non bus)

 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

Disegnare un semplice diagramma di Venn, due cerchi intersecanti. Mettere A sinistra e B nel giusto. Ora (A e B) è, ovviamente, il bit si intersecano. Quindi non (A e B) è tutto ciò che non è nel bit si intersecano, il resto di entrambi i cerchi. Color che in.

Disegnare un altro due cerchi come prima, A e B, che si intersecano. Ora NOT (A) è tutto ciò che è nel cerchio a destra (B), ma non l'incrocio, perché questo è ovviamente un così come B. Colore questo. Allo stesso modo non (B) è tutto nel cerchio di sinistra, ma non l'incrocio, perché questo è B e A. Colore questo.

Due disegni hanno lo stesso aspetto. Hai dimostrato che non (A e B) = NON (A) o meno (B). T'other caso viene lasciato come esercizio per lo studente.

Answer 7

La legge di DeMorgan consente di affermare una serie di operazioni logiche in modi diversi. Si applica alla logica e teoria degli insiemi, dove in teoria degli insiemi si utilizza complemento non per, intersezione e, e l'unione a favore o.

La legge di DeMorgan consente di semplificare un'espressione logica, l'esecuzione di un'operazione che è piuttosto simile alla proprietà distributiva della moltiplicazione.

Quindi, se avete la segue in un C-come il linguaggio

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

E 'logicamente equivalente a:

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

Funziona anche in questo modo:

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

giri in

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

E si può, naturalmente, andare in senso inverso.

L'equivalenza di queste affermazioni è facile vedere con qualcosa che si chiama una tabella di verità. In una tabella di verità, è sufficiente lay out le variabili (x, y, z) ed elencare tutte le combinazioni di ingressi per queste variabili. Devi quindi colonne per ogni predicato, o espressione logica, e si determina per gli ingressi dati, il valore dell'espressione. Ogni curriculum universitario per l'informatica, ingegneria informatica, ingegneria elettrica o probabilmente vi guidare bonkers con il numero e le dimensioni delle tabelle di verità si deve costruire.

E allora perché li imparare? Credo che la ragione principale nel mondo dei computer è che può migliorare la leggibilità delle espressioni logiche più grandi. Alcune persone non come l'utilizzo di logico non ! di fronte a espressioni, come pensano si può confondere qualcuno se perdere. L'impatto della usando la legge di DeMorgan sul piano porta di chip è utile, però, perché alcuni tipi di porta sono più veloci, più economici, o si sta già utilizzando un intero circuito integrato per loro in modo da poter ridurre il numero di pacchetti di chip richiesto per la risultato.

Answer 8

Non certo perché ho portati a nuovo Tale tutti questi anni, ma si è dimostrato utile in diverse occasioni. Grazie a Mr Bailey, il mio grado 10 insegnante di matematica. Lo chiamò di DeMorgan Teorema.

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

Quando si sposta la negazione dentro o fuori delle staffe, l'operatore logico (AND, OR) cambia.