Существуют два вида дискретных сигналов.

Предмет дискретной математики. Предмет её исследований.

1. Понятие множества. Способы задания множеств. Свойства множеств.

2. Соотношения между множествами.

1. Предмет дискретной математики. Предмет ее исследований.

Обмен информацией в системах компьютерного прорабатывания информации осуществляется с помощью сигналов, которыми могут быть любые физические величины – ток, напряжение, магнитные состояния, световые волны.

Физические величины являют собой функции времени или определено распределение сигналов в пространстве. Параметры передаваемых временных функций – частота, амплитуда, фаза, длительность импульсов или пространственное распределение сигналов, последовательность импульсов, точек на изображении, сочетание цветов на экране и тому подобное, - называются информационными параметрами сигналов.

Различают такие виды сигналов:

Аналоговый или непрерывный.

Его параметры внутри заданного диапазона могут приобретать любые значения в произвольный момент времени. Эти параметры являются информационными, поскольку передают информацию о состоянии отображаемого объекта.

Дискретный сигнал.

Параметры такого сигнала могут приобретать лишь определенные значения в конкретные моменты времени. При этом важным является не уровень, а его наличие. Это приводит к тому, что сигнал остается неизменным при разных его уровнях и формы и только тогда, когда при изменении сигнала достигается определенный предел, происходит скачкообразный переход его к другому состоянию. Дискретные сигналы меньше подлежат искажениям под воздействием препятствий, это приводит к тому, что искажения легче определяются и исправляются. Кроме того их проще хранить и обрабатывать. Поэтому дискретные сигналы находят более широкое применения, чем непрерывные.

Существуют два вида дискретных сигналов.

Дискретные сигналы, полученные способом дискретизации непрерывных сигналов.

Дискретные сигналы, поданные в виде кодовых комбинаций – слов.

Представление в виде слов является наиболее универсальным и распространенным. Оно применяется для кодировки человеческого языка, в математике, цифровой электронике.

Дискретная математика - наука о способах построения и эффективного обрабатывания последовательностей целых объектов, в частности букв а₁, а₂, а_n порождаемых некоторым алфавитом В = {b1, b2 ..., bm}, а_і принадлежат В, которые можно рассматривать как слова.

Таким образом, большинство дискретных устройств осуществляют обработку информации, поданной в виде слов. Использование вербальной (словесной) информации не налагает ограничений на применения дискретных устройств для обработки непрерывной информации, потому что непрерывная информация может быть с любой точностью аппроксимирована дискретными сигналами, а сигналы могут быть поданы в виде слов.

Чаще всего используются дискретные устройства, в которых входные и выходные сигналы имеют два разных уровня. Это связано с необходимостью простоты физической реализации устройств для обработки непрерывной информации, рассуждениями относительно надежности и экономичности логических и арифметических операций. Одному из уровней присваивается 0, а другому 1 и, таким образом, с помощью этих цифр, устройство осуществляет обработку двоичной информации - слов в алфавите В.

Из отмеченных преимуществ представления информации с помощью слов дискретные устройства сегодня занимают доминирующее положение в отрасли обработки информации.

Электронные вычислительные машины (ЭВМ) сначала были аналоговыми. Сегодня цифровые ЭВМ практически вытеснили аналоговые. Тоже происходит с звуко- и видеозаписью, приемниками, телевидением.

В ближайшие годы цифровая электроника будет продолжать занимать монопольное положение на рынке электронных систем и устройств. Однако вытеснить аналоговую технику цифровая в принципе не может, поскольку физические объекты, от которых цифровые ЭВМ получают информацию, а также объекты управления обычно имеют аналоговую природу. Поэтому на входе и на выходе электронных цифровых вычислительных машин нужны аналоговые, цифро-аналоговые и аналого-цифровые устройства. Кроме того, часто в местах ответственности цифровых схем используются аналоговые элементы.

Аналоговая электроника имеет также непревзойденное быстродействие, которое ограничивается скоростью физических процессов и как следствие, невзирая на то, что удельный вес аналоговой электроники падает, ее значение совсем по уменьшается. Поэтому "непрерывная" математика в образовании специалиста по электронике и автоматике не теряет своего значения, хотя роль дискретной математики при этом постоянно растет.

Дискретная математика, кроме ее приложения для электронных цифровых устройств и систем, широко также используется для создания и эксплуатации комплексных автоматизированных систем обработки информации, пакетов прикладных программ, банков данных, микропроцессорных систем, мереж передачи данные.

Основной особенностью дискретной математики является отсутствие предельного перехода и непрерывности, присущих классической математике. Дискретная математика содержит теорию множественных чисел и систем алгебраизма, математическую логику, теорию графов, теорию автоматов и формальных грамматик, теорию алгоритмов, теорию кодировки, теорию чисел, комбинаторные вычисления, дискретные экстремальные задачи.

В наш час методы и средства дискретной математики развиваются наиболее интенсивно. Среди этих заданий особенно выделяются задачи на построение, перебор и нумерацию дискретных объектов. Большинство других заданий или сводятся к ним, или содержат их в явном или неявном виде.

Перед появлением вычислительной техники эти задачи не имели особенного практического значения, поскольку для заданий малой размерности отыскивались естественные алгоритмы, а для заданий большой размерности не было технических средств их реализации.

Особенную трудность для решения дискретных задач создает отсутствие основополагающих теорем, из которых выплывали бы методы и алгоритмы решения этих задач. Их разработка является одной из центральных проблем теории дискретных вычислений.

Поэтому в данном курсе лекций рассматриваются наиболее важные вопросы дискретной математики из области теории множественных чисел и логики, которая используется в задачах информатики, программирования, управления, цифровой связи, медицинской техники, цифрового телевидения, а также при построении и эксплуатации электронных цифровых вычислительных машин и цифровых электронных устройств разного назначения, от бытовых к научным.

Особенное внимание уделяется теоретическим основам дискретной математики – теории множественных чисел, которая является не только основой дискретной, но и всей современной математики.

Значительное внимание уделяется также вопросам математической логики как основы теории дискретных автоматов и современных методов программирования.

В течение учебного года по дискретной математике будут изучены следующие разделы: теория множественных чисел и операции над ними, алгебра высказываний, алгебра предикатов, булевые функции, элементы теории графов.

2. Понятие множества. Способы задания множеств. Свойства множеств.

Понятие множества первично, т. е. его нельзя свести к другим понятиям и определениям, на его основе строятся все математические конструкции.

Под множеством будем понимать совокупность (систему) каких-либо объектов произвольной природы, обладающих некоторым общим признаком. Слова «произвольной природы» означают, что для некоторого объекта и множества следует отвлечься от всех их свойств, кроме одного: входит объект в состав множества или нет.

Множества обозначают заглавными буквами латинского, реже русского, алфавита. Множество задано (определено), если о на всяком объекте можно сказать, принадлежит он к данному множеству или нет. Объекты, образующие множество, будем называть элементами множества и обозначать соответствующими малыми буквами. Например, множество людей, множество целых чисел, множество столиц государств.

Если элемент п принадлежит множеству N, это обознача­ется так: п є N, в противном случае пишут п ∉ N.

Некоторые множества имеют общепринятые обозначения: N — множество натуральных чисел, R — множество действи­тельных чисел, Z — множество целых чисел.

Способы задания множеств.

Множества можно задать следующим образом.

— Перечислением всех входящих в него объектов, (эле­ментов множества). Например, {0,1,2,3,4,5,6,7,8,9} — множество десятичных цифр.

— Описанием свойств, которыми должны обладать эле­менты множества. Например, множество четных чисел, меньших 10, можно задать в следующем виде: М = {2, 4, 6, 8} или М — {m/m = 2n, где n — целое, 1 < n < 4} причем справа от наклонной черты указано свойств элементов этого множества.

Таким образом, множество можно задать выражением, которое входят идентификаторы (указатели) множеств, операции и, быть может, скобки. Такой способ задания множества называется аналитическим.

Если все элементы некоторого множества А можно пронумеровать: {а₁, а₂, ...}, причем, каждый элемент имеет только один номер, то множество счетное (конечное), если число эле­ментов конечно, в противном случае множество несчетное. Мно­жество, не содержащее ни одного элемента, называют пустым и обозначается 0. Количество элементов конечного множестве А называют мощностью множества и часто обозначают |А|.

Множества, в зависимости от числа входящих в них эле­ментов, делятся на конечные, бесконечные и пустые.

Любую часть множества А, выбранную по определенному признаку, называют подмножеством и, обычно обозначают буквой со штрихом, т. е. А':

А' ⊂ А ↔ {а ∊ А' → a ∊А},