Тема 1: Теория булевых функций и теория k-значных функций

Тема 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-мерным кубом и обозначается Bⁿ. Весом или нормой вектора называется число |||| =.

Множествовсех вершин куба, вес которых равен k, называется k -м слоем куба Bⁿ. Число называется номером вектора .

Число — называется расстоянием Хемминга.

Наборы (векторы) и называются соседними, если , и противоположными, если .

Говорят, что набор предшествует набору(обозначение: ), если для всех i =1 ,...,n a_i b_i. Если при этом , то говорят, что строго предшествует (обозначение ). Если выполняется условие () или (), то и называют сравнимыми наборами, иначе — несравнимыми. Последовательность вершин куба Bⁿ называется цепью, соединяющей и , если для i= 1 ,..,k, все вершины в последовательности различны. Число k называется длиной цепи. Цепь называется возрастающей, если для i= 1 ,...k. Если , то цепь называют циклом.

Множество всех наборов (a ₁ ,...,a_n) из , у которых a_ij =.

(j= 1 ,...,k), называется гранью куба Bⁿ. Множество номеров перeменных I= { i ₁ ,...,i_k } называется направлением грани, число k — рангом грани, (n-k) — размерностью грани. Интервалом куба Bⁿ называется множество вида . Число называется размерностью интервала.

2) Реализация булевых функций формулами [1,2,3,5]

Функция f (), определенная на множестве Bⁿ и принимающая значения из множества {0,1}, называется функцией алгебры логики или булевой функцией. Множество всех булевых функций обозначается P ₂.

Функциональные символы: & - конъюнкция, - сумма по модулю 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 ₂ зависит существенным образом от аргумента , если существуют такие значения переменных , что . В этом случае переменная называется существенной. Если не является существенной переменной, то она называется фиктивной.

Формулой над множеством функциональных символов Ф называется вся-кое (и только такое) выражение вида: 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

Дата добавления: 2014-01-04