Меню сайта
Лекции
Лекции
|
Определение и способ задания булевых функций.Определение и способ задания булевых функцийБулевой функцией от n аргументов называется однозначное отображение n – мерного булева куба на одномерный булев куб. Способы задания функций 1. Табличный 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 Таблица всех элементарных булевых функций, применяемых в записи формул Все эти функции от двух аргументов мы и будем называть элементарными булевыми функциями. Основными элементарными функциями являются конъюнкция, дизъюнкция и отрицание. Элементарные булевы функции удовлетворяют всем аксиомам булевой алгебры. Суперпозиции булевых функций Ф = {ф1…фk} F называется элементарной суперпозицией функции из множества Ф, если она получена одним из следующих способов. 1. Переименование какого-нибудь аргумента в одной из функций системы (возможно отождествление аргумента). 2. В одну из функций системы вместо любого аргумента ставится значение любой функции из этой системы. Ф1 = {Y…xn} Фi = (x1 … фj(x1…xn) … xn) Ф(1) – множество всех элементарных суперпозиций из системы Ф. Ф(k+1) – множество всех элементарных суперпозиций из систему Фk. Функция g называется суперпозицией функций из системы. Это означает, что g можно получить из функции системы Ф, применяя конечное число раз операцию элементарной суперпозиции. Конкретное выражение суперпозиции будем называть формулой над системой Ф. G = Fф Суперпозиция элементарных булевых функций – формула. Для удобства записи договоримся, что отрицание – самая сильная операция. Следующая – конъюнкция, а остальные – равносильны. _ _ X+Y = XY V XY _ _ X ~ Y = XY V XY |
Поиск
Счеткич визитов
Друзья сайта
|