Лекция 3: «Определение и способ задания булевых функций»
Булевой функцией от n аргументов называется однозначное отображение n – мерного булева куба на одномерный булев куб.
Способы задания функций 1. Табличный
gi - значение функции от данных аргументов. Порядок возрастания векторов по мере возрастания их номеров называют лексикографическим. 2. Векторный F = (g1...gn) 3. Геометрический Единичным вектором для данной функции называется тот вектор, значение функции на котором равно 1. Носителем данной функции – совокупность всех единичных векторов этой функции (Nf – носитель функции f)
На векторах, помеченных звездочкой, функция обращается в 1.
Nf = {001, 011, 100, 110} = [1,3,4,6] [] – указаны номера векторов.
3. В виде формулы. Функция f зависит от переменной xi фиктивно, если для любых двух наборов значений переменных, отличающихся только значением переменной xi, значения функции f совпадают. Будем говорить, что f зависит от переменной xi существенно, если существуют такие два набора значений, отличающихся только значением переменной xi, на которых значения функций различно. Фиктивные переменные у функции можно добавлять и исключать. Две булевы функции называются равными или равносильными, если одну можно получить из другой путем добавления и изъятия фиктивных переменных.
Строим таблицу функций при n = 1.
Таблица всех элементарных булевых функций, применяемых в записи формул
Все эти функции от двух аргументов мы и будем называть элементарными булевыми функциями. Основными элементарными функциями являются конъюнкция, дизъюнкция и отрицание. Элементарные булевы функции удовлетворяют всем аксиомам булевой алгебры. Суперпозиции булевых функций Ф = {ф1…фk}
F называется элементарной суперпозицией функции из множества Ф, если она получена одним из следующих способов. 1. Переименование какого-нибудь аргумента в одной из функций системы (возможно отождествление аргумента). 2. В одну из функций системы вместо любого аргумента ставится значение любой функции из этой системы.
Ф1 = {Y…xn} Фi = (x1 … фj(x1…xn) … xn)
Ф(1) – множество всех элементарных суперпозиций из системы Ф. Ф(k+1) – множество всех элементарных суперпозиций из систему Фk.
Функция g называется суперпозицией функций из системы, если $ N : g Î Фn Это означает, что g можно получить из функции системы Ф, применяя конечное число раз операцию элементарной суперпозиции. Конкретное выражение суперпозиции будем называть формулой над системой Ф. G = Fф Суперпозиция элементарных булевых функций – формула. Для удобства записи договоримся, что отрицание – самая сильная операция. Следующая – конъюнкция, а остальные – равносильны. _ _ X+Y = XY V XY _ _ X ~ Y = XY V XY __ X ® Y = X V Y _ _ X ¯ Y = X Y
Популярное: Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (811)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |