Для выбора «лучшего» алгоритма необходимо получение оценок или границ для объема памяти и времени работы ЭВМ, которое потребуется алгоритму для обработки конкретных данных. 1 страница

 

ГЛОССАРИЙ К МОДУЛЮ 2

Краткость символики способствует постижению сути дела, в то время как словесное выражение перегружает разум.

Т. Клайн

 

Абстрактный алфавит - это конечная совокупность объектов, называемых буквами или символами этого алфавита.

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

Алгоритм – это преобразование слов в абстрактном алфавите.

Алгоритм – это алфавитный оператор, задаваемый с помощью конечной системы правил.

Алгоритм – это алфавитный оператор с правилами, определяющими его действие.

Алгоритмический процесс – это последовательность действий в алгоритме.

Алгоритмический язык – это язык, на основании которого формулируется алгоритм.

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

Временная сложность алгоритма – это изменение алгоритма во времени или время, затраченное алгоритмом как функция размерности задачи.

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

Вычислимая функция – это функция, для которой имеется способ получения ее значений.

Вычислительная сложность алгоритма обычно называется временем работы алгоритма.

Графические схемы алгоритмов (ГСА) - представляют собой графическую интерпретацию алгоритмов Ляпунова.

Детерминированность – это свойство алгоритма выполнять на каждом шаге однозначные и независимые от исходных данных действия.

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

Длинаслова в абстрактном алфавите определяется числом символов.

Жадныйалгоритм на каждом шаге делает локально оптимальный выбор, - в предположении, что итоговое решение окажется оптимальным.

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

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

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

Интуиция — это знание, полученное на основе опыта, но не подвергнутое научному анализу.

Корректность – это свойство алгоритма при решении определенного класса задач давать правильные результаты для всех допустимых исходных данных.

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

Лингвистическая переменная - это кортеж Л = < b, Т, X >, где b — наименование; Т — множество значений переменной, представляющих наименования, областью определения которых является X.

Линейный алгоритм - это алгоритм, у которого зависимость времени решения от числа входов носит линейный характер.

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

Массовость — это свойство алгоритма быть применимым для множества исходных данных.

Машина Тьюринга (МТ) - детерминированное устройство, состоящее из трех частей: ленты, считывающего устройства (головки) и управляющего устройства (УУ).

Многозначный алфавитный оператор каждому входному слову может поставить в соответствие некоторое множество выходных слов.

NP -полные (Nondeterministic Polynomial - недетерминированные полиномиальные) задачи – задачи, для которых не найдены полиномиальные алгоритмы, однако и не доказано, что таких алгоритмов не существует.

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

Неправильный алгоритм – алгоритм, который для некоторого входа не останавливается или дает неправильный результат.

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

Нечеткий алгоритм принятия решений - служит для получения приближенного описания стратегии и решающего правила.

Нормальные алгоритмы Маркова (НАМ) основаны на использовании абстрактных алфавитов и марковских подстановок. В качестве исходных данных и конечных результатов используют строки символов, т.е. слова абстрактных алфавитов.

Область определения алфавитного оператора – это множество слов, на котором он определен.

Однозначный алфавитный оператор ставит в соответствие каждому входному слову одно выходное слово.

Операнды — это объекты, над которыми выполняются операции, предписываемые алгоритмами.

Операторный алгоритм Ван-Хао задается последовательностью приказов специального вида. Каждый приказ имеет определенный номер и указание, какую операцию необходимо выполнить над заданным объектом и с каким номером следует далее выполнять действие над результатом этой операции.

Определенность – это свойство алгоритма быть точным и полностью задает все его действия.

Первая универсальная алгоритмическая модель – определяется на основе соответствия между словами в абстрактном алфавите.

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

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

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

Полиномиальные алгоритмы – это алгоритмы, у которых время решения находится в полиномиальной зависимости от изменения размера входных данных.

Порочный круг - это определение, в котором новое понятие выводится либо из самого себя, либо из другого понятия, которое было из него выведено.

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

Примитивно - рекурсивные функции – это функции, полученные без использования оператора построения по первому нулю.

Псевдокод – это описание представляет симбиоз из основных операторов различных языков программирования с использованием комментариев для описания действий алгоритма.

Равные алгоритмы – это алгоритмы, имеющие одинаковые АО и совпадающие системы правил, задающих действие этих алгоритмов на входные слова.

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

Расплывчатая переменная - это кортеж П = < a, X, >, где a — наименование расплывчатой переменной; X = {x₁, х ₂,..., х _n } — область ее определения; A = {  (x_i) | x_i } x_i Î X — расплывчатое множество в X, определяющее ограничения на возможные значения П.

Результативность — это свойство алгоритма, обеспечивающее получение результата через конечное число шагов.

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

Рекурсивная процедура – это прямое или косвенное обращение к себе в процессе выполнения алгоритма.

Рекурсивные определения - состоят из двух частей: 1-я — циклическая, 2-я — прямая часть определения, которая является входом в циклическую.

Рекурсивные функции - представляют собой частичный класс вычислимых функций.

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

Символыабстрактного алфавита - это буквы, цифры, любые знаки, слова, предложения, любые тексты.

Словесная схема алгоритма (СА) задается через описание и перечисление операторов, аналогичных блокам, используемым структурной схемой алгоритма. Таким образом, словесная запись алгоритма представляет собой перечень операторов, пронумерованный в порядке их исполнения алгоритмом.

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

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

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

Тезис Тьюринга - любой алгоритм может быть реализован на машине Тьюринга.

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

Циклический алгоритм – это алгоритм, который выполняется путем многократного повторения некоторой последовательности действий.

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

Численные алгоритмы - это алгоритмы, в которых решения поставленных задач сводятся к арифметическим действиям.

Шаг алгоритма – это каждое отдельное действие алгоритма.

Эвристические алгоритмы (или эвристики) - это алгоритмы, теоретически не обоснованные, но позволяющие сократить количество переборов в пространстве поиска.

Эквивалентные алгоритмы – это алгоритмы с совпадающими АО, но не совпадающими способами их задания.

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

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

Языкоперандов - это язык, предложения которого являются допустимыми для алгоритма вариантами исходных данных.

 

Логика – это искусство ошибаться с уверенностью в своей правоте.

Д. Крач

 

 

Модуль 3. АЛГЕБРА ЛОГИКИ

(1,5 кредита)

Комплексная цель и задачи изучения модуля

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

В результате освоения Модуля 3 студент должен быть готов продемонстрировать следующие компетенции и уровень подготовки:

1) умение применять на практике законы и тождества алгебры логики, доказывать справедливость тождеств алгебры логики;

2) знание основных законов алгебры логики;

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

Самостоятельная работа предусматривает проработку лекций (1,2 часа в неделю), тестирование, а также изучение литературы, формулировку цели работы, объекта и задач исследования, методов, источников и средств библиографического поиска, использованных для достижения поставленной цели.

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

Глава 12. Элементы алгебры логики

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

Д. Локк

 

Алгебра логики, основные логические функции, основные логические операции, основные логические тождества и законы

ЦЕЛИ

Освоив эту главу, учащиеся должны знать и уметь:

· определять основные логические функции;

· строить таблицы истинности логических функций и операций;

· доказывать истинность логических тождеств;

12.1. Логические функции

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

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

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

Все люди смертны.

Сократ – человек.

Следовательно, Сократ смертен.

В XIX веке Пирс сформулировал абдуктивную логику. В ее основу он положил три основных принципа (Непейвода Н.Н.):

- индукция – получение общего закона по множеству частных случаев;

- дедукция – получение из общего утверждения другого общего либо частного;

- абдукция – получение нового частного случая из множества частных случаев.

Основная задача математической логики (МЛ): заменить рассуждения вычислениями». Основа математической логики была заложена в трудах де Моргана, Буля, Пирса, Кантора, Геделя, Маркова, Клини, Ляпунова и многих других ученых. Марков говорил: «Математическая логика – логика по предмету, математика по методу». Язык математической логики, ставший символическим языком современной математики, возник, когда неудобство математического языка для нужд математики было окончательно осознано. Следовательно, математическая логика – наука, изучающая саму математику математическими средствами.

Математическая логика изучает формальную структуру рассуждений математическими средствами. Язык математической логики – исторически первый, точно определенный формальный язык.

Существует двузначная и многозначная логика. Двузначная логика имеет дело с объектами, которые принимают одно из двух возможных значений (0, 1). Объекты, содержащие и принимающие значения из конечного множества, содержащего больше двух элементов, называют многозначными, они обрабатываются аппаратом многозначной логики или сводятся к двузначным объектам.

Высказывание – утверждение об объектах имеющих однозначный, точно определенный смысл. Например, В году 365 дней; 2 ´ 2 = 5; 3 ´ 3 = 9 и т.д. некоторые высказывания являются истинными, некоторые ложными. Выделяют, безусловно истинные высказывания (3 ´ 3 = 9) и безусловно ложные (2 ´ 2 = 5). Высказывания, говорящие о множестве утверждений называются общими. Атомарными элементарными высказываниями считают такие, которые сообщают единичный факт. Сложные образуются из атомарных применением трех операций:

- Логические связки применяются к высказываниям и, в результате, получается новое высказывание. Например, это «A и B»; «не только A, но и B и C»;

- Модальности применяются к высказываниям и изменяют наше отношение к ним. Например, «говорят, что A > B»; «по словам ученых…»;

- Кванторные конструкции применяются к совокупности однородных (отличающихся лишь значениями некоторых параметров) высказываний либо выражений и дают единое высказывание либо выражение, не зависящее от указанных параметров. Например, «Большинство…»; «Все…»; «Для любого…».

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

Определение 1. Единственными логическими значениями являются истина и ложь, обозначаемые (1 или 0, И или Л).

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

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

Для образования высказывания из предметов их соединяют отношением. Например, a = b – двуместное отношение, сопоставляющее двум числам a и b высказывание a = b, в частности 1 = 1 – истинное высказывание, а 1 = 9 – ложное.

В математической логике часто используется запись P(t₁, t₂, …, t_n), чтобы обозначить высказывание, образованное применением n-местного отношения P к предметам t₁, t₂, …, t_n. Символ P, изображающий отношение называется предикатом, а t₁, t₂, …, t_n – термы.

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

Одним из основных понятий алгебры логики является понятие логического высказывания. Под высказыванием в логике понимают любое утверждение, в отношении которого можно сказать, что оно либо истинно, либо ложно. Например, высказывание «два больше одного» - истинно, а высказывание «пять принадлежит множеству отрицательных чисел» - ложно. Высказывания бывают простые, т.е. не зависящие от других высказываний, и составные, т.е. состоящие из двух или более простых высказываний. Составные высказывания образуются из простых с помощью логических операций. Простые высказывания называют еще логическими переменными, а составные - логическими функциями (ЛФ) этих переменных.

Особенность ЛФ в том, что они принимают значения в конечных множествах. Область значений ЛФ - это конечная совокупность чисел, символов, любых объектов. ЛФ могут зависеть от одной, двух и любого числа переменных (аргументов). Аргументы могут принимать значения из элементов как конечных, так и бесконечных множеств.

Логическая функция Y = f (x ₁, x ₂,..., x _n) - это отображение множества наборов (n-мерных векторов, кортежей вида (x ₁,..., x _n)) на множество ее значений N = {l₁,..., ₂}. Если аргументы принимают значения из того же множества что и сама функция, то ее называют однородной.

Объекты с двумя возможными состояниями характеризуются булевыми переменными, которые принимают лишь два различных значения. Отношения между булевыми переменными представляются булевыми функциями y = f (x), но y и x принимают свои значения из двухэлементного множества {0, 1}. Множество всех БФ вместе с операциями отрицания, конъюнкции и дизъюнкции образует Булеву Алгебру (БА). Основные в БА три функции: отрицание, дизъюнкция и конъюнкция. Более сложные формулы получаются замещением входящих в них переменных другими логическими формулами, которые обычно заключаются в скобки, например.

Логическое отрицание (операция НЕ, инверсия) - это операция, результат которой является истинным тогда, когда исходное высказывание ложно, и наоборот.

Обозначается как . Таблица истинности этой операции будет иметь следующий вид:

x
0	1
1	0

Логическое сложение (операция ИЛИ, дизъюнкция) - это операция, которая истинна, когда истинно хотя бы одно из составляющих ее высказываний, и ложна - в случае, если оба высказывания ложны. Обозначается как x Ú y. Данная операция является многоместной. Таблицу истинности этой операции можем записать так:

х	y	x Ú y
0	0	0
1	0	1
0	1	1
1	1	1

Логическое умножение (операция И, конъюнкция) - это операция, которая истинна тогда и только тогда, когда истинны оба составляющих ее высказывания, и ложна во всех остальных случаях. Записывается как: x & y, или x Ù y или x y. Данная операция является многоместной. Таблица истинности этой операции будет выглядеть следующим образом:

x	y	x & y
0	0	0
1	0	0
0	1	0
1	1	1

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

x	y	x ® y
0	0	1
1	0	0
0	1	1
1	1	1

Эквивалентность - это операция, которая истинна в том случае, когда значения составляющих ее высказываний совпадают, и ложна - в противном случае. Обозначается следующим образом: x «y. Таблица истинности будет иметь следующий вид:

x	y	x «y
0	0	1
1	0	0
0	1	0
1	1	1

 

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

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

Связки Ù, Ú, Þ, Û, - называются связками исчисления высказываний или пропорциональными связками.

Принцип бритвы Оккама: «Не умножай сущностей без необходимости».

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

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

Квантор " сочетается со связкой Þ, а квантор $ - со связкой Ù. Например, утверждение «Некоторые хорошие (Х(x)) студенты (С(x)) становятся учеными (У(x))» можно записать в виде

$ x (Х(x) Ù С(x) Ù У(x)).

Например, утверждение: «Все сторожевые (СС(x)) собаки (С(x)) – злые (Зл(x))»:

" x (С(x) Ù СС(x)) Þ Зл(x).

Перевод утверждения «для всякого целого числа есть большее» можно записать:

" x (x Î Z Þ $ y (y Î Z Ù y > x)),

где Z – множество целых чисел.

Основной закон равенства: Если A – произвольная формула языка формальной теории, то

" x, y (x = y Þ (A(x) Þ A(y)))

Другими словами, свойства равных объектов эквивалентны.

Определение Лейбница: Два предмета равны, если они обладают одинаковыми свойствами.

Тождественно истинные формулы в математической логике называются тавтологии. Если формула A – тавтология, то она обозначается |= A.

В математической индукции имеется базис – утверждение, что свойство выполнимо для самого маленького из рассматриваемых чисел, и шаг – обоснование перехода от числа n к числу n + 1. На языке математической логики метод математической индукции запишется

A(0) Ù " n (A(n) Þ A(n + 1)) Þ " n A(n).

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

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Пример 12.1. Определить значение следующего составного высказывания:

x Ù (  Ú  Ú z Ù y ® ) Ú  Ù y

при условии, что х = 1; y = 0; z = 0.

Решение. Поскольку рассматриваемое высказывание состоит из двух частей, соединенных между собой операцией дизъюнкции, то, возможно, окажется достаточно определить значение только одной из составляющих его частей (в случае, если окажется, что эта составляющая истинна). Рассмотрим ту часть, которая содержит меньше переменных. Для этого подставим заданные значения переменных и получим выражение 0 Ù 0.Очевидно, что данное выражение ложно. В таком случае продолжим рассмотрение второй части исходного выражения. Здесь у нас имеет место операция конъюнкции. Поскольку