ЛОГИЧЕСКОЕ И ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

Целью логического и функционального программирования является вывод решений и они тесно связаны с задачами, решаемыми в искусственном интеллекте и экспертных системах (ЭС). На начальном этапе развития систем искусственного интеллекта (СИИ) и ЭС даже выделился целый класс специализированных языков программирования: языки логического и функционального программирования.

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

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

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

Наиболее известными языками функционального программирования являются ЛИСП и РЕФАЛ, а логического — Пролог. Однако, с развитием языков программирования (в частности, с появлением объектно-ориентированных языков) и баз данных область их применения сузилась. Так ЛИСП используется как оболочка Автокад, а РЕФАЛ как средство для построения метаязыков и метакомпиляторов.

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

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

Прямой и обратный вывод

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

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

Если <�условие>, То <�вывод>.

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

Для представления таких задач принято использовать дерево решений — специальную диаграмму для представления возможных решений. Дерево решений состоит из вершин двух типов. Вершины решений, содержащие вопросы, обозначаются окружностями. Цели или логические выводы обозначаются прямоугольниками. Вершины нумеруются. Каждая вершина может иметь не более одного входа. Рассмотрим простейший пример с приемом на работу, часто используемый в литературе.

Дерево решений будем хранить в следующей таблице [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 ко второму классу. Далее приводится таблица со значениями признаков для этих объектов.

Объекты для этой таблицы (надо нарисовать).

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

ЕСЛИ А ТО В,

ЕСЛИ (условие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).

Математическая запись этих правил выглядит следующим образом:

Такие правила имеют две основных характеристики: точность и полноту.

Точность правила — это доля случаев, когда правило подтверждается, среди всех случаев его применения (доля случаев В среди случаев А).

Полнота — это доля случаев, когда правило подтверждается, среди всех случаев, когда имеет место объяснимый исход (доля случаев А среди случаев В).

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

Точное, но неполное правило: Люди смертны (А — человек, В — смертен).

Неточное, но полное правило: Студенты посещают занятия (А — студент, В — посещает).

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

Вернемся к примеру.

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

Здесь одинаковой и максимальной силой обладают сразу семь признаков: Х2, Х3, Х6, Х7, Х10, Х11, Х14, Х15. Поэтому случайным образом выбираем один из них в качестве ведущего. Пусть это будет Х6. От этого признака отходит две ветви. Первая для значения Х6 = 0, а вторая — для Х6 = 1.

Для ветви Х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 в папке Sqlx86Setup.

Иерархия 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 New ADODB. Recordset

rst.Open SQLVar, 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 New ADODB. 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.Delete adAffectCurrent

Rst.Update

Rst.Close

2. Математические основы

Математическими основами индуктивного и дедуктивного вывода являются математическая логика и ее развитие логика предикатов первого порядка.

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

2.1 Алгебра высказываний

Одним из основных понятий логики является понятие высказывания, правильность или неправильность которого мы стараемся определить. Попытаемся определить смысл этого термина. Высказыванием называют предложения, про которые разумно говорить, разумно считать, что они являются истинными или ложными. Неуточненность понятий «истинно» и «ложно» делают понятие высказывания расплывчатым. Однако, вводя ограничения можно это понятие уточнить. Фразы «Пойдем в кино?», «Да здравствует президент!» не являются высказываниями (как и любые вопросительные и восклицательные предложения). Фраза «Треугольник называется равносторонним, если все его стороны равны» (как и любое другое определение) также не является высказыванием. Фразы «2*2 = 4» и «3>5» — высказывания (первое истинное, второе ложное). Фраза «В повести „Шинель“ 200 755 букв» — высказывание, но нам неизвестна его истинность. Фразу «Эта книга хорошая» не следует относить к высказываниям в традиционной логике в силу неопределенности понятия «хороший».

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

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

Переменную, в область значений которой входят только высказывания (а точнее истинностные значения 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 до 2^n-1. А отсюда в частности вытекает:

1. Имеется в точности 2ⁿ двоичных n-мерных наборов.

Нетрудно также подсчитать число различных булевых функций от n переменных. Для каждого набора значений, независимо от значений других наборов, можно выбрать в качестве значений функции T или F. Следовательно, прибавление каждого нового набора к области определения булевой функции увеличивает число различных булевых функций ровно в два раза.

На одном наборе можно определить две различных булевых функции. На двух — 2² и т. д. Продолжая подобным образом и с учетом 1, получим:

2. Имеется точно различных булевых функций от n переменных.

Следует отметить, что здесь и далее к числу функций от n переменных относятся и такие функции f (x1, x2,.. ., xn), которые не зависят от тех или иных переменных xi. В частности, в числе функций окажутся функции — константы (тождественная истина и тождественная ложь), которые можно рассматривать как функции от нуля переменных.

Условимся называть невырожденными функциями от n переменных такие функции, которые существенно зависят от всех этих переменных. Функции же от n переменных, сводящиеся к функциям от меньшего числа переменных называются вырожденными.

В теории булевых функций особое значение имеют функции одной и двух переменных. Имеется всего = 4 разных функций одной переменной.

G1, G4 — константы 0 и 1.

G2 = x.

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

Число булевых функций от двух переменных равно. Выпишем сводную таблицу всех этих функций.

Из выписанных функций шесть будут вырожденными, а именно функции 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.

Справедливо следующее: Любая булева функция имеет одну и только одну СДНФ/СКНФ.

Рассмотри процесс приведения к СДНФ/СКНФ.

Рассмотрим произвольную ДНФ от переменных x₁,.. ., x_n. Пусть некоторые элементарные произведения p, входящие в эту форму, не содержат какой либо переменной x_j. Тогда эти произведения можно заменить равными им выражениями

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

Назовем этот процесс приведением ДНФ к совершенному виду.

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

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

Пример: Выражение привести к СДНФ и СКНФ.

1.

2.

Синтез логических выражений.

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

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

Пример: Дана таблица истинности. Построить СДНФ и СКНФ.

СДНФ:

СКНФ:

Минимизация булевых функции

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

Булева функция называется импликантой функции, если на любом значении переменных, на котором значение g равно 1, значение f также равно 1.

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

Дизъюнкция любого множества импликант одной и той же функции является импликантой этой функции.

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

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

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

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

На пересечении p-й строки k-го столбца импликантной таблицы ставится * тогда и только тогда, когда импликанта составляет некоторую часть конституанты k. Для примера:

Система S простых импликант булевых функций f называется приведенной, если эта система полна и никакая ее часть не является полной системой импликант функции f. Дизъюнкция всех простых импликант, составляющих S, называется приведенной или тупиковой дизъюнктивной нормальной формой. Всякая минимальная ДНФ является тупиковой ДНФ.

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

Суть этого метода заключается в том, что по импликантной таблице строится некоторое выражение, называемое конъюнктивным представлением этой таблицы. Для этого производится обозначение всех простых импликант различными буквами (например, A, B, C, …). После этого для каждого столбца импликантной таблицы строится дизъюнкция всех букв, обозначающих строки, на пересечении которых со столбцом стоит *. Беря произведение полученных q для всех столбцов, конъюнктивное представление таблицы. Обозначим для нашего примера:. Тогда получим следующее представление таблицы:

Если в конъюнктивном представлении раскрыть все скобки в соответствии с законом дистрибутивности, получим дизъюнктивное представление.

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

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

Термам этого представления соответствуют все приведенные системы простых импликант функции.

В примере получим:

То есть получим 2 приведенные системы простых импликант (A, B, C) и (A, B, D). Им соответствуют две тупиковые ДНФ исходной функции:

Алгоритм Квайна.

1.Минимизируемая булева функция f от произвольного числа n переменных записывается в СДНФ f₀.

2.Начиная с f₀, строим последовательность ДНФ f₀, f₁,.. ., f_i,. .. до тех пор пока две какие либо ДНФ f_k и f_k+1 не совпадут между собой. Переход от формы f_i к f_i+1 по следующему правилу: в форме f_i выполняются все операции неполного склеивания Применимые к элементарным произведениям длины n =. После этого исключаются все те элементарные произведения длины, которые могут быть исключены на основании формулы элементарного поглощения:

.

3.Результатом алгоритма Квайна к функции f является заключительная ДНФ f_k.

Для любой булевой функции f результатом применения алгоритма Квайна к СДНФ будет сокращенная ДНФ этой функции.

Пример:

Операцию неполного склеивания можно применить к 1 и 3 элементу формулы, к 1 и 2, а также к 1 и 4. В результате получим:

Применяя формулу поглощения, получим:

Поскольку операция неполного склеивания дальше неприменима, f₁ — сокращенная ДНФ.

Диаграмма Вейча

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

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

Пример:

Синтаксис, семантика и правила вывода в исчислении высказываний

Синтаксис исчисления высказываний определяется правилами грамматики:

Предложение: = Элементарное предложение / Сложное предложение

Сложное предложение: = Предложение Связка Предложение /^{Предложение} / (Предложение)

Связка: = / / ^ / /

Семантика исчисления высказываний определяется с помощью таблиц истинности.

К правилам вывода относятся:

1.

Если посылка, А есть истина, то и заключение В есть истина.

2.Исключение И:

Знание того, что, А и В есть истина, должно означать, что, А есть истина и В есть истина.

3.Интродукция ИЛИ:

Если, А есть истина, то, А или В есть истина. То же самое имеет место, если В есть истина.

4.Интродукция И:

Если, А есть истина и В есть истина, то, А И В есть истина.

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

Если, А есть не не истина, то, А есть истина.

6.Единичная резолюция:

Если, А или В есть истина и не В, то, А есть истина. Точно также, если не А, то В — истина.

7.Резолюция:

Если, А или В и не В или С, то, поскольку В не может быть истинно и ложно одновременно, должно быть, А или С истинно.

Пример: Имеется следующая информация.

Если аккумулятор машины разряжен, то машина не заводится. Если машина Ивана не заводится и текущее время оказывается позже восьми часов утра, то Иван опоздает на поезд. Однажды после восьми утра аккумулятор Ивана оказался разряженным.

Используя логические правила вывода, доказать, что Иван опоздает на поезд.

В символьных обозначениях информация может быть представлена в следующем виде:

P: аккумулятор разряжен.

Q: машина не заводится.

R: время после восьми утра.

S: Иван опоздал на поезд.

Правило 1: P Q.

Правило 2. QR S.

Известно, что P и R есть истина. Задачей является доказать S. Доказательство строится следующим образом:

1. P — дано.

2. R — дано.

3. Q следует из 1 и правила 1 по правилу modes ponens.

4. QR следует из 3 и 2 по правилу интродукции И.

5. S следует из 4 и правила 2 по правилу modes ponens.

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

Практические задания

Задание 1

Даны логические функции:

Получить значения этих функций с помощью таблиц истинности. Преобразовать к алгебраическому виду и определить значения для x =1, y =1, z = 0. Преобразовать к виду с использованием только операций дизъюнкции, конъюнкции и отрицания. Упростить. Привести к СДНФ и СКНФ. Восстановить СДНФ и СКНФ по таблице истинности. Построить импликантную таблицу и определить сокращенную ДНФ с использованием метода Петрика. Минимизировать с использованием алгоритма Квайна и диаграммы Вейча.

Задание 2

Если собака видит кошку, то она за ней гонится. Если за котом Васькой гонится собака и рядом есть дерево, то кот Васька забирается на дерево. В саду много деревьев. Однажды, в саду Ваську увидела собака.

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

Компьютерное задание

Реализовать программу решающую следующую задачу:

На входе программы — таблица истинности для функции четырех переменных.

На выходе программы — СДНФ, СКНФ, диаграмма Вейча и минимальная нормальная форма.

2.2 Исчисление предикатов

Исчисление предикатов расширяет язык исчисления высказываний так, что мир оказывается, состоящим из объектов, отношений и свойств.

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

1. Слова, задающие сущности изучаемого мира.

2. Слова, задающие атрибуты / свойства этих сущностей, а также их поведение и отношения.

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

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

Например, функция f (x, y) принимает некоторые значения, которые определяются значениями констант и переменных (аргументов функции), содержащимися под знаком функции. Эти значения, так же как и аргументы, являются некоторыми сущностями рассматриваемого мира. Поэтому все они объединяются общим названием терм (константы, переменные, функции).

Атомарным предикатом (атомом) называется последовательность из n (1 n <) термов, заключенных в круглые скобки, следующие за предикатным символом, имя которого выражается конечной последовательностью букв. Предикат принимает одно из двух значений true или false в соответствии со значениями, входящих в него термов.

Предикат Нераспространенное простое предложение

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

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

но используются т.к. эквивалентен фразе «Если А, то В», а — «А и В эквивалентны».

В качестве символов второго класса используются и. Эти символы называются кванторами общности и существования, соответственно. Переменная, которая квантифицирована, т. е. к ней применен один из кванторов, называется связанной. Квантор общности является обобщением, аналогом конъюнкции, а квантор существования — обобщением, аналогом дизъюнкции на произвольное, не обязательно конечное множество.

Действительно, пусть Тогда для любого предиката U выполняется:

Аналогом законов Де Моргана для кванторов являются:

Часто возникает ситуация, когда некоторые переменные связываются кванторами, а все другие —. В этом случае может возникнуть неоднозначность при интерпретации кванторов.

Пусть задан некоторый предикат U (x, y). Очевидно, что возможно восемь случаев связывания его кванторами существования и общности:

Необходимо дать интерпретацию этим восьми случаям.

Рассмотрим, например, предикат подсистема (x, y), который задает отношение x подсистема y. Пусть переменная x связана квантором общности, а y — квантором существования. В этом случае существует две интерпретации: 1. «Для всех x, существует y, для которых x подсистема», 2. «Существует y, что все x его подсистемы».

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

— (x)(y)подсистема (x, y) — все объекты являются подсистемами;

— (x)(y)подсистема (x,y) — существует объект, который является подсистемой любого объекта;

— (y)(x)подсистема (x, y) — для всякого объекта существует объект, являющийся его подсистемой;

— (x)(y)подсистема (x, y) — существует объект, который является чей-то подсистемой.

Сделаем некоторые важные обобщения.

1.Чтобы найти отрицание выражения, начинающегося с кванторов, надо каждый квантор заменить на его двойственный и перенести знак отрицания за кванторы. Отсюда:

2.Одноименные кванторы можно переставлять. Разноименные кванторы можно переставлять только в одну сторону. Отсюда:

Если то

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

Если то

Действительно, если существует y, что все x его подсистемы, то для всех x существует y, для которого x подсистемы. Однако, перестановка в обратную сторону неверна. Например:

Если то необязательно.

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