Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету 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.
скачать работу


 Другие рефераты
Осип Мандельштам. Жизнь и творчество
Франколау немесе жеткізілімнің базистік шарты
Парламент и монархия - особенности истории (Великобритания)
Внеземные цивилизации


 

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

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


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