 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Булевы функции
Любую формулу алгебры логики можно рассматривать как функцию, определенную на множестве B ={1, 0}, где 1 соответствует значению “и”, а 0 – значению “л”.
Функцией алгебры логики (логической функцией) или булевой функцией f(x1,x2,...,xn) называетсяотображение f: B n® B, определенное на множестве упорядоченных наборов элементов множества B и принимающее значения из этого множества. Обозначим через P n - множество булевых функций n переменных.
Логическую функцию n переменных f(x1,x2,...,xn) можно задать таблицей, в левой части которой перечислены все 2n наборов значений переменных, а в правой части - значения функции на этих наборах.
| x1 x2 ... хn-1 xn | f(x1, x2 ,... хn-1 , xn) |
| 0 0... 0 0 0 0... 0 1 0 0... 1 0 ................ 1 1... 1 0 1 1... 1 1 | f(0,0,...,0,0) f(0,0,...,0,1) f(0,0,...,1,0) ........ f(1,1,...,1,0) f(1,1,...,1,1) |
При любом фиксированном упорядочении наборов булева функция n переменных полностью определяется вектор-столбцом своих значений, размерность которого равна числу наборов значений функции, то есть 2n . Поэтому число различных функций n переменных равно числу различных двоичных векторов длины 2n, то есть 
, т.е. | 
| = . Нулем (единицей) булевой функции назовем упорядоченный набор значений переменных, на котором значение функции равно 0 (1).
Пусть F={ 
} – множество булевых функций, называемое базисом. Формулой 
над базисом F (обозначается 
[F]) называется выражение вида [F]= 
, где 
F. Таким образом, всякая формула является суперпозицией базисных функций, для ее представления обычно применяется инфиксная форма записи с логическими операциями 
~. Каждой формуле однозначно соответствует некоторая булева функция f, в этом случае говорят, что формула реализует функцию f, однако, как будет показано ниже, такая реализация не единственна.
Приведем примеры логических функций одной и двух переменных и их реализаций в виде формул.
Логических функций одной переменной четыре: две нуль-местные (j0(х), j3(х)) - константы 0 и 1, значения которых не зависят от значения переменной, и две одноместные функции - тождественная и отрицание.
| Х | j0 | j1 | j2 | j3 |
Тождественная функция "повторяет" значение х: j1(х)=х. Функция отрицание возвращает значение, противоположное значению х: j2(х)=х.
Логических функций двух переменных шестнадцать:
| х1 | Х2 | j0 | j1 | j2 | j3 | j4 | j5 | j6 | j7 | j8 | j9 | j10 | j11 | j12 | j13 | j14 | j15 |
Рассмотрим подробнее все эти функции.
* j0(х1,х2) 
0 и j15 (х1,х2) 1.
* j1(х1,х2) = х1 Ù х2 . Эта функция называется ещё логическим умножением и обозначается, также, х1х2.
* j2(х1.х2) = Ø (х1®х2).
* j3(х1,х2) = х1.
* j4(х1.х2) = Ø (х2®х1).
* j5(х1,х2) = х2.
* j6(х1,х2) = 
(х1~х2) называются неравнозначностью, разделительной дизъюнкцией или сложением по модулю 2 и обозначается еще как х1Å х2.
* j7(х1.х2) = х1Ú х2 .
* j8(х1.х2) = 
(х1Úх2) – антидизъюнкция, которая называется, также, стрелка Пирса и обозначается х1¯х2.
* j9(х1.х2) = х1~х2. Эту функцию называют еще равнозначностью и обозначают х1ºх2 .
* j10(х1.х2) = 
.
* j11(х1.х2) = х2®х1.
* j12(х1.х2) = 
.
* j13(х1.х2) = х1®х2.
* j14(х1.х2) = (х1Ùх2) – антиконъюнкция, которая называется еще штрих Шеффера и обозначается х1 | х2.
Можно определить логические операции, соответствующие функциям j6, j8, j14, построив для них таблицы истинности.
Фиктивной переменной (несущественной) функции f(x1,..., xn) называется переменная хi, изменение значения которой не меняет значения функции, то есть
f(x1,..., хi-1, 1, xi+1,..., xn)= f(x1,..., хi-1, 0, xi+1,..., xn).
Например, в функциях j3 и j12 переменная х2 фиктивна, а в функциях j5 и j10 фиктивна переменная х1.
Функция f(x1,..., xn), имеющая фиктивную переменную xi, по существу зависит от (n-1)-й переменной, т.е. представляет собой функцию g(x1,..., хi-1, xi+1,..., xn). Говорят, что функция g получена из функции f удалением фиктивной переменной, а функция f получена из функции g введением фиктивной переменной, причём эти функции считаются равными.
Поиск по сайту: