Шпаргалка по "Дискретной математике"

Вопросы для зачета по дискретной математике.

1.Множество. Способы задания множества. Подмножество. Равные множества. Операции над множествами: объединение, пересечение, разность, дополнение.

Понятие «множество» относится к первоначальным понятиям, не подлежащим определению. Поэтому множеством называют совокупность некоторых объектов, объединённых каким-либо общим признаком. Объектами могут быть числа, фигуры, предметы, понятия и т.п.

Задать множество – это значит указать, какие элементы ему принадлежат. Это указание заключают в пару фигурных скобок.

1. Задание множества перечислением элементов. М: = {а, b, c, d}. Если множество состоит из чисел, то при их перечислении удобнее использовать не запятую, а точку с запятой, чтобы не спутать с десятичной точкой. A: = {1; 2; 3; 4; 5}.
2. Задание множества характеристическим предикатом. Характеристический предикат – это условие, выраженное в форме логического утверждения, возвращающей логическое значение и позволяющее проверить, принадлежит ли любой данный элемент множеству или нет. Если для данного элемента условие выполнено, то он принадлежит определяемому множеству, в противном случае – не принадлежит. Пример 4. M: = {x | P(x)}

Определение подмножества - множество A называется подмножеством множества B [pic 1], если каждый элемент A является элементом B. [pic 2].

Два множества называют равными (А = В), если они состоят из одних и тех же элементов или являются пустыми множествами. Так, как при равенстве множеств А и В во множестве А нет элементов, не принадлежащих В, а в В нет элементов, не принадлежащих А, то признаком равенства множеств является одновременное выполнение двух условий: А ⊆ В и В⊆ А .

1. Объединение множеств. Объединение множеств А и В обозначается А . Это множество всех таких х, что х является элементом хотя бы одного из множеств А, В. A B {x | x∈A ∨ x∈B }
2.  Пересечение множеств. Пересечение множеств А и В обозначается А . Это множество всех таких х, что х является одновременно элементом А и элементом В. A B {x | x∈A & x∈B }
3. Разность множеств А и В. Разность множеств А и В обозначается А . Это множество всех таких х, что х∈ А, но не содержаться в В. A B {x | x∈A & x B }
4. Дополнение. Дополнение – эта операция подразумевает, что задан некоторый универсум U, тогда ¬А= U \ A, в противном случае операция дополнения не определена. ¬А {x | x A}.

2.Высказывание. Элементарное высказывание. Булевы функции. Таблица истинности.

Высказывание – связное повествовательное предложение, о котором можно сказать, истинно оно или ложно. Каждому элементарному логическому высказыванию А соответствует некоторая логическая переменная х, которая принимает значение х=0, если высказывание А ложное, и х=1, если высказывание истинное.

Булевой функцией f(x1, x2, …, xn) называется n-местная функция, аргументы которой принимают значения во множестве {0, 1} и сама функция принимает значения в этом же множестве.

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

3.Основные операции: отрицание, дизъюнкция, конъюнкция, импликация, эквиваленция.

1) Отрицание. Пусть логическому высказыванию А соответствует логическая переменная х. Логическое отрицание задается следующей таблицей, которая называется таблицей истинности данной операции (табл. отрицания)

2) Дизъюнкция (логическое сложение) соответствует союзу «или» в русском языке, т.е. дизъюнкция А∨В ложна тогда и только тогда, когда ложны оба высказывания А и В(табл.)