Про обозначения

B15 (высокий уровень, время – 10 мин)

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

Про обозначения

К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (Ù, Ú,), неудобны, интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Автор, к своему стыду, до сих пор иногда путает Ù и Ú. Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение).
В разных учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ приводится расшифровка закорючек (Ù, Ú,), что еще раз подчеркивает проблему.

Что нужно знать:

· условные обозначения логических операций

A, не A (отрицание, инверсия)

A Ù B, A и B (логическое умножение, конъюнкция)

A Ú B, A или B (логическое сложение, дизъюнкция)

A → B импликация (следование)

A ↔ B, эквиваленция (эквивалентность, равносильность)

· таблицы истинности логических операций «И», «ИЛИ», «НЕ», «импликация», «эквиваленция» (см. презентацию «Логика»)

· операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

A → B = A Ú B или в других обозначениях A → B =

· операцию «эквиваленция» также можно выразить через «ИЛИ» и «НЕ»:

A ↔ B = A Ù B Ú A Ù B или в других обозначениях A ↔ B =

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

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

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

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

Закон	Для И	Для ИЛИ
двойного отрицания
исключения третьего
исключения констант	A · 1 = A; A · 0 = 0	A + 0 = A; A + 1 = 1
повторения	A · A = A	A + A = A
поглощения	A · (A + B) = A	A + A · B = A
переместительный	A · B = B · A	A + B = B + A
сочетательный	A · (B · C) = (A · B) · C	A + (B + C) = (A + B) + C
распределительный	A + B · C = (A + B) · (A + C)	A · (B + C) = A · B + A · C
де Моргана

Пример задания:

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

(x₁ ® x₂) Ù (x₂ ® x₃) Ù (x₃ ® x₄)= 1

(у₁ ® у₂) Ù (у₂ ® у₃) Ù (у₃ ® у₄) = 1

(Øy₁ Ú x₁) Ù (Øy₂ Ú x₂) Ù (Øy₃ Ú x₃) Ù (Øy₄ Ú x₄) = 1

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

Решение:

1) видим, что первые два уравнения независимы друг от друга (в первое входят только x₁, x₂, …, x₄, а во второе – только y₁, y₂, …, y₄)

2) третье уравнение связывает первые два, поэтому можно поступить так:

· найти решения первого уравнения

· найти решения второго уравнения

· найти множество решений первых двух уравнений

· из множества решений первых двух уравнений выкинуть те, которые не удовлетворяют последнему уравнению

3) найдем решения первого уравнения; каждая из логических переменных x₁, x₂, …, x₄ может принимать только два значения: «ложь» (0) и «истина» (1), поэтому решение первого уравнения можно записать как битовую цепочку длиной 4 бита: например, 0011 означает, что
x₁ = x₂ = 0 и x₃ = x₄ = 1

4) вспомним, что импликация x₁®x₂ ложна только для x₁ = 1 и x₂ = 0, поэтому битовая цепочка, представляющая собой решение первого уравнения, не должна содержать сочетания «10»; это дает такие решения (других нет!):

(x₁, x₂, x₃, x₄) = 0000 0001 0011 0111 1111

5) видим, что второе уравнение полностью совпадает по форме с первым, поэтому все его решения:

(y₁, y₂, y₃, y₄) = 0000 0001 0011 0111 1111

6) поскольку первые два уравнения независимы друг от друга, система из первых двух уравнений имеет 5·5=25 решений: каждому решению первого соответствует 5 разных комбинаций переменных y₁, y₂, …, y₄, которые решают второе, и наоборот, каждому решению второго соответствует 5 разных комбинаций переменных x₁, x₂, …, x₄, которые решают первое:

(y₁, y₂, y₃, y₄) = 0000 0001 0011 0111 1111

(x₁, x₂, x₃, x₄) = 0000 0000 0000 0000 0000

0001 0001 0001 0001 0001

0011 0011 0011 0011 0011

0111 0111 0111 0111 0111

1111 1111 1111 1111 1111

7) теперь проверим, какие ограничения накладывает третье уравнение; вспомнив формулу, которая представляет импликацию через операции «НЕ» и «ИЛИ» (), можно переписать третье уравнение в виде

(y₁ ® x₁) Ù (y₂ ® x₂) Ù (y₃ ® x₃) Ù (y₄ ® x₄) = 1

8) импликация y₁®x₁ ложна только для y₁ = 1 и x₁ = 0, следовательно, такая комбинация запрещена, потому что нарушает третье уравнение; таким образом, набору с y₁ = 1:

(y₁, y₂, y₃, y₄) = 1111

соответствует, с учетом третьего уравнения, только одно решение первого, в котором x₁ = 1

(x₁, x₂, x₃, x₄) = 1111

поэтому множество решений «редеет»:

(y₁, y₂, y₃, y₄) = 0000 0001 0011 0111 1111

(x₁, x₂, x₃, x₄) = 0000 0000 0000 0000

0001 0001 0001 0001

0011 0011 0011 0011

0111 0111 0111 0111

1111 1111 1111 1111 1111

9) аналогично двигаемся дальше по третьему уравнению; второй сомножитель равен 0, если импликация y₂®x₂ ложна, то есть только для y₂ = 1 и x₂ = 0, это «прореживает» предпоследний столбец:

(y₁, y₂, y₃, y₄) = 0000 0001 0011 0111 1111

(x₁, x₂, x₃, x₄) = 0000 0000 0000

0001 0001 0001

0011 0011 0011

0111 0111 0111 0111

1111 1111 1111 1111 1111

10) аналогично проверяем еще два ограничения, отбрасывая все решения, для которых y₃ = 1 и x₃ = 0, а также все решения, для которых y₄ = 1 и x₄ = 0:

(y₁, y₂, y₃, y₄) = 0000 0001 0011 0111 1111

(x₁, x₂, x₃, x₄) = 0000

0001 0001

0011 0011 0011

0111 0111 0111 0111

1111 1111 1111 1111 1111

11) итак, остается одно решение при (y₁, y₂, y₃, y₄)=1111, два решения при (y₁, y₂, y₃, y₄)=0111, три решения при (y₁, y₂, y₃, y₄)=0011, четыре решения при (y₁, y₂, y₃, y₄)=0001 и 5 решений при (y₁, y₂, y₃, y₄)=0000

12) всего решений 1+2+3+4+5=15.

Ещё пример задания:

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

X₁ → X₂ ÚX₃ Ù X₄ = 1

X₃ → X₄ ÚX₅ Ù X₆ = 1

X₅ → X₆ ÚX₁ Ù X₂ = 1

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

Решение:

1) перепишем уравнения в более простом виде, заменим знаки Ú и Ù соответственно на (логические) сложение и умножение:

2) вспомним, что сначала выполняется логическое умножение, потом логические сложение и только потом – импликация, поэтому уравнения можно переписать в виде

3) раскрывая импликацию по формуле , получаем

4) далее замечаем, что , и , поэтому можно ввести новые переменные , и , и переписать уравнения в виде

5) пусть , тогда из первого уравнения сразу имеем и далее из второго ; при этом третье автоматически выполняется; получили одно решение

6) теперь пуст , тогда из последнего уравнения имеем , а из второго – , при этом первое уравнение справедливо

7) таким образом, система уравнений относительно переменных имеет два решения: (0,0,0) и (1,1,1)

8) теперь вернемся обратно к исходным переменным; значению соответствует единственный вариант ; значению соответствуют остальные 3 пары возможных значений

9) то же самое можно сказать про и : нулевое значение дает один набор соответствующих исходных переменных, а единичное – три

10) переменные , и независимы друг от друга, так как каждая из них составлена из разных X-переменных, поэтому Y-решение (0,0,0) (см. п. 7) дает только одно X-решение, а Y-решение (1,1,1) – 3·3·3=27 решений

11) всего решений 1 + 27 = 28.

Ещё пример задания:

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

X₁ → X₂ → X₃ → X₄ → X₅ → X₆ = 1

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

Решение (вариант 1, табличный метод, динамическое программирование):

1) в левой части заданного уравнения стоят последовательно несколько операций импликации, скобок нет, поэтому порядок выполнения операций определяется приоритетом этих операций; в данном случае все операции имеют одинаковый приоритет

2) операции, имеющие одинаковый приоритет, выполняются слева направо, то есть первой выполняется импликация X₁ → X₂, а последней – последняя импликация

((((X₁ → X₂) → X₃) → X₄) → X₅) → X₆

3) каждая логическая переменная может принимать значение «истина» (1) или «ложь» (0)

4) для набора из 6 независимых логических переменных существует 2⁶ =64 разных комбинаций значений этих переменных

5) рассмотрим первую импликацию, X₁ → X₂; она дает в трёх случаях 1, и в одном – 0:

6) посмотрим, как меняется количество решений, если «подключить» следующую переменную;

· если X₁=0, то X₁ → X₂ =1 (из нулей получаются единиц)

· если X₁=1, то X₁ → X₂ =0 при X₂ =0 и X₁ → X₂ =1 при X₂ =1 (из единиц получаются нулей и единиц)

7) исходя из этого, можно составить формулы для вычисления количества нулей и количества единиц для уравнения с переменными:

,

8) для одной переменной имеем 1 ноль и 1 единицу, поэтому начальные условия для расчёта:

9) составим таблицу, которую будем заполнять слева направо, вычисляя число нулей и единиц по приведенным выше формулам; в таблице показано, как строится следующий столбец таблицы для :

10) таким образом, ответ: 43 решения.

Решение (вариант 2, «с хвоста»):

1) те же рассуждения, что и в п. 1-4 решения по варианту 1

2) если X₆ =1, то левая часть уравнения равна 1, то есть равенство выполняется; комбинаций с X₆ =1 ровно половина от общего количества, то есть 32

3) теперь проверяем варианты с X₆ =0; сразу получаем, что для выполнения заданного уравнения нужно, чтобы (X₁ → X₂ → X₃ → X₄ → X₅)=0; иначе получим 1 → X₆ = 1 →0 = 0

4) проверим отдельно случаи X₅=0 и X₅=1

5) пусть X₆ = 0 и X₅ =1; в этом случае никогда не будет выполнено условие
(X₁ → X₂ → X₃ → X₄ → X₅)=0, решений нет

6) пусть X₆ = X₅ =0; в этом случае условие (X₁ → X₂ → X₃ → X₄ → X₅)=0 выполняется только при (X₁ → X₂ → X₃ → X₄)=1; если X₄=1, это условие всегда верно, поэтому получаем еще 8 решений – 8 комбинаций, где X₆ = X₅ =0 и X₄=1 (1/8 всех комбинаций)

7) теперь рассмотрим случаи, когда X₆ = X₅ = X₄=0; рассуждая аналогично, находим, что условие (X₁ → X₂ → X₃ → 0)=1 верно при (X₁ → X₂ → X₃)=0, это сразу дает X₃ =0 и
(X₁ → X₂)=1

8) при всех известных значениях остальных переменных (X₆ = X₅ = X₄=X₃=0) условие
(X₁ → X₂)=1 истинно в трёх случаях: (X₁,X­₂) =(0,0), (0,1) и (1,1), это дает еще 3 решения

9) таким образом, ответ: 32 + 8 + 3 = 43 решения.

Решение (вариант 3, приведение к базису «И-ИЛИ-НЕ», Е.Н. Смирнова):

1) те же рассуждения, что и в п. 1-4 решения по варианту 1

2) заменяем импликацию по формуле ; на первом шаге получаем

3) далее по той же формуле

инверсию в первом слагаемом раскроем по закону де Моргана ():

4) сделав те же операции с оставшейся скобкой, получаем

5) и, применяя ту же формулу еще раз, получим уравнение

6) при остальные 5 переменных можно выбирать любым способом, это дает 2⁵ = 32 решения4⁴⁴⁴⁴⁴⁴

7) при и решений нет

8) при получаем 2³ = 8 решений при (можно выбирать , и произвольно)

9) при сразу находим, что , это дает еще 3 решения, при которых истинно выражение

10) таким образом, ответ: 32 + 8 + 3 = 43 решения.

Ещё пример задания:

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

X₁ Ú X₂ Ù X₃ = 1

X₂ Ú X₃ Ù X₄ = 1

...

X₈ Ú X₉ Ù X₁₀ = 1

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

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

1) рассмотрим сначала все решения первого уравнения; его левая части истинна, когда X₁=1 (при этом X₂ и X₃ могут быть любыми), а также когда X₁=0 и X₂=X₃ =1:

2) заметим, что первое и второе уравнения связаны через последние две переменных, в данном случае это X₂ и X₃

3) пусть i – число переменных в уравнениях; введем обозначения:

K_i – количество решений, в которых последние две переменные принимают
значения (0,0)

L_i – количество решений, в которых последние две переменные принимают
значения (0,1)

M_i – количество решений, в которых последние две переменные принимают
значения (1,0)

N_i – количество решений, в которых последние две переменные принимают
значения (1,1)

4) из таблицы видим, что K₃=1, L₃=1, M₃=1 и N₃=2

5) теперь подключаем второе уравнение; посмотрим, к чему приводят разные комбинации последних двух переменных:

6) находим, что
комбинация (0,0) не дает ни одного решения,
комбинация (0,1) дает одно решение, и при этом (X₃,X₄)=(1,1)

комбинация (1,0) дает два решения, причем (X₃,X₄)=(0,0) или (0,1)

комбинация (1,1) дает два решения, причем (X₃,X₄)=(1,0) или (1,1)

7) из предыдущего пункта делаем вывод, что

K_i+1 = M_i (комбинация (0,0) появилась из (1,0) на предыдущем шаге)

L_i+1 = M_i (комбинация (0,1) появилась из (1,0) на предыдущем шаге)

M_i+1 = N_i (комбинация (1,0) появилась из (1,1) на предыдущем шаге)

N_i+1 = L_i+N_i (комбинация (1,1) появляется из (0,1) и (1,1))

8) используя эти рекуррентные формулы, заполняем таблицу для i=4,…,10

9) таким образом, ответ: 13 + 13 + 19 + 28 = 73 решения.

Ещё пример задания:

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

(X₁ÚX₂) Ù (X₂ÚX₃) Ù (X₃ÚX₄) Ù (X₄ÚX₅) Ù (X₅ÚX₆) = 1

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

Решение:

11) перепишем уравнение, заменив знаки логических операций:

12) учитывая, что , заменяем все выражения в скобках на импликацию:

13) решение уравнения можно записать в виде шести двоичных знаков, которые обозначают соответственно, переменные

14) далее вспомним, что импликация дает ложное значение, если её первая часть (посылка) истинна, а вторая (следствие) ложно, поэтому из сразу следует, что

15) это значит, что в исходном выражении появится нуль, если в цепочке битов, соответствующей значениям переменных, появится комбинация 10, то есть предыдущее значение истинно, а следующее за ним – ложно

16) поэтому решениями этого уравнения будут все комбинации значений переменных, для которых в соответствующей битовой цепочке нет последовательности 10;

17) таких цепочек всего 7:

000000, 000001, 000011, 000111, 001111, 011111, 111111

18) таким образом, ответ: 7 решений.

Ещё пример задания:

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

X₁ Ú X₂ = 1

X₂ Ú X₃ = 1

...

X₉ Ú X₁₀ = 1

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

Решение (последовательное решение, через единицы):

1) количество комбинаций 10 логических переменных равно 2¹⁰ = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу

2) сначала рассмотрим первое уравнение ; согласно таблице истинности операции «ИЛИ» оно имеет 3 решения (точнее, с учетом других переменных, 3 группы решений): (0,0,*), (0,1,*) и (1,1,*); здесь звездочка означает, что остальные 8 переменных могут быть любыми

3) выпишем все решения в столбик, чтобы была видна закономерность:

(0,0,*)

(0,1,*)

(1,1,*)

4) заметим, что при X₂ = 0 значение X₁ должно быть равно 0, а при X₂ = 1 значение X₁ может быть любым

5) второе уравнение, рассматриваемое отдельно, тоже имеет 3 группы решений: (x₁,0,0,*), (x₁,0,1,*) и (x₁,1,1,*), где x₁, – некоторое логическое значение переменной X₁

6) решения системы первых двух уравнений – это те комбинации значений переменных, которые удовлетворяют одновременно и первому, и второму

7) из п. 4 следует, что при X₂ = 0 значение X₁ должно быть равно 0, а при X₂ = 1 значение X₁ может быть любым, поэтому решение системы двух первых уравнений включает 4 группы: из (x₁,0,0,*) и (x₁,0,1,*) при X₁ = 0 получаем две группы

(0,0,0,*) и (0,0,1,*)

и из (x₁,1,1,*) получается еще две:

(0,1,1,*) и (1,1,1,*).

8) таким образом, система из двух уравнений имеет 4 решения

9) выпишем все решения в столбик, чтобы была видна закономерность:

(0,0,0,*)

(0,0,1,*)

(0,1,1,*)

(1,1,1,*)

10) таким образом, если X­₃ = 0, все предыдущие переменные определяются однозначно – они должны быть равны нулю (идем по системе «снизу вверх»); если же X­₃ = 1, то предыдущие переменные могут быть любыми, второе уравнение их не ограничивает

11) поэтому при увеличении числа переменных на единицу количество решений также увеличивается на единицу

12) аналогично доказывается, что система из 3 уравнений имеет 5 решений, и т.д., то есть, система из 9 уравнений с 10 переменными имеет 11 решений

13) таким образом, ответ: 11 решений.

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

1) сначала рассмотрим первое уравнение ; согласно таблице истинности операции «ИЛИ» оно НЕ выполняется только в одном случае (точнее, с учетом других переменных, для одной группы комбинаций): (1,0,*) здесь звездочка означает, что остальные 8 переменных могут быть любыми

2) общее количество комбинаций X₁ и X_{2 ­­}равно 2² = 4, поэтому число решений первого уравнения равно 4 – 1 = 3

3) второе уравнение, рассматриваемое отдельно, тоже ложно только для одной комбинации имеет 3 группы решений: (x₁,1,0,*), где x₁, – некоторое логическое значение переменной X₁

4) теперь рассмотрим вместе первое и второе уравнения и определим, в скольких случаях хотя бы одно из них неверно

5) множества (1,0,x­­₃,*) и (x₁,1,0,*) не пересекаются, потому что в первом X₂ = 0, а во втором X₂ = 1, поэтому система из двух уравнений не выполнена для 4-х комбинаций:

(1,0,0,*), (1,0,1,*), (0,1,0,*) и (1,1,0,*)

6) общее количество комбинаций трех логический переменных равно 2³ = 8, поэтому количество решений системы из двух уравнений равно 8 – 4 = 4

7) аналогично доказывается, что система из 3 уравнений имеет 5 решений, и т.д., то есть, система из 9 уравнений с 10 переменными имеет 11 решений

8) таким образом, ответ: 11 решений.

Решение (табличный метод):

1) рассмотрим все решения первого уравнения по таблице истинности:

	X2	X1

2) строчка, выделенная красным фоном, не удовлетворяет условию, поэтому дальше ее рассматривать не будем

3) теперь подключаем третью переменную и второе уравнение:

4) при каких значениях переменной X₃ будет верно условие ? Очевидно, что на это уже не влияет X­₁ (этот столбец выделен зеленым цветом). Если X₂ = 1, то сразу получаем, что X₃ = 1 (иначе ):

5) как видно из таблицы, верхняя строчка предыдущей таблицы (где были все нули) дает два решения при подключении очередного уравнения, а все остальные – по одному

6) понятно, что такая же ситуация будет продолжаться и дальше, то есть, при добавлении каждой новой переменной число решений увеличивается на 1

7) рассуждая таким образом и дальше, получаем, что для 3-х уравнений с 4-мя переменными будет 5 решений, для 4 уравнений – 6 решений, …, а для 9 уравнений – 11 решений

8) обратите внимание на форму таблицы – единицы и нули образуют два треугольника

9) таким образом, ответ: 11 решений.

Еще пример задания:

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

(X₁ º X₂) Ú (X₃ º X₄) = 1

(X₃ º X₄) Ú (X₅ º X₆) = 1

(X₅ º X₆) Ú (X₇ º X₈) = 1

(X₇ º X₈) Ú (X₉ º X₁₀) = 1

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

Решение:

1) количество комбинаций 10 логических переменных равно 2¹⁰ = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу

2) заметим, что при обозначениях , , , и мы получаем систему из 4 уравнений и 5 независимыми переменными; эта система уравнений относится к типу, который рассмотрен в предыдущей разобранной задаче:

Y₁ Ú Y₂ = 1

Y₂ Ú Y₃ = 1

Y₃ Ú Y₄ = 1

Y₄ Ú Y₅ = 1

3) как следует из разбора предыдущей задачи, такая система имеет 5+1 = 6 решений для переменных Y₁ … Y₅

4) теперь нужно получить количество решений в исходных переменных, X₁ … X₁₀; для этого заметим, что переменные Y₁ … Y₅ независимы;

5) предположим, что значение Y₁ известно (0 или 1); поскольку , по таблице истинности операции «эквивалентность» (истина, когда два значения одинаковы), есть две соответствующих пары (X₁;X₂) (как для случая Y₁ = 0, так и для случая Y₁ = 1)

6) у нас есть 5 переменных Y₁ … Y_5, каждая их комбинация дает 2 пары (X₁;X₂), 2 пары (X₃;X₄), 2 пары (X₅;X₆), 2 пары (X₇;X₈) и 2 пары (X₉;X₁₀), то есть всего 2⁵ = 32 комбинации исходных переменных

7) таким образом, общее количество решений равно 6 ·32 = 192

8) ответ: 192 решения

Еще пример задания:

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

(X₁ÙX₂) Ú (X₁ÙX₂) Ú (X₃ÙX₄) Ú (X₃ÙX₄) = 1

(X₃ÙX₄) Ú (X₃ÙX₄) Ú (X₅ÙX₆) Ú (X₅ÙX₆) = 1

(X₅ÙX₆) Ú (X₅ÙX₆) Ú (X₇ÙX₈) Ú (X₇ÙX₈) = 1

(X₇ÙX₈) Ú (X₇ÙX₈) Ú (X₉ÙX₁₀) Ú (X₉ÙX₁₀) = 1

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

Решение:

1) количество комбинаций 10 логических переменных равно 2¹⁰ = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу

2) решать такую систему «в лоб» достаточно сложно, нужно попробовать ее упростить

3) заметим, что

(X₁ÙX₂) Ú (X₁ÙX₂) = (X₁ º X₂),

где символ º означает операцию «эквивалентность» (значения равны);

4) кроме того,

(X₃ÙX₄) Ú (X₃ÙX₄) = (X₃ Å X₄) = (X₃ º X₄),

где символ Å означает операцию «исключающее ИЛИ» (значения НЕ равны); это операция, обратная эквивалентности

5) используем замену переменных, выделив члены, объединяющие пары исходных переменных (X₁ и X₂, X₃ и X₄, X₅ и X₆, X₇ и X₈, X₉ и X₁₀)

Y₁ = (X₁ º X₂) Y₂ = (X₃ º X₄)

Y₃ = (X₅ º X₆) Y₄ = (X₇ º X₈)

Y₅ = (X₉ º X₁₀)

6) при этих обозначения система уравнений преобразуется к виду

Y₁ Ú Y₂ = 1

Y₂ Ú Y₃ = 1

Y₃ Ú Y₄ = 1

Y₄ Ú Y₅ = 1

9) как показано выше (при разборе пред-предыдущей задачи), такая система имеет 5+1 = 6 решений для независимых переменных Y₁ … Y₅

10) предположим, что значение Y₁ известно (0 или 1); поскольку , по таблице истинности операции «эквивалентность» есть две соответствующих пары (X₁;X₂) (как для случая Y₁ = 0, так и для случая Y₁ = 1)

11) у нас есть 5 переменных Y₁ … Y_5, каждая их комбинация дает 2 пары (X₁;X₂), 2 пары (X₃;X₄), 2 пары (X₅;X₆), 2 пары (X₇;X₈) и 2 пары (X₉;X₁₀), то есть всего 2⁵ = 32 комбинации исходных переменных

12) таким образом, общее количество решений равно 6 ·32 = 192

7) ответ: 192 решения

Еще пример задания:

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

((X₁ º X₂) Ù (X₃ º X₄)) Ú ((X₁ º X₂) Ù (X₃ º X₄)) = 1

((X₃ º X₄) Ù (X₅ º X₆)) Ú ((X₃ º X₄) Ù (X₅ º X₆)) = 1

((X₅ º X₆) Ù (X₇ º X₈)) Ú ((X₅ º X₆) Ù (X₇ º X₈)) = 1

((X₇ º X₈) Ù (X₉ º X₁₀)) Ú ((X₇ º X₈) Ù (X₉ º X₁₀)) = 1

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

Решение:

1) количество комбинаций 10 логических переменных равно 2¹⁰ = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу

2) решать такую систему «в лоб» достаточно сложно, нужно попробовать ее упростить

3) рассмотрим первое уравнение, заменив обозначения логических операций на более простые:

,

где и . Выражение в левой части последнего равенства – это операция эквивалентности между Y­₁ и Y₂, то есть первое уравнение запишется в виде

4) аналогично, вводя обозначения , и , запишем исходную систему в виде

(Y₁ º Y₂) = 1

(Y₂ º Y₃) = 1

(Y₃ º Y₄) = 1

(Y₄ º Y₅) = 1

заметим, что все переменные здесь независимы друг от друга

13) найдем решение этой системы относительно независимых переменных Y₁ … Y₅

14) первое уравнение имеет два решения (с учетом остальных переменных – две группы решений): (0,0,*) и (1,1,*), где * обозначает остальные переменные, которые могут быть любыми

15) второе уравнение тоже имеет две группы решений: (Y₁,0,0,*) и (Y ₁,1,1,*), где Y ₁ обозначает некоторое значение переменной Y ₁

16) теперь ищем решения, которые удовлетворяют и первому, и второму уравнению; очевидно, что их всего 2: (0,0,0,*) и (1,1,1,*)

17) рассуждая дальше аналогичным образом, приходим к выводу, что система имеет всего два решения относительно переменных Y₁ … Y₅: все нули и все единицы

18) теперь нужно получить количество решений в исходных переменных, X₁ … X₁₀; для этого вспомним, что переменные Y₁ … Y₅ независимы;

19) предположим, что значение Y₁ известно (0 или 1); поскольку , по таблице истинности операции «эквивалентность» (истина, когда два значения одинаковы), есть две соответствующих пары (X₁;X₂) (как для случая Y₁ = 0, так и для случая Y₁ = 1)

20) у нас есть 5 переменных Y₁ … Y_5, каждая их комбинация дает 2 допустимых пары (X₁;X₂), 2 пары (X₃;X₄), 2 пары (X₅;X₆), 2 пары (X₇;X₈) и 2 пары (X₉;X₁₀), то есть всего 2⁵ = 32 комбинации исходных переменных

21) таким образом, общее количество решений равно 2 ·32 = 64

22) ответ: 64 решения

Решение (табличный метод):

1) так же, как и в предыдущем варианте, с помощью замену переменных сведем систему к виду:

(Y₁ º Y₂) = 1

(Y₂ º Y₃) = 1

(Y₃ º Y₄) = 1

(Y₄ º Y₅) = 1

2) рассмотрим все решения первого уравнения по таблице истинности:

	Y2	Y1

3) строчки, выделенные красным фоном, не удовлетворяют условию, поэтому дальше их рассматривать не будем

4) теперь подключаем третью переменную и второе уравнение:

5) при каких значениях переменной X₃ будет верно условие ? Очевидно, что на это уже не влияет Y­₁ (этот столбец выделен зеленым цветом). Cразу получаем два решения:

6) как видно из таблицы, каждая строчка предыдущей таблицы дает одно решение при подключении очередного уравнения, поэтому для любого количества переменных система имеет 2 решения – все нули и все единицы

7) так же, как и в предыдущем способе, переходим к исходным переменным и находим общее количество решений: 2 ·32 = 64

8) ответ: 64 решения

Еще пример задания:

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

(X₂ º X₁) Ú (X₂ Ù X₃) Ú (X₂ Ù X₃)= 1

(X₃ º X₁) Ú (X₃ Ù X₄) Ú (X₃ Ù X₄)= 1

...

(X₉ º X₁) Ú (X₉ Ù X₁₀) Ú (X₉ Ù X₁₀)= 1

(X₁₀ º X₁) = 0

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

Решение (табличный метод):

1) количество комбинаций 10 логических переменных равно 2¹⁰ = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу

2) перепишем уравнения, используя более простые обозначения операций

...

3) заметим, что по свойству операции эквивалентности , поэтому уравнения можно переписать в виде

...

4) первое уравнение выполняется, когда есть X₂ равно X₁ или X₃

5) по таблице истинности находим 6 вариантов (для удобства мы будем записывать сначала столбец для X₁, а потом для всех остальных в обратном порядке):

обратите внимание, что в каждой строчке в первых двух столбцах должно быть по крайней мере одно значение, равное значению в третьем столбце (который выделен желтым)

6) добавим еще одно уравнение и еще одну переменную X­₄:

7) чтобы «подключить» второе уравнение, нужно использовать то же самое правило: каждой строчке в первых двух столбцах должно быть, по крайней мере, одно значение, равное значению в третьем столбце (который выделен желтым); это значит, что в первой и последней строчках (где X­₁ = X₃) значение X₄ может быть любое (0 или 1), а в остальных строчках – только строго определенное:

8) таким образом, количество решений при подключении очередного уравнения к системе возрастает на 2!

9) подключили X₅ – получили 10 решений, X₆ – получили 12 решений, X₇ – получили 14 решений, X₈ – получили 16 решений, X₉ – получили 18 решений, X₁₀ – получили 20 решений.

10) остается одно последнее уравнение (X₁₀ º X₁) = 0, из которого следует, что X₁₀ не равен X­₁

11) из таблицы следует, что только в первой и последней строчках значения первой и последней переменных совпадают, то есть из полученных 20 решений нужно отбросить 2

12) таким образом, получается 20 – 2 = 18 решений

13) ответ: 18 решений

Еще пример задания:

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

(X₁ Ù X₂) Ú (X₁ Ù X₂) Ú (X₁ º X₃) = 1

(X₂ Ù X₃) Ú (X₂ Ù X₃) Ú (X₂ º X₄) = 1

...

(X₈ Ù X₉) Ú (X₈ Ù X₉) Ú (X₈ º X₁₀) = 1

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

Решение (табличный метод):

1) количество комбинаций 10 логических переменных равно 2¹⁰ = 1024, поэтому вариант с построением полной таблицы истинности отпадает сразу

2) перепишем уравнения, используя более простые обозначения операций

...

3) заметим, что по свойству операции эквивалентности , поэтому уравнения можно переписать в виде

...

4) сделать замену переменных так, чтобы новые переменные был независимы друг от друга, здесь довольно затруднительно, поэтому будем решать уравнения последовательно табличным методом

5) рассмотрим все возможные комбинации первых двух переменных ­X₁ и X₂, и сразу попытаемся для каждой из них подобрать значения третьей так, чтобы выполнялось первое уравнение :

Поиск по сайту: