Реферат: Логическое и функциональное программирование
ЛОГИЧЕСКОЕ И ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ
Введение
Целью логического и функционального программированияявляется вывод решений и они тесно связаны с задачами, решаемыми вискусственном интеллекте и экспертных системах (ЭС). На начальном этаперазвития систем искусственного интеллекта (СИИ) и ЭС даже выделился целый классспециализированных языков программирования: языки логического и функциональногопрограммирования.
/>
Процедурная программасостоит из последовательности операторов и предложений, управляющихпоследовательностью их выполнения. В основе такого программирования лежатвзятие значения какой-то переменной, совершение над ним действия и сохранениенового значения с помощью оператора присваивания, и так до тех пор пока не будетполучено желаемое окончательное значение.
Функциональная программасостоит из совокупности определений функций. Функции, в свою очередь,представляют собой вызовы других функций и предложений, управляющихпоследовательностью вызовов. Каждый вызов возвращает некоторое значение ивызвавшую ее функцию, вычисление которой после этого продолжается. Этот процессповторяется до тех пор, пока запустившая процесс функция не вернет результат пользователю.
В логических языкахпрограммирования для решения задачи достаточно описания структуры и условийэтой задачи. Поскольку последовательность и способ выполнения программы нефиксируется, как при описании алгоритма, программы могут в принципе работать вобоих направлениях, то есть программа может как на основе исходных данныхвычислить результаты, так и по результатам – исходные данные.
Наиболее известнымиязыками функционального программирования являются ЛИСП и РЕФАЛ, а логического –Пролог. Однако, с развитием языков программирования (в частности, с появлениемобъектно-ориентированных языков) и баз данных область их применения сузилась.Так ЛИСП используется как оболочка Автокад, а РЕФАЛ как средство для построенияметаязыков и метакомпиляторов.
Поэтому в дальнейшемвнимание будет уделено не рассмотрению конкретных языков функционального илогического программирования, а подходам, лежащим в основе их реализации иявляющимися базовыми при создании систем принятия решений.
ЛИСП и Пролог в своевремя являлись базовыми для создания экспертных систем. Поэтому, для того чтобынаглядно представить какой круг задач решается с помощью логического ифункционального программирования, рассмотрим задачи, возникающие в ЭС. Прежде всего,это задачи прямого и обратного вывода.
Прямой и обратныйвывод
При использовании прямой цепочки рассуждений решаетсязадача по известным условиям найти последствия. Обратная цепочка рассужденийприменяется для того, чтобы по известным результатам найти причины ихвызвавшие.
Такие задачи частозаписывают в терминах продукционных систем представления знаний, в которыхзнания записываются в виде продукций/правил, имеющих вид:
Если <условие>, То <вывод>.
/>
Рассмотрим сначалапостроение обратной цепочки рассуждений. Обратная цепочка рассуждений всегданачинается со следствия (часть То правила). Если в правилах, относящихсяк проблемной области, не удается найти условную часть с выполняющимисяусловиями, необходимо ввести дополнительную информацию. Цепочка означаетпроцедуру логической связи ряда правил.
Для представления такихзадач принято использовать дерево решений — специальную диаграмму дляпредставления возможных решений. Дерево решений состоит из вершин двух типов.Вершины решений, содержащие вопросы, обозначаются окружностями. Цели илилогические выводы обозначаются прямоугольниками. Вершины нумеруются. Каждаявершина может иметь не более одного входа. Рассмотрим простейший пример сприемом на работу, часто используемый в литературе [1].
Дерево решений будемхранить в следующей таблице [2]:
Таблица дереварешений.
№ вершины
ПеременнаяЗначение
Исходная вершина
Дуга
Тип вершины
1 Звание - - - решение 2 Должность Отказ 1 нет вывод 3 Возможность да 1 да вывод 4 Открытия - 1 да решение 5 Средний балл - 3 да решение 6 Должность Научный сотрудник 4 да вывод 7 стаж - 5 < 3.5 решение 8 должность конструктор 5 > 3.5 вывод 9 должность Отказ 7 < 2 вывод 10 должность администратор 7 > 2 выводДля сохранения результатовбудем использовать таблицу вывода (в начальный момент таблица пуста).
Таблица вывода№ варианта
Переменная
Значение
Алгоритм1. Определитьпеременную логического вывода и ее значение.
2. Найти первое вхождение этойпеременной в таблицу дерева решений с заданным значением и типом вершины«вывод». Если переменная не найдена – неудача. Установить переменную var = 1.
3. Выбрать исходную по отношению кполученной вершине вершину. Если ее нат, перейти к шагу 5. Если есть, записатьв таблицу вывода новую строку со значениями полей № варианта = var, Переменная = Переменная из исходнойвершины таблицы дерева решений, Значение = Дуга текущей вершины.
4. Сделать исходную вершину текущей.Перейти к шагу 3.
5. Найти следующее вхождение переменнойвывода в таблицу дерева решений. Если нет, конец, иначе var = var + 1. Перейти к шагу 3.
Пусть отказано в приемена работу. Тогда в ходе выполнения алгоритма таблица вывода будет формироватьсяследующим образом.
Здесь пропущена таблицавывода на предпоследнем этапе.
Механизм, основанный напрямой цепочке рассуждений, функционирует следующим образом:
1. Вводится условие.
/>
2. Для каждой ситуации система ищет вбазе данных (знаний) правила, в условной части которых содержитсясоответствующее условие.
3. В соответствии с констатирующейчастью (частью ТО) каждое правило может генерировать новые ситуации, которыедобавляются к уже существующим.
4. Система обрабатывает каждую вновьсгенерированную ситуацию. При наличии хотя бы одной такой ситуации выполняютсядействия, начиная с шага 2. Рассуждения заканчиваются, когда больше нетнеобработанных ситуаций
Алгоритм CLS
Для построения деревьеврешений часто используется алгоритм CLS. Этот алгоритм циклически разбивает обучающие примеры на группы/классы всоответствии с переменной, имеющей наибольшую классифицирующую силу. Каждоеподмножество примеров (объектов), выделяемое такой переменной, вновьразбивается на классы с использованием следующей переменной с наибольшейклассифицирующей способностью и т.д. Разбиение заканчивается, когда вподмножестве оказываются объекты лишь одного класса. В ходе процесса образуетсядерево решений. Пути движения по этому дереву с верхнего уровня на самые нижниеопределяют логические правила в виде цепочек конъюнкций.
Рассмотрим следующийпример. Проводится антропологический анализ лиц людей двух национальностей по16 признакам.
Х1 (голова) – круглая –1, овальная – 0.
Х2 (уши) – оттопыренные –1, прижатые – 0.
Х3 (нос) – круглый –1, длинный– 0.
Х4 (глаза) – круглые – 1,узкие – 0.
Х5 (лоб) – с морщинами–1, без морщин – 0.
Х6(носогубная складка) –есть – 1, нет – 0.
Х7(губы) – толстые – 1,тонкие – 0.
Х8 (волосы) – есть – 1,нет – 0.
Х9(усы) – есть – 1, нет –0.
Х10 (борода) – есть – 1,нет – 0.
Х11(очки) – есть – 1, нет– 0.
Х12(родинка) – есть – 1,нет – 0.
Х13(бабочка) – есть – 1,нет – 0.
Х14(брови) – поднятыевверх – 1, опущенные – 0.
Х15(серьга) – есть – 1,нет – 0.
Х16(трубка) – есть – 1,нет – 0.
Пусть имеется 16объектов. Объекты с номерами 1 – 8 относятся к первому классу, 9 – 16 ковторому классу. Далее приводится таблица со значениями признаков для этихобъектов.
№
X1 X2 X3X4
X5
X6
X7
X8
X9
X10
X11
X12
X13X14
X15
X16
Кл.
1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 6 1 1 1 1 1 1 1 1 1 1 7 1 1 1 1 1 1 1 1 1 1 8 1 1 1 1 1 1 1 1 1 1 9 1 1 1 1 1 1 1 1 1 2 10 1 1 1 1 1 1 1 1 1 2 11 1 1 1 1 1 1 1 1 1 2 12 1 1 1 1 1 1 1 1 1 2 13 1 1 1 1 1 1 1 1 1 2 14 1 1 1 1 1 1 1 1 1 2 15 1 1 1 1 1 1 1 1 1 2 16 1 1 1 1 1 1 1 1 1 2Объекты для этой таблицы(надо нарисовать).
Основное требование кматематическому аппарату обнаружения закономерностей в данных заключается винтерпретации результатов. Правила, выражающие закономерности, формулируются наязыке логических высказываний:
ЕСЛИ А ТО В,
ЕСЛИ (условие1) И(условие2) И … И (условиеN) ТО(условиеN+1),
где условиеi может быть Xi=C1, Xi< C2, Xi> C3, C4 < Xi< C5 и т.д. Здесь Xi— переменная, Cj– константа.
Так классификация лиц врассматриваемом примере может быть произведена с помощью четырех логическихправил:
1. ЕСЛИ (головаовальная) И (есть носогубная складка) И (есть очки) И (есть трубка) ТО(класс1).
2. ЕСЛИ (глазакруглые) И (лоб без морщин) И (есть борода) И (есть серьга) ТО (класс1)
3. ЕСЛИ (носкруглый) И (лысый) И (есть усы) И (брови подняты вверх) ТО (класс2).
4. ЕСЛИ(оттопыренные уши) И (толстые губы) И (нет родинки) И (есть бабочка) ТО(класс2).
Математическая запись этих правил выглядит следующимобразом:
/>
Такие правила имеют две основных характеристики:точность и полноту.
Точность правила – этодоля случаев, когда правило подтверждается, среди всех случаев его применения(доля случаев В среди случаев А).
Полнота – это доляслучаев, когда правило подтверждается, среди всех случаев, когда имеет местообъяснимый исход (доля случаев А среди случаев В).
Правила могут иметь какиеугодно сочетания точности и полноты. За исключением одного случая, еслиточность равна нулю, то равна нулю и полнота, и наоборот.
Точное, но неполноеправило: Людисмертны (А – человек, В – смертен).
Неточное, но полноеправило: Студентыпосещают занятия (А – студент, В — посещает).
Методы поиска логическихзакономерностей в данных обращаются к информации не только в отдельныхпризнаках, но и в сочетании признаков. Это основное преимущество этих методовперед многими другими методами в ряде случаев.
Вернемся к примеру.
На первом шагеопределяется признак с наибольшей дискриминирующей силой. Для этогоопределяется отношение вхождения объектов в разные классы в соответствии созначениями разных признаков:
Признаки Х1 Х2 Х3 Х4 Х5 Х6 Х7 Х8 Х9 Х10 Х11 Х12 Х13 Х14 Х15 Х16 Кл1/Кл2 3/3 4/6 4/6 5/5 3/3 6/4 4/6 3/3 5/5 6/4 6/4 3/3 5/5 4/6 4/6 5/5Здесь одинаковой имаксимальной силой обладают сразу семь признаков: Х2, Х3, Х6, Х7, Х10, Х11,Х14, Х15. Поэтому случайным образом выбираем один из них в качестве ведущего.Пусть это будет Х6. От этого признака отходит две ветви. Первая для значения Х6= 0, а вторая – для Х6 = 1.
Объекты Признаки Х1 Х2 Х3 Х4 Х5 Х6 Х7 Х8 Х9 Х10 Х11 Х12 Х13 Х14 Х15 Х16 2 1 1 1 1 1 1 1 1 1 7 1 1 1 1 1 1 1 1 1 12 1 1 1 1 1 1 1 1 1 13 1 1 1 1 1 1 1 1 1 14 1 1 1 1 1 1 1 1 1 16 1 1 1 1 1 1 1 1 1 2/2 1/3 1/3 2/3 2/2 1/4 1/4 1/2 1/3 2/0 1/3 1/1 1/2 1/2 2/3 1/3Для ветви Х6 = 0окончательное решение дает признак Х10. Он принимает значение 1 на объектах 2 и7 из первого класса и значение 0 на объектах 12, 13, 14 и 16 второго класса.Ветвь Х6 = 1 устроена значительно более сложно и требует дополнительных ветвлений.В результате получаем дерево.
Как следует из рисункадерево логического вывода, выросшее из признака Х6 имеет 6 исходов. Только дваиз этих исходов имеет по четыре объекта (полнота 4/8). Один исход группируеттри объекта (полнота 3/8), один – два объекта (полнота 2/8) и три исходавключают по одному объекту (полнота 1/8). Отсюда, качество алгоритма не оченьвысоко, так как обладает малой полнотой. Алгоритм, кроме того, способенприводить к качественным решениям только в случае независимых признаков.
Домашнее заданиеПостроить дерево решений для проблемной области,заданной преподавателем, и построить цепочки прямых и обратных рассуждений дляразличных ситуаций.
/>
Компьютерное задание
Реализовать дереворешений, прямой и обратный вывод средствами Access. Для реализации необходимо использовать VBA. В Access 2000 по умолчанию установлена модель данных ADO (ActiveX Data Objects). Для установки MSDE, что соответствует модели данных DAO, используемой в Access 97, необходимо использовать другойфайл установки. Необходимо вставить установочный компакт диск и дважды щелкнутьна имени файла SETUPSQL.EXE в папке \Sql\x86\Setup.
Иерархия ADO проще иерархии объектов модели
Объекты ADO предназначены для организациидоступа к источникам данных, их редактирования и обновления. Модель ADO включает в себя объекты, необходимыедля выполнения следующих задач:
1. Соединение с источником данных.
2. Создание объекта, реализующегокоманды SQL.
3. Указание столбцов, таблиц и значенийв качестве переменных параметров в команде SQL.
4. Выполнение команды SQL.
5. Сохранение результатов выполнения вхеше.
6. Создание виртуального представления вхеше, чтобы пользователь мог сортировать, фильтровать данные в БД иперемещаться по ней.
7. Редактирование данных.
8. Обновление источника данных всоответствии со всеми изменениями сделанными в хеше.
9. Фиксация или отмена изменений,внесенных в ходе транзакции, и последующее закрытие транзакции.
К классам объектов вмодели ADO относятся:
· Connection – представляет среду, в которойбудет выполняться обмен данными с источником данных. Соединение должно бытьустановлено до начала выполнения любых других операций.
· Command – способ управления источникомданных. Можно удалять, добавлять, обновлять и считывать данные из источника.
· Parameter – представляет переменные компонентыобъекта Command. В командах часто необходимоуказывать вспомогательные параметры, уточняющие способ выполнения команд.Параметры являются изменяемыми, так что перед выполнением команд их можномодифицировать
· Recordset – служит локальным хешем данных,считанных из источника данных.
· Field – представляет столбец таблицы Recordset. Поле содержит свойства определяющиеполе. Пример таких свойств – Type, Value.
· Error – возвращает результат всякий раз,когда в приложении возникает ошибка. Каждый объект Connection имеет отдельное семейство объектов Error.
· Property– определяет объекты Connection, Command, Field, Recordset. Каждый объект ADO обладает набором свойств, задающимобъект и управляющим его поведением.
· Collection – служит для объединения сходныхобъектов в группы.
Обращение к объектам ADO выглядит так:
ADODB. имя_объекта.
При создании новогопроекта, Access 2000 загружает только библиотекуобъектов ADO. Если необходимо работать с DAO, добавляется библиотека объектов DAO в диалоге Preferences редактора VB. Для открытия VB Editor надо нажать Alt + F11.Диалог Preferences открывается командой меню Tools>References. В этом диалоге надо выбрать DAO 3.6 Object Library.
Для того чтобы связатьобъект Recordset в модели ADO с данными необходимо:
Dim rst As NewADODB.Recordset
rst.OpenSQLVar,CurrentProject.Connection
Здесь SQLVar символьная переменная, в которойопределяется набор данных либо как выражение SQL, либо как имя таблицы. Например, если необходимооткрыть таблицу с именем Student,вторая строка будет выглядеть:
rst.Open “Student”, CurrentProject.Connection
В случае DAO необходимо создать объектнуюпеременную rst типа Recordset без ADODB, а затем использовать метод OpenRecordset:
Set rst =CurrentDB.OpenRecordset(SQLVar, dbOpenDynaset).
Здесь необходимо бытьаккуратным, поскольку написание для объектов Recordset в обеих моделях одинаково.
Для перехода в обеихмоделях используются методы Move:
· rst.MoveFirst | MoveLast | MoveNext | MovePrevious | Move n – соответственно: Перейти к первой записи | к последней | кследующей | к предыдущей | на nзаписей
Метод Find используется при поиске в наборезаписей, удовлетворяющих тем или иным условиям.
Переменная_Recordset критерий, Пропустить Строки,Направление Поиска, Старт
Здесь:
· критерий – строковоезначение (обязательно в кавычках), определяющее имя столбца (поля), операторсравнения и искомое значение. Это единственный обязательный параметр.
· Пропустить строки– обозначает число строк, начиная с текущей или стартовой позиции, котороенеобходимо пропустить перед началом поиска.
· Направлениепоиска определяет должен ли поиск вестись по направлению к концу набора (adSearchForward) или к началу (adSearchBackward).
· Старт – закладка,обозначающая начальное положение указателя текущей записи при поиске: adBookmarkFirst (1) – первая запись, adBookmarkLast (2) – последняя запись, adBookmarkCurrent (0) – текущая запись.
Dim Rst As NewADODB.Recordset
Rst.Open“Student”, CurrentProject.Connection
Rst.Find “Sgroup= ‘АП51’”
Rst.Close
Значение критерия можетбыть строкой, числом или датой. Если значение имеет тип даты, то онозаключается в #, например, #11/11/03#.
При обновлении записей спомощью Recordset.Open необходимо установить значения нескольких свойств,определяющих набор данных. Самыми важными из этих свойств являются свойства LockType и CursorType.
LockType определяет право доступа к набору ипринимает значения:
· AdLockReadOnly – объект доступен только для чтения(значение по умолчанию).
· AdLockPessimistic – записи блокируются сразу посленачала редактирования по одной.
· AdLockOptimistic – устанавливает блокировку привызове метода Update (используйте этот вариант).
· AdLockBatchOptimistic – разрешает пакетное обновление.
Свойство CursorType определяет тип курсора, применяемыйв наборе данных. Его действие подобно определению набора данных в модели DAO. CursorType может принимать одноиз следующихзначений:
· AdOpenForwardOnly – набор представляет собойстатическую копию данных, пригодную для поиска, но поиск возможен только внаправлении к концу набора (значение по умолчанию).
· AdOpenKeySet – позволяет вносить изменения внабор данных, но пользователь видит изменения, внесенные им самим.
· AdOpenDynamic – позволяет вносить изменения.Пользователь видит все результаты изменений. Наименее эффективен, но имеетбольше всего возможностей. Поэтому используйте его.
· AdOpenStatic – набор представляет собойстатическую копию данных.
Редактирование:
Rst.Open“Student”, CurrentProject.Connection, adOpenDynamic, adLockOptimistic
Rst.MoveFirst
Rst(“YearEnter”)= 2001
Rst.Update
Rst.Close
Обновляется поле YearEnter первой записи.
Добавление записи:
Rst.Open“Student”, CurrentProject.Connection, adOpenDynamic, adLockOptimistic
Rst.AddNew
Rst(“FIO”) = “Петров И.И.”
Rst(“YearEnter”)= 2003
Rst.Update
Ret.Close
Удаление записи:
Rst.Open“Student”, CurrentProject.Connection, adOpenDynamic, adLockOptimistic
Rst.MoveFirst
Rst.DeleteadAffectCurrent
Rst.Update
Rst.Close
2.Математические основы
Математическими основами индуктивного и дедуктивноговывода являются математическая логика и ее развитие логика предикатов первогопорядка.
Логика используется для того, чтобы доказыватьправильность или неправильность тех или иных утверждений или высказываний. Этоимеет большое значение при решении задач проектирования и для другихвычислительных задач. Так искусственный интеллект во многом опирается нагипотезу символьных систем. Упрощенно эта гипотеза утверждает, что, организовавогромную структуру взаимосвязанных символов, представляющих реальные знания исложный набор символьных процессов, позволяющий оперировать структурами с цельюсоздания новых структур, можно создать машину, работающую также хорошо в смыслеинтеллектуальной деятельности, как человек.
2.1Алгебра высказываний
Одним из основных понятий логики является понятиевысказывания, правильность или неправильность которого мы стараемся определить.Попытаемся определить смысл этого термина. Высказыванием называют предложения,про которые разумно говорить, разумно считать, что они являются истинными илиложными. Неуточненность понятий «истинно» и «ложно» делают понятие высказываниярасплывчатым. Однако, вводя ограничения можно это понятие уточнить. Фразы«Пойдем в кино?», «Да здравствует президент!» не являются высказываниями (как илюбые вопросительные и восклицательные предложения). Фраза «Треугольникназывается равносторонним, если все его стороны равны» (как и любое другоеопределение) также не является высказыванием. Фразы «2*2 = 4» и «3>5» — высказывания (первое истинное, второе ложное). Фраза «В повести “Шинель” 200755букв» — высказывание, но нам неизвестна его истинность. Фразу «Эта книгахорошая» не следует относить к высказываниям в традиционной логике в силунеопределенности понятия «хороший».
Поэтому, определим, как простое высказывание –высказывание, для которого в определенных условиях времени и места можно делатьвывод об его истинности или ложности, причем это высказывание задается простымпредложением («Сегодня идет дождь»).
Из простых высказываний с помощью связок можно строитьсложные высказывания, и тогда возникает задача определения их истинности взависимости от истинности простых высказываний, его составляющих.
Переменную, в область значений которой входят тольковысказывания (а точнее истинностные значения T, F) будем называтьвысказывательной переменной (двоичной или булевой). В силу определения областьюзначений этих переменных является двоичный алфавит.
Функции от любого конечного числа двоичных переменных,также способные принимать лишь два значения T и F, принятоназывать булевыми функциями. Иногда такие функции называют переключательными,так как реализующие такие функции схемы осуществляют переключение входныхканалов, подавая на них сигналы, то одного, то другого вида.
Областью определения булевых функций от n – переменных служит совокупностьвсевозможных n – мерных упорядоченных наборов(векторов размерностью n),компонентами которых являются буквы двоичного алфавита T и F.
Для любого n = 1, 2,… среди n –мерных наборов можно ввести естественную лексикографическую упорядоченность.Для этого поставим в соответствие с F – 0, а с T – 1. Тогда наборпреобразуется в последовательность 0 и 1. Такой набор уже можно рассматриватькак представление целого неотрицательного числа в двоичной системе счисления.Например, TTTF ® 1110 ® 14. Это число будем называть номеромнабора. Эти наборы называются также кортежами или, используя геометрическуютерминологию, точками.
Последнее название связано с тем, что имеетсяестественная возможность отождествлять различные n – мерные наборы с вершинами n-мерного куба.
Естественную упорядоченность наборов мы получим, еслирасположим их в порядке возрастания номеров. Первым в таком расположенииявляется нулевой набор, все компоненты которого 0, последним – набор, всекомпоненты которого 1.
Отсюда, наборы размерности n нумеруются числами от 0 до 2n-1. А отсюда в частности вытекает:
1. Имеется в точности 2n двоичных n-мерных наборов.
Нетрудно также подсчитать число различных булевыхфункций от n переменных. Для каждого наборазначений, независимо от значений других наборов, можно выбрать в качествезначений функции T или F. Следовательно, прибавление каждогонового набора к области определения булевой функции увеличивает число различныхбулевых функций ровно в два раза.
На одном наборе можно определить две различных булевыхфункции. На двух – 22 и т. д. Продолжая подобным образом и с учетом1, получим:
2. Имеется точно /> различныхбулевых функций от n переменных.
Следует отметить, что здесь и далее к числу функций отn переменных относятся и такие функцииf(x1, x2,.. ., xn), которые не зависят от тех или иныхпеременных xi. В частности, в числе функцийокажутся функции – константы (тождественная истина и тождественная ложь),которые можно рассматривать как функции от нуля переменных.
Условимся называть невырожденными функциями от n переменных такие функции, которыесущественно зависят от всех этих переменных. Функции же от n переменных, сводящиеся к функциям отменьшего числа переменных называются вырожденными.
В теории булевых функций особое значение имеют функцииодной и двух переменных. Имеется всего /> =4 разных функций одной переменной.
x f
G1
G2
G3
G4
1 11
1 1G1, G4 – константы 0 и 1.
G2 = x.
/> и называется функцией отрицания илиинверсии.
Число булевых функций отдвух переменных равно />. Выпишем своднуютаблицу всех этих функций.
x y F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Из выписанных функцийшесть будут вырожденными, а именно функции F1, F4, F6, F11, F13, F16. Действительно, легко видеть:
/>
Остальные функции будут невырожденными. Введем для нихспециальные названия и обозначения.
Функция F2 носит название конъюнкции илипроизведения или логического И. Для ее обозначения используется либо знакумножения, либо Ù. Отсюда:
/>
Функция F7 носит название функциинеравнозначности или суммы по модулю два. Для ее обозначения будемиспользовать:
/>
Функция F8 носит название дизъюнкции илилогическое ИЛИ. Для ее обозначения принято использовать знак Ú:
/>
Функцию F9 будем называть отрицаниемдизъюнкции или стрелкой Пирса, и обозначать через:
/>
Функция F10 носит название функцииравнозначности или эквивалентности и обозначается:
/>
Функции F12 и F14 носят название импликации. Для их обозначения будем использовать:
/>
Здесь следует отметить,что импликация соответствует высказыванию «Если А, то В». При этом возникаетситуация, что это высказывание с ложным А и истинным В истинно. Прежде всего,это соглашение, причем это соглашение ничему не противоречит. В повседневномязыке утверждения с ложным А не употребляются.
Пример типа «Если бы ябыл космонавтом, я бы полетел на Луну» не опровергает наше утверждение. Здесь1. Имеем дело не с «Если А, то В», а с «Если бы А, то бы В»; 2. Считать ложнымтакое утверждение не имеет смысла.
Возникает вопрос, можноли бы было при ложном А, считать ложным высказывание «Если А, то В». В принципеможно, но математическая практика показывает, что выбранный нами вариантудобнее.
Приведем пример. Известно,что при возведении в квадрат обоих частей уравнения могут появиться новыекорни. При этом подразумевается, что при возведении в квадрат корни потерятьсяне могут. Что это значит. Это значит, что любой корень уравнения:
/>
является также корнемуравнения
/>
Это высказывание мы считаем верным, хотя исходноеуравнение может вовсе не иметь корней. Ясно, что здесь мы использоваливведенное соглашение.
Функция F15 носит название отрицаниеконъюнкции или штрих Шеффера. Для ее обозначения используется:
/>
Оставшиеся функции F3 и F5 назовем отрицание импликации:
/>
Для построения исчисления высказываний важным являетсявопрос о построении функционально полной системы функций.
Будем говорить, чтосистема логических функций называется функционально полной, если существуеталгоритм, позволяющий строить из этих функций любые наперед заданные функции.Функционально полная система называется несократимой, если исключениекакой-либо входящей в нее функции лишает систему свойства функциональнойполноты.
Можно показать, что:Максимальное число функций в несократимой функционально полной системе булевыхфункций от двух переменных равно четырем. Таким образом, для булевой алгебрыможно построить несколько вариантов функционально полных систем. В частности,стрелка Пирса и штрих Шеффера каждый по отдельности составляют функциональнополную систему. Однако наиболее часто в качестве функционально полной системыиспользуются: отрицание, конъюнкция и дизъюнкция.
Функции F7, F9, F15, F5, F3 уже выражены через эти операции. Выразим функции F10, F12, F14.
/>
Фактически значение любой функции можно получить потаблице ее истинности. Однако, это значение можно получить, представив функциибулевой алгебры с помощью алгебраических функций.
Алгебраическиперечисленные выше операции можно выразить следующим образом:
Отрицание(дополнение): />
Конъюнкция: />
Дизъюнкция: />
Тогда:
Сумма по модулю 2: />
Стрелка Пирса: />
Эквивалентность: />
Импликация: />
Штрих Шеффера: />
Отрицания импликации: />
Отметим, что эти формулы справедливы длябесконечнозначных и многозначных логик.
Законы булевойалгебры.
Для удобства разобьем законы на четыре группы.
Первая группа.
1. /> (закон коммутативности длядизъюнкции).
2. />
3. /> (первый закон поглощения).
4. /> (второй закондистрибутивности).
5. /> (закон идемпотентности длядизъюнкции).
Следующие пять законовполучаются заменой Ù на Ú инаоборот.
1¢. /> (закон коммутативности дляконъюнкции).
2¢. /> (законассоциативности для конъюнкции).
3¢. /> (второйзакон поглощения).
4¢. /> (первыйзакон дистрибутивности)
5¢. /> (законидемпотентности для конъюнкции).
Каждый из законов 1¢ — 5¢ называется двойственным ксоответствующему закону 1 – 5.
Вторая группа1. /> />
2. />/> />
3. /> />
4. /> />
5. /> />
6. /> />
Третья группа1. /> (закон двойногоотрицания).
2. />
3. />
Четвертая группа1. />
2. /> (закон контрапозиции).
3. />
Сформулируем некоторыеполезные следствия из приведенных законов.
С1. Выбрасывая изпроизвольной дизъюнкции дизъюнктивные элементы равные нулю, мы не изменимвеличину этой дизъюнкции.
С2. Если в дизъюнкциихотя бы один из элементов равен 1, то вся дизъюнкция равна 1.
С3. Выбрасывая изпроизвольной конъюнкции все сомножители равные 1, мы не изменим ее величины.
С4. Если в конъюнкциихотя бы один сомножитель равен 0, то все произведение равно 0.
С5. Дизъюнкция илипроизведение любого числа одинаковых элементов равняется А.
Эти следствия можнодоказать по индукции.
С6. Если А(а1,… ., ап)произвольное выражение булевой алгебры, построенное из выражений а1,… ., ап спомощью операций отрицания, дизъюнкции и конъюнкции, то отрицание этоговыражения равняется />, где В(а1,…, ап)получается из А с помощью замены всех умножений на дизъюнкции, а всех дизъюнкцийна умножения, при условии сохранения всех имевшихся в А отрицаний.
С7. Если к некоторомувыражению А булевой алгебры применено более чем одно отрицание, то, не меняязначения выражения, можно исключить любое четное число отрицаний.
Нормальные формыЭлементарной дизъюнкциейназывается выражение,/>представляющеесобой дизъюнкцию любого конечного множества попарно различных между собойпеременных, часть которых (возможна пустая) взята со знаком отрицания. К числуэлементарных дизъюнкций будем также относить выражения, состоящие из однойпеременной (с отрицанием или без), а также константу 0.
В силу определения: />
являются элементарнымидизъюнкциями, а /> не являются.
Элементарнымпроизведением называется выражение, представляющее собой произведение любогоконечного множества попарно различных между собой переменных, над частьюкоторых (быть может пустой) поставлен знак отрицания. К числу элементарныхпроизведений также относятся выражения с одной переменной с отрицанием или без,а также константа 1. Элементарные произведения: /> Неэлементарныепроизведения: /> Переменные и ихотрицания называются первичными термами или литералами.
Дизъюнкция любого числапервичных термов равна либо 1, либо элементарной дизъюнкции. Произведениелюбого числа первичных термов равно либо 0, либо элементарному произведению.
Нормальной дизъюнктивнойформой (ДНФ) называется дизъюнкция любого конечного множества попарно различныхпроизведений.
Конъюнктивной нормальнойформой (КНФ) называется произведение любого конечного множества попарноразличных дизъюнкций.
Алгоритм приведения к ДНФи КНФ заключается в следующем.
1. Преобразовать выражение в соответствиис операциями отрицания.
2. Использовать первый (ДНФ) или второй(КНФ) законы дистрибутивности.
Пример: Привести к ДНФ и КНФ выражение.
/>
На первом этапе обрабатываем знаки отрицания:
/>
Раскрывая скобки, приведем к ДНФ:
/>
При приведении к КНФпоследовательно применяем второй закон к первой скобке выражения />
/>
Рассмотрим некоторое множество М булевых переменных. Вкачестве такого множества будем выбирать множество аргументов той или инойбулевой функции.
Элементарные дизъюнкцииназываются конституантами 0 для данного множества М булевых переменных, еслиони содержат в прямом либо инверсном виде все переменные множества М.
Элементарные конъюнкцииназываются конституантами 1 для данного множества М булевых переменных, еслиони содержат в прямом либо инверсном виде все переменные множества М.
Для переменных /> произвольную конституантунуля можно представить в виде /> апроизвольную конституанту 0 в виде /> где /> означает либо />, либо /> . Условимся нумероватьконституанты нуля и единицы с помощью тех же номеров, что и соответствующие имнаборы переменных.
ДНФ/КНФ называетсясовершенной (СДНФ/СКНФ), если все составляющие ее элементарныепроизведения/дизъюнкции являются конституантами единицы/нуля для одного и тогоже множества М переменных. СДНФ/СКНФ называется СДНФ/СКНФ булевой функции f, если она равна этой функции и еслимножество, составляющих ее переменных, совпадает с множеством аргументовфункции f.
Справедливо следующее:Любая булева функция имеет одну и только одну СДНФ/СКНФ.
Рассмотри процессприведения к СДНФ/СКНФ.
Рассмотрим произвольнуюДНФ j от переменных x1,… ., xn. Пусть некоторые элементарные произведения p, входящие в эту форму, не содержаткакой либо переменной xj. Тогда эти произведения можно заменить равными им выражениями
/>
Продолжая этот процесс относительно других переменныхмножества аргументов функции, не входящих в то или иное элементарноепроизведение, после повторения этой процедуры некоторое конечное число разполучим СДНФ выражения j,поскольку в каждое составляющее ее элементарное произведение будут входить всепеременные из множества аргументов функции.
Назовем этот процессприведением ДНФ к совершенному виду.
Аналогичным образом можнопостроить процесс приведения КНФ к совершенному виду. Для этой цели к входящейв КНФ произвольной элементарной дизъюнкции q, не содержащей, например, переменной />, добавляется равный нулюэлемент />. Затем к полученномувыражению применяется второй дистрибутивный закон:
/>
Продолжая по аналогии, мы сможем в каждую элементарнуюдизъюнкцию ввести все недостающие в ней переменные, после чего формапревратится в совершенную.
Пример: Выражение /> привести к СДНФ и СКНФ.
1. />
2.
/>
Синтез логическихвыражений.
Используя таблицу истинности любой логической формулы,можно определить ее в СДНФ или СКНФ. Для построения СДНФ в таблице истинностинеобходимо выбрать строки, в которых функция принимает значение 1 исформировать конституанту 0. Переменная будет находиться в этой конституантебез знака отрицания, если она принимает значение 1 в этой строке и с отрицаниемв противном случае. Соединить полученные конституанты знаком дизъюнкции.
Для получения СКНФ ищутся строки, в которых функцияпринимает значение 0. Строятся конституанты 1. Переменная берется со знакомотрицания, если она равна 1 и наоборот. Конституанты соединяются знакомконъюнкции.
Пример: Дана таблица истинности. Построить СДНФ иСКНФ.
x
y
z
f
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1СДНФ: />
СКНФ: />
Минимизация булевых функции
Под минимизацией булевых функций понимается нахождениенаиболее простого представления этой функции в виде суперпозиции функций,составляющих какую-нибудь фиксированную функционально полую систему S булевых функций. Наиболее простымобычно считается представление, содержащее наименьшее возможное числосуперпозиций. При решении задачи минимизации важную роль играет понятие импликанты.
Булева функция /> называется импликантойфункции />, если на любом значениипеременных />, на котором значение g равно 1, значение f также равно 1.
Простой импликантойфункции f называется элементарное произведение/>, являющееся импликантой f и такое, что никакая его собственнаячасть (то есть произведение, получаемое из g отбрасыванием одного или нескольких компонент) уже неявляется импликантой функции f.
Дизъюнкция любогомножества импликант одной и той же функции является импликантой этой функции.
Дизъюнкция всех простыхимпликант булевой функции совпадает с этой функцией и называется сокращеннойдизъюнктивной нормальной формой.
Сокращенная нормальнаяформа является более экономной, чем СДНФ. Однако часто допускает дальнейшееупрощение за счет того, что некоторые из простых импликант могут поглощатьсядизъюнкцией других простых импликант. Например, в сокращенной ДНФ />простая импликанта yz поглощается дизъюнкцией остальныхэлементов формы: />.
Однако справедливоследующее утверждение для сокращенной дизъюнктивной формы. Если сокращенная ДНФне содержит никакой переменной, входящей в нее одновременно с отрицанием и безнего, то эта форма является минимальной дизъюнктивной формой.
Приведение к минимальнойнормальной форме от сокращенной ДНФ можно осуществит с помощью импликантнойтаблицы. Импликантная таблица представляет собой прямоугольную таблицу, строкикоторой обозначаются различными простыми импликантами, а столбцы конституантамиединицы, на которых функция обращается в единицу.
На пересечении p-й строки k-го столбца импликантной таблицы ставится * тогда и толькотогда, когда импликанта составляет некоторую часть конституанты k. Для примера: