Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по информатике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 294 RSS
←   Январь 2018   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/228
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

294 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Консультации по информатике


РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты в разделе

Коцюрбенко Алексей aka Жерар
Статус: Мастер-Эксперт
Рейтинг: 607
∙ повысить рейтинг » 		CradleA
Статус: Профессионал
Рейтинг: 252
∙ повысить рейтинг » 		mklokov
Статус: 6-й класс
Рейтинг: 42
∙ повысить рейтинг »

∙ Информатика

Номер выпуска:330
Дата выхода:11.01.2018, 19:15
Администратор рассылки:Андреенков Владимир (Академик)
Подписчиков / экспертов:22 / 22
Вопросов / ответов:1 / 1

Консультация # 192277: Уважаемые эксперты! Пожалуйста, ответьте на вопрос: Сколько различных решений имеет система уравнений (X1∨X2)∧(¬X3 ∨¬X4) = 0 (X3 ∨X4)∧(¬X5 ∨¬X6) = 0 (X5 ∨X6)∧(¬X7 ∨¬X8) = 0 (X7 ∨X8)∧(¬X9 ∨¬X10) = 0 (X9 ∨X10)∧(¬X11∨¬X12) = 0 где x1,...

Консультация # 192277:

Уважаемые эксперты! Пожалуйста, ответьте на вопрос:

Сколько различных решений имеет система уравнений
(X1∨X2)∧(¬X3 ∨¬X4) = 0
(X3 ∨X4)∧(¬X5 ∨¬X6) = 0
(X5 ∨X6)∧(¬X7 ∨¬X8) = 0
(X7 ∨X8)∧(¬X9 ∨¬X10) = 0
(X9 ∨X10)∧(¬X11∨¬X12) = 0

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

Дата отправки: 01.01.2018, 19:12
Вопрос задал: yak_2010 (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Коцюрбенко Алексей aka Жерар (Мастер-Эксперт):

Здравствуйте, yak_2010!

Первое уравнение содержит функцию (x1∨x2)∧(¬x3∨¬x4) четырёх переменных (x1, x2, x3 и x4). Чтобы определить, при каких значениях этих переменных функция равна 0, составим таблицу значений функции (добавиви в неё для облегчения расчётов значения промежуточных выражений x1∨x2 и ¬x3∨¬x4):

Из таблицы видно, что функция принимает нулевое значение на наборах 0000, 0001, 0010, 0011, 0111, 1011 и 1111. Поскольку функция не зависит от остальных переменных (x5 ... x12), то каждый из этих наборов представляет собой на самом деле несколько наборов. Например, 0000 - это наборы 000000000000, 000000000001, 000000000010,... 0000011111110, 000011111111, всего 256 наборов, в которых переменные x5...x12 принимают все возможные значения.
Для упрощения обычно используют сокращённую запись, в которой вместо двух наборов, отличающихся только значением одной переменной (0 или 1), используют один, в котором эта переменная имеет специальное значение x (означающее "0 или 1"). То есть, вместо 000000000000 и 000000000001 можно записать 00000000000x, вместо 00000000000x и 00000000001x - 0000000000xx и т.д.
Соответственно, найденные семь наборов запишутся как 0000xxxxxxxx, 0001xxxxxxxx, 0010xxxxxxxx, 0011xxxxxxxx, 0111xxxxxxxx, 1011xxxxxxxx и 1111xxxxxxxx. Если же объединить первые четыре набора (они отличаются только значением переменных x3 и x4 ) и последние два (отличающиеся значением переменной x2), то решение примет вид {00xxxxxxxxxx, 0111xxxxxxxx, 1x11xxxxxxxx}.
Определить количество наборов при такой форме записи решения очень просто: каждый компонент задаёт 2k наборов, где k - число значений x в этом компоненте. То есть в данном случае 00xxxxxxxxxx задаёт 210 = 1024 набора, 0111xxxxxxxx - 28 = 256 и 1x11xxxxxxxx 29 = 512, а всего 1024 + 256 + 512 = 1768 наборов, удовлетворяющих первому уравнению.

Можно заметить, что второе уравнение отличается от первого только используемыми переменными (x3, x4, x5 и x6 вместо x1, x2, x3 и x4 соответственно, то есть номера переменных отличаются на 2). Следовательно, множество на боров переменных, задающее решение второго уравнения, можно получить путём сдвига всех значений из предыдущего решения {00xxxxxxxxxx, 0111xxxxxxxx, 1x11xxxxxxxx} вправо на 2: {xx00xxxxxxxx, xx0111xxxxxx, xx1x11xxxxxx} - также 1768 наборов.
Решение, удовлетворяющее обоим уравнением, является пересечением этих двух решений. Поскольку каждая логическая функция может принимать некоторое значение на одном из следующих множеств значений переменной: {0}, {1}, {0,1} (которым соответствуют 0, 1 и x в соращённой форме записи), то из стандартных правил пересечения множеств ({0}∩{0} = {0}∩{0,1} = 0, {1}∩{1} = {1}∩{0,1} = 1, {0,1}∩{0,1} = {0,1}, {0}∩{1} = ∅ - пустое множество) следует правило выполнения операции "пересечения" над значениями 0, 1 и x:

(знак " ;-" означает, что пересечения нет). В случае нескольких переменных операция "пересечения" выполняется "поразрядно" - над каждой из переменных.
В данном случае пересечением двух наборов-решений будет {00xxxxxxxxxx, 0111xxxxxxxx, 1x11xxxxxxxx}∩{xx00xxxxxxxx, xx0111xxxxxx, xx1x11xxxxxx} = {00xxxxxxxxxx∩xx00xxxxxxxx, 00xxxxxxxxxx∩xx0111xxxxxx, 00xxxxxxxxxx∩xx1x11xxxxxx, 0111xxxxxxxx∩xx00xxxxxxxx, 0111xxxxxxxx∩xx0111xxxxxx, 0111xxxxxxxx∩xx1x11xxxxxx, 1x11xxxxxxxx∩xx00xxxxxxxx, 1x11xxxxxxxx∩xx0111xxxxxx, 1x11xxxxxxxx∩xx1x11xxxxxx} = {0000xxxxxxxx, 00011xxxxxxx, 001x11xxxxxx, ∅, ∅, 011111xxxxxx, ∅, ∅, 1x1111xxxxxx} = {0000xxxxxxxx, 00011xxxxxxx, 001x11xxxxxx, 011111xxxxxx, 1x1111xxxxxx} - это решение содержит 256+128+128+64+128=704 набора.

Аналогично третье уравнение отличается от второго лишь используемыми переменными (x5, x6 , x7 и x8 вместо x3, x4, x5 и x6 соответственно). Поэтому множество наборов значений переменных, являющихся его решением, можно записать как {xxxx00xxxxxx, xxxx0111xxxx, xxxx1x11xxxx}, а его пересечением с уже найденным решением первых двух уравнений будет {0000xxxxxxxx, 00011xxxxxxx, 001x11xxxxxx, 011111xxxxxx, 1x1111xxxxxx}∩{xxxx00xxxxxx, xxxx0111xxxx, xxxx1x11xxxx} = {0000xxxxxxxx∩xxxx00xxxxxx, 0000xxxxxxxx∩xxxx0111xxxx, 0000xxxxxxxx∩xxxx1x11xxxx, 00011xxxxxxx∩xxxx00xxxxxx, 00011xxxxxxx∩xxxx0111xxxx, 00011xxxxxxx∩xxxx1x11xxxx, 001x11xxxxxx∩xxxx00xxxxxx, 001x11xxxxxx∩xxxx0111xxxx, 001x11xxxxxx∩xxxx1x11xxxx, 011111xxxxxx∩xxxx00xxxxxx, 011111xxxxxx∩xxxx0111xxxx, 011111xxxxxx∩xxxx1x11xxxx, 1x1111xxxxxx∩xxxx00xxxxxx, 1x1111xxxxxx∩xxxx0111xxxx, 1x1111xxxxxx∩xxxx1x 11xxxx} = {000000xxxxxx, 00000111xxxx, 00001x11xxxx, ∅, ∅, 00011x11xxxx, ∅, ∅, 001x1111xxxx, ∅, ∅, 01111111xxxx, ∅, ∅, 1x111111xxxx} = {000000xxxxxx, 00000111xxxx, 00001x11xxxx, 00011x11xxxx, 001x1111xxxx, 01111111xxxx, 1x111111xxxx} = {000000xxxxxx, 00000111xxxx, 000x1x11xxxx, 001x1111xxxx, 01111111xxxx, 1x111111xxxx} - всего 64+16+64+32+16+32=224 набора.

Четвёртому уравнению (также отличающемуся от третьего лишь используемыми переменными) соответствует решение {xxxxxx00xxxx, xxxxxx0111xx, xxxxxx1x11xx}, пересечением которого с предыдущим решением будет {000000xxxxxx, 00000111xxxx, 000x1x11xxxx, 001x1111xxxx, 01111111xxxx, 1x111111xxxx}∩{xxxxxx00xxxx, xxxxxx0111xx, xxxxxx1x11xx} = {000000xxxxxx∩xxxxxx00xxxx, 000000xxxxxx∩xxxxxx0111xx, 000000xxxxxx∩xxxxxx1x11xx, 00000111xxxx∩xxxxxx00xxxx, 00000111xxxx∩xxxxxx0111xx, 00000111xxxx∩xxxxxx1x11xx, 000x1x11xxxx∩xxxxx x00xxxx, 000x1x11xxxx∩xxxxxx0111xx, 000x1x11xxxx∩xxxxxx1x11xx, 001x1111xxxx∩xxxxxx00xxxx, 001x1111xxxx∩xxxxxx0111xx, 001x1111xxxx∩xxxxxx1x11xx, 011x1111xxxx∩xxxxxx00xxxx, 011x1111xxxx∩xxxxxx0111xx, 011x1111xxxx∩xxxxxx1x11xx, 1x111111xxxx∩xxxxxx00xxxx, 1x111111xxxx∩xxxxxx0111xx, 1x111111xxxx∩xxxxxx1x11xx} = {00000000xxxx, 0000000111xx, 0000001x11xx, ∅, ∅, 0000011111xx, ∅, ∅, 000x1x1111xx, ∅, ∅, 001x111111xx, ∅, ∅, 011x111111xx, ∅, ∅, 1x11111111xx} = {00000000xxxx, 0000000111xx, 0000001x11xx, 0000011111xx, 000x1x1111xx, 001x111111xx, 011x111111xx, 1x11111111xx} = {00000000xxxx, 0000000111xx, 0000001x11xx, 0000011111xx, 000x1x1111xx, 0x1x111111xx, 1x11111111xx} - всего 16+4+8+4+16+16+8=72 набора.

Наконец решением последнего уравнения будет {xxxxxxxx00xx, xxxxxxxx0111, xxxxxxxx1x11}, и его пересечение с решением остальных четырёх уравнен ий {00000000xxxx, 0000000111xx, 0000001x11xx, 0000011111xx, 000x1x1111xx, 0x1x111111xx, 1x11111111xx}∩{xxxxxxxx00xx, xxxxxxxx0111, xxxxxxxx1x11} = {00000000xxxx∩xxxxxxxx00xx, 00000000xxxx∩xxxxxxxx0111, 00000000xxxx∩xxxxxxxx1x11, 0000000111xx∩xxxxxxxx00xx, 0000000111xx∩xxxxxxxx0111, 0000000111xx∩xxxxxxxx1x11, 0000001x11xx∩xxxxxxxx00xx, 0000001x11xx∩xxxxxxxx0111, 0000001x11xx∩xxxxxxxx1x11, 0000011111xx∩xxxxxxxx00xx, 0000011111xx∩xxxxxxxx0111, 0000011111xx∩xxxxxxxx1x11, 000x1x1111xx∩xxxxxxxx00xx, 000x1x1111xx∩xxxxxxxx0111, 000x1x1111xx∩xxxxxxxx1x11, 0x1x111111xx∩xxxxxxxx00xx, 0x1x111111xx∩xxxxxxxx0111, 0x1x111111xx∩xxxxxxxx1x11, 1x11111111xx∩xxxxxxxx00xx, 1x11111111xx∩xxxxxxxx0111, 1x11111111xx∩xxxxxxxx1x11} = {0000000000xx, 000000000111, 000000001x11, ∅, ∅, 000000011111, ∅, ∅, 0000001x1111, ∅, ∅, 000001111111 , ∅, ∅, 000x1x111111, ∅, ∅, 0x1x11111111, ∅, ∅, 1x1111111111} = {0000000000xx, 000000000111, 000000001x11, 000000011111, 0000001x1111, 000001111111, 000x1x111111, 0x1x11111111, 1x1111111111} будет решением задачи. Оно задаёт 4+1+2+1+2+1+4+4+2=21 набор.

Консультировал: Коцюрбенко Алексей aka Жерар (Мастер-Эксперт)
Дата отправки: 06.01.2018, 18:59
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!
В избранное