1

67

• Содержание
• 1. ТЕОРИЯ МНОЖЕСТВ
• 1.1 Понятие множества и подмножества
• 1.2 Графическая интерпретация множеств и операций над ними
• 1.3 Свойства операций
• 1.4 Тождества и их доказательство
• 1.5 Отношения на множествах
• 1.6 Свойства отношений
• 1.7 Отношение порядка
• 1.8 Отношение эквивалентности
• 2 МАТЕМАТИЧЕСКАЯ ЛОГИКА. АЛГЕБРА ЛОГИКИ
• 3. БУЛЕВА АЛГЕБРА
• 3.1 Совершенные нормальные формы
• 3.1.1 Совершенная дизъюнктивная нормальная форма
• 3.1.2 Разложение по переменным
• 3.1.3 Алгоритм преобразования формулы в СДНФ
• 3.2 Совершенная конъюнктивная нормальная форма (СКНФ)
• 3.2.1 Алгоритм преобразования формулы в СКНФ
• 4 ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
• 4.1 Равносильные формулы и их доказательство
• 4.2 Равносильные формулы
• 4.3 Доказательство равносильностей
• 5. БУЛЕВЫ ФУНКЦИИ
• 5.1 Полнота системы булевых функций
• 6. ЛОГИКА ПРЕДИКАТОВ
• 5.1 Операции над предикатами
• 5.2 Кванторы
• 5.3 Формулы
• 6. ТЕОРИЯ ГРАФОВ
• 6.1 Понятие смежности
• 6.2 Матрица инцидентности и списки ребер
• 6.3 Матрица смежности графа
• 6.4 Операции над членами графов
• 7 ОСНОВНЫЕ ТРЕБОВАНИЯ К ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ
• 8. ЭКЗАМЕНАЦИОННЫЕ ВОПРОСЫ
• 9. ЛИТЕРАТУРА
• Приложение I

1. ТЕОРИЯ МНОЖЕСТВ

1.1 Понятие множества и подмножества

В дискретной математике любое понятие можно определить с помощью понятия множества, с рассмотрения которого мы и начнем наш курс.

Множество - совокупность объектов, различаемых нашей интуицией.

Объекты, составляющие множество называются элементами этого множества.

Множества обозначаются большими латинскими буквами, а элементы - маленькими латинскими буквами.

Если элемент а принадлежит множеству А, то будем использовать запись , в противном случае используется запись .

Множество, содержащее конечное число элементов называется конечным. Если множество не содержит ни одного элемента, оно называется пустым. Если множество содержит все элементы, присутствующие в задаче, то оно называется универсальным и обозначается Е.

Множество можно задать различными способами. Самые распространенные это: перечисление элементов: ; указание свойств элементов: , (после двоеточия указаны свойства х).

Множество А называется подмножеством множества В только тогда, когда любой элемент множества А принадлежит множеству В. записывается это так: если .

- знак нестрогого включения (говорят В содержит или покрывает А).

- знак строгого включения.

- не включение.

Очевидно: если и , то эти множества состоят из одних и тех же элементов и А=В.

1.2 Графическая интерпретация множеств и операций над ними

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

1

67

Над множествами выполняются три двуместные операции:

Пересечение;

Объединение;

Разность множеств.

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

1

67

АВ

Пример:

Объединением множеств А и В (аддитивная операция) называется новое множество С, состоящее из элементов множества А и из элементов множества В.

1

67

АВ

Пример:

Разностью множеств А и В называется новое множество С, состоящее из элементов, принадлежащих множеству А и не принадлежащих множеству В.

1

67

А\ В из А вычесть В

Пример:

.

Кроме рассмотренных двухместных операций существует одна одноместная операция - дополнение. Дополнением множества М является множество (не М) = .

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

1.3 Свойства операций

Ассоциативность;

Коммутативность;

Дистрибутивность.

Операция называется ассоциативной, если выполняется равенство:

.

Выполнение этого условия (свойства ассоциативности) означает, что скобки в выражении можно не расставлять. Сложение и умножение чисел - ассоциативные операции, что и позволяет не ставить скобки (пример: a+b+c; abc) пример неассоциативной операции: возведение в степень (a^b)^c здесь скобки необходимы.

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

Операция называется дистрибутивной, если выполняется условие: .

1.4 Тождества и их доказательство

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

Доказать, что M=N, где M и N - выражения с множествами.

Доказательство производится в два этапа: 1) «в одну сторону», 2) «в обратную сторону».

Сначала предположим, что некий элемент х принадлежит левой части равенства: эта запись звучит следующим образом:

«если , то ».

На втором этапе предполагается, что элемент х принадлежит правой части равенства: .

Пример №1

Доказать тождество:

.

Решение:

;

.

1.5 Отношения на множествах

Отношения бывают одноместными, двуместными (бинарными) и n-местными. Одноместное отношение- это просто подмножество. Мы остановимся на бинарных отношениях.

упорядоченная пара (x, y) есть совокупность двух элементов записанных в определенном порядке.

Две пары (x, y) и (x₁, y₁) считаются равными тогда и только тогда x₁ = х, y₁ = y.

Прямым произведением x y называется совокупность пар (x,y)таких, что .

Можно привести следующие примеры бинарных отношений:

Отношение «иметь общий делитель отличный от 1» выполняется для пар (6,9); (4,2); (2,4); (4,4), но не выполняется для пар (7,9); (4,7).

Отношение «быть делителем», т. е. x делит y выполняется для пар (2,4); (4,4), но не выполняется для пар (4,2); (7,9).

Отношение выполняется для пар (7,9); (7,7), но не выполняется для пары (9,7).

1.6 Свойства отношений

1. Рефлексивность;

2. Симметричность;

3. Транзитивность.

Отношение обозначается R и записывается так: xRy (x и y находятся в отношении R).

Отношение R называется рефлективным, если для любого имеет место aRa. Главная диагональ его матрицы содержит только единицы.

Отношение R называется антирефлективным, если для любого не выполняется aRa. Главная диагональ его матрицы содержит только нули. Отношения = - рефлективные, а отношение < - антирефлективное.

Отношение R называется симметричным, если для пары (а,в)из aRb следует bRa, иначе говоря для любой пары отношение выполняется либо в обе стороны, либо не выполняется вообще. Матрица данного отношения симметрична относительно главной диагонали.

Отношение R называется транзитивным, если для любых a,b,c из aRb и bRс следует aRс отношения = - транзитивны, отношение «пересекаться» - нетранзитивно. (Пример: пересекается с пересекается с , однако и не пересекаются).

Задание №2

Установите какими свойствами обладает каждое из отношений, заданных на R следующими высказывательными формами:

x+y=2;

Решение:

в данном случае заданы отношения + и .

Подставим в выражение x+y=2 конкретные значения: 1+1=2, последовательно проверим каждое свойство:

Рефлективность: aRа = а+а = 1+1 - условие выполняется , следовательно данное отношение рефлективно.

Симметричность: из aRb следует bRa = из а+b следует b+а = из 1+1 следует 1+1 - условие выполняется, следовательно данное отношение симметрично.

Транзитивность: из aRb и bRс следует aRс данное условие мы проверит не можем, т. к. оно применимо только для трех или более элементов.

1.7 Декартово произведение множеств

Декартовым произведением - XY множеств X и Y называется множество М вида

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

Подмножество FXY называется функцией, если для каждого элемента xX, найдется не более одного элемента yY вида (x,y) F; при этом, если для каждого элемента х имеется один элемент y вида (x,y) F, то функция называется всюду (полностью) определенной, в противном случае - частично определенной (не доопределенной).

Множество Х образует область определения функции F.

Множество Y образует область значений функции F.

Часто вместо (x,y) F пишут у=F(х), при этом элемент х называется аргументом или переменной, а у - значением функции F.

Сопоставим с декартовым произведением двух множеств х=. и у=. прямоугольную решетку, узлы которой взаимно однозначно соответствуют элементам декартова произведения (рис.5).

Подмножества декартова произведения обозначены штриховкой соответствующих элементов.

На рис.5 а) показано подмножество декартова произведения не являющееся функцией.

На рис.5 б) показано подмножество декартова произведения, являющееся полностью определенной функцией.

На рис. 5 в) показано подмножество декартова произведения, являющееся частично определенной функцией.

Количество аргументов определяет местность функции. До настоящего момента были рассмотрены одноместные функции.

Аналогично понятию декартова произведения двух множеств можно определить понятие декартова произведения n-множеств.

Декартовым произведением множеств М₁, М₂,…., М_n называется множество Элементами декартова произведения являются всевозможные последовательности, каждая из которых состоит из n элементов, причем первый элемент принадлежит множеству М₁, второй - множеству М₂, n-ый - множеству М_n.

Если множество М_х в определении функции у=F(x) является декартовым произведением множеств М _х1, М _х2,…., М _хn, то получаем определение n-местной функции у=F(х₁, х₂,….,х_n).

1.8 Функция как отношение

Функцией называется функциональное соответствие.

Если функция f устанавливает соответствие между множествами А и В, то говорят, что функция f имеет тип АВ, обозначается f: АВ. каждому элементу а из своей области определения функция f ставит в соответствие единственный элемент b из области значений. Обозначается f(a)=b.

Элемент а называется аргументом функции, элемент b называется значением функции на а.

Полностью определенная функция f: AB называется отображением А и В.

Областью определения называется выражение D=

Функция называется инъективной, если из отношений (x₁,y)f, (x₂,y)f x₁=x₂

Функция называется сюръективной, если для каждого уY существует хХ.

Инъективная и сюръективная функции образуют биекцию - это взаимнооднозначное отношение множеств.

1.9 Отношение порядка

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

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

Элементы a,b сравнимы по отношению порядка, если выполняется aRb или bRa. Множество М, на котором задано отношение порядка называется полностью упорядоченным, если любые два элемента множества М сравнимы, в противном случае - частично упорядоченным.

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

Отношение эквивалентности

Отношение называется отношением эквивалентности (эквивалентностью), если оно одновременно рефлективно, симметрично и транзитивно.

Примеры:

1. отношение равенства на любом множестве является отношением эквивалентности;

2. утверждение вида (a+b)(b-a)=a²-b² - формулы соединенные знаком равенства задают бинарное отношение. Такое отношение называют отношением равносильности. Оно отличается от равенства, т. к. может выполняться для различных формул.

3. Отношение подобия геометрических фигур, «быть соседями по квартире», «быть ровесниками» так же являются отношениями эквивалентности.

Каждое отношение эквивалентности является в определенном смысле равенством, например, отношение «быть ровесником» означает равенство возрастов.

Задание №3

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

Решение: необходимо проверить каждое из свойств отношений (аналогично заданию №2) и определить эквивалентность или порядок отношений.

2. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ

Модель является отображением чего-либо. В науке о природе моделирование используется как метод познания.

2.1 Преобразование к модели

Эксперимент на модели должен быть проще эксперимента на оригинале.

Информация об объекте, полученная в результате эксперимента на модели должна быть переносима на объект.

Существуют различные модели, которые используют в физике и математике.

В физике под моделью понимается реальный объект, в математике модель не обязательно является реальным объектом. однако суть этих моделей одинакова:

модель должна отражать характеристики и свойства объекта,

модель должна прогнозировать поведение объекта,

модель должна быть более простой, чем оригинал, но с другой стороны она должна как можно полнее отражать свойства объекта.

2.2 Способы моделирования

Макетное. Широко применяется в строительстве.

Физическое. Основой для такого моделирования является теория подобия.

Электрическое моделирование.

Математическое моделирование.

Мы остановимся на математическом моделировании. Модель представляет собой совокупность зависимостей, позволяющих прогнозировать заданные свойсвта объекта. В математике термин «модель» применяется наряду с обычным толкованием. Может означать, например, теорию подобную другой теории. Математика использует символические модели. Такая модель охватывает определенное множество абстрактных объектов: это числа, векторы и т. д. И отношения между ними.

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

Математическая операция по определенному правилу любым двум элементам множества ставит в соответствие третий элемент, принадлежащий этому же множеству.

Характерным для математической модели может быть отсутствие объектов в физическом мире. Такие абстрактные модели являются отражением физических процессов, например, счет, упорядочение и т. д. Однако математическая модель будет воспроизводить физические стороны объекта, если будут установлены правила соответствия специфических свойств объекта математическим объектам и отношениям.

2.3 Алгебраические модели

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

3. ТЕОРИЯ КОДИРОВАНИЯ

В теории передачи информации существует проблема кодирования - декодирования, обеспечивающая надежную передачу информации при наличии помех.

Пусть А и В два конечных алфавита.

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

И R - некоторое множество конечных слов в алфавите А. Однозначное отображение множества R в некоторое множество слов в алфавите В называется кодированием множества R.

Образ С множества R при отображении называется кодом множества R. Слова из С называются кодовыми словами; при этом, если слово w из R отображается в слово v из С, то v называется кодом слова w. Слова из R называются сообщениями, алфавит А - алфавитом сообщений, алфавит В - кодирующим алфавитом. Если кодирующий алфавит В состоит из двух букв (в этом случае будем полагать, что ), то кодирование и соответствующий код С называется двоичным (с ними мы и будем работать).

Код называется равномерным или блочным, если все кодовые слова имеют одинаковую длину.

Блочный двоичный код, в котором каждое кодовое слово имеет длину n, представляет собой подмножество вершин n-мерного куба.

Пример: геометрическая модель трехзначного двоичного кода есть фигура трехзначного пространства, т. е. куб.

b=b₁, b₂, b₃

b=000

b=001

b=010

b=011

b=100

b=101

b=110

b=111

Каждой вершине куба присвоена кодовая комбинация по принципу: если проекция на ось равна нулю, то в комбинации ставится ноль, а если проекция равна единице, то в комбинации ставится единица. Порядок проекций должен быть одним и тем же: b₁, b₂, b₃. Длина ребра куба равна единице. d - это длина между соседними разрядами или кодовое расстояние.

Данный способ кодирования обозначим (2,3). В этой ситуации невозможно ни обнаружить ошибку ни исправить ее.

Пусть разрешенными кодами являются 000 и 111 , тогда количество возможных кодов - 8, количество разрешенных кодов - 2, расстояние между разрешенными кодами = 3.

Для того чтобы определить кодовое расстояние между двумя комбинациями двоичного кода достаточно просуммировать эти комбинации по модулю 2 и подсчитать число единиц в полученной комбинации. Пример:

000

111

. 111 число единиц = 3. Значит d=3.

Получаем сообщение с одной ошибкой в разряде. Тогда отнесем ошибочный код к той вершине, которая отстает на единицу. Вместо ошибочного кода запишем координату вершины (0,0,0), получим исправляющийся код тогда возможны три ситуации:

(3,3) когда количество сообщений = 8, количество кодов = 8. В этом случае ошибочный код будет совпадать с одним из сообщений и поэтому ошибку обнаружить невозможно.

(2,3) количество сообщений = 4, количество кодов = 8, тогда получим 4 разрешенных кода, совпадающих с вершинами (рис. 8).

1

67

Ошибку обнаружить можно, но исправить нельзя.

(1,3) ошибку можно и обнаружить и исправить.

Если мы хотим построить код, который может обнаружить n ошибок, то расстояние между кодовыми словами d = k + 1.

Если мы хотим исправлять ошибку, то расстояние должно быть d=2s+1

Если мы хотим построить код одновременно обнаруживающий и исправляющий ошибку, то минимальное кодовое расстояние должно быть

d=k+s+1.

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

10110 - переданная кодовая комбинация

10010 - 1-я принятая комбинация

10100 - 2-я принятая комбинация

00110 - 3-я принятая комбинация

10110 - накопленная комбинация

Как видим на всех трех комбинациях, были ошибки, но накопленная комбинация ошибок не содержит.

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

3.1 Коды с обнаружением ошибок

Имеем кодовое слово а=а₁, а₂,…, а_m; составляем другое кодовое слово с добавлением символа - b=b₁, b₂…b_m, b_m+1

a_i=b_i

b_m+1=………..

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

3.2 Корректирующие коды

а=а₁, а₂,…, а_m

b= a₁ a₁ a₁, a₂ a₂ a₂,…a_m a_m a_m

a_i=b_i, длина кода 3_m

а₂ а₂ а₂

если 0 0 0, то ошибки нет

если 1 1 1, то ошибки нет

если 0 1 1, то ошибка есть

Такие корректирующие коды надежность, причем их надежность возрастает с увеличением дублирующих, но не экономичны.

Аксиомы расстояния:

d(a,b)0

d(a,b)=0, если a=b

d(a,b)= d(b,a)

d(a,b)+d(b,c) d(a,c)

3.3 Групповые коды

Рассмотрим множество двоичных кодов с заданной операцией (сложение по модулю).

Запишем таблицу истинности для операции «сложение по модулю»

a	b	A+b
0	0	0
0	1	1
1	0	1
1	1	0

a+(b+c)=(a+b)+c

a+b=b+a

a+a=0, (a^-1=a)

a+0=a

На множестве кодов задана группа (В,+,0) в свою очередь множество принятых сообщений С образуют группу (С,+,0). Для рассмотренного примера множество кодов b= c=. Очевидно, что множество b является подгруппой множества С.

3.4 Классы

классы.

Смежным классом В и С называется множество В+С, где С - фиксированный элемент, а b пробегает все значения множества В. для примера построим левый смежный класс.

Два смежных класса пересекаются либо совпадают, а множество левых классов образуют разбиение множества С.

Восемь левых смежных классов:

b c

000 +000=000 000+111=111

001+000=001 001+111=110

010+000=010 010+111=101

011+000=011 011+111=100

100+000=100 100+111=011

101+000=101 101+111=010

110+000=110 110+111=001

111+000=111 111+111=000

I	II
000	111
001	110
010	101
011	100

Столбцы данной таблицы есть разбиение множества С. Известно, что разбиение определяет некоторое отношение эквивалентности, тогда процесс декодирования можно производить следующим образом: допустим, что получено сообщение С_i =011. Таким образом теория групп может рассматриваться математической основой теории кодирования.

ЛИНЕЙНАЯ АЛГЕБРА

Вектор (0, 0, ,0) со всеми координатами равными нулю, называется нулевым. Это единственный n-мерный вектор, для которого выполняются условия:

Если r^/, то r^/+= r^/

Если r^/, то r^/-= r^/

Если r^/, то r^/- r^/=

Если r^/, то 0* r^/=

Если а, то а*=

РЕЛЯЦИОННАЯ АЛГЕБРА

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

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

Пример: с помощью операции выбора построим отношение R^/₅ (расписание экзаменов профессора Иванова). Результатом операции выбора являются строки, в которых домен (столбец) D₃ представлен значением профессор Иванов: это 1,6,8-я строки.

Таб.1

R5	D1	D2	D3	D4	D5
1	K 5-01	Теория автоматов	Пр. Иванов	03.01	Ауд.210
6	K 5-02	Теория автоматов	Пр. Иванов	09.01	Ауд.211
8	K 5-04	Матем. статистика	Пр. Иванов	10.01	Ауд.210

Для определения проекций отношений множество в реляционной алгебре разбивается на два подмножества в случае бинарного отношения и на n подмножеств в случае n-арного отношения:

,

Проекцией П_р (R₂/A) бинарного отношения R₂, R₂на А называется множество элементов .

Проекцией П_р (R₂/A_i1, A_i2,…A_in) n-арного отношения называется множество кортежей (а_i1, a_i2,…,a_im), где , каждый из которых является частью элемента n-арного отношения R_n. операция проекции определяет построение «вертикального» подмножества отношения, т. е. множество подмножества кортежей, получаемого выбором одних доменов и исключения других доменов.

Пример: проекция П_р(R₅/D_2,, D₃) порождает множество пар, каждая из которых определяет дисциплину и экзаменатора.

Таб. 2

R2	D3	D3
	теория автоматов	пр. Иванов
	математическая статистика	пр. Петров
	физика	пр. Сидоров
	алгоритмические языки	пр. Иванов

одинаковые строки в таблице объединены в одну.

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

Пример: найдем по двум заданным таблицам (таб.3.а, таб.3_.б) результат операции соединения по домену D₁ (таб.3.в)

Таб. 3.а

R5	D1	D2	D3	D4	D5
	K5-01	теория автоматов	пр. Иванов	03.01	ауд. 210
	K5-02	математ. статистика	пр. Петров	03.01	ауд. 211
	K5-03	физика	пр. Сидоров	05.01	ауд. 211
	K5-04	алгоритмич. языки	пр. Иванов	05.01	ауд. 210

Таб.3б

R5	D1	D2	D3	D4	D5
	K5-01	физика	пр. Сидоров	09.01	ауд. 210
	K5-04	математ. статистика	пр. Иванов	10.01	ауд. 210
	K5-02	теория автоматов	пр. Иванов	09.01	ауд. 211
	K5-03	алгоритмич. языки	пр. Петров	10.01	ауд. 211

Таб.3в

R5	D1	D2	D3	D4	D5	D/2	D/3	D/4	D/5
	K5-01	теор.автом.	пр. Ив	03.01	а.210	физика	пр.Сид	09.01	а.210
	K5-02	мат. стат.	пр. Пет	03.01	а.211	т. авт.	пр.Ив	09.01	а.211
	K5-03	физика	пр. Сид	05.01	а.211	алг.яз.	пр.Пет	10.01	а.211
	K5-04	алг. языки	пр. Ив	05.01	а.210	мат. ст.	пр.Ив	10.01	а.210

Аналогично можно определить операцию соединения не только по условию «равенства», но и по другим условиям сравнения: <,>. Определим например операцию соединения по условию > соединение по условию > отношения R_а по атрибуту х и отношения R_b по атрибуту у (атрибуты х, у являются атрибутами одного и тог же домена общего для отношений R_{а ,} R_b ), х>у называется множество всех кортежей , таких, что - конкатенация кортежа а_i, принадлежащего R_b, где х - часть а_i, у - часть b_i и х>у.

Запрос в реляционной БД будет выполнен тем быстрее, чем меньше операций над отношениями он содержит Таким образом представляет практический интерес рассматриваемая выше задача упрощения представления множества через введенные операции.

2 МАТЕМАТИЧЕСКАЯ ЛОГИКА. АЛГЕБРА ЛОГИКИ.

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

Алгебра образованная множеством В вместе со всеми возможными операциями на нем, называется алгеброй логики.

Функцией алгебры логики (или логической функцией) от n-переменных, называется n-арная операция на В.

Логическая функция f (x_1,…x_n) - это функция принимающая значения 0,1. Множество всех логических функций обозначается Р₂, множество всех логических функций от n-переменных обозначается Р₂(n). Всякая логическая функция может быть задана таблицей, в левой части которой перечислены все наборы переменных, а в правой части - значения функции на этих наборах.

Переменная х_i в функции f(x_1,…x_i, x_i, x_i+1,…,x_n) называется несущественной (или фиктивной), если f(x_1,…x_i, 0, x_i+1,…,x_n) = f(x_1,…x_i,1,x_i+1,…,x_n) при любых значениях остальных переменных, т. е. если изменение значения x_i в любом наборе значений x_1,…x_i не меняет значение функции. Говорят, что функция g получена из функции f удалением фиктивной переменной и наоборот, причем эти функции считаются равными.

Пример: f(x₁ x₂ x₃ x₄) = g(x₁,x₂) означает, что при любых значениях x₁ и x₂ f=g незавасимо от значения x₃. Удаляют фиктивные переменные поскольку они не влияют на значение функции и являются с этой точки зрения лишними.

Рассмотрим примеры логических функций:

Одна переменная Х имеет 4 логических функции, которые приведены в таблице 1.

Таб.1.

Х	F0	F1	F2	F3
0	0	0	1	1
1	0	1	0	1

Функции F₀ и F₃ - константы 0 и 1 соответственно;

Функция F₁ (х) = х, т. е. функция F₁ повторяет х;

Функция F₂ (х) является отрицанием х (логическая операция НЕ) и обозначается .

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

Две переменные имеют 16 логических функций (таблица 2).

Таб. 2

х1	х2	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

Все функции в таблице 2 являются бинарными (для двух переменных).

Функции F₀ и F₁₅ - константы 0 и 1;

Функция F₁ (х_1, х₂) называется конъюнкцией х₁ и х_2, обозначается: &,,но чаще всего значок конъюнкции опускают, аналогично знаку умножения. Она ровна единице только тогда когда х₁ и х₂ =1. В остальных случаях она ровна 0. Это функция логического «И» или функция логического умножения.

Функция F₇ (х_1, х₂) называется дизъюнкцией х₁ и х_2, обозначается +,. Она ровна 1, если хотя бы одна переменная равна 1. Это функция логического «ИЛИ» или функция логического сложения.

Функция F₆ (х_1, х₂) - сложение по модулю 2, обозначается . Она ровна 1 когда значения ее аргументов различны и ровна 0 когда значения ее аргументов ровны, поэтому эта функция называется неравнозначностью.

Функция F₉ (х_1, х₂) - эквивалентность (равнозначность), обозначается «». Она ровна 1 когда аргументы ровны и ровна 0 когда аргументы различны.

Функция F₁₃ (х_1, х₂) - импликация, обозначается . Звучит данная функция так: “если х_1, то х₂ “ .

Функция F₈ (х_1, х₂) - стрелка Пирса, обозначается

Функция F₁₄ (х_1, х₂) - штрих Шеффера, обозначается х_1, х₂

Остальные функции своего названия не имеют, и легко выражаются через перечисленные выше функции.

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

Задание №4

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

Таб. 3

X	Y				f
0	0	1	0	1	1
0	1	1	0	1	1
1	0	0	0	0	1
1	1	1	1	0	1

3. БУЛЕВА АЛГЕБРА

Множество В, на котором определены две бинарные операции (конъюнкция и дизъюнкция) и одна унарная операция (отрицание ) и выделены два элемента 0 и 1 называется булевой алгеброй.

Причем для этих операций необходимо выполнение следующих свойств:

Ассоциативность

Коммутативность

Дистрибутивность конъюнкции относительно дизъюнкции

Дистрибутивность дизъюнкции относительно конъюнкции

Идемпотентность

Двойное отрицание

Свойства констант

Правила де Моргана

Закон противоречия

Закон исключенного третьего

В алгебре логики эти законы называются равносильностями.

3.1 Совершенные нормальные формы

3.1.1 Совершенная дизъюнктивная нормальная форма

Введем обозначения:

; А^А=1; Х^А=1, если Х=А, Х^А=0, если ХА.

Формула Х^А_1……Х^А_n, где А=- какой-либо двоичный набор, а среди переменных Хi могут быть совпадающие называется элементарной конъюнкцией.

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

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

Например: 1) (значок конъюнкции в данном случае опущен).

1),4) - правильные элементарные конъюнкции;

2)- переменная х входит один раз сама и второй раз под знаком отрицания;

- переменная y входит трижды: один раз сама и два раза под знаком отрицания.

Правильная элементарная конъюнкция называется полной относительно переменных х₁…..х_n, если в нее входит каждая их этих переменных причем только один раз (может быть и пол знаком отрицания).

Например: из перечисленных в предыдущем примере конъюнкций полной является только 4) относительно переменных x,y,z,t; а относительно переменных x,y,z полной является только 1).

Совершенной дизъюнктивной нормальной формой (СДНФ) относительно переменных х₁…..х_n называется дизъюнктивная нормальная форма_, в которой нет одинаковых элементарных конъюнкций и все элементарные конъюнкции правильны и полны относительно переменных х₁…..х_n

3.1.2 Разложение по переменным

Теорема 1. Всякая логическая функция может быть представлена в СДНФ:

, (1)

где m, а дизъюнкция берется по всем 2^m наборам значений переменных х₁,…х_m . Функция f разложена по первым n-переменным. Данное равенство называется разложением по переменным. х₁,…х_m. Например при n=4, m=2 разложение имеет вид:

теорема доказывается подстановкой в обе части равенства (1) произвольного набора (b₁,…,b_m, b_m+1,…,b_n) всех n-переменных.

При m = 1 из (1) получаем разложение функции по одной переменной:

(2)

Очевидно, что аналогичное разложение справедливо для любой из n- переменных.

Другой важный случай когда n=m. При этом все переменные в правой части (1) получают фиксированные значения и функции в конъюнкции правой части становятся равными 0 или 1, что дает:

, (3)

где дизъюнкция берется по всем наборам (b₁…b_n), на которых f=1. При f=0 множество конъюнкций в правой части пусто. Такое разложение называется совершенной дизъюнктивной нормальной формой. СДНФ функции f содержит ровно столько конъюнкций, сколько единиц получается в таблице истинности f. Каждому единичному набору (b₁,…, b_n) соответствует конъюнкция всех переменных, в которой x_i взято с отрицанием, если b_i =0 b ,и без отрицания, если, b_i=1. Таким образом существует взаимно однозначное соответствие между таблицей истинности функции f и ее СДНФ, и ,следовательно, СДНФ для всякой логической функции единственна. Единственная функция не имеющая СДНФ - это константа 0.

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

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

Действительно, для всякой функции, кроме константы 0, таким представлением может служит ее СДНФ. Константу 0 можно представить булевой формулой:

3.1.3 Алгоритм преобразования формулы в СДНФ

Равенство (3) дает возможность находить СДНФ для функции по ее таблице истинности

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

Таб. 4.

Х1	Х2	Х3	f
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Данная функция имеет следующую СДНФ: . Однако, если функция задана формулой, то строить СДНФ по таблице не рационально, тогда применяют следующий алгоритм: построение СДНФ состоит из двух этапов, каждых из которых состоит их трех шагов. На первом этапе строят ДНФ, а на втором этапе из ДНФ строят СДНФ.

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

импликация

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

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

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

Например:

3 шаг. Если в ДНФ имеется несколько одинаковых элементарных конъюнкций, то мы оставляем только одну (используя свойство идемпотентности: ).

4 шаг. Делаем все элементарные конъюнкции правильными путем одним из следующих преобразований:

если в элементарную конъюнкцию входит некоторая переменная вместе со своим отрицанием, то мы удаляем эту конъюнкцию из ДНФ (используя свойство ).

Если некоторая переменная входит в элементарную конъюнкцию несколько раз, причем или во всех функциях с отрицанием или во всех случаях без отрицания, то мы оставляем только одно вхождение (используя свойство идемпотентности: хх=х).

5 шаг. Делаем все элементарные конъюнкции полными. Если в некоторую конъюнкцию не входит переменная y , то необходимо рассмотреть равносильное выражение и вновь применить шаг 2. Если недостающих переменных несколько, то нужно добавить несколько конъюнктивных членов вида .

6 шаг. После применения 5-го шага могут вновь появится одинаковые конъюнкции. Поэтому на шестом шаге применяют шаг 3.

Задание №5.

Найти СДНФ для следующей формулы:

=

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

Используя свойство , получим

используя свойство ,получим

=

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

Используя свойство дистрибутивности получим

=

3. шаг. Все конъюнкции получились правильными, делаем их полными

4. шаг. Одинаковых конъюнкций нет, следовательно оставляем их все.

получили совершенную дизъюнктивную нормальную форму.

(в конце примера опущен знак конъюнкции)

3.2 Совершенная конъюнктивная нормальная форма (СКНФ)

Формула вида , называется элементарной дизъюнкцией.

Всякая конъюнкция элементарных дизъюнкций называется, конъюнктивной нормальной формой

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

Правильная элементарная дизъюнкция, называется полной относительно переменных х₁…х_{n ,} если в нее входит каждая их этих переменных причем только один раз (может быть и пол знаком отрицания).

Совершенной конъюнктивной нормальной формой относительно переменных х₁…х_n , называется КНФ, в которой нет одинаковых элементарных дизъюнкций и все элементарные дизъюнкции правильны и полны относительно переменных х₁…х_n.

Теорема 3: всякую функцию f можно представить в СКНФ

, (4)

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

3.2.1 Алгоритм преобразования формулы в СКНФ

Преобразование формулы в СКНФ производится аналогично преобразованию формулы в СДНФ. Отличие состоит в том, что образовывать нужно не конъюнкции, а дизъюнкции.

Находить СКНФ для функции также можно по ее таблице истинности, но дизъюнкции берутся по тем наборам, где функция =0. С отрицанием берется та переменная, значение которой =1.

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

Таб. 5

Х	Y	Z	f
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Данная функция имеет следующую СКНФ:

.

Однако, если функция задана формулой, то строить СКНФ по таблице не рационально, тогда применяют следующий алгоритм: построение СКНФ состоит из двух этапов, каждых из которых состоит их трех шагов. На первом этапе строят КНФ, а на втором этапе из КНФ строят СКНФ.

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

импликация

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

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

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

.

Например:

3 шаг. Если в КНФ имеется несколько одинаковых элементарных дизъюнкций, то мы оставляем только одну (используя свойство идемпотентности: ).

4 шаг. Делаем все элементарные конъюнкции правильными путем одним из следующих преобразований:

если в элементарную дизъюнкцию входит некоторая переменная вместе со своим отрицанием, то мы удаляем эту дизъюнкцию из КНФ (используя свойство ).

Если некоторая переменная входит в элементарную конъюнкцию несколько раз, причем или во всех функциях с отрицанием или во всех случаях без отрицания, то мы оставляем только одно вхождение (используя свойство идемпотентности: хх = х).

5 шаг. Делаем все элементарные дизъюнкции полными. Если в некоторую дизъюнкцию не входит переменная y , то необходимо рассмотреть равносильное выражение и вновь применить шаг 2. Если недостающих переменных несколько, то нужно добавить несколько дизъюнктивных членов вида .

6 шаг. После применения 5-го шага могут вновь появится одинаковые дизъюнкции. Поэтому на шестом шаге применяют шаг 3.

Задание №5

Найти СКНФ для формулы:

=

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

Используя свойство , получим

=

используя свойство ,получим =

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

Используя свойство дистрибутивности получим

шаг. Делаем дизъюнкции правильными

шаг. Делаем дизъюнкции полными

шаг. Применяем шаг 2. Получаем

шаг. Получили две одинаковые дизъюнкции, оставляем одну из них

получили совершенную конъюнктивную нормальную форму. (в конце примера опущен знак конъюнкции)

4 ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ

4.1 Равносильные формулы и их доказательство

Алгебра высказываний также как и булева алгебра использует два элемента: «истина», «ложь». В алгебре высказываний рассматриваются вопросы, связанные с образованием сложных высказываний. Если, у нас есть несколько высказываний, то при помощи логических связок (конъюнкции, дизъюнкции, импликации и эквивалентности) и при помощи операций из них можно образовывать различные, новые высказывания. При этом исходные высказывания называются простыми, а вновь образованные высказывания называются сложными.

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

на улице светит солнце, и в аудитории идут занятия;

на улице светит солнце, или в аудитории идут занятия;

если на улице светит солнце, то в аудитории идут занятия. и. т. д.

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

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

Алфавит - любое непустое множество.

Символ - элемент алфавита.

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

Выражение называется формулой, если оно удовлетворяет следующим требованиям:

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

если X и Y - формулы, то выражения

…Y

тоже являются формулами.

Упорядоченный набор высказывательных переменных называется списком.

Оценка из списка - это сопоставление каждой переменной ее истинного значения.

4.2 Равносильные формулы

Пусть X и Y - формулы алгебры высказываний, а х₁…..х_n - набор простых высказываний, входящих хотя бы в одну из формул. Формулы X и Y будем называть равносильными, если при всех значениях истинности х₁…..х_n значения истинности совпадают . равносильность обозначается ., но знак = ошибкой не будет.

Отношение равносильности является рефлексивным, симметричным и транзитивным.

Перечислим основные равносильности:

Двойное отрицание ;

Коммутативность

Дистрибутивность

Ассоциативность



Идемпотентность

Свойства констант

Правила де Моргана

Закон противоречия\

Закон исключенного третьего



4.3 Доказательство равносильностей

Доказательство равносильностей можно осуществить двумя способами:

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

с помощью рассуждений.

Пример (Задание №6): докажем равносильность

а) с помощью таблицы.

Таб. 6

X	Y	Z
1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0
0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0
0	1	1	1	1	1	1	1
1	0	0	0	1	1	1	1
1	0	1	0	1	1	1	1
1	1	0	0	1	1	1	1
1	1	1	1	1	1	1	1

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

б) с помощью рассуждений.

допустим истинность левой части

установим истинное значение для всех истинностных переменных, входящих в список или оценку списка

оценку списка подставим в правую часть равносильности

установим истинность для правой части

все повторим справа налево.

I.

х=И или И

если х=И И, И,

если и z = И

II.

и

х =И или y =И и х=И или z=И

если х=И И

если y=И и z=И =И

(И - «истина», т. е. присваивается истинное значение)

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

Правила перехода от одних равносильностей к другим

Пусть , а С - произвольная формула

С АС В

Правила равносильных преобразований

Пусть , а С - произвольная формула. Пусть х - формула, которая входит в С. тогда Са - формула, которая получается заменой в формуле С формулы х на а.Сb - получается из С заменой x на b, тогда Са=Сb.

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

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

Пусть f и g - функции алгебры логики, x_1,…,x_n - совокупность аргументов, входящих хотя бы в одну из этих функций, говорят, что f и g- равносильны, если при всех значениях x_1,…,x_n значения f и g - совпадают.

Тавтологии

Дана формула А х₁ х₂ х₃.

Формула А называется тождественно истинной, если на любом списке переменных она принимает значение «Истина».

Тавтология - это утверждение, которое всегда истинно, иначе ее определяют как закон.

Формула называется тождественно ложной, если на любом списке переменных она принимает значение «Ложь».

Противоречие - это утверждение, которое всегда ложно. Таблица истинности для противоречия всегда принимает значение «Ложь».

Например

А
И	Л	Л
Л	И	Л

Формула А называется выполнимой, если находится такой набор переменных, что она принимает значение «Истина».

Формула А называется опровержимой, если находится такой набор переменных, что она принимает значение «Ложь».

Что касается высказываний, то здесь применяется термин высказывание логически истинно, такое высказывание можно получить путем его подстановки в тавтологию (например: предложение «Если идет дождь или идет снег, и не идет дождь, то идет снег» получим путем подстановки в тавтологию и высказывание логически ложно, если его подставляют в противоречие.

Основные тавтологии

Доказательство утверждений

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

5. БУЛЕВЫ ФУНКЦИИ

5.1 Полнота системы булевых функций

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

Эти функции нам встречались в теме «Математическая логика» при составлении 16-ти функций для двух переменных.

Полная система булевых функций обозначается Е имеет следующий вид:

f₁(x₁,x₂,…x_k1)

f₂(x₁,x₂,…x_k2)

…………….

F_e(x₁,x₂,…x_ke)

Система функций (Е), называется полной, если любая ее булева функция может быть выражена с помощью f₁, f₂, … f_e через суперпозицию.

Суперпозиция - это функция f^*, которая получена из функции f с помощью следующих преобразований:

замена переменной. f(x₁, x₂, x_j,…,x_n) f^*=f(x₁, x₂, x_j-1,y, x_j+1,…,x_n)

подстановка вместо х_j некоторой функции из системы (1).

f^*=f_i(x₁, x₂, x_j-1, f_e(x₁,x₂,…x_ke) x_j+1,…,x_ki).

Пример: система функций (Е₁) всегда полна, т. к. каждая функция этой системы может быть представлена в виде СДНФ, следовательно СДНФ является суперпозицией, через которую может быть выражена любая из функций системы;

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

Задание №7

Доказать полноту системы:

.

Для наглядности эту систему можно записать следующим образом: . То есть нам дана система, состоящая из булевой функции (импликации) и константы 0. С их помощью мы можем выразить операцию отрицания, для этого мы константу 0 подставим вместо одной из переменных:

следовательно данная система является полной.

6. ЛОГИКА ПРЕДИКАТОВ

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