Schema elettrico, progettato per eseguire alcune operazioni logiche con i dati di input, è chiamato elemento logico. I dati di ingresso vengono qui rappresentati sotto forma di tensioni di vari livelli e anche il risultato dell'operazione logica in uscita viene ottenuto sotto forma di una tensione di un certo livello.

In questo caso vengono forniti gli operandi: all'ingresso dell'elemento logico vengono ricevuti segnali sotto forma di tensione di livello alto o basso, che servono essenzialmente come dati di ingresso. Pertanto, una tensione di alto livello - un 1 logico - indica un valore vero dell'operando e una tensione di basso livello 0 - un valore falso. 1 - VERO, 0 - FALSO.

Elemento logico- un elemento che implementa determinate relazioni logiche tra i segnali di ingresso e di uscita. Gli elementi logici vengono solitamente utilizzati per costruire circuiti logici di computer e circuiti discreti di monitoraggio e controllo automatici. Tutti i tipi di elementi logici, indipendentemente dalla loro natura fisica, sono caratterizzati da valori discreti dei segnali di ingresso e di uscita.

Gli elementi logici hanno uno o più ingressi e una o due uscite (solitamente inverse tra loro). I valori di "zero" e "uno" dei segnali di uscita degli elementi logici sono determinati dalla funzione logica eseguita dall'elemento e dai valori di "zero" e "uno" dei segnali di ingresso, che giocano il ruolo delle variabili indipendenti. Ci sono quelli basilari funzioni logiche, da cui può essere composta qualsiasi funzione logica complessa.

A seconda del design del circuito dell'elemento, sul suo parametri elettrici, livelli logici (alto e bassi livelli tensioni) ingresso e uscita hanno gli stessi valori per gli stati alto e basso (vero e falso).

Tradizionalmente, gli elementi logici vengono prodotti sotto forma di speciali componenti radio: circuiti integrati. Le operazioni logiche come congiunzione, disgiunzione, negazione e addizione del modulo (AND, OR, NOT, XOR) sono le operazioni di base eseguite sui principali tipi di porte logiche. Successivamente, esaminiamo ciascuno di questi tipi di elementi logici più da vicino.

Elemento logico "AND" - congiunzione, moltiplicazione logica, AND

"AND" è un elemento logico che esegue un'operazione di congiunzione o moltiplicazione logica sui dati di input. Questo elemento può avere da 2 a 8 (i più comuni in produzione sono gli elementi “AND” con 2, 3, 4 e 8 ingressi) ingressi e un'uscita.

Simboli di elementi logici "AND" con quantità diverse gli ingressi sono mostrati in figura. Nel testo, un elemento logico “AND” con un certo numero di ingressi è indicato come “2I”, “4I”, ecc. - un elemento “AND” con due ingressi, con quattro ingressi, ecc.

La tabella della verità per l'elemento 2I mostra che l'output dell'elemento sarà logico solo se quelli logici sono simultaneamente al primo input E al secondo input. Nei restanti tre casi possibili, l’output sarà zero.

Nei diagrammi occidentali, l'icona dell'elemento I ha una linea retta all'ingresso e una linea arrotondata all'uscita. SU schemi domestici- un rettangolo con il simbolo “&”.

Elemento logico "OR" - disgiunzione, addizione logica, OR

“OR” è un elemento logico che esegue un'operazione di disgiunzione o addizione logica sui dati di input. Come l'elemento “I”, è disponibile con due, tre, quattro, ecc. ingressi e un'uscita. Nella figura sono mostrati i simboli degli elementi logici "OR" con numeri diversi di ingressi. Questi elementi sono designati come segue: 2OR, 3OR, 4OR, ecc.

La tabella di verità per l'elemento “2OR” mostra che affinché ne compaia uno logico in uscita, è sufficiente che quello logico sia al primo ingresso OPPURE al secondo ingresso. Se ce ne sono logici su due input contemporaneamente, anche l'output sarà uno.

Nei diagrammi occidentali, l'icona dell'elemento "OR" ha un input arrotondato e un output arrotondato e appuntito. Sugli schemi domestici c'è un rettangolo con il simbolo “1”.

Elemento logico "NOT" - negazione, invertitore, NOT

"NOT" è un elemento logico che esegue un'operazione di negazione logica sui dati di input. Questo elemento, che ha un'uscita e un solo ingresso, è anche chiamato inverter, poiché di fatto inverte (inverte) il segnale di ingresso. La figura mostra simbolo elemento logico "NOT".

La tabella della verità per un inverter mostra che un potenziale di ingresso elevato produce un potenziale di uscita basso e viceversa.

Nei diagrammi occidentali, l'icona dell'elemento “NOT” ha la forma di un triangolo con un cerchio in uscita. Sugli schemi domestici c'è un rettangolo con il simbolo “1”, con un cerchio in uscita.

Elemento logico "NAND" - congiunzione (moltiplicazione logica) con negazione, NAND

“AND-NOT” è un elemento logico che esegue un'operazione di addizione logica sui dati di input, quindi un'operazione di negazione logica, il risultato viene inviato all'output. In altre parole, è fondamentalmente un elemento “AND”, completato da un elemento “NOT”. La figura mostra il simbolo dell'elemento logico “2AND-NOT”.

La tabella di verità per la porta NAND è l'opposto della tabella di verità per la porta AND. Invece di tre zeri e uno, ci sono tre uno e uno zero. L’elemento NAND è anche chiamato “elemento Schaeffer” in onore del matematico Henry Maurice Schaeffer, che per primo ne notò il significato nel 1913. Indicato come “I”, solo con un cerchio in uscita.

Elemento logico "OR-NOT" - disgiunzione (addizione logica) con negazione, NOR

“OR-NOT” è un elemento logico che esegue un'operazione di addizione logica sui dati di input, quindi un'operazione di negazione logica, il risultato viene inviato all'output. In altre parole, questo è un elemento "OR" integrato da un elemento "NOT" - un inverter. La figura mostra il simbolo dell'elemento logico “2OR-NOT”.

La tavola di verità per una porta OR è l'opposto della tavola di verità per una porta OR. Un potenziale di uscita elevato si ottiene solo in un caso: i potenziali bassi vengono applicati contemporaneamente a entrambi gli ingressi. È designato come "OR", solo con un cerchio sull'uscita che indica l'inversione.

Porta logica "OR esclusivo" - addizione modulo 2, XOR

“OR esclusivo” è un elemento logico che esegue un'operazione di addizione logica modulo 2 sui dati di input, ha due input e un output. Spesso questi elementi vengono utilizzati nei circuiti di controllo. La figura mostra il simbolo di questo elemento.

L'immagine nei circuiti occidentali è come “OR” con una striscia curva aggiuntiva sul lato ingresso, in quelli domestici è come “OR”, solo che al posto di “1” verrà scritto “=1”.

Questo elemento logico è anche chiamato “inequivalenza”. Un livello di tensione elevato sarà in uscita solo quando i segnali all'ingresso non sono uguali (uno è uno, l'altro è zero, oppure uno è zero e l'altro è uno), anche se ce ne sono due all'ingresso allo stesso tempo, l'output sarà zero: questa è la differenza da "OR". Questi elementi logici sono ampiamente utilizzati nei sommatori.

Congiunzione o moltiplicazione logica (nella teoria degli insiemi, questa è l'intersezione)

Una congiunzione è un'espressione logica complessa che è vera se e solo se entrambe le espressioni semplici sono vere. Questa situazione è possibile solo in un singolo caso; in tutti gli altri casi la congiunzione è falsa.

Notazione: &, $\wedge$, $\cdot$.

Tavola di verità per la congiunzione

Immagine 1.

Proprietà della congiunzione:

1. Se almeno una delle sottoespressioni di una congiunzione è falsa su qualche insieme di valori variabili, allora l'intera congiunzione sarà falsa per questo insieme di valori.
2. Se tutte le espressioni di una congiunzione sono vere su qualche insieme di valori variabili, allora anche l'intera congiunzione sarà vera.
3. Il significato dell'intera congiunzione di un'espressione complessa non dipende dall'ordine in cui sono scritte le sottoespressioni a cui è applicata (come la moltiplicazione in matematica).

Disgiunzione o addizione logica (nella teoria degli insiemi questa è l'unione)

Una disgiunzione è un'espressione logica complessa che è quasi sempre vera, tranne quando tutte le espressioni sono false.

Notazione: +, $\vee$.

Tavola di verità per la disgiunzione

Figura 2.

Proprietà della disgiunzione:

1. Se almeno una delle sottoespressioni della disgiunzione è vera su un certo insieme di valori variabili, allora l'intera disgiunzione assume un valore vero per questo insieme di sottoespressioni.
2. Se tutte le espressioni di qualche elenco di disgiunzioni sono false su qualche insieme di valori variabili, allora anche l'intera disgiunzione di queste espressioni è falsa.
3. Il significato dell'intera disgiunzione non dipende dall'ordine in cui sono scritte le sottoespressioni (come in matematica - addizione).

Negazione, negazione logica o inversione (nella teoria degli insiemi questa è negazione)

Negazione significa che la particella NOT o la parola FALSE viene aggiunta all'espressione logica originale, COSA e di conseguenza otteniamo che se l'espressione originale è vera, allora la negazione dell'originale sarà falsa e viceversa, se l'espressione originale è falso, allora la sua negazione sarà vera.

Notazione: non $A$, $\bar(A)$, $¬A$.

Tavola di verità per l'inversione

Figura 3.

Proprietà della negazione:

La “doppia negazione” di $¬¬A$ è una conseguenza della proposizione $A$, cioè è una tautologia nella logica formale ed è uguale al valore stesso nella logica booleana.

Implicazione o conseguenza logica

Un'implicazione è un'espressione logica complessa che è vera in tutti i casi tranne quando la verità segue la falsità. Cioè, questa operazione logica collega due semplici espressioni logiche, di cui la prima è una condizione ($A$) e la seconda ($A$) è una conseguenza della condizione ($A$).

Notazione: $\to$, $\Rightarrow$.

Tavola di verità per l'implicazione

Figura 4.

Proprietà di implicazione:

1. $A \to B = ¬A \vee B$.
2. L'implicazione $A \to B$ è falsa se $A=1$ e $B=0$.
3. Se $A=0$, allora l'implicazione $A \to B$ è vera per qualsiasi valore di $B$ (vero può seguire da falso).

Equivalenza o equivalenza logica

L'equivalenza è un'espressione logica complessa che vale per valori uguali delle variabili $A$ e $B$.

Notazione: $\leftrightarrow$, $\Leftrightarrow$, $\equiv$.

Tavola di verità per l'equivalenza

Figura 5.

Proprietà di equivalenza:

1. L'equivalenza è vera su insiemi uguali di valori delle variabili $A$ e $B$.
2. CNF $A \equiv B = (\bar(A) \vee B) \cdot (A \cdot \bar(B))$
3. DNF $A \equiv B = \bar(A) \cdot \bar(B) \vee A \cdot B$

Disgiunzione o addizione rigorosa modulo 2 (nella teoria degli insiemi, è l'unione di due insiemi senza la loro intersezione)

Una disgiunzione rigorosa è vera se i valori degli argomenti non sono uguali.

Per l'elettronica, ciò significa che la realizzazione dei circuiti è possibile utilizzando un elemento standard (sebbene si tratti di un elemento costoso).

Ordine delle operazioni logiche in un'espressione logica complessa

1. Inversione(negazione);
2. Congiunzione (moltiplicazione logica);
3. Disgiunzione e disgiunzione rigorosa (addizione logica);
4. Implicazione (conseguenza);
5. Equivalenza (identità).

Per modificare l'ordine specificato delle operazioni logiche, è necessario utilizzare le parentesi.

Proprietà generali

Per un insieme di variabili booleane $n$, esistono esattamente $2^n$ valori distinti. La tabella di verità per un'espressione logica di variabili $n$ contiene $n+1$ colonne e $2^n$ righe.

Sezioni: Informatica

Attualmente, negli esami di ammissione in informatica ci sono molti compiti sull'argomento "algebra della logica". Lo scopo di questa lezione è consolidare le capacità di risolvere i compiti dell'Esame di Stato Unificato in informatica utilizzando elementi di algebra logica.

Obiettivi della lezione:

• Formazione della capacità di applicare nella pratica le conoscenze acquisite;
• Sviluppo della capacità di costruire tavole di verità utilizzando formule date;
• Sviluppo della capacità di risolvere problemi verbali utilizzando le leggi della logica.

Obiettivi della lezione:

• Educativo – sviluppo dell’interesse cognitivo, del pensiero logico.
• Educativo– ripetizione delle basi della logica matematica, eseguendo compiti pratici.
• Sviluppo – sviluppo del pensiero logico, attenzione.

Durante le lezioni

1. Ripetizione di operazioni e leggi logiche.
2. Applicazione delle operazioni logiche e delle leggi nella pratica.
3. Spiegazione dei compiti.

Oggi stiamo finendo l'argomento "Fondamenti di logica" e applicheremo le operazioni logiche di base e le leggi di trasformazione per risolvere i compiti dell'esame di stato unificato in informatica.

La lezione si svolge parallelamente alla presentazione.<Приложение1>

1. Ripetizione di operazioni e leggi logiche.

L'algebra della logica è una branca della logica matematica che studia la struttura di affermazioni logiche complesse e metodi per stabilirne la verità utilizzando metodi algebrici.

1. Fondatore della logica formale?

Aristotele.

2. Fondatore dell'algebra della logica?

Giorgio Boole.

3. Elenca le operazioni logiche:

¬ negazione (inversione)
&, /\congiunzione (“E”)
Disgiunzione V (“OR”)
conseguenza logica (implicazione)
equivalenza (equivalenza)

4. Qual è il significato della legge della doppia negazione?

Un doppio negativo elimina il negativo.

5. Leggi di De Morgan (leggi di inversione generale).

La negazione di una disgiunzione è una congiunzione di negazioni:

¬(A V B) = ¬A /\ ¬B

La negazione di una congiunzione è una disgiunzione di negazioni:

¬(A /\B) = ¬A V ¬B

6. La legge dell'idempotenza (uguaglianza).

7. Qual è il significato della legge di esclusione del terzo?

Di due affermazioni contraddittorie sulla stessa cosa, una è sempre vera, la seconda è falsa e la terza non è data:

8. In cosa consiste il principio di contraddizione?

Un'affermazione e la sua negazione non possono essere vere allo stesso tempo:

9. Legge di esclusione delle costanti.

Per l'addizione logica:

A V 1 = 1 A V 0 = A

Per la moltiplicazione logica:

A /\ 1 = A A /\ 0 = 0

10. Come esprimere un'implicazione attraverso una disgiunzione?

A B = ¬A V B

2. Applicazione delle operazioni logiche e delle leggi nella pratica.

Esempio 1. ( Attività A11 versione demo 2004)

Per quale nome è vera l'affermazione:

¬ (La prima lettera del nome è una vocale -> La quarta lettera del nome è una consonante)?

Soluzione. Una frase complessa è composta da due frasi semplici:

A è la prima lettera del nome, vocale,

B è la quarta lettera del nome, una consonante.

¬ (A B) = ¬ (¬A V B) = (¬ (¬A) /\ ¬B) = A /\ ¬B

Formule utilizzate:

1. Implicazione attraverso la disgiunzione A? B = ¬A V B

2. Legge di De Morgan ¬(A V B) = ¬A /\ ¬B

3. La legge della doppia negazione.

(La prima lettera del nome è una vocale /\ La quarta lettera del nome è una vocale)

Esempio 2. ( Attività A12 versione demo 2004)

Quale espressione logica è equivalente all'espressione ¬ (A \/ ¬B)?

Soluzione. ¬ (A \/ ¬B)= ¬ A \/ ¬ (¬B)= ¬ A \/ B

Crea una tabella di verità per la formula

¬ (B /\ C) V (A/\C B)

L'ordine delle operazioni logiche:

¬ (B /\ C) V (A/\C B)

Crea una tabella di verità.

Quante righe ci saranno nella tua tabella? 3 variabili: A, B, C; 23=8

Quante colonne? 5 operazioni + 3 variabili = 8

UN	B	C	(AVANTI CRISTO)	¬(B/\C)	AC	(A/\C ? B)	¬ (B /\ C) V (A/\CB)
0	0	0	0	1	0	1	1
0	0	1	0	1	0	1	1
0	1	0	0	1	0	1	1
0	1	1	1	0	0	1	1
1	0	0	0	1	0	0	1
1	0	1	0	1	1	1	1
1	1	0	0	1	0	0	1
1	1	1	1	0	1	1	1

Che risposte hai ottenuto nell'ultima colonna?

identicamente vero, se assume valori 1 su tutti gli insiemi di istruzioni semplici in esso incluse. Si chiamano formule identiche vere tautologie.

Risolviamo questo esempio utilizzando il metodo analitico:

semplificare l'espressione

¬ (B /\ C) V (A/\C B)= (applicare la formula dell'implicazione)

¬ (B /\ C) V ¬ (A /\ C) V B = (applicare 1 e 2 leggi di de Morgan)

(¬B V ¬C) V (¬A V ¬C) V B = (togliere le parentesi)

¬B V ¬C V ¬A V ¬C V B= (applicare la legge commutativa)

¬B V B V ¬C V ¬C V ¬A = (legge di esclusione del mezzo, legge di idempotenza)

1 V ¬С V ¬A = 1 V ¬A = 1 (legge di esclusione delle costanti)

Risposta: 1 , significa che la formula è identicamente vera o una tautologia.

L'espressione logica viene chiamata identicamente falso, se assume valori 0 su tutti gli insiemi di istruzioni semplici in esso incluse.

(compito a casa 3)

La tabella mostra le query al server di ricerca. Disporre le designazioni delle query in ordine crescente in base al numero di pagine che il motore di ricerca troverà per ciascuna query.

Il simbolo I viene utilizzato per indicare l'operazione logica "OR" in una query e il simbolo & viene utilizzato per indicare l'operazione logica "AND".

Il primo metodo si basa sul ragionamento. Ragionando logicamente, vediamo che verranno trovate la maggior parte delle pagine per la query G, poiché quando viene eseguita, verranno trovate le pagine con la parola “laws”, le pagine con la parola “physical” e le pagine con la parola “biology”. trovato. Per la query B verrà trovato il minor numero di pagine, poiché contiene la presenza di tutte e quattro le parole nella pagina cercata. Resta da confrontare le query A e B. La query B troverà tutte le pagine corrispondenti alla query A (poiché quest'ultima contiene necessariamente la parola "leggi"), nonché le pagine contenenti entrambe le parole "fisica" e "biologia". Pertanto, verranno trovate più pagine per la query B che per la query A. Quindi, ordinando le query in ordine crescente di pagine, otteniamo VABG.

Risposta: VABG.

Il secondo metodo prevede l'utilizzo di una rappresentazione grafica delle operazioni sugli insiemi. (Vedi presentazione)

Esempio 5. ( Attività A16 versione demo 2006)

Di seguito è riportato in forma tabellare un frammento del database sui risultati dei test degli studenti (viene utilizzata una scala di cento punti)

Cognome	Pavimento	Matematica	lingua russa	Chimica	Informatica	Biologia
Aganyan	E	82	56	46	32	70
Voronin	M	43	62	45	74	23
Grigorchuk	M	54	74	68	75	83
Rodnina	E	71	63	56	82	79
Sergeenko	E	33	25	74	38	46
Cherepanova	E	18	92	83	28	61

Quanti record in questo frammento soddisfano la condizione

“Sesso=’m’ O Chimica>Biologia”?

Selezioniamo le voci: Ragazzi (due) e Chimica>Biologia (tre, ma un ragazzo, già frequentato 1 volta). Di conseguenza, 4 record soddisfano la condizione.

Compito 6. ( Attività B4 versione demo 2007)

Nel campionato scolastico di ping pong, le prime quattro erano ragazze: Natasha, Masha, Lyuda e Rita. I fan più accaniti hanno espresso le loro ipotesi sulla distribuzione dei posti in ulteriori competizioni.

Si crede che Natasha sarà la prima e Masha la seconda.

Un altro fan prevede che Luda sarà al secondo posto e Rita, secondo lui, prenderà il quarto posto.

Un terzo appassionato di tennis non era d'accordo con loro. Crede che Rita prenderà il terzo posto e Natasha la seconda.

Che posto hanno preso Natasha, Masha, Lyuda, Rita al campionato?

(Nella risposta elenca in fila, senza spazi, i numeri corrispondenti ai posti occupati dalle ragazze nell'ordine dei nomi specificato.)

Indichiamo le affermazioni:

H1 = “Natasha sarà la prima”;

M2 = “Masha sarà seconda”;

L2 = “Luda sarà seconda”;

P4 = “Rita sarà quarta”;

P3 = “Rita sarà terza”;

H2 = "Natasha sarà seconda."

Secondo la condizione:

dalle affermazioni di 1 fan ne consegue che H1VM2 è vero;

dalle dichiarazioni del tifoso2 ne consegue che A2VP4 è vero;

dalle dichiarazioni del fan 3 ne consegue che P3VH2 è vero.

Pertanto anche la congiunzione è vera

(H1VM2) /\ (L2VP4) /\ (Р3VН2) = 1.

Aprendo le parentesi otteniamo:

(Н1VM2) /\ (Л2VP4) /\ (Р3VН2) = (Н1/\Л2V Н1/\Р4 V М2/\Л2 V М2/\Р4) /\ (Р3VН2)=

Н1/\Л2/\Р3 V Н1/\Р4/\Р3 V М2/\Л2/\Р3 V М2/\Р4/\Р3 V Н1/\Л2/\Н2 V Н1/\Р4/\Н2 V М2/ \Л2/\Н2 V М2/\Р4/\Н2 =Н1/\ Л2/\Р3 V 0 V 0 V 0 V 0 V 0 V 0 V= Н1/\ Л2/\Р3

Natasha-1, Lyuda-2, Rita-3 e Masha-4.

Risposta: 1423

3. Spiegazione dei compiti.

Esercizio 1. ( Task B8 versione demo 2007)

La tabella mostra le query al server di ricerca. Disporre i simboli di query in ordine crescente in base al numero di pagine che il motore di ricerca troverà per ciascuna query.

Per denotare l'operazione logica “OR” nella query, utilizzare il simbolo |, mentre per denotare l'operazione logica “AND” – &.

Compito 2 ( Attività B4 versione demo 2008)

Prima dell'inizio del Torneo dei Quattro, i fan facevano le seguenti ipotesi sui loro idoli:

A) Max vincerà, Bill sarà secondo;

B) Bill è il terzo. Nick è il primo;

C) Max è l'ultimo e il primo è John.

Al termine della competizione, si è scoperto che ciascuno dei tifosi aveva ragione solo in una delle sue previsioni.

Che posto hanno preso John, Nick, Bill e Max nel torneo?

(Nella risposta, elenca i luoghi dei partecipanti in una riga senza spazi nell'ordine dei nomi specificato.)

PROPRIETÀ DELLE OPERAZIONI LOGICHE

1. Designazioni

1.1. Notazione per connettivi logici (operazioni):

UN) negazione(inversione, NOT logico) è indicato con ¬ (ad esempio, ¬A);

B) congiunzione(moltiplicazione logica, AND logico) è indicato con /\
(ad esempio A /\ B) oppure & (ad esempio A & B);

C) disgiunzione(addizione logica, OR logico) è indicato con \/
(ad esempio, A \/ B);

D) seguente(implicazione) è indicato con → (ad esempio, A → B);

e) identità indicato con ≡ (ad esempio, A ≡ B). L'espressione A ≡ B è vera se e solo se i valori di A e B sono uguali (o sono entrambi veri, oppure sono entrambi falsi);

f) il simbolo 1 è usato per denotare la verità (affermazione vera); simbolo 0 – per indicare una bugia (affermazione falsa).

1.2. Vengono chiamate due espressioni booleane contenenti variabili equivalente (equivalente) se i valori di queste espressioni coincidono per qualsiasi valore delle variabili. Pertanto, le espressioni A → B e (¬A) \/ B sono equivalenti, ma A /\ B e A \/ B non lo sono (i significati delle espressioni sono diversi, ad esempio, quando A = 1, B = 0 ).

1.3. Priorità delle operazioni logiche: inversione (negazione), congiunzione (moltiplicazione logica), disgiunzione (addizione logica), implicazione (seguente), identità. Pertanto, ¬A \/ B \/ C \/ D significa lo stesso di

((¬A) \/ B) \/ (C \/ D).

È possibile scrivere A \/ B \/ C invece di (A \/ B) \/ C. Lo stesso vale per la congiunzione: è possibile scrivere A /\ B /\ C invece di (A /\ B ) /\ C.

2. Proprietà

L'elenco seguente NON vuole essere completo, ma si spera sia sufficientemente rappresentativo.

2.1. Proprietà generali

1. Per una serie di N ci sono esattamente variabili logiche 2 N significati diversi. Tabella della verità per l'espressione logica da N le variabili contengono n+1 colonna e 2 N linee.

2.2.Disgiunzione

1. Se almeno una delle sottoespressioni a cui viene applicata la disgiunzione è vera per qualche insieme di valori delle variabili, allora l'intera disgiunzione è vera per questo insieme di valori.
2. Se tutte le espressioni di un certo elenco sono vere su un certo insieme di valori variabili, allora anche la disgiunzione di queste espressioni è vera.
3. Se tutte le espressioni di un certo elenco sono false su un certo insieme di valori variabili, anche la disgiunzione di queste espressioni è falsa.
4. Il significato di una disgiunzione non dipende dall'ordine di scrittura delle sottoespressioni a cui è applicata.

2.3. Congiunzione

1. Se almeno una delle sottoespressioni a cui viene applicata la congiunzione è falsa su qualche insieme di valori variabili, allora l'intera congiunzione è falsa per questo insieme di valori.
2. Se tutte le espressioni di un certo elenco sono vere su un certo insieme di valori variabili, allora anche la congiunzione di queste espressioni è vera.
3. Se tutte le espressioni di un certo elenco sono false su un certo insieme di valori variabili, anche la congiunzione di queste espressioni è falsa.
4. Il significato di una congiunzione non dipende dall'ordine di scrittura delle sottoespressioni a cui è applicata.

2.4. Disgiunzioni e congiunzioni semplici

Chiamiamo (per comodità) congiunzione semplice, se le sottoespressioni a cui è applicata la congiunzione sono variabili distinte o loro negazioni. Allo stesso modo, viene chiamata la disgiunzione semplice, se le sottoespressioni a cui si applica la disgiunzione sono variabili distinte o loro negazioni.

1. Una congiunzione semplice vale 1 (vero) esattamente su un insieme di valori variabili.
2. Una disgiunzione semplice restituisce 0 (falso) esattamente su un insieme di valori variabili.

2.5. Coinvolgimento

1. Coinvolgimento UN →B equivale alla disgiunzione (¬ A)\/B. Questa disgiunzione può anche essere scritta come segue: ¬ A\/B.
2. Coinvolgimento UN →B assume il valore 0 (falso) solo se A=1 E B=0. Se A=0, poi l'implicazione UN →B vero per qualsiasi valore B.

Per ricerca rapida le informazioni su Internet vengono utilizzate dalle query di ricerca. Una query di ricerca è un insieme parole chiave, collegati dai segni delle operazioni logiche AND, OR, NOT.

La priorità delle operazioni, se non sono presenti parentesi appositamente posizionate, è la seguente: prima NOT, poi AND, poi OR.

È necessario comprendere che l'operazione AND (adempimento simultaneo delle condizioni) riduce il volume del risultato ottenuto e l'operazione OR (adempimento di almeno una delle condizioni) al contrario aumenta il volume.

Se la richiesta contiene una frase tra virgolette, il sistema cercherà esattamente quella frase nella sua interezza.

1. Disposizione delle query in ordine crescente (discendente).

L'operazione “AND” (&) denota la presenza contemporanea di parole chiave nei documenti cercati, e quindi riduce la quantità di informazioni trovate. Più parole chiave vengono collegate utilizzando l'operazione “AND”, meno informazioni vengono trovate. Al contrario, l'operazione “OR” (|) indica la presenza di almeno una parola chiave nei documenti cercati, e quindi aumenta la quantità di informazioni trovate.

Esempio 1.

La tabella mostra le query al server di ricerca. Disporre i simboli di query in ordine crescente in base al numero di pagine che il motore di ricerca troverà per ciascuna query.

A) astratto | matematica | Gauss
B) astratto | matematica | Gauss | metodo
B) astratto | matematica
D) astratto, matematica e Gauss

Soluzione:

In base alla richiesta verrà selezionato il numero più piccolo di pagine il numero più grande Operazioni “AND” (query D), Il maggior numero di pagine verrà selezionato per la richiesta con il maggior numero di operazioni “OR” (query B). Verranno selezionate più pagine per la query A che per la query B, perché La query A contiene più parole chiave OR.

Risposta: GWAB

2. Conteggio delle pagine trovate su richiesta

Questo tipo di problema viene solitamente risolto mediante un sistema di equazioni. Suggerirò un modo più visivo e più semplice.

Il principio di selezione delle informazioni in base alle query di ricerca è ben illustrato dal diagramma di Eulero-Venn (cerchi di Eulero). Nel diagramma gli insiemi sono rappresentati da cerchi che si intersecano. L'operazione AND (&) è l'intersezione dei cerchi, mentre l'operazione OR (|) è l'unione dei cerchi.

Ad esempio, denotiamo i set Mele, Pere, Banane con cerchi. La query Mele & Pere & Banane selezionerà l'intersezione (parte comune) di tutti e tre i cerchi:

Su richiesta Mele | Le pere verranno selezionate combinando due cerchi:

Esempio 2.

La tabella mostra le query e il numero di pagine che il motore di ricerca ha trovato per queste query in un determinato segmento di Internet:

Quante pagine (in migliaia) verranno trovate per la query scacchi?

Soluzione:

Disegniamo un diagramma di Eulero-Venn. Il metodo per risolvere il problema consiste nel contare il numero di pagine corrispondenti a ciascuna area delimitata da linee:

La query scacchi e tennis corrisponde all'area centrale (1.000 mila pagine), mentre la query tennis corrisponde all'intero cerchio destro (5.500 mila pagine).

Quindi il “cerchio tagliato” destro è 5500-1000=4500:

Richiedi scacchi | tennis entrambi i cerchi corrispondono (7770), quindi il “cerchio tagliato” di sinistra è 7770-5500=2270