Свойства бинарных алгебраических операций
Условимся, чтобы последующие соотношения выглядели более привычно, результат применения бинарной операции к элементам а иb записывать не в функциональном виде , а в виде(как это принято в арифметических операциях).
Операция называетсяассоциативной, если для любых элементов а, b, с
.
Выполнение условия ассоциативности означает, что скобки в выражении можно не расставлять.
Пример:
1. Сложение и умножение чисел ассоциативны, что позволяет не ставить скобки в выражениях и.
2. Возведение в степень – не ассоциативна, так как
не равно .
3. Композиция отображений – ассоциативная операция.
Операция называетсякоммутативной, если для любых элементов a, b
.
Пример:
1. Сложение чисел коммутативно («от перемены мест слагаемых сумма не меняется»): .
Умножение чисел коммутативно: .
2. Вычитание и деление – некоммутативные операции.
Умножение матриц – некоммутативная операция, например:
, но .
Операция называетсядистрибутивной слева относительно операции , если для любыхa, b, с
.
Операция называетсядистрибутивной справа относительно операции , если для любыхa, b, с
.
Дистрибутивность разрешает раскрыть скобки.
Примеры:
1. Умножение дистрибутивно относительно сложения слева и справа
; .
2. Возведение в степень дистрибутивно относительно умножения справа.
,
но не слева, так как не равно
.
3. Сложение не дистрибутивно относительно умножения
,
.
- Дискретная математика
- Содержание
- Глава 1. Теория множеств. Дискретная теория вероятности......5
- Глава 2. Теория графов.....................................................................50
- Глава 3. Дискретные структуры: конечные автоматы, коды...73
- Глава 4. Алгебра логических функций..........................................85
- Глава 5. Логика высказываний и логика предикатов..............106
- Упражнения
- 1.2. Векторы и прямые произведения множеств. Проекция вектора на ось
- Упражнения
- 1.3. Комбинаторика Правило суммы
- Правило произведения
- Число размещений без повторений
- Число размещений с повторениями
- Число перестановок без повторений
- Число сочетаний без повторений
- Упражнения
- 1.4. Введение в дискретную теорию вероятностей
- Свойства элементарных событий:
- Соотношения между событиями:
- Свойства операций над событиями:
- Аксиомы Колмогорова
- Свойства вероятности
- Классическое определение вероятности
- Упражнения
- 1.5. Соответствия и функции
- Взаимно однозначные соответствия и мощность множеств
- Упражнения
- 1.6. Отношения
- Способы задания бинарных отношений
- Свойства бинарных отношений
- Отношение эквивалентности
- Отношение порядка
- Лексико-графический порядок.
- Упражнения
- 1.7. Операции и алгебры
- Свойства бинарных алгебраических операций
- 1.8. Гомоморфизм и изоморфизм алгебр
- Полугруппы, группы, решетки
- Упражнения
- Глава 2. Теория графов
- 2.1. Основные определения, способы задания, основные классы, изоморфизм графов
- Способы задания графа
- Степени вершин графа
- Части, суграфы и подграфы
- Операции над частями графа
- Графы и бинарные отношения
- Упражнения
- Маршруты, цепи и циклы. Расстояния, диаметры, центры. Обходы. Разделяющие множества и разрезы
- Упражнения
- Деревья, их свойства. Характеристические числа графов. Сети
- Упражнения
- Глава 3. Дискретные структуры: конечные автоматы, коды
- 3.1. Машина Тьюринга
- Упражнения
- Основы теории кодирования
- Упражнения
- Глава 4. Алгебра логических функций
- 4.1. Основные определения
- Упражнения
- 4.2. Эквивалентные преобразования
- 1) ; 2);
- 1) ; 2).
- Упражнения
- 4.3. Дизъюнктивные и конъюнктивные нормальные формы
- Упражнения
- 4.4. Дизъюнктивные нормальные формы и импликанты
- Упражнения
- 4.5. Минимизация днф. Тупикова днф
- Упражнения
- 4.6. Алгебра Жегалкина
- Упражнения
- 4.7. Двойственность
- Принцип двойственности
- Упражнения
- 4.8. Функциональная полнота систем
- Упражнения
- Глава 5. Логика высказываний и логика предикатов
- 5.1. Логика высказываний
- Алгебра логики
- Исчисление высказываний
- Упражнения
- 5.2. Логика предикатов
- Упражнения
- Глава 6. Схемы переключателей. Комбинационные схемы
- Схемы переключателей
- Комбинационные схемы
- Упражнения
- Литература
- 650043, Кемерово, ул. Красная, 6.