Seções: Informática

Atualmente, existem muitas tarefas nos vestibulares de informática sobre o tema "álgebra da lógica". O objetivo desta lição é consolidar as habilidades de resolver tarefas de USE em informática usando elementos de álgebra lógica.

Lições objetivas:

• Formação da capacidade de aplicar os conhecimentos adquiridos na prática;
• Desenvolvimento da capacidade de construir tabelas de verdade de acordo com fórmulas fornecidas;
• Desenvolvimento da habilidade de resolver problemas de palavras usando as leis da lógica.

Lições objetivas:

• Educacional - desenvolvimento de interesse cognitivo, pensamento lógico.
• Educacional- repetição dos fundamentos da lógica matemática, a implementação de tarefas práticas.
• Em desenvolvimento - desenvolvimento do pensamento lógico, atenção.

Durante as aulas

1. Repetição de operações lógicas e leis.
2. Aplicação de operações lógicas e leis na prática.
3. Explicação do dever de casa.

Hoje estamos finalizando o tópico "Fundamentos da Lógica" e aplicando as operações lógicas básicas, leis de transformação para resolver as tarefas de USE em informática.

A lição ocorre paralelamente à apresentação.<Приложение1>

1. Repetição de operações lógicas e leis.

A álgebra da lógica é um ramo da lógica matemática que estuda a estrutura de declarações lógicas complexas e maneiras de estabelecer sua verdade usando métodos algébricos.

1. O fundador da lógica formal?

Aristóteles.

2. O fundador da álgebra da lógica?

George Boole.

3. Liste as operações lógicas:

¬ negação (inversão)
&, / \\ conjunção (“AND”)
Disjunção V ("OU")
conseqüência lógica (implicação)
equivalência (equivalência)

4. Qual é o significado da lei da dupla negação?

A dupla negação exclui a negação.

5. Leis de De Morgan (leis de inversão geral).

A negação de uma disjunção é uma conjunção de negações:

¬ (A V B) \u003d ¬A / \\ ¬B

A negação de uma conjunção é uma disjunção de negações:

¬ (A / \\ B) \u003d ¬A V ¬B

6. A lei da idempotência (identidade).

7. Qual é o significado da lei de exclusão do terceiro?

De duas afirmações conflitantes sobre a mesma, uma é sempre verdadeira, a segunda é falsa e a terceira não é fornecida:

8. Qual é a lei da contradição?

A afirmação e sua negação não podem ser simultaneamente verdadeiras:

9. A lei de exclusão de constantes.

Para adição lógica:

A V 1 \u003d 1 A V 0 \u003d A

Para multiplicação lógica:

A / \\ 1 \u003d A A / \\ 0 \u003d 0

10. Como expressar implicação por meio de disjunção?

A B \u003d ¬A V B

2. Aplicação de operações lógicas e leis na prática.

Exemplo 1. ( Tarefa A11 da demonstração de 2004)

Para qual nome é dito verdadeiro:

¬ (Primeira letra de uma vogal -\u003e Quarta letra de uma consoante)?

Decisão. Uma declaração complexa consiste em duas declarações simples:

A - a primeira letra do nome é uma vogal,

B - a quarta letra do nome é uma consoante.

¬ (AB) \u003d ¬ (¬A V B) \u003d (¬ (¬A) / \\ ¬B) \u003d A / \\ ¬B

Fórmulas aplicáveis:

1. Implicação por meio da disjunção A? B \u003d ¬A V B

2. Lei de De Morgan ¬ (A V B) \u003d ¬A / \\ ¬B

3. A lei da dupla negação.

(A primeira letra do nome é uma vogal / \\ A quarta letra do nome é uma vogal)

Exemplo 2. ( Tarefa A12 da demonstração de 2004)

Qual expressão lógica é equivalente a ¬ (A \\ / ¬B)?

Decisão. ¬ (A \\ / ¬B) \u003d ¬ A \\ / ¬ (¬B) \u003d ¬ A \\ / B

Crie uma tabela verdade para uma fórmula

¬ (B / \\ C) V (A / \\ C B)

A ordem de execução das operações lógicas:

¬ (B / \\ C) V (A / \\ C B)

Elabore uma tabela de verdade.

Quantas linhas sua tabela terá? 3 variáveis: A, B, C; 2 3 \u003d 8

Quantas colunas? 5 operações + 3 variáveis \u200b\u200b\u003d 8

UMA	B	C	(B / \\ C)	¬ (B / \\ C)	A / \\ C	(A / \\ C? B)	¬ (B / \\ C) V (A / \\ C B)
0	0	0	0	1	0	1	1
0	0	1	0	1	0	1	1
0	1	0	0	1	0	1	1
0	1	1	1	0	0	1	1
1	0	0	0	1	0	0	1
1	0	1	0	1	1	1	1
1	1	0	0	1	0	0	1
1	1	1	1	0	1	1	1

Quais são as respostas da última coluna?

identicamente verdadeirose assumir os valores 1 em todos os conjuntos de instruções simples incluídas nele. Fórmulas identicamente verdadeiras são chamadas tautologias.

Vamos resolver este exemplo usando o método analítico:

simplificando a expressão

¬ (B / \\ C) V (A / \\ C B) \u003d (aplique a fórmula para a implicação)

¬ (B / \\ C) V ¬ (A / \\ C) V B \u003d (aplicar 1 e 2 leis de Morgan)

(¬B V ¬C) V (¬A V ¬C) V B \u003d (remova os colchetes)

¬B V ¬C V ¬A V ¬C V B \u003d (aplica-se a lei de transposição)

¬B V B V ¬C V ¬C V ¬A \u003d (a lei da exclusão do terceiro, a lei da idempotência)

1 V ¬C V ¬A \u003d 1 V ¬A \u003d 1 (lei de eliminação de constantes)

Responda: 1 , significa que a fórmula é identicamente verdadeira ou uma tautologia.

A expressão booleana é chamada identicamente falsose assumir os valores 0 em todos os conjuntos de instruções simples incluídas nele.

(tarefa 3 lição de casa)

A tabela lista as solicitações para o servidor de pesquisa. Organize as designações de consulta em ordem crescente do número de páginas que o mecanismo de pesquisa encontrará para cada consulta.

Para denotar a operação lógica "OU" na consulta, o símbolo I é usado, e para a operação lógica "E" - o símbolo &.

A primeira forma é baseada no raciocínio. Raciocinando logicamente, vemos que a maior parte das páginas será encontrada pela consulta D, pois quando ela for executada, serão encontradas páginas com a palavra “leis”, e páginas com a palavra “física”, e páginas com a palavra “biologia”. A menos de todas as páginas será encontrada para a consulta B, uma vez que contém todas as quatro palavras na página de pesquisa. Resta comparar as consultas A e B. Pela consulta B, todas as páginas correspondentes à consulta A serão encontradas (já que esta última contém necessariamente a palavra "leis"), bem como as páginas que contêm as palavras "física" e "biologia". Portanto, a consulta B encontrará mais páginas do que a consulta A. Assim, ordenando as consultas em ordem crescente de páginas, obtemos WABG.

Resposta: WABG.

O segundo método envolve o uso de uma representação gráfica das operações em conjuntos. (Veja apresentação)

Exemplo 5. ( Tarefa A16 da demonstração de 2006)

Abaixo, em forma de tabela, é apresentado um fragmento do banco de dados dos resultados dos testes dos alunos (uma escala de cem pontos é usada)

Sobrenome	Chão	Matemáticas	língua russa	Química	Informática	Biologia
Aganian	f	82	56	46	32	70
Voronin	m	43	62	45	74	23
Grigorchuk	m	54	74	68	75	83
Rodnina	f	71	63	56	82	79
Sergeenko	f	33	25	74	38	46
Cherepanova	f	18	92	83	28	61

Quantos registros em um determinado fragmento satisfazem a condição

"Gênero \u003d 'm' OR Química\u003e Biologia"?

Selecione as entradas: Meninos (dois) e Química\u003e Biologia (três, mas um menino, já cursou uma vez). Como resultado, 4 registros satisfazem a condição.

Tarefa 6. ( Tarefa B4 da demonstração de 2007)

No campeonato de tênis de mesa escolar, as quatro primeiras incluíram meninas: Natasha, Masha, Luda e Rita. Os fãs mais fervorosos expressaram suas suposições sobre a distribuição de vagas em competições futuras.

Acha-se que Natasha será a primeira, e Masha será a segunda.

Outro torcedor lê Luda em segundo lugar, e Rita, na opinião dele, ficará em quarto lugar.

Um terceiro amante do tênis discordou deles. Ele acredita que Rita ficará em terceiro lugar e Natasha em segundo.

Qual foi a colocação de Natasha, Masha, Luda, Rita no campeonato?

(Em sua resposta, liste os números em uma linha sem espaços correspondentes às casas das meninas na ordem de nomes fornecida.)

Vamos designar as afirmações:

Н1 \u003d “Natasha será a primeira”;

M2 \u003d “Masha será o segundo”;

L2 \u003d “o segundo será Luda”;

P4 \u003d “Rita será a quarta”;

P3 \u003d “Rita será a terceira”;

H2 \u003d “Natasha será a segunda”.

De acordo com a condição:

segue das declarações de 1 fã que Н1VМ2 é verdadeiro;

segue das afirmações2 do ventilador que L2VP4 é verdadeiro;

das declarações de 3 fãs conclui-se que o P3VH2 é verdadeiro.

Portanto, a conjunção

(H1VM2) / \\ (L2VP4) / \\ (P3VH2) \u003d 1.

Expandindo os colchetes, temos:

(H1VM2) / \\ (L2VP4) / \\ (P3VH2) \u003d (H1 / \\ L2V H1 / \\ P4 V M2 / \\ L2 V M2 / \\ P4) / \\ (P3VH2) \u003d

H1 / \\ L2 / \\ P3 V H1 / \\ P4 / \\ P3 V M2 / \\ L2 / \\ P3 V M2 / \\ P4 / \\ P3 V H1 / \\ L2 / \\ H2 V H1 / \\ P4 / \\ H2 V M2 / \\ L2 / \\ H2 V M2 / \\ P4 / \\ H2 \u003d H1 / \\ L2 / \\ P3 V 0 V 0 V 0 V 0 V 0 V 0 V 0 V \u003d H1 / \\ L2 / \\ P3

Natasha-1, Luda-2, Rita-3 e Masha-4.

Resposta: 1423

3. Explicação do dever de casa.

Exercício 1. ( Tarefa B8 da demonstração de 2007)

A tabela lista as solicitações para o servidor de pesquisa. Organize as designações de consulta em ordem crescente do número de páginas que o mecanismo de pesquisa encontrará para cada consulta.

Para denotar a operação lógica "OU" na consulta, o símbolo | é usado, e para a operação lógica "E" - &.

Tarefa 2 ( Tarefa B4 da demonstração de 2008)

Antes do início do Torneio dos Quatro, os fãs fizeram as seguintes suposições sobre seus ídolos:

A) Max ganha, Bill em segundo;

B) Bill é o terceiro. Nick é o primeiro;

C) Max é o último e o primeiro é John.

Quando a competição acabou, descobriu-se que cada um dos torcedores acertou apenas em uma de suas previsões.

Onde John, Nick, Bill, Max participaram do torneio?

(Na resposta, liste os lugares dos participantes em uma linha sem espaços na ordem de nomes fornecida.)

As consultas de pesquisa são usadas para encontrar informações rapidamente na Internet. Uma consulta de pesquisa é um conjunto de palavras-chave conectadas por operadores lógicos AND, OR, NOT.

A prioridade das operações, se não houver parênteses especiais, é a seguinte: primeiro NOT, depois AND e depois OR.

Deve-se entender que a operação AND (cumprimento simultâneo das condições) reduz o volume do resultado, e a operação OR (cumprimento de pelo menos uma das condições), ao contrário, aumenta o volume.

Se a consulta contiver uma frase entre aspas, o sistema pesquisará exatamente essa frase em sua totalidade.

1. Organização das consultas em ordem crescente (decrescente)

A operação AND (&) denota a presença simultânea de palavras-chave nos documentos pesquisados \u200b\u200be, portanto, reduz a quantidade de informações encontradas. Quanto mais palavras-chave forem conectadas pela operação "AND", menos informações serão encontradas. E vice-versa, a operação “OU” (|) denota a presença de pelo menos uma palavra-chave nos documentos pesquisados \u200b\u200be, portanto, aumenta a quantidade de informações encontradas.

Exemplo 1.

A tabela lista as solicitações para o servidor de pesquisa. Organize as designações de consulta em ordem crescente do número de páginas que o mecanismo de pesquisa encontrará para cada consulta.

A) resumo | matemática | Gauss
B) resumo | matemática | Gauss | método
C) resumo | Matemáticas
D) Abstrato e Matemática e Gauss

Decisão:

O menor número de páginas será selecionado pela consulta com mais operações "E" (consulta D). O maior número de páginas será selecionado pela consulta com mais operações "OU" (consulta B). Mais páginas serão selecionadas para a solicitação A do que para a solicitação B, porque a consulta A contém mais palavras-chave relacionadas a OR.

Resposta: GWAB

2. Contagem encontrada nas páginas de solicitação

Esse tipo de problema geralmente é resolvido por um sistema de equações. Vou sugerir uma forma mais visual e simples.

O princípio da seleção de informações para consultas de pesquisa é bem ilustrado pelo diagrama de Euler-Venn (círculos de Euler). No diagrama, os conjuntos são representados por círculos que se cruzam. A operação AND (&) é a interseção de círculos, e a operação OR (|) é a união dos círculos.

Por exemplo, denotemos por círculos os conjuntos de maçãs, pêras e bananas. Para Maçãs, Peras e Bananas, a interseção (parte comum) de todos os três círculos será selecionada:

A pedido Maçãs | Pears irá selecionar a união de dois círculos:

Exemplo 2.

A tabela mostra as solicitações e o número de páginas que o servidor de pesquisa encontrou para essas solicitações em um determinado segmento da Internet:

Quantas páginas (em milhares) a pesquisa de xadrez será encontrada?

Decisão:

Vamos desenhar um diagrama de Euler-Venn. A solução do problema consiste em contar o número de páginas correspondente a cada área delimitada pelas linhas:

A consulta de xadrez e tênis corresponde à região do meio (1000 mil páginas), e a consulta de tênis corresponde a todo o círculo direito (5500 mil páginas).

Então, o "círculo recortado" certo é 5500-1000 \u003d 4500:

Pedido de xadrez | tênis corresponde a ambos os círculos (7770), então o "círculo recortado" à esquerda é 7770-5500 \u003d 2270

Um circuito elétrico projetado para realizar qualquer operação lógica com dados de entrada é chamado de elemento lógico. Os dados de entrada são representados aqui na forma de tensões de vários níveis, e o resultado de uma operação lógica na saída também é obtido na forma de uma tensão de um determinado nível.

Nesse caso, os operandos são fornecidos - sinais na forma de alta ou baixa tensão são recebidos na entrada do elemento lógico, que servem essencialmente como dados de entrada. Portanto, a tensão de nível alto - este é 1 lógico - denota o valor verdadeiro do operando, e a tensão de nível baixo 0 - o valor falso. 1 - VERDADEIRO, 0 - FALSO.

Elemento lógico - um elemento que implementa uma certa relação lógica entre os sinais de entrada e saída. Elementos lógicos são normalmente usados \u200b\u200bpara construir circuitos lógicos de computadores, controle automático discreto e circuitos de gerenciamento. Todos os tipos de elementos lógicos, independentemente de sua natureza física, são caracterizados por valores discretos de sinais de entrada e saída.

As portas lógicas têm uma ou mais entradas e uma ou duas saídas (geralmente inversas). Os valores de "zeros" e "uns" dos sinais de saída de elementos lógicos são determinados pela função lógica, que o elemento executa, e os valores de "zeros" e "uns" dos sinais de entrada, que desempenham o papel de variáveis \u200b\u200bindependentes. Existem elementares funções lógicas, a partir do qual você pode compor qualquer função lógica complexa.

Dependendo do dispositivo do circuito do elemento, em seus parâmetros elétricos, os níveis lógicos (níveis de alta e baixa tensão) de entrada e saída têm os mesmos valores para os estados alto e baixo (verdadeiro e falso).

Tradicionalmente, os elementos lógicos são produzidos na forma de componentes especiais de rádio - circuitos integrados. Operações lógicas como conjunção, disjunção, negação e adição de módulo (AND, OR, NOT, OR exclusivo) são as principais operações realizadas em elementos lógicos de tipos básicos. Vamos dar uma olhada mais de perto em cada um desses tipos de portas lógicas.

Elemento lógico "AND" - conjunção, multiplicação lógica, AND

"AND" é um elemento lógico que realiza conjunção ou multiplicação lógica nos dados de entrada. Este elemento pode ter de 2 a 8 (os mais comuns na produção elementos "E" com 2, 3, 4 e 8 entradas) entradas e uma saída.

Os símbolos dos elementos lógicos "E" com um número diferente de entradas são mostrados na figura. No texto, um elemento lógico "AND" com um ou outro número de entradas é designado como "2I", "4I", etc. - um elemento "AND" com duas entradas, com quatro entradas, etc.

A tabela verdade para o elemento 2I mostra que a saída do elemento será uma unidade lógica apenas se as unidades lógicas estiverem simultaneamente na primeira entrada E na segunda entrada. Nos outros três casos possíveis, a saída será zero.

Nos diagramas ocidentais, o ícone do elemento "AND" possui uma linha reta na entrada e um arredondamento na saída. Em esquemas domésticos - um retângulo com um símbolo "&".

Elemento lógico "OU" - disjunção, adição lógica, OU

"OU" é um elemento lógico que realiza uma disjunção ou operação de adição lógica nos dados de entrada. Ele, como o elemento “AND”, é produzido com duas, três, quatro, etc. entradas e uma saída. Os símbolos dos elementos lógicos "OU" com diferentes números de entradas são mostrados na figura. Esses elementos são designados da seguinte forma: 2OR, 3OR, 4OR, etc.

A tabela verdade para o elemento "2OR" mostra que para o aparecimento de uma unidade lógica na saída, basta que a unidade lógica esteja na primeira entrada OU na segunda entrada. Se os lógicos estiverem ao mesmo tempo em duas entradas, a saída também será uma.

Nos diagramas ocidentais, o elemento OR tem uma entrada arredondada e uma saída arredondada. Em esquemas domésticos - um retângulo com o símbolo "1".

Porta lógica "NÃO" - negativo, inversor, NÃO

"NOT" é um elemento lógico que realiza a operação de negação lógica nos dados de entrada. Este elemento, que possui uma saída e apenas uma entrada, também é chamado de inversor, pois na verdade ele inverte (reverte) o sinal de entrada. A figura mostra a designação convencional do elemento lógico "NÃO".

A tabela verdade para o inversor mostra que um potencial de entrada alto dá um potencial de saída baixo e vice-versa.

Nos diagramas ocidentais, o ícone do elemento "NÃO" tem a forma de um triângulo com um círculo na saída. Em esquemas domésticos - um retângulo com o símbolo "1", com um círculo na saída.

Elemento lógico "AND-NOT" - conjunção (multiplicação lógica) com negação, NAND

"AND-NOT" - um elemento lógico que realiza a operação de adição lógica nos dados de entrada e, em seguida, a operação de negação lógica, o resultado é alimentado para a saída. Em outras palavras, é, em princípio, o elemento "AND", complementado pelo elemento "NOT". A figura mostra a designação convencional do elemento lógico "2I-NOT".

A tabela verdade para o elemento AND-NOT é o oposto da tabela AND. Em vez de três zeros e um, existem três uns e um zero. O elemento NAND também é chamado de elemento Schaeffer em homenagem ao matemático Henry Maurice Schaeffer, que primeiro observou a importância disso em 1913. É designado como "E", apenas com um círculo na saída.

Elemento lógico "OU-NÃO" - disjunção (adição lógica) com negação, NOR

"OR-NOT" - um elemento lógico que realiza uma adição lógica nos dados de entrada e, em seguida, uma negação lógica, o resultado é alimentado para a saída. Em outras palavras, é um elemento "OU", complementado por um elemento "NÃO" - um inversor. A figura mostra a designação convencional do elemento lógico "2OR-NOT".

A tabela verdade para o elemento OR-NOT é o oposto da tabela para o elemento OR. Um alto potencial na saída é obtido apenas em um caso - baixos potenciais são aplicados a ambas as entradas simultaneamente. Indicado como “OU”, somente com círculo na saída, indicando inversão.

Porta lógica "OU exclusivo" - módulo de adição 2, XOR

"OU exclusivo" - um elemento lógico que executa uma operação de adição lógica no módulo 2 de dados de entrada, tem duas entradas e uma saída. Esses elementos são freqüentemente usados \u200b\u200bem esquemas de controle. A figura mostra o símbolo para este elemento.

A imagem nos esquemas ocidentais - como em "OU" com uma faixa curva adicional na lateral da entrada, no doméstico - como "OU", somente em vez de "1" será escrita "\u003d 1".

Este elemento lógico também é chamado de "desigualdade". Um nível de alta tensão estará na saída apenas quando os sinais na entrada não forem iguais (em uma unidade, na outra zero, ou em um zero e na outra), mesmo se houver duas unidades ao mesmo tempo na entrada, a saída será zero - esta é a diferença de "OU". Esses elementos lógicos são amplamente usados \u200b\u200bem somadores.

Conjunção ou multiplicação lógica (na teoria dos conjuntos, esta é uma interseção)

Uma conjunção é uma expressão lógica complexa que é verdadeira se e somente se ambas as expressões simples forem verdadeiras. Essa situação só é possível em um único caso, em todos os outros casos a conjunção é falsa.

Designação: &, $ \\ wedge $, $ \\ cdot $.

Tabela da verdade para conjunção

Imagem 1.

Propriedades da conjunção:

1. Se pelo menos uma das subexpressões da conjunção for falsa para algum conjunto de valores das variáveis, toda a conjunção será falsa para esse conjunto de valores.
2. Se todas as expressões de conjunção forem verdadeiras em algum conjunto de valores das variáveis, então toda a conjunção também será verdadeira.
3. O significado de toda a conjunção de uma expressão complexa não depende da ordem de escrita das subexpressões às quais ela é aplicada (como na matemática, multiplicação).

Disjunção ou adição lógica (na teoria dos conjuntos, esta é uma união)

Disjunção é uma expressão lógica complexa que quase sempre é verdadeira, exceto quando todas as expressões são falsas.

Designação: +, $ \\ vee $.

Tabela da verdade para disjunção

Figura 2.

Propriedades de disjunção:

1. Se pelo menos uma das subexpressões de disjunção for verdadeira em algum conjunto de valores das variáveis, então a disjunção inteira assume um valor verdadeiro para este conjunto subexpressões.
2. Se todas as expressões de uma certa lista de disjunções são falsas em um certo conjunto de valores de variáveis, então toda a disjunção dessas expressões também é falsa.
3. O significado de toda a disjunção não depende da ordem de escrita das subexpressões (como na matemática - adição).

Negação, negação lógica ou inversão (na teoria dos conjuntos, isso é negação)

Negação - significa que a partícula NÃO ou a palavra ERRADO é adicionada à expressão lógica original, O QUE, e como resultado, obtemos que, se a expressão original for verdadeira, a negação da original será falsa, e vice-versa, se a expressão original for falsa, então sua negação será verdadeira.

Notação: não $ A $, $ \\ bar (A) $, $ ¬A $.

Tabela verdade para inversão

Figura 3.

Propriedades de negação:

A "negação dupla" $ ¬¬A $ é uma consequência do julgamento $ A $, ou seja, existe uma tautologia na lógica formal e é igual ao próprio valor na lógica booleana.

Implicação ou consequência lógica

A implicação é uma expressão lógica complexa que é verdadeira em todos os casos, exceto pelo fato de que a verdade segue falsa. Ou seja, essa operação lógica conecta duas expressões lógicas simples, das quais a primeira é uma condição ($ A $) e a segunda ($ A $) é uma consequência da condição ($ A $).

Designações: $ \\ to $, $ \\ Rightarrow $.

Tabela verdade para implicação

Figura 4.

Propriedades de implicação:

1. $ A \\ para B \u003d ¬A \\ vee B $.
2. A implicação $ A \\ para B $ é falsa se $ A \u003d 1 $ e $ B \u003d 0 $.
3. Se $ A \u003d 0 $, então a implicação $ A \\ para B $ é verdadeira para qualquer valor de $ B $, (a mentira pode seguir verdadeira).

Equivalência ou equivalência lógica

Equivalência é uma expressão booleana complexa verdadeira para valores iguais de $ A $ e $ B $.

Designações: $ \\ leftrightarrow $, $ \\ Leftrightarrow $, $ \\ equiv $.

Tabela da verdade para equivalência

Figura 5.

Propriedades de equivalência:

1. A equivalência é verdadeira em conjuntos iguais de valores das variáveis \u200b\u200b$ A $ e $ B $.
2. CNF $ A \\ equiv B \u003d (\\ bar (A) \\ vee B) \\ cdot (A \\ cdot \\ bar (B)) $
3. DNF $ A \\ equiv B \u003d \\ bar (A) \\ cdot \\ bar (B) \\ vee A \\ cdot B $

Disjunção estrita ou modo de adição 2 (na teoria dos conjuntos, esta é a união de dois conjuntos sem sua interseção)

A disjunção forte é verdadeira se os valores do argumento não forem iguais.

Para a eletrônica, isso significa que a implementação de circuitos é possível usando um elemento típico (embora este seja um elemento caro).

A ordem de execução das operações lógicas em uma expressão lógica complexa

1. Inversão (negação);
2. Conjunção (multiplicação lógica);
3. Disjunção e disjunção estrita (adição lógica);
4. Implicação (consequência);
5. Equivalência (identidade).

Para alterar a ordem especificada de execução das operações lógicas, você deve usar parênteses.

Propriedades gerais

Para um conjunto de $ n $ variáveis \u200b\u200bbooleanas, existem exatamente $ 2 ^ n $ valores distintos. A tabela verdade para uma expressão booleana de $ n $ variáveis \u200b\u200bcontém $ n + 1 $ colunas e $ 2 ^ n $ linhas.

PROPRIEDADES DE OPERAÇÕES LÓGICAS

1. Notação

1.1. Símbolos para conectivos lógicos (operações):

a) negação (inversão, NOT lógico) é denotado por ¬ (por exemplo, ¬A);

b) conjunção (multiplicação lógica, AND lógico) é denotado / \\
(por exemplo, A / \\ B) ou & (por exemplo, A & B);

c) disjunção (adição lógica, OR lógico) é denotado por \\ /
(por exemplo, A \\ / B);

d) segue (implicação) é denotado por → (por exemplo, A → B);

e) identidadedenotado por ≡ (por exemplo, A ≡ B). A expressão A ≡ B é verdadeira se e somente se os valores de A e B são iguais (ou são ambos verdadeiros ou ambos são falsos);

f) o símbolo 1 é usado para denotar a verdade (afirmação verdadeira); símbolo 0 - para denotar uma mentira (declaração falsa).

1.2. As duas expressões booleanas contendo variáveis \u200b\u200bsão chamadas equivalente (equivalente) se os valores dessas expressões coincidem para quaisquer valores das variáveis. Assim, as expressões A → B e (¬A) \\ / B são equivalentes, mas A / \\ B e A \\ / B não (os valores das expressões são diferentes, por exemplo, para A \u003d 1, B \u003d 0).

1.3. Prioridade booleana: inversão (negação), conjunção (multiplicação lógica), disjunção (adição lógica), implicação (seguinte), identidade. Assim, ¬A \\ / B \\ / C \\ / D significa o mesmo que

((¬A) \\ / B) \\ / (C \\ / D).

É possível escrever A \\ / B \\ / C em vez de (A \\ / B) \\ / C. O mesmo se aplica à conjunção: é possível escrever A / \\ B / \\ C em vez de (A / \\ B) / \\ C.

2. Propriedades

A lista abaixo NÃO pretende ser completa, mas sim representativa o suficiente.

2.1. Propriedades gerais

1. Para um conjunto de nvariáveis \u200b\u200bbooleanas existem exatamente 2 n valores diferentes. Tabela verdade para expressão booleana de nvariáveis \u200b\u200bcontém n + 1coluna e 2 nlinhas.

2.2 Disjunção

1. Se pelo menos uma das subexpressões às quais a disjunção é aplicada for verdadeira em algum conjunto de valores das variáveis, então toda a disjunção também será verdadeira para esse conjunto de valores.
2. Se todas as expressões de uma certa lista são verdadeiras em um certo conjunto de valores de variáveis, então a disjunção dessas expressões também é verdadeira.
3. Se todas as expressões de uma certa lista são falsas em um certo conjunto de valores de variáveis, então a disjunção dessas expressões também é falsa.
4. O significado da disjunção é independente da ordem de escrita das subexpressões às quais ela é aplicada.

2.3. Conjunção

1. Se pelo menos uma das subexpressões às quais a conjunção é aplicada for falsa para algum conjunto de valores das variáveis, a conjunção inteira também será falsa para esse conjunto de valores.
2. Se todas as expressões de alguma lista forem verdadeiras em algum conjunto de valores de variáveis, a conjunção dessas expressões também será verdadeira.
3. Se todas as expressões de uma determinada lista forem falsas em um determinado conjunto de valores de variáveis, a conjunção dessas expressões também será falsa.
4. O significado de uma conjunção não depende da ordem de escrita das subexpressões às quais ela é aplicada.

2.4. Disjunções e conjunções simples

Vamos chamar (por conveniência) a conjunção aviãose as subexpressões às quais a conjunção se aplica forem variáveis \u200b\u200bdistintas ou suas negações. Da mesma forma, uma disjunção é chamada aviãose as subexpressões às quais a disjunção é aplicada são variáveis \u200b\u200bdistintas ou suas negações.

1. Uma conjunção simples assume o valor 1 (verdadeiro) em exatamente um conjunto de valores de variáveis.
2. A disjunção simples assume o valor 0 (falso) em exatamente um conjunto de valores de variáveis.

2,5. Implicação

1. Implicação UMA →Bé equivalente a disjunção (¬ A) \\ / B.Essa disjunção pode ser escrita assim: ¬ A \\ / B.
2. Implicação UMA →Bassume o valor 0 (falso) apenas se A \u003d 1e B \u003d 0. E se A \u003d 0,então a implicação UMA →Bverdadeiro para qualquer valor B.