- •Е.Д. Стрельцова, в.С. Стрельцов моделирование дискретных систем Учебно-методическое пособие по дисциплине «Дискретная математика»
- •2. Теория множеств и отношений………………………………….20
- •Введение
- •1. Функции алгебры логики
- •1.1. Основные понятия
- •Пример функции алгебры логики , заданной таблицей
- •1.2. Алгоритм нахождения фиктивных аргументов.
- •1.3. Элементарные функции алгебры логики
- •Функции алгебры логики, зависящие от одного аргумента
- •Вопросы к разделу 1
- •2. Теория множеств и отношений
- •2.1. Множества. Способы задания множеств
- •2.2. Основные операции над множествами
- •2.2.1. Объединение множеств
- •2 .2.2. Пересечение множеств
- •2.2.3. Разность множеств
- •2.2.4. Дополнение множеств
- •2.4. Свойства операций над множествами
- •2.5. Упорядоченные множества
- •2.6. Прямое (декартово) произведение множеств
- •2.7. Степень множеств
- •2.8. Сечение и проекция
- •Декартово произведение
- •2.9. Соответствия
- •2.10. Композиция соответствий.
- •2.11. Отображения
- •2.12. Виды отображений. Функциональное отображение (функция)
- •2.13. Функционалы
- •2.14. Операторы
- •2.15. Линейные операторы
- •Отношение «Читает лекции по…»
- •Отношение «Посещать лекции»
- •2.20. Бинарные отношения
- •2.20.1. Матричный способ задания отношений
- •2.20.2. Задание отношений в виде графа
- •2.20.3. Задание отношений с помощью фактор множества
- •2.21. Свойства бинарных отношений
- •2.22. Отношение эквивалентности
- •2.23. Отношение порядка
- •2.24. Изоморфизм отношений
- •2.26. Операции над бинарными отношениями
- •2.26.1. Объединение отношений
- •2.26.2. Пересечение отношений
- •2.26.3. Разность отношений
- •2.26.4. Включение отношений
- •2.26.5. Переход к обратному отношению
- •2.26.6. Произведение отношений
- •2.26.7. Транзитивное замыкание
- •Вопросы к разделу № 2
- •3. Алгебраические системы
- •3.1. Понятие алгебраической системы
- •3.1. Морфизм алгебраических систем
- •3.3. Автоморфизмы
- •3.4. Виды универсальных алгебр
- •3.4.1. Полугруппы. Моноиды
- •3.4.2. Морфизм групп
- •3.4.3. Свойства морфизма групп
- •3.4.4. Кольцо
- •Вопросы к разделу №3
- •4. Практикум к решению задач Основные обозначения
- •4.1. Операции над множествами
- •Разностью множеств а и в называется множество
- •Симметрической разностью множеств а и в называется множество
- •Пустым множеством называется множество, не имеющее ни одного элемента.
- •Задачи и упражнения
- •На основании (14) можно записать
- •По определению объединения
- •Пусть теперь у (ав) (ас) у (ав) у (ас) (у а у в) (у а у с) у а (у в у с)
- •Задачи для самостоятельного решения
- •4.2. Векторное произведение
- •4.3. Соответствие
- •Свойства отношений
- •Список литературы
- •Моделирование дискретных систем
- •3 46428, Г. Новочеркасск, ул. Просвещения, 132
Функции алгебры логики, зависящие от одного аргумента
№ п/п |
|
|
|
|
|
|
|
|
|
||
1 |
0 |
0 |
0 |
1 |
1 |
2 |
1 |
0 |
1 |
0 |
1 |
3 |
|
н/с |
с |
с |
н/с |
Рассмотрим множество функций, зависящих от двух аргументов, т.е. : . Количество этих функций составляет . Среди этих функций найдутся функции как существенно, так и несущественно зависящие от аргументов и . Рассмотрим только те функции алгебры логики вида , которые существенно зависят от своих аргументов. Эти функции представлены в виде таблицы истинности (табл. 1.4).
Таблица 1.4
Таблица истинности элементарных функций алгебры логики
|
|
|
|
|
|
|
|
|
|
(&) |
(~) |
(+) |
↓ |
/ |
→ |
||
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
В таблице 1.4 функции означают следующее:
функция логического сложения, дизъюнкция (функция «или») : ;
функция логического умножения, конъюнкция (функция «и»): ;
эквиваленция, функция принимает значение 1 если значения обоих аргументов одинаковы: ;
сложение по модулю2, принимает значение 1 при различных значениях аргументов: ;
функция Вебба, принимает значения, обратные дизъюнкции: ;
штрих Шеффира – принимает значения, обратные конъюнкции:
импликация: (читается, если , то , или влечет за собой , или имплицирует ).
Свойства операций дизъюнкции, конъюнкции и отрицания
Коммутативность.
; .
Ассоциативность.
;
.
Дистрибутивность.
;
.
Теоремы А. Де-Моргана.
;
Имеют место следующие выражения
; ; ; ;
; ; ; .
Свойства операций дизъюнкции, конъюнкции и отрицания могут быть доказаны с помощью таблиц истинности. Приведём пример даказательства. Докажем, например, одну из теорем А. Де-Моргана . Слева и справа от знака равенства стоят функции ылгебры логики: и , равенство которых необходимо установить. Вспомним определение равенства функций алгебры логики: две функции алгебры логики называются равными тогда и только тогда, когда на равных наборах значений аргументов они принимают одинаковые значения. Составим таблицы истинности для функций и (таблицы 1.5 и 1.6 соответственно).
Таблица 1.5 Таблица истинности для функции |
|
Таблица 1.6 Таблица истинности для функции |
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
|
1 |
1 |
0 |
0 |
0 |
На основе таблиц 1.5 и 1.6 можно сделать вывод о равенстве функций алгебры логики и .
Свойства сложения по модулю 2
Для функции сложения по модулю 2 имеют место коммутативный, ассоциативный, а также дистрибутивный закон относительно конъюнкции.
Коммутативность.
;
Ассоциативность.
.
Дистрибутивность относительно конъюнкции.
.
Имеют место следующие очевидные соотноше6ния:
; ; ; .
Кроме того, имеет место формула .
Свойства импликации
В отличие от ранее рассмотренных функций для импликации не имеют места коммутативный и ассоциативный законы:
и .
Для импликации выполняются следующие соотношения:
; ; ; ; ; ;
; .
Функции дизъюнкции и конъюнкции могут быть выражены через импликацию:
; .
Доказательство этих формул может быть проведено на основе таблиц истинности. Проверка справедливости этих соотношений предоставляется студентам.
Свойства операции штрих Шеффера и функции Вебба.
Для функций Шеффера и Вебба имеет место коммутативный закон:
; .
Свойство ассоциативности для этих функций не выполняется.
; .
Имеют место следующие очевидные соотношения:
; ; ; ; ; ;
; ; ; .
Доказательство соотношений рекомендуется студентам провести самостоятелльно.