Булева алгебра

Булевой функцией называют функцию, аргументы которой и сама функция могут принимать только два значения.

Два возможных значения функции и каждого из её аргументов в различных областях применения булевых функций обозначают по-разному: истина, ложь — в математической логике; да, нет — на блок-схемах алгоритмов; true, false — в ряде языков программирования.

Проще всего обозначать эти значения единицей и нулём, что в дальнейшем и делается.

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

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

Будем обозначать простые высказывания буквами. Из них можно составить такие высказывания:

“ A и B ”, обозначается A&B;

“ A или B ”, обозначается A ⋁ B;

“не A ”, (то есть, не верно, что A), обозначается;

“если A, то B ”, обозначается.

Перечисленными связками, по существу исчерпываются средства образования сложных высказываний из простых.

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

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

Говорят, что на входы поступает комбинация налей и единиц, и устройство преобразует их в некоторую комбинацию налей и единиц на выходе.

Способы задания булевых функций.

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

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

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

Возможности задания булевых функций при помощи таблиц, например, при n= 10 нужно составить таблицу из 1024 строк. Поэтому, используются другие способы задания булевых функций, одним из которых является использование элементарных функций. Этот способ состоит в том, что некоторые функции выделяются, их называют элементарными, а другие функции строят из элементарных, подставляя их друг в друга.

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

Далее, перечислим все 16 функций от двух аргументов.

Некоторые из этих функций не представляют интереса, так как сводятся к функциям одного аргумента.

Из остальных функций семь выделены, они имеют специальные названия и обозначения. Эти функции вместе с отрицанием образуют совокупность элементарных булевых функций, из них строятся формулы.

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

Дизъюнкция, задается столбцом. Обозначается. Эта функция вычисляет истинность высказывания A или B: данное высказывание ложно тогда и только тогда, когда оба высказывания ложны.

Импликация, задаётся столбцом. Обозначается как. Эта функция вычисляет истинность высказывания – если A, то B.

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

Кроме перечисленных, ещё три функции встречаются в литературе по булевым функциям со специальными названиями и обозначениями:

Дата добавления: 2014-01-20