Мои Конспекты
Главная | Обратная связь

...

Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Лемма о несамодвойственной функции





Помощь в ✍️ написании работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Если f (nS , то из нее путем подстановки х и`х вместо переменных х1, х2, ... , хn можно получить константу.

Доказательство. Из f (n) ÏS следует, что существует набор`a = (a1, a2, ..., an ), для которого: f (a1, a2, ... , an ) = f(`a1,`a2, ... , `an ) = С. Подстановки выбираем по правилу: j i (x)= x ai , где j i (x)= x при a i =1, j i (x) =`x при a i = 0. В итоге получаем функцию одной переменной F(x), которая принимает следующие значения: F(0) = f(j1(0), ... ,j n (0)) = C, F(1) = f(j1(1),...,j n (1)) = C, т.е. является константой.

ЗАДАЧИ

1. Будут ли двойственными функции: а) | и ¯ ;б) | и Å;в) (10100010)и (11100000) ;г) (10100010)и (10111010).

2. Найти с использованием принципа двойственности функции, двойственные к: а) ху Ú уz ;б) ху | (х Ú z) у ; в) х¯ у.

3. Доказать, что если f (nS, то в ее векторе значений будет равное число значений 1и 0.

4. Будут ли самодвойственными функции: а) х )` х ;в) х у Ú xz Ú yz;г) (01001011);д) (1100101100101100) .

5. Доказать, что если f (`х nS, то f (х,х,...,х)Î(х,`х).

6. Доказать, что все двухместные самодвойственные функции f(х, у)имеют ровно одну фиктивную переменную и сводятся к функциям х, у,Øх, Øу.

7. Доказать замкнутость класса S.

8. Доказать предполноту класса S(например, используя лемму о несамодвойственной функции и 3 — местную самодвойственную функцию f =(00010111) ).

9. Найти мощность класса S n.

Монотонность. Класс М

Определение. Булев вектор`an предшествует вектору`bn, если для всех их компонент i (1 £ i£ n ) выполняется условие: a i £b i . Обозначают предшествование как:`a n £`b n. Функцию f(n) называют монотонной, если на всех предшествующих наборах ее переменных`a n и`b n (`an £`bn ) предшествование сохраняется и для значений функции, т.е. выполняется условие: f (a nf (b n ).

Свойство предшествования вводит на множестве n — мерных булевых векторов E2n бинарное отношение нестрогого порядка, поскольку оно удовлетворяет аксиомам рефлексивности, антисимметричности и транзитивности. При n >1 данное отношение вводит на E2n частичный порядок, так как есть не сравнимые между собой наборы – например (01) и (10), (011) и (110) и др.

Множество монотонных функций n переменных обозначается Мn, все множество монотонных функций алгебры логики — М. Оно является предполным классом в Р2. Если функция f ÏМ, то ее называют немонотонной. Выяснить монотонность любой функции можно непосредственной проверкой всех предшествующих наборов по таблице истинности.

Замечание. Если функция на некотором наборе`an равна 0, то ее значения на всех последующих наборах`bn, сравнимых с`an (`a n £ b n), можно не проверять, поскольку значение f (`a n )= 0предшествует любому значению f (`b n ). Аналогично, если функция на некотором наборе`b n равна 1, то ей предшествуют любые значения на всех предшествующих наборах`a n, сравнимых с`b n (`a n £`b n).

Пример. Проверить монотонность функций: а) Øх , б) х Ú у , в) (00101011).

Решение.Задачу решаемсучетом Замечания путем проверки сохранения функциями свойства предшествования на всех парах сравнимых наборов переменных в таблице истинности.

 

х Ø
х У z f
х у Ú

 

 

а) Функция Øх принимает значение 1 на наборе х=(0). Он является предшествующим набору х=(1): (0) £ (1). Сравнивая значения функции: f(0)=1 > f(1)=0, получим нарушение предшествования. Следовательно, отрицание не монотонно.

б) Первое единичное значение функции — на наборе (х,у) =(0,1). С ним сравним набор (1,1). Для данной пары наборов: f(0,1)=1 = f(1,1)=1 — отношение предшествования сохраняется. Аналогично для следующего набора (х,у)=(1,0) с единичным значением функции сравнимым является набор (1,1). В этом случае: f(1,0)=1 = f(1,1)=1 — отношение также сохраняется. Поскольку все сравнимые наборы проверены, то функция логического сложения является монотонной.

в) Рассмотрим первое единичное значение функции — на наборе (х,у,z)=(0,1,0). С ним сравнимы наборы (0,1,1), (1,1,0) и (1,1,1). Проверка набора (0,1,1) дает: f(0,1,0)=1 > f(0,1,1)=0 — нарушение отношения предшествования. Следовательно, данная функция не монотонна.

Ответ: функции а) Øх и в) (00101011) не монотонны, функция б) хÚу — монотонна.

Монотонными являются элементарные функции 0, 1, х, Ú, &. Для немонотонных функций (не входящих вМ) справедлива

Доверь свою работу ✍️ кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.