Булевы функции (стр. 1 из 7)
1.Основные понятия булевой алгебры
Технические вопросы, связанные с составлением логических схем ЭВМ, можно решить с помощью математического аппарата, объектом исследования которого являются функции, принимающие, так же как и их аргументы, только два значения - “0” и “1”.
Таким аппаратом является математическая логика (алгебра логики, булева алгебра).
Логика - это наука о законах и формах мышления.
Математическая логика занимается изучением возможностей применения формальных методов для решения логических задач. Один из разделов математической логики является алгебра логики.
Основное понятие алгебры логики - высказывание. Высказывание - это некоторое предложение, о котором можно утверждать, что оно истинно или ложно.
Любое высказывание можно обозначить символом х и считать, что х=1, если высказывание истинно, а х=0 - если высказывание ложно. Истинному высказыванию соответствует утверждение -“Да”, ложному высказыванию - утверждение - “Нет”.
Логическая (булева) переменная - такая величина х, которая может принимать только два значения х={0,1}.
Высказывание абсолютно истинно, если соответствующая ей логическая величина принимает значение х=1 при любых условиях.
Высказывание абсолютно ложно, если соответствующая ей логическая величина принимает значение х=0 при любых условиях.
Функция f, зависящая от nпеременных x1,x2,...,xn, называется булевой, или переключательной, если функция fи любой из ее аргументов
принимают значения только из множества {0,1}. Аргументы булевой функции также называются булевыми.2.Способы задания булевых функций
Произвольная булева функция задается одним из трех способов: матричным (табличным), геометрическим и аналитическим.
При матричном способе булева функция f(x1,...,xn) задается таблицей истинности (табл. 1 и 2), в левой части которой представлены все возможные двоичные наборы длины n, а в правой указывается значение функции на этих наборах.
Под двоичным набором понимается совокупность значений аргументов x1,x2,...,xnбулевой функции f. Двоичный набор имеет длину n, если он представлен nцифрами из множества {0,1}. В табл. 1 и 2 перечислены все двоичные наборы соответственно длины 3 и 4.
Таблица 1 Таблица 3
| х1 | х2 | х3 | f(х1,х2,,х3) | Номернабора | f(х1,х2,,х3) |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 2 | 0 |
| 0 | 1 | 1 | 0 | 3 | 0 |
| 1 | 0 | 0 | 1 | 4 | 1 |
| 1 | 0 | 1 | 1 | 5 | 1 |
| 1 | 1 | 0 | 0 | 6 | 0 |
| 1 | 1 | 1 | 1 | 7 | 1 |
Таблица 2 Таблица 4.
| x1 | x2 | x3 | x4 | f(х1..х4) | x1,x2,...,xj-1 | xj,xj+1,...,xn | |||
| 00..0 | 0...1 | ... | 11..1 | ||||||
| 0 | 0 | 0 | 0 | 1 | |||||
| 0 | 0 | 0 | 1 | 0 | 00...0 | ... | |||
| 0 | 0 | 1 | 0 | 0 | |||||
| 0 | 0 | 1 | 1 | 1 | |||||
| 0 | 1 | 0 | 0 | 1 | |||||
| 0 | 1 | 0 | 1 | 0 | 00...1 | ... | |||
| 0 | 1 | 1 | 0 | 1 | f(х1...хn) | ||||
| 0 | 1 | 1 | 1 | 1 | |||||
| 1 | 0 | 0 | 0 | 1 | |||||
| 1 | 0 | 0 | 1 | 0 | ... | ... | ... | ... | ... |
| 1 | 0 | 1 | 0 | 0 | |||||
| 1 | 0 | 1 | 1 | 0 | |||||
| 1 | 1 | 0 | 0 | 0 | |||||
| 1 | 1 | 0 | 1 | 0 | 11...1 | ||||
| 1 | 1 | 1 | 0 | 1 | |||||
| 1 | 1 | 1 | 1 | 0 | |||||
Иногда двоичные наборы в таблице истинности булевой функции удобно представлять номерами наборов. Запишем аргументы x1,x2,...,xnв порядке возрастания их индексов. Тогда любой двоичный набор можно рассматривать какцелое двоичное число N, называемое номером набора. Например, двоичные наборы 0101 и 1000 имеют номера 5 и 8 соответственно. Очевидно, любая булева функция может быть задана таблицей истинности, в которой двоичные наборы заменены своими номерами (табл.3).
Булевы функции, зависящие от большого числа переменных, задавать таблицей истинности неудобно в силу ее громоздкости. Например, таблица истинности булевой функции 8 переменных будет содержать 28 = 256 строк. Поэтому для задания функций многих переменных удобно использовать модификацию таблицы истинности.
Рассмотрим способ построения такой таблицы истинности для функции nпеременных. Множество из nпеременных функции разбивается на два подмножества: x1,x2,...,xj-1 и хj, xj,xj+1,...,xn. Переменными x1,x2,...,xj-1 отмечают строки таблицы истинности, задавая в каждой строке значение соответствующего двоичного набора длины j-1. Переменными xj,xj+1,...,xnотмечают ее столбцы, задавая в каждом столбце значения соответствующего двоичного набора длины n-j+1. Значение функции записывается в клетке на пересечении соответствующей строки и столбца (табл.4.).
При геометрическом способе булева функция f(х1,..., xn) задается с помощью n-мерного куба. В геометрическом смысле каждый двоичный набор есть n-мерный вектор, определяющий точку n-мерного пространства. Исходя из этого, все множество наборов, на которых определена функция nпеременных, представляется вершинами n-мерного куба. Отмечая точками вершины куба, в которых функция принимает единичные (либо нулевые) значения, получим геометрическое представление функции. Например, булева функция, заданная табл.1, геометрически представляется 3-мерным кубом (рис. 1.в).
 |
а) n=1 б) n=2 в) n=3
Рисунок 1- Геометрическое задание булевой функции:
а) одной переменной: б) двух переменных; в) трех переменных.
При аналитическом способе булева функция задается формулами, т. е. аналитическими выражениями, построенными на основе операций булевой алгебры. Аналитический способ задания булевых функций занимает особое место в проектировании цифровых автоматов. Фактически, все преобразования над булевыми функциями, необходимые для построения цифровых автоматов, ведутся на аналитическом уровне.
Рассмотрим области определения булевых функций. Между двоичными наборами и двоичными числами существует взаимно однозначное соответствие. Следовательно, существует 2nразличных наборов двоичных переменных.
Таким образом, областью определения булевой функции nпеременных при матричном способе задания является множество всех возможных двоичных наборов длины n, а при геометрическом способе задания — множество всех вершин n-мерного единичного куба.
Булеву функцию, определенную на всех своих наборах, называют полностью определенной.
Булеву функцию nпеременных называют неполностью определенной или частичной, если она определена не на всех двоичных наборах длины n.
3.Булевы функции одной и двух переменных
Рассмотрим наиболее употребимые булевы функции одной и двух переменных. Функции одной переменной представлены в табл. 5.
Таблица 5
| f(х) | х | Усл. | Наименование | |
| 0 | 1 | обозн | ||
| f0 (х) | 0 | 0 | 0 | тождественный ноль (константа 0); |
| f1 (х) | 0 | 1 | х | тождественная функция |
| f2 (х) | 1 | 0 |  | отрицание х (инверсия); |
| f3 (х) | 1 | 1 | 1 | тождественная единица (константа 1). |
Функции двух переменных представлены в табл. 6.
Рассмотренные простейшие булевы функции позволяют строить новые булевы функции с помощью обобщенной операции, называемой операцией суперпозиции. Фактически операция суперпозиции заключается в подстановке вместо аргументов других булевых функций (в частности аргументов).
Отметим, что реально элементарной функции соответствует реализующий ее элемент, а суперпозиции булевых функций соответствует соединение элементов.
Таблица 6
| х1 | 0 | 0 | 1 | 1 | Наименование функции | |
| х2 | 0 | 1 | 0 | 1 | ||
| f0 (х1,х2) | 0 | 0 | 0 | 0 | константа 0 | |
| f1 (х1,х2) | 0 | 0 | 0 | 1 | конъюнкция | |
| f2 (х1,х2) | 0 | 0 | 1 | 0 | запрет по х2 | |
| f3 (х1,х2) | 0 | 0 | 1 | 1 | переменная х1 | |
| f4 (х1,х2) | 0 | 1 | 0 | 0 | запрет по х1 | |
| f5 (х1,х2) | 0 | 1 | 0 | 1 | переменная х2 | |
| f6 (х1,х2) | 0 | 1 | 1 | 0 | сумма по модулю 2 | |
| f7 (х1,х2) | 0 | 1 | 1 | 1 | дизъюнкция | |
| f8 (х1,х2) | 1 | 0 | 0 | 0 | операция Пирса (ф-ция Вебба) | |
| f9 (х1,х2) | 1 | 0 | 0 | 1 | логическая равнозначность | |
| f10 (х1,х2) | 1 | 0 | 1 | 0 | инверсия х2 | |
| f11 (х1,х2) | 1 | 0 | 1 | 1 | импликация от х2 к х1 | |
| f12 (х1,х2) | 1 | 1 | 0 | 0 | инверсия х1 | |
| f13 (х1,х2) | 1 | 1 | 0 | 1 | импликация от х1 к х2 | |
| f14 (х1,х2) | 1 | 1 | 1 | 0 | штрих Шеффера | |
| f15 (х1,х2) | 1 | 1 | 1 | 1 | константа 1 | |
Суперпозиция булевых функций представляется в виде логических формул. Однако следует отметить:
- одна и та же функция может быть представлена разными формулами;
- каждой формуле соответствует своя суперпозиция и, следовательно, своя схема соединений элементов;
- между формулами представления булевых функций и схемами, их реализующими, существует взаимнооднозначное соответствие.
Очевидно, среди схем, реализующих данную функцию, есть наиболее простая. Поиск логической формулы, соответствующей этой схеме, представляет большой практический интерес, а преобразование формул булевых функций основано на использовании соотношений булевой алгебры.