|
|
ОглавлениеКонтрольная работа 1. Простейшие свойства функций алгебры логики Контрольная работа 2. Специальные представления булевых функций Контрольная работа 3. Полнота систем функций алгебры логики Для бесплатного чтения доступна только часть главы! Для чтения полной версии необходимо приобрести книгуТеоретическая частьОпределение 1. Набор , , называется двоичным (булевым). Число n называется длиной набора. Весом набора (нормой) называется число единиц в наборе, таким образом, вес набора . Номером набора называется число где n — длина набора. Набор , , является двоичным разложением своего номера. Множество всех двоичных наборов образует n-мерный булев куб B n (или ). Это множество образует метрическое пространство, где для каждой пары элементов пространства и определено число — расстояние Хэмминга , удовлетворяющее всем аксиомам метрики. Понятно, что . Если , то наборы и называются соседними. Если то наборы противоположны. Таким образом, расстояние Хэмминга — число позиций, в которых соответствующие символы двух наборов одинаковой длины различны. Говорят, что набор предшествует набору если i = 1, …, n. Определение 2. Булевой функцией (логической функцией или функцией алгебры логики) f от n аргументов называется отображение f: → {0, 1}. Элементы булева множества {0, 1} обычно интерпретируют в алгебре высказываний как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Неотрицательное целое число n еще называют арностью, или местностью, функции, в случае n = 0 булева функция превращается в булеву константу. Множество всех булевых функций от любого числа аргументов часто обозначается P2, а от n аргументов — P2 (n). Булевы функции названы по фамилии математика Джорджа Буля. Перечислим булевы функции. Нульместными булевыми функциями (n = 0) являются константы и . Булеву функцию можно задать таблицей истинности. При n = 1 имеется ровно 4 функции
также называется константой нуль, называется константой единицей, тавтологией (эти функции могут быть как нульместными, так и от любого числа переменных). называется тождественной функцией, называется отрицанием x (NOT (x), логическое «НЕТ», «НЕ», инвертор). При n = 2 имеется 16 функций.
Внимание! Авторские права на книгу "Дискретная математика. Булевы функции. Сборник контрольных работ" (Викторова Н.Б.) охраняются законодательством! |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
