Главная / Задания по информатике / Группа B / Задание 23 / Задание 23. Задачи с решениями

Задание 23. Задачи с решениями

Задачи с сайта ege.yandex.ru:       23.1       23.2      23.3      23.4      23.5     

Подготовительные задачи:        23.П1     23.П2     

Более сложные задачи:               23.Д1     23.Д2

 

 

 

23.1 ( ege.yandex.ru-1 ) Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

(x1->x2) /\ (x2->x3) /\ (x3->x4) /\ (x4->x5 )  = 1

(y1->y2) /\ (y2->y3) /\ (y3->y4) /\ (y4->y5 )  = 1

x1\/y1 =1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. Первое уравнение означает, что если x[i]=1, то для всех k>=i выполнено x[k]  = 1 . Поэтому первое уравнение имеет 6 решений (1-я цифра в наборе – значение x1, 2-я цифра в наборе – значение x2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Второе уравнение имеет 6 аналогичных решений (1-я цифра в наборе – значение y1, 2-я цифра в наборе – значение y2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Решение системы – пара таких наборов. Ввиду третьего уравнения, один наборов в паре должен быть набором 11111. Таких пар – 11: {11111, 11111}, 5 пар вида {11111, R} и 5 пар вида {R, 11111}, здесь R – один из наборов 00000, 00001, 00011, 00111, 01111.

Ответ: 11

Замечание. На первый раз выпишем все решения явно:

{11111, 00000}; {11111, 00001};  {11111, 00011};  {11111, 00111};  {11111, 01111};

{11111, 11111}

{00000, 11111};  {00001, 11111};  {00011, 11111};  {00111, 11111};  {01111, 11111};

{11111, 11111}

Написано 12 пар, но решений - 11.  Выделенная жирным пара  {11111, 11111} написана 2 раза!

 


 

 

23.2 ( ege.yandex.ru-2 ) Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

(x1->x2) /\ (x2->x3) /\ (x3->x4) /\ (x4->x5 )  = 1

(y5->y4) /\ (y4->y3) /\ (y3->y2) /\ (y2->y1 )  = 1

X3 /\ y3 =1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. Первое уравнение означает, что если x[i]=1, то для всех k>=i выполнено x[k]  = 1 . Поэтому  первое уравнение имеет 6 решений (1-я цифра в наборе – значение x1, 2-я цифра в наборе – значение x2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Второе уравнение имеет 6 аналогичных решений (1-я цифра в наборе – значение y1, 2-я цифра в наборе – значение y2 и т.д.):

00000, 10000, 11000, 11100, 11110, 11111

Решение системы – пара таких наборов. Ввиду третьего уравнения, первый набор в паре должен принадлежать множеству {00111, 01111, 11111},  а второй - множеству  {11100, 11110, 11111}.  При этом любой из перечисленных наборов может образовывать пару с любым другим. Поэтому система имеет 3*3 = 9 решений.

Ответ: 9

 

23.3 ( ege.yandex.ru-3 ) Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

(x1->x2) /\ (x2->x3) /\ (x3->x4) /\ (x4->x5 )  = 1

(y1->y2) /\ (y2->y3) /\ (y3->y4) /\ (y4->y5 )  = 1

x1->y1 =1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. Первое уравнение означает, что если x[i]=1, то для всех k>=i выполнено x[k]  = 1 . Поэтому первое уравнение имеет 6 решений (1-я цифра в группе – значение x1, 2-я цифра в группе – значение x2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Второе уравнение имеет 6 аналогичных решений (1-я цифра в группе – значение y1, 2-я цифра в группе – значение y2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Решение системы – пара таких наборов. Ввиду третьего уравнения, если первый набор в паре – это набор 11111, то и второй набор – 11111. Любой из остальных пяти наборов значений для переменных x1, x2, x3, x4, x5 может образовать решение системы с любым из 6 возможных  решений для  переменных y1, y2, y3, y4, y5. Таким образом, система имеет 1+5*6 = 31 решение.

Ответ: 31


 

23.4 ( ege.yandex.ru-4 ) Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

(x1->x2) /\ (x2->x3) /\ (x3->x4) /\ (x4->x5 )  = 1

(y1->y2) /\ (y2->y3) /\ (y3->y4) /\ (y4->y5 )  = 1

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. Первое уравнение означает, что если x[i]=1, то для всех k>=i выполнено x[k]  = 1 . Поэтому первое уравнение имеет 6 решений (1-я цифра в группе – значение x1, 2-я цифра в группе – значение x2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Второе уравнение имеет 6 аналогичных решений (1-я цифра в группе – значение y1, 2-я цифра в группе – значение y2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Решение системы – пара таких наборов. При этом любой из 6 возможных наборов значений для переменных x1, x2, x3, x4, x5 может образовать решение системы с любым из 6 возможных  решений для  переменных y1, y2, y3, y4, y5. Таким образом, система имеет 6*6 = 36 решений.

Ответ: 36


 

23.5 ( ege.yandex.ru-5 ) Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

(x1->x2) /\ (x2->x3) /\ (x3->x4) /\ (x4->x5 )  = 1

(y1->y2) /\ (y2->y3) /\ (y3->y4) /\ (y4->y5 )  = 1

(x1->y1)  /\ (x2->y2)  =1

 

В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

Решение. Первое уравнение означает, что если x[i]=1, то для всех k>=i выполнено x[k]  = 1 . Поэтому первое уравнение имеет 6 решений (1-я цифра в группе – значение x1, 2-я цифра в группе – значение x2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Второе уравнение имеет 6 аналогичных решений (1-я цифра в группе – значение y1, 2-я цифра в группе – значение y2 и т.д.):

00000, 00001, 00011, 00111, 01111, 11111

Решение системы – пара таких наборов. Ввиду третьего уравнения, если первый набор в паре – это набор 11111, то и второй набор – 11111. Если первый набор в паре – это набор 01111, то и второй набор – 11111 или 01111. Любой из остальных 4-х наборов значений для переменных x1, x2, x3, x4, x5 может образовать решение системы с любым из 6 возможных  решений для  переменных y1, y2, y3, y4, y5. Таким образом, система имеет 1+2+4*6 = 27 решение.

Ответ: 27

     ПОДГОТОВИТЕЛЬНЫЕ ЗАДАЧИ

 

23.П1  Сколько существует различных наборов значений логических переменных x1, x2, ..., x5, которые удовлетворяют всем перечисленному ниже условию?

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

В ответе не нужно перечислять все различные наборы значений x1, x2, ..., x5, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Решение. Очевидно, выполнены следующие соотношения:

 (x1  x2) = 1

 (x2  x3) = 1

 (x3  x4) = 1

 (x4  x5) = 1

Допустим, что набор {a1, a2, a3. a4, a5} – решение нашего уравнения. Допустим, что  a4 = 1. Тогда, из уравнения

(x4  x5) = 1

следует, что a5 = 1 (напомним: 1  0  ложно!). Допустим теперь, что а3=1. Из условия

(x3  x4) = 1

следует, что a4=1 и, значит, по доказанному, a5 = 1.

Аналогично можно показать (проверьте сами!), что если в решении встречается 1, то далее идут только единицы.

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

!!! Важно не забыть про «особые» наборы – 00000 и 11111. Они тоже годятся.

Таким образом, вот все решения уравнения:

00000, 00001, 00011, 00111, 01111, 11111

Каждое решение полностью описывается количеством единиц в нем. Это количество может быть от 0 до 5. Количество решений – 6.

Ответ: 6


 

Задача 23.П2  Сколько существует различных наборов значений логических переменных x1, x2, ..., x5, z1, ..., z4, которые удовлетворяют всем перечисленному ниже условию?

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

(z1  z2) /\  (z2  z3) /\ (z3  z4)  = 1                                                       (2)

В ответе не нужно перечислять все различные наборы значений x1, x2, ..., x5, , z1, ..., z4 , при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов.

Решение. Про такие системы говорят, что переменные в них «разделенные»: x1, …, x5 встречаются только в уравнении (1), а z1, …, z4  - только в уравнении (2). Из решения задачи 3 следует, что уравнению (1) удовлетворяют 6 наборов значений переменных x1, x2, ..., x5, а уравнению (2) – 5 наборов значений переменных z1, …, z4  Каждый из этих наборов для {xi } может образовать решение с любым из наборов для {zi }. Поэтому общее количество решений равно 6∙5 = 30.

Ответ: 30

БОЛЕЕ СЛОЖНЫЕ ЗАДАЧИ

 

23.Д1  [задачу прислала Жанна]  Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, которые удовлетворяют всем перечисленным ниже условиям?

х1 \/  ¬х2 \/ (¬х3)/\х4  = 1
х3 \/  ¬х4 \/  (¬х5)/\х6 = 1
х5 \/  ¬х6 \/  (¬х7)/\х8 = 1
х7 \/  ¬х8 \/  (¬х9)/\х10= 1

Решение. По определению импликации, для всех значений A, B выполнено:

A \/ ¬B  =  B → A
По правилу Де Моргана  и определению импликации, выполнено:

(¬A)/\B  =  ¬(A\/ ¬B) = ¬ (B→A)
Поэтому исходную систему можно переписать в виде:

(x2 → x1) \/  ¬ (x4→x3)  = 1           (*)
(x4 → x3) \/  ¬ (x6→x5)  = 1
(x6 → x5) \/  ¬ (x8→x7)  = 1
(x8 → x7) \/  ¬ (x10→x9)  = 1

Сделаем замену:
t1 = x2 → x1;
t2 = x4 → x3;
t3 = x6 → x5;
t4 = x8 → x7;
t5 = x10 → x9.

Получим систему:
t1 \/ ¬ t2 = 1
t2 \/ ¬ t3 = 1
t3 \/ ¬ t4 = 1
t4 \/ ¬ t5 = 1

Снова применим определение импликации. Получим:
t2 → t1 = 1                                   (**)
t3 → t2 = 1
t4 → t3 = 1
t5 → t4 = 1

Эта система имеет 6 решений (см. http://ege-go.ru/zadania/grb/b15/b15-answ/#23.6):

00000; 10000; 11000; 11100; 11110; 11111

(в каждой пятерке первая цифра – значение t1, 2-я цифра – значение t2 и т.д.).

Вспоминаем про замены. Разберемся, сколько решений исходной системы (*) соответствует каждому решению  системы (**).
Заметим:  ни одна из исходных переменных не входит в определение двух переменных замены (иногда говорят: «переменные замены независимы»).  Поэтому, например, количество решений системы (*), соответствующих решению 00000 системы (**) равно

N1(0)*N2(0)*…*N5(0)
.
Здесь N1(0) – количество пар значений переменных x1, x2, при которых t1=0;  N2(0) – количество пар значений переменных x3, x4, при которых t2=0 и т.д. Аналогично, через N1(1) будем обозначать количество пар значений переменных x1, x2, при которых t1=1 и т.д.   Это замечание основано на формуле перемножения вариантов (см. http://ege-go.ru/temy/topics-multvars/ ).
Далее, отметим, что все замены имеют вид T = A→ B . Поэтому

N1(0) = N2(0) = … = N5(0) = 1

и

N1(1) = N2(1) = … = N5(1) = 3

[Для тех, кто забыл, напомним: A→ B = 0 только при A=1, B=0. В остальных трех возможных случаях, то есть при A=1, B=1; A=0, B=0; A=0, B=1, выполнено A→ B = 1].

Таким образом решению 00000 системы (**) соответствует 1*1*1*1*1 = 1 решение системы (*). На всякий случай выпишем это решение:
x1=0, x2 = 1, x3=0, x4 = 1, x5=0, x6 = 1, x7=0, x8 = 1, x9=0, x10 = 1.
Аналогично,
для 10000 существует 3*1*1*1*1 = 3 решений системы (*);
для 11000 существует 3*3*1*1*1 = 32 = 9 решений системы (*);
для 11100 существует 3*3*3*1*1 = 33 = 27 решений системы (*);
для 11110 существует 3*3*3*3*1 = 34 = 81 решений системы (*);
для 11111 существует 3*3*3*3*3 = 35 = 243 решений системы (*).
Таким образом, так как разным решениям системы (**) соответствуют разные решения системы (*), то исходная система (*) имеет 1+3+9+27+81+243 = 364 решения.
Ответ: 364
Замечание. Сложить  1+3+9+27+81+243 несложно. Но можно и воспользоваться формулой для суммы геометрической прогрессии:
1 + 3 + 32 + 33 + 34 + 35  = (36-1)/(3-1) = 728/2 = 364

 

23.Д2  [задачу прислала Настя]  Сколько существует различных наборов значений логических переменных x1, …, x7, y1, …, y7, которые удовлетворяют всем перечисленным ниже условиям?

(x1 ∨ x2) ∧ (x1 ∧ x2 → x3) ∧ (x1 ∨ y1) = 1

(x2 ∨ x3) ∧ (x2 ∧ x3 → x4) ∧ (x2 ∨ y2) = 1

...

(x5 ∨ x6) ∧ (x5 ∧ x6 → x7) ∧ (x5 ∨ y5) = 1

(x6 ∨ x7) ∧ (x6 ∨ y6) = 1

x7 ∨ y7 = 1

В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение.

Для набора значений переменных x1, …, x7, y1, …, y7, который является решением системы, должны быть истинны правые части всех уравнений. Каждая правая часть – это конъюнкция. Поэтому должны быть истинны все члены всех конъюнкций.

Эти члены можно сгруппировать в три группы:

1) (x1 ∨ x2) ∧ (x2 ∨ x3) ∧ … ∧ (x6 ∨ x7)

2) (x1 ∧ x2 → x3) ∧ (x2 ∧ x3 → x4) ∧ … ∧ (x5 ∧ x6 → x7)

3) (x1 ∨ y1) ∧ (x2 ∨ y2) ∧ … ∧ (x7 ∨ y7)

Каждая из трех этих конъюнкций должна быть истинна.

Каждое решение удобно представлять в виде двух двоичных цепочек длиной 7 каждая, первая цепочка представляет значения переменных x1, …, x7, а вторая – переменных y1, …, y7.  См. статью "К.Ю. Поляков, М.А. Ройтберг.  Системы логических уравнений: решение с помощью битовых цепочек // Информатика, № 12, 2014, с. 4-12"

Например, пара цепочек 0111111 1000000 представляет такой набор значений:

x1=0; x2=x3=…=x7=1;     y1 = 1; y2= …, = y7 = 0.

Для удобства будем в паре цепочек первую цепочку называть x-цепочкой, а вторую – y-цепочкой.

Посмотрим на конъюнкции 1) – 3).

Первая конъюнкция означает, что в x-цепочке не может быть двух нулей подряд. Вторая цепочка означает, что, если в x-цепочке встретились две единицы подряд, то дальше будут только единицы. Вместе это означает, что в x-цепочке сначала нули и единицы чередуются, чередование может кончиться только на двух единицах подряд и с этого места будут только единицы. Вот все такие цепочки:

0101010;  0101011; 0101111;  0111111;  1010101; 1010111; 1011111; 1111111

То есть, возможно ровно 8 вариантов x-цепочек.

Посмотрим, какие y-цепочки подходят к каждой x-цепочке. Конъюнкция 3) означает, что ели i-е число в x-цепочке – 0, то соответствующее число в y-цепочке должно быть 1. А если i-е число в x-цепочке – 1, то соответствующее число в y-цепочке может быть и 0, и 1.

Поэтому количество возможных y- цепочек для данной x-цепочки равно 2n , где n – количество единиц в x-цепочке. то замечание основано на формуле перемножения вариантов (см. http://ege-go.ru/temy/topics-multvars/ ).

В наших цепочках вот сколько единиц:

0101010  - 3;  0101011 - 4; 0101111 - 5;  0111111 - 6;

1010101 - 4; 1010111 - 5; 1011111 - 6; 1111111 – 7

Таким образом, общее количество решений равно:

23 + 24 + 25 + 26 + 24 + 25 + 26 +27 = 23 * (1+ 2+ 4 +8) + 24 * (1+ 2+ 4 +8)  = 8*15 + 16*15 = 24*15 = 360

Ответ:  360

 

 

 

 

 

 

 
 

33 комментария

  1. Ольга:

    Помогите пожалуйста решить вот такую систему уравнений:
    (x1→x2) /\ (x1→y1) = 1
    (x2→x3) /\ (x2→y2) = 1

    (x7→x8) /\ (x7→y7) = 1
    (x8→y8) = 1

    • Женя:

      Решение.
      Все уравнения однотипные, разберемся с первым.
      (x1 → x2) ∧ (x1 → y1) = 1 означает, что должно одновременно выполняться два равенства:
      1) x1 → x2 = 1
      2) x1 → y1 = 1
      Поскольку среди переменных x1, x2, y1 только переменная x2 присутствует в следующем уравнении, будем сначала рассматривать только уравнение x1 → x2 = 1 и искать все последовательности x1,x2,…,x10, которые удовлетворяют нашей системе уравнений. x1 → x2 = 1 означает, что x1 и x2 не могут быть равны соответственно 1 и 0 (в этом случае 1 → 0 = 0). Значит, нам подходят только три пары значений: 0 и 0, 0 и 1, 1 и 1. Для каждой пары рассмотрим возможные значения x3, удовлетворяющие уравнению x2 → x3 = 1 (из второго уравнения системы):
      Если x1 = 0 и x2 = 0, то x3 может быть как 0, так и 1.
      Если x1 = 0 и x2 = 1, то x3 = 1, т.к. при x3 = 0 имеем 1 → 0 = 0.
      Если x1 = 1 и x2 = 1, то x3 = 1, т.к. при x3 = 0 имеем 1 → 0 = 0.
      Поскольку все уравнения однотипны, замечаем, что в последовательности x1,x2,…,x10 после 1 может стоять только 1, а после 0 может стоять как 0, так и 1. Выпишем все последовательности x1,x2,…,x10, удовлетворяющие этому условию:
      0000000000
      0000000001
      0000000011
      0000000111
      0000001111
      0000011111
      0000111111
      0001111111
      0011111111
      0111111111
      1111111111
      Всего 11 решений.
      Рассмотрим теперь последовательность y1,y2,…,y10. y1 должен удовлетворять условию x1 → y1 = 1, значит при x1 = 1 имеем y1 = 1, а при x1 = 0 имеем y1 = 1 или y1 = 0. То же самое можем сказать про y2,y3,…,y10. Таким образом, для каждой переменной xi = 0 существует два возможных значения yi, а для каждой переменной xi = 1 только одно значение yi.
      Таким образом,
      при x1,x2,…,x10 = 1111111111 имеем единственную последовательность y1,y2,…,y10 = 1111111111;
      при x1,x2,…,x10 = 0111111111 имеем две последовательности: y1,y2,…,y10 = 0111111111 и y1,y2,…,y10 = 1111111111;
      при x1,x2,…,x10 = 0011111111 имеем четыре последовательности: y1,y2,…,y10 = 0011111111, y1,y2,…,y10 = 0111111111, y1,y2,…,y10 = 1011111111, y1,y2,…,y10 = 1111111111;
      Заметим, что кол-во последовательностей y1,y2,…,y10 равно двойке, возведенной в степень, равную кол-ву нулей в последовательности x1,x2,…x10 (замечание основано на формуле перемножения вариантов, см. http://ege-go.ru/temy/topics-multvars/ ).
      Подсчитаем кол-во нулей и кол-во соответствующих последовательностей y1,y2,…,y10 для каждой последовательности x1,x2,…,x10:
      0000000000 = 10 нулей, 1024 последовательности y1,y2,…,y10
      0000000001 = 9 нулей, 512 последовательностей y1,y2,…,y10
      0000000011 = 8 нулей, 256 последовательностей y1,y2,…,y10
      0000000111 = 7 нулей, 128 последовательностей y1,y2,…,y10
      0000001111 = 6 нулей, 64 последовательности y1,y2,…,y10
      0000011111 = 5 нулей, 32 последовательности y1,y2,…,y10
      0000111111 = 4 нуля, 16 последовательностей y1,y2,…,y10
      0001111111 = 3 нуля, 8 последовательностей y1,y2,…,y10
      0011111111 = 2 нуля, 4 последовательности y1,y2,…,y10
      0111111111 = 1 нуль, 2 последовательности y1,y2,…,y10
      1111111111 = нет нулей, 1 последовательность y1,y2,…,y10
      Сложим кол-ва всех подходящих последовательностей x1,x2,…,x10,y1,y2,…,y10:
      1024+512+256+128+64+32+16+8+4+2+1 = 2047
      Ответ: 2047

  2. Лиза:

    А вот это как решать? Тоже 23 (№ 3152).
    ((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1
    Ответ: 8.
    (Задания я с решу егэ взяла, там непонятно объясняется) .

    • editor:

      Решение.
      Формула в левой части – конъюнкция трех выражений:

      1) (J → K) → (M ∧ N ∧ L)
      2) (J ∧ ¬K) → ¬ (M ∧ N ∧ L)
      3) M → J

      Все эти выражения должны быть истинными при нужных нам наборах значений переменных J, K, L, M, N.
      Дальше можно рассуждать по-разному. Можно, например, так.
      1. (J ∧ ¬K) – это отрицание (J → K). Действительно,
      ¬(J → K) = ¬(¬J \/ K) = J ∧ ¬K
      (если эти преобразования непонятны – напиши).
      Поэтому 2-е выражение эквивалентно
      ¬(J → K) → ¬ (M ∧ N ∧ L)
      а оно, в свою очередь эквивалентно
      4) (M ∧ N ∧ L) → (J → K)
      (потому, что A → B эквивалентно ¬B → ¬A, в этом можно убедиться, например, построив таблицы истинности)
      Из формул 1) и 4) следует, что значения выражений M ∧ N ∧ L и J → K должны совпадать.
      Рассмотрим два случая.
      а) M ∧ N ∧ L = J → K =1
      Для M, N, L есть только один допустимый набор переменных: M=N=L = 1. Из-за условия 3) получаем: J=1 и, значит, K= 1. Получили одно решение: J=K=L = M=N =1
      б) M ∧ N ∧ L = J → K =0
      Для J и K есть только один набор значений J=1; K=0. Т.к. J=1, то 3-е выражение истинно при любом M. Поэтому нам подходит любой набор значений M , N, L, кроме M=N=L=1. Таких наборов 7.
      Всего получаем 1+7 = 8 решений.

  3. Лиза:

    Здравствуйте, как тут решать?
    Сколько существует различных наборов значений логических переменных x1, x2, ... x10, которые удовлетворяют всем перечисленным ниже условиям?

    ¬(x1 ≡ x2) ∧ (x1 ∨ x3) ∧ (¬x1 ∨ ¬x3) = 0
    ¬(x2 ≡ x3) ∧ (x2 ∨ x4) ∧ (¬x2 ∨ ¬x4) = 0
    ...
    ¬(x8 ≡ x9) ∧ (x8 ∨ x10) ∧ (¬x8 ∨ ¬x10) = 0

    В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x10 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
    Ответ: 20.

    • editor:

      Решение.
      Преобразуем уравнения к более понятному виду. Все уравнения однотипные, разберемся с первым.
      (x1 ∨ x3) ∧ (¬x1 ∨ ¬x3) означает, что x1 и x3 не могут быть равны (если оба 1 – неверна 2-я дизъюнкция; если оба 0 – первая). Поэтому (x1 ∨ x3) ∧ (¬x1 ∨ ¬x3) можно заменить на ¬(x1 ≡ x3). Далее условие
      ¬(x1 ≡ x2) ∧¬(x1 ≡ x3) = 0
      Можно заменить на более привычное – с 1 в правой части. Имеем:
      ¬ (¬(x1 ≡ x2) ∧¬(x1 ≡ x3) ) = 1
      (x1 ≡ x2) \/ (x1 ≡ x3) = 1
      Таким образом, исходная система эквивалентна такой системе (обозначим ее S2):
      (x1 ≡ x2) \/ (x1 ≡ x3) = 1
      (x2 ≡ x3) \/ (x2 ≡ x4) = 1

      (x8 ≡ x9) \/ (x8 ≡ x9) ) = 1
      Посмотрим, какие наборы значений x1, …, x10 могут быть решениями этой системы.
      Утверждение. Набор значений x1, …, x10 является решением системы S2 тогда и только тогда, когда в нем сначала идут одинаковые значения, а, начиная с какого-то места нули и единицы чередуются (наборы из 10 одинаковых значений тоже подходят).
      Доказательство. То, что такие наборы, подходят, - очевидно (выполнено x1 = x3 = … = x9; x2 = x4 = … = x10). Докажем, что других нет. Пусть набор x1, … , x10 – решение системы S2 и, скажем, x3≠x4. Тогда, т.к. (x3 ≡ x4) \/ (x3 ≡ x5) = 1, должно быть выполнено x3 ≡ x5 и, т.к. x3≠x4, то x4≠x5. Теперь аналогично получаем, x4 ≡ x6 и x5≠x6. И т.д.
      Таким образом, решение задается значением x1 и местом, где впервые появляются соседние различные значения. При x1 = 0 получаем 10 решений:
      0000000000
      0000000001
      0000000010
      0000000101
      0000001010
      0000010101
      0000101010
      0001010101
      0010101010
      0101010101
      Еще 10 аналогичных решений получаем для x1 = 1
      Ответ: 20

  4. Настя:

    Помогите решить
    Сколько различных решений имеет система логических уравнений
    (x1 ∨ x2) ∧ (x1 ∧ x2 → x3) ∧ (x1 ∨ y1) = 1
    (x2 ∨ x3) ∧ (x2 ∧ x3 → x4) ∧ (x2 ∨ y2) = 1
    ...
    (x5 ∨ x6) ∧ (x5 ∧ x6 → x7) ∧ (x5 ∨ y5) = 1
    (x6 ∨ x7) ∧ (x6 ∨ y6) = 1
    x7 ∨ y7 = 1
    где x1, …, x7, y1, …, y7, - логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
    Ответ:

  5. Жанна:

    Помогите, пожалуйста с решением системы:
    х1+не х2+не х3*х4=1 х3+не х4+не х5*х6=1 х5+не х6+не х7*х8=1 х7+не х8+не х9*х10=1

  6. editor:


    Это сообщение отправлено посредством контактной формы на Информатика http://ege-go.ru
    ОТ: Сергей
    Тема: B15.1
    -
    К задаче B15.1. нет мотивировки, почему исключены из подсчета пары:
    5 пар вида {11111, Y} и 5 пар вида {Y, 11111}, которые могли бы увеличить ответ с 11 до 21.
    Если ответ 11 правильный, то в чем здесь ловушка? Конкретно, почему не следует учитывать пары, указанные здесь выше?

    • editor:

      === Потому, что пары, о которых ты пишешь, - это и есть те пары, о которых написано в решении. Объяснения вида "5 пар вида {11111, X} и 5 пар вида {X, 11111}, здесь X – один из наборов 00000, 00001, 00011, 00111, 01111" более привычны для "взрослой" математики-информатики, чем для школьной. Видимо, это и привело к путанице - ведь неважно, какую букву использовать - X или Y, если сказано что-то вроде "здесь X – один из наборов 00000, 00001, 00011, 00111, 01111". Я добавил явный список решений и заменил X на R.
      Стало понятнее?
      Спасибо за хороший вопрос. Пиши еще.

      • Сергей:

        Мне было бы понятнее, если бы решение давалось без предварительных исключений, т.е. не для 5 наборов, а для всех 6:

        00000, 00001, 00011, 00111, 01111, 11111.

        Исключение повторного счета для {11111, 11111} следует произвести уже после определения 6 + 6 =12 вычитанием единицы.

        Доходчивость такого объяснения состоит в том, что никакие изначальные предположения не делаются, расчет производится "в лоб": суммируются количества строк и столбцов таблицы исходов и вычитается повторный счет их пересечения.

  7. editor:

    От: Вячеслав
    Тема: По поводу B15
    Тело сообщения:
    Не лучше ли было бы начать объяснение с системой попроще, например:
    x1 /\ x2 = 0
    x3 \/ x4 = 1
    Или что-то вроде этого. Чтобы легче было разглядеть откуда что берется

    --
    Это сообщение отправлено посредством контактной формы на Информатика http://ege-go.ru

    • editor:

      Вы правы. Начинать нужно с того, что понятно ученику. Но этот уровень разный у разных учеников. Уточните пож - к какому месту на сайте относится Ваше замечание.
      PS Видели ли Вы лекцию по логике в разделе ВИДЕО? Прямая ссылка: http://www.ustream.tv/recorded/20482158

      • Buckstabue:

        Здравствуйте, приятно удивлен таким быстрым ответом. С математикой в школе у меня проблем нет, до C3 включительно на математике ЕГЭ решаю всё быстро и практически без ошибок и могу порассуждать в C5, С С4 по информатики особых проблем не возникает т.е. я не совсем безнадежен. А вот B15 уже третий день не могу "натаскать". Видео видел не один раз, видел/читал решения других ресурсов и везде всё начинается со сложных для меня примеров. Один раз на яндексе дошел-таки до сильного упрощения и вышло, что обоим системам соответствовало 6 независимых наборов( 4 вариант кажись ). И вот тут возник вопрос: когда наборы складывать, а когда перемножать? Я сложил по аналогии с вашим видео, а в ответе узнал, что их надо было перемножать, обидно и слава богу это был только тренировочный егэ

        • editor:

          Давай по порядку. Натаскиваться не нужно - нужно разбираться.
          1. Разбор твоей задачи поместил на странице http://ege-go.ru/zadania/grb/b15/b15-2more/ (задача 2013-B15-1 -1-я задача на странице)
          Чего непонятно пиши. Кстати, напиши, пож, если есть что-то непонятное в видео.

          2. Насчет сложения и умножения при подсчете количеств объектов. Если совсем коротко, получится примерно так.
          2.1. Пусть множества А и В не пересекаются, в множестве А - p объектов, в множестве B - q объектов.
          Тогда в объединении множеств А и В будет p+q объектов.
          Пример. У Жени 3 конфеты, у Вали - 4 конфеты (у каждой - свои конфеты!). Сколько конфет у девочек вместе?

          2.2. Пусть в множестве А - p объектов, в множестве B - q объектов. Рассмотрим множество С, которое состоит из всех пар вида (x, y), где x - элемент множества A, y = элемент множества B (С называется декартовым произведением множеств А и В).
          Тогда в множестве С будет p*q объектов.
          Пример. На второе в школьной столовой всегда дают "что-то" с гарниром. "Что-то" бывает 4-х видов: котлета, отварное мясо, колбаса, рыба. Гарнир бывает 3-х видов: пюре, гречневая каша, макароны. Сколько разных видов второго бывает в школьной столовой.

          Упражнение 1. Придумай еще по две задачи для каждого случая.
          Упражнение 2. Реши пример из п. 2.2 - выпиши все виды еды

          Успехов!

  8. Маг:

    Добрый день. Ничего не понял, а можно как нибудь ещё подробней? (для особо недоразвитых))

    • editor:

      Можно для всех 🙂 Время есть - разберемся.

      Давай сделаем так.
      1. Посмотри пож другие материалы по логике на сайте:
      1) справочный материал в разделе "Темы" (прямая ссылка: http://ege-go.ru/temy/%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0/ )
      2) лекцию в разделе "Видео" (прямая ссылка: http://www.ustream.tv/recorded/20482158 )
      2. Посмотри материалы на основной странице про B15 (http://ege-go.ru/zadania/grb/b15/ )

      Будут вопросы - напиши. Постарайся писать не "ничего не понял", а не понял такое-то место.

      3. Перечитай решения задач на этой странице.

  9. Nikita:

    B15.1
    точно ответ 11 ?
    я никак не могу понять,почему не 12

  10. Спасибо за разбор

  11. Виталий:

    Спасибо за материал, наконец-то разобрался.

  12. В [B]B15.5 (ege.yandex.ru-5)[/B] опечатка [B](x1->y1) /\ (x1->y1) =1[/B]
    Должно быть [B](x1->y1) /\ (x2->y2) =1[/B]

 
 

Ответить editor

 




 
 

 
 
Яндекс.Метрика