Введение

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

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

В результате освоения дисциплины обучающийся должен:

уметь:

- формулировать задачи логического характера и применять средства математической логики для их решения;

- применять законы алгебры логики;

- определять типы графов и давать их характеристики;

- строить простейшие автоматы;

знать:

- основные понятия и приемы дискретной математики;

- логические операции, формулы логики, законы алгебры логики;

- основные классы функций, полнота множества функций, теорема Поста;

- основные понятия теории множеств, теоретико-множественные операции и их связь с логическими операциями;

- логику предикатов, бинарные отношения и их виды;

- элементы теории отображений и алгебры подстановок;

- метод математической индукции;

- алгоритмическое перечисление основных комбинаторных объектов;

- основные понятия теории графов, характеристики и виды графов;

- элементы теории автоматов.

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

• Теория вероятностей и математическая статистика

• Основы алгоритмизации и программирования

Курс рассчитан на 40 часов лекций и 38 часов практических занятий. Промежуточная оценка знаний и умений студентов проводится с помощью, самостоятельных работ, которые включают в себя основные проблемы курса. Завершается изучение дисциплины «Математика» сдачей экзамена.

1Практическая работа№1 Логические операции, формулы логики.

Цель работы: Изучить понятие высказывания. Научится производить операции над высказываниями. Составлять логические формулы и строить таблицы истинности.

1.1 Ход работы:

1) изучить теоретический материал по теме практической работы (лекции, учебники);

2) выполнить задание своего варианта;

3) составить отчет по работе;

4) защитить работу.

1.2 Содержание отчета

Отчет по практической работе должен содержать:

1) тему работы;

2) цель работы;

3) ход работы;

4) формулировку заданий;

5) решение заданий своего варианта.

1.3 Методические указания к практической работе № 1

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

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

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

Отрицание обозначается через и читается как «не а», «неверно, что а».

Пример.

а – «Степан любит танцевать».

Тогда - «Не верно, что Степан любит танцевать».

Определение. Конъюнкцией двух высказываний является новое высказывание, которое истинно только тогда, когда оба исходных высказывания истинны.

Конъюнкция обозначается или a&b и читается как «a и b», «a, но b», «a, а b».

Пример.

а – «Степан любит танцевать», b – «Степан любит петь».

Тогда - «Степан любит танцевать и петь».

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

Дизъюнкция обозначается через и читается как «a или b».

Пример.

а – «Степан любит танцевать», b – «Степан любит петь».

Тогда - «Степан любит танцевать или петь».

Определение. Импликацией двух высказываний является новое высказывание, которое ложно только тогда, когда первое истинно, а второе – ложно.

Импликация обозначается a b и читается как «если a, то b»; « из а следует b». При этом a называется посылкой или условием, b – следствием или заключением.

Пример.

а – «Степан любит танцевать», b – «Степан любит петь».

Тогда - «Если Степан любит танцевать, то он любит петь».

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

Эквивалентность обозначается a b и читается как «a эквивалентно b».

Пример.

а – «Степан любит танцевать», b – «Степан любит петь».

Тогда - «Для того, чтобы Степан любил танцевать, необходимо и достаточно, чтобы он любил петь».

Сведем все сказанное выше в единую таблицу и введем в рассмотрение еще три операции: сумма по модулю два, штрих Шеффера, стрелка Пирса.

Таблица 1 – Логические операции

Обозначения логической операции	Другие обозначения логической операции	Названия логической операции и связки	Как читается выражение, приведенное в первом столбце
 a		отрицание	неверно, что а; не а
a  b	a  b ab min(a; b)	конъюнкция, логическое умножение, логическое «и»	a и b
a b	a+b max(a; b)	дизъюнкция, логическое сложение, логическое «или»	а или b
a b	ab ab	импликация, логическое следование	если а, то b; а имплицирует b; а влечет b
a  b	a  b a  b a  b	эквиваленция, эквивалентность, равнозначность, тождественность	а тогда и только тогда, когда b; а эквивалентно b
a b	a+ b a  b	сумма по модулю два, разделительная дизъюнкция, разделительное «или»	а плюс b; либо а, либо b
a  b		штрих Шеффера, антиконъюнкция	неверно, что а и b; а штрих Шеффера b
a  b	a  b	стрелка Пирса, антидизъюнкция, функция Вебба, функция Даггера	ни а, ни b; а стрелка Пирса b

В дальнейшем значению «истина» будем ставить в соответствие 1, а «ложь» - 0. Каждой логической операции ставится в соответствие таблица истинности. Таблица истинности выражает значения истинности высказываний в зависимости от значений элементарных высказываний.

Для рассмотренных выше логических операций таблицы истинности будут иметь вид:

Таблица 2 – Таблицы истинности

a
0	1
1	0

a	b	ab	ab	ab	a↔b	a b	a  b	a  b
0	0	0	0	1	1	0	1	1
0	1	0	1	1	0	1	1	0
1	0	0	1	0	0	1	1	0
1	1	1	1	1	1	0	0	0

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

Определение. Алфавитом называется любое непустое множество. Элементы этого множества называются символами данного алфавита. Словом в данном алфавите называется произвольная конечная последовательность символов (возможно пустая).

Алфавит логики высказываний содержит следующие символы:

• высказывательные переменные;

• логические символы;

• символы скобок.

Определение. Слово в алфавите логики высказываний называется формулой, если оно удовлетворяет следующему определению:

1. любая высказывательная переменная – формула;

2. если А и В – формулы, то  А, А  В, А В, А В, А В, А В, А  В, А  В – формулы;

3. только те слова являются формулами, для которых это следует из 1) и 2).

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

Пример.

Представить логическими формулами следующие высказывания:

1. «Сегодня понедельник или вторник».

2. «Если идет дождь, то крыши мокрые. Дождя нет, а крыши мокрые».

3. «Что в лоб, что по лбу».

Решение.

1. Составное (сложное) высказывание «Сегодня понедельник или вторник» состоит из двух простых:

• а – «сегодня понедельник»;

• b – «сегодня вторник».

Высказывания а и b соединены связкой «или» очевидно в разделительном смысле (не допускается одновременное выполнение обоих условий), то есть используется логическая связка «сумма по модулю два». Таким образом, данное высказывание представимо логической формулой: a  b.

2. Сложное высказывание «Если идет дождь, то крыши мокрые. Дождя нет, а крыши мокрые» включает два простых высказывания:

• а – «идет дождь»;

• b – «крыши мокрые».

В первом предложении «Если идет дождь, то крыши мокрые» высказывания а, b соединены связкой «если …, то…»: а  b.

Во втором «Дождя нет, а крыши мокрые» союз «а» здесь имеет смысл связки «и» (), и кроме того высказывание а следует взять с отрицанием: .

Остается объединить представленные выше два высказывания:

.

3. Высказывание «Что в лоб, что по лбу», если обозначить:

• а – «в лоб»,

• b – «по лбу»,

представимо логической формулой a  b.

Определение. Формула называется выполнимой (опровержимой), если существует такой набор значений переменных, при которых эта формула принимает значение 1 (0).

Определение. Формула называется тождественно-истинной, или тавтологией (тождественно-ложной или противоречием), если эта формула принимает значение 1 (0) при всех наборах значений переменных.

Пример.

Составить таблицы истинности для формул:

1. ;

2. .

Решение.

1. Таблица истинности для формулы имеет вид:

x	y	xy	(xy)x
0	0	0	0
0	1	0	0
1	0	0	1
1	1	1	1

2. Таблица истинности для формулы имеет вид:

x	y	z
0	0	0	1	1	0	1	0	0
0	0	1	1	1	0	1	1	1
0	1	0	0	1	1	0	0	0
0	1	1	0	1	1	0	0	0
1	0	0	1	1	1	0	0	0
1	0	1	1	1	1	0	0	0
1	1	0	0	0	1	0	0	1
1	1	1	0	0	1	0	0	1