Операции суперпозиции и замыкания. Полнота, базис системы функций. Тема: «Функция: понятие, способы задания, основные характеристики. Обратная функция. Суперпозиция функций Преимущества построения графиков онлайн
Построить функцию
Мы предлагаем вашему вниманию сервис по потроению графиков функций онлайн, все права на который принадлежат компании Desmos . Для ввода функций воспользуйтесь левой колонкой. Вводить можно вручную либо с помощью виртуальной клавиатуры внизу окна. Для увеличения окна с графиком можно скрыть как левую колонку, так и виртуальную клавиатуру.
Преимущества построения графиков онлайн
- Визуальное отображение вводимых функций
- Построение очень сложных графиков
- Построение графиков, заданных неявно (например эллипс x^2/9+y^2/16=1)
- Возможность сохранять графики и получать на них ссылку, которая становится доступной для всех в интернете
- Управление масштабом, цветом линий
- Возможность построения графиков по точкам, использование констант
- Построение одновременно нескольких графиков функций
- Построение графиков в полярной системе координат (используйте r и θ(\theta))
С нами легко в режиме онлайн строить графики различной сложности. Построение производится мгновенно. Сервис востребован для нахождения точек пересечения функций, для изображения графиков для дальнейшего их перемещения в Word документ в качестве иллюстраций при решении задач, для анализа поведенческих особенностей графиков функций. Оптимальным браузером для работы с графиками на данной странице сайта является Google Chrome. При использовании других браузеров корректность работы не гарантируется.
- (позднелат. superpositio, – наложение, от лат. superpositus – положенный наверх) (композиция) – операция логико математич. исчислений, заключающаяся в получении из к. л. данных функций f и g данного исчисления новой функции g (f) (выражение g… … Философская энциклопедия
Термин суперпозиция (наложение) может относиться к следующим понятиям: Суперпозиция композиция функций (сложная функция) Принцип суперпозиции принцип в физике и математике, описывающий наложение процессов (например, волн) и, как следствие,… … Википедия
Композиция функций, составление из двух функций сложной функции … Математическая энциклопедия
У этого термина существуют и другие значения, см. Суперпозиция. Квантовая механика … Википедия
В данной статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из за отсутствия сносок … Википедия
В теории дискретных функциональных систем булевой функцией называют функцию типа, где булево множество, а n неотрицательное целое число, которое называют арностью или местностью функции. Элементы 1 (единица) и 0 (ноль) стандартно интерпретируют… … Википедия
Один из важнейших для оснований математики и математич. логики классов понятий, служащих уточнениями содержат. понятий эффективно вычислимой арифметической функции и эффективно разрешимого арифметического предиката, а в конечном счете, – и… … Философская энциклопедия
Функция, вычисление значений к рой может быть проведено с помощью заранее заданной эффективной процедуры, или алгоритма. Характерная черта вычислительных процессов вычисление искомых величин задач происходит последовательно из данных исходных… … Математическая энциклопедия
Необходимо перенести содержимое этой статьи в статью «Дифференцирование сложной функции». Вы можете помочь проекту, объединив статьи. В случае необходимости обсуждения целесообразности объединения, замените этот шаблон на шаблон {{к объединению}} … Википедия
- (лат. compositio составление, связывание, сложение, соединение): В Викисловаре есть статья «композиция» Искусство Композиция (изобразительное искусство) организующий компонент художественной формы, придающий прои … Википедия
Книги
- Дискретная математика. Основные теоретико-множественные конструкции. Часть VI , А. И. Широков. Пособие представляет собой VI часть раздела «Основные теоретикомножественные конструкции дискретной математики». В гл. XI рассматриваются следующие понятия: композиции функций (§1); функции,…
Однотактные (не содержащие элементов памяти) дискретные логические устройства реализуют на выходе некоторый набор функций алгебры логики `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 .
Функция f, получаемая из функций f 1 , f 2 ,…f n с помощью операций подстановки и переименования аргументов, называется суперпозицией функций.
Всякая формула, выражающая функцию f как суперпозицию других функций, задаёт способ её вычисления, т. е. формулу можно вычислить, если вычислены значения всех её подформул. Значение подформулы можно вычислить по известному набору значений двоичных переменных.
По каждой формуле можно восстановить таблицу логической функции, но не наоборот, т.к. каждой логической функции можно представить несколько формул в различных базисах
Формулы F i и F j представляющие одну и ту же логическую функцию f i, называются эквивалентными . Так, эквивалентными формулами являются:
1. f 2 (x 1 ; x 2)=(x 1 ×`x 2)=ù(`x 1 Úx 2)= ù(x 1 ®x 2);
2. f 6 (x 1 ; x 2)=(`x 1 ×x 2 Úx 1 ×`x 2)= ù(x 1 «x 2)=(x 1 Åx 2);
3. f 8 (x 1 ; x 2)=(`x 1 ×`x 2)= ù(x 1 Úx 2)=(x 1 ¯x 2);
4. f 14 (x 1 ;x 2)=(`x 1 Ú`x 2)= ù(x 1 ×x 2)=x 1 ½x 2 ;
5. f 9 (x 1 ;x 2)=((`x 1 ×`x 2)Ú(x 1 ×x 2))=(x 1 «x 2) ;
6. f 13 (x 1 ;x 2)= (`x 1 Úx 2)=(x 1 ®x 2).
Если какая-либо формула F содержит подформулу F i , то замена F i на эквивалентную F j не изменяет значения формулы F при любом наборе булевого вектора, но изменяет форму её описания. Вновь полученная формула F` эквивалентна формуле F.
Для упрощения сложных алгебраических выражений булевой функции выполняют эквивалентные преобразования , используя законы булевой алгебры и правила подстановки и замещения ,
При написании формул булевой алгебры следует помнить:
· число левых скобок равно числу правых скобок,
· нет двух рядом стоящих логических связок, т. е. между ними должна быть формула,
· нет двух рядом стоящих формул, т. е. между ними должна быть логическая связка,
· логическая связка “×” сильнее логической связки “Ú”,
· если “ù ” относится к формуле (F 1 ×F 2) или (F 1 Ú F 2), то прежде всего следует выполнить эти преобразования по закону де Моргана: ù(F 1 ×F 2)=`F 1 Ú`F 2 или ù(F 1 ÚF 2)=`F 1 ×`F 2 ;
· операция “× ” сильнее “Ú”, что позволяет опускать скобки.
Пример : выполнить эквивалентные преобразования формулы F=x 1 ×x 2 ×x 3 ×`x 4 Ú`x 1 ×x 3 Ú`x 2 ×x 3 Úx 3 ×x 4 .
· по закону коммутативности:
F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×`x 1 Úx 3 ×`x 2 Úx 3 ×x 4 ;
· по закону дистрибутивности:
F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×`x 1 Úx 3 ×(`x 2 Úx 4);
· по закону дистрибутивности:
F=x 3 ×x 1 ×x 2 ×`x 4 Úx 3 ×(`x 1 Ú`x 2 Úx 4);
· по закону дистрибутивности:
F=x 3 ×((x 1 ×x 2 ×`x 4)Ú(`x 1 Ú`x 2 Úx 4));
· по закону де Моргана:
F=x 3 ×((x 1 ×x 2 ×`x 4)Úù(x 1 ×x 2 ×`x 4));
· по закону противоречия:
Таким образом x 1 ×x 2 ×x 3 ×`x 4 Ú`x 1 ×x 3 Ú`x 2 ×x 3 Úx 3 ×x 4 =x 3 .
Пример: выполнить преобразования формулы
F=(x 1 ×`x 2 Ú`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ú`x 1 ×x 2);
· по закону де Моргана
F=(x 1 ×`x 2 Ú`x 1 ×x 2)×(`x 1 Ú`x 2)Ú(x 1 ×x 2)×(`x 1 Úx 2)×(x 1 Ú`x 2);
· по закону дистрибутивности:
F=x 1 ×`x 2 Ú`x 1 ×x 2 Úx 1 ×x 2 ;
· по законам коммутативности и дистрибутивности:
F= `x 1 ×x 2 Úx 1 ×(`x 2 Úx 2);
· по закону противоречия:
F= `x 1 ×x 2 Úx 1 ;
· по закону Порецкого
Таким образом (x 1 ×`x 2 Ú`x 1 ×x 2)×ù(x 1 ×x 2)Ú(x 1 ×x 2)×ù(x 1 ×`x 2 Ú`x 1 ×x 2)= (x 2 Úx 1).
Пример: выполнить преобразование формулы F=ù(`x 1 Úx 2)Ú((`x 1 Úx 3)×x 2).
· по закону де Моргана:
F= ù(`x 1 Úx 2)×ù((`x 1 Úx 3)×x 2);
· по закону де Моргана:
F=x 1 ×`x 2 ×(ù(`x 1 Úx 3)Ú`x 2);
· по закону де Моргана:
F=x 1 ×`x 2 ×(x 1 ×`x 3 Ú`x 2);
· по закону дистрибутивности:
F=x 1 ×`x 2 ×`x 3 Úx 1 ×`x 2 ;
· по закону поглощения:
Таким образом ù(`x 1 Úx 2)×((`x 1 Úx 3)×x 2)= x 1 ×`x 2 .
Пример : выполнить преобразование формулы:
F=ù(x 1 ®x 2)×(`x 3 Ú`x 4)Ú(x 1 ¯x 2)×ù(x 3 ×x 4).
1) преобразовать формулу в базис булевой алгебры:
F=ù(`x 1 Úx 2)×(`x 3 Ú`x 4)Úù(x 1 Úx 2)× ù(x 3 ×x 4);
2) опустить знак “` “ до двоичных переменных:
F=(x 1 ×`x 2)×(`x 3 Ú`x 4)Ú(`x 1 ×`x 2)×(`x 3 Ú`x 4);
3) преобразовать формулу по закону дистрибутивности:
F=x 1 ×`x 2 ×`x 3 Úx 1 ×`x 2 ×`x 4 Ú`x 1 ×`x 2 ×`x 3 Ú`x 1 ×`x 2 ×`x 4 ;
4) вынести за скобку `x 2 по закону дистрибутивности:
F=`x 2 ×(x 1 ×`x 3 Úx 1 ×`x 4 Ú`x 1 ×`x 3 Ú`x 1 ×`x 4);
5) преобразовать по закону дистрибутивности:
F=`x 2 ×(`x 3 ×(x 1 Ú`x 1)Ú`x 4 ×(x 1 Ú`x 1));
6) использовать закон противоречия:
F=`x 2 ×(`x 3 Ú`x 4)
Свойства булевых функций
Часто возникает вопрос: всякая ли булева функция представима суперпозицией формул f 0 , f 1 ,..f 15 ? Для того, чтобы определить возможность формирования любой булевой функции с помощью суперпозиции этих формул, необходимо определить их свойства и условия использования функционально полной системы.
Самодвойственные булевы функции
самодвойственной , если f(x 1 ;x 2 ;…x n)=`f(`x 1 ;`x 2 ;…`x n).
Например, функции f 3 (x 1 ;x 2)=x 1 , f 5 (x 1 ;x 2)=x 2 , f 10 (x 1 ;x 2)=`x 2 и f 12 (x 1 ;x 2)=`x 1 являются самодвойственными, т. к. при изменении значения аргумента они изменяют свое значение.
Любая функция, полученная с помощью операций суперпозиции из самодвойственных булевых функций, сама является самодвойственной. Поэтому множество самодвойственных булевых функций не позволяет формировать не самодвойственные функции.
Монотонные булевы функции
Функция f(x 1 ; x 2 ;…x n) называется монотонной , если для каждого s 1i £s 2i булевых векторов (s 11 ; s 12 ;……;s 1n) и (s 21 ;s 22 ;……;s 2n) выполняется условие: f(s 11 ;s 12 ;…;s 1i ;…;s 1n)£f(s 21 ;s 22 ;…;s 2i ;…;s 2n).
Например, для функций f(x 1 ; x 2) монотонными функциями являются:
если (0; 0)£(0; 1), то f(0; 0)£f(0; 1),
если (0; 0)£(1; 0), то f(0; 0)£f(1; 0),
если (0; 1)£(1; 1), то f(0; 1)£f(1; 1),
если (1; 0)£(1; 1), то f(1; 0)£f(1; 1).
Таким условиям удовлетворяют следующие функции:
f 0 (x 1 ; x 2)=0; f 1 (x 1 ; x 2)=(x 1 ×x 2); f 3 (x 1 ; x 2)=x 1 ; f 5 (x 1 ; x 2)=x 2 ; f 7 (x 1 ;x 2)=(x 1 Úx 2); f 15 (x 1 ; x 2)=1.
Любая функция, полученная с помощью операции суперпозиции из монотонных булевых функций, сама является монотонной. Поэтому множество монотонных функций не позволяет формировать не монотонные функции.
Линейные булевы функции
Алгебра Жегалкина, опирающаяся на базис F 4 ={×; Å; 1}, позволяет любую логическую функцию представить полиномом, каждый член которого есть конъюнкция I булевых переменных булевого вектора в пределах 0£i£n:
P(x 1 ; x 2 ;…x n)=b 0 ×1 Å b i ×x i Å 1 £ j ¹ k £ n b j ×x j ×x k Å……Å b 2n-1 ×x 1 ×x 2 ×...×x n.
Например, для логических функций f 8 (x 1 ; x 2)
полином Жегалкина имеет вид: P(x 1 ; x 2)=1Å x 1 Å x 2 Å x 1 ×x 2 .
Преимущества алгебры Жегалкина состоят в “арифметизации” логических формул, а недостатки - в сложности, особенно при большом числе двоичных переменных.
Полиномы Жегалкина, не содержащие конъюнкции двоичных переменных, т.е. P(x 1 ; x 2 ;…;x n)=b 0 ×1Åb 1 ×x 1 Å…Åb n ×x n называют линейными .
Например, f 9 (x 1 ; x 2)=1Åx 1 Åx 2 , или f 12 (x 1 ;x 2)=1Åx 1 .
Основные свойства операции сложения по модулю 2 приведены в таблице 1.18.
Если логическая функция задана таблицей или формулой в любом базисе, т.е. известны значения булевой функции для различных наборов булевых переменных, то можно вычислить все
коэффициенты b i полинома Жегалкина, составив систему уравнений по всем известным наборам двоичных переменных.
Пример : дана булева функция f(x 1 ;x 2)=x 1 Úx 2 . Значение этой функции известны для всех наборов булевых переменных.
F(0;0)=0=b 0 ×1Å b 1 ×0 Å b 2 ×0 Å b 3 ×0×0;
f(1;0)=1=b 0 ×1Å b 1 ×1Å b 2 ×0Å b 3 ×1×0;
f(1;1)=1=b 0 ×1Å b 1 ×1Å b 2 ×1Å b 3 ×1×1;
Откуда находим b 0 =0; b 1 =1; b 2 =1; b 3 =1.
Следовательно, (x 1 Úx 2)=x 1 Åx 2 Åx 1 ×x 2 , т. е. дизъюнкция есть нелинейная булева функция.
Пример : дана булева функция f(x 1 ;x 2)=(x 1 ®x 2). Значение этой функции также известны для всех наборов двоичных переменных.
F(0;0)=1=b 0 ×1Å b 1 ×0 Å b 2 ×0 Å b 3 ×0×0;
f(0;1)=1=b 0 ×1Å b 1 ×0 Å b 2 ×1Å b 3 ×0×1;
f(1;0)=0=b 0 ×1Åb 1 ×1Åb 2 ×0Åb 3 ×1×0;
f(1;1)=1=b 0 ×1Åb 1 ×1Åb 2 ×1Åb 3 ×1×1;
Откуда находим b 0 =1; b 1 =1; b 2 =0; b 3 =1.
Следовательно, (x 1 ®x 2)=1Å x 2 Å x 1 ×x 2 .
В таблице 1.19 приведены полиномы Жегалкина для основных представителей булевых функций из таблицы 1.15.
Если дано аналитическое выражение логической функции и неизвестны ее значения для различных наборов двоичных переменных, то можно построить полином Жегалкина, опираясь на конъюнктивный базис алгебры Буля F 2 ={` ; ×}:
Пусть f(x 1 ; x 2)=(x 1 Úx 2).
Тогда (x 1 Úx 2)=ù(`x 1 ×`x 2)=((x 1 Å 1)×(x 2 Å 1))Å 1=x 1 ×x 2 Å x 1 ×1Å x 2 ×1Å 1×1Å1=
(x 1 Åx 2 Åx 1 ×x 2).
Пусть f(x 1 ;x 2)=(x 1 ®x 2).
Тогда (x 1 ®x 2)=(`x 1 Úx 2)=ù(x 1 ×`x 2)=x 1 ×(x 2 Å 1)Å 1=x 1 ×x 2 Å x 1 ×1Å 1= =(1Åx 1 Åx 1 ×x 2).
Пусть f(x 1 ;x 2)=(x 1 «x 2).
Тогда (x 1 «x 2)=(`x 1 ×`x 2 Úx 1 ×x 2)=ù(ù(`x 1 ×`x 2)×ù(x 1 ×x 2))=(((x 1 Å1)×(x 2 Å1))Å1)× ×(x 1 ×x 2 Å)Å1=(x 1 ×x 2 Åx 1 Åx 2 Å1Å1)×(x 1 ×x 2 Å1)Å1=x 1 ×x 2 Åx 1 ×x 2 Åx 1 ×x 2 Åx 1 Å
x 1 ×x 2 Åx 2 Å1=(1Åx 1 Åx 2).
Любая функция, полученная с помощью операции суперпозиции из линейных логических функций, сама является линейной. Поэтому множество линейных функций не позволяет формировать нелинейные функции.
1.5.6.4. Функции, сохраняющие “0”
Функция f(x 1 ; x 2 ;...x n) называется сохраняющей “0”, если для наборов значений двоичных переменных (0; 0;...0) функция принимает значение f(0; 0;…0)=0.
Например, f 0 (0; 0)=0, f 3 (0; 0)=0, f 7 (0; 0)=0 и др.
Любая функция, полученная с помощью операции суперпозиции из функций, сохраняющих “0”, сама является функцией, сохраняющей “0” Поэтому множество функций, сохраняющих “0”, не позволяет формировать функции, не сохраняющие “0”.
1.5.6.5. Функции, сохраняющие “1”
Функция f(x 1 ; x 2 ;…x n) называется сохраняющей “1”, если для наборов значений двоичных переменных (1; 1;…1) функция принимает значение f(1;1;…1)=1.
Например, f 1 (1; 1)=1, f3(1; 1)=1, f 5 (1; 1)=1 и др.
Любая функция, полученная с помощью операции суперпозиции из функций, сохраняющих “1”, сама является сохраняющей “1”. Поэтому множество функций, сохраняющих “1”, не позволяет формировать функции, не сохраняющие “1”.
Пусть есть 2 функции:
: A→B и g: D→F
Пусть область определения D функции g входит в область значений функции f (DB). Тогда можно определить новую функцию – суперпозицию (композицию, сложную функцию) функций f и g: z = g ( (x )).
Примеры. f(x)=x 2 , g(x)=e x . f:R→R, g:R→R.
(g(x))=e 2x , g((x))=.
Определение
Пусть идве функции. Тогда их композицией называется функция, определённая равенством:
Свойства композиции
Композиция ассоциативна:
Если F = id X - тождественное отображение на X , то есть
.
Если G = id Y - тождественное отображение на Y , то есть
.
Дополнительные свойства
Счетные и несчетные множества.
Два конечных множества состоят из равного числа элементов, если между этими множествами можно установить взаимно однозначное соответствие. Число элементов конечного множества – мощность множества.
Для бесконечного множества можно установить взаимно однозначное соответствие между всем множеством и его частью.
Самым простым из бесконечных множеств является множество N.
Определение. Множества А и В называются эквивалентными (АВ), если между ними можно установить взаимно однозначное соответствие.
Если эквивалентны два конечных множества, то они состоят из одного и того же числа элементов.
Если же эквивалентные между собой множества А и В произвольны, то говорят, что А и В имеют одинаковую мощность . (мощность = эквивалентность).
Для конечных множеств понятие мощности совпадает с понятием числа элементов множества.
Определение. Множество называется счетным , если можно установить взаимно однозначное соответствие между ним и множеством натуральных чисел. (Т.е. счетное множество – бесконечное, эквивалентное множеству N).
(Т.е. все элементы счетного множества можно занумеровать).
Свойства отношения равномощности.
1) АА- рефлексивность.
2) АВ, то ВА – симметричность.
3) АВ и ВС, то АС – транзитивность.
Примеры.
1) n→2n, 2,4,6,… - четные натуральные
2) n→2n-1, 1,3,5,…- нечетные натуральные.
Свойства счетных множеств .
1. Бесконечные подмножества счетного множества счетны.
Доказательство . Т.к. А – счетно, то А: х 1 ,х 2 ,… - отобразили А в N.
ВА, В: →1,→2,… - поставили каждому элементу В в соответствиенатуральное число, т.е. отобразили В в N. Следовательно В – счетно. Ч.т.д.
2. Объединение конечной (счетной) системы счетных множеств – счетно.
Примеры .
1. Множество целых чисел Z – счетно, т.к. множество Z можно представить как объединение счетных множеств А и В, где А: 0,1,2,.. и В: -1,-2,-3,…
2. Множество упорядоченных пар {(m,n): m,nZ} (т.е. (1,3)≠(3,1)).
3 (!) . Множество рациональных чисел – счетно.
Q=. Можно установить взаимно однозначное соответствие между множеством несократимых дробейQ и множеством упорядоченных пар:
Т.о. множество Q равномощно множеству {(p,q)}{(m,n)}.
Множество {(m,n)} – множество всех упорядоченных пар – счетно. Следовательно и множество {(p,q)} – счетно, а значит и Q – счетно.
Определение. Иррациональным числом называется произвольная бесконечная десятичная непериодическая дробь, т.е. 0 , 1 2 …
Множество всех десятичных дробей образуют множество вещественных (действительных) чисел.
Множество иррациональных чисел – несчетно.
Теорема 1 . Множество вещественных чисел из промежутка (0,1) – несчетное множество.
Доказательство . Допустим противное, т.е. что все числа интервала (0,1) можно занумеровать. Тогда, записывая эти числа в виде бесконечных десятичных дробей, получим последовательность:
х 1 =0,а 11 а 12 …a 1n …
x 2 =0,a 21 a 22 …a 2n …
…………………..
x n =0,a n 1 a n 2 …a nn …
……………………
Рассмотрим теперь вещественное число х=0,b 1 b 2 …b n …, где b 1 - любая цифра, отличная от а 11 , (0 и 9), b 2 - любая цифра, отличная от а 22 , (0 и 9),…, b n - любая цифра, отличная от a nn , (0 и 9).
Т.о. х(0,1), но хx i (i=1,…,n) т.к. в противном случае, b i =a ii . Пришли к противоречию. Ч.т.д.
Теорема 2. Любой промежуток вещественной оси является несчетным множеством.
Теорема 3. Множество действительных (вещественных) чисел – несчетно.
Про всякое множество, равномощное множеству вещественных чисел говорят, что оно мощности континуума (лат. continuum – непрерывное, сплошное).
Пример . Покажем, что интервал обладает мощностью континуума.
Функция у=tg x: →R отображает интервал на всю числовую прямую (график).
