Дискретная математика (стр. 1 )

РОСЖЕЛДОР

Государственное образовательное учреждение

высшего профессионального образования

«Ростовский государственный университет путей сообщения»

(РГУПС)

,

ДИСКРЕТНАЯ МАТЕМАТИКА

Учебно-методическое пособие

Ростов-на-Дону

2010

УДК 512.2 (07) + 06

Балашов, С. К.

Дискретная математика : учебно-методическое пособие / С. К. Балашов, О. Л. Наумов ; Рост. гос. ун-т путей сообщения. – Ростов н/Д, 2010. – 43 с. Библиогр. : 11 назв.

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

Пособие предназначено для студентов дневной и заочной форм обучения. Одобрено к изданию кафедрой «Высшая математика-1» РГУПС.

Рецензент д-р техн. наук, проф. (РГУПС)

© Ростовский государственный университет

путей сообщения, 2010

Содержание

Введение…………………………………………………………………………...4

1  Алгебра высказываний…………………………………………………………5

1.1 Логические операции над высказываниями……………………………….5

1.2 Зависимости между операциями. Основные равносильности для

булевых операций……………………………………………………………….8

1.3 Релейно-контактные схемы….………………..…………………………...12

2  Множества……………………………………………………………………..14

2.1 Начальные понятия теории множеств……….……………………………14

2.2 Операции над множествами: объединение, пересечение, дополнение…17

2.3 Конечные и бесконечные множества. Эквивалентность множеств.

Счетные и несчетные множества……………………………..……………….22

2.4 Декартово произведение множеств. Отображения, множество степень..25

2.5 Правило суммы……………………………………………………….…….26

3  Комбинаторика………………………………………………………….……..28

3.1 Историческая справка. Виды выборок: с возвращением и без

возвращения, упорядоченные и неупорядоченные……………………..……28

3.2 Соединения комбинаторики………………………………………….……30

Задачи для самостоятельного решения…………………………………….…...36

Библиографический список……………………………………………….……..42

Введение

В учебно-методическом пособии приводятся теоретические сведения и задачи к разделам «Алгебра высказываний», «Множества», «Элементы комбинаторики», входящие в состав курса «Дискретная математика».

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

Рассмотренные в учебно-методическом пособии разделы дискретной математики читались доцентом кафедры «Высшая математика-1» на факультете АТС для студентов специальности «Многоканальные телекоммуникационные системы».

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

1 Алгебра Высказываний

1.1 Логические операции над высказываниями

Основным понятием логики высказываний является высказывание.

Определение. Высказыванием называется связное повествовательное предложение, о котором можно сказать, истинно оно или ложно.

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

Приведем основные общепринятые обозначения (алфавит) и определения алгебры высказываний.

Высказывания обозначаются, как правило, буквами из начала латинского алфавита: а, b, с, …

Определение. Если a – высказывание, то символом обозначается значение его истинности, причем каждое высказывание может быть или истинным или ложным, но не может быть одновременно и истинным и ложным.

Если a – истинное высказывание, то = 1 (возможно также использование обозначений: = и (истина); = t (true)). Если a – ложное высказывание, то = 0 (возможно также использование обозначений: = л (ложно); = f (false)).

Высказывательные (пропозициональные) переменные, т. е. символы, вместо которых можно подставлять высказывания, как правило, обозначают буквами из конца латинского алфавита: х, у, z, … .

Определение. Два высказывания, a и b, будем называть равносильными (и записывать а b), если равны значения их истинности = , т. е.

а b =

(знак означает: «тогда и только тогда, когда …»).

Под элементарным высказыванием понимается высказывание, которое невозможно расчленить на другие, более простые высказывания, например, «2 × 2 = 4». Под сложным высказыванием понимается высказывание, состоящее из элементарных высказываний, которые определенным образом соединены словами и словосочетаниями: «не», «и», «или», «если…, то», «тогда и только тогда, когда» и некоторыми другими, и которые на русском языке обозначают логические операции.

Очевидно, любое высказывание (являющееся связным повествователь­ным предложением) повествует о наступлении чего-либо. Как известно, «то, что произошло, то или иное значительное явление, факт общественной, личной жизни» – называется событием. Таким образом, любое высказывание повест­вует о наступлении некоторого события, причем это событие может быть элементарным, не расчленяемым на другие, более простые события, – в случае элементарного высказывания, либо событие может быть сложным, состоя­щим из элементарных событий, – в случае сложного высказывания.

Логические операции алгебры высказываний – это операции над высказы­ваниями, порождающие новые высказывания.

1  Отрицание. Отрицанием некоторого высказывания а называется такое высказывание (или а), читаемое «не а» или «неверно, что а», которое ис­тинно, когда а ложно, и ложно, когда а истинно, и определяемое следующей таблицей истинности:

0	1
1	0

2  Конъюнкция. Конъюнкцией двух высказываний, a и b, называется та­кое высказывание ab (а·b, аb, а&b), читаемое «а и b», которое истинно тогда и только тогда, когда истинны оба высказывания, а и b. Конъюнкция определя­ется следующей таблицей истинности:

0	0	0
0	1	0
1	0	0
1	1	1

3  Дизъюнкция. Дизъюнкцией двух высказываний, а и b, называется та­кое высказывание аb, читаемое «а или b», которое истинно тогда и только то­гда, когда истинно хотя бы одно из этих высказываний (т. е. дизъюнкция двух высказываний ложна тогда и только тогда, когда ложны оба эти высказывания).