Конспекты лекций по математической логике

Конспекты лекций по математической логике.

Лекция №1. Введение. Роль дискретной математики и математической логики в математике и информатике. При изучении многих математических объектов, прежде всего, создайте соответствующие им математические модели. Теория множеств. Операции над множествами.

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

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

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

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

ТЕОРИЯ МНОЖЕСТВ

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

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

Множества и операции над ними

Множество-это совокупность объектов, называемых элементами множества.

Например,

• {Адамс, Йорк, Девон};

• {2, 3, 5, 7, 11} ;

• {сыр, яйцо, молоко, сметана}.

В этом примере элементы каждого множества заключены в фигурные скобки. Чтобы обеспечить возможность ссылок, мы обычно будем обозначать множества прописными латинскими буквами. Например, S={3,2,11,5,7} - множество, содержащее данные элементы. Заметим, что множество S совпадает с одним из множеств, выписанных выше, поскольку порядок, в котором записываются элементы множества, значения не имеет.

В общем случае запись означает, что объект элемент

множества S. Часто говорят, что принадлежит множеству . Если объект не принадлежит , то пишут: .