Взаємозв’язок між матроїдами і монотонними булевими функціями електрічних кіл

Аннотация

Установлення взаємозв'язку між матроїдами і монотонними булевими функціями (МБФ) дозволяє ввести класифікацію матроїдів за видами (як сімейств підмножин Шпернера), а також удосконалювати теорію електричних кіл, зокрема, при символьному описуванні функцій цих кіл і знаходженні їх остовів і циклів. Введені поняття базової і циклоїдної МБФ, видів і діаграм матроїдів, заповнених матроїдів. Принцип квадріальності розширений на МБФ, відповідні будь-яким матроїдам. Доведено, що базова і циклоїдна МБФ будь-якого матроїда, а також базова і циклоїдна МБФ дуального до нього матроїда утворюють таку квадріальну систему, що по одній з цих МБФ нескладно знайти три інші.