русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Двойственные функции


Дата добавления: 2013-12-23; просмотров: 9295; Нарушение авторских прав


Определение.Двойственной для функции f(x1, x2, …, xn) называется функция

Пример 44.

Построить функцию, двойственную данной:

1. f = x Ú y;

2. f = x® y.

Решение.

1.

2.

Определение. Функция, совпадающая со своей двойственной, называется самодвойственной.

Утверждение. Если функция f(x1, x2, …, xn) самодвойственна, то функция тоже самодвойственна.

Утверждение. Чтобы функция была самодвойственной необходимо и достаточно, чтобы на всяких двух противоположных наборах она принимала разные значения.

Противоположными называются те наборы, которые в сумме дают двоичный код числа (2n-1).

Пример 45.

Выяснить являются ли функции самодвойственными:

1. ;

2. f = 01110010.

Решение.

1. Строим таблицу истинности для данной функции (табл. 55):

Таблица 55

x y z
0
1
2
3
4
5
6
7

Так как наборы (0, 0, 0) и (1, 1, 1) являются противоположными, а f(0, 0, 0) = f(1, 1, 1), то данная функция не является самодвойственной.

2. Строим таблицу значений для функции f = 01110001 (табл. 56).

Таблица 56

x y z f(x, y, z)
0
1
2
3
4
5
6
7

Перечислим пары противоположных наборов: (0, 7), (1, 6), (2, 5), (3, 4). Легко убедиться по таблице, что на всяких двух противоположных наборах функция принимает разные значения. Следовательно, функция является самодвойственной.



 

Теорема. Класс S = {f | f = f*}самодвойственных функций замкнут относительно суперпозиций.

 

2.2.3.2. Линейные функции

Определение. Арифметические функции в алгебре логики это сложение по модулю два и умножение (конъюнкция).

Определение. Многочленом Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени: , причем на каждом наборе <i1, …, ik> все аij (j = 1, …, k) различны, aj Î {0, 1}.

Теорема. Всякую булеву функцию можно представить единственным полиномом Жегалкина.

Многочлен Жегалкина можно получить различными способами. Остановимся на рассмотрении построения многочлена Жегалкина с помощью треугольника Паскаля. Рассмотрим алгоритм на примере.

Пример 46.

Построить многочлен Жегалкина для функции f=10011110.

Решение.

Алгоритм построения многочлена Жегалкина:

Шаг 1. Строим таблицу (табл. 57). Первый столбец содержит возможные слагаемые полинома Жегалкина. Нулевому набору всегда соответствует слагаемое 1. Остальным наборам соответствует слагаемое, представляющее собой конъюнкцию переменных, которые на данном наборе принимают значение 1. Следующие n столбцов – всевозможные наборы из 0 и 1, соответствующие переменным. Далее столбец значений функции f. Функция g является вспомогательной, поэтому изначально этот столбец не заполнен.

Таблица 57

Слагаемые полинома Жегалкина x1 x2 x3 f g Треугольник Паскаля
1 0 0 0 1
x3 0 0 1 0
x2 0 1 0 0
x2x3 0 1 1 1
x1 1 0 0 1
x1 x3 1 0 1 1
x1 x2 1 1 0 1
x1 x2 x3 1 1 1 0

 

Шаг 2. Построение треугольника Паскаля. Верхняя сторона треугольника есть функция f. Любой другой элемент треугольника есть сумма по модулю два двух соседних элементов предыдущей строки. Левая сторона треугольника представляет собой значение вспомогательной функции g (табл. 58).

Таблица 58

Слагаемые полинома Жегалкина x1 x2 x3 f g Треугольник Паскаля
1 0 0 0 1 1 f = 1 0 0 1 1 1 1 0
x3 0 0 1 0 1 1 0 1 0 0 0 1
x2 0 1 0 0 1 1 1 1 0 0 1
x2x3 0 1 1 1 0 0 0 1 0 1
x1 1 0 0 1 0 0 1 1 1
x1 x3 1 0 1 1 1 1 0 0
x1 x2 1 1 0 1 1 1 0
x1 x2 x3 1 1 1 0 1 1

Шаг 3. Построение полинома Жегалкина. В полином войдут только те слагаемые, которым соответствует единица во вспомогательной функции g.

Для данной функции многочлен Жегалкина имеет вид:

f = 1 + x3 + x2 + x1 x3 + x1 x2 + x1 x2 x3.

 

Определение. Функция f(x1, x2, …, xn) называется линейной, если многочлен Жегалкина для нее имеет следующий линейный относительно переменных вид:

f(x1, x2, …, xn) = a1x1 + … + anxn + an+1, где каждое ai равно 0 или 1.

Булева функция из рассмотренного выше примера не является линейной.

Теорема. Класс L = {f | f = a0+a1x1+…+anxn, aiÎ{0, 1}} линейных функций замкнут относительно суперпозиций.



<== предыдущая лекция | следующая лекция ==>
Приведение к СКНФ. Алгоритм приведения. | Монотонные функции


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.004 сек.