Курсовая с практикой на тему Классы булевых функций: симметрические, регулярные, уравновешенные, их количество и распознавание

Содержание:

Введение. 3

Глава
1. Понятие классов булевых функций. 5

1.1.
Представление булевых функций. 5

1.2.
Формы булевых функция. 13

Глава
2. Количество и распознавание классов булевых функций. 17

2.1.
Распознавание классов булевых функций. 17

2.2.
Количество классов булевых функций. 29

Заключение. 34

Список литературы.. 36

Введение:

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

а) эквивалентные функции в каждом классе обладают сходными свойствами
и

б) число представителей в каждом классе намного меньше, чем у
булевых функций.

Ранее, когда две булевы функции переменной отличаются только
перестановкой или дополнением своих переменных, они попадают в классы эквивалентности.
Классификация классов аффинной эквивалентности косетов кода Рида-Мюллера первого
порядка по криптографическим свойствам, таким как корреляционная устойчивость, устойчивость
и характеристики распространения. Три переменные булевы функции во имя правил клеточных
автоматов 3-окрестности были классифицированы на основе расстояния Хэмминга относительно
линейных правил. Характеристика 3-переменных нелинейных булевых функций была предпринята
тремя различными способами: булевыми производными, девиантными состояниями и матрицами.

Объект исследования – классы булевых функций.

Предмет исследования – рассмотреть классы булевых функций.

Цель исследования – рассмотреть классы булевых функций:
симметрические, регулярные, уравновешенные, их количество и распознавание

Задачи:

— Представление булевых функций.

— Формы булевых функция.

— Распознавание классов булевых функций.

— Количество классов булевых функций.

Структура работы представлена введением, двумя главами,
заключением и списком литературы.

Заключение:

Суть данной работы заключается в ее систематическом
рассмотрении классов булевых функций с акцентом на выдающиеся бинарные операции,
такие как расстояние Хэмминга, XOR и CVT.

В курсе математического анализа изучаются функции,
определённые на числовой прямой или на отрезке числовой прямой или на (гипер-)
плоскости и т.п. Так или иначе область определения – непрерывное множество. В курсе
дискретной математики изучаться должны функции, область определения которых
– дискретное множество*.
Простейшим (но нетривиальным) таким множеством является множество, состоящее из
двух элементов. Так мы и приходим к понятию булевой функции.

Булевой
функцией от n аргументов
называется функция f из n-ой степени множества {0, 1} в
множество { 0, 1 }.

Иначе говоря, булева функция – это функция, и аргументы и
значение которой принадлежит множеству {0, 1}. Множество {0, 1} мы будем в
дальнейшем обозначать через B.

Булеву функцию от n аргументов можно рассматривать как n-местную алгебраическую операцию на
множестве B. При этом
алгебра <B;W>,
где W – множество всевозможных булевых функций, называется алгеброй логики.

Конечность области определения функции имеет важное
преимущество – такие функции можно задавать перечислением значений при
различных значениях аргументов. Для того, чтобы задать значение функции
от n переменных, надо определить значения для каждого из 2n наборов.

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

Фрагмент текста работы:

Глава 1. Понятие классов булевых функций 1.1. Представление булевых функций Булева алгебра — это алгебра логики. Он имеет дело с
переменными, которые могут иметь два дискретных значения, 0 (False) и 1 (True);
и операции, которые являются логическими. Первый метод манипулирования
символической логикой был изобретен Джорджем Булом и позже стал известен как
булевая алгебра.

Булева алгебра теперь стала незаменимым инструментом в
информатике из-за ее широкой применимости в теории коммутации, строительстве
основных электронных схем и дизайне цифровых компьютеров.

Знаменитый Готфрид Вильгельм Лейбниц сформулировал понятие
"математическая логика", задачи которой были доступны лишь узкому
кругу ученых. Это направление не вызвало особого интереса, и до середины XIX
века мало кто знал математическую логику[2].

Большой интерес в научных сообществах вызвал спор, в котором
англичанин Джордж Буль объявил о намерении создать отрасль математики, не
имеющую абсолютно никакого практического применения. Как мы помним из истории,
в те времена активно развивалось промышленное производство, разрабатывались
всевозможные вспомогательные машины и станки, то есть все научные открытия
имели практическую направленность.

Забегая вперед, скажем, что булева алгебра является наиболее
часто используемой частью математики в современном мире. Так что Буль лишился
аргумента.

Сама личность автора заслуживает особого внимания. Даже
принимая во внимание, что в прошлом люди росли до нас, надо все же отметить,
что в 16 лет Дж. Буль свободно владел пятью иностранными языками, а в свободное
время читал работы Ньютона и Лагранжа.