Основные двоичные функции и их своства

Элементы функциональной полноты в классе двоичных функций.

Введение

Основы схем из функциональных элементов. Проблема минимизации

схемы заданной функции…………………………………………………………………..131

6.1 Сложность мультиплексора порядка ……………………………………………….136

6.2 Сложность дешифратора порядка n…………………………………………………..137

6.3 Сложность универсального многополюсника……………………………………….137

6.4 Оценка сложности функций n переменных…………………………………………138

7. Элементы теории конечных автоматов……………………………………………….142

7 .1 Ограниченно- детерминированные функции и автоматные языки. Эквивалентность…………………………………………………………………………….144

7.2 Схемы автоматов. Полнота логического базиса и задержки……………………...146

8. Элементы теории кодирования…………………………………………………………151

8.1 Критерий однозначности кодирования……………………………………………….152

8.2 Критерий префиксного кодирования Мак-Миллана……………………………….153

Литература……………………………………………………………………153

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

Все разделы снабжены большим количеством учебных примеров и задач.

Пособие создано на основе программы первого семестра курса лекций по дискретной математике, читавшегося в Волгоградском государственном университете.

Булевой функцией f(x₁ … x_n) называют функцию, аргументы которой принимают значения из множества, и значение функции также из множества {0;1}.

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

x1	…	xn	F(x1…xn)
	…		*
	…		*
…	…	…	…
	…		*

В начале выписываются двоичные наборы из n нулей и единиц. Это удобно делать в двоичной системе счисления – то есть начиная с нуля прибавлять единицу в двоичной системе счисления. На каждом наборе надо задать значение функции.

Пример табличного задания функции:

x1	x2	x3	f(x1 x1 x3)

2.Основные булевые функции и их таблицы.

0 – константа ноль;

1 – константа один;

x - тождественная;

- отрицание;

- конъюнкция (логическое умножение);

- дизъюнкция (логическое сложение);

+ - модульная сумма;

~ - эквивалентность (отрицание модульной суммы);

- следствие.

x1	x2			x1		x1 x2	x1 x2	x1+ x2	x1 ~ x2	x1 x2

3. Свойства булевых функций:

Дата добавления: 2017-01-13