Помогите найти сложность булевой матрицы

[denisovviktor]

Задача по дискретной математике
Дана матрица 0ей и 1иц. Найти минимальную сложность матрицы в базисе сложение по модулю 2. Скорее всего здесь нужна схемная сложность. и глубина

$L ( x \oplus y ) =?$

$$\begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 0 & 1 & 0\end{pmatrix}$$

Попытка решить:
В виде функций получается:

$f(x) = x_1 \oplus x_3 \oplus x_5 \oplus x_6 \oplus x_7 $

$f(y) = y_1 \oplus y_2 \oplus y_3 \oplus y_4 \oplus y_6 $

Для одной функции вроде такая схема получается

То есть по моему сложность 4, но может возможно сделать меньшую сложность
И как делать для 2-х функций?

[kotenok gav]

Когда вашу тему отнесут в Карантин, переоформите ваше сообщение вот так:

denisovviktor в сообщении #1315698 писал(а):

Задача по дискретной математике
Дана матрица 0-ей и 1-иц. Найти минимальную сложность матрицы в базисе сложение по модулю 2. Скорее всего здесь нужна схемная сложность и глубина.

$L\{x\oplus y\}=?$

$$\begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 0 & 1 & 0\end{pmatrix}$$

В виде функций получается:
$f(x) = x_1\oplus x_3\oplus x_5\oplus x_6\oplus x_7$
$f(y) = y_1\oplus y_2\oplus y_3\oplus y_4\oplus y_6$

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Sender]

denisovviktor в сообщении #1315698 писал(а):

Найти минимальную сложность матрицы в базисе сложение по модулю 2.

Честно говоря, для меня это просто набор слов. Я слышал только о схемной сложности булевой функции или системы функций. Да и сложение по модулю 2 базиса вроде как не образует... Что там в учебнике пишут по этому поводу, открывать не пробовали?

[denisovviktor]

Тогда переформулирую вопрос
Какая схемная сложность системы булевых функций (система булеых функций задана матрицей)
В базисе {XOR} или для примера как это решается в базисе {AND,OR,NOT}

L( x \oplus y ) = ?
\begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 \end{pmatrix}

А какой учебник посоветуйте?

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

[gogoshik]

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

[eugensk]

Вот эта ваша матрица 7х2 что вообще означает, можете пояснить? Может, она означает наборы, на которых булева функция равна 1? Если да, то что делает $y$?

[Aritaborian]

Задача-то откуда взялась? Обычно если есть задача, то есть и некий курс, некий предмет. А к курсу и предмету, как правило, прилагаются учебники. Не приснилась же вам она.

[Sender]

denisovviktor в сообщении #1315882 писал(а):

А какой учебник посоветуйте?

Не могу сказать, что профессионал в этом, но мне понравились лекции Чашкина по дискретной математике:
http://new.math.msu.su/department/dm/dmmc/EDU/DM07.pdf
Кстати, там на стр 118 приводится пример с универсальной системой функций, подозрительно похожий на ваш. И в конце главы приводятся схожие задачи, но в них говорится именно о линейных функциях и о матрицах их коэффициентов.

[Aritaborian]

Можно также поискать в следующих книгах.
Новиков. Дискретная математика для программистов.
Кнут, Орен, Паташник. Конкретная математика.

[denisovviktor]

Это задача которую дал решать преподаватель по курсу Распределенные величины
Вот как выглядит задание:

Насколько я понимаю это и есть матрица коэффициентов для линейных функций, потомучто когда я переписал эту матрицу в виде линейных функций преподаватель сказал, что это правильное начало решения

f(x) = x_1 \oplus x_3 \oplus x_5 \oplus x_6 \oplus x_7

f(y) = y_1 \oplus y_2 \oplus y_3 \oplus y_4 \oplus y_6

Книга, которую он посоветовал для решения А. В. Чашкин Лекции по дискретной математике
Пример из этой книги, чем то похож на мой но мне не понятен, так как здесь функции еще и зависят от (2^n)-1 а вот что это означает не ясно:



При попытках решения рассказал про сложность функциональных элементов
Но он спросил конкретно какая сложности матрицы (не схемы из функциональных элементов) в базисе { \oplus }

[gogoshik]

denisovviktor, существует несколько способов представления систем булевых функций. Вы можете представить данную систему в виде таблицы истинности? Сколько вам дано линейных функций и переменных?

[denisovviktor]

Дано 2 лениейных функции и 7 переменных
f_1 = x_1 \oplus x_3 \oplus x_5 \oplus x_6 \oplus x_7

f_2 = x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_6

таблица истинности для 7 переменных получится на 128 строк
но может вот так будет верная таблица:

[denisovviktor]

Хотя еще раз посмотрел на задание возможно все так 2е переменные x и y