Основные законы булевой алгебры и преобразование

СОДЕРЖАНИЕ

Предисловие……………………………………………………………………..

ДИСКРЕТНАЯ МАТЕМАТИКА …………………………………………….

1. Множества и алгебраические системы. Булевы алгебры ………...........

1.1. Основные понятия теории множеств………………………………….

1.2. Основные операции над множествами…………………………..........

1.3. Декартово произведение множеств……………………………………

1.4. Соответствия и функции………………………………………….........

1.5. Отношения………………………………………………………………

1.6. Использование множеств в языке Паскаль…………………………...

2. Элементы общей алгебры ………………………………………………….

2.1. Операции на множествах………………………………………………

2.2. Группа подстановок Галуа……………………………………………..

2.3. Алгебра множеств (алгебра Кантора)…………………………………

2.4. Алгебраические системы. Решетки……………………………………

2.5. Задание множеств конституентами……………………………………

2.6. Решение уравнений в алгебре множеств……………………………...

3. Элементы комбинаторики ……………………………………………........

3.1. Комбинаторные вычисления…………………………………………..

3.2. Основные понятия комбинаторики……………………………………

3.3. Размещения……………………………………………………………...

3.4. Перестановки……………………………………………………………

3.5. Сочетания………………………………………………………………..

3.6. Треугольник Паскаля…………………………………………………...

3.7. Бином Ньютона……………………………………………………........

3.8. Решение комбинаторных уравнений………………………………….

 

4. Основные понятия теории графов ………………………………………...

4.1. Способы задания графов……………………………………………….

4.2. Характеристики графов………………………………………………...

4.3. Понятие о задачах на графах…………………………………………..

4.4. Задача о Ханойской башне……………………………………………

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

5.1. Понятие о переключательных функциях……………………………...

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

5.3. Основные бинарные логические операции…………………………...

5.4. Понятие о переключательных схемах и технической

  реализации переключательных функций………………………........

5.5. Использование логических операций в теории графов……………...

Элементарные двоичные переключательные функции

и функциональная полнота систем переключательных

функций ……………………………………………………………………….

6.1. Элементарные переключательные функции одной переменной........

6.2. Элементарные переключательные (логические) функции

  двух переменных………………………………………………………..

6.3. Функциональная полнота систем переключательных функций…….

6.4. Базисы представления переключательных функций…………………

6.5. Пример анализа и определения свойств ПФ, заданной

        десятичным номером………………………….………………………..

Основные законы булевой алгебры и преобразование

переключательных функций ………………………………………………

7.1. Основные законы булевой алгебры переключательных функций…..

7.2. Равносильные преобразования. Упрощение формул

  алгебры переключательных функций…………………………………

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

8. Минимизация переключательных функций …………………………….

8.1. Цель минимизации переключательных функций…………………….

8.2. Основные понятия и определения, используемые

  при минимизации……………………………………………………….

8.3. Аналитические методы минимизации переключательных

  функций………………………………………………………………….

8.4. Минимизация переключательных функций по картам Карно………

8.5. Метод поразрядного сравнения рабочих и запрещенных наборов…

8.6. Минимизация переключательных функций, заданных

  в базисе { , И, НЕ}…………………………………………………….

8.7. Минимизация систем переключательных функций………………….

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

  неопределенных коэффициентов……………………………………...

9. Понятие об автомате и его математическом описании ………………...

9.1. Основные определения теории конечных автоматов………………...

9.2. Описание конечных детерминированных автоматов

  таблицами переходов-выходов и графами……………………………

9.3. Понятие о технической интерпретации конечных автоматов……….

9.4. Синтез комбинационных автоматов в заданном базисе……………..

9.5. Булева производная…………………………………………………….

9.6. Элементарные автоматы памяти на основе комбинационного

  автомата и задержки……………………………………………………

9.7. Синтез автомата – распознавателя последовательности……………..

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

10.1. Понятие о кодировании……………………………………………….

10.2. Системы счисления, как основа различных кодов………………….

10.3. Понятие о помехоустойчивом кодировании………………………...

10.4. Кодирование по Хэммингу…………………………………………...

10.5. Кодирование с использованием циклических кодов

    и математического аппарата умножения и деления

    полиномов. Сигнатурный анализ…………………………………….

10.6. Понятие о криптографической защите информации……………….

10.7. Понятие о сжатии информации………………………………………

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ ………….

11. Понятие об алгоритмах. Схемы алгоритмов …………………………...

11.1. Понятие об алгоритме и теории алгоритмов………………………...

11.2. Схемы алгоритмов…………………………………………………….

11.3. Рекурсивные функции………………………………………………...

11.4. Машина Тьюринга…………………………………………………….

11.5. Машина Поста…………………………………………………………

11.6. Нормальные алгорифмы А.А. Маркова……………………………...

11.7. Универсальная абстрактная машина…………………………………

11.8. Разрешимость в теории алгоритмов.

    Проблема самоприменимости………………………………………..

11.9. Сложность алгоритма…………………………………………………

11.10. Представление схемы алгоритма эквивалентным автоматом…….

11.11. Представление схемы алгоритма микропрограммой

      с двумя типами микрокоманд……………………………………….

12. Элементы формальной логики …………………………………………..

12.1. Предмет формальной логики…………………………………………

12.2. Понятие и его виды……………………………………………………

12.3. Отношения между понятиями………………………………………..

12.4. Операции над понятиями……………………………………………..

12.5. Суждение и его характеристика……………………………………...

13. Умозаключение …………………………………………………………….

13.1. Виды умозаключений…………………………………………………

13.2. Непосредственное умозаключение…………………………………..

13.3. Опосредованное дедуктивное умозаключение.

    Фигуры силлогизма……………………………………………………

13.4. Дополнительные виды силлогизмов…………………………………

13.5. Индуктивные умозаключения. Математическая индукция………...

14. Логика высказываний …………………………………………………….

14.1. Семантика логики высказываний…………………………………….

14.2. Синтаксис логики высказываний.

    Формулы логики высказываний……………………………………...

14.3. Формализация высказываний………………………………………...

14.4. Интерпретации, разрешимость, выполнимость, общезначимость…

14.5. Логическая равносильность. Законы логики…………………….….

14.6. Формы представления формул логики высказываний……………...

14.7. Проблема дедукции в логике высказываний………………………...

15. Проверка правильности логических выводов. Метод резолций …….

15.1. Закон контрапозиции………………………………………………….

15.2. Логическое следование. Проверка правильности

    логических выводов…………………………………………………...

15.3. Силлогизмы в логике высказываний………………………………...

15.4. Получение следствий из данных посылок…………………………...

15.5. Метод резолюций……………………………………………………...

16. Синтаксис и семантика языка логики предикатов ……………………

16.1. Понятие предиката…………………………………………………….

16.2. Кванторы и связанные переменные………………………………….

16.3. Синтаксис языка логики предикатов. Формулы логики

    предикатов и формализация суждений………………………………

16.4. Семантика формул логики предикатов………………………………

17. Тождественные преобразования формул логики предикатов ……….

17.1. Операции над предикатами…………………………………………...

17.2. Основные равносильности логики предикатов……………………...

17.3. Тождественные преобразования формул…...……………………….

17.4. Универсум Эрбрана…………………………………………………...

18. Использование метода резолюций в логике предикатов ……………..

18.1. Подстановка и унификация…………………………………………...

18.2. Резольвенция и факторизация………………………………………..

18.3. Метод резолюций в логике предикатов……………………………...

18.4. Принцип логического программирования…………………………..

19. Логические исчисления …………………………………………………...

19.1. Понятие о формальных теориях……………………………………...

19.2. Исчисление высказываний……………………………………………

19.3. Исчисление предикатов……………………………………………….

19.4. Система натурного вывода………………………………………..….

19.5. Понятие о математической лингвистике…………………………….

19.6. Формальный язык……………………………………………………..

19.7. Формальные грамматики и их свойства……………………………..

19.8. Теоремы Геделя………………………………………………………..

20. Неклассические логики ………………………………….………………..

20.1. Современные модальные логики……………………..………………

20.2. Понятие о теории неопределенности………………….……………..

20.3. Элементы теории нечетких множеств и нечеткая логика…………..

20.4. Нечеткие алгоритмы……………………….………………………….

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

Приложение 1. Варианты контрольных заданий по дисциплине

                       «Дискретная математика»……………………………………

Приложение 2. Варианты контрольных заданий по дисциплине

                        «Математическая логика»…………………………………...

 

 

ПРЕДИСЛОВИЕ

 

Дискретная математика – раздел математики, занимающийся изучением свойств объектов дискретного и (или) конечного характера, к числу которых могут быть отнесены конечные группы, конечные графы, многие математические модели преобразователей информации. Все эти объекты и модели основываются на теоретико-множественных понятиях. В нынешнее цифровое тысячелетие знание дискретной математики, «цифровое мышление» – необходимый элемент информационной культуры специалиста.

Как отдельная учебная дисциплина в большинстве вузов РФ дискретная математика выделилась сравнительно недавно в 70-80-е годы прошлого века.

Математическая логика – это логика, развиваемая математическим методом. Характерным является использование формальных языков с точным синтаксисом и чёткой семантикой, однозначно определяющими понимание формул. Потребность в такой логике выявилась в начале ХХ века в связи с интенсивной разработкой оснований математики, возникновением, уточнением понятия алгоритма и другими глубокими и принципиальными вопросами математической науки. Значение математической логики для науки не исчерпывается её математическими приложениями, поскольку рассуждать и доказывать приходится во всех науках. Поэтому математическая логика с полным правом может быть охарактеризована как логика на современном этапе.

Математическая логика чаще всего являлась отдельным разделом дискретной математики. И только в конце ХХ века в государственных образовательных стандартах даже «нематематических» специальностей она представляется как отдельная дисциплина.

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

Учебное пособие предназначено для изучения двух дисциплин – «Дискретная математика» и «Математическая логика».

Авторы стремились с одной стороны, как можно более конкретизировать абстрактные понятия математики на «информационных» и «технических» примерах, а с другой стороны, проводили идеологию цифрового и числового кодирования математических объектов. Кодирование – это и основа информационных технологий новой цивилизации, и предоставление возможности формирования большого количества вариантов заданий для самостоятельной работы (см. прил. 1-2) по многим разделам изучаемых дисциплин.

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

Авторы пользуются термином «переключательные функции» в дискретной математике, который в последнее время утвердился и в государственных образовательных стандартах. В математической логике, как правило, используется более конкретный термин – «логическая функция».

Авторы посвящают свой скромный труд учителям – Л.Ф. Викентьеву, Т.И. Когану, В.А. Несмелову, и выражают благодарность А.М. Гревцеву за помощь в подготовке заданий для самостоятельной работы.

 

ДИСКРЕТНАЯ МАТЕМАТИКА