Учебное пособие. — Издание 2-е, исправленное и дополненое. —
Саратов: Научная книга, 2010. — 68 с.
Настоящее учебное пособие содержит материал по общему курсу лекций
«Дискретная математика», читаемому в Саратовском госуниверситете.
Материал включает базовые знания по разделам «Элементы теории
множеств и отношений», «Функции алгебры логики», «Функции к-значной
логики ». В конце пособия показано, как функции алгебры логики
могут быть использованы для описания систем без памяти. Объем
приведенных знаний рассчитан на изучение их в течение одного
семестра в объёме 2 часа в неделю. Для студентов
механико-математического факультета и факультета компьютерных наук
и информационных технологий университета.
Предисловие.
Введение. Предмет дискретной математики.
Элементы теории множеств и отношений.
Комбинаторика.
Элементы теории отношений.
Мощность бесконечных множеств.
Функции алгебры логики.
Понятие функции алгебры логики. Задание функции алгебры логики таблицей. Элементарные функции алгебры логики.
Задание функций алгебры логики формулами. Суперпозиция функций. Алгебра логики.
Понятие существенной и фиктивной переменной. Равенство функций. Эквивалентность формул.
Функции, двойственные к заданным. Принцип двойственности.
Разложение функций алгебры логики по переменным. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы.
Логические полиномы. Теорема о представлении функций алгебры логики в виде полинома Жегалкина.
3амкнутость в Рг. Важнейшие замкнутые классы.
Понятие функциональной полноты в Р2, базис в Р2, примеры функционально полных систем.
Критерий функциональной полноты в Р2.
Следствия из критерия функциональной полноты в Р2, предполные классы в Р 2.
Функции к-значной логики.
Понятие функции k-значной логики. Теорема о числе функций k-значной логики. Элементарные функции k-значной логики.
Функциональная полнота в Р k.
Построение моделей дискретных систем без памяти с помощью функций алгебры логики на примере описания функционирования сумматора параллельного действия.
Список использованных источников.
Введение. Предмет дискретной математики.
Элементы теории множеств и отношений.
Комбинаторика.
Элементы теории отношений.
Мощность бесконечных множеств.
Функции алгебры логики.
Понятие функции алгебры логики. Задание функции алгебры логики таблицей. Элементарные функции алгебры логики.
Задание функций алгебры логики формулами. Суперпозиция функций. Алгебра логики.
Понятие существенной и фиктивной переменной. Равенство функций. Эквивалентность формул.
Функции, двойственные к заданным. Принцип двойственности.
Разложение функций алгебры логики по переменным. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы.
Логические полиномы. Теорема о представлении функций алгебры логики в виде полинома Жегалкина.
3амкнутость в Рг. Важнейшие замкнутые классы.
Понятие функциональной полноты в Р2, базис в Р2, примеры функционально полных систем.
Критерий функциональной полноты в Р2.
Следствия из критерия функциональной полноты в Р2, предполные классы в Р 2.
Функции к-значной логики.
Понятие функции k-значной логики. Теорема о числе функций k-значной логики. Элементарные функции k-значной логики.
Функциональная полнота в Р k.
Построение моделей дискретных систем без памяти с помощью функций алгебры логики на примере описания функционирования сумматора параллельного действия.
Список использованных источников.