Определение 7: Дистрибутивная решетка с отличными друг от друга 0 и 1, в которой всякий элемент имеет дополнение, называется булевой алгеброй.
Определение 7: Дистрибутивная решетка с отличными друг от друга 0 и 1, в которой всякий элемент имеет дополнение, называется булевой алгеброй. - раздел Математика, КУРС ЛЕКЦИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ Отметим, Что Теория Решеток И Теория Булевых Алгебр – Это Самостоятельные Раз...
Отметим, что теория решеток и теория булевых алгебр – это самостоятельные разделы алгебры.
Определение 8: Линейно упорядоченное множество, удовлетворяющее условию минимальности (а значит и двум другим условиям, эквивалентным с ним), называется вполне упорядоченным.
Примером вполне упорядоченного множества служит множество натуральных чисел с естественным порядком. Всякое подмножество вполне упорядоченного множества само вполне упорядочено. Из определения вполне упорядоченного множества следует, что оно обладает единственным минимальным элементом.
Во вполне упорядоченном множестве для всякого элемента существует элемент, непосредственно следующий за . Элемент может не иметь, однако, непосредственно предшествующего элемента; в этом случае он называйся предельным элементом.
При изучении бесконечных множеств часто приходится пользоваться следующей аксиомой, которую называют аксиомой выбора.
Аксиома: Если дано множество , то существует функция , сопоставляющая каждому непустому подмножеству определенный элемент этого подмножества.
Другими словами, функция отмечает по одному элементу в каждом из непустых подмножеств множества .
Вопрос о логических основах этой аксиомы и о законности ее использования относится к числу самых трудных и спорных вопросов обоснования теории множеств. Многие из теорем, доказанные с помощью аксиомы выбора совершенно противоречили наглядности. Поэтому один из видных математиков XX века Бертран Рассел так высказался об этой аксиоме: «Сначала она кажется очевидной; но чем больше вдумываешься в нее, тем более странными кажутся выводы из этой аксиомы; под конец же перестаешь понимать, что же она означает».
Имеется целый ряд утверждений, каждое из которых эквивалентно аксиоме выбора. Например, следующие теоремы.
Теорема Цериело: Всякое множество можно вполне упорядочить.
Теорема Хауздорфа: Всякая цепь частично упорядоченного множества содержится в некоторой максимальной цепи.
Представление бинарных отношений графами.
Понятие графа используется в математике для наглядного представления бинарных отношений, заданных на конечных множествах.
Граф представляет собой конечный набор точек плоскости (
И порядка. Фактор-множество.
В данном параграфе будут рассмотрены некоторые виды бинарных отношений. Рассмотрим непустое множество и зададим на нём бинар
Булевы алгебры.
Определение 1: Пусть - отношение порядка на множестве
Трансфинитная индукция.
Понятие мощности множества является обобщением понятия количества элементов конечного множества. А число элементов во множестве – это натуральное число. Но над натуральными числами
Задачи для самостоятельной работы.
1) Доказать, что два множества равны тогда и только тогда, когда их пересечение и объединение совпадают.
2) Обозначим через множес
Формулы алгебры логики. Тавтологии.
В алгебре выводятся формулы, которые остаются верными, какие бы числа не подставляли вместо букв, входящих в эти формулы. Подобным образом в алгебре высказываний конструируются форм
Доказательство.
Необходимость: Пусть формулы и равносильны. Тогда, по определению, для люб
Формальный язык логики высказываний.
Таблицы истинности в логике высказываний позволяют ответить на многие вопросы. Например, является ли данная формула тавтологией, противоречием или выполнимой формулой; влечёт ли она
Теорема Поста.
В предыдущем параграфе были рассмотрены некоторые классы булевых функций. В каждый класс попадают функции, обладающие определённым свойством. Для удобства введём следующие обозначен
Правила комбинаторики.
Начнем с основных принципов комбинаторики, т.е. с правил.
Существует два общих правила комбинаторики: правило сложения и правило умножения.
Правило слож
Свойства сочетаний.
Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать след
Комбинаторика с повторениями.
Одна из особенностей комбинаторных задач заключается в том, что в ней исключительно большую роль играет точность формулировки. Обычно в задаче по комбинаторике необходимо определить
Упражнения для самостоятельной работы.
1. Сколько всегочетырёхзначных натуральныхчисел? Сколько всего четырёхзначных натуральныхчисел, в записи которых нет одинаковых цифр?
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов