Монотонные функции

Монотонные функции.

Опр. из того что включено в

Примеры:

1. 0,1,x, ,

2.

Способы выявления монотонности

1. Эквивалентные преобразования. Если функция содержит только конъюнкцию и дизъюнкцию, то она монотонна.

2. С помощью таблицы истинности.

М – замкнутый класс

Док-во. Надо доказать: суперпозиция класса М совпадает с самим классом М.

Рассмотрим функцию - суперпозицию монотонных функций. Т. е. таким образом, надо показать, что если то и

Пусть G определена на наборе переменных

Тогда будет определена на наборе И т. д.

будет определена на наборе

Возьмем две оценки списка переменных и обозначим их и

Причем:

Аналогичным образом получим наборыи,и … и

Кроме того,,....

Таким образом в силу того что функции F монотонные и получим:

Тогда если составить наборы из соответствующих наборов функций то будет иметь место следующее соотношение

А в силу того что функция F монотонная получим что

Таким образом

Таким образом в силу произвольности выбора функции F мы доказали что суперпозиция класса М совпадает с самим классом М.

Лемма о несамодвойственной функции.

Если функция то из нее путем подстановки и можно получить несамодвойственную функцию одного переменного – константу

Док-во.

Если , то двоичный набор

Рассмотрим подобранные функции которые конструируются следующим образом

Рассмотрим

Рассмотрим значение при и

Если ,

Если , то

Если , то

Если , то

Таким образом –константа.

Лемма о немонотонной функции

Если функция То из нее путем подстановки можно получить немонотонную функцию одного переменного -

Док-во

1 этап. Покажем что если , то два двоичных набора и

и

1 случай доказывать ничего не надо

2 случай это значит, что

Покажем что можно выбрать другие наборы и они будут соседними

Между и Мы можем взять промежуточных набора, причем таких что

и

Значит хотя бы для одной пары промежуточных наборов ( обозначим их и ) будет выполняться неравенство:

Пусть данные наборы имеют соседство по i-ой координате

2этап

Рассмотрим функцию, которая конструируется следующим образом

Рассмотрим значения при и

Учитывая, что мы работаем с булевыми функциями, это становится возможным только если

а

Следовательно .

Лемма о нелинейной функции

Если функция То из нее путем подстановки можно получить не линейную функцию -

Док-во

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

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

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

Выберем такой двоичный набор на котором

Пусть функция

Рассмотрим функцию которая конструируется следующим образом

Подставим в функцию Формулу для функции

Лемма доказана.

Таблица Поста. Алгоритм построения базисов

Дана система функций

Таблица Поста:

На пересечении класса и функций ставится “+” если функция принадлежит классу. Иначе – “-”

Критерий Поста:

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

Алгоритм построения базисов.

1. Построить таблицу Поста.

2. По таблице Поста составить КНФ, в которой элементарные дизъюнкции соответствуют столбцам таблицы и включены в качестве дизъюнктивных членов символы тех функций, которые не входят в класс, соответствующий столбцу.

3. Применяя дистрибутивный закон, законы идемпотентности и поглощения привести КНФ к ДНФ

К-значная логика. Определения. Способы задания. Элементарные функции.

– булевая функция

– функция k-значной логики.

Обозначим

Опр. функция k-значной логики – это произвольная функция, область определения которой – декартово произведение , а область значения – само .

Способы задания

1. таблица истинности

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

Элементарные функции.

1. Константы

2. Отрицание Поста (циклический сдвиг) ( сложение осуществляется по модулю k)

3. Отрицание Лукасевича ( операция зеркального отражения)

4. Характеристическая функция 1 рода

5. Характеристическая функция 2 рода

6. Функция (первое обобщение конъюнкции)

7. Второе обобщение конъюнкции

8. Функция (обобщение дизъюнкции)

9. Сложение по модулю k

10. Импликация

11. Усеченная разность

12. Разность по модулю

13. Функция Вебба

Первая и вторая форма функций

Первая форма

==

Вторая форма

Детерминированные функции

Опр. Функция Называется детерминированной, если каково бы ни было число m и каковы бы ни были последовательности и такие что:

Значенияи функции F, где и, представляют собой последовательности, у которых тоже совпадают первые m членов, т. е.:

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

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

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

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

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

Опр. Бесконечное ориентированное корневое дерево - это дерево удовлетворяющее условиям:

1. из каждой вершины выходит ровно N дуг.

2. в каждую вершину входит только одна дуга. В корень ни одной.

3. каждой дуге приписана некоторая буква алфавита А, причем разным дугам из одной вершины разные буквы.

Деревья

Опр. Два поддерева с корнями И Исходного дерева называются эквивалентными, если

Опр. Число r классов эквивалентности, на которое разбивается множество всех поддеревьев данного дерева называется весом дерева и соответственно весом детерминированной функции.

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

В противном случае – они разные.

Опр. Пусть у нас есть две детерминированные функции

Если (конечное число) такое что

То Называется остаточной функцией для , порожденная словом

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

Опр. Функция называется ограниченно детерминированной, если она имеет конечное число попарно различных состояний.

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

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

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

Опр. Функция наз-ся огр-дет если она имеет конечный вес.

Способы задания

1 способ.

Усеченное дерево. Для любой усеченной детермин. функции соответствующее ей бесконечное информативное дерево можно свести к конечному. Для этого надо :

1. Перенумеруем классы эквивалентности таким образом что бы класс в которое попадет исходное дерево имело № 0

2. Берем произвольную вершину и присваиваем ей № q класса в которое попадает дерево с корнем в вершине

3. Берем произвольную ветвь

Т. к ф-ия огр.-дет. то найдется такое число j что ( то есть номера начнут повторяться) и для всех пар так что номер о является наименьшим

4. Проведем усечение ветви сохранив ее нач-ый отрезок до вершины

2 способ.

Выписываем номера всех состояний и расписываем каждое из них. После того как состояние расписано оно зачеркивается.

Расписать состояние значит указать состояние в котором можно попасть из него

Диаграмма Мура

Если в усеченном дереве отождествить вершины с одинаковыми номерами то получим диаграмму мура.

Для построения Д. М необходимо осущ. следующие действия:

1. Наносим произ-ым образом на плоскость сост. в виде точек, нумеруем их №, соотв. № состояний. Корневая вершина получается «*».

2. Идем от корня по усеченному дереву и каждую дугу дерева отображаем на диаграмме. При этом важно указывать направление.

Диаграмма Мура.

3. способ Канонические уравнения

Пусть F - огр. дет ф-ия. Рассмотрим диаграмму мура.

Предположим что в момент времени (t-1) мы нах. в вершине q(t-1) тогда при поступлении в момент времени t числа (t) мы переместимся в диаграмме по ребру (t) выходящему из вершины q (t) при этом получим выходное значение (t) и перейдем в вершину q (t)

Т. о величины однозначно опр. величины

Введенные величины и будем называть соотв. входной и выходной величинами, а q состоянием.

Пусть переменные X Y Q таковы что : Х описывает значение входной величины,Q описывает состояние q и Y опис. значение выходной величины .

Получаем что с помощью Д. М можно создать две функции.

F: AQB функция выходов

G: AQQ функция переходов

На основании приведенных выше рассуждений мы приходим к след. уравнениям.

(1)

Где

Это канон. урав. с в векторной форме с начальным условием q,

1. способ Канонические таблицы

2. способ Аналитические задания.

3. способ. Бесконечное информ. дерево.

Вместо канон. урав.(1) бывает удобно рассматривать канон. урав. в которых функция выходов и переходов явл. формулами K-значной логики. Для получения соотв. представления ф-ии F алфавиты A, B, Q кодируется векторами (наборами) координаты (компоненты которых пренад. множеству

Если F – ограничено-детерм. ф-ия и , , то для кодирования букв из алфавита A, B, Q достаточно взять векторы имеющие длины n, m, r соответственно.

Система (1) преобразуется тогда в следующую

(2)

Используются такие векторная запись систем аналогичных системе (2) При такой записи система (2) примет вид

(3)

Ф-ии и в системе (2) явл-ся частичными, т. е не всюду определенными.

Обычно их доопределяют так. чтобы правые части уравнения в (2) имели по возможности более простой вид.

Операции над детерминированными функциями.

Пусть детерминированная ф-ия F задана системой (2) и каждая из функций и всюду определенные функции к-значной логики.

Будем рассматривать ф-ию f как элемент мн-ва

Обозначим схему реализующую ф-ию f.

Схемубудем изображать в виде прямоугольника с n входами и m выходами. Входы изображаются в виде стрелок исходящих из входных полюсов. Выходы - стрелки из выходных. Полюса- кружочки.

Если m=1 то схемуреализующую ф-ию. f иногда изображают в виде треугольникас n входными и одним выходным полюсами.

Считаем что в каждый момент времени t=1, 2 на i-ый входпоступает входной символ а на j-ом выходе выдается значение.

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

АССОЦИАТИВНОЕ ИСЧИСЛЕНИЕ - совокупность всех слов в некотором алфавите вместе с какой нить конеч системой допустимых знач.

СМЕЖНЫЕ СЛОВА - если слово R преобразовано к слову S путем однократного применения подстановки.

ДЕДУКТИВНАЯ ЦЕПОЧКА - послед. слов r-1 ... r-n таких что любая пара r-i и r-i+1 явл. смежными.

ЭКВИВАЛЕНТНЫЕ СЛОВА, если сущ. цепочйа, ведущая от R к S.

ФОРМАЛЬНЫЕ ТЕОРИИ:

1)задан язык теорий,

2)опр понятие формулы,

3)задано мн-во аксиом,

4)опр правила вывода в теориях.

ВЫВОД В ТЕОРИИ T - любая послед формул А-1 ... А-n таких что любая ф-ла А-i либо аксиома, либо следствие нек пред ф-л в соотв с одним из правил вывода.

МАШИНА ТЬЮРИНГА - абстрактное устройство, состоящее из бесконечной ленты, считывающей (и печатающей) головки и управляющего устройства или конеч. автомата

КОНФИГУРАЦИЯ МАШИНЫ В МОМЕНТ t - слово а-j1 ... а-jl-1 а-ji а-jl... а-js

КОМАНДЫ:

1)состояние, в котором находится машина в данный момент времени;

2)значение в ячейке, которую обозревает считывающая головка;

3)сост., в которое перейдет машина после выполнения команды;

4)значение, записываемое в ячейку после выполнения команды;

5)указание движения головки в ту или иную сторону.

ПРОГРАММА-список всех пятерок, опр. работу машины Т.

Если в прогр. для машины Т. нет команды для пары (g-итое, а-житое) или новое сост. g-итое-житое является ЗАКЛЮЧИТЕЛЬНЫМ, то машина ПРЕКРАЩАЕТ РАБОТУ, а результирующая конфигурация - ЗАКЛЮЧИТЕЛЬНАЯ

СЛОВО - Р=а-житая1, а-житая2, ... , а-житая-р, ..., а-житая-s, где а-житая-р - символ, содержащийся в ячейке с-пэтая

СЛОВО - конфигурация машины в момент t.

МАШИНА Т. ВЫЧИСЛЯЕТ ФУНКЦИЮ, если ф-ция вычислима по Тьюрингу с помощью машины Т.

КЛАСС ВСЕХ ПРИМЕТИВНО РЕКУРСИВНЫХ ФУНКЦИЙ - мн-во всех ф-ций, к-ые могут быть получены из простейших ф-ций с помощью операций суперпозиции и примитивной рекурсии.

КЛАСС ЧАСТИЧНО РЕКУРСИВНЫХ ФУНКЦИЙ - //-// и минимизации.

КЛАСС ВСЕХ ОБЩЕ РЕКУРСИВНЫФ ФУНКЦИЙ - мн-во всех всюду опред. частично рекурс. ф-ций.