Решение задачи В15 ЕГЭ по информатике

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

Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны.

Результатом ИМПЛИКАЦИИ является ЛОЖЬ только  тогда, когда условие А истинно, а следствие В ложно.

Определим сначала на скольких наборах  значений переменных Х1, Х2 и Х3 будет  истинно уравнение 1.

В таблице  чёрным шрифтом представлены  все возможные наборы  значений трёх переменных.

Зелёным шрифтом  в таблице вписаны значения  эквивалентности соответствующих переменных.

Можно видеть, что  второй и седьмой наборы  дадут  0,  как результат импликации в первом  уравнения (  1 -> 0 = 0 ).

Следовательно первое уравнение с тремя переменными будет истинно только на 6  наборах.

Рассмотрим первое и второе уравнения вместе, приняв во внимание, что  второе  уравнение  включает ещё одну переменную Х4.

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

Аналогично можно показать , что:

 -  3 уравнения с 5-ю переменными будут истинны на 10-ти наборах;

 -  4 уравнения с 6-ю переменными будут истинны на 12-ти наборах;

и, наконец,

- 5 уравнений с 7-ю переменными будут истинны на 14-ти наборах.

Ответ . Представленная в задаче система  из 5-ти  уравнений  с 7-ю неизвестными имеет  14 решений.

Решение задачи В15

(диагностическая работа №2)

ЕГЭ

по информатике

Решение системы уравнений,

содержащих логические переменные

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

ниже, система уравнений?

1. (Х1=Х2) (Х2=Х3) = 1

2. (Х2=Х3) (Х3=Х4) = 1

3. (Х3=Х4) (Х4=Х5) = 1

4. (Х4=Х5) (Х5=Х6) = 1

5. (Х5=Х6) (Х6=Х7) = 1

Таблицы истинности для эквивалентности и импликации

выглядят следующим образом

Эквивалентность

Импликация

A

A

B

0

B

0

F

0

0

0

0

F

1

1

1

1

1

1

1

1

0

0

0

0

0

1

1

0

1

1

Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое

выражение, которое будет истинным тогда и только тогда, когда оба

исходных выражения одновременно истинны или ложны.

Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно.

Определим сначала на скольких наборах значений переменных Х1, Х2 и Х3 будет истинно уравнение 1.

В таблице чёрным шрифтом представлены все возможные наборы значений трёх переменных.

=

X1

X2

X3

=

0

1

1

0

0

0

1

1

0

0

1

0

0

0

0

1

1

1

0

0

0

0

0

1

1

0

0

1

0

1

0

1

1

0

1

1

1

1

1

1

Зелёным шрифтом в таблице

вписаны значения эквивалентности

соответствующих переменных.

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

Следовательно первое уравнение с тремя переменными будет истинно

только на 6 наборах.

Рассмотрим первое и второе уравнения вместе, приняв во внимание, что второе уравнение включает ещё одну переменную Х4.

В случае эквивалентности Х2 и Х3 (Х2=Х3=1) Х3 и Х4 обязательно

должны быть эквивалентны, то - есть должно быть Х3=Х4=1, в

противном случае импликация второго уравнения будет равна 0 и

второе уравнение не будет истинным.

Этому случаю соответствуют наборы , в которых эквивалентность

переменных выделена зелёным.

В тех же случаях, когда Х2=Х3=0

(красные цифры) Х3 и Х4 могут

быть как эквивалентны Х3=Х4=1

так и неэквивалентны Х3=Х4=0,

что порождает два

дополнительных набора.

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

X1

0

=

0

1

X2

0

0

=

0

1

0

X3

1

1

0

=

0

1

0

0

1

1

  Х4

1

0

1

0

0

1

  0

0

0

1

1

1

  0

0

1

0

0

  1

1

1

0

1

  1

1

1

0

1

1

0

1

1

  0

1

  1

  1

Аналогично можно показать , что:

- 3 уравнения с 5-ю переменными будут истинны на 10-ти наборах;

- 4 уравнения с 6-ю переменными будут истинны на 12-ти наборах;

и, наконец,

- 5 уравнений с 7-ю переменными будут истинны на 14-ти наборах.

Ответ .

Представленная в задаче система из 5-ти уравнений с 7-ю неизвестными

имеет 14 решений.