Б) Основные функции дискретной математики, их свойства, ДНФ и КНФ. Применение дискретной математики в информатике.

Любая ИС может считаться эффективной, если выборка данных осуществляется быстро, качественно и в требуемом объёме. Наиболее эффективным решением этой проблемы является возможность построения запросов средствами команд SQL. Язык SQL, в отличии от существующих команд языка СУБД, является множественно-ориентированным языком и направлен на получение готовых таблиц с результатами запроса. SQL – это структурированный язык запросов, является стандартом в области использования реляционных БД. Особенности SQL: команда SQL работает с данными на уровне машинного представления, поэтому скорость обработки возрастает в сотни раз по сравнению с традиционными командами СУБД; 2) команды SQL самостоятельно выполняют создание индексов и ключей при необходимости, это экономит место на диске и затраты ресурсов на поддержание целостности структуры индексов.

Для построения запроса в диалоговом режиме может быть использован конструктор запросов, где генерируется тело команды SQL и создаётся файл с .qpr. Этот файл можно выполнить, используя команду DO имя запроса .QPR. Сгенерировать код команды SQL возможно также в дизайнере представлений, однако в том и другом случае в дизайнерах не могут быть реализованы все сложные синтаксические конструкции SQL , поэтому один из вариантов может быть следующим: в конструкторе создаётся тело SQL и вручную дополняются тонкие настройки.

Обобщённый алгоритм построения запроса ---- Описание полей данных в результате---- Список источников данных----Условия связи между различными источниками данных----*Усл. отбора данных-----*Усл. Суммирования данных

*Задание порядка записей в результате

* - необязательные блоки алгоритма

Выделяют 4 типа запросов данных в SQL, которые относятся к так называемому языку манипулирования данными: SELECT – выборка строк из таблиц; INSERT – добавление строк в таблицу; UPDATE – изменение строк в таблице; DELETE – удаление строк в таблице

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

Также, можно получить все столбцы из таблицы, используя подстановочный знак «*»: SELECT * FROM table_name;

Запрос возвратит все столбцы со всех строк, где «имя поля» содержит значение «3»:

Кроме «=» (равно), существуют следующие условные операторы: <>, > , < , >= , <=.

Дополнительно можно использовать условия BITWEEN (задается диапазон значений) и LIKE(маска для символьных переменных (% - любое количество произвольных символов, *- один произвольный символ)) для сравнения с условием WHERE (условие выборки), а так же комбинации операторов AND и OR. (или)

Что в переводе на русский язык означает: выбрать все столбцы из таблицы table_name, где значение столбца age больше или равно 18, а также значение столбца LastName находится в алфавитном промежутке от Иванов до Сидоров включительно, или же значением столбца Company является Motorola.

Команда INSERT позволяет добавить запись и присвоить ее полям необходимые значения. Требуется определить только ключевые поля и поля, которые не могут принимать пустые значения. Остальные поля можно оставить незаполненными. Формат команды:

INSERT INTO ИмяТаблицы (ИмяПоля1, ИмяПоля2, ...)

VALUES (ЗначениеПоля1, ЗначениеПоля2, ...)

Обновление (команда UPDATE) -Используется для изменения записей, которые уже существуют в таблице. Можно изменить любое количество записей в таблице от одной до каждой записи в таблице. Формат команды:

UPDATE ИмяТаблицы

SET ИмяПоля1=ЗначениеПоля1, ИмяПоля2=ЗначениеПоля2, ...

WHERE УсловиеОтбораЗаписе

Удаление (команда DELETE) -похожа на UPDATE, за исключением того, что в ней нет опции SET, и все записи, соответствующие условию отбора удаляются, а не модифицируются. Формат команды: DELETE FROM ИмяТаблицы WHERE УсловиеОтбора

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

Дизъюнктивные нормальные формы (ДНФ)

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

Элементарной конъюнкцией (ЭК) называется выражение вида (х – множества) X₁^a1 X₂^a2…X_n^an

ЭК называется правильной, если все входящие в неё переменные различны. Правильная ЭК называется полной относительно данного набора переменных, если в неё входят все эти переменные.

Для элементарных дизъюнкций (ЭД) – аналогичный набор определений. ЭД – выражение вида X₁^a1 V X₂^a2 V…V X_n^an

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

__

X₁ V X₁X₂ V X₁X₂X₃ – ДНФ.

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

Дизъюнктивной нормальной формой (ДНФ) называется произвольная дизъюнкция элементарных конъюнкций. Конъюнктивной нормальной формой (КНФ)называется произвольная конъюнкция элементарных дизъюнкция. СКНФ – совершенная КНФ. У нее все ЭД полны.

Алгоритм представления функции в виде СДНФ.

1. Выписываем носитель функции.

2. Для каждого вектора из носителя выписываем конъюнкцию соответствующих переменных. (если координата равна нулю, переменную пишем с отрицанием, если единице – без отрицания). Это и будут все полные ЭК.

3. Выписываем дизъюнкцию всех этих ЭК.

Алгоритм представления функции в виде СКНФ.

1. Выписываем носитель функции

2. Для каждого вектора из носителя выписываем дизъюнкцию соответствующих переменных. (если координата равна нулю, переменную пишем без отрицания, . если единице – с отрицанием). Это и будут все полные ЭД.

3. Выписываем конъюнкцию всех этих ЭД.

Булевы функции. Множество M с двумя введенными бинарными операциями (&, V), одной унарной операцией (*) и двумя выделенными элементами называется булевой алгеброй, если выполнены следующие свойства (аксиомы булевой алгебры):

1. X & Y = Y&X, X V Y = Y V X – коммутативность.

2. (X & Y) & Z = X & (Y & Z), (X V Y) V Z = X V (Y V Z) – ассоциативность.

3. (X V Y) & Z = (X & Z) V (Y & Z), (X & Y) V (Y & Z) = (X V Z) & (Y & Z) – дистрибутивность.

4. Поглощение – X & X = X, X V X = X.

5. Свойства констант: X & 0 = 0, X & I = X, где I – аналог универсального множества.

6. Инвальтивность (X*)* = X

7. Дополнимость X V X* = I, X & X* = 0.

8. Законы двойственности – (X & Y)* = X* V Y*, (X V Y)* = X* & Y

Применение дискретной математики в информатике

Нечеткая логика – надмножество Булевой логики, которая была расширена с целью обработки концепции частичной правды - значения истинности между «полностью истинным» и «полностью ложным».

Основным отличием нечеткой логики от классической, как явствует из названия, является наличие не только двух классических состояний (значений) – истина и ложь, но и промежуточных:

F = {0…1}

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

Как можно легко заметить, при использовании только классических состояний (ложь – 0, истина – 1) мы приходим к классическим законам логики.

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

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

 

Билет №14