86371 (Булевы функции)
Описание файла
Документ из архива "Булевы функции", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "контрольные работы и аттестации", в предмете "математика" в общих файлах.
Онлайн просмотр документа "86371"
Текст из документа "86371"
-
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.
Рассмотренные простейшие булевы функции позволяют строить новые булевы функции с помощью обобщенной операции, называемой операцией суперпозиции. Фактически операция суперпозиции заключается в подстановке вместо аргументов других булевых функций (в частности аргументов).