Пятница, 29.03.2024, 13:22
Приветствую Вас Гость | RSS

Мультимедийное пособие по дискретной математике

Меню сайта
Форма входа

Определение и способ задания булевых функций.

Определение и способ задания булевых функций 

Булевой функцией от n аргументов называется однозначное отображение n – мерного булева куба на одномерный булев куб. 

Способы задания функций 
1. Табличный








3. В виде формулы. 
Функция f зависит от переменной xi фиктивно, если для любых двух наборов значений переменных, отличающихся только значением переменной xi, значения функции f совпадают. 
Будем говорить, что f зависит от переменной xi существенно, если существуют такие два набора значений, отличающихся только значением переменной xi, на которых значения функций различно. 
Фиктивные переменные у функции можно добавлять и исключать. 
Две булевы функции называются равными или равносильными, если одну можно получить из другой путем добавления и изъятия фиктивных переменных. 

Строим таблицу функций при n = 1. 

X
0
X _ 
X

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  

Поиск
Счеткич визитов

Copyright MyCorp © 2024
Бесплатный хостинг uCoz


Яндекс.Метрика