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

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

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

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

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

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

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

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

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

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