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

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

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 I2Ik = 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) назовем ядерной, если она принадлежит ровно одному максимальному для этой функции интервалу. Максимальный интервал называется ядерным, если он содержит ядерную точку.

Читайте также:  Кинотеатры для андроид tv box

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

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

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

Для задания произвольной булевой функции широко используются табличный (матричный) и аналитическийспособы. При табличном способе булева функция f (х1, . хn) задается таблицей истинности (табл. 7), в левой части которой представлены все возможные двоичные наборы длины n, а в правой указывается значения функции на этих наборах.

№ набора х1х2х3 f
0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 0 1 0 0 1 1 0 1

Под двоичным набором понимается совокупность значений аргументов х12, . xn булевой функции f. Двоичный набор имеет длину n, если он представлен n цифрами из множества <0,1>. В табл. 7 представлены все двоичные наборы длины 3. Иногда двоичные наборы из таблицы истинности булевой функции удобно представлять их номерами. Запишем аргументы х12, . xn в порядке возрастания их индексов. Тогда любому двоичному набору можно поставить в соответствие целое десятичное число N, называемое номером набора. Например, двоичные наборы 011 и 101 имеют номера 3 и 5 соответственно. Булевы функции, зависящие от большого числа переменных, задавать таблицей истинности неудобно в силу ее громоздкости. Например, таблица истинности булевой функции 8 переменных будет содержать 2 8 = 256 строк. Для задания функций многих переменных удобно использовать модификацию таблицы истинности. Рассмотрим способ построения такой таблицы истинности для функции n переменных. Множество из n переменных функции разбивается на два подмножества: х1, х2, . хj-1 и хj, хj+1, . хn. Переменными x1, x2, . xn отмечают строки таблицы истинности, задавая в каждой строке значение соответствующего двоичного набора длины j-1. Переменными xj, xj+i, . xn отмечают ее столбцы, задавая в каждом столбце значения соответствующего двоичного набора длины n-j+1. Значение функции записывается в клетке на пересечении соответствующей строки и столбца (табл. 8).

x1,x2. xj-1 xj, xj+1, . xn
00. 0 0. 1 . 11. 1
00. 0
00. 1
.
11. 1

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

Основные понятия алгебры логики

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

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

Читайте также:  Какие квадрокоптеры самые лучшие

x 0 x x 1

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

Переменная xi называется фиктивной (несущественной) переменной функции f(x1,···,xn), если

Функции двух переменных представлены в табл. 9 .

х1х2 f f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15
00 01 10 11 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1

Отметим наиболее часто используемые функции из числа приведенных в таблице:

f (x1, x2) = 0 — тождественный ноль (константа 0);

f1 (x1, x2) = x1 ∙ x2 – конъюнкция (логическое произведение, И). Иногда употребляется знак & или /:

f6 (x1, x2) = x1 Åx2 — сложение по модулю 2 или сумма mod 2;

f7 (х1, х2) = x1 + x2 — дизъюнкция (логическое сложение, ИЛИ) или знак V;

f8 (x1, x2) = x1 x2 — функция Вебба (стрелка Пирса, ИЛИ-НЕ);

f15(x1, x2) = 1-тождественная единица (константа 1).

Основными операциями булевой алгебры являются: отрицание, логическое сложение и логическое умножение. В булевой алгебре возведение в степень и извлечение корня являются вырожденными логическими операциями, поскольку значения, принимаемые аргументами при возведении в степень и извлечении корня, остаются неизменными, если принять справедливость равенств 1·1= 1 и 0·0= 0. Операции вычитания и деления не рассматриваются и не допускаются.

Логическое отрицание (функция НЕ). Логическим отрицанием высказывания x называется такое сложное высказывание f1(x), которое истинно, когда x ложно, и наоборот. Функция НЕ записывается следующим образом f1=x. Реализующий функцию НЕ элемент приведен на рис. 13а.

Логическое умножение (конъюнкция). Конъюнкция (функция И) двух переменных x1 и x2 это сложное высказывание, которое истинно только тогда, когда истинны x1 и x2, и ложно для всех остальных наборов переменных. Логическая функция конъюнкции имеет вид f=x1·x2. Для обозначения операции конъюнкции используются также символы & и Λ. Функция логического умножения (И) от n переменных имеет вид f2=(x1, x2, …, xn)= x1·x2· … ·xn = Λ xi. Элемент, реализующий операцию логического умножения, изображен на рис. 13б.

Логическое сложение (дизъюнкция). Дизъюнкция (функция ИЛИ) двух переменных x1 и x2 – это сложное высказывание, которое истинно тогда, когда истинна хотя бы одна из переменных x1 и x2, и ложно, когда они обе ложны. Логическая функция дизъюнкции имеет вид f=x1+x2. Для обозначения операции дизъюнкции используется также символ V. Функция логического сложения (ИЛИ) от n переменных имеет вид f2=(x1, x2, …, xn)= x1+x2+ … +xn = V xi. Элемент, реализующий операцию логического сложения, изображен на рис. 13в.

Отрицание конъюнкции (операция Шеффера). Отрицание конъюнкции (функция И-НЕ) двух переменных x1 и x2 – сложное высказывание, ложное только при истинности обоих аргументов x1 и x2. Логическая функция И-НЕ имеет вид f=x1·x2. Элемент, реализующий указанную операцию, изображен на рис. 13г и называется элементом Шеффера или элементом И-НЕ.

Отрицание дизъюнкции (операция Пирса (Вебба)). Отрицание дизъюнкции (функция ИЛИ-НЕ) двух переменных x1 и x2 – сложное высказывание, истинное только тогда, когда оба аргумента принимают ложное значение. Логическая функция ИЛИ-НЕ имеет вид f=x1+x2. Элемент, реализующий указанную операцию, изображен на рис. 13д и называется элементом Пирса или элементом ИЛИ-НЕ.

Читайте также:  Сабвуфер bbk fsw 108

Сложение по модулю 2 (исключающее ИЛИ). Сложение по модулю два это сложное высказывание, которое истинно только тогда, когда истинна только одна из переменных x1 и x2. Логическая функция ”сумма по модулю два” имеет вид f=x1Åx2. Если число переменных n>2, то функция истинна на тех наборах, в которых число единиц нечетно. Элемент, реализующий операцию сумма по модулю два, изображен на рис. 13ж.

Импликация. Это высказывание, принимающее ложное значение только в случае если x1 истинно и x2 ложно.

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

Функция f(x,y) = (x & y) является суперпозицией функций и &. Функция g(x,y) = x Å (x Ú y) является суперпозицией функций Å и Ú. Функция h(x,y,z) = (x & y) Å z является суперпозицией функций Å и &.

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

§ одна и та же функция может быть представлена разными формулами;

§ каждой формуле соответствует своя суперпозиция и, следовательно, своя схема соединений элементов;

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

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

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

Функция f, зависящая от n переменных x1, x2, …, xn называется булевой, или переключательной, если функция f и любой из ее аргументов xi, i=(1, … , n) принимают значения только из множества <1, 0>. Аргументы булевой функции также называется булевыми.

Произвольная булева функция может быть задана табличным способом. При таком способе булева функция f(x1, …, xn) задается таблицей истинности (табл. 5.1), в левой части которой представлены все возможные двоичные наборы длины n, а в правой указывается значение функции на этих наборах. Под двоичным набором y=(y1, y2, … , yn), yi <1, 0>понимается совокупность значений аргументов x1, x2, …, xn булевой функции f. Двоичный набор имеет длину n, если он представлен n цифрами из множества <0, 1>.

Иногда двоичные наборы в таблице истинности булевой функции удобно представлять номерами наборов. Запишем аргументы x1, x2, …, xn в порядке возрастания их индексов. Тогда любой двоичный набор y=(y1, y2, … , yn), yi <1, 0>можно рассматривать как двоичное число N:

N= y12 n -1 +y22 n -2 +…+yn, называемое номером набора у.

Таблица 5.1 Таблица 5.2

Таблица истинности Таблица истинности

Ссылка на основную публикацию
Совместимость ssd с ноутбуками
Вопрос совместимости Многие пользователи интересуются совместимостью материнской платы и SSD, который они купили или хотят купить. Опыт показывает, что не...
Скрыть не интересуюсь уже купил спам мешает
"Яндекс" запустил опцию "Скрыть объявление" на сайтах входящих в Рекламную сеть Яндекса. Опция позволяет отключить показ рекламных объявлений, которые в...
Слабо работает интернет что делать
Как настроить роутер, как настроить модем, как настроить оптический терминал. Настройка роутера по http://192.168.1.1 или http://192.168.0.1 Что делать если медленно...
Совместимость ремешков apple watch
Здесь приводятся общие инструкции, которые помогут Вам снять, поменять и застегнуть ремешок. В случае смены ремешка убедитесь, что размеры используемого...
Adblock detector