Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

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



 Другие рефераты
Множество. Алгебра множеств. Теория булевых функций. Булева алгебра. Метод Квайна – Мак-Клоски для нахождения минимальной ДНФ Функционально полные системы функций

Булевой функцией от 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.
скачать работу


 Другие рефераты
Свадебный обряд Пинежья
Психология цвета
17 ғасырдың музыкалық мәдениеті
Итальянское Возрождение


 

Отправка СМС бесплатно

На правах рекламы


ZERO.kz
 
Модератор сайта RESURS.KZ