Определение и способ задания булевых функций
Другие рефераты
Булевой функцией от n аргументов называется однозначное отображение n –
мерного булева куба на одномерный булев куб.
Способы задания функций
1. Табличный
|X1 X2 X3 … XN |F(X) |
|0 0 0 0 0 0 0 0 0 |?1 |
|… |?? |
|1 1 1 1 1 1 1 1 1 |?n |
?? - значение функции от данных аргументов.
Порядок возрастания векторов по мере возрастания их номеров называют
лексикографическим.
2. Векторный
F = (?1...?n)
3. Геометрический
Единичным вектором для данной функции называется тот вектор, значение
функции на котором равно 1.
Носителем данной функции – совокупность всех единичных векторов этой
функции (Nf – носитель функции f)
На векторах, помеченных звездочкой, функция обращается в 1.
Nf = {001, 011, 100, 110} = [1,3,4,6] [] – указаны номера векторов.
3. В виде формулы.
Функция f зависит от переменной xi фиктивно, если для любых двух наборов
значений переменных, отличающихся только значением переменной xi, значения
функции f совпадают.
Будем говорить, что f зависит от переменной xi существенно, если существуют
такие два набора значений, отличающихся только значением переменной xi, на
которых значения функций различно.
Фиктивные переменные у функции можно добавлять и исключать.
Две булевы функции называются равными или равносильными, если одну можно
получить из другой путем добавления и изъятия фиктивных переменных.
Строим таблицу функций при n = 1.
| | | |_ | |
|X |0 |X |X |1 |
|0 |0 |0 |1 |1 |
|1 |0 |1 |0 |1 |
Таблица всех элементарных булевых функций, применяемых в записи формул
|0 |0 |0 |0 |
|0 |0 |1 |1 |
|0 |1 |0 |0 |
|0 |1 |1 |1 |
|1 |0 |0 |1 |
|1 |0 |1 |0 |
|1 |1 |0 |1 |
|1 |1 |1 |1 |
Выделение всех возможных интервалов.
1. Для булева куба размерности 3 интервалом ранга 1 могут быть 4 вершины,
лежащие в одной грани.
2. Ранга 2 – любые 2 вершины, соединенные ребром.
3. Ранга 3 – любая отдельная вершина.
1. Нет _
2. I1 = { 001 011} <-> П1 = x1x3 - ядровый
I2 = { 011 111} <-> П2 = x2x3
Если координата вектора меняет значения, то переменная не входит
I3 = { 111 110} <-> П3 = x1x2
_
I4 = { 110 100} <-> П4 = x1x3
Dсокр. = П1 V П2 V П3 V П4
Nf = I1 U I4 U I2 (U – объединение)
Получили неприводимое покрытие, добавив к ядру недостающие интервалы так,
чтобы все единичные вершины были задействованы.
D1= П1 V П4 V П2
Nf = I1 U I4 U I3
D2= П1 V П4 V П3
Сосчитаем ранги тупиковых ДНФ
R1 = 6
R2 = 6
Dmin = D1 = D2
Метод карт Карно для нахождения минимальной ДНФ
n = 4
Карта Карно – плоскостная интерпретация 4-мерного булева куба.
| |00 |01 |11 |10 |
|00 | |0001| | |
|01 |0100|0101|0111 |0110|
|11 | |1101| | |
|10 | | | | |
Считаем, что левый край склеен с правым, а верхний – с нижним.
Если таблицу Карно свернуть таким образом, то получится тор (torus -
геометрическая фигура, напоминающая бублик).
Правила поиска интервалов.
1. Интервалом ранга 1 могут быть 2 соседних строки (2 соседних столбца)
2. Интервалом ранга 2 может быть вся строка, весь столбец или квадрат 2х2.
3. Интервалом ранга 3 – любые 2 соседние по горизонтали и вертикали клетки.
4. Одна отдельно взятая вершина будет интервалом ранга 4.
| |  скачать работу |
Другие рефераты
| 
