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. |
|
Из двух высказываний АиВможно составить четыре импликации, которые носят название
A
Bпрямая
теоремаB
Aобратная
теорема
противоположная
теорема
теорема
противоположная к обратной
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 — шаг индукции, или индукционный переход.