Espandi la funzione f con una determinata colonna di valori. Scomposizione di funzioni booleane in variabili

Considera il problema della presentazione n-funzione booleana locale F(X 1 ,X 2 ,…,X n) da qualche formula di algebra proposizionale.

Introduciamo la notazione, dove è un parametro uguale a 0 o 1.

È ovvio che

Teorema 1.1. Ogni funzione di algebra booleanaF(X 1 , X 2 ,…, X n ) per ognim (1£ m £ n) può essere rappresentato nella forma seguente:

dove la disgiunzione è presa su tutti i possibili insiemi di valori variabili.

Prova... Considera un insieme arbitrario di valori per tutte le variabili di una data funzione. Dimostriamo che su questo insieme i lati sinistro e destro della formula (1) assumono lo stesso valore. Il lato sinistro è uguale a , Giusto

da , se solo, se, allora il termine logico corrispondente può essere scartato.

Commento... La rappresentazione della funzione indicata nel teorema è detta espansione della funzione in termini di m variabili.

Corollario 1(espansione in una variabile).

In questo caso, le funzioni e sono chiamati componenti di decomposizione.

Corollario 2(espansione in tutte le variabili).

Ovviamente, se , poi

Quindi se la funzione F(X 1 ,X 2 ,…,X n) non è una funzione identicamente falsa, allora può essere espressa da una formula equivalente, che è una somma logica di vari prodotti della forma, e tale rappresentazione è unica.

La formula (2) può essere notevolmente semplificata. È noto che qualsiasi formula dell'algebra della logica può essere ridotta mediante trasformazioni equivalenti a una formula contenente solo congiunzione e negazione o disgiunzione e negazione. Come risultato dell'esecuzione di trasformazioni equivalenti, è possibile ottenere diverse formule, tuttavia solo una di esse avrà le seguenti proprietà:

1. Ogni termine logico contiene tutte le variabili incluse nella formula F(X 1 ,X 2 ,…,X n).

2. Non un solo termine logico contiene sia una variabile che la sua negazione.

3. Tutti i termini logici nella formula sono diversi.

4. Nessun termine logico contiene due volte la stessa variabile.

Queste quattro proprietà sono chiamate proprietà di perfezione(o proprietà C).

Se F(X 1 ,X 2 ,…,X n) è data dalla tavola di verità, allora la corrispondente formula dell'algebra della logica può essere ricostruita abbastanza semplicemente. Per tutti i valori degli argomenti X 1 ,X 2 ,…,X n al quale F prende il valore 1, devi scrivere la congiunzione delle dichiarazioni di variabili elementari, prendendo come termine di congiunzione x io, Se x io= 1, e se x io= 0. La disgiunzione di tutte le congiunzioni registrate sarà la formula necessaria. A proposito di significati F 0 non devi preoccuparti, perché il termine corrispondente nella formula sarà uguale a 0 e può essere scartato a causa dell'equivalenza FÚ 0 ≡ F.

Ad esempio, lascia che la funzione F(X, sì, z) ha la seguente tabella di verità:

X	sì	z	F(X, sì, z)

Questo teorema è di natura costruttiva, poiché consente a ciascuna funzione di costruire una formula che la implementa sotto forma di un DN perfetto. F. Per fare ciò, nella tabella di verità per ogni funzione, segniamo tutte le righe in cui

Condividi il tuo lavoro sui social media

Se questo lavoro non ti soddisfa in fondo alla pagina c'è un elenco di lavori simili. Puoi anche usare il pulsante di ricerca

Aranov Victor Pavlovic. Matematica discreta.

Sezione 4. Sistemi funzionali con operazioni. Algebra della logica.

Lezione 21. Il principio di dualità. Scomposizione di funzioni in variabili. Perfetto DNF e CNF

lezione 21. PRINCIPIO DI DUALITÀ. DECOMPOSIZIONE DEL BOOLE

FUNZIONI SU VARIABILI. DISGIUNTIVO PERFETTO E

FORME NORMALI CONGIUNTIVE

Piano delle lezioni:

1. Principio di dualità.
2. Scomposizione di funzioni booleane in variabili. Forme normali disgiuntive e congiuntive perfette.

1. Principio di dualità

Viene chiamata una funzione uguale a duale funzione per funzione.

Ovviamente, la tabella di verità per la funzione duale si ottiene dalla tabella di verità per la funzione invertendo (cioè sostituendo 0 con 1 e 1 con 0) dei valori delle variabili e della funzione. Ad esempio, .

È facile impostare per le funzioni 0, 1 che

1. la funzione 0 è duale a 1;
2. la funzione 1 è duale a 0;
3. la funzione è duale;
4. la funzione è duale;
5. la funzione è duale;
6. la funzione è duale.

Dalla definizione di dualità segue che

cioè, la funzione è duale a (proprietà di reciprocità).

Principio di dualità.Se una formula implementa una funzione, allora la formula, ovvero la formula ottenuta dalla sostituzione delle funzioni con, rispettivamente, implementa la funzione.

La formula sarà chiamata la formula duale a.

Per dimostrare questa affermazione, è necessario verificarne la validità per i passaggi elementari della sovrapposizione e.

Ad esempio, si ottenga una funzione da una funzione come risultato della seguente sostituzione di variabili:

Poi

cioè la funzione è ottenuta da come risultato della stessa sostituzione di variabili.

Dimostriamo la validità del principio di dualità per un passo usando un esempio. Permettere

Poi

cioè, la funzione è ottenuta da e allo stesso modo della funzione da e.

Il principio di dualità semplifica la derivazione delle tautologie di base e ha una serie di utili applicazioni, che verranno discusse in seguito.

Esempio 1. L'identità segue dall'identità.

Veramente,

;; .

Esempio 2. Costruzione di una formula per la negazione di una funzione.

La definizione della funzione duale implica

Otteniamo la seguente regola: permettere la formula implementa la funzione. Per ottenere una formula per una funzione, è necessario sostituire tutte le variabili nella formula con i relativi negativi.

Troviamo la negazione della funzione.

Da allora.

1. Scomposizione di funzioni booleane in variabili. Perfetto

Forme normali disgiuntive e congiuntive

Introduciamo la notazione

dove è un parametro uguale a 0 o 1. È ovvio che

È facile vedere che 1 se e solo se.

Il teorema sullo sviluppo di funzioni in variabili. Ogni funzione dell'algebra della logica per any() può essere rappresentata nella forma seguente:

, (1)

dove la disgiunzione è presa su tutti i possibili insiemi di valori variabili.

Questa performance si chiamaespansione della funzione in variabili.

Prova. Considera un insieme arbitrario di valori di variabili e mostra che i lati sinistro e destro della relazione (1) assumono lo stesso valore su di esso. Il lato sinistro dà. Destra -

Come corollari del teorema, si considerino due casi particolari di decomposizione.

1. Espansione variabile:

Funzioni e sono chiamatecomponenti di decomposizione.Questa scomposizione è utile quando alcune proprietà sono stabilite per induzione.

1. Espansione in tutte le variabili:

Se non è identicamente uguale a 0, può essere trasformato:

Di conseguenza, finalmente otteniamo

. (2)

Tale decomposizione è chiamataforma normale disgiuntiva perfetta(perfetto dn. f.).

Direttamente al concetto di un perfetto D.N. F. il seguente teorema confina.

Teorema. Ogni funzione dell'algebra della logica può essere rappresentata da una formula nella base.

Dim. 1) Let. Allora ovviamente

1. Lascia che non sia identicamente uguale a 0. Quindi può essere rappresentato dalla formula (2).

Questo teorema è di natura costruttiva, poiché consente a ciascuna funzione di costruire una formula che la implementa sotto forma di un DN perfetto. F. Per fare ciò, nella tabella della verità per ogni funzione, segniamo tutte le righe in cui. Per ciascuna di queste linee, formiamo un prodotto logico e quindi colleghiamo tutte le congiunzioni risultanti con un segno di disgiunzione.

Esempio 3. Trova il dn perfetto. F. per la funzione.

Perfetto d.N. F. è un'espressione di tipo P. Mostriamo che per identicamente diverso da 1 può essere rappresentato nella forma. Per una funzione duale (ovviamente non identicamente uguale a 0), scriviamo l'espansione sotto forma di DN perfetto. F .:

Il principio di dualità implica

Quindi, otteniamo una scomposizione, che si chiamaperfetta forma normale congiuntivo(dottorato perfetto):

. (3)

Esempio 4. Costruisci il dottorato perfetto F. per la funzione.

Abbiamo.

Altri lavori simili che potrebbero interessarti Wshm>
200.		Forme normali di funzioni logiche	63,53 KB
	Forme normali di funzioni logiche La rappresentazione di una funzione booleana sotto forma di disgiunzione dei termini congiuntivi dei costituenti dell'unità Ki 2.7 è chiamata forma normale disgiuntiva del DNF di questa funzione. contengono esattamente una alla volta tutte le variabili logiche prese con o senza negazioni, allora questa forma della rappresentazione della funzione è chiamata la perfetta forma normale disgiuntiva del SDNF di questa funzione. Come puoi vedere, quando compili la funzione SDNF, devi fare una disgiunzione di tutti i minterm per cui la funzione assume il valore 1.
9015.		METODI PER MINIMIZZARE LE FUNZIONI BOOLEAN	81.74 KB
	Circuiti DNF e FE. Minimizzazione di funzioni booleane basate sulla costruzione di DNF senza uscita. Minimizzazione delle funzioni booleane basata sulla costruzione di DNF senza uscita I DNF senza uscita ridotti e minimi si trovano nella seguente relazione. Un DNF senza uscita si ottiene da uno accorciato rimuovendo alcuni membri.
9017.		IL PROBLEMA DELLA MINIMIZZAZIONE DELLE FUNZIONI BOOLEANE. INTERPRETAZIONE GEOMETRICA	109.86 KB
	Circuiti DNF e FE. INTERPRETAZIONE GEOMETRICA Piano delle lezioni: Il concetto di forma normale disgiuntiva DNF. concetto di DNF. L'espressione per dove è una congiunzione elementare di rango è chiamata forma normale disgiuntiva di DNF.
14731.		Scomposizione di segnali in una serie di Fourier generalizzata in termini di sistemi di funzioni ortogonali. Funzioni Walsh	38.95 KB
	Scomposizione di segnali in una serie di Fourier generalizzata in termini di sistemi di funzioni ortogonali. Familiarizzare con le caratteristiche di base dei segnali e delle interferenze. Studiare la rappresentazione dei segnali sotto forma di serie di Fourier generalizzata per sistemi di funzioni ortogonali. Scomposizione di segnali in una serie di Fourier generalizzata in termini di sistemi di funzioni ortogonali.
6707.		Progettazione di database relazionali. Problemi di progettazione nell'approccio classico. Principi di normalizzazione, forme normali	70,48 KB
	Cos'è un progetto di database relazionale Si tratta di un insieme di relazioni interconnesse in cui vengono definiti tutti gli attributi, vengono specificate le chiavi primarie della relazione e vengono specificate alcune proprietà aggiuntive della relazione che si riferiscono ai principi di mantenimento dell'integrità. Pertanto, la progettazione del database deve essere molto accurata e verificata. Infatti, il progetto del database è la base del futuro pacchetto software che verrà utilizzato per molto tempo e da molti utenti.
4849.		Forme e modalità di esercizio delle funzioni statali	197.3 KB
	Il termine "funzione" ha tutt'altro che lo stesso significato nella letteratura scientifica russa e straniera. In termini filosofici e sociologici generali, è considerato come "una manifestazione esterna delle proprietà di un oggetto in un dato sistema di relazioni"; come un insieme di azioni ordinarie o specifiche di individui o organi
1790.		Scomposizione in termini	180.15 KB
	La stessa parola algoritmo ricorda algoritmi - forme latine scritte dal grande matematico del IX secolo. al-Khorezm, che ha formulato le regole per la somministrazione dell'aritmetica fai da te. Una selezione di algoritmi e uniche regole per visualizzare soluzioni aritmetiche su grandi numeri digitali.
2690.		Studio delle prestazioni di frese a passo variabile di un'elica	18.85 KB
	I modelli del processo di taglio possono essere rappresentati da un sistema di equazioni matematiche che determinano, in ogni caso specifico, la funzione o i criteri di valutazione per le prestazioni degli utensili da taglio, nonché i vincoli tecnici sulla cinematica della macchina, la rigidità del taglio strumenti e l'intero sistema tecnologico.
17088.		RESPONSABILITA' PENALE PER REATI COMMESSI ALL'INTERNO DI UN GRUPPO CRIMINALE ORGANIZZATO	50.97 KB
	Lomtev DESCRIZIONE GENERALE DEL LAVORO La rilevanza del tema di ricerca è determinata dalla necessità di un ulteriore sviluppo e miglioramento della teoria e della pratica di attuazione della responsabilità penale per reati commessi nell'ambito di un gruppo criminale organizzato. La ricerca nel campo della lotta alla criminalità organizzata mostra che è all'interno dei gruppi criminali organizzati che vengono commessi i crimini più pericolosi e difficili da risolvere. Nell'ambito della risoluzione del problema di aumentare l'efficacia del diritto penale in termini di contrasto ...
11576.		Concetto, tipologie e forme delle transazioni. Conseguenze del mancato rispetto della forma di transazione richiesta	49.82 KB
	Riconoscimento di una transazione non valida tipi di transazioni non valide. Il valore applicato del lavoro del corso risiede nella semplificazione del concetto di transazione, ovvero la sua presentazione pubblica in una forma più accessibile.

Impostazione di funzioni booleane di variabili mediante una tabella di verità, definizione di una formula, tipi delle più importanti equivalenze (leggi) dell'algebra della logica. Formule equivalenti, leggi di equivalenza, equazioni logiche. Scomposizione di funzioni booleane in variabili.

Cliccando sul pulsante "Scarica archivio", scaricherai gratuitamente il file di cui hai bisogno.
Prima di scaricare questo file, ricordati di quei buoni abstract, test, tesine, tesi, articoli e altri documenti che non sono stati reclamati sul tuo computer. Questo è il tuo lavoro, deve partecipare allo sviluppo della società e giovare alle persone. Trova questi lavori e inviali alla knowledge base.
Noi e tutti gli studenti, dottorandi, giovani scienziati che utilizzano la base di conoscenza nei loro studi e nel lavoro, te ne saremo molto grati.

Per scaricare un archivio con un documento, nel campo sottostante, inserisci un numero di cinque cifre e clicca sul pulsante "Scarica archivio"

Documenti simili

Assiomi di base e identità dell'algebra della logica. Forma analitica di rappresentazione delle funzioni booleane. Funzioni elementari dell'algebra della logica. Funzioni dell'algebra della logica di un argomento e forme della sua implementazione. Proprietà, caratteristiche e tipi di operazioni logiche.

abstract, aggiunto il 12/06/2010


Il concetto di algebra della logica, la sua essenza e caratteristiche, concetti e definizioni di base, oggetto e metodo di studio. Le leggi dell'algebra della logica e le loro conseguenze, metodi per costruire formule secondo una data tavola di verità. Forme di rappresentazione delle funzioni booleane.

tutorial, aggiunto il 29/04/2009


Le algebre booleane sono un tipo speciale di reticolo utilizzato nello studio della logica (sia la logica del pensiero umano che la logica del computer digitale), nonché i circuiti di commutazione. Forme minime di polinomi booleani. Teoremi di algebra booleana astratta.

tesina, aggiunta il 05/12/2009


Operazioni su enunciati logici: funzioni booleane ed espressione di alcune di queste dipendenze attraverso altre. Formule proposizionali e alcune leggi della logica degli enunciati. Traduzione di espressioni del linguaggio naturale in discorso simbolico dell'algebra della logica.

test, aggiunto il 26/04/2011


La logica è la scienza delle leggi e delle forme di pensiero, e il concetto di base dell'algebra della logica è un'affermazione. Concetti di base e identità dell'algebra booleana. Studio di metodi per minimizzare le funzioni booleane. Metodo di Quine, basato sull'applicazione di due relazioni fondamentali.

test, aggiunto il 20/01/2011


Concetti di base dell'algebra della logica. Forme normali disgiuntive e congiuntive. L'essenza del teorema di Shannon. Funzioni booleane di due variabili. Collegamento in serie e parallelo di due interruttori. Proprietà delle funzioni elementari dell'algebra della logica.

test, aggiunto il 29/11/2010


Variabile booleana in algebra booleana. Operazioni logiche: negazione, congiunzione, disgiunzione, implicazione, equivalenza. Leggi fondamentali dell'algebra della logica. Regole di minimizzazione per una funzione logica (eliminazione delle operazioni di implicazione ed equivalenza).

tesina aggiunta 16/01/2012

L'insieme B, sul quale vengono definite due operazioni binarie (congiunzione e disgiunzione) e un'operazione unaria (negazione) e vengono selezionati due elementi 0 e 1, è detto algebra booleana.

Inoltre, per queste operazioni, devono essere soddisfatte le seguenti proprietà:

Associatività

commutatività

Distributività di una congiunzione rispetto alla disgiunzione

Distributività di una disgiunzione rispetto a una congiunzione

idempotenza

due volte no

Proprietà costanti

Le regole di De Morgan

La legge della contraddizione

La terza legge esclusa

Nell'algebra della logica, queste leggi sono chiamate equivalenze.

Forme normali perfette

Perfetta forma normale disgiuntiva

Introduciamo la notazione:

; AA = 1; X A = 1 se X = A, X A = 0 se XA.

La formula X A 1 …… X A n, dove A = è un qualsiasi insieme binario, e tra le variabili Xi possono essercene di coincidenti è detta congiunzione elementare.

Qualsiasi disgiunzione di congiunzioni elementari è chiamata forma normale disgiuntiva (DNF).

Una congiunzione elementare si dice corretta se ogni variabile compare in essa al massimo una volta (inclusa la sua occorrenza sotto il segno di negazione).

Ad esempio: 1) (l'icona della congiunzione è omessa in questo caso).

1), 4) - congiunzioni elementari regolari;

2) - la variabile x entra una volta in se stessa e una seconda volta sotto il segno di negazione;

La variabile y compare tre volte: una da sola e due sotto il segno di negazione.

Una congiunzione elementare regolare si dice completa rispetto alle variabili x 1 ... .. x n se ognuna di queste variabili vi entra una sola volta (può anche essere segno negativo).

Ad esempio: delle congiunzioni elencate nell'esempio precedente, solo 4) è completa rispetto alle variabili x, y, z, t; e rispetto alle variabili x, y, z, solo 1) è completo.

La forma normale disgiuntiva perfetta (CDNF) rispetto alle variabili x 1 ... ..xn è una forma normale disgiuntiva in cui non esistono congiunzioni elementari identiche e tutte le congiunzioni elementari sono corrette e complete rispetto alle variabili x 1 ... ..xn

Espansione in variabili

Teorema 1. Qualsiasi funzione logica può essere rappresentata in SDNF:

dove m, e la disgiunzione è presa su tutti i 2 m insiemi di valori delle variabili x 1, ... x m. La funzione f è espansa nelle prime n-variabili. Questa uguaglianza è chiamata espansione variabile. x 1, ... x m. Ad esempio, per n = 4, m = 2, l'espansione è:

il teorema si dimostra sostituendo in entrambi i membri dell'uguaglianza (1) un insieme arbitrario (b 1,…, b m, b m + 1,…, b n) di tutte le n-variabili.

Per m = 1, da (1) si ottiene lo sviluppo della funzione in una variabile:

Ovviamente, un'espansione simile è valida per qualsiasi delle n-variabili.

Un altro caso importante è quando n = m. In questo caso, tutte le variabili sul lato destro di (1) ottengono valori fissi e le funzioni nella congiunzione del membro destro diventano uguali a 0 o 1, che dà:

dove la disgiunzione è presa su tutte le tuple (b 1… b n) su cui f = 1. Per f = 0, l'insieme delle congiunzioni a destra è vuoto. Questa scomposizione è detta forma normale disgiuntiva perfetta. L'SDNF di una funzione f contiene esattamente tante congiunzioni quante ce ne sono nella tavola di verità di f. Ogni insieme di unità (b 1,…, b n) corrisponde alla congiunzione di tutte le variabili, in cui x i si assume con negazione se b i = 0 b, e senza negazione se b i = 1. Pertanto, esiste una corrispondenza biunivoca tra la tabella di verità della funzione f e il suo SDNF e, pertanto, l'SDNF è unico per qualsiasi funzione logica. L'unica funzione che non ha SDNF è la costante 0.

Teorema 2... Qualsiasi funzione logica può essere rappresentata come una formula booleana.

Infatti, per qualsiasi funzione, ad eccezione della costante 0, il suo SDNF può servire come tale rappresentazione. La costante 0 può essere rappresentata da una formula booleana.

3.1 Scomposizione di funzioni booleane in variabili

3.2 Algebra di Zhegalkin

Abbiamo mostrato sopra che qualsiasi funzione booleana può essere specificata usando una tabella di verità. Questa sezione descrive la transizione dalla transizione tabellare dell'impostazione della funzione a quella analitica.

3.1 Scomposizione di funzioni booleane in variabili.

Sia G un parametro uguale a 0 o 1. Introduciamo la notazione:

È facile verificare mediante verifica che X G = 1 se e solo se X = G. Ne segue che la congiunzione
è uguale a 1 (qui G è uguale a 0 o 1) se e solo se
... Ad esempio, la congiunzione
(in cui G 2 = G 1 = 0, G 3 = G 4 = 1) è uguale a 1 solo nel caso in cui X 1 =X 2 = 0,X 3 =X 4 = 1.

Teorema 1Qualsiasi funzione booleanaF(X 1 , X 2 ,…, X n ) può essere presentato nella seguente forma:

dove 1 ≤K ≤ n, in disgiunzione viene ripreso tutti gli insiemi di valori variabili.

Questa rappresentazione è detta espansione di una funzione in termini di variabili.
... Ad esempio, per n = 4, k = 2, l'espansione (3.1) ha la forma:

.

Dimostriamo la validità dell'espansione (3.1). Per fare ciò, prendi un insieme arbitrario di valori delle variabili
... Mostriamo che i lati sinistro e destro della relazione (3.1) assumono per essa lo stesso valore. Infatti, poiché X G = 1 se e solo se X = G, allora tra le 2 К congiunzione
a destra della (3.1), solo uno in cui
... Tutte le altre congiunzioni
sono uguali a zero.

Così . Come conseguenza della scomposizione (3.1), otteniamo le seguenti due decomposizioni speciali.

Espansione variabileX n :

Se la funzione booleana non è una costante 0, allora l'espansione

Espansione in tutte le variabili:

,
(3.3)

dove la disgiunzione è presa su tutti gli insiemi
per cui il valore della funzione
è uguale a 1.

L'espansione (3.3) è detta forma normale disgiuntiva perfetta (abbreviazione di SDNF) della funzione.

L'espansione (3.3) fornisce un modo per costruire l'SDNF. Per fare ciò, segna tutte le righe nella tabella della verità
, in quale
... Per ciascuna di queste linee, formiamo la congiunzione
e poi colleghiamo tutte le congiunzioni risultanti con un segno di disgiunzione.

Esiste quindi una corrispondenza biunivoca tra la tavola di verità della funzione
e il suo SDNF. Ciò significa che l'SDNF per una funzione booleana è unico.

Una singola funzione booleana che non ha SDNF è la costante 0.

Esempio 1 Trova la forma disgiuntiva perfetta per una funzione
.

Componiamo una tabella di verità per questa funzione:

Da qui otteniamo:
==.

La seguente espansione delle funzioni booleane gioca un ruolo importante nell'algebra della logica.

Teorema 2Qualsiasi funzione booleana
possono essere presentati nella seguente forma:

dove 1≤k≤n, e si prende la congiunzione tutto 2 K insiemi di valori variabili.

Infatti, lascia
- un insieme arbitrario di valori variabili. Mostriamo che i lati sinistro e destro della relazione (3.4) assumono lo stesso valore per essa. Perché
solo quando
, quindi tra 2 k disgiunzioni
a destra della (3.4), solo uno svanisce, in cui
... Tutte le altre clausole sono uguali a 1.

Così
==
.

Le espansioni delle funzioni booleane seguono direttamente dall'espansione (3.4):

L'ultima decomposizione è chiamata forma normale congiuntiva perfetta (SKNF). L'espansione (3.6) fornisce un modo per costruire SKNF. Per fare ciò, segna tutte le righe nella tabella della verità
, in quale. Per ciascuna di queste linee, formiamo una disgiunzione
e poi colleghiamo tutte le congiunzioni risultanti con il segno di congiunzione. Esiste quindi una corrispondenza biunivoca tra la tavola di verità della funzione
e il suo SKNF. Ciò significa che l'SKNF per una funzione booleana è unico.

L'unica funzione booleana che non ha SCNF è costante 1.

Esempio 2 Trova la forma normale congiuntiva perfetta per la funzione
.

Componiamo una tabella di verità per questa funzione.

Da questo otteniamo SKNF

Formula di forma (notazione breve
), dove
- congiunzioni
chiamato forma normale disgiuntiva (DNF).

In virtù della precedente definizione di DNF, ad esempio, le espressioni saranno:
,
.

Come notato nella clausola 2.2, tutte le operazioni logiche possono essere ridotte a tre: congiunzione, disgiunzione e negazione. Inoltre, in considerazione della legge di de Morgan, si può ipotizzare che il segno di negazione sia attribuibile solo a variabili.

Ora, usando la legge distributiva, espandiamo le parentesi e otteniamo la forma normale disgiuntiva. Quindi vale il seguente teorema.

Teorema3 Per ogni formula dell'algebra della logica esiste una forma normale disgiuntiva ad essa equivalente.

La dimostrazione di questo teorema fornisce un modo per costruire una forma normale disgiuntiva per qualsiasi formula nell'algebra della logica.

Esempio 3 Trova la forma normale disgiuntiva per la seguente formula:
.

Segno escluso
legalmente
e applicando le leggi di de Morgan e la doppia negazione, si ottiene:

Quindi, applicando la legge di distributività, espandiamo le parentesi

L'ultima espressione è la forma normale disgiuntiva.

Visualizza modulo
(voce breve ), dove
- disgiunzioni
chiamato forma normale congiuntiva (CNF).

Queste sono, ad esempio, espressioni:

,
.

Come mostrato sopra, per ogni formula dell'algebra della logica esiste una forma disgiuntiva equivalente ad essa. Usando la legge distributiva, è facile ottenere il CNF dal DNF dato.

Quindi vale il seguente teorema.

Teorema 4Per ogni formula dell'algebra della logica esiste una forma normale congiuntiva equivalente.

La dimostrazione di questo teorema fornisce un modo per costruire una forma normale congiuntiva per qualsiasi formula nell'algebra della logica.

Esempio4 Trova le forme normali disgiuntiva e congiuntiva per la seguente formula:
.

Usando la legge
, escludere il segno
... Otteniamo la formula
.

Usando la legge di de Morgan, otteniamo la formula
... Espandendo le parentesi si ottiene la forma normale disgiuntiva

.

Per ottenere la forma normale congiuntiva, applichiamo alla formula
legge distributiva, si ottiene:

L'ultima espressione è la forma normale congiuntiva. Perché
e
, allora il CNF ottenuto è equivalente al seguente CNF:

Tra tutte le formule normali di questa formula, individuiamo la forma normale perfetta, sia disgiuntiva che congiuntiva. Tenendo conto della decomposizione (3), è facile vedere che la forma normale disgiuntiva perfetta di una formula di algebra logica contenente esattamente n diverse variabili è la sua forma normale disgiuntiva, in cui:

1) tutte le congiunzioni sono a coppie diverse;

2) ogni congiunzione contiene esattamente n variabili;

3) ogni congiunzione contiene tutte le n variabili.

Utilizzando l'esempio 1, abbiamo esaminato uno dei modi per costruire l'SDNF, basato sulla compilazione di una tabella di verità. Il prossimo modo per costruire SDNF si basa sull'applicazione delle leggi dell'algebra della logica.

Esempio 5 Trova la forma disgiuntiva perfetta di una formula
.

usando quello
, noi abbiamo
... In vista delle leggi di de Morgan e della doppia negazione, abbiamo ottenuto la forma normale disgiuntiva
... Questo DNF è equivalente alla formula.

Espandendo le parentesi si ottiene:.

Usando la legge dell'idempotenza, otteniamo l'SDNF richiesto:

Tenendo conto della scomposizione (3.6), è facile vedere che la forma normale congiuntiva perfetta di una formula di algebra booleana contenente esattamente n diverse variabili, c'è la sua forma normale congiuntiva, in cui:

1) tutte le disgiunzioni sono distinte a coppie;

2) ogni disgiunzione contiene esattamente n termini;

3) in ogni disgiunzione ci sono tutte n variabili.

Utilizzando l'esempio 2, abbiamo esaminato uno dei modi per costruire l'SCNF, basato sulla compilazione di una tabella di verità. Il prossimo modo per costruire SKNF si basa sull'applicazione delle leggi dell'algebra della logica.

Esempio 6 Trova la forma normale congiuntiva perfetta della formula
.

Usando,
, noi abbiamo
.

Questa formula è la forma normale congiuntiva. È equivalente a una formula.

Usando la legge di distribuzione, otteniamo:

Applicando la legge dell'idempotenza, otteniamo la forma normale congiuntiva perfetta richiesta

identicamente vero se per tutti i valori delle variabili in essa incluse prende il valore in verità.

Esempi di formule identiche sono:

L'algebra delle formule logiche si chiama identicamente falso, se per tutti i valori delle variabili in essa contenute assume il valore Giacente.

Esempi di formule identicamente false sono:

,

L'algebra delle formule logiche si chiama fattibile, se per alcuni valori delle variabili in essa contenute assume il valore vero.

Esempi di formule eseguibili sono le seguenti formule:

,
.

Nell'algebra della logica si può porre il seguente problema: indicare un metodo (algoritmo) che permetta a ciascuna formula dell'algebra della logica di scoprire se è identicamente vera o no. Il compito si chiama problemi di risoluzione.

Considera i seguenti due modi per risolvere questo problema.

Metodo 1 (tabellare) Per determinare se una data formula è identicamente vera o no, è sufficiente stilarne la tavola di verità.

Tuttavia, questo metodo, sebbene fornisca una soluzione fondamentale al problema della risolvibilità, è piuttosto macchinoso.

Metodo 2 basata sulla riduzione delle formule alla forma normale.

Teorema 4Una formula di algebra logica è identicamente vera se e solo se ogni disgiunzione nella sua forma normale congiuntiva contiene una variabile insieme alla sua negazione.

Infatti, se ogni disgiunzione in forma normale congiuntiva contiene una variabile insieme alla sua negazione, allora tutte le disgiunzioni sono uguali a 1, perché
,
... Quindi segue che CNF è identicamente vero.

Ora lascia che questa formula sia identicamente vera e che
c'è qualche disgiunzione nel CNF di questa formula. Supponiamo che la data disgiunzione non contenga una variabile insieme alla sua negazione. In questo caso, possiamo dare a ogni variabile non sotto il segno negativo il valore 0 e ogni variabile sotto il segno negativo - il valore 1. Dopo questa sostituzione, tutte le disgiunzioni diventano uguali a 0, quindi la formula non è identicamente vera. Abbiamo una contraddizione.

Esempio 7 Scopri se la formula

.

usando quello
, noi abbiamo
.

Applicando la legge di distributività si ottiene il CNF:

Poiché ogni disgiunzione contiene una variabile insieme alla sua negazione, la formula è identicamente vera.

Analogamente al teorema precedente, si dimostra il seguente teorema:

Teorema 5 Una formula dell'algebra della logica se e solo se è identicamente falsa quando ogni congiunzione nella sua forma disgiuntiva contiene una variabile insieme alla sua negazione.