Меню

Булевы функции таблицы значений

Элементарные булевы функции

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

1. Булева функция f(x1, x2 . xn) принимающая значение 1 на всех наборах нулей и единиц называется константой 1, или тождественной единицей. Обозначение: 1.

2. Булева функция f(x1, x2 . xn) принимающая значение 0 на всех наборах нулей и единиц называется константой 0, или тождественным нулем. Обозначение: .

3. Отрицанием называется булева функция одной переменной, которая определяется следующей таблицей истинности:

Обозначения: ¬x. Запись ¬x читается «не икс» или «отрицание икс».

4. Конъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности:

Другие названия: логическое умножение (произведение); логическое «и».

Обозначения: x&y, x⋅y, min(x,y).

Запись x&y может читаться так: «икс и игрек» или «икс умножить на игрек».

5. Дизъюнкцией называется булева функция двух переменных, которая определяется следующей таблицей истинности:

Другие названия: логическое сложение (сумма); логическое «или».

Обозначения: x∨y, max(x,y).

Запись x∨y может читаться так: «икс или игрек» или «сумма икс и игрек».

6. Импликацией называется булева функция двух переменных, которая определяется следующей таблицей истинности:

Другое название: логическое следование.

Обозначения: x→y, x⇒y, x⊃y.

Запись x→y может читаться так: «из икс следует игрек».

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

Обозначения: x∼y, x↔y.

Запись x∼y может читаться так: «икс эквивалентно игрек» или «икс равносильно игрек».

8. Cуммой по модулю 2 называется булева функция двух переменных, которая определяется следующей таблицей истинности:

Другое название: антиэквивалентность.

Обозначения: x⊕y, x+y.

Запись x⊕y может читаться так: «икс плюс игрек».

9. Штрих Шеффера это булева функция двух переменных, которая определяется следующей таблицей истинности:

Другое название: отрицание конъюнкции, логическое «не-и».

Запись x|y может читаться так: «не икс или не игрек», «икс и игрек несовместны», «икс штрих Шеффера игрек».

10. Стрелка Пирса это булева функция двух переменных, которая определяется следующей таблицей истинности:

Другое название: отрицание дизъюнкции, логическое «не-или», функция Вебба.

Обозначение: x↓y; для функции Вебба — x°y.

Запись x↓y может читаться так: «ни икс и ни игрек», «икс стрелка Пирса игрек».

Замечание: Символы ¬, &, ∨, →, ∼, ⊕, |, ↓ участвующие в обозначениях элементарных функций будем называть связками или операциями.

x 1 1 1
y 1 1 1 1
z 1 1 1 1
f(x,y,z) 1 1 1

Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение 1.Полученную в примере функцию f можно также задать следующей системой равенств: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) = 0.

Вектором значений булевой функции y=f(x1, x2 . xn) называется упорядоченный набор всех значений функции f, при котором значения упорядочены по лексикографическому порядку. Например, пусть функция трех переменных f задана вектором значений (0000 0010) и необходимо найти набор, на котором f принимает значение 1. Т.к. 1 стоит на 7 месте, а нумерация в лексикографическом порядке начинается с 0, то необходимо найти двоичное разложение 6. Таким образом, функция f принимает значение 1 на наборе (110).

Источник

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

Представление булевой функции формулой логики высказываний

  • Определение. Булевой функцией называется n-местная функция, аргументы которой принимают значения во множестве <0, 1>и сама функция принимает значения в этом же множестве.

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

Для n=3 булеву функцию можно задать таблицей .

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

Пусть задана булева функция от трех переменных (табл.). Тогда число наборов 2 3 =8.

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

Существует ровно $2^<2^>$ различных булевых функций от n переменных. Константы 0 и 1 считают нуль-местными булевыми функциями.

Утверждение. Каждой формуле логики высказываний соответствует некоторая булева функция.

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

Решение. Поскольку n=2, различных булевых функций от двух переменных существует ровно 16 (табл.).

Источник



Булевы функции таблицы значений

1) Задание булевой функции таблицей истинности. Так называется таблица, состоящая из двух частей: в левой части перечисляются все наборы значений аргументов (булевы векторы пространства B n ) в естественном порядке, то есть по возрастанию значений чисел, представляемых этими векторами, а в правой части – значения булевой функции на соответствующих наборах.

Пример. Рассмотрим булеву функцию трех аргументов, называемую мажоритарной (или функцией голосования): она принимает значение 1 на тех и только тех наборах, в которых единиц больше, чем нулей (major – больший).

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

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

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

2) Задание булевой функции характеристическими множествами. Так называются два множества:

M 1 f, состоящее из всех наборов, на которых функция принимает значение 1, то есть M 1 f = <α B n :f(α) = 1>;

M 0 f, состоящее из всех наборов, на которых функция принимает значение 0, то есть M 0 f = <α B n :f(α) = 0>.

Пример (мажоритарная функция).

3) Задание булевой функции вектором ее значений.

Пример (мажоритарная функция).

4) Задание булевой функции матрицей Грея. Булево пространство задается матрицей Грея, и наборы (клетки матрицы), на которых булева функция f(x1, …, xn) принимает значение 1, отмечаются и называются точками.

Пример (мажоритарная функция).

5) Интервальный способ задания булевой функции. Булеву функцию f(x1, …, xn) можно задать множеством интервалов If = 1, I2, …, Ik>, объединение которых образует характеристическое множество M 1 f, то есть I1 I2 … Ik = M 1 f. Множество интервалов If называется достаточным для функции f(x1, …, xn).

Пример. Мажоритарная функция может быть задана достаточным множеством If = 1, I2, I3> интервалов:

Здесь интервалы представлены троичными векторами и изображены на матрице Грея.

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

Пример. Зададим мажоритарную функцию другим достаточным множеством I’f = 1, I2, I3, I4> интервалов:

Очевидно, что это множество интервалов избыточно: первый интервал (011) можно удалить.

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

Примеры. I1= – 1 1 – допустимый интервал для мажоритарной функции, I2= 1 0 – – не допустимый.

Определение. Интервал I назовем максимальным для булевой функции f(x1, …, xn), если он является допустимым для этой функции, и не существует другого допустимого интервала I’, такого что I I’.

Пример. I1= –11 является максимальным интервалом для мажоритарной функции, а допустимый интервал I2 = 111 не является максимальным, так как I2 I1.

Пример. Зададим мажоритарную функцию множеством I»f = 1 I2, I3> всех максимальных интервалов.

Определение. Точку булевой функции f(x1, …, xn) назовем ядерной, если она принадлежит ровно одному максимальному для этой функции интервалу. Максимальный интервал называется ядерным, если он содержит ядерную точку.

Пример. Для мажоритарной функции ядерными точками являются 011 (принадлежит только интервалу –11), 101 (принадлежит только интервалу 1 –1) и 110 (принадлежит только интервалу 11 –). Все максимальные интервалы этой функции являются ядерными. •

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

6) Задание булевой функции формулами будет рассмотрено несколько позже.

Источник

Булевы функции и их представления

Булевы функции от 1-ой и 2-х переменных

Представим вначале в табличном виде все булевы функции от 1-ой переменной. Как мы знаем, их всего четыре.

Таблица 3.2. Булевы функции от 1-ой переменной

x1 f1 f2 f3 f4
1 1
1 1 1

В этой таблице представлены следующие функции:

  1. f1(x1)= 0 — константа 0;
  2. f2(x1)= 1 — константа 1;
  3. f3(x1)= x1 — тождественная функция;
  4. f_<4 data-lazy-src=

Многие из этих функций часто используются в качестве «элементарных» и имеют собственные обозначения.

  1. f1(x1,x2)= 0 — константа 0;
  2. f2(x1,x2)= 1 — константа 1;
  3. f3(x1,x2)= x1 — функция, равная 1-му аргументу ;
  4. f_<4 data-lazy-src=
Читайте также:  Родион Раскольников цитаты из романа