lec02
.pdf
Кафедра Прикладной математики Института информационных технологий РТУ МИРЭА
Дисциплина
«Математическая логика и теория алгоритмов»
2022-2023 уч.г.
Наполнение курса
Объем курса
16 лекционных и 8 практических занятий
Темы лекционных занятий
1.Элементы теории множеств. Булева алгебра
2.Булевы вектора и булевы функции
3.ДНФ, СДНФ, КНФ, СКНФ
4.Минимизация ДНФ
5.Метод Карно и метод Квайна
6.Двойственные функции
7.Функциональная полнота. Полные классы. Алгебра Жегалкина.
8.Замкнутые классы функций: монотонные, самодвойственные, сохраняющие const.
9.Теорема Поста
10.Исчисление высказываний
11.Исчисление предикатов. Основные положения. Кванторы
12.Нормальные формы. Доказательства
13.Конечные автоматы
14.Соединения и синтез автоматов
15.Машина Тьюринга
16.ЧРФ и НАМ
2
Лекция 2.
Булевы вектора
ибулевы функции.
2.1.Булевы вектора.
2.2.Булева алгебра булевых векторов.
2.3.Характеристические векторы подмножеств.
2.4.Булевы функции. Способы задания БФ.
Часть 1.
Булевы вектора.
Булевы вектора.
Множество всех n-мерных векторов вида
α = (α1, α2, … αi, … αn), где αi = 10 , 1≤i≤n.
A(α)
Множество всех таких n-мерных векторов называется n-мерным булевым кубом Вn
Вn = {α A(α)}
5
Булев куб размерности 1 - В1
Размерность n=1, В1. Булев куб вида α = (α1),
в одномерном кубе два элемента – отрезок.
6
Булев куб размерности 2 - В2
Размерность n=2, В2.
Булев куб вида α = (α1,α2), в двухмерном кубе четыре элемента
– квадрат («булев квадрат»).
7
Булев куб размерности 3 – В3
Размерность n=3, В3.
Булев куб вида α = (α1,α2,α3) – куб с восемью вершинами.
8
Булев куб размерности 4 – В4
Размерность n=4, В4.
Булев куб вида α = (α1,α2,α3,α4) – гиперкуб с 16 вершинами.
Теорема о мощности булевой алгебры Вn
Теорема 2.1. Мощность булевой алгебры |Вn| = 2n
Доказательство:
Рассмотрим множество всех n-мерных векторов вида α = (α1,α2, … αi, … αn), где αi = 10 – координата вершины n-мерного булева куба Вn.
Для каждого αi – соответственно 2 возможности включения или же нет, ибо куб имеет размерность n = 2n возможностей.
10