Про обозначения 2 страница

комбинация (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₆ – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение:

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

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

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

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

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

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

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

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

41) таким образом, ответ: 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) второе уравнение тоже имеет две группы решений: (x₁,0,0,*) и (x₁,1,1,*), где x₁ обозначает некоторое значение переменной x₁

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) заметим, что по свойству операции эквивалентности , поэтому уравнения можно переписать в виде

...