infoegehelp.ru

Успешно сдать ЕГЭ по информатике
  • Главная
  • Контакты
  • Карта сайта
  • Помощь сайту
Важно
  • Демо варианты ЕГЭ
  • Учим числа: 2 в степени
  • Биты, байты, килобайты
Решение задач
  • Задачи вне основных разделов информатики
Разделы информатики
  • 2011-12-18-14-33-54Системы счисления
  • 2011-12-18-16-45-20Алгебра логики
  • 2011-12-18-16-55-26Программирование
  • 2011-12-18-16-53-40Кодирование информации
  • 2011-12-18-16-56-19Компьютерные сети и Интернет
  • -excelЭлектронные таблицы (Excel)
  • 2011-12-18-16-57-50Базы данных
  • 2011-12-18-16-58-50Графы
  • 2011-12-18-17-00-15Файловая система
  • Устройство компьютера
  • ПО компьютера

Разбор задачи B15 (демо ЕГЭ 2013)

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2 y3, y4, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1
(¬y1 \/ y2) /\ (¬y2 \/ y3) /\ (¬y3 \/ y4) = 1
(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, y1, y2 y3, y4, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.
Ответ: 15
Решение:

Преобразуем систему уравнений к виду:

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

(y1 → y2) /\ (y2 → y3) /\ (y3 → y4) = 1 (2)

(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1 (3)

Розовым выделено уравнение, которое было преобразовано. ¬y1 \/ y2=y1 → y2. Аналогично и для остальных частей данного уравнения.

Решим уравнение (1).

1 способ

Уравнение (1) содержит импликации (→), связанные конъюнкцией (/\). Соответственно, чтобы уравнение было истинно, все входящие импликации должны быть истинны:

x1 → x2=1,

x2 → x3=1,

x3 → x4=1.

Таблица истинности для импликации на примере x1 → x2:

x1x2
x1→x2
0 0 1
0 1 1
1 0 0
1 1 1

Розовым выделена комбинация, когда импликация ложна. Видно, что в ней идут подряд "1" и "0". Выпишем комбинации для x1x2x3x4, в которых не встречается подряд "1" и "0", чтобы импликации x1 → x2, x2 → x3, x3 → x4 не были равны 0-ю.

x1
x2
x3
x4
0
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
1
1
1
1

Получили 5 комбинаций.

2 способ

Решим методом от противного. Рассмотрим случаи, когда уравнение (x1 → x2) /\ (x2 → x3) /\ (x3 → x4)=0.

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

Исходя из этого определим случаи, когда импликация ложна.

Если x1 → x2=0:

x1
x2
x3
x4
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1

x1=1, x2=0,

x3 и x4 - 0 или 1, поэтому они дают 22=4 комбинации.

Если x2 → x3=0:

x1
x2
x3
x4
0
1
0
0
0
1
0
1
1
1
0
0
1
1
0
1

x2=1, x3=0,

x1 и x4 - 0 или 1, поэтому они дают 4 комбинации.

Если x3 → x4=0:

x1
x2
x3
x4
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
0

x3=1, x4=0,

x1 и x2 - 0 или 1, поэтому они дают 4 комбинации.

Получили 4*3=12 комбинаций.

Также нужно учеть повторные комбинации. В данном случае повторная комбинация одна: 1010. В таблицах выше такая комбинация выделена синей рамкой. Она встретилась 2 раза, поэтому общее число комбинаций с учетом повторов:

12−1=11.

Мы решали уравнение методом от противного. Теперь перейдем к исходному уравнению.

Общее число комбинаций при 4-х переменных: 24=16. 16-11=5 комбинаций.

Перейдем к уравнению (2):

(y1 → y2) /\ (y2 → y3) /\ (y3 → y4) = 1.

Это уравнение содержит переменные y1, y2, y3, y4, которые не связаны с уравнением (1). Уравнения (1) и (2) независимы друг от друга. Но вид уравнения (2) аналогичен виду уравнения (1), которое мы решили выше. Поэтому получаем 5 комбинаций.

y1
y2
y3
y4
0
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
1
1
1
1

Добавим к системе уравнение (3):

(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1

Выпишем рядом решения уравнений (1) и (2)

y1
y2
y3
y4
  
   
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1

Будем решать систему уравнений методом от противного. Уравнение (3) равно 0-ю.

y1 → x1=0:

y1=1, x1=0

y1
y2
y3
y4

   
 
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1

Получили 4 комбинации.

y2 → x2=0:

y2=1, x2=0. Строку 1111 (y1y2y3y4) не берем во избежания повторов.

y1
y2
y3
y4

   
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1

Получили 3 комбинации.

y3 → x3=0

y3=1, x3=0. Строки 1111, 0111 (y1y2y3y4) не берем во избежания повторов.

y1
y2
y3
y4

   
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1

Получили 2-е комбинации.

y4 → x4=0

y4=1, x4=0. Строки 1111, 0111, 0011 (y1y2y3y4) не берем во избежания повторов.

y1
y2
y3
y4

   
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1

Получили 1-у комбинацию.

Всего комбинаций: 4+3+2+1=10.

Мы решали систему уравнений методом от противного. Теперь перейдем к исходной системе.

Общее число комбинаций: 5*5=25. Уравнения (1) и (2) дают по 5 независимых комбинаций.

25-10=15 комбинаций.

Перейти к другим задачам.

 

Rambler's Top100

© Латыпова В.А., 2012-2020. Все права защищены.
Копирование материалов сайта только с разрешения администрации сайта