ДМ_Конспект

Схематически выполнение операции представлено на рис. 5.9.

Рисунок 5.9 Схема выполнения операции деления отношений ( )

Пример.

Выполним проекцию отношения СТУДЕНТ_КН-01 по атрибутам Фамилия, Инициалы, т.е. ФАМИЛИЯ СТУДЕНТ_КН_01= ФамилиябИнициалы(СТУДЕНТ_КН-01).

ФАМИЛИЯ СТУДЕНТ_КН_01

Фамилия	Инициалы
Алексеев	И.А.
Быкова	Н.А.
Дроздов	И.К.
Кузнецова	Е.В

Затем произведем деление отношения НОМЕР на отношение ФАМИЛИЯ СТУДЕНТ_КН_01.

В результате деления получим таблицу номеров студентов группы КН-01. НОМЕР ФАМИЛИЯ СТУДЕНТ_КН_01

Зачетка №	Студ. №
11197	784567
11216	784588
11193	784611
11195	785587

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

5.3 Контрольные вопросы и задания

1.Какое функциональное отношение называется всюду определенным?

2.Как выглядит матрица функционального отношения?

3.Какое функциональное отношение называют отображением множества X в Y ?

4.Что такое сюръекция?

5.Что такое инъекция?

61

6.Что такое биекция?

7.Какое отображение называется взаимно однозначным?

8.Что называется образом элемента?

9.Что такое прообраз элемента?

10.Перечислите основные свойства отображений.

11.Что представляет собой реляционный метод построения баз данных?

12.Что называется кортежем, атрибутом, доменом?

13.Перечислите теоретико-множественные операции, применяемые при работе с реляционными базами данных. Объясните принцип их выполнения.

14.Перечислите специальные реляционные операции. Объясните принцип выполнения каждой из них.

ЛЕКЦИЯ 6. ДВУЗНАЧНАЯ ЛОГИКА. БУЛЕВЫ ФУНКЦИИ. ОСНОВНЫЕ

ПОНЯТИЯ

6.1 Двузначная логика

В данном разделе курса «Дискретная математика» рассматриваются базовые элементы аппарата двузначной логики (который был разработан Д. Булем в середине ХІХ века) − булевы функции и преобразования над ними.

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

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

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

Понятия, методы и средства данного типа логики лежит в основе современных компьютерных технологий.

6.2 Булевы переменные и функции

Рассмотрим основные понятия и определения алгебры логики.

Пусть задано двухэлементное множество B и двоичные переменные, принимающие значения из B . Элементы B часто обозначают 0 и 1, однако они не являются числами в обычном смысле. Наиболее распространенная интерпретация двоичных переменных – логическая: «нет» – «да», «истинно» (и)

62

– «ложно» (или), «false» – «true». Будем считать, что B {0, 1}, рассматривая 0

и 1 как формальные символы, не имеющие арифметического смысла.

Определение.

Переменные, которые могут принимать значения только из множества B , называются булевыми или логическими переменными. Элемент 1 называется

единичным элементом, или единицей; элемент 0 называется нулевым элементом, или нулем. Сами значения 0 и 1 называются булевыми

константами.

Пример.

Булевыми переменными, которые способны принимать лишь два различных значения, характеризуются объекты с двумя возможными состояниями (наличие или отсутствие у объекта определенного признака, низкое или высокое напряжение, истинное или ложное высказывание).

Пример.

В языках программирования для работы с такими переменными, как правило, вводится специальный логический тип (например, в языках Pascal и Java boolean, в C bool). Переменная этого типа принимает два значения

«false» и «true».

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

Определение.
Функция вида y f (x1, x2 , ..., xn ) ,			аргументы xi	и значения	y которой
принадлежат	множеству	B ,	называется	n -местной	булевой

(переключательной, логической) функцией.

Важнейшая особенность булевых функций состоит в том, что они, как и их аргументы, принимают свои значения из двухэлементного множества B {0, 1}, т.е. характеризуются одним из двух возможных состояний.

Пример.

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

Определение.

Совокупность конкретных значений аргументов булевой функции называется кортежем, двоичным словом ( n -словом) или булевым набором длины n и обозначается как (x1 , x2 , ..., xn ) . Для булевой функции

y f (x1, x2 , ..., xn ) конкретное (индивидуальное) значение булевого набора

(x1 , x2 , ..., xn ) называется также интерпретацией булевой функции f.

63

Пример. Для булевой функции y f (x1 , x2 ) кортежами являются следующие совокупности конкретных значений аргументов: (0, 0) , (0, 1) , (1, 0) ,

(1, 1) ; для булевой функции		y f (x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 ) кортежами
являются:	(0, 0, 0, 0, 0, 0, 0, 0) ,	(0, 0, 0, 0, 0, 0, 0, 1),	(0, 0, 0, 1, 0, 0, 0, 0),
(1, 0, 1, 0, 1, 0, 1, 0) и т.д.

6.3 Область определения и область значений булевой функции

Определение.

Множество всех двоичных слов, обозначаемое как Bn , называется n-

мерным булевым кубом и содержит 2n элементов-слов, т.е. | Bn | 2n .
Пример.
В	множество двоичных слов для булевой функции			y f (x)	входит
| B1 | 21	2 слова: (0) и (1); в множество двоичных слов для булевой функции
y f (x , x , x ) входит | B3 | 23 8 слов: (0, 0, 0) , (0, 0, 1)			,	(0, 1, 0) ,	(0, 1, 1) ,
1	2	3
(1, 0, 0) ,	(1, 0, 1) , (1, 1, 0) , (1, 1, 1) .

Определение.

Областью определения булевой функции от n -переменных служит множество слов длины n , которые представляют собой всевозможные наборы

из n двоичных цифр и их общее количество равно 2n .

Определение.

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

Пример.

Булева функция от двух элементов является полностью определенной, если указаны еѐ значения для каждого из четырех возможных наборов ( 22 4 ),

функция трех аргументов – на 8 ( 23 8 ) наборах также будет полностью определенной.

Теорема 6.1

Число всех функций, зависящих от n переменных x1 , x2 ,...,xn , равно 22n .

Действительно, булева функция n аргументов определена на 2n наборах, на которых она может принимать «0» или «1» из общего количества 2n . Поэтому в соответствие каждой булевой функции можно поставить 2n - разрядное двоичное число. Но количество различных 2n -разрядных чисел равно 22n , а следовательно и количество различных булевых функций равно

22n .

64

Пример. От двух аргументов x1 , x2 существует 16 булевых функций, т.е.

22n 222 24 16 ;	от	трех – 256 ( 22n 223	28	256 ), от четырех – 65536
функций ( 22n 224	216	65536 ).

6.4 Способы задания булевых функций

Существует четыре способа задания булевой функции:

вербальный (словесный);

табличный (с помощью таблицы истинности);

порядковым номером, который имеет функция;

аналитический (в виде формулы).

Задание булевых функций при помощи таблиц. Булевы функции можно задавать с помощью таблиц, подобных таблицам сложения и умножения одноразрядных чисел. В левой части такой таблицы перечисляются все 2n наборов значений переменных (булевых наборов длины n ), а в правой части − значения функций на этих наборах. Этот способ задания универсален, т.е. пригоден для любой функции, однако громоздок, поэтому применяется для задания функции небольшого числа переменных.

Определение.

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

истинности (соответствия) булевой функции.

В таблице истинности каждой переменной x1 , x2 , ..., xn и значению самой функции y f (x1, x2 , ..., xn ) соответствует по одному столбцу, а каждой

интерпретации по одной строке. Интерпретации расположены в определенном порядке − лексикографическом, который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа.

Пример.

Таблица истинности функции f (x1, x2 , x3 ) может иметь следующий вид

(табл. 6.1).

Таблица 6.1 – Пример таблицы истинности функции f (x1, x2 , x3 )

x0	x1	x2	f (x1, x2 , x3 )
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0
			65

В столбцах 1, 2, 3 даны все возможные кортежи значений трех аргументов, т.е. сочетание нулевых и единичных значений трех аргументов. В столбце 4 – значения функции f (x1, x2 , x3 ).

Рассмотрим булевы функции, которые зависят от одной и двух переменных.

Булевы функции, которые зависят от одной переменной, приведены в

табл. 6.2 (их количество равно 22n 221					22 4 ).
Таблица 6.2 Таблица истинности для булевых функций одной
переменной
		y0 f0 (x) 0		y1 f1 (x) x							y3 f3 (x) 1
	x					y f		(x) x
						2	2
	0	0			0		1				1
	1	0			1		0				1
Две функции y0 f0 (x)				и y3	f3 (x)	представляют					собой функции-

константы:

f0 (x) является абсолютно ложной (константа нуля);

f3 (x) является абсолютно истинной (константа единицы).

Функция f1 (x) (функция повторения аргумента) повторяет значения переменной x и поэтому просто совпадает с ней. Функция f2 (x) x ,

называемая отрицанием или инверсией ( x читается «не x »), является единственной нетривиальной функцией. Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.

Всевозможные булевы функции двух переменных f (x1, x2 ) представлены

в табл. 6.3 (их количество равно 22n														222 24				16 ).
	Таблица 6.3 Таблица истинности для булевых функций двух
переменных
	x1		x2		f0	f1		f2		f3		f4	f5		f6		f7	f8	f9	f10		f11		f12		f13		f14	f15
	0	0			0	0		0		0		0	0		0		0	1	1	1		1		1		1		1	1
	0	1			0	0		0		0		1	1		1		1	0	0	0		0		1		1		1	1
	1	0			0	0		1		1		0	0		1		1	0	0	1		1		0		0		1	1
	1	1			0	1		0		1		0	1		0		1	0	1	0		1		0		1		0	1
	В табл. 6.4 приведена характеристика булевых функций двух
переменных.
	Таблица 6.4 Характеристика булевых функций двух переменных
Функ-				Обозначения											Названия									Чтение
ция					(другие
				обозначения)
f0						0					Константа 0						(тождественный							Константа 0
											нуль, всегда ложно)													(Любое 0)
f1					x1 x2 x1 x2						Конъюнкция						(произведение,								x1	и x2
														66

( x1 & x2 ; x1 x2 )

пересечение, логическое «и»)

(и x1 и x2 ).

(AND, И)

Истинна тогда,

когда истинны обе

переменные

f2

Отрицание

импликации

x1 , но не x2

x x

1

2

(запрет)

( x1 x2 ; x1 \ x2 )

(>)

f3

x1

Повторение

(утверждение)

Как x1

первого аргумента

f4

Отрицание

обратной

Не x1 , но x2

x x

1

2

импликации

( x1 x2 ; x2 \ x1 )

f5

x2

Повторение второго аргумента

Как x2

f6

x1 x2

Сумма

по

модулю

2

x1 не как x2

(x1 x2 ;

x1 x2 )

(неравнозначность,

(или x1 или x2 ).

(

антиэквивалетность)

Истинна, когда

, , ,! , XOR

истинны или x1 ,

)

или x2 в

отдельности

f7

x1 x2

Дизъюнкция

(логическая

x1

или x2

( x1 x2 ; x1 x2 )

сумма, логическое «или»)

( x или хотя бы

1

(OR, ИЛИ)

x2 ).

Истинна тогда,

когда истинны или

x1 , или x2 , или обе

переменные

f8

x

x

2

Стрелка

Пирса

(функция

Не x1 и не x2 .

1

Вебба,

отрицание

Истинна только

( x1 x2 ;

x1 x2 )

дизъюнкции)

тогда, когда x1 и

x2

ложны

f9

x1 ~ x2

Эквиваленция

x1

как x2

(

(равнозначность,

( x1 , если, и только

эквивалентность)

x1 x2 ; x1 x2 ; x1 x

если x2 )

)

(Eqv)

f10

Отрицание (инверсия) второго

Не x2

x

2

аргумента

'

x2 )

( x2

;

f11

x1 x2

Обратная

импликация

Если x2 , то x1

( x1 x2 ; x1 x2 )

(обратное

разделение

с

( x1 или не x2 )

запретом)

67

f12			x					Отрицание (инверсия) первого		Не x1
	1							аргумента
	'
		( x1 ; x1 )
f13		x1 x2						Импликация	(следование,	Если x1 , то x2
	( x1 x2 ; x1 x2 )							селекция)		(не x1 или x2 ).
		(Imp)								Ложна тогда и
										только тогда,
										когда x1 истинна и
										x2	ложна
f14		x1 | x2						Штрих Шеффера	(отрицание	Не x1	или не x2 .
								конъюнкции,		Ложна только
	( x1 x2 ; x1 & x2 )
								несовместимость,	логическое
										тогда, когда x1 и
								«не-и»)
										x2 истинны
f15	1							Константа 1 (тождественная		Константа 1
								единица, всегда истинно)		(Любое 1)

Шесть из приведенных функций не зависят от							x1	или x2	(или от обоих
вместе). Это две константы ( f0 0 и f15 1), повторения ( f3									x1 , f5 x2 ) и
отрицания ( f10 x2 и f12			x1 ), являющиеся функциями одной переменной ( x1
или x2 .) Из остальных			десяти			функций две ( f4	и	f11 ) отличаются от
соответствующих им ( f2			и f13 )			лишь порядком расположения элементов и

поэтому не являются самостоятельными. Поэтому из 16 функций двух

переменных	только	восемь	являются	оригинальными
( f1, f2 , f6 , f7 , f8 , f9 , f13, f14 ).

В математической логике часто употребляются так называемые элементарные функции, которые играют такую же важную роль, как, например,

xn или sin x в математическом анализе. Элементарные логические функции –

6это одноместные и двухместные логические функции.

Примеры элементарных функций одной переменной приведены в табл. 6.2. Примеры элементарных функций двух переменных представлены в табл.

6.3 и 6.4, это: отрицание		f10 x2			( f12 x1 ); дизъюнкция f7				x1 x2 ; конъюнкция
f1 x1 x2 ;	импликация	f13 x1			x2 ;		эквивалентность		f9 x1 ~ x2 ; сумма по
модулю 2 f6	x1 x2 ; штрих Шеффера						f14 x1 | x2 ; стрелка Пирса			f8 x1 x2 .
Булевы функции		можно			рассматривать как логические					операции над

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

отрицание (функция y f (x) , принимающая значения 1, когда x 0 ,

изначение 0, когда x 1);

дизъюнкция (функция y f (x1 , x2 ) x1 x2 , принимающая значение 0

тогда и только тогда, когда оба аргумента имеют значение 0);

68

конъюнкция (функция y f (x1, x2 ) x1 x2 , принимающая значение 1

тогда и только тогда, когда оба аргумента имеют значение 1).

Задание булевой функции порядковым номером. Каждой функции присваивается порядковый номер в виде натурального числа, двоичный код которого представляет собой столбец значений функции в таблице истинности. Младшим разрядом считается самая нижняя строка (значение функции на интерпретации (1, 1, 1, ...,1) , а старшим самая верхняя (значение функции на

интерпретации (0, 0, 0, ...,0)). Указанный порядковый номер функции, как

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

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

Пример.

Найдем порядковый номер функции f (x1, x2 , x3 ) , которая задана таблицей истинности (см. табл. 6.1). Для этого переведем двоичное число 010111002 в

десятичную систему счисления:

010111002 0 27 1 26 0 25 1 24 1 23 1 22 0 21 0 20 32 16 8 4 60

Кортеж значений аргументов (интерпретацию) также можно рассматривать как запись целого положительного числа в двоичной системе счисления. Первая интерпретация в таблице истинности называется нулевой, последняя – единичной (номер интерпретации 2n 1, где n – количество аргументов функции).

Определение.

Десятичный эквивалент двоичного представления интерпретации

называется номером интерпретации (кортежа).
Пример.
Шестой	интерпретацией		является	(1, 1, 0) ,	т.е.
1 22 1 21 0 20 4 2 0 6 .
Пример.
Пусть функция		f (x, y, z)	принимает единичные значения		на
интерпретациях 1,	4, 7.	Тогда, используя числовую форму записи, функция

3

будет иметь вид: f (x, y, z) F (1,4,7) , что означает, что функция принимает

1

единичные значения на наборах 1, 4 и 7.

6.5 Реализация булевых функций формулами

Булевы функции могут быть заданы аналитически, т.е. формулами (аналитическими выражениями).

Определение.

69

Формула – это выражение, содержащее булевы функции и их суперпозиции.

Пример.

Формулы булевой алгебры можно представить следующим образом:

{[(x1 x2 ) x1 ] x2}; [ x1 (x1 x2 ) ], {x1 [(x2 x3 )(x3 x2 )]}.

Определение.

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

Пример.
Рассмотрим	формулу, задающую				функцию f (x, y, z) следующим
				формула содержит функции: g(x1 )
образом f (x, y, z) (x y) z . Эта
отрицание, s(x1, x2 )	конъюнкцию,			l(x1, x2 )	дизъюнкцию. Данную формулу

можно представить в виде суперпозиции указанных функций следующим образом: f (x, y, z) l(s(x, g( y)), z)

Как и в элементарной алгебре, в алгебре логики можно строить формулы, исходя из элементарных функций.

При образовании (построении) формул используются знаки (символы) трех категорий:

1)символы первой категории обозначают переменные: x, y, a, b, c,...;

2)символы логических операций , , , , и т.д.;

3)пары символов (), [], {}.

Если в формуле отсутствуют скобки, то операции выполняются в следующей последовательности: отрицание, конъюнкция, дизъюнкция,

импликация, и эквивалентность: , , , , ~ .

Определение.

Запись формул, при которой знаки функций стоят между аргументами, называют инфиксной (в дальнейшем будем пользоваться такой формой записи).

Формула каждому набору значений аргумента ставит в соответствие значение функции и, следовательно, может служить, наряду с таблицей, способом задания и вычисления функций. По формуле можно восстановить таблицу функций.

Определение.

О формуле, задающей функцию, говорят также, что она реализует или

представляет эту функцию.

В отличие от табличного задания представление булевой функции формулой не единственно.

Определение.

70