Булевы функции

Теория
  • Понятие булевой функции. Булев куб

    В дискретной математике большую роль играют конечные функции. Конечной функцией называют отображенuе одного конечного множества в другое. Важный клacc таких функций образуют булевы функции.Подробнее
  • Таблицы булевых функций

    Булева функция от n переменных может быть задана таблицей, состоящей из двух столбцов и 2n строк. В первомстолбце перечисляются все наборы из Bn в лексикографическом порядке, а во втором - значения функции на наборах. Форма таблицы произвольной булевой функции приведена ниже (табл. 6.1).Подробнее
  • Фиктивные переменные. Равенство булевых функций

    Ключевым понятием в теории булевых функцuй является понятие равных булевых функций. Для функций от одного и того же числа переменных n нет необходимости рассматривать какое- то специальное определение равенства, ибо такие функции равны, если они совпадают как отображения булева куба Bn в В. Проблема состоит в том, чтобы определить равенство булевых функций независимо от числа переменных.Подробнее
  • Формулы и суперпозиции

    Табличный способ задания булевой функции не является эффективным. Им практически нельзя воспользоваться при большом числе переменных. Помимо этого способа существует способ представления булевых функций в виде формул. Этот способ аналогичен аналитическому способу задания функций действительного переменного [I].Подробнее
  • Дизъюнктивные и конъюнктивные нормальные формы

    Любая формула вида х или х над стандартным базисом, где х - произвольное переменное, называется литералом. Таким образом, литерал есть обозначение либо самого переменного х, либо его отрицания. Часто используют такое обозначение: для σ ∈ {0, 1} пишут хσ, понимая под этим само переменное х, если σ = 1, и отрицание х, если σ = 0, т.е.Подробнее
  • Построение минимальных ДНФ

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

    В силу теоремы о представлении любой булевой функции дизъюнктивной или конъюнктивной нормальной формой стандартный базис {∨, ·,   } является полным множеством. Поскольку, согласно законам де Моргана, можно выразить конъюнкцию через дизъюнкцию и отрицание, равно как и дизъюнкцию можно выразить через конъюнкцию и отрицание, то при удалении из стандартного базиса одной функции, дизъюнкции или конъюнкции, при сохранении отрицания, получим снова полное множество.Подробнее
  • Схемы из функциональных элементов

    Представлению булевых функций формулами можно придать следующий "инженерно-конструктивный" смысл. Будем рассматривать формулу Ф(x1,..., xn) над каким-то произвольно фиксированным множеством F как "черный ящик", некое устройство, на вход которого подаются всевозможные наборы значений переменных, а на выходе появляются соответствующие этим наборам значения функции f, представляемой формулой Ф (рис. 6.22).Подробнее
  • Вопросы и задачи

    6.1. Найти число дуг в булевой n-сети.Подробнее