1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы



страница2/18
Дата23.12.2012
Размер1.84 Mb.
ТипДокументы
1   2   3   4   5   6   7   8   9   ...   18

2.Дискретная математика.

2.1.Математическая логика: высказывания и алгебра высказываний, логические функции, суперпозиция функций, формулы.

Математическая логика представляет собой методику и теорию математических доказательств. Алгебра образованная множеством В={0,1} вместе со всеми возможными операциями на нем, называется алгеброй высказываний (алгеброй логики). Высказываниями называются 1) элементарные высказывания; 2) составные или сложные высказывания. Элементарным высказыванием называется символ, которому поставлено в соответствие логическое значение истина или ложь. Составные высказывания строятся с помощью логических связок Ø, Ù, Ú, ®, ~, (соответственно "не", "и", "или", "влечет", "эквивалентно", "неэквивалентно").

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


  1. Логические функции двух переменных

x1

x2

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

0

0

0

1

0

0

0

1

1

1

1

0

0

0

1

1

1

0

1

0

1

0

1

1

0

1

0

1

0

1

1

0

0

1

1

0

0

1

0

1

1

0

0

0

1

1

0

0

1

1

0

1

1

0

1

1

1

0

1

1

0

0

1

0

1

0

1

0

Функции f012) и f112) - константы. Функция f212) называется конъюнкцией х1 и х2 (операция логического умножения или функция И). Её обозначения: х12, х1Ùх2, х1·х2, х1х2. Функция f312) называется дизъюнкцией х1 и х2 (операция логического сложения или функция ИЛИ). Её обозначения: х1Úх2, х12. Функция f412) - это сложение по модулю 2 (функция неравнозначности). Она равна 1, когда значения ее аргументов различны и равна 0, когда они равны. Её обозначения: х1Åх2, х12. Функция f512) называется эквивалентностью или равнозначностью. Её обозначения: х12, х1ºх2. Функция f612) - импликация. Её обозначения: х1®х2, х1Éх2. Функция f712) - стрелка Пирса. Её обозначение: х1¯х2. Функция f812) - штрих Шеффера. Её обозначение: х1ïх2. Остальные функции специальных названий не имеют и легко выражаются через перечисленные ранее функции. Приведенные выше операции над логическими значениями известны под названием булевых операций.

Суперпозицией функций f1,...,fm называется функция f, полученная с помощью подстановок этих функций друг в друга и переименованием переменных, а формулой называется выражение, описывающее эту суперпозицию. Формулы, представляющие одну и ту же функцию, называются эквивалентными или равносильными.

2.2.Булева алгебра.

Алгебра (Р2; Ú, &, Ø), основным множеством которой является все множество логических функций, а операциями - дизъюнкция, конъюнкция и отрицание, называется булевой алгеброй логических функций. Операции булевой алгебры также часто называют булевыми операциями. Они имеют следующие основные свойства.

  • Ассоциативность: а) х12х3)=(х1х23; б)(х1Úх2)Úх31Ú(х2Úх3)

  • Коммутативность: а) х1х22х1; б)х1Úх22Úх1

  • Дистрибутивность конъюнкции относительно дизъюнкции: х12Úх3)=х1х2Úх1х3

  • Дистрибутивность дизъюнкции относительно конъюнкции: х1Ú(х2х3)=(х1Úх2)(х1Úх3)

  • Идемпотентность (одинаковость): а) хх=х; б)хÚх=х.

  • Двойное отрицание: .

  • Свойства констант: а) хÙ1=х; б) хÙ0=0; в) хÚ1=1; г) хÚ0=х; д) ; е).

  • Правила де Моргана: а) =; б) =.

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

  • Закон "исключенного третьего": .

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

  • Поглощение: xÚxy=x, x(xÚy)=x;

  • Склеивание: ;

  • Обобщенное склеивание: ;

  • Закон Блейка-Порецкого: .

Элементарными конъюнкциями называются конъюнкции переменных или их отрицаний, в которых каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций. Приведение к ДНФ осуществляется следующим образом. Сначала с помощью двойного отрицания и правил де Моргана все отрицания "спускаются" до переменных. Затем раскрываются скобки, с помощью идемпотентности, законов противоречия и "исключенного третьего" удаляются лишние конъюнкции и повторения переменных в конъюнкциях, а также исключаются константы с помощью соответствующих соотношений. Совершенной дизъюнктивной нормальной формой (СДНФ) называется формула, имеющая дизъюнктивную нормальную форму, в которой каждая элементарная конъюнкция содержит все переменные.

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

2.3.Понятие множества и подмножества, операции над множествами, понятие кортежа и проекции.

Абстракцию, в результате которой некоторая часть мира признается предметом, будем называть абстракцией предмета. Математическое понятие множества, иллюстрациями которого в реальном мире являются различные собрания предметов, коллекции, совокупности, связано с еще одной абстракцией, которую будем называть абстракцией множества. Если предмет а входит в множество М, то говорят: "а является элементом М" или "элемент а принадлежит множеству М" и пишут аÎМ. Если множество А состоит из конечного числа элементов а1, а2,..., аn, то пишут А={а12,...,аn}. Множество, не содержащее ни одного элемента, называют пустым и обозначают Æ. Число элементов в конечном множестве А называется мощностью А и обозначается ïАï. Если каждый элемент множества А является также элементом множества В, то А называют подмножеством множества В и пишут АÍВ.

Пусть А и В - два множества. Множество С тех элементов, которые принадлежат и А и В, называется пересечением или теоретико-множественным произведением множеств А и В. При этом пишут С=АÇВ={xïxÎА и xÎВ}. Операция построения АÇВ по заданным А и В называется теоретико-множественным умножением. Множество D всех элементов, каждый из которых принадлежит хотя бы одному из множеств А или В, называется объединением или теоретико-множественной суммой множеств А и В. При этом пишут D=АÈВ={xïxÎА или xÎВ}. Операция построения АÈВ по заданным А и В называется теоретико-множественным сложением. Множество Е тех элементов, принадлежащих А, которые не принадлежат В, называется теоретико-множественной разностью А и В. При этом пишут Е=А\В={xïxÎА и xÏВ}. Операция, позволяющая получить А\В по заданным А и В, называется теоретико-множественным вычитанием.

Множество пар, первая компонента в которых является элементом множества А, а вторая - элементом множества В, называется декартовым, геометрическим или прямым произведением множеств А и В и обозначается А´В. Если члены декартова произведения равны между собой, то декартово произведение называется декартовой степенью. Пары, являющиеся элементами множества А´В, обозначаются (а, b), где аÎА, bÎB. Элементами декартова произведения множеств А´В и С являются пары вида ((а,b),с)=(а,b,c), где сÎС. Если число множеств сомножителей равно n, то элементами их декартова произведения будут кортежи или векторы (упорядоченные наборы) по n элементов. Элементы, образующие кортеж (вектор), называются координатами или компонентами кортежа. Число координат называется длиной или размерностью кортежа. Проекцией вектора v на i-ю ось (обозначается прiv) называется его i-я компонента. Проекцией множества V векторов одинаковой длины на i-ю ось называется множество проекций всех векторов из V на i-ю ось: прiV={прivïvÎV}.

2.4.Понятие соответствия и функции. Композиция и способ задания функций.

Соответствием между множествами А и В называется подмножество GÍАxВ. Если (а, b)ÎG, то говорят, что b соответствует а при соответствии G. Множество пр1G называется областью определения соответствия, множество пр2G - областью значений соответствия. Если пр1G=А, то соответствие называется всюду определенным. В противном случае соответствие называется частичным. Если пр2G=B, то соответствие называется сюръективным. Множество всех bÎB, соответствующих элементу аÎА, называется образом а в В при соответствии G. Множество всех а, которым соответствует b, называется прообразом b в А при соответствии G. Соответствие G называется функциональным (или однозначным), если образом любого элемента из пр1G является единственный элемент из пр2G. Соответствие G между А и В называется взаимно-однозначным, если оно всюду определено, сюръективно, функционально и, кроме того, прообразом любого элемента из пр2G является единственный элемент из пр1G.

Функцией называется функциональное соответствие. Если функция f устанавливает соответствие между множествами А и В, то говорят, что функция f имеет тип А→В и обозначают это f: А→В. Каждому элементу а из своей области определения функция f ставит в соответствие единственный элемент b из области значений. Это обозначается следующей записью: f(a)=b. Элемент a называется аргументом функции, b - значением функции на a. Функция типа А1´А2´...´Аn→В называется n-местной функцией. Пусть дано соответствие GÍA´B. Если соответствие HÍB´A таково, что (b, a) ÎH тогда и только тогда, когда (a, b)ÎG, то соответствие H называется обратным к G и обозначается G-1. Если соответствие, обратное к функции f: А→B, является функциональным, то оно называется функцией, обратной к f и обозначается f-1.

Пусть даны функции f: А→B и g: B→C. Функция h: A→C называется композицией функций f и g (обозначается f°g), если имеет место равенство h(x)=g(f(x)), где xÎA. Функция, полученная из f1, ..., fn некоторой подстановкой их друг в друга и переименованием аргументов, называется суперпозицией. f1, ..., fn. Выражение, описывающее эту суперпозицию и содержащее функциональные знаки и символы аргументов, называется формулой.

Наиболее простой способ задания функций - это таблицы, т.е. конечные списки пар (x, f(x)). Другим способом задания функций является формула, описывающая функцию как суперпозицию других функций. Еще одним способом задания функции является рекурсивная процедура, позволяющая вычислить значение функции на основе других, ранее определенных её значений.
1   2   3   4   5   6   7   8   9   ...   18

Похожие:

1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconРеферат на тему: "логистические информационные системы. Иерархия использования логистической информационной системы. Функции логистической информационной системы. Поток информации в предпринимательстве."
Основные направления информационно-технического обеспечения логистических систем
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconРазработка автоматизированной информационной системы «кафедра» с помощью современных средств web-программирования
Рассматривается разработка автоматизированной информационной системы «Кафедра» и средства ее реализации
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconБазы данных и информационные системы
...
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconЭкзаменационные вопросы по информатике Направление подготовки «Адаптивная физическая культура»
Основные понятия информатики: информационная среда, информационные технологии, информационные системы, базы данных, интеллектуальные...
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconРабочая программа для студентов направления 230400. 62 «Информационные системы и технологии»
...
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconДисциплина «Интеллектуальные информационные системы», пиэ, 4 курс, 1 семестр вопросы на зачет
Понятие интеллектуальной информационной системы (иис), особенности и основные свойства иис
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconИнформационные системы
Информационная система (ИС) – это комплекс, состоящий из информационной базы (хранилища информации) и процедур, позволяющих накапливать,...
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconРазработка автоматизированной системы эксергетического анализа сложных химико-технологических систем
Поэтому необходимость разработки автоматизированной системы расчета и оптимизации эксергетического баланса хтс произвольной структуры...
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconЛекция 1) гис как специализированная информационная система. Структура информационных систем, представление о модели данных. Последовательность действий при создании информационной системы
Модели данных для пространственной информации. Геокодирование, общее понятие. Геокодирование как процесс перевода пространственной...
1. Информационные системы. Понятия информации, системы, автоматизированной информационной системы iconТемы, вопросы для изучения
Понятия: системы; фаза; гомогенные и гетерогенные системы; процессы и их классификация; параметры и функции состояния системы
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org