Материал: дискретка

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

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

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

Для того чтобы система функций была полно, необходимо и достаточно чтобы она целиком не содержалась ни в одном из 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 остаточные ф-ии и эквивалентны, то соответствующие им вершины и растущим из под них поддеревья называются эквивалентными.

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