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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Лекции Графическая интерпретация множеств и операций над ними. Математическая логика, булева алгебра. Совершенная конъюнктивная нормальная форма. Равносильные формулы и их доказательство. Полнота системы булевых функций. Логика предикатов, теория графов.

Информация:

Тип работы: Лекции. Предмет: Математика. Добавлен: 01.12.2009. Сдан: 2009. Уникальность по antiplagiat.ru: --.

Описание (план):


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) пример неассоциативной операции: возведение в степень (ab)c здесь скобки необходимы.
Операция называется коммутативной, если выполняется условие: . Сложение и умножение являются коммутативными (от перемены мест слагаемых сумма не меняется). Вычисление и деление - некоммутативные, некоммутативной так же является операция умножения матриц.
Операция называется дистрибутивной, если выполняется условие: .
1.4 Тождества и их доказательство
При выполнении операций над множествами часто приходиться доказывать равенства, т. е. тождества. (В частности, условия приведенные выше являются тождествами, которые необходимо доказать).
Доказать, что M=N, где M и N - выражения с множествами.
Доказательство производится в два этапа: 1) «в одну сторону», 2) «в обратную сторону».
Сначала предположим, что некий элемент х принадлежит левой части равенства: эта запись звучит следующим образом:
«если , то ».
На втором этапе предполагается, что элемент х принадлежит правой части равенства: .
Пример №1
Доказать тождество:
.
Решение:
;
.
1.5 Отношения на множествах
Отношения бывают одноместными, двуместными (бинарными) и n-местными. Одноместное отношение- это просто подмножество. Мы остановимся на бинарных отношениях.
упорядоченная пара (x, y) есть совокупность двух элементов записанных в определенном порядке.
Две пары (x, y) и (x1, y1) считаются равными тогда и только тогда x1 = х, y1 = 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-множеств.
Декартовым произведением множеств М1, М2,…., Мn называется множество Элементами декартова произведения являются всевозможные последовательности, каждая из которых состоит из n элементов, причем первый элемент принадлежит множеству М1, второй - множеству М2, n-ый - множеству Мn.
Если множество Мх в определении функции у=F(x) является декартовым произведением множеств М х1, М х2,…., М хn, то получаем определение n-местной функции у=F(х1, х2,….,хn).
1.8 Функция как отношение
Функцией называется функциональное соответствие.
Если функция f устанавливает соответствие между множествами А и В, то говорят, что функция f имеет тип АВ, обозначается f: АВ. каждому элементу а из своей области определения функция f ставит в соответствие единственный элемент b из области значений. Обозначается f(a)=b.
Элемент а называется аргументом функции, элемент b называется значением функции на а.
Полностью определенная функция f: AB называется отображением А и В.
Областью определения называется выражение D=
Функция называется инъективной, если из отношений (x1,y)f, (x2,y)f x1=x2
Функция называется сюръективной, если для каждого уY существует хХ.
Инъективная и сюръективная функции образуют биекцию - это взаимнооднозначное отношение множеств.
1.9 Отношение порядка
Отношение называется отношением нестрогого порядка, если оно рефлективное, антисимметрично, транзитивно.
Отношение называется отношением строгого порядка, если оно антирефлективное, антисимметрично, транзитивно. Оба типа отношений называются отношениями порядка.
Элементы a,b сравнимы по отношению порядка, если выполняется aRb или bRa. Множество М, на котором задано отношение порядка называется полностью упорядоченным, если любые два элемента множества М сравнимы, в противном случае - частично упорядоченным.
Пример: отношения для чисел являются отношениями нестрого порядка, отношения <,> - отношения строгого порядка. Оба отношения полностью упорядочивают множество. Отношение строгого включения задает строгий частичный порядок: .
Отношение эквивалентности
Отношение называется отношением эквивалентности (эквивалентностью), если оно одновременно рефлективно, симметрично и транзитивно.
Примеры:
1. отношение равенства на любом множестве является отношением эквивалентности;
2. утверждение вида (a+b)(b-a)=a2-b2 - формулы соединенные знаком равенства задают бинарное отношение. Такое отношение называют отношением равносильности. Оно отличается от равенства, т. к. может выполняться для различных формул.
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=b1, b2, b3
b=000
b=001
b=010
b=011
b=100
b=101
b=110
b=111
Каждой вершине куба присвоена кодовая комбинация по принципу: если проекция на ось равна нулю, то в комбинации ставится ноль, а если проекция равна единице, то в комбинации ставится единица. Порядок проекций должен быть одним и тем же: b1, b2, b3. Длина ребра куба равна единице. 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 Коды с обнаружением ошибок
Имеем кодовое слово а=а1, а2,…, аm; составляем другое кодовое слово с добавлением символа - b=b1, b2…bm, bm+1
ai=bi
bm+1=………..
получим на входе нечетный код, он является всегда ошибочным. Ошибку обнаружить можно но исправить нельзя. Данный код соответствует разработанному примеру (2,3)
3.2 Корректирующие коды
а=а1, а2,…, аm
b= a1 a1 a1, a2 a2 a2,…am am am
ai=bi, длина кода 3m
а2 а2 а2
если 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/5 (расписание экзаменов профессора Иванова). Результатом операции выбора являются строки, в которых домен (столбец) D3 представлен значением профессор Иванов: это 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-арного отношения:
,
Проекцией Пр (R2/A) бинарного отношения R2, R2на А называется множество элементов .
Проекцией Пр (R2/Ai1, Ai2,…Ain) n-арного отношения называется множество кортежей (аi1, ai2,…,aim), где , каждый из которых является частью элемента n-арного отношения Rn. операция проекции определяет построение «вертикального» подмножества отношения, т. е. множество подмножества кортежей, получаемого выбором одних доменов и исключения других доменов.
Пример: проекция Пр(R5/D2,, D3) порождает множество пар, каждая из которых определяет дисциплину и экзаменатора.
Таб. 2
R2
D3
D3
теория автоматов
пр. Иванов
математическая статистика
пр. Петров
физика
пр. Сидоров
алгоритмические языки
пр. Иванов
одинаковые строки в таблице объединены в одну.
Операция соединения по двум таблицам, имеющим общий домен, позволят построить одну таблицу, каждая строка которой образуется соединением двух строк исходных таблиц. Из заданных таблиц берут строки, содержащие одно и то же значение из общего домена; общему домену сопоставляется один столбец.
Пример: найдем по двум заданным таблицам (таб.3.а, таб.3.б) результат операции соединения по домену D1 (таб.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а по атрибуту х и отношения Rb по атрибуту у (атрибуты х, у являются атрибутами одного и тог же домена общего для отношений Rа , Rb ), х>у называется множество всех кортежей , таких, что - конкатенация кортежа аi, принадлежащего Rb, где х - часть аi, у - часть bi и х>у.
Запрос в реляционной БД будет выполнен тем быстрее, чем меньше операций над отношениями он содержит Таким образом представляет практический интерес рассматриваемая выше задача упрощения представления множества через введенные операции.
2 МАТЕМАТИЧЕСКАЯ ЛОГИКА. АЛГЕБРА ЛОГИКИ.
В булевой алгебре рассматривается двухэлементное множество В, элементы которого обозначаются как 0 и 1 и рассматривают их как формальные символы, не имеющие арифметического смысла. Наиболее распространенная интерпретация двоичных переменных - логическая: «да» - «нет», «истина» - «ложь».
Алгебра образованная множеством В вместе со всеми возможными операциями на нем, называется алгеброй логики.
Функцией алгебры логики (или логической функцией) от n-переменных, называется n-арная операция на В.
Логическая функция f (x1,…xn) - это функция принимающая значения 0,1. Множество всех логических функций обозначается Р2, множество всех логических функций от n-переменных обозначается Р2(n). Всякая логическая функция может быть задана таблицей, в левой части которой перечислены все наборы переменных, а в правой части - значения функции на этих наборах.
Переменная хi в функции f(x1,…xi, xi, xi+1,…,xn) называется несущественной (или фиктивной), если f(x1,…xi, 0, xi+1,…,xn) = f(x1,…xi,1,xi+1,…,xn) при любых значениях остальных переменных, т. е. если изменение значения xi в любом наборе значений x1,…xi не меняет значение функции. Говорят, что функция g получена из функции f удалением фиктивной переменной и наоборот, причем эти функции считаются равными.
Пример: f(x1 x2 x3 x4) = g(x1,x2) означает, что при любых значениях x1 и x2 f=g незавасимо от значения x3. Удаляют фиктивные переменные поскольку они не влияют на значение функции и являются с этой точки зрения лишними.
Рассмотрим примеры логических функций:
Одна переменная Х имеет 4 логических функции, которые приведены в таблице 1.
Таб.1.
Х
F0
F1
F2
F3
0
0
0
1
1
1
0
1
0
1
Функции F0 и F3 - константы 0 и 1 соответственно;
Функция F1 (х) = х, т. е. функция F1 повторяет х;
Функция F2 (х) является отрицанием х (логическая операция НЕ) и обозначается .
Все перечисленные функции являются унарными (для одной переменной) функциями.
Две переменные имеют 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 являются бинарными (для двух переменных).
Функции F0 и F15 - константы 0 и 1;
Функция F1 1, х2) называется конъюнкцией х1 и х2, обозначается: &,,но чаще всего значок конъюнкции опускают, аналогично знаку умножения. Она ровна единице только тогда когда х1 и х2 =1. В остальных случаях она ровна 0. Это функция логического «И» или функция логического умножения.
Функция F7 1, х2) называется дизъюнкцией х1 и х2, обозначается +,. Она ровна 1, если хотя бы одна переменная равна 1. Это функция логического «ИЛИ» или функция логического сложения.
Функция F6 1, х2) - сложение по модулю 2, обозначается . Она ровна 1 когда значения ее аргументов различны и ровна 0 когда значения ее аргументов ровны, поэтому эта функция называется неравнозначностью.
Функция F9 1, х2) - эквивалентность (равнозначность), обозначается «». Она ровна 1 когда аргументы ровны и ровна 0 когда аргументы различны.
Функция F13 1, х2) - импликация, обозначается . Звучит данная функция так: “если х1, то х2 “ .
Функция F8 1, х2) - стрелка Пирса, обозначается
Функция F14 1, х2) - штрих Шеффера, обозначается х1, х2
Остальные функции своего названия не имеют, и легко выражаются через перечисленные выше функции.
При построении таблицы для конкретной формулы необходимо «разложить формулу по ее составляющим», т. е. по числу операций следуя изнутри наружу. для каждой операции составляется таблица истинности, а в последнем столбце записывается вся формула (или ставится буква 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 входит трижды: один раз сама и два раза под знаком отрицания.
Правильная элементарная конъюнкция называется полной относительно переменных х1…..хn, если в нее входит каждая их этих переменных причем только один раз (может быть и пол знаком отрицания).
Например: из перечисленных в предыдущем примере конъюнкций полной является только 4) относительно переменных x,y,z,t; а относительно переменных x,y,z полной является только 1).
Совершенной дизъюнктивной нормальной формой (СДНФ) относительно переменных х1…..хn называется дизъюнктивная нормальная форма, в которой нет одинаковых элементарных конъюнкций и все элементарные конъюнкции правильны и полны относительно переменных х1…..хn

3.1.2 Разложение по переменным
Теорема 1. Всякая логическая функция может быть представлена в СДНФ:
, (1)
где m, а дизъюнкция берется по всем 2m наборам значений переменных х1,…хm . Функция f разложена по первым n-переменным. Данное равенство называется разложением по переменным. х1,…хm. Например при n=4, m=2 разложение имеет вид:
теорема доказывается подстановкой в обе части равенства (1) произвольного набора (b1,…,bm, bm+1,…,bn) всех n-переменных.
При m = 1 из (1) получаем разложение функции по одной переменной:

(2)

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

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

, (3)

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

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



Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.