Exemplo. Encontre fórmulas CNF

~ ~

A forma normal disjuntiva perfeita do SDNF pode ser construída usando o seguinte algoritmo:

1. = 1. Algoritmo DNF

2. = 2. Algoritmo DNF

3. = 3. Algoritmo DNF

4. = 4. Algoritmo DNF

5. Omitir termos identicamente falsos, ou seja, termos da forma

6. Complete os termos restantes com as variáveis ​​que faltam

7. Repita o ponto 4.

Exemplo. Encontre fórmulas SDNF.

~

Para construir o SCNF, você pode usar o seguinte esquema:

Exemplo. Encontre fórmulas SDNF.

~

Sabe-se (Teoremas 2.11, 2.12) que SDNF e SCNF são definidos exclusivamente pela fórmula e, portanto, podem ser construídos usando a tabela verdade da fórmula.

O esquema para construção de SDNF e SCNF de acordo com a tabela verdade é dado abaixo, para a fórmula ~ :

			~
			1 0 1 0 1 1 0 1	SDNF; SKNF.

2.2. Exercício.

2.2.1 Abaixo estão expressões lógicas. Simplifique as expressões da sua variante tanto quanto possível usando as leis da lógica de Boole. Em seguida, use tabelas verdade para comparar sua expressão simplificada com a original.

2.2.2. Esclareça a questão da equivalência de f 1 e f 2 reduzindo-os a SDNF (Tabela 1).

2.2.3. Encontre a função dual para f 3 usando o princípio generalizado e booleano (Tabela 1). Compare os resultados.

№	f1	f2	f3

2.3. Perguntas de controle.

2.3.1. Defina uma declaração.

2.3.2. Liste as principais operações em uma declaração.

2.3.3. O que é uma tabela verdade?

2.3.4. Crie tabelas verdade para as seguintes fórmulas:

~ ~ ~ ;

2.3.5. Levando em consideração as convenções sobre a ordem das operações, omita os parênteses “extras” e o sinal “ ” nas fórmulas:

;

2.3.6. Usando transformações equivalentes, prove a verdade idêntica das fórmulas:

2.3.7. Encontre fórmulas duplas:

)

2.3.8. Reduza as seguintes fórmulas para a forma DNF perfeita (SDNF):

~

2.3.9. Reduza as seguintes fórmulas para a forma perfeita de CNF (SCNF):

~

Trabalho de laboratório nº 3

Assunto:“Minimização de funções booleanas. Lógica"

Alvo: Adquirir competências práticas no trabalho com métodos de minimização de funções booleanas.

3.1. Informações teóricas.

Formulários mínimos

Como foi mostrado em, qualquer função booleana pode ser representada na forma normal perfeita (disjuntiva ou conjuntiva). Além disso, tal representação é o primeiro passo na transição de uma especificação tabular de uma função para a sua expressão analítica. A seguir procederemos da forma disjuntiva, e os resultados correspondentes para a forma conjuntiva são obtidos com base no princípio da dualidade.

O problema canônico de sintetizar circuitos lógicos em uma base booleana se resume a minimizar funções booleanas, ou seja, a representá-las na forma normal disjuntiva, que contém o menor número de letras (variáveis ​​e suas negações). Esses formulários são chamados de mínimos. Na síntese canônica, assume-se que ambos os sinais e suas inversões são fornecidos às entradas do circuito.

A fórmula apresentada na forma normal disjuntiva é simplificada pelo uso repetido da operação de colagem e da operação de absorção e (as identidades duais para a forma normal conjuntiva têm a forma: e). Aqui, e pode ser entendido como qualquer fórmula de álgebra booleana. Como resultado, chegamos a uma expressão analítica onde outras transformações não são mais possíveis, ou seja, obtemos um formulário sem saída.

Entre as formas sem saída há também uma forma disjuntiva mínima, podendo não ser única. Para ter certeza de que um determinado formulário sem saída é mínimo, você precisa encontrar todos os formulários sem saída e compará-los pelo número de letras que contêm.

Deixe, por exemplo, a função ser dada na forma disjuntiva normal perfeita:

Agrupando os termos e aplicando a operação de colagem, temos.

Com outro método de agrupamento, obtemos:

Ambas as formas sem saída não são mínimas. Para obter a forma mínima, você precisa adivinhar para repetir um termo na fórmula original (isso sempre pode ser feito, já que ). No primeiro caso, tal membro pode ser . Então . Somando o termo , obtemos: . Depois de passar por todas as opções possíveis, você pode ter certeza de que os dois últimos formulários são mínimos.

Trabalhar com fórmulas nesse nível é como vagar no escuro. O processo de busca por formas mínimas torna-se mais visual e proposital se forem utilizadas algumas representações e símbolos gráficos e analíticos especialmente desenvolvidos para esse fim.

Cubo multidimensional

Cada vértice de um cubo dimensional pode ser associado a um constituinte de uma unidade. Conseqüentemente, o subconjunto de vértices marcados é um mapeamento no cubo -dimensional de uma função booleana de variáveis ​​na forma normal disjuntiva perfeita. Na Fig. 3.1 mostra esse mapeamento para a função da cláusula 3.7.

Fig. 3.1 Exibição de uma função apresentada em SDNF em um cubo tridimensional

Para visualizar uma função de variáveis ​​apresentadas em qualquer forma normal disjuntiva, é necessário estabelecer uma correspondência entre seus minitermos e os elementos do cubo -dimensional.

Um minitermo de classificação (-1) pode ser considerado como o resultado da colagem de dois minitermos de classificação (constituinte da unidade), ou seja, , Em um cubo tridimensional, isso corresponde à substituição de dois vértices que diferem apenas nos valores da coordenada que conecta esses vértices a uma aresta (diz-se que a aresta cobre os vértices incidentes a ela). Assim, os minitermos de (-1) ordem correspondem às arestas do cubo -dimensional. Da mesma forma, a correspondência de minitermos de (-2)ª ordem é estabelecida com as faces de um cubo -dimensional, cada uma das quais cobre quatro vértices (e quatro arestas).

Os elementos de um cubo dimensional caracterizado por dimensões são chamados de cubos. Assim, os vértices são 0 cubos, as arestas são 1 cubos, as faces são 2 cubos, etc. Generalizando o raciocínio acima, podemos assumir que um minitermo de ()-ésima classificação na forma normal disjuntiva para uma função de variáveis ​​​​é representado por um -cubo, e cada -cubo cobre todos aqueles -cubos de dimensão inferior que estão associados aos seus vértices . Como exemplo na Fig. 3.2 mostra uma função de três variáveis. Aqui, os minitermos e correspondem a 1 cubo (), e o minitermo é representado por 2 cubos ().

Fig.3.2 Cobertura de funções

Assim, qualquer forma normal disjuntiva é mapeada em um cubo -dimensional por um conjunto de -cubos que cobrem todos os vértices correspondentes aos constituintes da unidade (0-cubos). A afirmação inversa também é verdadeira: se um certo conjunto de -cubos cobre o conjunto de todos os vértices correspondentes aos valores unitários de uma função, então a disjunção dos minitermos correspondentes a esses -cubos é uma expressão desta função em normal disjuntiva forma. Diz-se que tal coleção de -cubos (ou seus minitermos correspondentes) forma a cobertura de uma função.

O desejo de uma forma mínima é intuitivamente entendido como a busca por tal cobertura, cujo número de cubos seria menor e sua dimensão seria maior. A cobertura correspondente à forma mínima é denominada cobertura mínima. Por exemplo, para a função de cobertura da Fig. 3.3 atende aos formulários mínimos E .

Arroz. 3.3 Coberturas de funções.

esquerda – ; na direita –

A exibição de uma função em um cubo tridimensional é clara e simples quando. Um cubo quadridimensional pode ser representado como mostrado na Fig. 3.4, que mostra uma função de quatro variáveis ​​e sua cobertura mínima correspondente à expressão . A utilização deste método requer construções tão complexas que todas as suas vantagens são perdidas.

Arroz. 3.4 Exibição de funções em um cubo quadridimensional

Mapas de Carnot

Outro método para exibir graficamente funções booleanas usa Mapas de Carnot, que são tabelas de correspondência especialmente organizadas. As colunas e linhas da tabela correspondem a todos os conjuntos possíveis de valores de no máximo duas variáveis, e esses conjuntos são organizados de tal forma que cada um subsequente difere do anterior no valor de apenas uma das variáveis . Graças a isso, as células vizinhas da tabela diferem horizontal e verticalmente no valor de apenas uma variável. As células localizadas nas bordas da tabela também são consideradas adjacentes e possuem esta propriedade. Na Fig. A Figura 3.5 mostra mapas de Karnaugh para duas, três, quatro variáveis.

Arroz. 3.5 Mapas de Carnaugh para duas, três e quatro variáveis

Como nas tabelas verdade comuns, as células dos conjuntos em que a função assume o valor 1 são preenchidas com uns (os zeros geralmente não cabem, correspondem a células vazias). Por exemplo, na Fig. 3.6, A mostra um mapa de Karnaugh para uma função cuja representação em um cubo quadridimensional é dada na Fig. 3.4. Para simplificar as coisas, linhas e colunas correspondentes aos valores de 1 para uma variável são destacadas com chaves indicando essa variável.

Arroz. 3.6 Exibindo uma função de quatro variáveis ​​em um mapa de Carnaugh

(a) e sua cobertura mínima (b)

Entre mapeamentos de funções para n cubo tridimensional e o mapa de Carnot há uma correspondência um-para-um. No mapa de Carnot é-um cubo corresponde a um conjunto de 2 células vizinhas colocadas numa linha, coluna, quadrado ou retângulo (tendo em conta a proximidade das arestas opostas do mapa). Portanto, todas as disposições acima expostas (ver parágrafo. cubo multidimensional), são válidos para mapas de Karnaugh. Então, na Fig. 3.6, b mostra a cobertura das unidades do mapa correspondentes à forma disjuntiva mínima a função em questão.

A leitura de minitermos de um mapa de Karnaugh segue uma regra simples. Células se formando é-cubo, dê miniter (n–s)-ª classificação, que inclui aqueles (n–s) variáveis ​​​​que mantêm os mesmos valores neste é-cubo, onde o valor 1 corresponde às próprias variáveis, e o valor 0 corresponde às suas negações. Variáveis ​​que não mantêm seus valores para é-cubo, estão ausentes no minitermo. Diferentes formas de leitura resultam em diferentes representações da função na forma normal disjuntiva (a da extrema direita é mínima) (Figura 3.7).

O uso de mapas de Karnaugh requer construções mais simples em comparação ao mapeamento em n cubo -dimensional, especialmente no caso de quatro variáveis. Para exibir funções de cinco variáveis, são usados ​​dois mapas de Karnaugh para quatro variáveis, e para uma função de seis variáveis, são usados ​​quatro desses mapas. Com um aumento adicional no número de variáveis, os mapas de Karnaugh tornam-se praticamente inutilizáveis.

Famoso na literatura Cartões Veitch Eles diferem apenas na ordem diferente dos conjuntos de valores de variáveis ​​​​e têm as mesmas propriedades dos mapas de Karnaugh.

Complexo de cubos

A inconsistência dos métodos gráficos com um grande número de variáveis ​​​​é compensada por vários métodos analíticos de representação de funções booleanas. Uma dessas representações é complexo de cubos, usando terminologia de espaço lógico multidimensional em combinação com simbolismo especialmente desenvolvido.

). Os cubos 0 correspondentes aos constituintes da unidade são representados por conjuntos de valores variáveis ​​nos quais a função é igual à unidade. Obviamente na gravação

Arroz. 3.8 Complexo de cubos de uma função de três variáveis ​​( A) e sua representação simbólica ( b)

O complexo de cubos se forma cobertura máxima de função. Excluindo disso todos aqueles é-cubos que são cobertos por cubos de dimensão superior, obtemos coberturas correspondentes a formas sem saída. Assim, para o exemplo em consideração (Fig. 3.8), temos um beco sem saída cobrindo

,

que corresponde à função . Neste caso, esta cobertura é mínima.

Para duas funções booleanas, a operação de disjunção corresponde à união dos seus complexos de cubo, e a operação de conjunção corresponde à intersecção dos seus complexos de cubo. A negação de uma função corresponde ao complemento de um complexo de cubos, ou seja, e é determinada por todos os vértices nos quais a função assume o valor 0. Assim, existe uma correspondência biunívoca (isomorfismo) entre a álgebra de Funções booleanas e conjuntos booleanos representando complexos de cubos.

Representar uma função na forma de complexos de cubos é menos visual, mas suas vantagens mais importantes são que as restrições ao número de variáveis ​​são removidas e a codificação da informação é facilitada no uso de computadores.

Minimizando funções booleanas

Formulação do problema. Minimizar um circuito numa base booleana resume-se a encontrar a forma disjuntiva mínima que corresponde à cobertura mínima. O número total de cartas incluídas na forma normal é expresso pelo custo da cobertura , onde é o número de cubos que formam a cobertura de uma determinada função de n variáveis. A cobertura mínima é caracterizada pelo menor valor do seu preço.

Normalmente, o problema de minimização é resolvido em duas etapas. Primeiro, procuramos uma cobertura reduzida que inclua todos os cubos de dimensão máxima, mas não contenha um único cubo coberto por nenhum cubo desta cobertura. A forma normal disjuntiva correspondente é chamada de reduzida e seus minitermos são chamados de implicantes simples. Para uma determinada função, a cobertura reduzida é única, mas pode ser redundante devido ao facto de alguns dos cubos serem cobertos por colecções de outros cubos.

Na segunda etapa, é feita uma transição das formas normais disjuntivas reduzidas para as formas normais disjuntivas sem saída, das quais as formas mínimas são selecionadas. As formas sem saída são formadas pela exclusão da cobertura reduzida de todos os cubos redundantes, sem os quais o conjunto restante de cubos ainda forma uma cobertura de uma determinada função, mas com a exclusão adicional de qualquer um dos cubos, não cobre mais o conjunto de todos os vértices correspondentes a valores únicos da função, ou seja, deixa de ser uma cobertura.

Um cubo de cobertura reduzida que cobre vértices de uma determinada função que não são cobertos por nenhum outro cubo não pode ser redundante e sempre será incluído na cobertura mínima. Tal cubo, assim como seu implicante correspondente, é chamado de extremo (implicante essencial), e os vértices que ele cobre são chamados de vértices cancelados. O conjunto de extremos forma o núcleo da cobertura, é claro que ao passar de uma cobertura reduzida para uma mínima, em primeiro lugar, todos os extremos devem ser isolados. Se o conjunto de extremos não formar uma cobertura, então é complementado para cobrir com cubos da cobertura reduzida.

As definições dadas são ilustradas na Fig. 3.9, onde a cobertura reduzida (ver Fig. 3.9a, ) e as coberturas mínimas (Fig. 3.9b) e (ver Fig. 3.9, b) são expressas da seguinte forma.

Definição 1.Monômio conjuntivo (conjunção elementar) de variáveis ​​é a conjunção dessas variáveis ​​ou suas negações.

Por exemplo, é uma conjunção elementar.

Definição 2.Monômio disjuntivo (disjunção elementar) das variáveis ​​é a disjunção dessas variáveis ​​ou suas negações.

Por exemplo, é uma disjunção elementar.

Definição 3. Uma fórmula que é equivalente a uma dada fórmula de álgebra proposicional e é uma disjunção de monômios conjuntivos elementares é chamada forma normal disjuntiva(DNF) desta fórmula.

Por exemplo,– DNF.

Definição 4. Uma fórmula que é equivalente a uma dada fórmula de álgebra proposicional e é uma conjunção de monômios disjuntivos elementares é chamada forma normal conjuntiva(CNF) desta fórmula.

Por exemplo, – KNF.

Para cada fórmula de álgebra proposicional pode-se encontrar um conjunto de formas normais disjuntivas e conjuntivas.

Algoritmo para construção de formas normais

Usando as equivalências da álgebra lógica, substitua todas as operações básicas na fórmula: conjunção, disjunção, negação:

Livre-se das negativas duplas.

Aplicar, se necessário, as propriedades das fórmulas de distributividade e absorção às operações de conjunção e disjunção.

2.6. Formas normais disjuntivas perfeitas e conjuntivas perfeitas

Qualquer função booleana pode ter muitas representações na forma de DNF e CNF. Um lugar especial entre essas representações é ocupado pelo DNF perfeito (SDNF) e pelo CNF perfeito (SCNF).

Definição 1. Forma normal disjuntiva perfeita(SDNF) é um DNF em que cada monômio conjuntivo contém cada variável do conjunto exatamente uma vez, seja ele mesmo ou sua negação.

Estruturalmente, o SDNF para cada fórmula de álgebra proposicional reduzida a um DNF pode ser definido da seguinte forma:

Definição 2. Forma normal disjuntiva perfeita(SDNF) de uma fórmula de álgebra proposicional é chamada de DNF, que possui as seguintes propriedades:

Definição 3. Forma normal conjuntiva perfeita(SCNF) é um CNF em que cada monômio disjuntivo contém cada variável do conjunto exatamente uma vez, e aparece ele mesmo ou sua negação.

Estruturalmente, o SCNF para cada fórmula de álgebra proposicional reduzida ao CNF pode ser definido como segue.

Definição 4. Forma normal conjuntiva perfeita(SCNF) de uma determinada fórmula de álgebra proposicional é chamada de CNF que satisfaz as seguintes propriedades.

Teorema 1. Toda função booleana de variáveis ​​que não seja identicamente falsa pode ser representada em SDNF, e de forma única.

Métodos para encontrar SDNF

1º método

2º método

selecione as linhas onde a fórmula assume o valor 1;

compomos uma disjunção de conjunções sob a condição de que se uma variável estiver incluída na conjunção com valor 1, então anotamos essa variável, se com valor 0, então sua negação; Obtemos SDNF.

Teorema 2. Toda função booleana de variáveis ​​que não seja identicamente verdadeira pode ser representada em SCNF, e de forma única.

Métodos para encontrar SCNF

1º método– usando transformações equivalentes:

2º método– usando tabelas verdade:

selecione as linhas onde a fórmula assume o valor 0;

compomos uma conjunção de disjunções sob a condição de que se uma variável estiver incluída na disjunção com valor 0, então anotamos essa variável, se com valor 1, então sua negação; Obtemos SKNF.

Exemplo 1. Construa funções CNF.

Solução

Vamos eliminar o conectivo "" usando as leis da transformação de variáveis:

= /de Leis de Morgan e dupla negação/ =

/leis distributivas/ =

Exemplo 2. Dê a fórmula para DNF.

Solução

Vamos expressar operações lógicas usando e:

= /vamos classificar a negação como variáveis ​​e reduzir os duplos negativos/ =

= /lei ​​da distributividade/ .

Exemplo 3. Escreva a fórmula em DNF e SDNF.

Solução

Usando as leis da lógica, reduzimos esta fórmula a uma forma contendo apenas disjunções de conjunções elementares. A fórmula resultante será o DNF desejado:

Para construir o SDNF, vamos criar uma tabela verdade para esta fórmula:

Marcamos as linhas da tabela em que a fórmula (última coluna) assume o valor 1. Para cada linha, escrevemos uma fórmula que é verdadeira no conjunto de variáveis ​​desta linha:

linha 1: ;

linha 3:;

linha 5: .

A disjunção dessas três fórmulas assumirá o valor 1 apenas nos conjuntos de variáveis ​​das linhas 1, 3, 5 e, portanto, será a forma normal disjuntiva perfeita desejada (PDNF):

Exemplo 4. Traga a fórmula para SKNF de duas maneiras:

a) usando transformações equivalentes;

b) usando uma tabela verdade.

Solução:

Vamos transformar a segunda disjunção elementar:

A fórmula se parece com:

b) elabore uma tabela verdade para esta fórmula:

Marcamos aquelas linhas da tabela em que a fórmula (última coluna) assume o valor 0. Para cada linha, escrevemos uma fórmula que é verdadeira no conjunto de variáveis ​​desta linha:

linha 2: ;

linha 6: .

A conjunção dessas duas fórmulas assumirá o valor 0 apenas nos conjuntos de variáveis ​​das linhas 2 e 6, e portanto será a forma normal conjuntiva perfeita desejada (PCNF):

Perguntas e tarefas para solução independente

1. Usando transformações equivalentes, reduza as fórmulas para DNF:

2. Usando transformações equivalentes, traga as fórmulas para CNF:

3. Usando a segunda lei distributiva, converta DNF em CNF:

A) ;

4. Converta os DNFs fornecidos em SDNFs:

5. Converta o CNF fornecido em SCNF:

6. Para determinadas fórmulas lógicas, construa SDNF e SCNF de duas maneiras: usando transformações equivalentes e usando uma tabela verdade.

b) ;

A forma normal conjuntiva é conveniente para provar teoremas automaticamente. Qualquer fórmula booleana pode ser reduzida a CNF. Para isso você pode usar: a lei da dupla negação, lei de Morgan, distributividade.

YouTube enciclopédico

• 1 / 5

  Fórmulas em KNF:

  ¬ A ∧ (B ∨ C) , (\displaystyle \neg A\wedge (B\vee C),) (A ∨ B) ∧ (¬ B ∨ C ∨ ¬ D) ∧ (D ∨ ¬ E) , (\displaystyle (A\vee B)\wedge (\neg B\vee C\vee \neg D)\wedge ( D\vee\neg E),) A∧B. (\ displaystyle A \ cunha B.)

  Fórmulas não em KNF:

  ¬ (B ∨ C) , (\displaystyle \neg (B\vee C),) (A ∧ B) ∨ C , (\displaystyle (A\wedge B)\vee C,) A ∧ (B ∨ (D ∧ E)) . (\ displaystyle A \ cunha (B \ vee (D \ cunha E)).)

  Mas essas 3 fórmulas que não estão no CNF são equivalentes às seguintes fórmulas no CNF:

  ¬ B ∧ ¬ C , (\displaystyle \neg B\wedge \neg C,) (A ∨ C) ∧ (B ∨ C) , (\displaystyle (A\vee C)\wedge (B\vee C),) A ∧ (B ∨ D) ∧ (B ∨ E) . (\displaystyle A\cunha (B\vee D)\cunha (B\vee E).)

  Construção de CNF

  Algoritmo para construção de CNF

  1) Livre-se de todas as operações lógicas contidas na fórmula, substituindo-as pelas básicas: conjunção, disjunção, negação. Isso pode ser feito usando fórmulas equivalentes:

  A → B = ¬ A ∨ B , (\displaystyle A\rightarrow B=\neg A\vee B,) A ↔ B = (¬ A ∨ B) ∧ (A ∨ ¬ B) . (\displaystyle A\leftrightarrow B=(\neg A\vee B)\wedge (A\vee \neg B).)

  2) Substitua o sinal de negação relativo à expressão inteira por sinais de negação relativos a declarações de variáveis ​​individuais com base nas fórmulas:

  ¬ (A ∨ B) = ¬ A ∧ ¬ B , (\displaystyle \neg (A\vee B)=\neg A\wedge \neg B,) ¬ (A ∧ B) = ¬ A ∨ ¬ B . (\displaystyle \neg (A\wedge B)=\neg A\vee \neg B.)

  3) Livre-se das negativas duplas.

  4) Aplicar, se necessário, as propriedades das fórmulas de distributividade e absorção às operações de conjunção e disjunção.

  Um exemplo de construção de um CNF

  Vamos trazer a fórmula para o CNF

  F = (X → Y) ∧ ((¬ Y → Z) → ¬ X) . (\displaystyle F=(X\rightarrow Y)\wedge ((\neg Y\rightarrow Z)\rightarrow \neg X).)

  Vamos transformar a fórmula F (\estilo de exibição F) para uma fórmula que não contém → (\ displaystyle \ seta direita):

  F = (¬ X ∨ Y) ∧ (¬ (¬ Y → Z) ∨ ¬ X) = (¬ X ∨ Y) ∧ (¬ (¬ Y ∨ Z) ​​​​∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge (\neg (\neg Y\rightarrow Z)\vee \neg X)=(\neg X\vee Y)\wedge (\neg (\neg \ neg Y\vee Z)\vee \neg X).)

  Na fórmula resultante, transferimos a negação para as variáveis ​​​​e reduzimos os negativos duplos:

  F = (¬ X ∨ Y) ∧ ((¬ Y ∧ ¬ Z) ∨ ¬ X) . (\displaystyle F=(\neg X\vee Y)\wedge ((\neg Y\wedge \neg Z)\vee \neg X).)

  Por exemplo, a seguinte fórmula está escrita em 2-CNF:

  (A ∨ B) ∧ (¬ B ∨ C) ∧ (B ∨ ¬ C) . (\displaystyle (A\lor B)\land (\neg B\lor C)\land (B\lor \neg C).)

  Simples conjunção chamado conjunção um ou diversos variáveis, no esse cada variável encontra Não mais um vezes (ou ela mesma, ou dela negação).

  Por exemplo, é uma conjunção simples,

  Disjuntivo normal forma(DNF) chamado disjunção simples conjunções.

  Por exemplo, a expressão é DNF.

  Perfeito disjuntivo normal forma(SDNF) chamado assim disjuntivo normal forma, no qual V todo conjunção incluído Todos variáveis dado lista (ou eles mesmos, ou deles negação), e V um E volume mesmoOK.

  Por exemplo, a expressão é DNF, mas não SDNF. Expressão é SDNF.

  Definições semelhantes (com substituição de conjunção por disjunção e vice-versa) são verdadeiras para CNF e SKNF. Deixe-nos dar a redação exata.

  Simples disjunção chamado disjunção um ou diversos variáveis, no esse cada variável incluído Não mais um vezes (ou ela mesma, ou dela negação).Por exemplo, a expressão é uma disjunção simples,

  Conjuntivo normal forma(KNF) chamado conjunção simples disjunções(por exemplo, a expressão é CNF).

  Uma forma normal conjuntiva perfeita (PCNF) é uma CNF em que cada disjunção simples inclui todas as variáveis ​​de uma determinada lista (elas mesmas ou suas negações), e na mesma ordem.

  Por exemplo, a expressão é SKNF.

  Apresentaremos algoritmos para transições de uma forma para outra. Naturalmente, em casos específicos (com uma certa abordagem criativa) o uso de algoritmos pode ser mais trabalhoso do que simples transformações usando um tipo específico de um determinado formulário:

  a) transição de DNF para CNF

  O algoritmo para esta transição é o seguinte: colocamos duas negações acima do DNF e, usando as regras de De Morgan (sem tocar na negação superior), reduzimos a negação do DNF de volta para DNF. Neste caso, é necessário abrir os colchetes usando a regra de absorção (ou regra de Blake). A negação (superior) do DNF resultante (novamente de acordo com a regra de Morgan) nos dá imediatamente o CNF:

  Observe que o CNF também pode ser obtido a partir da expressão original se retirarmos no além dos colchetes;

  b) transição de CNF para DNF

  Esta transição é realizada simplesmente abrindo os colchetes (a regra de absorção é novamente usada)

  Assim, recebemos DNF.

  A transição reversa (de SDNF para DNF) está associada ao problema de minimização de DNF. Isso será discutido com mais detalhes na seção. 5, mostraremos aqui como simplificar DNF (ou SDNF) de acordo com a regra de Blake. Este tipo de DNF é denominado abreviado DNF;

  c) abreviatura DNF (ou SDNF) por regra Blake

  A aplicação desta regra consiste em duas partes:

  Se entre os termos disjuntos do DNF houver termos , então a toda a disjunção adicionamos o termo PARA 1 PARA 2. Realizamos esta operação várias vezes (possivelmente sequencialmente ou simultaneamente) para todos os pares de termos possíveis e depois aplicamos a absorção normal;

  Se o termo adicionado já estiver contido no DNF, então ele poderá ser descartado completamente, por exemplo,

  ou

  É claro que o DNF abreviado não é definido de forma única, mas todos contêm o mesmo número de letras (por exemplo, existe DNF , após aplicar a regra de Blake, pode-se chegar a um DNF equivalente a este):

  c) transição de DNF para SDNF

  Se alguma conjunção simples estiver faltando uma variável, por exemplo, z, insira a expressão nele e abra os parênteses (não escrevemos termos disjuntos repetidos). Por exemplo:

  d) transição de KNF para SKNF

  Esta transição é realizada de maneira semelhante à anterior: se faltar alguma variável em uma disjunção simples (por exemplo, z, então adicionamos uma expressão a ela (isso não altera a disjunção em si), após a qual abrimos os colchetes usando a lei de distribuição):

  Assim, o SKNF foi obtido da CNF.

  Observe que o CNF mínimo ou reduzido é geralmente obtido a partir do DNF correspondente.

  Formas normais de funções lógicas A representação de uma função booleana na forma de uma disjunção de termos conjuntivos dos constituintes da unidade Ki 2.7 é chamada de forma normal disjuntiva do DNF desta função. contém exatamente uma de todas as variáveis ​​​​lógicas tomadas com ou sem negações, então esta forma de representação de uma função é chamada de forma normal disjuntiva perfeita SDNF desta função. Como você pode ver, ao compor uma função SDNF, você precisa criar uma disjunção de todos os mintermos para os quais a função assume o valor 1.

  
  Compartilhe seu trabalho nas redes sociais

  Se este trabalho não combina com você, no final da página há uma lista de trabalhos semelhantes. Você também pode usar o botão de pesquisa

  
  

  Aula 1.xx

  Formas normais de funções lógicas

  Representação de uma função booleana na forma de uma disjunção de termos conjuntivos (constituinte unitário) K eu

  , (2.7)

  chamado forma normal disjuntiva(DNF) desta função.

  Se todos os termos conjuntivos em DNF forem mintermos , ou seja, contém exatamente uma de todas as variáveis ​​lógicas, tomadas com ou sem negações, então esta forma de representação de função é chamadaforma normal disjuntiva perfeita(SDNF ) esta função. Chama-se SDNF perfeito , porque cada termo da disjunção inclui todas as variáveis; disjuntivo , porque a operação principal da fórmula é a disjunção. Conceito "forma normal”Significa uma maneira inequívoca de escrever uma fórmula que implementa uma determinada função.

  Levando em consideração o acima exposto, o seguinte teorema segue do Teorema 2.1.

  Teorema 2. Qualquer função booleana(não idêntico 0) pode ser apresentado em SDNF, .

  Exemplo 3. Vamos ter uma tabela dada função f (x 1 , x 2 , x 3 ) (Tabela 10).

  Tabela 10

  			f (x 1 , x 2 , x 3 )

  Com base na fórmula (2.6) obtemos:

  Como você pode ver, ao compor uma função SDNF, você precisa criar uma disjunção de todos os mintermos para os quais a função assume o valor 1.

  Representação de uma função booleana na forma de uma conjunção de termos disjuntivos (constituinte zero) Eu

  , (2.8)

  chamado forma normal conjuntiva(CNF) desta função.

  Se todos os termos disjuntivos do CNF forem maxtermos , ou seja, contém exatamente uma de todas as variáveis ​​​​lógicas da função, tomadas com ou sem negações, então tal CNF é chamadoforma normal conjuntiva perfeita(SKNF) desta função.

  Teorema 3. Qualquer função booleana(não é idêntico a 1) pode ser submetido à SKNF, e tal representação é a única.

  A prova do teorema pode ser realizada de forma semelhante à prova do Teorema 2.1 com base no seguinte lema de Shannon sobre decomposição conjuntiva.

  Lema de Shannon . Qualquer função booleana f (x 1, x 2, …, xm) de m variáveis ​​​​podem ser representadas assim:

  . (2.9)

  Deve-se notar que ambas as formas de representação de uma função lógica (DNF e CNF) são teoricamente iguais em suas capacidades: qualquer fórmula lógica pode ser representada tanto em DNF (exceto para o zero idêntico) quanto em CNF (exceto para o idêntico). ). Dependendo da situação, a representação de uma função de uma forma ou de outra pode ser mais curta.

  Na prática, o DNF é mais frequentemente usado, porque esta forma é mais familiar para uma pessoa: desde criança ela está mais acostumada a somar produtos do que a multiplicar somas (neste último caso, ela intuitivamente deseja abrir os colchetes e assim passar para DNF).

  Exemplo 4. Para a função f (x 1 , x 2 , x 3 ), dado pela tabela. 10, escreva para SKNF.

  Ao contrário do SDNF, ao compilar o SCNF na tabela verdade de uma função lógica, você precisa observar as combinações de variáveis ​​nas quais a função assume o valor 0 e criar uma conjunção dos maxtermos correspondentes,mas as variáveis ​​devem ser tomadas com inversão reversa:

  Deve-se notar que é impossível passar diretamente do SDNF de uma função para o seu SCNF ou vice-versa. Ao tentar tais transformações, os resultados são funções opostas às desejadas. Expressões para as funções SDNF e SCNF podem ser obtidas diretamente apenas de sua tabela verdade.

  Exemplo 5. Para a função f (x 1 , x 2 , x 3 ), dado pela tabela. 10, tente mudar de SDNF para SKNF.

  Usando o resultado do exemplo 2.3 obtemos:

  Como você pode ver, na inversão geral obtivemos o SCNF de uma função lógica, que é o inverso da função obtida no exemplo 2.4:

  porque contém todos os maxtermos que não estão na expressão do SCNF da função em consideração.

  1. Utilizando as propriedades das operações (ver Tabela 9) identidade (), soma módulo 2 (), implicação (), passamos para as operações AND, OR, NOT (na base booleana).

  2. Utilizando as propriedades da negação e as leis de De Morgan (ver Tabela 9), garantimos que as operações de negação se aplicam apenas a variáveis ​​individuais, e não a expressões inteiras.

  3. Utilizando as propriedades das operações lógicas AND e OR (ver Tabela 9), obtemos a forma normal (DNF ou CNF).

  4. Se necessário, passamos para formas perfeitas (SDNF ou SKNF). Por exemplo, para obter SCNF muitas vezes você precisa usar a propriedade: .

  Exemplo 6. Converter uma função lógica em SKNF

  Realizando as etapas do algoritmo acima em ordem, obtemos:

  Usando a propriedade de absorção, obtemos:

  Assim, obtivemos a função CNF f (x 1 , x 2 , x 3 ). Para obter seu SCNF, é necessário repetir cada disjunção em que falta alguma variável, duas vezes com esta variável e com sua negação:

  2.2.6. Minimizando funções lógicas

  Como a mesma função lógica pode ser representada como h fórmulas pessoais e, em seguida, encontrar a forma mais simples R mule definindo uma função booleana, simplifica o circuito lógico que implementa a função booleana para ção. Forma mínima lÓ função lógicade alguma forma, podemos considerar aquele que contém o número mínimo de superposições de diversão Para ções da base, permitindo parênteses. Contudo, é difícil construir uma estratégia eficaz eu algoritmo para tal minimização para obter o parêntese mínimo nós.

  Consideremos um problema de minimização mais simples na síntese de circuitos combinacionais, no qual procuramos não a forma entre parênteses mínima de uma função, mas seu DNF mínimo. Existem algoritmos simples e eficientes para esta tarefa.

  Método de Quine

  A função a ser minimizada é representada em SDNF, e todas as possíveis operações de colagem incompleta são aplicadas a ela

  , (2.10)

  e então absorção

  , (2.11)

  e este par de etapas é aplicado repetidamente. Assim, é possível reduzir a classificação dos termos. Este procedimento é repetido até que não reste um único termo que possa ser ligado a qualquer outro termo.

  Observe que o lado esquerdo da equação (2.10) poderia ser imediatamente minimizado de uma forma mais simples e óbvia:

  Este método é ruim porque com essa minimização direta os termos conjuntivos ou desaparecem, embora ainda existam casos possíveis de sua utilização para colagem e absorção com os demais termos.

  Deve-se notar que o método de Quine é bastante trabalhoso, portanto a probabilidade de cometer erros durante as transformações é bastante elevada. Mas a sua vantagem é que teoricamente pode ser utilizado para qualquer número de argumentos e à medida que o número de variáveis ​​aumenta, as transformações tornam-se menos complicadas.

  Método do mapa de Karnaugh

  O método dos mapas (tabelas) de Carnot é uma forma mais visual, menos trabalhosa e confiável de minimizar funções lógicas, mas seu uso é praticamente limitado a funções de 3-4 variáveis, máximo de 5-6 variáveis.

  Mapa de Carnot esta é uma forma tabular bidimensional de representação da tabela verdade de uma função booleana, que permite encontrar facilmente os DNFs mínimos de funções lógicas em uma forma visual gráfica. Cada célula da tabela está associada ao mintermo SDNF da função que está sendo minimizada, e de forma que quaisquer eixos de simetria da tabela correspondam a zonas que são mutuamente inversas em relação a alguma variável. Esta disposição das células na tabela facilita a determinação dos termos de aderência do SDNF (diferindo no sinal de inversão de apenas uma variável): eles estão localizados simetricamente na tabela.

  Tabelas verdade e mapas de Carnaugh para as funções AND e OR de duas pistas e As variáveis ​​são apresentadas na Fig. 8. Um valor está escrito em cada célula do cartão A O valor de uma função no conjunto de valores de argumentos correspondentes a esta célula N camarada

  A) E b) OU

  Arroz. 8. Exemplo de mapas de Karnaugh para funções de duas variáveis

  No mapa de Karnaugh existe apenas um 1 para a função And, portanto não pode ser colado em nada. A expressão para a função mínima conterá apenas o termo correspondente a este 1:

  f = x y .

  No mapa de Carnot para a função OR já existem três 1s e você pode fazer dois pares fixos, com o 1 correspondendo ao termo xy , é usado duas vezes. Na expressão da função mínima, é necessário anotar os termos dos pares que estão sendo colados, deixando neles todas as variáveis ​​​​que não mudam para este par, e retirando as variáveis ​​​​que mudam de valor. Para colagem horizontal obtemos x , e para verticais sim , como resultado obtemos a expressão

  f = x + y.

  Na Fig. 9 mostra as tabelas verdade de duas funções de três variáveis ​​( A ) e seus mapas de Carnot ( bec). Função f2 difere do primeiro porque não é definido em três conjuntos de variáveis ​​​​(na tabela isso é indicado por um travessão).

  Ao determinar a função DNF mínima, as seguintes regras são usadas. Todas as células contendo 1 são combinadas em áreas retangulares fechadas chamadas k-cubos, onde k = log 2 K, K quantidade 1 em uma área retangular. Neste caso, cada área deve ser um retângulo com o número de células 2 k, onde k = 0, 1, 2, 3,…. Para k = 1 retângulo é chamado um é um cubo e contém 2 1 = 2 unidades; para k = 2 retângulo contém 2 2 = 4 unidades e é chamado dois cubos; para k = 3 região de 2 3 = 8 unidades são chamadas três cubos ; etc. Unidades que não podem ser combinadas em retângulos podem ser chamadas cubos zero , que contém apenas uma unidade (2 0 = 1). Como pode ser visto, mesmo para k as áreas podem ter uma forma quadrada (mas não necessariamente) e, se forem ímpares k apenas retângulos.

  						b c

  Arroz. 9. Exemplo de mapas de Karnaugh para funções de três variáveis

  Essas regiões podem se sobrepor, ou seja, as mesmas células podem entrar em regiões diferentes. Então a função DNF mínima é escrita como a disjunção de todos os termos conjuntivos correspondentes a k - cubos.

  Cada uma das áreas indicadas no mapa de Karnaugh é representada em um DNF mínimo por uma conjunção, cujo número de argumentos é k menor que o número total de argumentos da função eu , ou seja, este número é igual mk . Cada conjunção de um DNF mínimo é composta apenas por aqueles argumentos que para a área correspondente do mapa possuem valores sem inversões ou apenas com inversões, ou seja, não alteram seu significado.

  Assim, ao cobrir células do mapa com áreas fechadas, deve-se esforçar-se para garantir que o número de áreas seja mínimo, e que cada área contenha o maior número possível de células, pois neste caso o número de termos no DNF mínimo será mínimo e o o número de argumentos na conjunção correspondente será mínimo.

  Para a função de acordo com o mapa de Karnaugh da Fig. 9, b encontramos

  já que para a região fechada superior as variáveis x 1 e x 2 possuem valores sem inversões, para os inferiores x 1 importa com inversão, e x 3 sem inversão.

  Valores indefinidos no mapa da Fig. 9, V pode ser definido posteriormente substituindo-o por zero ou um. Para esta função, fica claro que é mais lucrativo substituir ambos os valores indefinidos por 1. Nesse caso, são formadas duas áreas, que são tipos diferentes de 2 cubos. Então a expressão para a função DNF mínima será a seguinte:

  Ao construir áreas fechadas, é permitido dobrar o mapa de Carnot em um cilindro tanto horizontal quanto verticalmente. R eixos tikal com a união de faces opostas R você, ou seja, unidades localizadas ao longo das bordas do mapa de simetria de Carnot h mas também pode ser combinado.

  Os mapas de Carnaugh podem ser desenhados de diferentes maneiras (Fig. 10).

  									x 2 x 3

  um b

  Arroz. 10. Diferentes maneiras de representar mapas de Carnaugh
  para uma função de 3 variáveis

  Mas as opções mais convenientes para mapas de Karnaugh para funções de 2 a 4 variáveis ​​são aquelas mostradas na Fig. 11 tabelas, porque são mostradas para cada célula A Temos todas as variáveis ​​na forma direta ou inversa.

  um b

  Arroz. onze. A imagem mais conveniente dos mapas de Carnaugh
  para funções 3 ( a) e 4 (b) variáveis

  Para funções de 5 e 6 variáveis, o método mostrado na Fig. 10, V.

  Arroz. 12. Imagem de um mapa de Karnaugh para uma função de 5 variáveis

  Arroz. 13. Imagem de um mapa de Karnaugh para uma função de 6 variáveis

  Outros trabalhos semelhantes que podem lhe interessar.vshm>
  9020.		O PRINCÍPIO DA DUALIDADE. EXPANSÃO DE FUNÇÕES BOOLEANAS EM VARIÁVEIS. FORMAS NORMAIS DISJUNTIVAS E CONJUNTIVAS PERFEITAS	96,34KB
  	Este teorema é de natureza construtiva, pois permite que cada função construa uma fórmula que a implementa na forma de um d.n. f. Para fazer isso, na tabela verdade de cada função, marcamos todas as linhas em que
  6490.		Descrição e minimização de funções lógicas	187,21 KB
  	A relação entre os argumentos de uma função e seus valores é expressa na forma verbal. Exemplo: uma função de três argumentos assume um valor quando dois ou mais argumentos da função são iguais. Consiste na construção de uma tabela verdade contendo valores de função para todos os conjuntos de valores de argumentos. Neste exemplo, usando a tabela verdade, obtemos a seguinte entrada na forma de DNF...
  6707.		Projeto de bancos de dados relacionais. Problemas de design na abordagem clássica. Princípios de normalização, formas normais	70,48KB
  	O que é um projeto de banco de dados relacional? Este é um conjunto de relacionamentos interconectados nos quais todos os atributos são definidos, as chaves primárias dos relacionamentos são especificadas e algumas propriedades adicionais dos relacionamentos relacionadas aos princípios de manutenção da integridade são especificadas. Portanto, o design do banco de dados deve ser muito preciso e verificado. Na verdade, um projeto de banco de dados é a base de um futuro pacote de software que será utilizado por muito tempo e por muitos usuários.
  4849.		Formas e métodos de implementação de funções de estado	197,3 KB
  	O termo “função” tem longe de ter o mesmo significado na literatura científica nacional e estrangeira. Em termos filosóficos e sociológicos gerais, é considerado como “uma manifestação externa das propriedades de um objeto num determinado sistema de relações”; como um conjunto de ações ordinárias ou específicas de indivíduos ou entidades
  17873.		Formação de UUD lógico para alunos da 3ª série	846,71KB
  	Aspectos psicológicos e pedagógicos do problema da formação de ações lógicas universais em alunos do ensino fundamental. Métodos de avaliação da formação de UUDs lógicos. O desenvolvimento de um conceito para o desenvolvimento de atividades educativas universais no sistema de ensino geral vai ao encontro das novas necessidades sociais. A tarefa mais importante do sistema educacional moderno é a formação de atividades educacionais universais da UUD. A formação de atividades educativas universais é a chave para prevenir as dificuldades escolares.
  2638.		Implementação técnica de conexões lógicas em sistemas de bloqueio automático	1,04MB
  	Implementação técnica de conexões lógicas em sistemas de bloqueio automático A implementação técnica de algoritmos de controle para baterias de três e quatro dígitos pode ser alcançada usando contato de relé e elementos lógicos discretos e integrais sem contato...
  10203.		APLICAÇÃO DO CONCEITO DE ABORDAGEM ORIENTADA A RISCOS NA CONSTRUÇÃO DE MODELOS ESTRUTURAIS E LÓGICOS DE OCORRÊNCIA E DESENVOLVIMENTO DE EMERGÊNCIAS	70,8 KB
  	Análise geral dos riscos O ambiente de produção está a ficar saturado de poderosos sistemas tecnológicos e tecnologias que tornam o trabalho humano produtivo e menos difícil fisicamente, mas mais perigoso. O risco é caracterizado pelo inesperado e repentino início de uma situação perigosa. Todos os dias nos deparamos com inúmeros riscos, mas a maioria deles permanece potencial. A teoria dos riscos prevê uma avaliação quantitativa do impacto negativo sobre uma pessoa, bem como dos danos à sua saúde e à sua vida.
  11576.		Conceito, tipos e formas de transações. Consequências do não cumprimento da forma de transação exigida	49,82KB
  	Reconhecimento de uma transação como tipos inválidos de transações inválidas. O valor aplicado do trabalho da unidade curricular reside na simplificação do conceito de transação, ou seja, na sua apresentação pública de forma mais acessível.
  6213.		Aproximação de função	3,08MB
  	A primeira consiste em substituir uma determinada função especificada analiticamente ou tabularmente por outra função próxima da original, porém mais simples e conveniente para os cálculos. Por exemplo, substituir uma função por um polinômio permite obter fórmulas simples para integração e diferenciação numérica; Substituir a tabela por uma função de aproximação permite obter valores em seus pontos intermediários. Surge também o segundo problema: restaurar uma função em um determinado segmento a partir dos valores da função dados neste segmento em um conjunto discreto de pontos. A resposta a esta pergunta...
  14058.		Evolução das funções do estado	29,99KB
  	O Estado russo, enquanto fenómeno jurídico, deve, em primeiro lugar, garantir a implementação do propósito do Estado, bem como as suas principais características constitucionais como um Estado social secular jurídico federal democrático com uma forma republicana de governo. A finalidade principal do Estado é determinada pelo art.