Come risolvere le funzioni logiche in informatica. Metodi per la risoluzione di sistemi di equazioni logiche. Livello di difficoltà del compito
Tabella della verità: una tabella contenente tutte le possibili combinazioni di variabili di input e i relativi valori di output.
La tabella di verità contiene 2n righe, dove n è il numero di variabili di input e n+m sono colonne, dove m sono le variabili di output.
Istruzione. Quando si entra da tastiera, utilizzare le seguenti convenzioni:
Ad esempio, l'espressione logica abc+ab~c+a~bc deve essere inserita in questo modo: a*b*c+a*b=c+a=b*cPer inserire i dati sotto forma di diagramma logico, utilizzare questo servizio.
Regole di input della funzione logica
- Usa il segno + invece di v (disgiunzione, OR).
- Prima della funzione logica, non è necessario specificare la designazione della funzione. Ad esempio, invece di F(x,y)=(x|y)=(x^y) dovresti semplicemente digitare (x|y)=(x^y) .
- Importo massimo le variabili sono 10 .
La progettazione e l'analisi dei circuiti logici dei computer vengono eseguite con l'aiuto di una sezione speciale di matematica: l'algebra della 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 delle variabili di uscita dalle variabili di ingresso correnti, tale dipendenza è chiamata funzione di commutazione o funzione dell'algebra logica.
Una funzione di algebra logica si dice completamente definita se sono dati tutti e 2 i suoi valori, dove n è il numero di variabili di output.
Se non tutti i valori sono definiti, la funzione viene chiamata parzialmente definita.
Un dispositivo è detto logico se il suo stato è descritto utilizzando una funzione dell'algebra della logica.
I seguenti metodi vengono utilizzati per rappresentare la funzione di algebra logica:
In forma algebrica, è possibile costruire un diagramma di un dispositivo logico utilizzando elementi logici. 
Figura 1 - Schema di un dispositivo logico
Tutte le operazioni dell'algebra della logica sono definite tavole di verità i valori. La tabella della verità determina il risultato dell'esecuzione di un'operazione per tutto possibile x valori logici delle affermazioni 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 affermazioni nell'espressione logica è N, la tabella di verità conterrà 2 N righe, poiché ci sono 2 N diverse combinazioni di possibili valori di argomento.
Operazione NOT - negazione logica (inversione)
L'operazione logica NON viene applicata a un singolo argomento, che può essere un'espressione logica semplice o complessa. Il risultato dell'operazione NON è il seguente:- se l'espressione originale è vera, il risultato della sua negazione sarà falso;
- se l'espressione originale è falsa, il risultato della sua negazione sarà vero.
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 svolge la funzione di combinare due istruzioni, che possono essere un'espressione logica semplice o complessa. Le istruzioni iniziali per 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 entrambi A e B sono veri e falso quando sia A che B sono falsi.
Operazione AND - moltiplicazione logica (congiunzione)
L'operazione logica AND svolge la funzione dell'intersezione di due enunciati (argomenti), che possono essere un'espressione logica semplice o complessa. Il risultato dell'operazione AND è un'espressione vera se e solo se entrambe le espressioni originali sono vere.Simboli utilizzati: A e B, A Λ B, A e 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 applicate:
se A, allora B; A attrae 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 conseguenza (implicazione) è falso solo quando la premessa A è vera e la conclusione B (conseguenza) è falsa.
Operazione "A se e solo se B" (equivalenza, equivalenza)
Denominazione applicabile: A ↔ B, A ~ B.Tavola della verità:
| UN | B | A↔B |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Operazione di addizione Modulo 2 (XOR, esclusivo o, disgiunzione rigorosa)
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 di un'operazione di equivalenza è vero solo se sia A che B sono entrambi veri o entrambi falsi.
Precedenza delle operazioni logiche
- Azioni tra parentesi
- Inversione
- Congiunzione (&)
- Disgiunzione (V), OR esclusivo (XOR), somma modulo 2
- Implicazione (→)
- Equivalenza (↔)
Forma normale disgiuntiva perfetta
Perfetta forma normale disgiuntiva di una formula(SDNF) è una formula equivalente ad essa, che è una disgiunzione di congiunzioni elementari, che ha le seguenti proprietà:- Ogni termine logico della formula contiene tutte le variabili incluse nella funzione F(x 1 ,x 2 ,...x n).
- Tutti i termini logici della formula sono diversi.
- Nessun termine logico contiene una variabile e la sua negazione.
- Nessun termine logico in una formula contiene la stessa variabile due volte.
Per ogni funzione, SDNF e SKNF sono definiti in modo univoco fino a una permutazione.
Forma normale congiuntiva perfetta
Forma normale congiuntiva perfetta di una formula (SKNF)è una formula equivalente ad essa, che è una congiunzione di disgiunzioni elementari che soddisfa le seguenti proprietà:- Tutte le disgiunzioni elementari contengono tutte le variabili incluse nella funzione F(x 1 ,x 2 ,...x n).
- Tutte le disgiunzioni elementari sono distinte.
- Ogni disgiunzione elementare contiene una variabile una volta.
- Nessuna disgiunzione elementare contiene una variabile e la sua negazione.
Argomento della lezione: Soluzione equazioni logiche
Educativo - imparare a risolvere equazioni logiche, formare abilità e abilità per risolvere equazioni logiche e costruire un'espressione logica secondo la tavola di verità;Educativo - creare le condizioni per lo sviluppo dell'interesse cognitivo degli studenti, promuovere lo sviluppo della memoria, dell'attenzione, pensiero logico;
Educativo : contribuire all'educazione della capacità di ascoltare le opinioni degli altri, educazione alla volontà e alla 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. Visita medica compiti a casa(10 minuti)
Nelle lezioni precedenti, abbiamo familiarizzato con le leggi di base dell'algebra della logica, abbiamo imparato come utilizzare queste leggi per semplificare le espressioni logiche.
Controlliamo i compiti sulla semplificazione delle espressioni logiche:
1. Quale delle seguenti parole soddisfa la condizione logica:
(prima consonante → seconda consonante)٨ (vocale dell'ultima lettera → vocale della penultima lettera)? Se ci sono più di queste parole, indica la più piccola di esse.
1) ANNA 2) MARIA 3) OLEG 4) STEPAN
Introduciamo la notazione:
A è la prima lettera di una consonante
B è la seconda lettera di una consonante
S è l'ultima vocale
D - penultima vocale
Facciamo un'espressione:
Facciamo una tabella:
2. Indicare quale espressione logica è equivalente all'espressione
Semplifichiamo la scrittura dell'espressione originale e le opzioni proposte:
3. Si riporta 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:
Familiarizzazione con l'argomento della lezione, presentazione di nuovo materiale (30 minuti)
Continuiamo a studiare le basi della logica e l'argomento della nostra lezione di oggi "Risoluzione delle equazioni logiche". Dopo aver studiato questo argomento, imparerai i modi di base per risolvere le equazioni logiche, acquisirai le abilità per risolvere queste equazioni usando il linguaggio dell'algebra logica e la capacità di comporre un'espressione logica sulla tavola della verità.
1. Risolvi l'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 a K=1, L=1, M=0, N=1.
Soluzione:
Trasformiamo l'espressione(¬K M) → (¬L M N)
L'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 (indica solo il numero nella tua risposta)?
Soluzione: trasformare l'espressione
(LA+B)*(C+D)=1
A+B=1 e C+D=1
Metodo 2: compilazione di una tavola di verità
3 vie: costruzione di SDNF - una forma normale disgiuntiva perfetta per una funzione - una disgiunzione di congiunzioni elementari regolari complete.Trasformiamo l'espressione originale, apriamo le parentesi per ottenere la disgiunzione delle congiunzioni:
(LA+B)*(C+D)=LA*C+B*C+LA*D+B*D=
Integriamo le congiunzioni per completare le congiunzioni (il prodotto di tutti gli argomenti), apriamo le parentesi:
Considera le stesse congiunzioni:
Di conseguenza, otteniamo un SDNF contenente 9 congiunzioni. Pertanto, la tabella di verità per questa funzione ha un valore di 1 su 9 righe su 2 4 =16 insiemi di valori variabili.
3. Quante soluzioni ha l'equazione (indica solo il numero nella tua risposta)?
Semplifichiamo l'espressione:
,
3 vie: costruzione di SDNF
Considera le stesse congiunzioni:
Di conseguenza, otteniamo un SDNF contenente 5 congiunzioni. Pertanto, la tabella di verità per questa funzione ha un valore di 1 su 5 righe di 2 4 = 16 insiemi di valori variabili.
Costruire un'espressione logica secondo la tavola di verità:
per ogni riga della tabella di verità contenente 1, componiamo il prodotto degli argomenti, e le variabili pari a 0 sono incluse nel prodotto con negazione e le variabili pari a 1 - senza negazione. L'espressione F desiderata sarà composta dalla somma dei prodotti ottenuti. Quindi, se possibile, questa espressione dovrebbe essere semplificata.
Esempio: viene fornita la tavola di verità di un'espressione. Costruisci un'espressione logica.
Soluzione:3. Compiti a casa (5 minuti)
Risolvi l'equazione:
Quante soluzioni ha l'equazione (rispondi solo al numero)?
Secondo la tabella di verità data, fare un'espressione logica e
semplificalo.
Bilancio comunale Istituto d'Istruzione
"Media scuola comprensiva n. 18"
distretto urbano della città di Salavat della Repubblica del Bashkortostan
Sistemi di equazioni logiche
nei compiti dell'esame di informatica
Sezione "Fondamenti di Algebra della Logica" in USA le assegnazioniè considerato uno dei più difficili e mal risolti. La percentuale media di completamento delle attività su questo argomento è la più bassa ed è 43,2.
| Sezione del corso | Percentuale media di completamento per gruppi di attività |
| Codificare le informazioni e misurarne la quantità | |
| modellazione delle informazioni | |
| Sistemi numerici | |
| Fondamenti di Algebra della Logica | |
| Algoritmizzazione e programmazione | |
| Fondamenti di tecnologie dell'informazione e della comunicazione |
Basato sulla specifica KIM 2018, questo blocco include quattro attività diversi livelli le difficoltà.
| № compiti | Controllato elementi di contenuto | Livello di difficoltà del compito |
| Capacità di costruire tavole di verità logica | ||
| Possibilità di ricercare informazioni su Internet | ||
| Conoscenza dei concetti e delle leggi di base logica matematica | ||
| Capacità di costruire e trasformare espressioni logiche |
L'attività 23 è un livello di difficoltà elevato, quindi ha la percentuale di completamento più bassa. Tra i laureati formati (81-100 punti) il 49,8% ha completato il compito, i mediamente preparati (61-80 punti) se la cavano del 13,7%, il restante gruppo di studenti non completa questo compito.
Il successo nella risoluzione di un sistema di equazioni logiche dipende dalla conoscenza delle leggi della logica e dalla precisa applicazione dei metodi per risolvere il sistema.
Considera la soluzione di un sistema di equazioni logiche con il metodo della mappatura.
(23.154 Polyakov K.Yu.) Quante soluzioni differenti ha il sistema di equazioni?
((X1 y1 ) (X2 y2 )) (X1 X2 ) (s1 y2 ) =1
((X2 y2 ) (X3 y3 )) (X2 X3 ) (s2 y3 ) =1
((X7 y7 ) (X8 y8 )) (X7 X8 ) (y7 y8 ) =1
dove X1 , X2 ,…, X8, a1 ,y2 ,…,y8 - Variabili booleane? La risposta non ha bisogno di elencare tutti i diversi insiemi di valori variabili per i quali vale questa uguaglianza. Come risposta, è necessario indicare il numero di tali set.
Soluzione. Tutte le equazioni incluse nel sistema sono dello stesso tipo e in ciascuna equazione sono incluse quattro variabili. Conoscendo x1 e y1, possiamo trovare tutti i possibili valori di x2 e y2 che soddisfano la prima equazione. Argomentando in modo simile, dalle note x2 e y2 possiamo trovare x3, y3 che soddisfa la seconda equazione. Cioè, conoscendo la coppia (x1 , y1) e determinando il valore della coppia (x2 , y2) , troveremo la coppia (x3 , y3 ), che a sua volta porterà alla coppia (x4 , y4 ) e così Su.
Troviamo tutte le soluzioni della prima equazione. Questo può essere fatto in due modi: per costruire una tavola di verità, attraverso il ragionamento e l'applicazione delle leggi della logica.
Tavola della verità:
| x 1 si 1 | x2 y2 | (x 1 y1) (x 2 y2) | (x 1 x2) | (y 1 y2) | (x 1 x2) (y 1 y2) | |||||
Costruire una tavola di verità è laborioso e inefficiente in termini di tempo, quindi utilizziamo il secondo metodo: il ragionamento logico. Il prodotto è 1 se e solo se ogni fattore è 1.
(X1 y1 ) (X2 y2 ))=1
(X1 X2 ) =1
(y1 y2 ) =1
Considera la prima equazione. Seguente è uguale a 1, quando 0 0, 0 1, 1 1, allora (x1 y1)=0 a (01), (10), quindi la coppia (X2 y2 ) può essere qualsiasi (00), (01), (10), (11), e per (x1 y1)=1, cioè (00) e (11) la coppia (x2 y2)=1 assume gli stessi valori (00) e (11). Escludiamo da questa soluzione quelle coppie per le quali la seconda e la terza equazione sono false, cioè x1=1, x2=0, y1=1, y2=0.
| (X1 , y1 ) | (X2 , y2 ) |
Numero totale di coppie 1+1+1+22= 25
2) (23.160 Polyakov K.Yu.) Quante soluzioni differenti ha un sistema di equazioni logiche
(X 1 (X 2 y 2 )) (s 1 y 2 ) = 1
(X 2 (X 3 y 3 )) (s 2 y 3 ) = 1
...
( X 6 ( X 7 y 7 )) ( y 6 y 7 ) = 1
X 7 y 7 = 1
Soluzione. 1) Le equazioni sono dello stesso tipo, quindi con il metodo del ragionamento troveremo tutte le possibili coppie (x1,y1), (x2,y2) della prima equazione.
(X1 (X2 y2 ))=1
(y1 y2 ) = 1
La soluzione della seconda equazione sono le coppie (00), (01), (11).
Troviamo soluzioni alla prima equazione. Se x1=0, allora x2 , y2 - any, se x1=1, allora x2 , y2 assume il valore (11).
Facciamo connessioni tra coppie (x1 , y1) e (x2 , y2).
| (X1 , y1 ) | (X2 , y2 ) |
Facciamo una tabella per calcolare il numero di coppie in ogni fase.
| 0 |
|||||||
Tenendo conto delle soluzioni dell'ultima equazione X 7 y 7 = 1, eliminiamo la coppia (10). Trova il numero totale di soluzioni 1+7+0+34=42
3)(23.180) Quante soluzioni differenti ha il sistema di equazioni logiche
(X1 X2 ) (X3 X4 ) = 1
(X3 X4 ) (X5 X6 ) = 1
(X5 X6 ) (X7 X8 ) = 1
(X7 X8 ) (X9 X10 ) = 1
X1 X3 X5 X7 X9 = 1
Soluzione. 1) Le equazioni sono dello stesso tipo, quindi con il metodo del ragionamento troveremo tutte le possibili coppie (x1,x2), (x3,x4) della prima equazione.
(X1 X2 ) (X3 X4 ) = 1
Escludiamo dalla soluzione le coppie che danno 0 (1 0) nel seguito, queste sono le coppie (01, 00, 11) e (10).
Componi collegamenti tra coppie (x1,x2), (x3,x4)
Sia una funzione logica di n variabili. L'equazione logica è:
La costante C ha il valore 1 o 0.
Un'equazione logica può avere da 0 a diverse soluzioni. Se C è uguale a 1, allora le soluzioni sono tutti quegli insiemi di variabili della tavola di verità su cui la funzione F assume il valore true (1). Gli insiemi rimanenti sono soluzioni dell'equazione per C uguale a zero. Possiamo sempre considerare solo equazioni della forma:
Infatti, sia data l'equazione:
In questo caso, puoi passare all'equazione equivalente:
Consideriamo un sistema di k equazioni logiche:
La soluzione del sistema è un insieme di variabili su cui sono soddisfatte tutte le equazioni del sistema. In termini di funzioni logiche, per ottenere una soluzione del sistema di equazioni logiche, si dovrebbe trovare un insieme su cui è vera la funzione logica Ф, che rappresenta la congiunzione delle funzioni originali:
Se il numero di variabili è piccolo, ad esempio inferiore a 5, non è difficile costruire una tabella di verità per la funzione , che permette di dire quante soluzioni ha il sistema e quali sono gli insiemi che danno soluzioni.
In alcuni compiti dell'esame di stato unificato sulla ricerca di soluzioni a un sistema di equazioni logiche, il numero di variabili raggiunge il valore di 10. Quindi costruire una tavola di verità diventa un compito quasi irrisolvibile. Risolvere il problema richiede un approccio diverso. Per un sistema arbitrario di equazioni, non esiste modo generale, che è diverso dall'enumerazione, che consente di risolvere tali problemi.
Nei problemi proposti all'esame, la soluzione si basa solitamente sulla presa in considerazione delle specificità del sistema di equazioni. Ripeto, a parte l'enumerazione di tutte le varianti di un insieme di variabili, non esiste un modo generale per risolvere il problema. La soluzione deve essere costruita in base alle specifiche del sistema. Spesso è utile effettuare una semplificazione preliminare di un sistema di equazioni utilizzando leggi logiche note. Un'altra tecnica utile per risolvere questo problema è la seguente. Non siamo interessati a tutti gli insiemi, ma solo a quelli su cui la funzione ha il valore 1. Invece di costruire una tabella di verità completa, costruiremo il suo analogo: un albero decisionale binario. Ogni ramo di questo albero corrisponde a una soluzione e specifica l'insieme su cui la funzione ha il valore 1. Il numero di rami nell'albero decisionale coincide con il numero di soluzioni del sistema di equazioni.
Che cos'è un albero decisionale binario e come è costruito, spiegherò con esempi di diverse attività.
Problema 18
Quanti diversi insiemi di valori di variabili booleane x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ci sono che soddisfano un sistema di due equazioni?
Risposta: Il sistema ha 36 diverse soluzioni.
Soluzione: il sistema di equazioni include due equazioni. Troviamo il numero di soluzioni per la prima equazione in base a 5 variabili - . La prima equazione può a sua volta essere considerata come un sistema di 5 equazioni. Come è stato mostrato, il sistema di equazioni rappresenta in realtà una congiunzione di funzioni logiche. Vale anche l'affermazione inversa: la congiunzione di condizioni può essere considerata come un sistema di equazioni.
Costruiamo un albero decisionale per l'implicazione () - il primo termine della congiunzione, che può essere considerata come la prima equazione. Ecco come appare l'immagine grafica di questo albero
L'albero è composto da due livelli in base al numero di variabili nell'equazione. Il primo livello descrive la prima variabile. Due rami di questo livello riflettono i possibili valori di questa variabile: 1 e 0. Al secondo livello, i rami dell'albero riflettono solo quei possibili valori della variabile per i quali l'equazione assume il valore true. Poiché l'equazione definisce un'implicazione, il ramo su cui ha valore 1 richiede che su quel ramo abbia valore 1. Il ramo su cui ha valore 0 genera due rami con valori pari a 0 e 1. L'albero costruito definisce tre soluzioni, su cui l'implicazione assume il valore 1. Su ogni ramo viene scritto il corrispondente insieme di valori delle variabili, che fornisce una soluzione all'equazione.
Questi insiemi sono: ((1, 1), (0, 1), (0, 0))
Continuiamo a costruire l'albero decisionale aggiungendo la seguente equazione, la seguente implicazione. La specificità del nostro sistema di equazioni è che ogni nuova equazione del sistema utilizza una variabile dell'equazione precedente, aggiungendo una nuova variabile. Poiché la variabile ha già valori nell'albero, quindi su tutti i rami in cui la variabile ha un valore di 1, anche la variabile avrà un valore di 1. Per tali rami, la costruzione dell'albero continua al livello successivo, ma non compaiono nuovi rami. L'unico ramo in cui la variabile ha il valore 0 darà un ramo in due rami, dove la variabile otterrà i valori 0 e 1. Pertanto, ogni aggiunta di una nuova equazione, data la sua specificità, aggiunge una soluzione. Prima equazione originale:
ha 6 soluzioni. Ecco come appare l'albero decisionale completo per questa equazione:
La seconda equazione del nostro sistema è simile alla prima:
L'unica differenza è che l'equazione utilizza variabili Y. Questa equazione ha anche 6 soluzioni. Poiché ogni soluzione variabile può essere combinata con ciascuna soluzione variabile, il numero totale di soluzioni è 36.
Si noti che l'albero decisionale costruito fornisce non solo il numero di soluzioni (in base al numero di rami), ma anche le soluzioni stesse, scritte su ciascun ramo dell'albero.
Problema 19
Quanti diversi insiemi di valori di variabili booleane x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 ci sono che soddisfano tutte le seguenti condizioni?
Questa attività è una modifica dell'attività precedente. La differenza è che viene aggiunta un'altra equazione che mette in relazione le variabili X e Y.
Dall'equazione segue che quando ha il valore 1 (esiste una di queste soluzioni), allora ha il valore 1. Quindi, c'è un insieme su cui e hanno i valori 1. Quando è uguale a 0, può avere qualsiasi valore, sia 0 che 1. Pertanto, ogni insieme con uguale a 0, e ci sono 5 di tali insiemi, corrisponde a tutti i 6 insiemi con variabili Y. Pertanto, il numero totale di soluzioni è 31.
Problema 20
Soluzione: ricordando l'equivalenza di base, scriviamo la nostra equazione come:
La catena ciclica delle implicazioni significa che le variabili sono identiche, quindi la nostra equazione equivale a:
Questa equazione ha due soluzioni quando tutti sono 1 o 0.
Problema 21
Quante soluzioni ha l'equazione:
Soluzione: proprio come nel problema 20, si passa dalle implicazioni cicliche alle identità riscrivendo l'equazione nella forma:
Costruiamo un albero decisionale per questa equazione:
Problema 22
Quante soluzioni ha il seguente sistema di equazioni?
Risolvere sistemi di equazioni logiche modificando variabili
Il metodo del cambio di variabili viene utilizzato se alcune variabili sono incluse nelle equazioni solo sotto forma di un'espressione specifica e nient'altro. Quindi questa espressione può essere indicata da una nuova variabile.
Esempio 1
Quanti diversi insiemi di valori di variabili logiche x1, x2, x3, x4, x5, x6, x7, x8 ci sono che soddisfano tutte le seguenti condizioni?
(x1 → x2) → (x3 → x4) = 1
(x3 → x4) → (x5 → x6) = 1
(x5 → x6) → (x7 → x8) = 1
La risposta non ha bisogno di elencare tutti i diversi insiemi di valori delle variabili x1, x2, x3, x4, x5, x6, x7, x8, in base ai quali questo sistema di uguaglianze è soddisfatto. Come risposta, è necessario indicare il numero di tali set.
Soluzione:
(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.
Quindi il sistema può essere scritto come una singola equazione:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. La congiunzione è 1 (vera) quando ogni operando restituisce 1. Cioè, ciascuna delle implicazioni deve essere vera, e questo vale per tutti i valori tranne (1 → 0). Quelli. nella tabella dei valori delle variabili y1, y2, y3, y4, l'unità non deve essere a sinistra di zero:
Quelli. le condizioni sono soddisfatte per 5 insiemi y1-y4.
Perché y1 = x1 → x2, quindi il valore y1 = 0 si ottiene su un unico insieme x1, x2: (1, 0), e il valore y1 = 1 si ottiene su tre insiemi x1, x2: (0,0) , ( 0,1), (1.1). Allo stesso modo per y2, y3, y4.
Poiché ogni insieme (x1,x2) per la variabile y1 è combinato con ogni insieme (x3,x4) per la variabile y2, e così via, i numeri degli insiemi di variabili x vengono moltiplicati:
|
Numero di set per x1…x8 |
||||
Aggiungiamo il numero di insiemi: 1 + 3 + 9 + 27 + 81 = 121.
Risposta: 121
Esempio 2
Quanti diversi insiemi di valori di variabili booleane x1, x2, ... x9, y1, y2, ... y9 ci sono che soddisfano tutte le seguenti condizioni?
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)
In risposta non c'è bisogno elenca tutti i diversi insiemi di valori delle variabili x1, x2, ... x9, y1, y2, ... y9 per cui questo sistema uguaglianze. Come risposta, è necessario indicare il numero di tali set.
Soluzione:
Facciamo un cambio di variabili:
(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9
Il sistema può essere scritto come una singola equazione:
(¬z1 ≡ z2) ∧ (¬z2 ≡ z3) ∧ …..∧ (¬z8 ≡ z9)
L'equivalenza è vera solo se entrambi gli operandi sono uguali. Le soluzioni di questa equazione saranno due insiemi:
| z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Perché zi = (xi ≡ yi), allora il valore zi = 0 corrisponde a due insiemi (xi,yi): (0,1) e (1,0), e il valore zi = 1 corrisponde a due insiemi (xi,yi ): (0 ,0) e (1,1).
Allora il primo insieme z1, z2,…, z9 corrisponde a 2 9 insiemi (x1,y1), (x2,y2),…, (x9,y9).
Lo stesso numero corrisponde al secondo insieme z1, z2,…, z9. Quindi ci sono 2 9 +2 9 = 1024 set in totale.
Risposta: 1024
Risolvere sistemi di equazioni logiche mediante definizione visiva di ricorsione.
Questo metodo viene utilizzato se il sistema di equazioni è abbastanza semplice e l'ordine di aumento del numero di insiemi quando si aggiungono variabili è ovvio.
Esempio 3
Quante soluzioni differenti ha il sistema di equazioni
¬x9 ∨ x10 = 1,
dove x1, x2, ... x10 sono variabili booleane?
La risposta non ha bisogno di enumerare tutti i diversi insiemi di valori x1, x2, ... x10 per i quali vale il dato sistema di uguaglianze. Come risposta, è necessario indicare il numero di tali set.
Soluzione:
Risolviamo la prima equazione. Una disgiunzione è uguale a 1 se almeno uno dei suoi operandi è uguale a 1. Cioè, le soluzioni sono gli insiemi:
Per x1=0 ci sono due valori x2 (0 e 1), e per x1=1 c'è un solo valore x2 (1), tale che l'insieme (x1,x2) è la soluzione dell'equazione. Solo 3 set.
Aggiungiamo la variabile x3 e consideriamo la seconda equazione. È simile al primo, il che significa che per x2=0 ci sono due valori di x3 (0 e 1), e per x2=1 c'è un solo valore di x3 (1), tale che l'insieme ( x2,x3) è una soluzione dell'equazione. Ci sono 4 set in totale.
È facile vedere che quando si aggiunge un'altra variabile, viene aggiunto un set. Quelli. formula ricorsiva per il numero di insiemi su variabili (i+1):
N i +1 = N i + 1. Quindi per dieci variabili otteniamo 11 insiemi.
Risposta: 11
Risolvere sistemi di equazioni logiche di vario tipo
Esempio 4
Quanti diversi insiemi di valori di variabili booleane x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 ci sono che soddisfano tutte le seguenti condizioni?
(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1
(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1
(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1
x 4 ∧ y 4 ∧ z 4 = 0
In risposta non c'è bisogno elenca tutti i diversi insiemi di valori delle variabili x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 , in base ai quali è soddisfatto il dato sistema di uguaglianze .
Come risposta, è necessario indicare il numero di tali set.
Soluzione:
Si noti che le tre equazioni del sistema sono le stesse su diversi insiemi indipendenti di variabili.
Considera la prima equazione. Una congiunzione è vera (uguale a 1) solo se tutti i suoi operandi sono veri (uguale a 1). L'implicazione è 1 su tutti gli insiemi tranne (1,0). Quindi, la soluzione della prima equazione sarà tali insiemi x1, x2, x3, x4, in cui 1 non è a sinistra di 0 (5 insiemi):
Allo stesso modo, le soluzioni della seconda e della terza equazione saranno esattamente gli stessi insiemi di y1,…,y4 e z1,…,z4.
Analizziamo ora la quarta equazione del sistema: x 4 ∧ y 4 ∧ z 4 = 0. La soluzione sarà tutti gli insiemi x4, y4, z4 in cui almeno una delle variabili è uguale a 0.
Quelli. per x4 = 0 sono adatti tutti gli insiemi possibili (y4, z4) e per x4 = 1 sono adatti gli insiemi (y4, z4) che contengono almeno uno zero: (0, 0), (0,1) , ( 1, 0).
|
Numero di set |
||||
Il numero totale di serie è 25 + 4*9 = 25 + 36 = 61.
Risposta: 61
Risolvere sistemi di equazioni logiche costruendo formule ricorrenti
Il metodo di costruzione di formule ricorrenti viene utilizzato per risolvere sistemi complessi in cui l'ordine di aumento del numero di insiemi non è ovvio e la costruzione di un albero è impossibile a causa dei volumi.
Esempio 5
Quanti diversi insiemi di valori di variabili booleane x1, x2, ... x7, y1, y2, ... y7 ci sono che soddisfano tutte le seguenti condizioni?
(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1
(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
La risposta non ha bisogno di elencare tutti i diversi insiemi di valori delle variabili x1, x2, ..., x7, y1, y2, ..., y7, sotto cui vale il dato sistema di uguaglianze. Come risposta, è necessario indicare il numero di tali set.
Soluzione:
Si noti che le prime sei equazioni del sistema sono le stesse e differiscono solo per l'insieme delle variabili. Considera la prima equazione. La sua soluzione saranno i seguenti insiemi di variabili:
Denota:
numero di insiemi (0,0) su variabili (x1,y1) fino a A 1 ,
numero di insiemi (0,1) su variabili (x1,y1) fino a B 1 ,
numero di insiemi (1,0) su variabili (x1,y1) tramite C 1 ,
numero di insiemi (1,1) su variabili (x1,y1) tramite D 1 .
numero di insiemi (0,0) su variabili (x2,y2) fino a A 2 ,
numero di insiemi (0,1) su variabili (x2,y2) tramite B 2 ,
numero di insiemi (1,0) su variabili (x2,y2) tramite C 2 ,
numero di insiemi (1,1) su variabili (x2,y2) tramite D 2 .
Dall'albero decisionale, lo vediamo
LA 1 =0, LA 1 =1, LA 1 =1, LA 1 =1.
Si noti che la tupla (0,0) sulle variabili (x2,y2) si ottiene dalle tuple (0,1), (1,0) e (1,1) sulle variabili (x1,y1). Quelli. A 2 \u003d B 1 + C 1 + D 1.
L'insieme (0,1) sulle variabili (x2,y2) si ottiene dagli insiemi (0,1), (1,0) e (1,1) sulle variabili (x1,y1). Quelli. B 2 \u003d B 1 + C 1 + D 1.
Discutendo in modo simile, notiamo che C 2 \u003d B 1 + C 1 + D 1. D2 = D1.
Si ottengono così formule ricorsive:
UN io+1 = B io + C io + D io
B io+1 = B io + C io + D io
C io+1 = B io + C io + D io
D io+1 = UN io + B io + C io + D io
Facciamo un tavolo
| Imposta | Simbolo. | Formula |
Numero di set |
||||||
| io=1 | io=2 | io=3 | io=4 | io=5 | io=6 | io=7 | |||
| (0,0) | un io | Ai+1 =Bi+Ci+Di | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B io | B io+1 = B io + C io + D io | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C io | C io+1 = B io + C io + D io | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D i | D io+1 =D io | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
L'ultima equazione (x7 ∨ y7) = 1 è soddisfatta da tutti gli insiemi tranne quelli in cui x7=0 e y7=0. Nella nostra tabella, il numero di tali insiemi è A 7 .
Allora il numero totale di insiemi è B 7 + C 7 + D 7 = 127+127+1 = 255
Risposta: 255