Тема 0: Введение
Симферополь, 2004
ПО ДИСЦИПЛИНЕ Дискретная математика
КОНСПЕКТЫ ЛЕКЦИЙ
для студентов дневной (заочной) формы обучения
направления 0802 Прикладная математика,
специальностей 6.080200 Информатика,
6.080200 Прикладная информатика
Составитель:доктор физико-математических наук, профессор Донской В.И. | |
Рассмотрены и рекомендованы на заседании кафедры ……………………………. от «__» _____200_г. (протокол №_) |
Лекция 1. Предмет, мета та задачі дискретної математики
1) Непрерывность и дискретность [1,2,3,5]
2) Конструктивные объекты и задача синтеза. Ведение в теорию множеств и отношений [1,2,3,4,5]
Литература:
1. Яблонский С.В. Введение в дискретную математику. М.:Высш. шк., 2001. – 384 с.
2. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. М.: Наука, 1977. – 386 с.
3. Гиндикин С. Г. Алгебра логики в задачах. М.: Наука, 1972.- 288 с.
4. Грэхем Р., Кнут Д., Паташник О. Конкретная математика (основание информатики). М.: Мир, 1998. – 703 с.
5. Донской В. И. Дискретная математика. – Симферополь: Сонат, 2000. –356 с.
|
|
Лекция 1. Предмет, мета та задачі дискретної математики
1) Основные понятия теории булевых функций [1,2,3,5]
Вектор , координаты которого принимают значения из множества {0,1}, называется двоичным (булевым) вектором длины n.
Множество всех булевых векторов длины n называется единичным n-мерным кубом и обозначается Bn. Весом или нормой вектора называется число |||| =.
Множествовсех вершин куба, вес которых равен k, называется k -м слоем куба Bn. Число называется номером вектора .
Число — называется расстоянием Хемминга.
Наборы (векторы) и называются соседними, если , и противоположными, если .
Говорят, что набор предшествует набору(обозначение: ), если для всех i =1 ,...,n ai bi. Если при этом , то говорят, что строго предшествует (обозначение ). Если выполняется условие () или (), то и называют сравнимыми наборами, иначе — несравнимыми. Последовательность вершин куба Bn называется цепью, соединяющей и , если для i= 1 ,..,k, все вершины в последовательности различны. Число k называется длиной цепи. Цепь называется возрастающей, если для i= 1 ,...k. Если , то цепь называют циклом.
Множество всех наборов (a 1 ,...,an) из , у которых aij =.
(j= 1 ,...,k), называется гранью куба Bn. Множество номеров перeменных I= { i 1 ,...,ik } называется направлением грани, число k — рангом грани, (n-k) — размерностью грани. Интервалом куба Bn называется множество вида . Число называется размерностью интервала.
2) Реализация булевых функций формулами [1,2,3,5]
Функция f (), определенная на множестве Bn и принимающая значения из множества {0,1}, называется функцией алгебры логики или булевой функцией. Множество всех булевых функций обозначается P 2.
|
|
Функциональные символы: & - конъюнкция, - сумма по модулю 2, - импликация, V - дизъюнкция, ~ - эквивалентность, / - штрих Шеффера, - стрелка Пирса называются логическими связками.
Элементарные булевы функции:
- одной переменной:
X | 1 | 0 - тождественный ноль 1 - тождественная единица | |||
x - тождественная функция | |||||
- инверсия (отрицание) |
- двух переменных:
x | y | x & y | x V y | x y | x~y | x y | x/y | x y |
Функция из P 2 зависит существенным образом от аргумента , если существуют такие значения переменных , что . В этом случае переменная называется существенной. Если не является существенной переменной, то она называется фиктивной.
Формулой над множеством функциональных символов Ф называется вся-кое (и только такое) выражение вида: 1) и , где – нуль-местный, а — n -местный функциональные символы и – символы переменных; 2) , где — s -местный функциональный символ и — либо формула над Ф, либо символ переменной.
Формула называется тождественно истинной (тождественно ложной), если реализуемая ею функция равна 1 (соответственно 0).
3) Основные тождества [1,2,3,5]
x* y=y*x — коммутативность любой операции * из {&,V, ,~,/, }
(x * y) * z = x * (y * z) — ассоциативность любой операции * из {&,V, ,~}
= и = — тождества де Моргана
x V (x & y) = x и x & (x V y) = x — правила поглощения
и
дистрибутивность:
x &(y V z) = (x & y) V (x & z) — конъюнкции относительно дизъюнкции
x V (y & z) = (x V y) & (x V z) — дизъюнкции относительно конъюнкции
x & (y z) =(x & y) (x & z) — конъюнкции относительно сложения по mod 2
0 = x & = x &0 = x x, x = = x V x = x & x = x &1 = x V 0
1 = x V = x V1 = x~ x, = x 1, x~ y= (x y) 1
Литература:
1. Яблонский С.В. Введение в дискретную математику. М.:Высш. шк., 2001. – 384 с.
2. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. М.: Наука, 1977. – 386 с.
3. Гиндикин С. Г. Алгебра логики в задачах. М.: Наука, 1972.- 288 с.
4. Грэхем Р., Кнут Д., Паташник О. Конкретная математика (основание информатики). М.: Мир, 1998. – 703 с.
5. Донской В. И. Дискретная математика. – Симферополь: Сонат, 2000. –356 с.