Операции суперпозиции и замыкания. Полнота, базис системы функций. Суперпозиция функций Свойства булевых функций
Однотактные (не содержащие элементов памяти) дискретные логические устройства реализуют на выходе некоторый набор функций алгебры логики `F m = (F 1 ,F 2 ,…,F m ), которые в каждый момент времени зависят только от состояния входов устройства `х n = (x 1 ,x 2 ,…,x n ): `F m = `F m (`х n ). Практически такие устройства проектируют и изготавливают из отдельных неделимых элементов, реализующих некоторый набор (систему) {f } элементарных функций алгебры путем присоединения выходов одних элементов ко входам других.
При проектировании логических устройств актуальными являются следующие вопросы.
1. Задана система элементарных функций {f }. Какие выходные функции F i можно получить, используя функции из {f }?
2. Задано множество выходных булевых функций {F } (в частности, равное всему множеству функций алгебры логики Р 2). Какой должна быть исходная система элементарных функций {f }, обеспечивающая возможность получения на выходе любой из функций множества {F }?
Для обоснованного ответа на данные вопросы используют понятия суперпозиции, замкнутости и полноты систем функций.
Определение. Рассмотрим множество логических связок {F }, соответствующее некоторой системе функций {f }. Суперпозицией над {f } называется любая функция j, которую можно реализовать формулой над {F }.
Практически суперпозицию можно представить как результат подстановки функций из {f } в качестве аргументов в функции из этого же множества.
Пример 1 . Рассмотрим систему функций {f }= {f 1 (х ) =`х, f 2 (х,у )= х &у, f 3 (х,у )= х Úу } . Подставляя в функцию f 3 (х,у ) вместо первого аргумента х функцию f 1 (х ), вместо второго - f 2 (х,у ), получим суперпозицию h (х,у )= f 3 (f 1 (х ), f 2 (х,у ))=`х Ú х & у . Физическая реализация подстановки дана на рис.1.18.
Определение. Пусть М -некоторое множество функций алгебры логики(P 2). Множество всех суперпозиций над М называется замыканием множества М и обозначается [М ]. Получение [М ]по исходному множеству М называется операцией замыкания . Множество М называется функционально замкнутым классом , если [М ] = М . Подмножество m Í M называется функционально полной системой в М , если [m ] = М .
Замыкание [М ]представляет собой все множество функций, которое можно получить из М путем применения операции суперпозиции, т.е. всех возможных подстановок.
Замечания. 1. Очевидно, любая система функций {f } является функционально полной в себе самой.
2 . Без ограничения общности можно считать, что тождественная функция f (х )=х , не изменяющая значений истинности переменных, изначально входит в состав любой системы функций.
Пример 2 . Для рассмотренных ниже систем функций {f } выполнить следующие действия:
1) найти замыкание [f ],
2) выяснить, будет ли система {f } замкнутым классом,
3) найти функционально полные системы в {f }.
Решение .
I. {f }={0}. При подстановке функции {fº 0} в саму себя получаем ее же, т.е. никаких новых функций не образуется. Отсюда следует: [f ] = {f }. Рассмотренная система является функционально замкнутым классом. Функционально полная система в ней одна и равна всей {f }.
II. {f }= {0,Ø }. Подстановка Ø (Ø х )дает тождественную функцию, которая формально не расширяет исходную систему. Однако при подстановке Ø (0) получим тождественную единицу - новую функцию, которой не было в исходной системе: Ø (0)=1. Применение всех других подстановок не приводит к появлению новых функций, например: ØØ 0= 0, 0(Ø х )=0.
Таким образом, применение операции суперпозиции позволило получить более широкое по сравнению с исходным множество функций [f ]={0,Ø ,1}. Отсюда следует строгое вхождение: {f } Ì [f ]. Исходная система {f }не является функционально замкнутым классом. Кроме самой системы {f }других функционально полных систем в ней нет, поскольку в случае её сужения из одной функции f= 0 нельзя путем подстановки получить отрицание, а из одной функции отрицания нельзя получить тождественный нуль.
III. {f } = {& ,Ú ,Ø }.Замыканием данной системы является все множество функций алгебры логики P 2 , так как формулу любой из них можно представить в виде ДНФ либо КНФ, в которых используются элементарные функции {f } = {& ,Ú ,Ø}. Данный факт является конструктивным доказательством полноты рассмотренной системы функций в P 2: [f ] =P 2 .
Поскольку в P 2 содержится бесконечное множество других функций, отличных от {f } = {& ,Ú ,Ø }, то отсюда следует строгое вхождение: {f }Ì[f ]. Рассмотренная система не является функционально замкнутым классом.
Помимо самой системы функционально полными в ней будут подсистемы {f } 1 = {& ,Ø } и {f } 2 = {Ú ,Ø }. Это следует из того, что при помощи правил де Моргана функцию логического сложения Úможно выразить через {& ,Ø},а функцию логического умножения & - через {Ú, Ø}:
(х & у ) = Ø (`х Ú`у ), (х Ú у ) = Ø (х &`у ).
Других функционально полных подсистем в {f } нет.
Проверку полноты подсистемы функций {f } 1 Ì {f }во всей системе {f }можно производить путем сведения {f } 1 к другой, заведомо полной в {f }системе.
Неполноту подсистемы {f } 1 в {f }можно проверить, доказав строгое вхождение [f 1 ] Ì [f ].
Определение. Подмножество m Í M называют функциональным базисом (базисом ) системы М , если [m ] = М , а после исключения из нее любой функции множество оставшихся не полно в М .
Замечание . Базисами системы функций {f} являются все ее функционально полные подсистемы {f} 1 , которые невозможно уменьшить без потери полноты в {f} .
Пример 3 . Для всех систем, рассмотренных в Примере 2, найти базисы.
Решение .В случаях 1 и 2 функционально полными являются только сами системы и сузить их невозможно. Следовательно, они же являются и базисами.
В случае 3 есть две функционально полные в {f }подсистемы {f } 1 = {&,Ø } и {f } 2 ={Ú,Ø }, которые невозможно сократить без потери полноты. Они будут базисами системы {f } = {&,Ú,Ø}.
Определение. Пусть система {f }является замкнутым классом. Ее подмножество {f } 1 Ì {f }называют предполным классом в {f }, если {f } 1 не полно в {f } ([f 1 ] Ì [f ]), а для любой функции jиз системы{f }, не входящей в {f } 1 (jÎ{f } \ {f } 1) справедливо: [j È {f } 1 ] = [f ], т.е. прибавление jк {f } 1 делает ее полной в {f }.
Задачи
1. Проверить замкнутость множеств функций:
а) {Ø }; б) {1, Ø }; в) {(0111); (10)};г) {(11101110); (0110)};д) {(0001); (00000001); (0000000000000001); … }.
2. Проверить полноту систем функций в P 2:
а) {0,Ø }; б) {(0101) , (1010) }; в) {¯ }; г) {(0001) , (1010) }.
3. Найти замыкание системы функций и ее базис:
а) {0 , 1 , Ø }; б) {(1000) , (1010), (0101) }; в) {(0001) , (1110), (10) }; г) {(1010) , (0001), (0111) }.
1.10.2 Функции, сохраняющие константы. Классы Т 0 и Т 1
Определение. Функция f (`х n ) сохраняет 0, если f (0,..., 0) = 0. Функция f (`х n ) сохраняет 1, если f (1, ... , 1) = 1.
Множества функций n переменных, сохраняющих 0 и 1, обозначают, соответственно, Т 0 n и Т 1 n . Все множества функций алгебры логики, сохраняющих 0 и 1, обозначают Т 0 и Т 1 . Каждое из множеств Т 0 и Т 1 является замкнутым предполным классом в Р 2 .
Из элементарных функций в Т 0 и Т 1 одновременно входят, например, &и Ú. Принадлежность любой функции к классам Т 0 , Т 1 можно проверить по первому и последнему значению ее вектора значений в таблице истинности либо непосредственной подстановкой нулей и единиц в формулу при аналитическом задании функции.
Определение. Дублирующей называют такую подстановку, при которой вместо нескольких независимых переменных в функцию подставляют одну и ту же переменную. При этом величины переменных в наборах, которые раньше принимали значения независимо друг от друга, всегда будут одинаковыми.
ЗАДАЧИ
1.Проверить принадлежность к классам Т 0 и Т 1 функций:
а) обощенного сложения, б) обощенного умножения, в) констант, г) ху Ú yz , д) х ® у ® ху , е) х Å у , ж)( х 1 Å… Å х n) ® ( y 1 Å… Å y m) при n,m Î N.
2. Доказать замкнутость каждого из классов Т 0 и Т 1 .
3. Доказать, что если f (`х n ) ÏТ 0 , то из нее путем дублирующей подстановки можно получить константу 1 либо отрицание.
4. Доказать, что если f (`х n ) ÏТ 1 , то из нее путем дублирующей подстановки можно получить константу 0 либо отрицание.
5. Доказать предполноту каждого из классов Т 0 и Т 1 (например, сведением дополненной системы к {f } = {& ,Ú ,Ø }).
6. Найти мощность классов Т 0 n и Т 1 n .
Определение функции, области задания и множества значений. Определения, связанные с обозначением функции. Определения сложной, числовой, действительной, монотонной и многозначной функции. Определения максимума, минимума, верхней и нижней граней для ограниченных функций.
СодержаниеФункцией y = f(x) называется закон (правило, отображение), согласно которому, каждому элементу x множества X ставится в соответствие один и только один элемент y множества Y .
Множество X
называется областью определения функции
.
Множество элементов y ∈
Y
,
которые имеют прообразы во множестве X
,
называется множеством значений функции
(или областью значений
).
Область определения функции иногда называют множеством определения или множеством задания функции.
Элемент x ∈
X
называют аргументом функции
или независимой переменной
.
Элемент y ∈
Y
называют значением функции
или зависимой переменной
.
Само отображение f называется характеристикой функции .
Характеристика f обладает тем свойством, что если два элемента и из множества определения имеют равные значения: , то .
Символ, обозначающий характеристику, может совпадать с символом элемента значения функции. То есть можно записать так: . При этом стоит помнить, что y - это элемент из множества значений функции, а - это правило, по которому для элемента x ставится в соответствие элемент y .
Сам процесс вычисления функции состоит из трех шагов. На первом шаге мы выбираем элемент x из множества X . Далее, с помощью правила , элементу x ставится в соответствие элемент множества Y . На третьем шаге этот элемент присваивается переменной y .
Частным значением функции называют значение функции при выбранном (частном) значении ее аргумента.
Графиком функции f называется множество пар .
Сложные функции
Определение
Пусть заданы функции и .
Причем область определения функции f
содержит множество значений функции g
.
Тогда каждому элементу t
из области определения функции g
соответствует элемент x
,
а этому x
соответствует y
.
Такое соответствие называют сложной функцией
: .
Сложную функцию также называют композицией или суперпозицией функций и иногда обозначают так: .
В математическом анализе принято считать, что если характеристика функции обозначена одной буквой или символом, то она задает одно и то же соответствие. Однако, в других дисциплинах, встречается и другой способ обозначений, согласно которому отображения с одной характеристикой, но разными аргументами, считаются различными. То есть отображения и считаются различными. Приведем пример из физики. Допустим мы рассматриваем зависимость импульса от координаты . И пусть мы имеем зависимость координаты от времени . Тогда зависимость импульса от времени является сложной функцией . Но ее, для краткости, обозначают так: . При таком подходе и - это различные функции. При одинаковых значениях аргументов они могут давать различные значения. В математике такое обозначение не принято. Если требуется сокращение, то следует ввести новую характеристику. Например . Тогда явно видно, что и - это разные функции.
Действительные функции
Область определения функции и множество ее значений могут быть любыми множествами.
Например, числовые последовательности - это функции, областью определения которых является множество натуральных чисел, а множеством значений - вещественные или комплексные числа.
Векторное произведение тоже функция, поскольку для двух векторов и имеется только одно значение вектора .
Здесь областью определения является множество всех возможных пар векторов .
Множеством значений является множество всех векторов.
Логическое выражение является функцией. Ее область определения - это множество действительных чисел (или любое множество, в котором определена операция сравнения с элементом “0”). Множество значений состоит из двух элементов - “истина” и “ложь”.
В математическом анализе большую роль играют числовые функции.
Числовая функция - это функция, значениями которой являются действительные или комплексные числа.
Действительная или вещественная функция - это функция, значениями которой являются действительные числа.
Максимум и минимум
Действительные числа имеют операцию сравнения. Поэтому множество значений действительной функции может быть ограниченным и иметь наибольшее и наименьшее значения.
Действительная функция называется ограниченной сверху (снизу)
, если существует такое число M
,
что для всех выполняется неравенство:
.
Числовая функция называется ограниченной
, если существует такое число M
,
что для всех :
.
Максимумом M
(минимумом m
)
функции f
,
на некотором множестве X
называют значение функции при некотором значении ее аргумента ,
при котором для всех ,
.
Верхней гранью
или точной верхней границей
действительной, ограниченной сверху функции называют наименьшее из чисел, ограничивающее область ее значений сверху. То есть это такое число s
,
для которого для всех и для любого ,
найдется такой аргумент ,
значение функции от которого превосходит s′
:
.
Верхняя грань функции может обозначаться так:
.
Верхней гранью неограниченной сверху функции
Нижней гранью
или точной нижней границей
действительной, ограниченной снизу функции называют наибольшее из чисел, ограничивающее область ее значений снизу. То есть это такое число i
,
для которого для всех и для любого ,
найдется такой аргумент ,
значение функции от которого меньше чем i′
:
.
Нижняя грань функции может обозначаться так:
.
Нижней гранью неограниченной снизу функции является бесконечно удаленная точка .
Таким образом, любая действительная функция, на не пустом множестве X , имеет верхнюю и нижнюю грани. Но не всякая функция имеет максимум и минимум.
В качестве примера рассмотрим функцию ,
заданную на открытом интервале .
Она ограничена, на этом интервале, сверху значением 1
и снизу - значением 0
:
для всех .
Эта функция имеет верхнюю и нижнюю грани:
.
Но она не имеет максимума и минимума.
Если мы рассмотрим туже функцию на отрезке ,
то она на этом множестве ограничена сверху и снизу, имеет верхнюю и нижнюю грани и имеет максимум и минимум:
для всех ;
;
.
Монотонные функции
Определения возрастающей и убывающей функций
Пусть функция определена на некотором множестве действительных чисел X
.
Функция называется строго возрастающей (строго убывающей)
.
Функция называется неубывающей (невозрастающей)
, если для всех таких что выполняется неравенство:
.
Определение монотонной функции
Функция называется монотонной
, если она неубывающая или невозрастающая.
Многозначные функции
Пример многозначной функции. Различными цветами обозначены ее ветви. Каждая ветвь является функцией.
Как следует из определения функции, каждому элементу x из области определения, ставится в соответствие только один элемент из множества значений. Но существуют такие отображения, в которых элемент x имеет несколько или бесконечное число образов.
В качестве примера рассмотрим функцию арксинус
: .
Она является обратной к функции синус
и определяется из уравнения:
(1)
.
При заданном значении независимой переменной x
,
принадлежащему интервалу ,
этому уравнению удовлетворяет бесконечно много значений y
(см. рисунок).
Наложим на решения уравнения (1) ограничение. Пусть
(2)
.
При таком условии, заданному значению ,
соответствует только одно решение уравнения (1). То есть соответствие, определяемое уравнением (1) при условии (2) является функцией.
Вместо условия (2) можно наложить любое другое условие вида:
(2.n)
,
где n
- целое. В результате, для каждого значения n
,
мы получим свою функцию, отличную от других. Множество подобных функций является многозначной функцией
. А функция, определяемая из (1) при условии (2.n) является ветвью многозначной функции
.
Это совокупность функций, определенных на некотором множестве.
Ветвь многозначной функции - это одна из функций, входящих в многозначную функцию.
Однозначная функция - это функция.
Использованная литература:
О.И. Бесов. Лекции по математическому анализу. Часть 1. Москва, 2004.
Л.Д. Кудрявцев. Курс математического анализа. Том 1. Москва, 2003.
С.М. Никольский. Курс математического анализа. Том 1. Москва, 1983.
Соответствием G между множествами А и В называется подмножество . Если , то говорят, что b
соответствует а. Множество всех соответствующих элементу
Называется образом элемента а. Множество всех которым соответствует элемент , называется
прообразом элемента b .
Множество пар (Ь, а) таких, что называется обратным по
отношению к G и обозначается . Понятия образа и прообраза для
" G и взаимно обратны.
Примеры. 1) Поставим в соответствие натуральному числу п
множество действительных чисел . Образом числа 5
будет полуинтервал
(так обозначают наибольшее целое, меньшее или равное X ). Прообразом числа 5 при этом соответствии является бесконечное множество: полуинтервал }