Контрольная работа: Булевы функции
Технические вопросы, связанные с составлением логических схем ЭВМ, можно решить с помощью математического аппарата, объектом исследования которого являются функции, принимающие, так же как и их аргументы, только два значения - “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-мерного единичного куба.
Булеву функцию, определенную на всех своих наборах, называют полностью определенной.
--> ЧИТАТЬ ПОЛНОСТЬЮ <--