Risolvere equazioni logiche in matematica. Risoluzione di equazioni logiche

Scopo del servizio. Il calcolatore online è progettato per costruzione di una tavola di verità per un'espressione logica.
Tabella della verità: una tabella contenente tutte le possibili combinazioni di variabili di input e i loro corrispondenti valori di output.
La tabella della verità contiene 2n righe, dove n è il numero di variabili di input e n+m sono colonne, dove m sono variabili di output.

Istruzioni. Quando si accede dalla tastiera, utilizzare le seguenti convenzioni:

Espressione booleana:

Derivazione di tabelle intermedie per la tabella di verità
Costruzione dell'SKNF
Costruzione dell'SDNF
Costruzione del polinomio di Zhegalkin
Costruzione della mappa Veitch-Karnaugh
Minimizzare una funzione booleana

Ad esempio, l'espressione logica abc+ab~c+a~bc deve essere inserita in questo modo: a*b*c+a*b=c+a=b*c
Per inserire i dati sotto forma di diagramma logico, utilizzare questo servizio.

Regole per l'immissione di una funzione logica

1. Invece del simbolo v (disgiunzione, OR), usa il segno +.
2. Non è necessario specificare una designazione di funzione prima di una funzione logica. Ad esempio, invece di F(x,y)=(x|y)=(x^y) devi semplicemente inserire (x|y)=(x^y) .
3. Il numero massimo di variabili è 10.

La progettazione e l'analisi dei circuiti logici del computer vengono eseguite utilizzando un ramo speciale della matematica: l'algebra logica. Nell'algebra della logica si possono distinguere tre funzioni logiche principali: “NOT” (negazione), “AND” (congiunzione), “OR” (disgiunzione).
Per creare qualsiasi dispositivo logico, è necessario determinare la dipendenza di ciascuna variabile di uscita dalle variabili di ingresso esistenti; questa dipendenza è chiamata funzione di commutazione o funzione di algebra logica.
Una funzione di algebra logica si dice completamente definita se sono dati tutti e 2n i suoi valori, dove n è il numero di variabili di output.
Se non tutti i valori sono definiti, la funzione viene detta parzialmente definita.
Un dispositivo è detto logico se il suo stato è descritto utilizzando una funzione di algebra logica.
I seguenti metodi vengono utilizzati per rappresentare una funzione algebra logica:
In forma algebrica, puoi costruire un circuito di un dispositivo logico utilizzando elementi logici.


Figura 1 - Schema del dispositivo logico

Tutte le operazioni dell'algebra della logica sono definite tavole di verità valori. La tabella della verità determina il risultato di un'operazione per tutti sono possibili x valori logici delle dichiarazioni originali. Il numero di opzioni che riflettono il risultato dell'applicazione delle operazioni dipenderà dal numero di istruzioni nell'espressione logica. Se il numero di istruzioni in un'espressione logica è N, allora la tabella di verità conterrà 2 N righe, poiché ci sono 2 N combinazioni diverse di possibili valori degli argomenti.

Operazione NOT - negazione logica (inversione)

Un'operazione logica NON viene applicata ad un singolo argomento, che può essere un'espressione logica semplice o complessa. Il risultato dell'operazione NON è il seguente:

• se l'espressione originale è vera, allora il risultato della sua negazione sarà falso;
• se l'espressione originale è falsa, allora il risultato della sua negazione sarà vero.

Per l'operazione di negazione NON sono accettate le seguenti convenzioni:
non A, Â, non A, ¬A, !A
Il risultato dell'operazione di negazione NON è determinato dalla seguente tabella di verità:

UN	non A
0	1
1	0

Il risultato dell'operazione di negazione è vero quando l'affermazione originale è falsa e viceversa.

Operazione OR - addizione logica (disgiunzione, unione)

L'operazione logica OR esegue la funzione di combinare due istruzioni, che possono essere un'espressione logica semplice o complessa. Le istruzioni che costituiscono il punto di partenza di un'operazione logica sono chiamate argomenti. Il risultato dell'operazione OR è un'espressione che sarà vera se e solo se almeno una delle espressioni originali è vera.
Denominazioni utilizzate: A o B, A V B, A o B, A||B.
Il risultato dell'operazione OR è determinato dalla seguente tabella di verità:
Il risultato dell'operazione OR è vero quando A è vero, o B è vero, o sia A che B sono veri, e falso quando gli argomenti A e B sono falsi.

Operazione AND - moltiplicazione logica (congiunzione)

L'operazione logica AND svolge la funzione di intersezione di due affermazioni (argomenti), che possono essere un'espressione logica semplice o complessa. Il risultato dell'operazione AND è un'espressione che sarà vera se e solo se entrambe le espressioni originali sono vere.
Denominazioni utilizzate: A e B, A Λ B, A & B, A e B.
Il risultato dell'operazione AND è determinato dalla seguente tabella di verità:

UN	B	A e B
0	0	0
0	1	0
1	0	0
1	1	1

Il risultato dell'operazione AND è vero se e solo se le affermazioni A e B sono entrambe vere e false in tutti gli altri casi.

Operazione “IF-THEN” - conseguenza logica (implicazione)

Questa operazione collega due semplici espressioni logiche, di cui la prima è una condizione e la seconda è una conseguenza di questa condizione.
Denominazioni utilizzate:
se A, allora B; A implica B; se A allora B; A→B.
Tavola della verità:

UN	B	A→B
0	0	1
0	1	1
1	0	0
1	1	1

Il risultato dell'operazione di implicazione è falso solo se la premessa A è vera e la conclusione B (conseguenza) è falsa.

Operazione “A se e solo se B” (equivalenza, equivalenza)

Designazione utilizzata: A ↔ B, A ~ B.
Tavola della verità:

UN	B	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

Operazione “Addizione modulo 2” (XOR, disgiunzione esclusiva o stretta)

Notazione utilizzata: A XOR B, A ⊕ B.
Tavola della verità:

UN	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Il risultato dell'operazione di equivalenza è vero solo se A e B sono contemporaneamente veri o falsi.

Priorità delle operazioni logiche

• Azioni tra parentesi
• Inversione
• Congiunzione (&)
• Disgiunzione (V), OR esclusivo (XOR), somma modulo 2
• Implicazione (→)
• Equivalenza (↔)

Forma normale disgiuntiva perfetta

Forma normale disgiuntiva perfetta di una formula(SDNF) è una formula equivalente, che è una disgiunzione di congiunzioni elementari e ha le seguenti proprietà:

1. Ogni termine logico della formula contiene tutte le variabili incluse nella funzione F(x 1,x 2,...x n).
2. Tutti i termini logici della formula sono diversi.
3. Nessun termine logico contiene una variabile e la sua negazione.
4. Nessun termine logico in una formula contiene la stessa variabile due volte.

L'SDNF può essere ottenuto utilizzando tabelle di verità o utilizzando trasformazioni equivalenti.
Per ciascuna funzione, SDNF e SCNF sono definiti in modo univoco fino alla permutazione.

Forma normale congiuntiva perfetta

Forma normale congiuntiva perfetta di una formula (SCNF) Questa è una formula ad essa equivalente, che è una congiunzione di disgiunzioni elementari e soddisfa le proprietà:

1. Tutte le disgiunzioni elementari contengono tutte le variabili incluse nella funzione F(x 1 ,x 2 ,...x n).
2. Tutte le disgiunzioni elementari sono diverse.
3. Ogni disgiunzione elementare contiene una variabile una volta.
4. Nessuna disgiunzione elementare contiene una variabile e la sua negazione.

Metodi per la risoluzione di sistemi di equazioni logiche

Kirgizova E.V., Nemkova A.E.

Istituto pedagogico di Lesosibirsk –

filiale dell'Università Federale Siberiana, Russia

La capacità di pensare in modo coerente, ragionare in modo convincente, costruire ipotesi e confutare conclusioni negative non viene da sola; questa abilità è sviluppata dalla scienza della logica. La logica è una scienza che studia metodi per stabilire la verità o la falsità di alcune affermazioni sulla base della verità o falsità di altre affermazioni.

Padroneggiare le basi di questa scienza è impossibile senza risolvere problemi logici. La verifica dello sviluppo delle competenze per applicare le proprie conoscenze in una nuova situazione viene effettuata attraverso il passaggio. In particolare, questa è la capacità di risolvere problemi logici. I compiti B15 nell'Esame di Stato Unificato sono compiti di maggiore complessità, poiché contengono sistemi di equazioni logiche. Esistono vari modi per risolvere sistemi di equazioni logiche. Questa è la riduzione a un'equazione, la costruzione di una tabella di verità, la scomposizione, la soluzione sequenziale di equazioni, ecc.

Compito:Risolvere un sistema di equazioni logiche:

Consideriamo metodo di riduzione a un'equazione . Questo metodo prevede la trasformazione delle equazioni logiche in modo che i loro lati destri siano uguali al valore di verità (cioè 1). Per fare ciò, utilizzare l'operazione di negazione logica. Quindi, se le equazioni contengono operazioni logiche complesse, le sostituiamo con quelle basilari: “AND”, “OR”, “NOT”. Il passo successivo è combinare le equazioni in una sola, equivalente al sistema, utilizzando l'operazione logica “AND”. Successivamente, dovresti trasformare l'equazione risultante in base alle leggi dell'algebra logica e ottenere una soluzione specifica per il sistema.

Soluzione 1:Applicare l'inversione a entrambi i membri della prima equazione:

Immaginiamo l’implicazione attraverso le operazioni basilari “OR” e “NOT”:

Poiché i membri a sinistra delle equazioni sono uguali a 1, possiamo combinarli utilizzando l'operazione "AND" in un'equazione equivalente al sistema originale:

Apriamo la prima parentesi secondo la legge di De Morgan e trasformiamo il risultato ottenuto:

L'equazione risultante ha una soluzione: A= 0, B = 0 e C = 1.

Il metodo successivo è costruzione di tavole di verità . Poiché le quantità logiche hanno solo due valori, puoi semplicemente esaminare tutte le opzioni e trovare tra queste quelle per le quali è soddisfatto un dato sistema di equazioni. Cioè, costruiamo una tabella di verità comune per tutte le equazioni del sistema e troviamo una linea con i valori richiesti.

Soluzione 2:Creiamo una tabella di verità per il sistema:

0	0	1	1	0	1

La riga per la quale sono soddisfatte le condizioni dell'attività è evidenziata in grassetto. Quindi A = 0, B = 0 e C = 1.

Modo decomposizione . L'idea è di fissare il valore di una delle variabili (impostarla uguale a 0 o 1) e quindi semplificare le equazioni. Quindi puoi correggere il valore della seconda variabile e così via.

Soluzione 3: Permettere A = 0, quindi:

Dalla prima equazione otteniamo B =0, e dalla seconda – C=1. Soluzione del sistema: A = 0, B = 0 e C = 1.

Puoi anche usare il metodo soluzione sequenziale di equazioni , ad ogni passo aggiungendo una variabile all'insieme in esame. Per fare ciò è necessario trasformare le equazioni in modo che le variabili vengano inserite in ordine alfabetico. Successivamente, costruiamo un albero decisionale, aggiungendovi variabili in sequenza.

La prima equazione del sistema dipende solo da A e B, mentre la seconda equazione da A e C. La variabile A può assumere 2 valori 0 e 1:

Dalla prima equazione segue questo , cosi quando A = 0 e otteniamo B = 0, e per A = 1 abbiamo B = 1. Quindi la prima equazione ha due soluzioni rispetto alle variabili A e B.

Descriviamo la seconda equazione, dalla quale determiniamo i valori di C per ciascuna opzione. Quando A = 1 l'implicazione non può essere falsa, cioè il secondo ramo dell'albero non ha soluzione. A A= 0 otteniamo l'unica soluzione C= 1 :

Abbiamo così ottenuto la soluzione del sistema: A = 0, B = 0 e C = 1.

Nell'Esame di Stato Unificato di Informatica, molto spesso è necessario determinare il numero di soluzioni di un sistema di equazioni logiche, senza trovare le soluzioni stesse; esistono anche alcuni metodi per questo. Il modo principale per trovare il numero di soluzioni di un sistema di equazioni logiche è sostituzione delle variabili. Innanzitutto, è necessario semplificare il più possibile ciascuna delle equazioni in base alle leggi dell'algebra logica, quindi sostituire le parti complesse delle equazioni con nuove variabili e determinare il numero di soluzioni per il nuovo sistema. Successivamente, torna alla sostituzione e determina il numero di soluzioni per essa.

Compito:Quante soluzioni ha l'equazione ( A → B ) + (C → D ) = 1? Dove A, B, C, D sono variabili logiche.

Soluzione:Introduciamo nuove variabili: X = A → B e Y = C → D . Tenendo conto delle nuove variabili, l’equazione verrà scritta come: X + Y = 1.

La disgiunzione è vera in tre casi: (0;1), (1;0) e (1;1), mentre X e Y è un'implicazione, cioè è vera in tre casi e falsa in uno. Pertanto il caso (0;1) corrisponderà a tre possibili combinazioni di parametri. Caso (1;1) – corrisponderà a nove possibili combinazioni di parametri dell'equazione originale. Ciò significa che le possibili soluzioni totali di questa equazione sono 3+9=15.

Il prossimo modo per determinare il numero di soluzioni di un sistema di equazioni logiche è albero binario. Diamo un'occhiata a questo metodo utilizzando un esempio.

Compito:Quante soluzioni diverse ha il sistema di equazioni logiche:

Il sistema di equazioni dato è equivalente all'equazione:

( X 1 → X 2 )*( X 2 → X 3 )*…*( x m -1 → x m) = 1.

Facciamo finta cheX 1 – è vero, allora dalla prima equazione otteniamo quelloX 2 anche vero, dal secondo -X 3 =1 e così via fino a x m= 1. Quindi l'insieme (1; 1; …; 1) di M unità è la soluzione del sistema. Lascialo adessoX 1 =0, quindi dalla prima equazione abbiamoX 2 =0 o X 2 =1.

Quando X 2 vero, otteniamo che anche le restanti variabili sono vere, cioè l'insieme (0; 1; ...; 1) è una soluzione del sistema. AX 2 =0 abbiamo capito X 3 =0 o X 3 =, e così via. Proseguendo con l'ultima variabile, troviamo che le soluzioni dell'equazione sono i seguenti insiemi di variabili ( M +1 soluzione, in ciascuna soluzione M valori variabili):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Questo approccio è ben illustrato costruendo un albero binario. Il numero di soluzioni possibili è il numero di rami diversi dell'albero costruito. È facile vedere che è uguale m+1.

Variabili	Albero	Numero di soluzioni
x1
x2
x3

In caso di difficoltà nel ragionamento e nella costruzione di un albero decisionale, puoi cercare una soluzione utilizzando tavole di verità, per una o due equazioni.

Riscriviamo il sistema di equazioni nella forma:

E creiamo una tabella di verità separatamente per un'equazione:

x1	x2	(x1→x2)

Creiamo una tabella di verità per due equazioni:

x1	x2	x3	x1→x2	x2→x3	(x1→x2) * (x2→x3)

Successivamente, puoi vedere che un'equazione è vera nei seguenti tre casi: (0; 0), (0; 1), (1; 1). Un sistema di due equazioni è vero in quattro casi (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). In questo caso è subito chiaro che esiste una soluzione composta solo da zeri e altro ancora M soluzioni in cui viene aggiunta un'unità alla volta, partendo dall'ultima posizione fino a riempire tutti i posti possibili. Si può presumere che la soluzione generale avrà la stessa forma, ma affinché tale approccio diventi una soluzione è necessaria la prova che l'ipotesi sia corretta.

Per riassumere tutto quanto sopra, vorrei attirare la vostra attenzione sul fatto che non tutti i metodi discussi sono universali. Quando si risolve ciascun sistema di equazioni logiche, si dovrebbe tener conto delle sue caratteristiche, sulla base delle quali scegliere il metodo di soluzione.

Letteratura:

1. Problemi logici / O.B. Bogomolov – 2a ed. – M.: BINOM. Laboratorio della Conoscenza, 2006. – 271 p.: ill.

2. Polyakov K.Yu. Sistemi di equazioni logiche / Giornale didattico e metodologico per insegnanti di informatica: Informatica n. 14, 2011.

Metodi per la risoluzione di sistemi di equazioni logiche

Puoi risolvere un sistema di equazioni logiche, ad esempio, utilizzando una tabella di verità (se il numero di variabili non è troppo grande) o utilizzando un albero decisionale, dopo aver prima semplificato ciascuna equazione.

1. Metodo di sostituzione delle variabili.

L'introduzione di nuove variabili consente di semplificare il sistema di equazioni, riducendo il numero di incognite.Le nuove variabili devono essere indipendenti l'una dall'altra. Dopo aver risolto il sistema semplificato, dobbiamo tornare alle variabili originali.

Consideriamo l'applicazione di questo metodo utilizzando un esempio specifico.

Esempio.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Soluzione:

Introduciamo nuove variabili: A=(X1≡X2); B=(X3 ≡ X4); á=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Attenzione! Ognuna delle variabili x1, x2, ..., x10 deve essere inclusa in una sola delle nuove variabili A, B, C, D, E, cioè le nuove variabili sono indipendenti l'una dall'altra).

Quindi il sistema di equazioni sarà simile a questo:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Costruiamo un albero decisionale per il sistema risultante:

Considera l'equazione A=0, cioè (X1≡ X2)=0. Ha 2 radici:

		X1 ≡ X2

Dalla stessa tabella si vede che anche l'equazione A=1 ha 2 radici. Organizziamo il numero di radici sull'albero decisionale:

Per trovare il numero di soluzioni di un ramo, devi moltiplicare il numero di soluzioni ad ogni livello. Il ramo sinistro ne ha 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 soluzioni; anche il ramo destro ha 32 soluzioni. Quelli. l'intero sistema ha 32+32=64 soluzioni.

Risposta: 64.

2. Metodo di ragionamento.

La difficoltà di risolvere sistemi di equazioni logiche risiede nell'ingombro di un albero decisionale completo. Il metodo del ragionamento permette di non costruire l'intero albero, ma di capire quanti rami avrà. Diamo un'occhiata a questo metodo utilizzando esempi specifici.

Esempio 1. Quanti diversi insiemi di valori delle variabili logiche x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 esistono che soddisfano tutte le condizioni elencate di seguito?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

x1\/y1 =1

Non è necessario che la risposta elenchi tutti i diversi insiemi di valori delle variabili x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 per i quali questo sistema di uguaglianze è soddisfatto. Come risposta, è necessario indicare il numero di tali set.

Soluzione:

La prima e la seconda equazione contengono variabili indipendenti correlate dalla terza condizione. Costruiamo un albero delle soluzioni per la prima e la seconda equazione.

Per rappresentare un albero delle soluzioni per un sistema della prima e della seconda equazione, ciascun ramo del primo albero deve essere continuato con un albero delle variabili A . L'albero costruito in questo modo conterrà 36 rami. Alcuni di questi rami non soddisfano la terza equazione del sistema. Segniamo il numero di rami dell'albero sul primo albero"y" , che soddisfano la terza equazione:

Spieghiamo: per soddisfare la terza condizione, quando x1=0 deve esserci y1=1, cioè tutti i rami dell'albero"X" , dove x1=0 può essere continuato con un solo ramo dell'albero"y" . E solo per un ramo dell'albero"X" (a destra) tutti i rami dell'albero si adattano"y". Pertanto, l'albero completo dell'intero sistema contiene 11 rami. Ogni ramo rappresenta una soluzione al sistema di equazioni originale. Ciò significa che l'intero sistema ha 11 soluzioni.

Risposta: 11.

Esempio 2. Quante soluzioni diverse ha il sistema di equazioni?

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1

(X1 ≡ X10) = 0

dove x1, x2, …, x10 sono variabili logiche? Non è necessario che la risposta elenchi tutti i diversi insiemi di valori variabili per i quali vale questa uguaglianza. Come risposta, è necessario indicare il numero di tali set.

Soluzione: Semplifichiamo il sistema. Costruiamo una tabella di verità per parte della prima equazione:

		X1 ∧ X10	¬X1 ∧ ¬X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)

Presta attenzione all'ultima colonna, corrisponde al risultato dell'azione X1 ≡ X10.

X1 ≡ X10

Dopo la semplificazione otteniamo:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Consideriamo l'ultima equazione:(X1 ≡ X10) = 0, cioè x1 non dovrebbe coincidere con x10. Affinché la prima equazione sia uguale a 1, l'uguaglianza deve essere vera(X1 ≡ X2)=1, cioè x1 deve corrispondere a x2.

Costruiamo un albero delle soluzioni per la prima equazione:

Consideriamo la seconda equazione: per x10=1 e per x2=0 la parentesideve essere uguale a 1 (cioè x2 coincide con x3); per x10=0 e per x2=1 parentesi(X2 ≡ X10)=0, che significa la parentesi (X2 ≡ X3) dovrebbe essere uguale a 1 (cioè x2 coincide con x3):

Ragionando in questo modo, costruiamo un albero decisionale per tutte le equazioni:

Pertanto, il sistema di equazioni ha solo 2 soluzioni.

Risposta: 2.

Esempio 3.

Quanti diversi insiemi di valori delle variabili logiche x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 esistono che soddisfano tutte le condizioni elencate di seguito?

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Soluzione:

Costruiamo un albero delle soluzioni per la prima equazione:

Consideriamo la seconda equazione:

• Quando x1=0 : la seconda e la terza parentesi saranno pari a 0; affinché la prima parentesi sia uguale a 1, y1=1, z1=1 (cioè in questo caso - 1 soluzione)
• Quando x1=1 : la prima parentesi sarà pari a 0; secondo O la terza parentesi deve essere uguale a 1; la seconda parentesi sarà pari a 1 quando y1=0 e z1=1; la terza parentesi sarà uguale a 1 quando y1=1 e z1=0 (cioè in questo caso - 2 soluzioni).

Allo stesso modo per le restanti equazioni. Notiamo il numero risultante di soluzioni per ciascun nodo dell'albero:

Per scoprire il numero di soluzioni per ciascun ramo, moltiplica i numeri risultanti separatamente per ciascun ramo (da sinistra a destra).

1 ramo: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 soluzione

Ramo 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 soluzioni

3° ramo: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 soluzioni

4° ramo: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 soluzioni

5° ramo: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 soluzioni

Sommiamo i numeri risultanti: ci sono 31 soluzioni in totale.

Risposta: 31.

3. Aumento naturale del numero di radici

In alcuni sistemi, il numero di radici dell'equazione successiva dipende dal numero di radici dell'equazione precedente.

Esempio 1. Quanti diversi insiemi di valori delle variabili logiche x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 esistono che soddisfano tutte le condizioni elencate di seguito?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Semplifichiamo prima equazione:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Quindi il sistema assumerà la forma:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

Eccetera.

Ogni equazione successiva ha 2 radici in più rispetto alla precedente.

L'equazione 4 ha 12 radici;

L'equazione 5 ha 14 radici

L'equazione 8 ha 20 radici.

Risposta: 20 radici.

A volte il numero delle radici cresce secondo la legge di Fibonacci.

Risolvere un sistema di equazioni logiche richiede un approccio creativo.

Argomento della lezione: Risoluzione di equazioni logiche

Educativo – studiare metodi per risolvere equazioni logiche, sviluppare abilità nella risoluzione di equazioni logiche e costruire un'espressione logica utilizzando una tabella di verità;

Sviluppo - creare condizioni per lo sviluppo dell'interesse cognitivo degli studenti, promuovere lo sviluppo della memoria, dell'attenzione e del pensiero logico;

Educativo : promuovere la capacità di ascoltare le opinioni degli altri, coltivare la volontà e la perseveranza per raggiungere i risultati finali.

Tipo di lezione: lezione combinata

Attrezzatura: computer, proiettore multimediale, presentazione 6.

Durante le lezioni

Ripetizione e aggiornamento delle conoscenze di base. Controllo dei compiti (10 minuti)

Nelle lezioni precedenti abbiamo conosciuto le leggi fondamentali dell'algebra logica e abbiamo imparato a utilizzare queste leggi per semplificare le espressioni logiche.

Controlliamo i nostri compiti sulla semplificazione delle espressioni logiche:

1. Quale delle seguenti parole soddisfa la condizione logica:

(consonante della prima lettera→consonante della seconda lettera)٨ (ultima lettera vocale → penultima lettera vocale)? Se sono presenti più parole simili, indicare la più piccola.

1) ANNA 2) MARIA 3) OLEG 4) STEPAN

Introduciamo la seguente notazione:

A – consonante della prima lettera

B – consonante della seconda lettera

S – vocale dell'ultima lettera

D – penultima vocale

Facciamo un'espressione:

Facciamo una tabella:

2. Indicare quale espressione logica è equivalente all'espressione

Semplifichiamo la registrazione dell'espressione originale e delle opzioni proposte:

3. Dato un frammento della tavola di verità dell'espressione F:

Quale espressione corrisponde a F?

Determiniamo i valori di queste espressioni per i valori specificati degli argomenti:

Introduzione all'argomento della lezione, presentazione di nuovo materiale (30 minuti)

Continuiamo a studiare le basi della logica e l'argomento della nostra lezione di oggi è "Risolvere equazioni logiche". Dopo aver studiato questo argomento, imparerai i metodi di base per risolvere le equazioni logiche, acquisirai le competenze per risolvere queste equazioni utilizzando il linguaggio dell'algebra logica e la capacità di comporre un'espressione logica utilizzando una tabella di verità.

1. Risolvi un'equazione logica

(¬K M) → (¬L M N) = 0

Scrivi la tua risposta come una stringa di quattro caratteri: i valori delle variabili K, L, M e N (in quest'ordine). Quindi, ad esempio, la riga 1101 corrisponde al fatto che K=1, L=1, M=0, N=1.

Soluzione:

Trasformiamo l'espressione(¬K  M) → (¬L  M  N)

Un'espressione è falsa quando entrambi i termini sono falsi. Il secondo termine è uguale a 0 se M =0, N =0, L =1. Nel primo termine K = 0, poiché M = 0, e
.

Risposta: 0100

2. Quante soluzioni ha l'equazione (nella risposta indica solo il numero)?

Soluzione: trasformare l'espressione

(A+B)*(C+D)=1

A+B=1 e C+D=1

Metodo 2: elaborazione di una tavola di verità

3 vie: costruzione di una SDNF - una forma normale disgiuntiva perfetta per una funzione - una disgiunzione di congiunzioni elementari regolari complete.

Trasformiamo l'espressione originale, apriamo le parentesi in modo da ottenere la disgiunzione delle congiunzioni:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Integriamo le congiunzioni per completare le congiunzioni (il prodotto di tutti gli argomenti), apriamo le parentesi:

Prendiamo in considerazione le stesse congiunzioni:

Di conseguenza, otteniamo un SDNF contenente 9 congiunzioni. Pertanto, la tabella della verità per questa funzione ha il valore 1 in 9 righe di 2 4 =16 insiemi di valori variabili.

3. Quante soluzioni ha l'equazione (nella risposta indica solo il numero)?

Semplifichiamo l'espressione:

,

3 vie: costruzione della SDNF

Prendiamo in considerazione le stesse congiunzioni:

Di conseguenza, otteniamo un SDNF contenente 5 congiunzioni. Pertanto, la tabella della verità per questa funzione ha il valore 1 su 5 righe di 2 4 =16 insiemi di valori variabili.

Costruire un'espressione logica utilizzando una tabella di verità:

per ogni riga della tabella di verità contenente 1, componiamo un prodotto di argomenti, e le variabili uguali a 0 sono incluse nel prodotto con negazione, e le variabili uguali a 1 sono incluse senza negazione. L'espressione desiderata F sarà composta dalla somma dei prodotti risultanti. Quindi, se possibile, questa espressione dovrebbe essere semplificata.

Esempio: viene fornita la tabella di verità di un'espressione. Costruisci un'espressione logica.

Soluzione:

3. Compiti a casa (5 minuti)

Risolvi l'equazione:

Quante soluzioni ha l'equazione (indica solo il numero nella risposta)?

Utilizzando una data tabella di verità, costruisci un'espressione logica e

semplificarlo.

Alla fine dell’anno si è scoperto che solo una delle tre ipotesi era vera. Quali divisioni hanno realizzato un profitto alla fine dell’anno?

Soluzione. Scriviamo le ipotesi dalle condizioni problematiche sotto forma di affermazioni logiche: “Ricevere un profitto per divisione B non è una condizione necessaria per ottenere

profitto per divisione A ":F 1 (A, B, C) = A → B

“Ottenere un profitto da almeno una divisione B e C non è sufficiente perché la divisione A realizzi un profitto”: F 2 (A, B, C) = (B + C) → A

“Le divisioni A e B non realizzeranno profitti contemporaneamente”: F 3 (A, B, C) = A B

Dalla condizione si sa che solo una delle tre ipotesi è vera. Ciò significa che dobbiamo trovare quale delle seguenti tre espressioni logiche non è identicamente falsa:

1) FA 1F 2F 3

2) FA 1F 2F 3

3) F1F2F3

1) (A→ B) ((B+ C) → A) (A↔ B) = A B(B C+ A) (A B+ A B) = 0

2) (A→ B) ((B+ C) → A) (A↔ B) = (A+ B) (A B+ A C) (A B+ A B) = A B C

3) (A→ B) ((B+ C) → A) (A B) = (A+ B) (B C+ A) (A B+ A B) = 0

Di conseguenza, alla fine dell'anno, la seconda ipotesi si è rivelata vera, mentre la prima e la terza erano false.

									A=0
	F1 FA2 FA3 = LA B DO= 1
									se e solo se B = 0.
									C=1

Pertanto, la divisione C riceverà un profitto, ma le divisioni A e B non riceveranno alcun profitto.

Risoluzione di equazioni logiche

Nei testi di verifica centralizzata statale c'è un compito (A8), che chiede di trovare la radice di un'equazione logica. Diamo un'occhiata ai modi per risolvere tali compiti usando un esempio.

Trova la radice dell'equazione logica: (A + B)(X AB) = B + X → A.

La prima soluzione è costruire una tavola di verità. Costruiamo tabelle di verità per i lati destro e sinistro dell'equazione e vediamo a quale X coincidono i valori nelle ultime colonne di queste tabelle.

F1 (A, B, X) = (A+ B)(X AB)

					A+B	(A+B)(XAB)	F1(A,B,X)

F2 (A, B, X) = B+ X→ A

			X→A							F2(A,B,X)
					X→A			X→A

Confrontiamo le tabelle di verità risultanti e selezioniamo quelle righe in cui i valori di F 1 (A, B, X) e F 2 (A, B, X) coincidono.

			F1(A,B,X)	F2(A,B,X)

Riscriviamo solo le righe selezionate, lasciando solo le colonne degli argomenti. Consideriamo la variabile X in funzione di A e B.

Ovviamente X = B → A.

La seconda soluzione consiste nel sostituire il segno uguale nell'equazione con un segno equivalente e quindi semplificare l'equazione logica risultante.

Per facilitare il lavoro successivo, semplifichiamo prima i lati destro e sinistro dell'equazione logica e troviamo le loro negazioni:

F1 = (A+ B)(X AB) = A+ B+ (X↔ AB) = A B+ X A B+ X A+ X B

F1 = (A+ B)(X AB) = (A+ B)(X A+ X B+ X A B) = X A B+ X A B+ X A B

F2 = B+ X→ A= B(X→ A) = B(X+ A) = X B+ A B F2 = B+ X→ A= B+ X+ A= B+ X A

Sostituiamo il segno di uguale nella nostra equazione logica con un segno di equivalenza:

F1 ↔ F2 = F1 F2 + F1 F2 = (A B+ X A B+ X A+ X B) (X B+ A B) +

+ (X A B+ X A B+ X A B) (B+ X A) =

= (X A B+ X B+ X A B) + (X A B+ X A B) =

Riorganizziamo i termini logici di questa espressione, togliendo i fattori X e X tra parentesi.

X(A B) + X(B+ AB) = X(A B) + X(B+ A) =

Indichiamo allora T = A B

X T+ X T= X↔ T.

Pertanto, affinché un'equazione logica abbia una soluzione: X = A B = B + A = B → A.

Elementi di logica informatica. Costruzione di diagrammi funzionali

Con lo sviluppo della tecnologia informatica, la logica matematica si è rivelata strettamente correlata alle questioni di progettazione e programmazione della tecnologia informatica. L'algebra della logica trovò inizialmente ampia applicazione nello sviluppo contatto relè schemi La prima ricerca fondamentale che attirò l’attenzione degli ingegneri impegnati nella progettazione informatica sulla possibilità di analizzare i circuiti elettrici utilizzando l’algebra booleana fu pubblicata nel dicembre 1938 dall’americano Claude Shannon, “Symbolic Analysis of Ladder Circuits”. Dopo questo articolo, la progettazione del computer non potrebbe essere eseguita senza l'uso dell'algebra booleana.

Elemento logicoè un circuito che implementa le operazioni logiche di disgiunzione, congiunzione e inversione. Consideriamo l'implementazione di elementi logici attraverso circuiti elettrici di contatto relè, a te familiari da un corso di fisica scolastica.

Collegamento seriale dei contatti

Collegamento in parallelo dei contatti

Compiliamo una tabella delle dipendenze dello stato dei circuiti da tutti i possibili stati dei contatti. Introduciamo le seguenti notazioni: 1 – il contatto è chiuso, c'è corrente nel circuito; 0 – il contatto è aperto, non c'è corrente nel circuito.

		Condizioni del circuito	Condizione del circuito con parallelo
		connessione seriale	connessione

Come puoi vedere, un circuito con una connessione seriale corrisponde all'operazione logica di congiunzione, poiché la corrente nel circuito appare solo quando i contatti A e B sono chiusi contemporaneamente. Un circuito con collegamento in parallelo corrisponde all'operazione logica di disgiunzione, poiché non c'è corrente nel circuito solo nel momento in cui entrambi i contatti sono aperti.

L'operazione logica dell'inversione viene implementata attraverso il circuito di contatto di un relè elettromagnetico, il cui principio viene studiato in un corso di fisica scolastica. Il contatto x è aperto quando x è chiuso e viceversa.

L'uso di elementi di contatto relè per costruire circuiti logici di computer non si è giustificato a causa della bassa affidabilità, delle grandi dimensioni, dell'elevato consumo energetico e delle basse prestazioni. L'avvento dei dispositivi elettronici (vuoto e semiconduttori) ha creato la possibilità di costruire elementi logici con velocità di 1 milione di commutazioni al secondo e superiori. Gli elementi logici a semiconduttore funzionano in modalità interruttore simile a un relè elettromagnetico. L'intera teoria presentata per i circuiti di contatto viene trasferita agli elementi a semiconduttore. Gli elementi logici sui semiconduttori sono caratterizzati non dallo stato dei contatti, ma dalla presenza di segnali in ingresso e in uscita.

Consideriamo gli elementi logici che implementano le operazioni logiche di base:

Invertitore: implementa l'operazione di negazione o inversione. U

l'inverter ha un ingresso e un'uscita. Viene visualizzato il segnale di uscita

quando non ce n'è in ingresso e viceversa.

Congiuntore -

X1 X2...Xn

implementa l'operazione di congiunzione.

Dal congiuntore

un'uscita e almeno due ingressi. Segnale attivo

appare nell'output se e solo se

tutti gli ingressi vengono segnalati.

X2+...Xn

Disgiuntore: implementa l'operazione di disgiunzione. U

il disgiuntore ha un'uscita e almeno due

Il segnale in uscita non appare se e solo se

quando non vengono forniti segnali a tutti gli ingressi.

	Costruire	funzionale
F(X, Y, Z) = X(Y+ Z)
			X+Z

diagramma corrispondente alla funzione:

&F(X, Y, Z)

Risolvere problemi utilizzando la normale congiuntiva

E disgiuntivo-normale forme

IN I libri sui problemi di logica spesso contengono problemi standard in cui è necessario scrivere una funzione da implementare diagramma ladder, semplificarlo e costruire una tabella di verità per questa funzione. Come risolvere il problema inverso? Data una tabella di verità arbitraria, è necessario costruire un diagramma funzionale o relè. Affronteremo questo problema oggi.

Qualsiasi funzione algebra logica può essere rappresentata da una combinazione di tre operazioni: congiunzione, disgiunzione e inversione. Scopriamo come è fatto. Per fare ciò, scriviamo alcune definizioni.

Un minterm è una funzione formata dalla congiunzione di un certo numero di variabili o dalle loro negazioni. Minterm assume il valore 1 per l'unico tra tutti gli insiemi possibili

argomenti e il valore è 0 per tutti gli altri. Esempio: x 1 x 2 x 3 x 4 .

Un maxterm è una funzione formata dalla disgiunzione di un certo numero di variabili o delle loro negazioni. Maxterm assume il valore 0 in uno dei possibili insiemi e 1 in tutti gli altri.

Esempio: x1 + x2 + x3.

Funzione dentro forma normale disgiuntiva(DNF) è la somma logica dei minterm.

Esempio: x 1x 2+ x 1x 2+ x 1x 2x 3.

Forma normale congiuntiva(CNF) è un prodotto logico di disgiunzioni elementari (maxterms).

Esempio: (x 1+ x 2+ x 3) (x 1+ x 2) .

Forma normale disgiuntiva perfetta è chiamato DNF, in ogni minterm in cui sono presenti tutte le variabili o le loro negazioni.

Esempio: x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3

Forma normale congiuntiva perfetta si chiama CNF, in ogni maxtermine del quale sono presenti tutte le variabili o le loro negazioni.

Esempio: (x 1+ x 2+ x 3) (x 1+ x 2+ x 3)

Scrivere una funzione logica da una tabella

Qualsiasi funzione logica può essere espressa come SDNF o SCNF. Ad esempio, considera la funzione f presentata nella tabella.

			f(x1, x2, x3)

Le funzioni G0, G1, G4, G5, G7 sono minterm (vedi definizione). Ognuna di queste funzioni è il prodotto di tre variabili o dei loro inversi e assume valore 1 in una sola situazione. Si può vedere che per ottenere 1 nel valore della funzione f è necessario un minterm. Di conseguenza, il numero di minterm che compongono l'SDNF di questa funzione è uguale al numero di unità nel valore della funzione: f= G0+G1+G4+G5+G7. Pertanto, la SDNF ha la forma:

f (x 1, x 2, x 3) = x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3.

Allo stesso modo, puoi creare SKNF. Il numero di fattori è uguale al numero di zeri nei valori della funzione:

f (x 1, x 2, x 3) = (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) .

Pertanto, qualsiasi funzione logica data sotto forma di tabella può essere scritta come formula.

Algoritmo per costruire SDNF utilizzando una tabella di verità

Viene fornita una tavola di verità di alcune funzioni. Per creare un SDNF, è necessario eseguire la seguente sequenza di passaggi:

1. Seleziona tutte le righe della tabella in cui la funzione assume il valore 1.

2. Per ciascuna di queste righe, assegnare una congiunzione di tutti gli argomenti o le loro inversioni (minterm). In questo caso, l'argomento che assume il valore 0 viene incluso nel minterm con negazione, mentre il valore 1 viene incluso senza negazione.

3. Infine, formiamo la disgiunzione di tutti i minterm ottenuti. Il numero di minterm deve corrispondere al numero di unità della funzione logica.

Algoritmo per costruire SCNF utilizzando una tabella di verità

Viene fornita una tavola di verità di alcune funzioni. Per creare SKNF, è necessario eseguire la seguente sequenza di passaggi:

1. Seleziona tutte le righe della tabella in cui la funzione assume il valore 0.

2. Per ciascuna di queste righe, assegna una disgiunzione di tutti gli argomenti o le loro inversioni (maxterm). In questo caso, un argomento che assume il valore 1 viene incluso nel maxterm con negazione e il valore 1 viene incluso senza negazione.

3. Infine, formiamo la congiunzione di tutti i maxterms ottenuti. Il numero di maxterm deve corrispondere al numero di zeri della funzione logica.

Se accettiamo tra due forme (SDNF o SKNF) di dare la preferenza a quella che contiene meno lettere, allora SDNF è preferibile se ce ne sono meno tra i valori della funzione della tabella di verità, SKNF - se ci sono meno zeri.

Esempio. Viene fornita la tavola di verità di una funzione logica di tre variabili. Costruisci una formula logica che implementa questa funzione.

			F(A, B, C)

Selezioniamo quelle righe in questa tabella di verità in cui il valore della funzione è 0.

F(A, B, C) = (A+ B+ C) (A+ B+ C)

Controlliamo la funzione derivata creando una tabella di verità.

Confrontando le tavole di verità iniziale e finale, possiamo concludere che la funzione logica è costruita correttamente.

Risoluzione dei problemi

1. Tre insegnanti selezionano i problemi per le Olimpiadi. Ci sono diversi compiti tra cui scegliere. Per ogni compito ogni insegnante esprime la sua opinione: compito facile (0) o difficile (1). Un compito è incluso nel compito delle Olimpiadi se almeno due insegnanti lo contrassegnano come difficile, ma se tutti e tre gli insegnanti lo considerano difficile, allora tale compito non è incluso nel compito delle Olimpiadi perché troppo difficile. Crea un diagramma logico di un dispositivo che restituirà 1 se l'attività è inclusa nell'attività delle Olimpiadi e 0 se non è inclusa.

Costruiamo una tabella di verità per la funzione desiderata. Abbiamo tre variabili di input (tre insegnanti). Pertanto, la funzione richiesta sarà una funzione di tre variabili.

Analizzando la condizione del problema, otteniamo la seguente tabella di verità:

Stiamo costruendo SDNF. F(A, B, C) = ABC+ ABC+ ABC

Ora costruiamo un diagramma logico di questa funzione.

B&1F(A,B,C)

2. Olimpiadi cittadine del corso base di informatica, 2007.Costruisci uno schema elettrico per l'ingresso di una casa a tre piani in modo che un interruttore su qualsiasi piano possa accendere o spegnere le luci dell'intera casa.

Quindi, abbiamo tre interruttori che dobbiamo usare per accendere e spegnere la luce. Ciascun interruttore ha due stati: su (0) e giù (1). Supponiamo che se tutti e tre gli interruttori sono in posizione 0, le luci all'ingresso siano spente. Quindi, quando sposti uno qualsiasi dei tre interruttori sulla posizione 1, la luce all'ingresso dovrebbe accendersi. Ovviamente spostando un qualsiasi altro interruttore sulla posizione 1 la luce dell'ingresso si spegnerà. Se si porta il terzo interruttore in posizione 1 si accenderà la luce nell'ingresso. Costruiamo una tabella della verità.

Allora F(A, B, C) = ABC+ ABC+ ABC+ ABC.

	3. Cambia condizione			valori delle funzioni logiche			F(A, B, C) = C→		A+B
	cambiare gli argomenti B e C contemporaneamente è uguale a:
		A → (B C)						(B C) → A
					A(BC)
	4) (B C) → A				A → (B C)

Nota. Per risolvere con successo questo problema, ricorda le seguenti formule logiche:

x → y= x+ y x y= x y+ x y

x ↔ y= x y+ x y

Ci viene data una funzione logica di tre variabili F 1 (A, B, C) = C → A + B = C + A B.

Cambiamo le variabili B e C contemporaneamente: F 2 (A, B, C) = F 1 (A, B, C) = C + A B. Costruiamo tabelle di verità per queste due funzioni:

Analizziamo la tabella risultante. Delle otto righe della tabella, solo in due (2a e 3a) la funzione non cambia valore. Si noti che in queste righe la variabile A non inverte il suo valore, ma le variabili B e C lo fanno.

Costruiamo funzioni SKNF utilizzando queste righe:

F3 (A, B, C) = (A+ B+ C) (A+ B C) = A+ AB+ AC+ AB+ BC+ AC+ B C= .

A+ (B↔ C) = A+ B C= (B C) → A

Pertanto la risposta desiderata è 4.

4. Condizione per modificare il valore di una funzione logica F (A, B, C) = C + AB cambiando contemporaneamente gli argomenti A e B è uguale a:

1) C+ (A B)

C+(A B)

TAXI)

4) C(A B)

C → (A B)

F1(A,B,C)=

C+AB

F2 (A,B,C)= F1 (

C)=A

Costruiamo una tabella della verità.

Analizziamo la tabella risultante. Delle otto righe della tabella, solo in due (1a e 7a) la funzione cambia valore. Tieni presente che in queste righe la variabile C non cambia il suo valore, ma le variabili A e B sì.

Costruiamo funzioni SDNF utilizzando queste righe:

F3 (A, B, C) = A B C+ A B C= C(A B+ A B) = C(A↔ B) = C+ (A B)

Pertanto la risposta desiderata è 2.

Riferimenti

1. Shapiro S.I. Risoluzione di problemi logici e di gioco(studi logici e psicologici). – M.: Radio e comunicazioni, 1984. – 152 p.

2. Sholomov L.A. Fondamenti della teoria dei dispositivi logici e computazionali discreti. – M.: Scienza. cap. ed. fisico - mat. lett., 1980. - 400 p.

3. Pukhalsky G.I., Novoseltseva T.Ya. Progettazione di dispositivi discreti su circuiti integrati: Manuale. – M.: Radio e comunicazioni, 1990.