Informatica. Conversione di espressioni booleane

La carta proposta sarà esaminata in dettagliola questione della trasformazione delle espressioni logiche. Inoltre, ti suggeriamo di seguire un breve corso sulla logica, in cui verranno esaminate le principali leggi e concetti. La trasformazione delle espressioni logiche è un processo piuttosto complicato, se non si familiarizzano con tutte le sfumature del soggetto stesso.

Il corso di informatica sembrerà semplice edare piacere leggendo attentamente questo articolo e familiarizzando con le regole e le leggi della trasformazione, risolvendo problemi e elaborando schemi. Suggeriamo di iniziare adesso.

Logica della scienza

Nozioni di base sulla logica: questo è un argomento piuttosto difficile,su di esso è scritto un sacco di volumi. In questo articolo considereremo le basi e le leggi della trasformazione delle espressioni logiche, cioè l'informazione sarà compressa e concentrata al massimo. Ciò è necessario per considerare in modo più significativo le tecnologie informatiche e la progettazione dei circuiti.

Per cominciare, cos'è la logica e perché è necessaria? È importante notare che questa è una scienza completa che considera le forme e i metodi del ragionamento. Tutto ciò che vediamo, ascoltiamo o facciamo obbedisce alle leggi. Getta la palla da un'altezza - vola sempre verso il basso, in quanto obbedisce alle leggi della fisica. Produciamo caffè fragrante al mattino, aggiungiamo zucchero e le sostanze sciolte si dissolvono all'istante in acqua, obbedendo alle leggi della fisica. Stiamo parlando con gli amici, condividendo i nostri piani: "Se proteggerò bene il lavoro, otterrò un diploma rosso", "Non posso venire in macchina, perché è in riparazione". Senza accorgercene, stiamo costruendo tutte le nostre conversazioni, facendo affidamento sulla logica e le sue leggi. Allora, perché abbiamo bisogno della scienza della logica? Ovviamente, conoscendo le sue leggi, puoi determinare con precisione il risultato di un evento, dal momento che non devi agire casualmente e rischiare.

Anche se il pensiero è un processo piuttosto complesso, tuttavia può essere diviso in alcune componenti, più precisamente, forme (attraverso le quali avviene l'espressione del pensiero):

• concetti;
• dichiarazioni;
• ragionamento;
• prove.

Successivamente, ti suggeriamo di andare alle funzioni logiche e convertire le espressioni logiche. L'informatica sarà divertente e abbastanza semplice per te se leggi attentamente questo articolo.

Funzioni logiche

Ora ci proponiamo di familiarizzare con la logicafunzioni. Spesso, nei biglietti per esami di stato uniformi nella Parte B, ci sono problemi con la trasformazione delle espressioni logiche in segmenti numerici. Non possono essere risolti senza conoscere le funzioni della logica.

Qual è il compito principale di questa scienza? Certo, lo studio delle espressioni logiche (sia complesse che semplici). Come nasce una dichiarazione complessa? Unendo semplici, ciò che accade attraverso i bundle, che sono comunemente chiamati funzioni.

In totale, puoi distinguere cinque pacchetti:

• l'inversione (cioè la negazione, con l'aiuto di questa funzione, si può ottenere una dichiarazione, al contrario: oggi vado al cinema - oggi non vado al cinema);
• disgiunzione (questa funzione è spesso chiamata logicaInoltre, per chiarire, diamo un semplice esempio dalla vita: "se ho mal di testa o mal di stomaco, allora non andrò a scuola" - questa espressione sarà vera se uno dei requisiti è preso in considerazione);
• congiunzione (spesso chiamata moltiplicazione logica: "se lavo i piatti e faccio lezioni, poi esco con gli amici" - questa espressione sarà vera se si prendono in considerazione due condizioni);
• implicazione (in logica questa funzione è chiamataSfortunatamente, non può essere illustrato dalla situazione della vita; una funzione falsa sarà nel caso in cui qualcosa volesse essere fatto, ma non ha funzionato, in altri casi la funzione sarà vera);
• l'equivalenza (o l'uguaglianza, se due affermazioni sono vere o false, allora come risultato otteniamo la verità).

È importante notare che in informatica qualsiasi semplicel'espressione è denotata dalla lettera maiuscola dell'alfabeto latino. Quindi, è necessario ricordare la tabella di verità per ciascuna funzione. Si noti che non è necessario impararlo, sarà sufficiente solo per capire le funzioni.

Tabelle di verità

congiunzione

disgiunzione

inversione

implicazione

equivalenza

Inoltre, è importante notare il fatto che la menzognain logica è indicato dal numero 0 e dalla vera espressione del numero 1. Per praticità, puoi usare entrambi i segni più e meno. Presta attenzione al fatto che le espressioni false e vere nelle tabelle proposte sono indicate rispettivamente dalle lettere "L" e "I".

costruzione

Prima di procedere alla trasformazione delle espressioni logiche, è necessario familiarizzarsi con la loro stessa costruzione. Qualsiasi composto o, come detto prima, un'espressione complessa è composta da due parti:

• Variabili, che sono indicate con lettere maiuscole dell'alfabeto latino;
• Segni che denotano una funzione e connettono tra loro espressioni semplici.

Come fare un'espressione nel linguaggio dell'algebra della logica? Per questo è necessario fare diverse cose:

• dividere l'intera frase in espressioni semplici;
• designare questi elementi con lettere;
• distinguere tra espressioni semplici;
• scrivi l'espressione risultante usando simboli speciali dell'algebra della logica.

Consideriamo un semplice esempio: (Z * F = 5 o Z * F = 4) E (Z * F non è uguale a 5 o Z * F non è uguale a 4). Invece di variabili, sostituire 2. Quindi otteniamo l'espressione (4 = 5 o 4 = 4) e (4 non è 5 o 4 non è 4). Dopo le operazioni eseguite, dobbiamo selezionare le espressioni e le relazioni tra di loro, dovrebbe essere come segue: (Z o F) e (non Z o non F). Dopodiché, dobbiamo convertire questo record, sostituendo il significato delle affermazioni. Se l'espressione è corretta, è necessario sostituire 1, altrimenti - 0. Otteniamo: G = 1 e 1. Dopo i calcoli necessari, otteniamo il risultato: G = 1, cioè l'espressione complessa è vera.

legislazione

Ora ti suggeriamo di considerare le leggi della logica eregole per la conversione di espressioni logiche. È importante ricordare che qualsiasi espressione logica può essere trasformata in un'altra mediante le leggi della logica. Ora considereremo tutte e dieci le regole in dettaglio.

Il primo nella nostra lista è "la legge della doppia negazione". Cioè, l'espressione "non (non A)" sarà uguale all'espressione "A".

La legge comunicativa è anche in matematica, è abbastanza facile da ricordare. A + B = B + A, A * B = B * A.

La legge associativa - (D + E) + F = (D + F) + E, la stessa legge si applica alla moltiplicazione logica.

La legge distributiva è un'apertura elementare di parentesi. Esempio: (A + B) * C = (A * C) + (B * C).

La legge di De Morgan: no (A + B) = * Nea Neuve, non (A * B) + = HEA HEB, HEA AimplikatsiyaV = + B, non (AimplikatsiyaV) = ​​A * Neuve.

Idempotenza: X + X = X o C * C = C.

L'eliminazione delle costanti: X + 1 = 1, X + 0 = X; X * 1 = X, X * 0 = 0.

Poi distinguiamo la legge della contraddizione, seguendola, possiamo affermare la seguente uguaglianza: B * non B = 0.

Nella logica c'è anche una legge di assorbimento, che in pratica assomiglia a questa: C + (C * D) = C o C * (C + D) = C.

È anche importante per la trasformazione delle espressioni logiche ricordare la legge di esclusione: (C * E) + (non C * E) = E o (C + E) * (non C + E) = E.

Se esamini e ricordi tutto in dettagliopresentato in questa sezione delle leggi, quindi i problemi con la trasformazione non sorgeranno mai. Altrettanto importante è l'ordine di esecuzione delle funzioni. Prestare maggiore attenzione a questo punto, la corretta distribuzione dell'ordine delle funzioni è la chiave per la corretta soluzione del problema.

Regole e leggi di trasformazione e semplificazione, l'ordine di esecuzione delle azioni con esempi

Leggi logiche e regole di trasformazionele espressioni logiche sono molto facili da ricordare. Se dubiti della veridicità di almeno uno di loro, allora controlla te stesso. Per fare ciò, è necessario dedicare 10 minuti del proprio tempo e compilare tabelle di verità per ottenere una risposta.

Ora ci proponiamo di considerare le leggi logiche eregole per la conversione di espressioni logiche su esempi specifici. Questo è necessario per consolidare correttamente le conoscenze acquisite. Presta particolare attenzione alla sequenza di azioni.

Ci viene dato: C + (non C * E). È necessario semplificare l'espressione. Il primo passo è aprire le parentesi. Quindi otteniamo l'espressione: (C + notC) * (C + E). Notiamo subito che l'aggiunta logica di due espressioni opposte ci dà la verità. Quello che otteniamo come risultato: 1 * (C + E). Ancora una volta, apri le parentesi: (1 * C) + (1 + E). Ora ancora una volta ricordiamo le leggi e otteniamo la risposta: C + E.

Come hai già visto, tutto è abbastanza semplice. Per risolvere tali problemi, è necessario ricordare le leggi elencate nell'ultima sezione. Proponiamo di procedere alla soluzione di problemi logici, poiché questo compito è già leggermente più complicato rispetto al precedente.

Problem Solving

Abbiamo familiarizzato con le basi della scienza sotto il nome"Logica", la trasformazione delle espressioni logiche, abbiamo brevemente considerato, le leggi elencate. Le attività più complesse con la creazione di espressioni logiche sono attività. È importante notare che possono essere risolti ragionando, convertendo un'espressione o usando un metodo tabulare. Suggeriamo di considerare uno di essi in dettaglio.

Tre ragazzi (Cyril, Anton e Kostya) erano dentrouna stanza All'improvviso, una madre della cucina sente il suono di una tazza rotta. Corsi ai miei figli e chiesi: "Chi è stato?" La risposta fu: Cyril disse che la coppa non era stata spezzata da Kostya, ma da Anton; Anton disse che era Kostya, non Cirillo; Kostya sostiene che Anton non è il colpevole. Sappiamo che uno dei ragazzi ha detto a mamma una bugia. Dobbiamo scoprire chi ha rotto la coppa.

Se discutere logicamente, le risposte di Cyril eAnton si contraddicono a vicenda, proprio come Cyril di Bones. Pertanto, non possono essere entrambi veritieri. Facciamo la seguente deduzione: Anton e Kostya hanno detto la verità, e Cyril è il colpevole della tazza rotta. Questo era il metodo di riflessione usato. Ora vedremo la soluzione dello stesso problema, solo con l'aiuto del metodo di trasformazione dell'espressione. Per cominciare, introduciamo le abbreviazioni:

• KR: la coppa è spezzata da Cirillo;
• A - la tazza è rotta da Anton;
• K è il colpevole di Kostya.

Le risposte dei ragazzi:

• Cirillo - neK, A;
• Anton - non-RK, K;
• Kostya no.

Proponiamo di formulare un'espressione se KostyaHa mentito, e Cirillo e Anton ha detto la verità: HEK * A = 1 e K * necro = 1 e A = 1. Trasformando l'espressione, otteniamo una contraddizione: 0 = 1. La nostra ipotesi è errata, vale la pena controllare altre ipotesi.

Se ipotizziamo che Cyril abbia mentito, e Antone Kostya ha detto a mia madre la verità, otteniamo la seguente espressione: K * notA = 1 e K * notKP = 1 e notA = 1. Semplificando l'espressione, otteniamo KP * notA * notK = 1. Questo suggerisce che la nostra ipotesi era corretta, infatti, Cyril ruppe la coppa e mentì a sua madre.

Metodo di tabella di soluzione

Le leggi ponderate della logica e della trasformazioneespressioni logiche, certamente ci hanno aiutato a far fronte al compito, che è presentato nella sezione precedente. Ora suggeriamo di considerare il metodo della tabella per risolvere il seguente problema.

Dmitry, Anatoly e Lyudmila sono fan dicorrispondenza postale, sappiamo che tutti vivono in diverse parti del mondo e hanno diversi hobby. Determina chi vive in quale città e cosa è dipendente. Sono noti i seguenti fatti:

• Dmitri non era mai stato a Parigi, e Ludmila era a Roma;
• chi vive a Parigi non ama i film;
• una persona che vive a Roma, è impegnata nella voce;
• Lyudmila è disgustata dal balletto.

Per risolvere il problema, è necessario compilare un piccolo tavolo.

Oltre a te è richiesta la massima attenzione. Tutto ciò che leggi nella condizione dovrebbe riflettersi in questa tabella. Man mano che il riempimento diventa chiaro, diventa chiaro quanto segue:

• Dmitry vive a Roma ed è impegnato nella voce;
• Anatoly vive a Parigi e frequenta spesso il balletto;
• Ludmila è una grande fan del cinema, che vive negli Stati Uniti.

Riporta la tua attenzione sul fatto che la vera espressione è contrassegnata dal numero 1 e quella falsa è 0. Quando riempi la tabella con questi simboli, troverai rapidamente la risposta alla domanda che ti interessa.

Mikroskhematika

Esempi di conversione di espressioni logiche,che abbiamo considerato, sono piuttosto complicati a prima vista. Sui biglietti dell'esame di stato unificato, la condizione può essere data a tutti sotto forma di un microcircuito.

È importante sapere che tutti i dispositivi digitali sono basati su elementi logici, cioè su determinati dispositivi che eseguono una singola funzione logica.

Abbiamo già parlato di una funzione come la congiunzione(moltiplicazione logica). Di solito è indicato dal simbolo &. Questa funzione è necessaria per la combinazione di più valori. Nell'immagine vedi lo schema della moltiplicazione logica.

La funzione di disgiunzione è necessaria per implementare la disgiunzione di alcuni valori di input. Quando si scrive un'espressione, questa funzione è solitamente indicata dal simbolo Ú. L'immagine mostra lo schema.

La funzione di inversione serve da convertitore di un'espressione al contrario. Nella figura, si vede come appare lo schema "not".

Un esempio di semplificazione della formula n. 1

Le regole considerate per la trasformazione logicale espressioni devono essere consolidate nella pratica. È nel perseguire questo obiettivo, proponiamo di risolvere in modo indipendente due esempi di complessità media e confrontarli con i risultati di questa sezione dell'articolo.

Se non hai ancora memorizzato le formule per convertire le espressioni logiche, puoi farti un piccolo "promemoria". Vedrai che presto non lo guarderai.

Esempio: (X + T) * (notX + T) * (M + notT). Non scrivere alla cieca, cerca di risolvere l'esempio da solo.

Durante semplificando otteniamo le seguenti voci: T * (M + no) = (T * M) + (T * No) = (T * NTU) + 0 = (T + 0) * (M + 0) = T * M.

Come puoi vedere, da un punto piuttosto lungo e macchinosoespressione complessa abbiamo un breve T * M. Se non sei riuscito a risolvere da solo questo esempio, torna al punto in cui abbiamo considerato la trasformazione delle espressioni logiche, delle attività.

Un esempio di semplificazione della formula n. 2

In questa sezione ti suggeriamo di semplificarel'espressione (E + H) * (E + K). Cerchiamo di analizzare la soluzione passo dopo passo. Prima di tutto, abbiamo bisogno di aprire le parentesi, ricorda il corso della matematica iniziale. Di conseguenza, otteniamo la seguente espressione: E * E + E * K + H * E + H * K. Inoltre, notiamo che nell'espressione risultante c'è una parte di E * E, ricordiamo la legge dell'idempotenza e trasformiamo la notazione: E + E * K + H * E + H * K. Il prossimo passo è trasformare la parte E + E * K, usando il bracketing della variabile E e la proprietà: A + 1 = 1. Otteniamo l'espressione: E + H * E + H * K. Procediamo in modo simile all'ultimo punto e lo togliamo dalle parentesi E. Come risultato, otteniamo la risposta: E + H * K.

Presta attenzione al fatto che i compiti sembrano solo complicati a prima vista. Per "cliccarli come semi", devi solo imparare le leggi fondamentali della logica.