- •1. Понятие множества.
- •6. Булеан. Что позволяет определить булеан?
- •7. Диаграмма Эйлера-Венна. Когда она применяется?
- •8. Операции над множествами. Дополнение и симметрическая разность множеств.
- •9. Законы алгебры множеств.
- •19. Свойства отношений.
- •29. Принцип математической индукции, алгоритм применения математической индукции.
- •30. Методы доказательства. Обратное рассуждение.
- •31. Предикаты. Кванторы.
- •32. Исчисление предикатов. Диаграммы Эйлера.
- •33. Двоичная арифметика. Булевы функции.
- •35. Днф и кнф.
- •36. Карта Карно.
- •37. Понятие алгоритма. Вычислимые функции.
- •38. Примитивно-рекурсивные функции.
- •39. Понятие сложности алгоритма.
- •40. Комбинаторика. Правила суммы и произведения.
- •41. Комбинаторика. Принцип включения и исключения.
- •42. Бином Ньютона.
19. Свойства отношений.
Говорят, что отношение Rна подмножестве А
Рефлексивно, если для всех х Е А хRx
Симметрично, еслиxRyyRxдля каждой парыxиyиз А.
Кососимметрично, если (xRyиyRxx=y) для всех х иyиз А.
Транзитивно, если (xRyиyRzxRz) для любой тройки элементовx,y,zEA.
20. Композиция бинарных отношений.
Композиция (суперпозиция) бинарных отношений R и S — это множество {(x, y)| Э z(xSz zRy)} и обозначается, как R oS.
21. График.
Графиком называется множество пар. График функции — понятие в математике, которое даёт представление о геометрическом образе функции.
Графики могут задаваться:
1. перечислением:
2. описанием свойств:
22. Множества. Отношение частичного порядка.
Рефлексивное, транзитивное, но кососимметрическое отношение Rна множестве А называется частичным порядком. Частичный порядок важен тогда, когда мы хотим как-то охарактеризовать старшинство.
23. Диаграмма Хасса. Для чего она применяется?
Диаграмма Хасса представляет собой граф, чьи вершины изображают элементы частично упорядоченного множества.
Диаграмма Хасса выдаст полную информацию об исходном частичном порядке, если мы поднимемся по всем цепочкам рёбер.
24. Высказывания.
Высказывание – это повествовательное предложение, о котором можно сказать истинно оно или ложно.
25. Методы доказательства. Прямое рассуждение.
Прямое рассуждение
Предполагаем, что высказывание Pистинно и показываем справедливостьQ. Такой способ доказательства исключает ситуацию, когдаP- истинно, аQ– ложно, поскольку именно в этом и только в этом случае импликация принимает ложное значение.
Обратное рассуждение
Метод от противного
26. Основные логические операции.
В алгебре логики существует три основные операции:
Логическое отрицание {инверсия).
Логическое умножение {конъюнкция).
Логическое сложение {дизъюнкция)
27. Таблицы истинности.
Таблица истинности – таблица, с помощью которой можно определить значение истинности составных высказываний.
28. Формулы алгебры высказываний. Эквивалентность формул.
Отрицание, конъюнкция, дизъюнкция.
Два сложных высказывания, построенные из одних и тех же простых утверждений, но разными путями, могут принимать одинаковые значения истинности на любом возможном наборе значений истинности своих составных чисел.
1. | |
2. |
Законы |
3. |
де Моргана |
4. |
|
5. |
|
Из двух высказываний АиВможно составить четыре импликации, которые носят название
ABпрямая теоремаBAобратная теоремапротивоположная теорематеорема противоположная к обратной
29. Принцип математической индукции, алгоритм применения математической индукции.
Проверка корректности алгоритма, содержащего циклы, нуждается в мощном методе доказательства, который называется математической индукцией
Алгоритм, определяющий максимальный элемент из набора а1, а2, а3,…, аnнатуральных чисел.
Begin
I:=0
M:=0
While i< n do
Begin
J:=j+1
M:=max (M,a);
End
End
Математическая индукция — метод математического доказательства, используется чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 — база (базис) индукции, а затем доказывается, что, если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — шаг индукции, или индукционный переход.