28.Преобразование логических выражений

Преобразование логических выражений.

• если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», потом – «импликация», и самая последняя – «эквиваленция»

• логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)

• логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)

• правила преобразования логических выражений (законы алгебры логики):

Сколько различных решений имеет система логических уравнений

(x₁  x₂)  (x₂  x₃) = 1

x₁  y₁  z₁  x₁  y₁  z₁  x₁  y₁  z₁ = 1

x₂  y₂  z₂  x₂  y₂  z₂  x₂  y₂  z₂ = 1

x₃  y₃  z₃  x₃  y₃  z₃  x₃  y₃  z₃ = 1

где x₁, …, x₃, y₁, …, y₃, z₁, …, z₃ – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение (последовательное подключение уравнений):

1. перепишем уравнения с помощью более простых обозначений:

1. заметим, что последние 3 уравнения независимы друга от друга, и вся система связана только через первое уравнение

2. рассмотрим второе уравнение

оно имеет три решения, каждое из которых соответствует единичному значению одного из слагаемых:

1. аналогичные уравнения 3-4 тоже имеют по три решения

2. теперь рассмотрим множество решений системы уравнений 2-3

при ограничении, которое накладывается первым уравнением:

1. поскольку импликация дает ложное значение (0) только для случая 10, первое уравнение в исходной системе запрещает комбинацию .

2. рассмотрим решение уравнений 2 и 3:

Эти уравнения независимы, поэтому система уравнений 2-3 (без дополнительных ограничений) имеет 33=9 решений

При ограничении :

• в случае имеем только одно решение системы, когда в уравнении  2, то есть

• для двух решений уравнения 3, когда , подходят все 3 отдельных решения уравнения 2

поэтому количество решений системы уравнений 2-3 при ограничении вычисляется как 1 + 3 + 3 = 7 решений

1. рассуждая аналогично, подключаем уравнение 4 и ограничение , получаем, что количество решений системы уравнений 2-4 при ограничении вычисляется как 1 + 7 + 7 = 15 решений

2. Ответ: 15.

Решение (метод отображений, решение А.Н. Носкина):

1. п. 1-4 совпадают с предыдущим вариантом решения

2. построим правило отображения троек переменных.

1 уравнение

2 уравнение

3 уравнение

x₂y₂z₂

x₃y₃z₃

x₁y₁z₁

011

011

011

101

110

101

101

110

110

Если бы не было никаких ограничений, то данная система имела бы 9 решений.

1. так как система имеет ограничения в виде первого уравнения,

(x₁x₂)  (x₂x₃) = 1

то убираем все связи где выше указанные импликации ложны, а именно:

для (x₁x₂): x₁ = 1, x₂ = 0,

(x₂x₃): x₂ = 1, x₃ = 0.

1 уравнение

2 уравнение

3 уравнение

x₂y₂z₂

x₃y₃z₃

x₁y₁z₁

011

011

011

101

110

101

101

110

110

1. Заполняем таблицу, вычисляя количество решений при подключении каждого последующего уравнения.

   xyz	1 уравнение	2 уравнение	3 уравнение
   011	1	1	1
   101	1	3	7
   110	1	3	7

2. Складываем все результаты: 1 + 7 + 7 = 15.

3. Ответ: 15.