Instituição de ensino orçamentária municipal

"Escola secundária nº 18"

distrito urbano da cidade de Salavat da República do Bascortostão

Sistemas de equações lógicas

nas tarefas do exame em informática

A seção "Fundamentos de Álgebra da Lógica" nas tarefas do exame é considerada uma das mais difíceis e mal resolvidas. A porcentagem média de conclusão de tarefas neste tópico é a mais baixa e é de 43,2.

Seção do curso	Porcentagem média de conclusão por grupos de tarefas
Codificando informações e medindo sua quantidade
modelagem de informações
Sistemas numéricos
Fundamentos de Álgebra da Lógica
Algoritmização e programação
Fundamentos das Tecnologias de Informao e Comunicao

Baseado na especificação do KIM 2018, este bloco inclui quatro tarefas de diferentes níveis de complexidade.

№ tarefas	Verificado elementos de conteúdo	Nível de dificuldade da tarefa
	Capacidade de construir tabelas verdade e circuitos lógicos
	Capacidade de pesquisar informações na Internet
	Conhecimento de conceitos básicos e leis lógica matemática
	Capacidade de construir e transformar expressões lógicas

A tarefa 23 é um nível de dificuldade alto, portanto, tem o menor percentual de conclusão. Entre os egressos treinados (81-100 pontos) 49,8% concluíram a tarefa, os preparados medianamente (61-80 pontos) lidam com 13,7%, o restante grupo de alunos não conclui esta tarefa.

O sucesso da resolução de um sistema de equações lógicas depende do conhecimento das leis da lógica e da aplicação precisa de métodos para resolver o sistema.

Considere a solução de um sistema de equações lógicas pelo método de mapeamento.

(23.154 Polyakov K.Yu.) Quantas soluções diferentes o sistema de equações tem?

((x1  y1 )  (x2  y2 ))  (x1  x2 )  (s1  y2 ) =1

((x2  y2 )  (x3  y3 ))  (x2  x3 )  (s2  y3 ) =1

((x7  y7 )  (x8  y8 ))  (x7  x8 )  (y7  y8 ) =1

Onde x1 , x2 ,…, x8, no1 ,y2 ,…,s8 - Variáveis ​​booleanas? A resposta não precisa listar todos os diferentes conjuntos de valores de variáveis ​​para os quais essa igualdade vale. Como resposta, você precisa indicar o número de tais conjuntos.

Solução. Todas as equações incluídas no sistema são do mesmo tipo e quatro variáveis ​​são incluídas em cada equação. Conhecendo x1 e y1, podemos encontrar todos os valores possíveis de x2 e y2 que satisfaçam a primeira equação. Argumentando de maneira semelhante, a partir dos conhecidos x2 e y2 podemos encontrar x3, y3 que satisfaz a segunda equação. Ou seja, conhecendo o par (x1, y1) e determinando o valor do par (x2, y2), encontraremos o par (x3, y3), que por sua vez levará ao par (x4, y4) e assim sobre.

Vamos encontrar todas as soluções da primeira equação. Isso pode ser feito de duas maneiras: construir uma tabela-verdade, por meio do raciocínio e da aplicação das leis da lógica.

Tabela verdade:

				x 1  1	x2  ano 2	(x 1  1)  (x 2  2)	(x 1  x2)	(s 1  2)	(x 1  x2)  (s 1  2)

Construir uma tabela verdade é trabalhoso e ineficiente em termos de tempo, então usamos o segundo método - raciocínio lógico. O produto é 1 se e somente se cada fator for 1.

(x1  y1 )  (x2  y2 ))=1

(x1  x2 ) =1

(y1  y2 ) =1

Considere a primeira equação. A seguir é igual a 1, quando 0 0, 0 1, 1 1, então (x1 y1)=0 em (01), (10), então o par (x2  y2 ) pode ser qualquer (00), (01), (10), (11), e para (x1 y1)=1, ou seja, (00) e (11) o par (x2 y2)=1 assume os mesmos valores (00) e (11). Excluímos desta solução aqueles pares para os quais a segunda e a terceira equações são falsas, ou seja, x1=1, x2=0, y1=1, y2=0.

(x1 , y1 )	(x2 , y2 )

Número total de pares 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) Quantas soluções diferentes um sistema de equações lógicas tem?

(x 1  (x 2  y 2 ))  (s 1  y 2 ) = 1

(x 2  (x 3  y 3 ))  (s 2  y 3 ) = 1

...

( x 6  ( x 7  y 7 ))  ( y 6  y 7 ) = 1

x 7  y 7 = 1

Solução. 1) As equações são do mesmo tipo, então pelo método de raciocínio encontraremos todos os pares possíveis (x1,y1), (x2,y2) da primeira equação.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

A solução da segunda equação são os pares (00), (01), (11).

Vamos encontrar soluções para a primeira equação. Se x1=0, então x2, y2 - qualquer, se x1=1, então x2, y2 assume o valor (11).

Vamos fazer conexões entre os pares (x1 , y1) e (x2 , y2).

(x1 , y1 )	(x2 , y2 )

Vamos fazer uma tabela para calcular o número de pares em cada etapa.

							0

Levando em conta as soluções da última equação x 7  y 7 = 1, eliminamos o par (10). Encontre o número total de soluções 1+7+0+34=42

3)(23.180) Quantas soluções diferentes o sistema de equações lógicas tem

(x1  x2 )  (x3  x4 ) = 1

(x3  x4 )  (x5  x6 ) = 1

(x5  x6 )  (x7  x8 ) = 1

(x7  x8 )  (x9  x10 ) = 1

x1  x3  x5  x7  x9 = 1

Solução. 1) As equações são do mesmo tipo, então pelo método de raciocínio encontraremos todos os pares possíveis (x1,x2), (x3,x4) da primeira equação.

(x1  x2 )  (x3  x4 ) = 1

Excluímos da solução os pares que dão 0 (1 0) a seguir, são os pares (01, 00, 11) e (10).

Compor links entre pares (x1,x2), (x3,x4)

Existem várias maneiras de resolver sistemas de equações lógicas. Esta é uma redução a uma equação, a construção de uma tabela-verdade e decomposição.

Uma tarefa: Resolva um sistema de equações lógicas:

Considerar método de redução a uma equação . Este método envolve a transformação de equações lógicas, de modo que seus lados direitos sejam iguais ao valor de verdade (ou seja, 1). Para fazer isso, use a operação de negação lógica. Então, se houver operações lógicas complexas nas equações, nós as substituímos por básicas: “AND”, “OR”, “NOT”. O próximo passo é combinar as equações em uma, equivalente ao sistema, usando a operação lógica "AND". Depois disso, você deve fazer transformações da equação resultante com base nas leis da álgebra da lógica e obter uma solução específica para o sistema.

Solução 1: Aplique a inversão a ambos os lados da primeira equação:

Vamos representar a implicação através das operações básicas "OR", "NOT":

Como os lados esquerdos das equações são iguais a 1, você pode combiná-los usando a operação “AND” em uma equação equivalente ao sistema original:

Abrimos o primeiro colchete de acordo com a lei de Morgan e transformamos o resultado:

A equação resultante tem uma solução: A=0, B=0 e C=1.

A próxima maneira é construção de tabelas verdade . Como os valores lógicos têm apenas dois valores, você pode simplesmente percorrer todas as opções e encontrar entre elas aquelas para as quais o sistema de equações fornecido é satisfeito. Ou seja, construímos uma tabela-verdade comum para todas as equações do sistema e encontramos uma linha com os valores desejados.

Solução 2: Vamos fazer uma tabela verdade para o sistema:

0	0	1	1	0	1

Negrito é a linha para a qual as condições do problema são atendidas. Então A=0, B=0 e C=1.

Caminho decomposição . A ideia é fixar o valor de uma das variáveis ​​(colocá-la igual a 0 ou 1) e assim simplificar as equações. Então você pode corrigir o valor da segunda variável e assim por diante.

Solução 3: Seja A = 0, então:

Da primeira equação obtemos B = 0 e da segunda - С=1. Solução do sistema: A = 0, B = 0 e C = 1.

No USE em ciência da computação, muitas vezes é necessário determinar o número de soluções para um sistema de equações lógicas, sem encontrar as próprias soluções, também existem certos métodos para isso. A principal maneira de encontrar o número de soluções para um sistema de equações lógicas émudança de variáveis. Primeiro, é necessário simplificar cada uma das equações o máximo possível com base nas leis da álgebra da lógica e, em seguida, substituir as partes complexas das equações por novas variáveis ​​e determinar o número de soluções para o novo sistema. Em seguida, retorne à substituição e determine o número de soluções para ela.

Uma tarefa: Quantas soluções tem a equação (A → B ) + (C → D ) = 1? Onde A, B, C, D são variáveis ​​booleanas.

Solução: Vamos introduzir novas variáveis: X = A → B e Y = C → D . Levando em conta as novas variáveis, a equação será escrita na forma: X + Y = 1.

A disjunção é verdadeira em três casos: (0;1), (1;0) e (1;1), enquanto X e Y são uma implicação, ou seja, é verdadeira em três casos e falsa em um. Portanto, o caso (0;1) corresponderá a três combinações possíveis de parâmetros. Caso (1;1) - corresponderá a nove combinações possíveis dos parâmetros da equação original. Portanto, existem 3+9=15 soluções possíveis para esta equação.

A seguinte maneira de determinar o número de soluções para um sistema de equações lógicas é - árvore binária. Vamos considerar este método com um exemplo.

Uma tarefa: Quantas soluções diferentes o sistema de equações lógicas tem:

O sistema de equações dado é equivalente à equação:

(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.

Vamos fingir que x 1 é verdade, então da primeira equação obtemos que x 2 também é verdade, a partir do segundo - x 3 =1 e assim sucessivamente até x m= 1. Isso significa que o conjunto (1; 1; …; 1) de m unidades é a solução do sistema. Vamos agora x 1 =0, então da primeira equação temos x 2 =0 ou x 2 =1.

Quando x 2 verdadeiro, obtemos que as demais variáveis ​​também são verdadeiras, ou seja, o conjunto (0; 1; ...; 1) é a solução do sistema. No x 2 =0 temos isso x 3 =0 ou x 3 =, e assim por diante. Continuando para a última variável, obtemos que as soluções da equação são os seguintes conjuntos de variáveis ​​(m + 1 solução, cada solução tem m valores de variáveis):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Essa abordagem é bem ilustrada pela construção de uma árvore binária. O número de soluções possíveis é o número de ramos diferentes da árvore construída. É fácil ver que é igual a m + 1.

	Madeira	Número de decisões
x 1
x2
x 3
		…

Em caso de dificuldades de raciocínio niyah e construção derugido de soluções, você pode procurar uma solução com usando tabelas verdade, para uma ou duas equações.

Reescrevemos o sistema de equações na forma:

E vamos fazer uma tabela-verdade separadamente para uma equação:

x 1	x2	(x 1 → x 2)

Vamos fazer uma tabela verdade para duas equações:

x 1	x2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) * (x 2 → x 3)

Tópico da lição: Resolvendo equações lógicas

Educacional - aprender a resolver equações lógicas, a formação de habilidades e habilidades para resolver equações lógicas e construir uma expressão lógica de acordo com a tabela-verdade;

Educacional - criar condições para o desenvolvimento do interesse cognitivo dos alunos, promover o desenvolvimento da memória, atenção, raciocínio lógico;

Educacional : contribuir para a educação da capacidade de ouvir as opiniões dos outros, educação da vontade e perseverança para alcançar os resultados finais.

Tipo de aula: lição combinada

Equipamento: computador, projetor multimídia, apresentação 6.

Durante as aulas

Repetição e atualização de conhecimentos básicos. Verificando a lição de casa (10 minutos)

Nas lições anteriores, nos familiarizamos com as leis básicas da álgebra da lógica, aprendemos como usar essas leis para simplificar expressões lógicas.

Vamos verificar a lição de casa sobre simplificação de expressões lógicas:

1. Qual das seguintes palavras satisfaz a condição lógica:

(primeira consoante → segunda consoante)٨ (vogal da última letra → vogal da penúltima letra)? Se houver várias dessas palavras, indique a menor delas.

1) ANNA 2) MARIA 3) OLEG 4) STEPAN

Vamos introduzir a notação:

A é a primeira letra de uma consoante

B é a segunda letra de uma consoante

S é a última vogal

D - penúltima vogal

Vamos fazer uma expressão:

Vamos fazer uma tabela:

2. Indique qual expressão lógica é equivalente à expressão

Vamos simplificar a escrita da expressão original e as opções propostas:

3. Um fragmento da tabela verdade da expressão F é dado:

Que expressão corresponde a F?

Vamos determinar os valores dessas expressões para os valores especificados dos argumentos:

Familiarização com o tópico da lição, apresentação de novo material (30 minutos)

Continuamos a estudar os fundamentos da lógica e o tópico da nossa lição de hoje "Resolvendo equações lógicas". Depois de estudar este tópico, você aprenderá as maneiras básicas de resolver equações lógicas, obterá as habilidades para resolver essas equações usando a linguagem da álgebra lógica e a capacidade de compor uma expressão lógica na tabela-verdade.

1. Resolva a equação lógica

(¬K M) → (¬L M N)=0

Escreva sua resposta como uma string de quatro caracteres: os valores das variáveis ​​K, L, M e N (nessa ordem). Assim, por exemplo, a linha 1101 corresponde a K=1, L=1, M=0, N=1.

Solução:

Vamos transformar a expressão(¬K  M) → (¬L  M  N)

A expressão é falsa quando ambos os termos são falsos. O segundo termo é igual a 0 se M=0, N=0, L=1. No primeiro termo, K = 0, já que M = 0, e
.

Resposta: 0100

2. Quantas soluções tem a equação (indique apenas o número na sua resposta)?

Solução: transforme a expressão

(A+B)*(C+D)=1

A+B=1 e C+D=1

Método 2: compilando uma tabela verdade

3 vias: construção de SDNF - uma forma normal disjuntiva perfeita para uma função - uma disjunção de conjunções elementares regulares completas.

Vamos transformar a expressão original, abra os colchetes para obter a disjunção das conjunções:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Vamos complementar as conjunções para completar as conjunções (o produto de todos os argumentos), abra os colchetes:

Considere as mesmas conjunções:

Como resultado, obtemos um SDNF contendo 9 conjunções. Portanto, a tabela verdade para esta função tem um valor de 1 em 9 linhas de 2 4 =16 conjuntos de valores de variáveis.

3. Quantas soluções tem a equação (indique apenas o número na sua resposta)?

Vamos simplificar a expressão:

,

3 vias: construção do SDNF

Considere as mesmas conjunções:

Como resultado, obtemos um SDNF contendo 5 conjunções. Portanto, a tabela verdade para esta função tem um valor de 1 em 5 linhas de 2 4 =16 conjuntos de valores de variáveis.

Construindo uma expressão lógica de acordo com a tabela verdade:

para cada linha da tabela verdade contendo 1, compomos o produto dos argumentos, e as variáveis ​​iguais a 0 são incluídas no produto com negação, e as variáveis ​​iguais a 1 não são negadas. A expressão desejada F será composta pela soma dos produtos obtidos. Então, se possível, essa expressão deve ser simplificada.

Exemplo: a tabela verdade de uma expressão é dada. Construir uma expressão lógica.

Solução:

3. Dever de casa (5 minutos)

Resolva a equação:

Quantas soluções tem a equação (responda apenas o número)?

De acordo com a tabela-verdade dada, faça uma expressão lógica e

simplificá-lo.

Formas de resolver sistemas de equações lógicas

Kirgizova E.V., Nemkova A.E.

Instituto Pedagógico de Lesosibirsk -

filial da Universidade Federal da Sibéria, Rússia

A capacidade de pensar consistentemente, argumentar conclusivamente, construir hipóteses, refutar conclusões negativas, não vem por si só, essa habilidade é desenvolvida pela ciência da lógica. A lógica é uma ciência que estuda os métodos para estabelecer a verdade ou falsidade de algumas afirmações com base na verdade ou falsidade de outras afirmações.

Dominar os fundamentos desta ciência é impossível sem resolver problemas lógicos. A verificação da formação de habilidades para aplicar seus conhecimentos em uma nova situação é realizada por passagem. Em particular, esta é a capacidade de resolver problemas lógicos. As tarefas B15 do exame são tarefas de maior complexidade, pois contêm sistemas de equações lógicas. Existem várias maneiras de resolver sistemas de equações lógicas. Isso é redução a uma equação, construção de uma tabela-verdade, decomposição, solução sequencial de equações, etc.

Uma tarefa:Resolva um sistema de equações lógicas:

Considerar método de redução a uma equação . Este método envolve a transformação de equações lógicas, de modo que seus lados direitos sejam iguais ao valor de verdade (ou seja, 1). Para fazer isso, use a operação de negação lógica. Então, se houver operações lógicas complexas nas equações, nós as substituímos por básicas: “AND”, “OR”, “NOT”. O próximo passo é combinar as equações em uma, equivalente ao sistema, usando a operação lógica "AND". Depois disso, você deve fazer transformações da equação resultante com base nas leis da álgebra da lógica e obter uma solução específica para o sistema.

Solução 1:Aplique a inversão a ambos os lados da primeira equação:

Vamos representar a implicação através das operações básicas "OR", "NOT":

Como os lados esquerdos das equações são iguais a 1, você pode combiná-los usando a operação “AND” em uma equação equivalente ao sistema original:

Abrimos o primeiro colchete de acordo com a lei de Morgan e transformamos o resultado:

A equação resultante tem uma solução: A= 0, B=0 e C=1.

A próxima maneira é construção de tabelas verdade . Como os valores lógicos têm apenas dois valores, você pode simplesmente percorrer todas as opções e encontrar entre elas aquelas para as quais o sistema de equações fornecido é satisfeito. Ou seja, construímos uma tabela-verdade comum para todas as equações do sistema e encontramos uma linha com os valores desejados.

Solução 2:Vamos fazer uma tabela verdade para o sistema:

0	0	1	1	0	1

Negrito é a linha para a qual as condições do problema são atendidas. Então A = 0 , B = 0 e C = 1 .

Caminho decomposição . A ideia é fixar o valor de uma das variáveis ​​(colocá-la igual a 0 ou 1) e assim simplificar as equações. Então você pode corrigir o valor da segunda variável e assim por diante.

Solução 3: Deixar A = 0, então:

Da primeira equação obtemos B =0, e a partir do segundo - С=1. Solução do sistema: A = 0 , B = 0 e C = 1 .

Você também pode usar o método solução sequencial de equações , adicionando uma variável ao conjunto em consideração em cada etapa. Para isso, é necessário transformar as equações de forma que as variáveis ​​sejam inseridas em ordem alfabética. Em seguida, construímos uma árvore de decisão, adicionando variáveis ​​sequencialmente a ela.

A primeira equação do sistema depende apenas de A e B, e a segunda equação de A e C. A variável A pode assumir 2 valores 0 e 1:

Segue da primeira equação que , então quando A = 0 temos B = 0 , e para A = 1 temos B = 1 . Assim, a primeira equação tem duas soluções em relação às variáveis ​​A e B .

Desenhamos a segunda equação, a partir da qual determinamos os valores de C para cada opção. Para A = 1, a implicação não pode ser falsa, ou seja, o segundo ramo da árvore não tem solução. No A= 0 temos a única solução C= 1 :

Assim, temos a solução do sistema: A = 0 , B = 0 e C = 1 .

No USE em ciência da computação, muitas vezes é necessário determinar o número de soluções para um sistema de equações lógicas, sem encontrar as próprias soluções, também existem certos métodos para isso. A principal maneira de encontrar o número de soluções para um sistema de equações lógicas é mudança de variáveis. Primeiro, é necessário simplificar cada uma das equações o máximo possível com base nas leis da álgebra da lógica e, em seguida, substituir as partes complexas das equações por novas variáveis ​​e determinar o número de soluções para o novo sistema. Em seguida, retorne à substituição e determine o número de soluções para ela.

Uma tarefa:Quantas soluções a equação ( A → B ) + (C → D ) = 1? Onde A, B, C, D são variáveis ​​booleanas.

Solução:Vamos introduzir novas variáveis: X = A → B e Y = C → D . Levando em conta as novas variáveis, a equação pode ser escrita como: X + Y = 1.

A disjunção é verdadeira em três casos: (0;1), (1;0) e (1;1), enquanto X e Y é uma implicação, ou seja, é verdadeira em três casos e falsa em um. Portanto, o caso (0;1) corresponderá a três combinações possíveis de parâmetros. Caso (1;1) - corresponderá a nove combinações possíveis dos parâmetros da equação original. Portanto, existem 3+9=15 soluções possíveis para esta equação.

A seguinte maneira de determinar o número de soluções para um sistema de equações lógicas é - árvore binária. Vamos considerar este método com um exemplo.

Uma tarefa:Quantas soluções diferentes o sistema de equações lógicas tem:

O sistema de equações dado é equivalente à equação:

( x 1 → x 2 )*( x 2 → x 3 )*…*( x m -1 → x m) = 1.

Vamos fingir quex 1 é verdade, então da primeira equação obtemos quex 2 também é verdade, a partir do segundo -x 3 =1 e assim sucessivamente até x m= 1. Daí o conjunto (1; 1; …; 1) de m unidades é a solução do sistema. Vamos agorax 1 =0, então da primeira equação temosx 2 =0 ou x 2 =1.

Quando x 2 verdadeiro, obtemos que as demais variáveis ​​também são verdadeiras, ou seja, o conjunto (0; 1; ...; 1) é a solução do sistema. Nox 2 =0 temos isso x 3 =0 ou x 3 =, e assim por diante. Continuando para a última variável, descobrimos que as soluções para a equação são os seguintes conjuntos de variáveis ​​( m +1 solução, em cada solução m valores variáveis):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Essa abordagem é bem ilustrada pela construção de uma árvore binária. O número de soluções possíveis é o número de ramos diferentes da árvore construída. É fácil ver que é m+1.

Variáveis	Madeira	Número de decisões
x 1
x2
x 3

Em caso de dificuldades de raciocínio e construção de uma árvore de decisão, você pode procurar uma solução usando tabelas verdade, para uma ou duas equações.

Reescrevemos o sistema de equações na forma:

E vamos fazer uma tabela-verdade separadamente para uma equação:

x 1	x2	(x 1 → x 2)

Vamos fazer uma tabela verdade para duas equações:

x 1	x2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) * (x 2 → x 3)

Em seguida, você pode ver que uma equação é verdadeira nos três casos a seguir: (0; 0), (0; 1), (1; 1). O sistema de duas equações é verdadeiro em quatro casos (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). Nesse caso, fica imediatamente claro que existe uma solução que consiste apenas em zeros e mais m soluções nas quais uma unidade é adicionada, começando da última posição até que todas as vagas possíveis sejam preenchidas. Pode-se supor que a solução geral terá a mesma forma, mas para que tal abordagem se torne uma solução, é necessária a prova de que a suposição é verdadeira.

Resumindo todos os itens acima, gostaria de chamar a atenção para o fato de que nem todos os métodos considerados são universais. Ao resolver cada sistema de equações lógicas, suas características devem ser levadas em consideração, com base nas quais o método de solução deve ser escolhido.

Literatura:

1. Tarefas lógicas / O.B. Bogomolov - 2ª ed. – M.: BINOM. Laboratório do Conhecimento, 2006. - 271 p.: ll.

2. Polyakov K.Yu. Sistemas de equações lógicas / Jornal educativo e metódico para professores de informática: Informática nº 14, 2011

Métodos para resolver sistemas de equações lógicas

Você pode resolver um sistema de equações lógicas, por exemplo, usando uma tabela-verdade (se o número de variáveis ​​não for muito grande) ou usando uma árvore de decisão, após simplificar cada equação.

1. Método de mudança de variáveis.

A introdução de novas variáveis ​​permite simplificar o sistema de equações reduzindo o número de incógnitas.Novas variáveis ​​devem ser independentes umas das outras. Após resolver o sistema simplificado, é necessário retornar novamente às variáveis ​​originais.

Considere a aplicação deste método em um exemplo específico.

Exemplo.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Solução:

Vamos introduzir novas variáveis: А=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Atenção! Cada uma de suas variáveis ​​x1, x2, ..., x10 deve ser incluída em apenas uma das novas variáveis ​​A, B, C, D, E, ou seja, as novas variáveis ​​são independentes umas das outras).

Então o sistema de equações ficará assim:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Vamos construir uma árvore de decisão do sistema resultante:

Considere a equação A=0, ou seja (X1≡ X2)=0. Possui 2 raízes:

		X1 ≡ X2

Na mesma tabela, pode-se ver que a equação A \u003d 1 também possui 2 raízes. Vamos organizar o número de raízes na árvore de decisão:

Para encontrar o número de soluções para um ramo, você precisa multiplicar o número de soluções em cada nível. O ramo esquerdo tem 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 soluções; o ramo direito também tem 32 soluções. Aqueles. todo o sistema tem 32+32=64 soluções.

Resposta: 64.

2. Método de raciocínio.

A complexidade de resolver sistemas de equações lógicas reside no volume da árvore de decisão completa. O método de raciocínio permite que você não construa completamente a árvore inteira, mas ao mesmo tempo entenda quantos galhos ela terá. Vamos considerar este método em exemplos concretos.

Exemplo 1 Quantos conjuntos diferentes de valores de variáveis ​​booleanas x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 existem que satisfazem todas as seguintes condições?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

x1\/y1 =1

A resposta não precisa listar todos os diferentes conjuntos de valores das variáveis ​​x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 sob os quais o determinado sistema de igualdades é satisfeito. Como resposta, você precisa indicar o número de tais conjuntos.

Solução:

A primeira e a segunda equações contêm variáveis ​​independentes que são relacionadas por uma terceira condição. Vamos construir uma árvore de decisão para a primeira e segunda equações.

Para representar a árvore de decisão do sistema a partir da primeira e segunda equações, é necessário continuar cada ramo da primeira árvore com uma árvore para variáveis no . A árvore construída desta forma conterá 36 ramos. Alguns desses ramos não satisfazem a terceira equação do sistema. Anote na primeira árvore o número de ramos da árvore"no" , que satisfazem a terceira equação:

Vamos esclarecer: para o cumprimento da terceira condição em x1=0 deve haver y1=1, ou seja, todos os ramos da árvore"X" , onde x1=0 pode ser continuado com apenas um galho da árvore"no" . E apenas para um galho da árvore"X" (direita) caber todos os ramos da árvore"no". Assim, a árvore completa de todo o sistema contém 11 ramos. Cada ramo representa uma solução para o sistema de equações original. Portanto, todo o sistema tem 11 soluções.

Resposta: 11.

Exemplo 2 Quantas soluções diferentes tem o sistema de equações

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬X10)= 1

(X1 ≡ X10) = 0

onde x1, x2, …, x10 são variáveis ​​booleanas? A resposta não precisa listar todos os diferentes conjuntos de valores de variáveis ​​para os quais essa igualdade vale. Como resposta, você precisa indicar o número de tais conjuntos.

Solução: Vamos simplificar o sistema. Vamos construir uma tabela verdade da parte da primeira equação:

		X1 ∧ X10	¬X1 ∧ ¬X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬X10)

Preste atenção na última coluna, ela corresponde ao resultado da ação X1 ≡ X10.

X1 ≡ X10

Após simplificação, obtemos:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Considere a última equação:(X1 ≡ X10) = 0, ou seja. x1 não deve ser o mesmo que x10. Para que a primeira equação seja igual a 1, a igualdade deve valer(X1 ≡ X2)=1, ou seja. x1 deve corresponder a x2.

Vamos construir uma árvore de decisão para a primeira equação:

Considere a segunda equação: para x10=1 e para x2=0 o colchetedeve ser igual a 1 (ou seja, x2 é o mesmo que x3); em x10=0 e em x2=1 colchete(X2 ≡ X10)=0 , então colchete (X2 ≡ X3) deve ser igual a 1 (ou seja, x2 é o mesmo que x3):

Argumentando desta forma, construímos uma árvore de decisão para todas as equações:

Assim, o sistema de equações tem apenas 2 soluções.

Resposta: 2.

Exemplo 3

Quantos conjuntos diferentes de valores de variáveis ​​booleanas x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 existem que satisfazem todas as seguintes condições?

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Solução:

Vamos construir uma árvore de decisão da 1ª equação:

Considere a segunda equação:

• Quando x1=0 : segundo e terceiro colchetes serão 0; para o primeiro colchete ser igual a 1, deve y1=1 , z1=1 (ou seja, neste caso - 1 solução)
• Com x1=1 : o primeiro parêntese será 0; segundo ou o terceiro parêntese deve ser igual a 1; o segundo colchete será igual a 1 quando y1=0 e z1=1; o terceiro colchete será igual a 1 para y1=1 e z1=0 (ou seja, neste caso - 2 soluções).

Da mesma forma para o resto das equações. Observe o número de soluções obtidas para cada nó da árvore:

Para descobrir o número de soluções para cada ramo, multiplicamos os números obtidos separadamente para cada ramo (da esquerda para a direita).

1 ramo: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 solução

2 ramificações: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 soluções

3ª ramificação: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 soluções

4 ramificações: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 soluções

5 ramificações: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 soluções

Vamos somar os números obtidos: um total de 31 soluções.

Resposta: 31.

3. Aumento regular no número de raízes

Em alguns sistemas, o número de raízes da próxima equação depende do número de raízes da equação anterior.

Exemplo 1 Quantos conjuntos diferentes de valores de variáveis ​​booleanas x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 existem que satisfazem todas as seguintes condições?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Simplificar primeira equação:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Então o sistema terá a forma:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

etc.

Cada equação a seguir tem 2 raízes a mais que a anterior.

4 equação tem 12 raízes;

A equação 5 tem 14 raízes

8 equação tem 20 raízes.

Resposta: 20 raízes.

Às vezes, o número de raízes cresce de acordo com a lei dos números de Fibonacci.

Resolver um sistema de equações lógicas requer uma abordagem criativa.