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





НазваниеОсновные способы задания двоичных функций
страница2/4
Дата публикации15.03.2015
Размер0.52 Mb.
ТипЛекция
100-bal.ru > Математика > Лекция
1   2   3   4

Определение 1.1.9 Множество двоичных наборов

  • {(a1, ... ,an) | f(a1, ... ,an) = 1}, на которых функция f принимает значение 1, называется областью истинности функции f.


    Мощность области истинности функции f называется весом функции f и обозначается ||f||.

    Очевидно, что 0 ||f|| 2n, причем равенства достигаются лишь для функций-констант 0 и 1. Если ||f|| = 2n-1, то функция f называется равновероятной.

    Для двоичных функций используются и другие способы задания, приспособленного для рассматриваемой в каждом конкретном случае задачи, которые будут рассмотрены ниже.
    §1.2 Геометрический способ задания
    1. Под геометрическим способом задания двоичной функции f(x1, ... ,xn) понимается выделение тех вершин n –мерного двоичного куба, на наборах координат которых функция принимает единичное значение. На рис. 1.2.1 приведены двоичные кубы размерностей n = 0, 1, 2, 3.


    Рис. 1.2.1
    Выделим среди множества вершин n-мерного куба те, на наборе координат которых функция принимает единичное значение. Например, функции, заданной таблицей 1.2.2 соответствует геометрическое задание, изображенное на рис. 1.2.3

    Таблица 1.2.2

    x1x2x3f

    Рис. 1.2.300010010010101101001101011011111

    Часто по геометрическому заданию функции строят граф связности вершин n-мерного куба, соответствующий данной функции. Для этого сначала отмечают те ребра, у которых оба конца выделены, т.е. соответствующие вершины лежат в области истинности. Затем все остальные ребра и вершины, не лежащие в области истинности, отбрасывают. Так функции, изображенной на рис. 1.2.3, соответствует граф связанности вида

    Рис 1.2.4

    §1.3 Задание двоичных функций формулами
    Пусть имеется некоторый класс (т.е. множество) двоичных функций K. Он может быть как конечным, так и бесконечным. Обозначим через f1, f2, ... , входящие в него функции, и пусть X = {x1, x2 ,...} множество двоичных переменных. Дадим индуктивное определение формулы над классом K.

    1. Символ переменной xi, xiX есть формула над K.

    2. Если f –обозначение некоторой функции от m переменных из класса K и Ф1, ..., Фm - формулы над K то запись Ф = f(Ф1, ... , Фm) есть формула над K


    Таким образом, формулы – это записи, в которых используются символы переменных и функций из K. Если необходимо подчеркнуть, от каких переменных зависит формула Ф, то используют обозначение Ф(x1, ... ,xn), где x1, ... ,xn - это все переменные, участвующие в задании формулы Ф.

    Установим теперь связь между формулами и двоичными функциями. Сначала заметим, что для произвольного набора значений переменных, входящих в формулу, можно, используя индуктивных характер определения, вычислять ее значение на этом наборе. Действительно, если значение формул Ф1, ..., Фm, входящих в формулу Ф = f(Ф1, ... , Фm), уже подсчитаны и равны соответственно b1, ..., bm, biF2, то значение формулы Ф равно значению функции f(b1, ..., bm). Поставим в соответствие каждой формуле Ф(x1, ... ,xn) функцию fФ(x1, ... ,xn), зависящую от тех же переменных, значения которой при всех значениях переменных совпадают со значениями формулы Ф(x1, ... ,xn).

    Легко видеть, что одна и та же формула может быть использована для записи целого ряда функций. Например, формула x1 соответствует функциям

    x1f10011

    x1x2f000010101111

    x1x2x3f00000010010001101001101111011111

    и.т.д. Поэтому естественным оказывается следующее определение.

    Определение 1.3.1 Под функциями, реализуемыми формулой Ф понимается функция fФ , а также все функции, которые получаются из fФ удалением или добавлением несущественных переменных.

    С другой стороны, одной функции может соответствовать множество различных формул. Например, рассматриваемые выше функции могут быть заданы любой из следующих формул:

    x1, x1 (x1 x2), x1 (x1 x2), x1 (x2 ), ...

    Чтобы учесть эту неоднозначность введем понятие равносильности

    формул.

    Определение 1.3.2. Две формулы Ф1 и Ф2 называются равносильными (обозначается Ф1 = Ф2), если они реализуют одинаковые множества функций.
    Замечание 1.3.3. Заметим, что для проверки равносильности формул Ф1 и Ф2 достаточно добавить к функции те переменные, которые входят в Ф2, но не входят в формулу Ф1, а к функции добавить переменные из Ф1, которые не входят в формулу Ф2, а затем сравнить таблицы полученных функций.

    Приведем два свойства, облегчающих проверку равносильности формул. Для их формулировки нам потребуется понятие подформулы.

    Определение 1.3.4. Подформулой формулы Ф называется сама формула Ф; подформулой формулы f(Ф1, ..., Фm) называется она сама, а также все подформулы формул Ф1, ..., Фm.
    Свойство 1.3.5. Если Ф1 - подформула формулы Ф, и Ф1 равносильна Ф2, то подформула Ф, полученная из Ф путем замены Ф1 на Ф2 будет равносильна формуле Ф.
    Свойство 1.3.6. Если формулы Ф1 и Ф2 равносильны, то, подставив одновременно в них вместо некоторых переменных любые формулы, получим в результате также равносильные формулы.

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

    (продолжение)

    §2.1 нормальные формы двоичных функций.

    Всюду в этом параграфе рассматриваются формулы над классом . Обозначим через функцию

    Очевидно, что тогда и только тогда, когда ,

    Определение 2.1.1 Элементарной конъюнкцией называются формулы вида , где все переменные различны. Рангом элементарной конъюнкции называется число входящих в неё переменных.

    Непосредственно из определения 2.1.1 получаем, что элементарная конъюнкция принимает единичное значение в том и только том случае, когда , . Этот факт запомним как свойство элементарных конъюнкций.
    Определение 2.1.2. Дизъюнктивной нормальной формой (ДНФ) называется формула вида , где дизъюнкция берется по некоторым наборам , и , .

    Обозначим через функцию, полученную из функции фиксацией первых переменных значениями . Из следующей теоремы вытекает, что любую двоичную функцию можно задать с помощью ДНФ.
    Теорема 2.1.3 (о разложении функции). При любом , , двоичную функцию можно представить в виде:

    (2.1.4)

    Доказательство. Покажем, что функция, стоящая в левой и правой части равенства 2.1.4 , принимает одинаковое значение при одинаковых значениях переменной. Пусть . Тогда в силу свойств элементарных конъюнкций значение функции из правой части равно = . Теорема доказана.
    Следствие 2.1.5

    (2.1.6)

    Доказательство. Следует из теоремы 2.1.3, если положить
    Следствие 2.1.7

    (2.1.8)

    Доказательство. Вытекает из следствия 2.1.5 при перенумерации переменных.

    Замечание 2.1.9. Разложение (2.1.6) называется разложением Шеннона.
    Следствие 2.1.10

    (2.1.11)

    Доказательство. Следует из теоремы 2.1.3 , если положить .
    Замечание 2.1.12. В разложении 2.1.11 можно опустить все элементарные конъюнкции, которым соответствуют нулевые значения функций. Полученная в результате формула имеет вид :

    (2.1.13)

    Определение 2.1.14. Равенство (2.1.13) называется совершенной ДНФ (СДНФ) функции .
    Как построить СДНФ функции ?

    СДНФ двоичной функции легко построить по ее табличному заданию. С этой целью для каждого набора аргументов , на котором функция принимает единичное значение, строится элементарная конъюнкция ранга по правилу:

    (2.1.15)

    Затем берется дизъюнкция всех построенных элементарных конъюнкций. Приведём пример:

    Пример 2.1.16. Пусть функция задана следующей таблицей:




    0 0 0

    0 0 1

    0 1 0

    0 1 1

    1 0 0

    1 0 1

    1 1 0

    1 1 10

    1

    0

    1

    0

    0

    11
    Таблица 2.1.17

    Построим для неё СДНФ:









    Поэтому:



    Заметим, что СДНФ является частным случаем ДНФ. В ней все элементарные конъюнкции имеют ранг .

    Отличительной особенностью СДНФ является то, что она однозначно определяется по функции . Действительно, все элементарные конъюнкции в ней находятся во взаимно-однозначном соответствии с векторами из области истинности функции: .

    В отличие от СДНФ, ДНФ не однозначно соответствует функции. Так функция из предыдущего примера может быть записана в виде следующих ДНФ:



    Аналогично ДНФ вводятся конъюктивные нормальные формы (КНФ). Они являются конъюнкциями элементарных дизъюнкций и имеют вид , где конъюнкция берется по некоторым наборам , , . Как и в случае СДНФ можно показать, что функции соответствует однозначно определенная КНФ( называемая совершенная КНФ), в которой все элементарные дизъюнкции имеют ранг . Её можно получить из СДНФ функции : с помощью соотношений: , . Из свойств 1.3.5 и 1.3.6 равносильных формул имеем :

    = = .

    СКНФ функции легко строится по её табличному зданию. Для функции , заданной таблицей 2.1.17, получаем:









    Поэтому


    §2.2 Многочлен Жегалкина и действительный

    многочлен двоичной функции.

    Будем рассматривать формулы над классом
    Определение 2.2.1. Многочленом Жегалкина (приведенным многочленом) называется представление двоичной функции формулой вида:

    , где .
    Теорема 2.2.2. Для каждой двоичной функции существует единственный многочлен Жегалкина.

    Доказательство. Покажем, что по таблице функции однозначно определяются коэффициенты её многочлена Жегалкина. Воспользуемся методом неопределенных коэффициентов. Будем последовательно вычислять значения искомого многочлена на наборе из одних нулей, затем на наборе с одной единицей, затем – с двумя, и т.д. В результате получим систему:



    Из первого уравнения находим , из второго ,…, из - ,

    из - ,…, из последнего . Теорема доказана.

    Определение 2.2.3. Конъюнкции , входящие в многочлен Жегалкина, называются одночленами. Степенью одночлена называется число входящих в него переменных (ранг конъюнкции). Степенью нелинейности (порядком) многочлена Жегалкина функции (обозначается ) называют максимальную из степеней входящих в него многочленов.

    Многочлен Жегалкина можно вычислять исходя из ДНФ или СДНФ

    функции , выразив операции дизъюнкция и отрицание через операции конъюнкция и сложение по модулю два :



    Пример 2.2.4.



    =

    =

    Двоичные функции можно также задавать многочленами, в которых используются операции сложения, вычитания и умножения действительных чисел. Так, непосредственно проверкой убеждаемся, что



    Поскольку каждую двоичную функцию можно задать своим многочленом Жегалкина, СДНФ или СКНФ, то ,заменив все используемые в этих формулах операции на их выражения (по приведенным выше формулам) и раскрыв затем скобки получаем для всякой двоичной функции эквивалентную запись в виде некоторого действительного многочлена. Вместе с тем, можно заметить, что такая запись неоднозначна. Например , функцию можно представить действительными многочленами вида :



    Перечисленные многочлены при и принимают значения 1 и 0 соответственно. Все многочлены в этом примере обладают той особенностью, что они содержат степени переменной , в то же время для двоичных переменных очевидны равенства:



    Если отказаться от использования переменных в степенях выше первой , то неоднозначность представления двоичных функций можно исключить.

    Теорема 2.2.4. Любая двоичная функция однозначно представляется в виде следующего действительного многочлена :



    все коэффициенты ,которого являются целыми числами.

    Доказательство. Полностью аналогично тому, которое было приведено в теореме 2.2.2. Необходимо только заменить операцию « » на «+».

    Ниже, говоря «действительный многочлен», будем всюду иметь в виду определенный в теореме 2.2.4 многочлен
    § 2.3. Теорема о разложении в ряд Фурье.
    Сопоставим каждому двоичному вектору линейную двоичную функцию ( сокращенно ( )), и определим функции :



    Например, векторам и соответствуют из функции



    соответственно. Всего имеется функций вида . Как показывает следующая лемма, они образуют ортогональную систему функций.

    Лемма 2.3.1. Для любых векторов справедливы равенства

    Доказательство. Сначала заметим, что

    Поскольку линейная функция при принимает значение 0 ровно . Теперь

    . Отсюда и следует утверждение леммы.
    Теорема 2.3.2. (о разложении в ряд Фурье). Для всякой двоичной функции имеется единственное разложение вида : , где коэффициенты являются рациональными числами. При этом значения коэффициентов определяются равенствами

    .

    Доказательство. Докажем сначала, что указанный ряд представляет функцию . Имеем

    Поскольку в последней сумме будет только одно нулевое слагаемое при y=x.

    Покажем теперь, что коэффициенты однозначно определяются по функции . Предположим, существует другое разложение . Тогда . Домножив обе части этого равенства на для и просуммировав по полученные равенства, получаем :

    Отсюда . Так как b-произвольный вектор из получаем требуемое утверждение.

    Определение 2.3.2. Коэффициенты , , называется коэффициентами Фурье функции .
    Лекция №3

    Полнота и замкнутость. Критерий полноты системы. Функционально полные системы. Замкнутые классы булевых функций.
    §3.1 Полнота и замкнутость. Функционально полные системы.
    Определение 3.1.1. Для произвольного класса системы двоичных функций множество всех двоичных функций, представимых формулами ,над , называется замыканием класса (системы) функций и обозначается через .

    Имеют место следующие свойства замыкания:

    Свойство 3.1.2. .

    Свойство 3.1.3.

    Свойство 3.1.4.

    Обозначим через - множество всех двоичных функций от переменных, а через множество всех двоичных функций (от произвольного числа переменных).

    Определение 3.1.5. Система функций называется полной, если .
    Утверждение 3.1.6. Система функций является полной системой функций.

    Доказательство. Очевидно, что элементарная конъюнкция является формулой над . Отсюда следует, что дизъюнкция любого числа элементарных конъюнкций является формулой над . Отсюда и из равенства (2.1.13) следует, что любая функция ,представима над формулой . Следовательно, .
    Утверждение 3.1.7. Система функций является полной системой функций.

    Доказательство. Очевидно, что , из равенства следует, что . Отсюда и из свойств 3.1.3 и 3.1.4 имеем , т.е. . Таким образом, показано, что и . Полученные включения означают, что
    Утверждение 3.1.8. Система функций является полной системой функций.

    Доказательство. Очевидно, что , из равенства следует, что . Отсюда и из свойств 3.1.3 и 3.1.4 имеем , т.е. . Таким образом, показано, что и . Полученные включения означают, что

    Утверждение 3.1.9. Система функций является полной системой функций, где - двоичная функция, называемая штрихом Шеффера, задается таблицей

    1. 0

    2. 1

    3. 0

    1 1 1

    1

    1

    0 Доказательство. Очевидно, что . Из равенств:



    и



    следует, что . Далее доказательство текстуально аналогично доказательству утверждения 3.1.8 при подстановке вместо

    Утверждение 3.1.10. Система функций , является полной системой функций.

    Доказательство. Очевидно, что . Из равенства следует, что . Далее доказательство текстуально аналогично доказательству утверждения 3.1.8 при подстановке вместо
    Утверждение 3.1.11. Система функций , является полной системой функций, где - двоичная функция, называемая стрелкой Пирса, задается таблицей:

    1. 0

    2. 1

    3. 0

    1 1 1

    0

    0

    0Доказательство. Очевидно, что . Из равенств : и следует , что . Далее доказательство текстуально аналогично доказательству утверждения 3.1.8 при подстановке вместо и вместо
    Определение 3.1.12. Каждая двоичная функция сама одна образующая полную систему называется Шефферовой функцией.
    Пример 3.1.13. Функция является Шефферовой функцией. Это следует из утверждения 3.1.9.

    Пример 3.1.14. Функция является Шефферовой функцией. Это следует из утверждения 3.1.11.

    Примеры Шефферовых функций от большего числа переменных будут приведены ниже, после изложения критерия полноты системы двоичных функций.
    §3.2. Замкнутые классы булевых функций.
    Определение 3.2.1. Класс булевых функций называется замкнутым, если он совпадает со своим замыканием, т.е. .

    Замечание 3.2.2 Полное описание всех замкнутых классов было дано американским математиком Э. Постом. В частности, он доказал, что множество всех замкнутых классов булевых функций счетно и в каждом замкнутом классе можно выделить конечную подсистему , порождающую , т.е. имеющую своим замыканием класс , т.е. .

    Определение 3.2.3. Булева функция называется функцией, сохраняющей константу 0, если .

    Класс всех булевых функцией, сохраняющих константу 0, обозначим .

    Определение 3.2.4. Булева функция называется функцией, сохраняющей константу 1, если .

    Класс всех булевых функцией, сохраняющих константу 1, обозначим .

    Определение 3.2.5. Булева функция называется линейной, если , такие ,что .

    Класс всех булевых линейных функций обозначим через .

    Определение 3.2.6. Булева функция называется аффинной функцией, если , такие, что .

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

    Определение 3.2.7. Булева функция называется самодвойственной функцией, если (3.2.8)

    Класс всех булевых самодвойственных функций обозначим через S.

    Далее определим понятие монотонной функции. Для этого нам необходимы некоторые дополнительные сведения. Изложим их. На множестве введем отношение , положив для наборов и : , где отношение на понимается как неравенство на множестве чисел {0,1}.

    Несложно доказать, то отношение рефлексивно, транзитивно и антисимметрично, т.е. является отношением частичного порядка.

    Определение 3.2.9. Булева функция называется монотонно возрастающей, или монотонной, если для любых наборов выполняется условие:

    Замечание 3.2.10. Нульместные функции 0 и 1 также естественно считать монотонными.

    Класс всех булевых монотонных функций обозначим через М.

    Утверждение 3.2.11. Классы булевых функций и являются замкнутыми классами булевых функций.

    Для доказательства данного утверждения нам необходимо определить понятие ранга формулы над классом .

    Определение 3.2.12. Число всех символов функций из , встречающихся в формуле над , называется рангом формулы и обозначается через .

    Замечание 3.2.13. Понятие ранга формулы над классом не следует путать с понятие ранга элементарной конъюнкции из определения 2.1.1.

    Доказательство утверждения 3.2.11. Замкнутость перечисленных в утверждении 3.2.11 шести классов функций доказывается по одной и той же схеме. Проделаем это для какого-нибудь одного класса, например S.

    Согласно определениям замыкания (определение 3.1.1) и замкнутого класса (определение 3.2.1) нам необходимо доказать, что любая функция, представимая формулой над S, принадлежит S. Докажем это индукцией по рангу формулы А, представляющей функцию .

    Если , то , и утверждение очевидно, так как .

    Пусть утверждение верно для всех , таких что , где .

    Докажем, что утверждение верно и при .

    Если , то А имеет вид: , где и - формулы меньших рангов, чем , т.е. . По предположению индукции формулы представляют булевы функции . Тогда для любых имеем:



    Следовательно , удовлетворяет условию (3.2.8), т.е
    §3.3 Критерий полноты системы булевых функций.
    Теорема 3.3.1. Система булевых функций полна тогда и только тогда, когда она содержит хотя бы по одной функции каждого из следующих классов :

    , , , , . (3.3.2)

    (без доказательства).
    Пример 3.3.3. Пусть функция задана таблицей 3.3.4




    0 0 0

    0 0 1

    0 1 0

    0 1 1

    1 0 0

    1 0 1

    1 1 0

    1 1 11

    0

    0

    0

    0

    0

    00



    Таблица 3.3.4


    Показать, что - Шефферова функция, т.е. - полная система, т.е. . Выразить и формулами над К.

    Решение:





    , но не

    .

    Чтобы выяснить вопрос о принадлежности классу , представим многочленом Жегалкина:

    Итак, все условия теоремы 3.3.1 выполнены. Следовательно -полная система, т.е. - Шефферова функция. Теперь решим вторую часть примера. Так как , то очевидно , .
    Лекция №4.

    §4.1. Псевдобулевы функции.

    Пусть Р- произвольное поле. Элементы будем рассматривать как нуль и единицу поля .

    Определение 4.1.1. Псевдобулевой функцией от переменных, или -местной псевдобулевой функцией, над полем Р при называется любое отображение в Р. Нуль-местными псевдобулевыми функциями над Р называются все элементы поля Р.

    Множество всех пседобулевых функций от переменных над полем Р обозначим через . В частности, при класс совпадает с классом булевых функций . В других случаях эти классы различны и если условиться , псевдобулеву функцию со значением из считать булевой, то : .

    Множество функций относительно естественным образом определяемых операций сложения функций и умножения функций на элементы из Р образуют линейное пространство над полем Р.

    Рассмотрим систему функций:

    (4.1.2)

    ,где -символ Кронекера, т.е. :

    Утверждение 4.1.3. Система функций (4.1.2) является базисом пространства .

    Доказательство. Очевидно, что система (4.1.2) – линейно независимая система. Далее пусть - произвольная функция из . Тогда очевидно, что :

    (4.1.4)

    Отсюда следует, что (4.1.2) – базис пространства .

    Замечание 4.1.5. Если , то - булева функция и разложение (4.1.4) функции совпадает с разложением , полученным заменой в её СДНФ операции на .

    Замечание 4.1.6. Если , то система функций :

    (4.1.7)

    является базисом пространства . Это следует из теоремы 2.2.4 об однозначном представлении булевых функций многочленами Жегалкина. В этом случае представление функции многочленом Жегалкина есть (4.1.7).

    Замечание 4.1.8. Представление булевых функций через базисы пространства сопряжено со многими трудностями. Вот две из них :

    1. Непростым является вопрос об описании базисов пространства ;

    2. Если даже имеется система функций являющаяся базисом пространства, то в общем случае сложным является вопрос о нахождении коэффициентов в разложении булевой функции по указанному базису.

    Замечание 4.1.9. В решении вопроса об описании базисов пространства иногда оказывается полезным переход от пространства к пространству векторов-столбцов длинны над полем Р. Сопоставим каждой функции вектор столбец значений этой функции. В итоге получаем отображение пространства в пространство . Нетрудно видеть, что есть изоморфизм пространств, а поэтому система функций является базисом пространства тогда и только тогда, когда матрица является невырожденной .
    § 4.2. Функции к-значной логики.
    Пусть , где .

    Определение 4.2.1. Функцией k-значной логики, или k-значной функцией, от переменных при называется произвольное отображение k-значными функциями от 0 переменных называются функции- константы 0,1,…,к-1.

    Обозначим через и множества всех k-значных функций и k-значных функций от переменных.

    При изучении k-значных функций используются многие из терминов и обозначений, введенных при изучении булевых функций. В частности, аналогичным образом определяются равенство функций, существенные и несущественные переменные, функции от переменных, тождественно равны константам 0,1,…,к-1, подфункции и т.д.

    Так как множество конечно, то k-значную функцию от переменных можно задать таблицей её значений на всех наборах (или векторах) из . При этом условимся записывать их в порядке возрастания как числа в конечной системе исчисления. Непосредственно из табличного значения видно, что различных k-значных функций равно . При табличное задание k-значных функций практически еще более трудно осуществимо.

    В связи с этим важным вопросом является вопрос о разработке аналитических способов k-значных функций.

    Множество можно рассматривать как кольцо вычетов по модулю , и потому можно считать определенными на операции сложения и умножения по модулю . Будем обозначать эти операции при теми же значками , что и операции над числами. Используя эти операции и функции-константы можно построить кольцо многочленов от переменных . Каждый многочлен из этого кольца представляет k-значную функцию от переменный . При простом , когда - есть поле, многочленами представляются все k-значные функции. При составном - это не так.

    Используя операции сложения и умножения, а так же элементарные функции



    можно получить представление k-значной функции сходное с совершенной дизъюнктивной нормальной формой для случая .

    (4.2.2)

    Другими, часто используемыми операциями на являются аналоги дизъюнкции, конъюнкции и отрицания :

    .

    Для k-значных функций, как и в двоичном случае, можно ввести понятия операции, представления функций формулами над заданной системой функций, замыкания, замкнутой и полной системы функций и.т.д. Приведем примеры полных систем k-значных функций.

    1. Из представления (4.2.2) следует, что полной является система функций

    2. Так как в разложении (4.2.2) операцию сложения можно заменить на дизъюнкцию( выбор максимума), то полной является также система функций

    3. Наряду с разложением (4.2.2) имеет место еще один аналог совершенной дизъюнктивной нормальной формы функции , где . Отсюда следует, что полной является система функций .

    4. Система функций является полной системой функций.

    Доказательство. С помощью суперпозиции из функции легко получить функции . Из них получим константу , а поэтому все функции константы . Теперь нетрудно получить функции :

    .

    Как следует из примера 3, остается построить функцию , т.е. Для этого сначала построим функции

    Теперь из них можно получить функции и .

    1. Аналогично функции Шеффера в k-значной логике является функция Вебба , которая одна образует систему, т.е. система является ????????

    Доказательство. Используя при имеем . Далее получаем :



    А так как . Отсюда имеем, что - полная система функций.
    Утверждение 4.2.3. Все k-значные функции представляются многочленами над в том и только том случае, когда к- простое число, т.е. -поле.

    (без доказательства).

    Утверждение 4.2.4. (критерий полноты- Критерий ?????Слунецкого??).

    Пусть система k-значных функций K содержит се функции одной переменной, причем . Тогда для полноты системы К необходимо и достаточно, чтобы К содержала функцию, существенно зависящую по меньшей мере от двух переменных и принимающую все значений из .
  • 1   2   3   4

    Похожие:

    Основные способы задания двоичных функций icon1. Функции, их свойства и графики Числовая функция. Способы задания...
    ...
    Основные способы задания двоичных функций iconУрок по теме «Модуль действительного числа»
    Здравствуйте, ребята! Сегодня на уроке мы постараемся повторить всё, что мы узнали о модуле числа, основные способы решения уравнений,...
    Основные способы задания двоичных функций iconКонспект урока возрастание и убывание функций. Экстремумы. (Тема...
    Цель урока: ввести понятия возрастания и убывания функций, экстремумов функций, научить применять эти понятия при чтении и построении...
    Основные способы задания двоичных функций iconРешение д Общий член последовательности имеет вид
    В этой главе вводится понятие числовой последовательности, изучаются основные способы задания числовой последовательности, главное...
    Основные способы задания двоичных функций iconПриложение №2 Вопросы к промежуточной аттестации
    Хирургическая обработка рук различными способами. Способы обработки операционного поля, хирургического инструментария, шовного материала....
    Основные способы задания двоичных функций icon2. место дисциплины в структуре образовательной программы
    Для реализации поставленных целей в курсе рассматриваются основные положения оптимизации налогов, изучаются методы налогового планирования,...
    Основные способы задания двоичных функций icon“ Альтернативные источники энергии”
    Также описаны основные группы рисков, характерные, на современном этапе, для мировой экономики. Приведены основные проблемы развития...
    Основные способы задания двоичных функций iconУрок изучения нового материала
    Цель. Закрепить определение и свойства тригонометрических функций. Назначение тригонометрических функций, необходимость их возникновения....
    Основные способы задания двоичных функций iconРадиофизический факультет
    Содержание дисциплины «Теория функций комплексного переменного» направлено на ознакомление студентов с теорией аналитических функций,...
    Основные способы задания двоичных функций iconПрограмма по формированию навыков безопасного поведения на дорогах...
    Цель: формирование знаний о конфликте и его функций. Определение путей предупреждения конфликтных ситуаций и способы их решения,...
    Основные способы задания двоичных функций iconОбщая трудоемкость дисциплины
    Содержание дисциплины «Теория функций комплексного переменного» направлено на ознакомление студентов с теорией аналитических функций,...
    Основные способы задания двоичных функций iconРасчёт коэффициента передачи по току низкочастотного фильтра
    В данной курсовой работе рассматриваются методы анализа линейных цепей (классификация методов, их применение) и способы их линеаризации,...
    Основные способы задания двоичных функций iconТ. Эдисон. Цель
    Тема Дискретная случайная величина, способы ее задания. Числовые характеристики. Функция распределения и ее свойства. 19
    Основные способы задания двоичных функций iconРабочая программа дисциплины
    Тема Дискретная случайная величина, способы ее задания. Числовые характеристики. Функция распределения и ее свойства. 19
    Основные способы задания двоичных функций iconЦуканова Ольга Анатольевна
    Тема Дискретная случайная величина, способы ее задания. Числовые характеристики. Функция распределения и ее свойства. 19
    Основные способы задания двоичных функций iconУрок по теме: «Математическое моделирование»
    Тема Дискретная случайная величина, способы ее задания. Числовые характеристики. Функция распределения и ее свойства. 19


    Школьные материалы


    При копировании материала укажите ссылку © 2013
    контакты
    100-bal.ru
    Поиск