Математическая логика и теория алгоритмов

Министерство науки и высшего образования Российской Федерации Кубанский государственный технологический университет Кафедра информационных систем и программирования Конспект лекций по дисциплине МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ для студентов очной формы обучения направления 09.03.04 Программная инженерия Краснодар 2019 УДК 510.6 Математическая логика и теория алгоритмов: Конспект лекций / Сост. В.Н. Марков; Кубан. гос. технол. ун-т., Каф. Инф. сист. и прогр. – Краснодар, 2019. – 71 с. Режим доступа: http://moodle.kubstu.ru (по паролю). В конспекте лекций приводятся основные положение и определения тех разделов математической логики и теории алгоритмов, которые представляют интерес для студентов, обучающихся по специальностям, связанным с информатикой и программированием. В лекциях приведены ссылки на литературные источники. Материал носит тезисный и конспективный характер и не составляет полнотекстовые лекции. Основное внимание уделено алгебре логики, как одному из инструментов программирования и разработки цифровой техники; логическому выводу в исчислении предикатов и его автоматизации, как одному из инструментов логического программирования; теории рекурсивных функций и вычислительным моделям Тьюринга и Маркова, как средствам оценки вычислительной сложности алгоритмов. Предназначено для студентов направления 09.03.04 Программная инженерия. Ил. 1. Табл. 25. Библиогр.: 3 назв. Содержание Лекция 1. Основы алгебры Буля…………………………………………….. 4 Лекция 2. Булевы функции………………………………..…………………. 8 Лекция 3. Разложение булевых функций по переменным…………………. 13 Лекция 4. Минимизация булевых функций………………………………… 17 Лекция 5. Полнота и замкнутость булевых функций……………………… 21 Лекция 6. Свойства булевых функций……………………………………… 24 Лекция 7. Алгебра Жегалкина…………………………………………..…… 28 Лекция 8. Формальные системы и дедукция……………………….…....…. 32 Лекция 9. Недедуктивный логический вывод.…………….…………..……. 41 Лекция 10. Исчисление высказываний……..……………………….………. 45 Лекция 11. Логика предикатов………………………………….………..….. 48 Лекция 12. Машина логического вывода……………..……….……………. 51 Лекция 13. Введение в теорию рекурсивных функций…………..…..……. 55 Лекция 14. Частично рекурсивные и общерекурсивные функции…..….… 56 Лекция 15. Машина Тьюринга……………………………………….….…… 57 Лекция 16. Нормальные алгоритмы Маркова………………………………. 59 Лекция 17. Равнодоступная адресная машина……………………………… 61 Лекция 18. Сложность алгоритмов…………………………………….……. 62 Литература……………………………….………………………………….… 70 Раздел 1. Алгебра логики Лекция 1. Основы алгебры Буля 1. Элементарные логические операции. 2. Язык алгебры Буля. 3. Условные графические обозначения логических построение функциональных схем. 4. Обработка булевых данных на языке C#. элементов и 1. Элементарные логические операции Множество B из двух элементов: 0 (или Ложь) и 1 (или Истина) B={0,1}. Переменная, принимающая значение из этого множества называется булевой переменной. Операции B2B и BB над булевскими переменными: бинарные аддитивная и мультипликативная, унарная инверсия. Таблицы истинности элементарных логических операций на множестве B={0,1}: Отрицание :BB x 1 x 1 Дизъюнкция +:B2B или +:B2B x 1 1 y 1 1 xy 1 1 1 Конъюнкция &:B2B или :B2B x 1 1 y 1 1 xy 1 2. Язык алгебры Буля Булевой алгеброй (B,A) называется непустое множество A с двумя бинарными операциями (конъюнкция), (дизъюнкция), одной унарной операцией (отрицание) и носитель B из двух элементов: 0 (или Ложь) и 1 (или Истина) такие, что для всех a, b и c из множества B верны следующие аксиомы: Ассоциативность Коммутативность Законы поглощения Дистрибутивность Дополнительность Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение ¬a любого элемента a однозначно определено. Для всех a и b из B верны также следующие равенства: Идемпотентность Свойства констант Комплементарность, дополнительность Законы де Моргана Инволютивность отрицания Блейка-Порецкого Склеивание / расщепление ̅ Применение закона поглощения: ; ; ̅ ̅ Применение закона Блейка-Порецкого: ̅̅̅ ̅ ; ; ̅̅̅ ̅̅̅ ̅ ; ̅; 3. Условные графические обозначения логических элементов и построение функциональных схем Краткое обозначение элементов: 2И, 2ИЛИ, НЕ. Операция «исключающее ИЛИ» по современным нормам называется «ИЛИ, исключающее И». Другое название «сумма по модулю 2». Построение функциональной схемы (ФС) Пример. Пусть дано логическое выражение ̅ . Построим ФС устройства, вычисляющую значение этого логического выражения, на элементах 2И, 2ИЛИ, НЕ: x y z t 1 𝑦̅ & 𝑥𝑦̅ & 𝑥𝑦̅𝑧 1 𝑥𝑦̅𝑧 + 𝑡 4. Обработка булевых данных на языке C# Логические операции языка C#: bool x = true; bool y = !x; // инверсия, отрицание bool z1 = x & y; // И, конъюнкция bool z2 = !(x & y); // И-НЕ bool z3 = x | y; // ИЛИ, дизъюнкция bool z4 = !(x | y); // ИЛИ-НЕ bool z5 = x ^ y; // искл.ИЛИ, сумма по модулю 2 Console.WriteLine($"{y} {z1} {z2} {z3} {z4} {z5}"); Ввод/вывод булевых данных: string x = Console.ReadLine(); // true bool x1 = Convert.ToBoolean(x); bool y1 = Convert.ToBoolean(Console.ReadLine()); // одной строкой Console.WriteLine("x1=" + x1 + " y1=" + y1 + "\nx1 & y1 = " + (x1 & y1)); Console.WriteLine($"x1={x1} y1={y1} \nx1 & y1 = {x1 & y1}"); Console.ReadLine(); ЛР 1. Равносильные преобразования логических выражений и построение функциональных схем Пример. Дано логическое выражение ̅̅̅̅̅ ̅ .̅ Необходимо упростить это выражение, построить ФС на элементах 2И, 2ИЛИ, НЕ, вычисляющую значение упрощённого выражения, и написать программу на языке C# для расчёта значения упрощённого выражения. Решение. Упростим: ̅̅̅̅̅ ( ) ̅ ̅ ̅ ( ̅ ̅) ̅ ̅ ̅ ̅ Построим ФС: x y z & 𝑥𝑦 1 𝑧̅ 1 𝑥𝑦 𝑧̅ Программа на языке C# для расчёта значения упрощённого выражения: bool x = Convert.ToBoolean(Console.ReadLine()); bool y = Convert.ToBoolean(Console.ReadLine()); bool z = Convert.ToBoolean(Console.ReadLine()); bool p = x&y | !z; Console.WriteLine("p=" + p); // true // false // true Задача. 1. Упростить до минимального количества бинарных операций, если это возможно, построить таблицу истинности выражения, изобразить ФС на элементах 2И, 2ИЛИ, НЕ, вычисляющую значение упрощённого выражения, и написать программу на языке C# для расчёта значения упрощённого выражения по введённым с консоли данным. ̅̅̅ ̅̅̅ а) ̅ ̅ в) ̅ б) (̅̅̅̅̅̅̅̅̅̅̅ ̅ )̅ г) ̅̅̅̅̅̅̅̅ ̅ ̅ Лекция 2. Булевы функции 1. Понятие булевой функции. 2. Способы задания булевых функций. 3. Примеры булевых функций. 1. Понятие булевой функции Булева функция от n переменных – отображение Bn → B, где B = {0,1} булево множество. Элементы 1 и 0 булева множества обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определённого смысла. Неотрицательное целое число n называют арностью или местностью функции. В случае n = 0 булева функция превращается в булеву константу. Элементы декартова произведения Bn называют булевыми векторами. Булевы функции названы так по фамилии математика Джорджа Буля. Каждая булева функция арности n полностью определяется заданием значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2n. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество n всех n-арных булевых функций равно 22 . 2. Способы задания булевой функции. Логическая функция может быть задана тремя способами: 1. Математическим выражением (формулой). 2. Таблицей истинности. 3. Единичными или нулевыми наборами. Таблица является наиболее общим и универсальным способом задания функции. Таблицы носят название таблиц истинности и в левой части содержат все комбинации значений двоичных переменных, а в правой – значения функции для каждой комбинации: … ( ) … f(0,0,…,0) … 1 f(0,0,…,1) 1 … f(1,1,…,0) 1 … 1 f(1,1,…,1) Наборы, на которых функция равна единице, называют единичными наборами, а наборы, на которых функция равна нулю – нулевыми. Пример представления булевой функции тремя способами: 1) Таблица истинности: № 1 2 3 2) ( 3) ( ) ) ̅̅̅̅̅̅̅̅̅ ( ) x 1 1 y 1 1 f(x,y) 1 – формула; – единичный набор (множество номеров строк, в которых значение функции равно 1); – нулевой набор (множество номеров строк, в которых значение функции равно 0). 3. Примеры булевых функций Практически все булевы функции малых арностей (0, 1, 2 и 3) имеют исторически сложившиеся названия. Если функция при любых значениях переменных принимает значение 0, то такую функцию называют нулевой или константой нуля, или тождественно ложной функцией. Если функция при любых значениях переменных принимает значение 1, то такую функцию называют единичной или константой единицы, или тождественно истинной функцией. Две булевы функции ( ) и ( ) называют равными, если на всех возможных наборов значений аргументов функции принимают одинаковые значения и, таким образом, имеют одинаковую таблицу истинности. Если функция определена не на всех комбинациях аргументов, то она называется частично определённой. Неопределённые значения функции обозначаются в таблице истинности тильдами, например: № 1 2 3 x 1 1 y 1 1 f(x,y) 1 ~ ~ Если значение функции не зависит от одной из переменных, то эта переменная называется фиктивной и её можно исключить. Например, ( ) функция ̅ имеет фиктивную переменную y. Исключение фиктивной переменной уменьшит арность функции: ( ) ̅. Нульарные функции При n = 0 количество булевых функций сводится к двум , первая из них тождественно равна 0, а вторая 1. Их называют булевыми константами – тождественный нуль и тождественная единица. Унарные функции При n = 1 число булевых функций равно этих функций содержится в следующей таблице. . Определение x 0 ̅ x 1 0 0 1 0 1 1 0 0 1 1 Названия булевых функций от одной переменной: Обозначение ̅ x 1 Название тождественный ноль, тождественная ложь, тождественное "НЕТ" отрицание, логическое "НЕТ", "НЕ" тождественная функция, логическое "ДА" тождественная единица, тождественная истина, тождественное "ДА", тавтология Бинарные функции При n = 2 число булевых функций равно x y x↓y xy ̅̅̅̅̅̅̅̅ ̅ 1 1 1 1 1 1 1 1 1 1 1 xy x|y xy 1 1 1 1 1 x&y 1 . x=y y x≡y 1 1 1 1 xy 1 1 1 x 1 1 xy 1 1 1 xy 1 1 1 1 1 1 1 1 Названия булевых функций от двух переменных: Обозначение x ↓ y, x ИЛИ-НЕ y, ИЛИ-НЕ(x,y), x NOR y, NOR(x,y) x < y, x LT y, LT(x,y) x, НЕ1(x,y), NOT1(x,y), ̅ x > y, x GT y, GT(x,y) y, НЕ2(x,y), NOT2(x,y), ̅ x ⊕ y, x +2 y, x ≠ y, x XOR y, XOR(x,y) x | y, x NAND y, NAND(x,y), x И-НЕ y, И-НЕ(x,y) Название Тождественный ноль, тождественная ложь, тождественное "НЕТ" НЕ- 2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Даггера, функция Вебба, стрелка Пирса Меньше, инверсия обратной импликации Отрицание (негация, инверсия) первого операнда Больше, инверсия прямой импликации Отрицание (негация, инверсия) второго операнда Сложение по модулю 2; не равно; ИЛИ, исключающее И НЕ-2И, 2И-НЕ, антиконъюнкция, штрих еффера x & y, x · y, xy, x ∧ y, x AND y, 2И, конъюнкция AND(x,y), x И y, И(x,y), min(x,y) x ≡ y, x = y, x EQV y, EQV(x,y), Равенство, эквивалентность x ~ y, x ↔ y y, ДА2(x,y), YES2(x,y) Второй операнд Меньше или равно, прямая (материальная) x → y, x ≤ y, x ⊃ y, x LE y, импликация (от первого аргумента ко LE(x,y) второму) x, ДА1(x,y), YES1(x,y) Первый операнд Больше или равно, обратная импликация (от x ≥ y, x ⊂ y, x GE y, GE(x,y) второго аргумента к первому) x  y, x + y, x ИЛИ y, ИЛИ(x,y), 2ИЛИ, дизъюнкция x OR y, OR(x,y), max(x,y) Тождественная единица, тождественная 1 истина, тождественное "ДА", тавтология Тернарные функции При n = 3 число булевых функций равно них определены в следующей таблице: x 1 1 1 1 y 1 1 1 1 . Некоторые из z x↓y↓z ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ( ) x≠y≠z x|y|z min(x,y,z) x=y=z xyz ≥2(x,y,z) f1 0 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 f2 max(x,y,z) 1 1 1 1 1 1 1 1 1 1 1 Названия булевых функций трёх переменных: Обозначения x↓y↓z = ↓(x,y,z) = Webb2(x,y,z) (>=2(x,y,z)) Названия 3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией Неравенство 3-И-НЕ, штрих еффера x≠y≠z = [≠(x,y,z)] = NE(x,y,z,v) x|y|z = |(x,y,z) x&y&z = &(x,y,z) = (x AND y AND z) = AND(x,y,z) = (x И y И z) = 3-И, минимум И(x,y,z) = min(x,y,z) (x=y=z) = [=(x,y,z)] = EQV(x,y,z,v) Равенство x2y2z = x+2y+2z = (x,y,z) >=2(x,y,z)] = (x И y) ИЛИ (y И z) ИЛИ (z И x) f1 f2 (x+y+z) = +(x,y,z) = max(x,y,z) = (x OR y OR z) = OR(x,y,z) = (x ИЛИ y ИЛИ z) = ИЛИ(x,y,z) Тернарное сложение по модулю 2 Переключатель по большинству, 3-ППБ, мажоритарный клапан Разряд займа при тернарном вычитании Разряд переноса при тернарном сложении 3-ИЛИ, максимум Лекция 3. Разложение булевых функций по переменным 1. Дизъюнктивная и конъюнктивная нормальные формы. 2. Совершенная дизъюнктивная нормальная форма. 3. Совершенная конъюнктивная нормальная форма. 1. Дизъюнктивная и конъюнктивная нормальные формы Любая функция булевой алгебры может быть представлена в нормальных формах. Нормальные формы – стандартное представление функции с помощью элементарных конъюнкций или элементарных дизъюнкций. Элементарная дизъюнкция (ЭД, дизъюнкт) – дизъюнкция нескольких переменных или их отрицаний, например ̅ Элементарная конъюнкция (ЭК, конъюнкт) – конъюнкция нескольких переменных или их отрицаний, например ̅. Дизъюнктивная нормальная форма (ДНФ) функции – дизъюнкция ЭК, например ̅ ̅. Конъюнктивная нормальная форма (КНФ) функции – конъюнкция ЭД, например ( ̅ )( ̅ ̅). Приведение исходной формулы к нормальной форме: 1 .Все функции выразить через дизъюнкцию, конъюнкцию и отрицание. 2. Все отрицания над формулами опустить на переменные с помощью закона де Моргана. 3. С помощью тождеств булевой алгебры привести формулу к ДНФ или КНФ. Пример: ̅̅̅ ̅ ( ̅) ⏟( ̅ )( ̅) ( ̅)( ̅) ⏟ ̅ ̅ ̅ ̅ Нормальную форму функции можно существенно упростить по правилам: - дизъюнкция ЭК и её отрицания: - конъюнкция ЭД и её отрицания: ̅ ̅ 2 Совершенная ДНФ (СДНФ) Совершенная форма – разложение булевой функции по всем переменным. Правильная элементарная конъюнкция – ЭК, в которую каждая переменная входит не более одного раза, включая и вхождение под знаком отрицания. Правильная ЭК является полной относительно вектора переменных ( ), если каждая из этих переменных входит в него один раз. Условия совершенства ДНФ функции n переменных: 1. Все конъюнкты в ДНФ различны. 2. Каждый конъюнкт правилен и полон. СДНФ составляется для единичных значений логической функции, когда она задана таблично. Если функция задана формулой, то для получения СДНФ выполняем алгоритм: 1. Преобразуем формулу в ДНФ. 2. Если в каком-то конъюнкте S нет переменной x, то заменяем конъюнкт S выражением ( ̅) ̅ 3. Если в ДНФ два одинаковых слагаемых, то одно отбрасываем 4. Если в конъюнкте ДНФ переменная x входит дважды, то одну переменную можно убрать 5. Если в конъюнкте ДНФ содержится конъюнкция конъюнкт можно исключить. ̅ , то весь 3. Совершенная КНФ (СКНФ) Правильная элементарная дизъюнкция – ЭД, в которую каждая переменная входит не более одного раза, включая и вхождение под знаком отрицания. Правильная ЭД является полной относительно вектора переменных ( ), если каждая из этих переменных входит в него один раз. Условия совершенства КНФ функции n переменных: 1. Все дизъюнкты в КНФ различны. 2. Каждый дизъюнкт правилен и полон. СКНФ составляется для нулевых значений логической функции и инверсных значений аргументов, когда она задана таблично. Если функция задана формулой, то для получения СКНФ выполняем алгоритм: 1. Преобразуем формулу в КНФ. 2. Если в каком-то дизъюнкте S нет переменной x, то заменяем дизъюнкт S выражением ( ̅) ( )( ̅) 3. Если в КНФ два одинаковых сомножителя S, то один отбрасываем 4. Если в дизъюнкте КНФ переменная x входит дважды, то одну переменную можно убрать 5. Если в дизъюнкте КНФ содержится пара можно исключить. ̅ , то весь дизъюнкт 4. Получение СДНФ и СКНФ по таблице истинности Пример 1:Таблица истинности двух функций: x 1 1 СДНФ: ( ) СКНФ: ( ) СДНФ: ( ) СКНФ: ( ) ̅̅ ̅ ̅ y 1 1 f(x,y) g(x,y) 1 1 1 1 ; ; ̅ ̅; ( ̅)( ̅ )( ̅ ̅); Пример 2: Таблица истинности: x 1 1 1 1 СДНФ: СКНФ: ( ( ) ) ̅ ( ̅ ̅ ̅ )( y 1 1 1 1 z 1 1 1 1 f(x,y,z) 1 1 1 1 ̅ ̅) ( ̅ ̅) ( ̅ ̅) ЛР 2. Построение нормальных форм логических функций 1. Построить ДНФ или КНФ бинарных функций по таблице истинности. Выбор ДНФ или КНФ сделать самостоятельно по критерию минимального количества операций. x 1 1 y 1 1 x↓y 1 ̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅ 1 1 xy 1 1 x|y 1 1 1 x≡y 1 1 1 1 1 1 1 1 2. Выразить и упростить функции по заданным нулевым и единичным наборам. Выбор формы представления (ДНФ или КНФ) сделать самостоятельно по критерию минимального количества операций. ) а) ( б) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ( ) 3. Используя решение задачи 1 построить и упростить ДНФ логических выражений: ( ) ⊕ ( ) ̅̅̅̅̅̅̅ а) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅̅̅̅ ( ) ( ̅ ⊕ ̅) б) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ Лекция 4. Минимизация булевых функций 1. Метод неопределённых коэффициентов. 2. Карты Карно. 3. Минимизация частично определённых булевых функций. 1. Метод неопределённых коэффициентов Минимизация функции – построение такой ДНФ (КНФ) заданной функции, которая имеет наименьшее число операций и переменных в формуле. Это актуально для построения технических устройств, так как ведёт к уменьшению массогабаритных характеристик и продлению срока службы батарей. Методы минимизации: - метод неопределённых коэффициентов. - метод Квайна – Мак Класки. - метод карт Карно. Представление функции в неопределёнными коэффициентами: ( ) ̅ ⏟ самом ̅ общем виде ̅ ⏟ ̅ в ДНФ с ̅̅ Слагаемые, содержащие k переменных, называются слагаемыми ранга k. x 1 1 ( ( ( ( ( y 1 1 ) ) ) ) ) Сумма коэффициентов ( ) ( ) ( ) ( ) Для нулевых значений конкретной функции вычёркиваются коэффициенты, т.к. они приравниваются к нулю. В оставшихся строках таблицы приравнивается единице тот коэффициент, который входит в слагаемое наименьшего ранга. Пример. x 1 1 y 1 1 ( ( ( { ( ( ) 1 1 1 ) ) ) ) Сумма коэффициентов ( ) ( ) ( ) ( ) { ( { ( ) ) ( ) { ( ) ̅ Функция трёх переменных имеет уже 26 коэффициентов. Метод Квайна – Мак Класки – на самостоятельную работу! 2. Метод карт Карно Карта Карно – графическое представление таблицы истинности логической функции. Число в ячейке карты – это значение функции на соответствующем наборе. Строка таблицы истинности с единичным значением соответствует единичной ячейке. Контур – прямоугольник единичных ячеек, имеющий количество клеток, равное степени двойки. Принципы минимизации: 1) Все единичные ячейки объединяются в минимальное число максимальных контуров. 2) Контур выражается в виде конъюнкции тех переменных, которые не меняют своё значение в пределах контура. 3) Функция записывается в виде дизъюнкции контуров (ДНФ). Для КНФ описываем нулевые контуры как произведение сумм, но инвертируем значения переменных. Пример для ДНФ. 1. Таблица истинности. 2. Карта Карно. № x y z w f(x,y,z,w) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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 f0=1 f1=1 f2=0 f3=0 f4=1 f5=1 f6=1 f7=0 f8=0 f9=0 f10=0 f11=0 f12=0 f13=0 f14=0 f15=1 x=0 x=0 x=1 x=1 y=0 y=1 y=1 y=0 z=0 w=0 f0 f4 f12 f8 z=0 w=1 f1 f5 f13 f9 z=1 w=1 f3 f7 f15 f11 z=1 w=0 f2 f6 f14 f10 3. Контуры единичных значений / контуры нулевых значений. | | | | x — — — 1 1 1 1 — z w 1 1 y Контур 1: 4 зелёные единицы в левом верхнем углу ̅ ̅. Контур 2: Жёлтый фон ̅ ̅ Контур 3: Одинокая единица на бирюзовом фоне 4. Построение ДНФ / КНФ. ( ) ̅ ̅ ̅ ̅ 3. Минимизация частично определённых булевых функций Частично определённые функции определены не на всех наборах переменных и поэтому принимают на некоторых наборах произвольное/безразличное значение, которое обозначается тильдой ~. В ходе минимизации тильду можно заменить нулём или единицей так, как выгодно при выделении контуров для минимизации их количества и максимизации их площади. Пример для ДНФ. В карте присутствуют три тильды. Две из них будем полагать единицами, а тильду в правом нижнем углу положим равной нулю. | | | | x — 1 1 1 1 — — — ~ 1 ~ 1 z w ~ y Контур 1: 4 зелёные единицы в левом верхнем углу ̅ ̅. Контур 2: Строка с жёлтым фоном ̅ Контур 3: Единица с тильдой на бирюзовом фоне Построение ДНФ ( ) ̅ ̅ ̅ ЛР 3. Минимизация логических функций 1. Минимизировать логические функции, заданные нулевым или единичным наборам. Использовать карты Карно. а) ( б) ( ) ) в) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ( ) г) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ ( ) 2. Минимизировать частично определённые логические функции. Использовать карты Карно. x 1 1 1 1 1 1 1 1 y 1 1 1 1 1 1 1 1 z 1 1 1 1 1 1 1 1 w 1 1 1 1 1 1 1 1 f1(x,y,z,w) ~ ~ 1 1 1 1 1 ~ 1 ~ ~ f2(x,y,z,w) ~ ~ 1 1 ~ 1 ~ 1 1 1 f3(x,y,z,w) 1 1 ~ ~ 1 1 1 ~ ~ 1 ~ f4(x,y,z,w) 1 1 ~ 1 ~ 1 ~ ~ 1 1 ~ ~ Лекция 5. Полнота и замкнутость логических функций 1. Двойственные функции. 2. Понятие функционально полной системы 3. Замыкание и замкнутые классы 1. Двойственные функции Логическая функция ( ) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ (̅̅̅ ̅̅̅ ̅̅̅) называется двойственной по отношению к функции ( ). ) Принцип двойственности: если ( ( ), то ( ) ( ) Функция ( ) является самодвойственной, если ( ) ( ). ) Всегда ( ( ). Всегда ̅( ) (̅̅̅ ̅̅̅ ̅̅̅). Если ( ) ( ), то ( ) ( ). ̅̅̅̅̅̅̅ ) Пример. Функция, двойственная дизъюнкции ( ̅ ̅ ∧ . Следовательно, функция, двойственная конъюнкции – это дизъюнкция ( ∧ ) 2. Понятие функционально полной системы Система логических функций называется функционально полной, если любая логическая функция может быть записана в виде формулы через функции этой системы. Для двух систем функций и , относительно которых известно, что F – полная система и каждая её функция может быть выражена в виде формулы через функции системы H, можно сделать вывод, что H – также функционально полная система. Примеры функционально полных систем (ФПС): {,,} – ФПС И-ИЛИ-НЕ, так как любая функция представляется в виде ДНФ или КНФ. {,} – минимальная ФПС И-НЕ, так как ИЛИ выражается через И-НЕ по закону де-Моргана. {,} – минимальная ФПС ИЛИ-НЕ, так как И выражается через ИЛИНЕ по закону де-Моргана. 3. Замыкание и замкнутые классы Замыканием множества функций М называют множество всех логических функций [М], представляемых в виде формул через функции множества М. Очевидно М  [М]. Для М = {}, [М] = {,}. Для М = {,}, [М] – всё множество логических функций. Множество М называют замкнутым классом, если при замыкании М не происходит его дальнейшее расширение, т.е. М = [М]. Множество логических функций называется полной системой, если замыкание этого множества совпадает с множеством всех логических функций. Предполный класс – замкнутый класс логических функций, обладающий следующим свойством – замыкание объединения этого класса с любой логической функцией, не принадлежащей ему, порождает полное множество логических функций. Существует пять предполных классов:    Класс T0 функций, сохраняющих константу 0: ( ) ( ) Пример: ( )  . Класс T1 функций, сохраняющих константу 1: ( ) ( ) Пример: ( )  . Класс L линейных функций: ) ( ) { ( ⊕ ⊕ ⊕ ) Пример: ( ⊕ ⊕ . } Класс S самодвойственных функций: ) (̅̅̅ ( )} { ( ̅̅̅) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ Пример: ( ) ̅.  Класс M монотонных функций: ( ) ( ) ( ) ( ) ) Пример: ( . Критерий Поста: система логических функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов T0, T1, S, M, L. Полная система логических функций называется базисом, если при удалении из неё хотя бы одной функции теряется её полнота. Состав систем, которые относятся к базису можно определить по таблице  № 1 2 3 4 5 6 7 8 9 Функция xy xy xy x y x xy x|y xy 1 T0 + + + - T1 + + + + + L + + + + S + - M + + + Символ “+” обозначает факт принадлежности функции замкнутому классу. К базису можно отнести минимальный набор функций, строки которого будут содержать хотя бы один символ “-” в каждом столбце. Базисами являются {,}, {,}, {|}, {}, {,}, {,,1}. Перечисленные базисы составляют множество операций различных алгебр логики. Например, алгеброй логики является множество операций {,,1} над булевым носителем {0,1}. Указанная алгебра ещё называется алгеброй Жегалкина. ЛР 4. Построение алгебр логики 1. Найти двойственные функции всех логических функций. 2. Описать выражения алгебры логики в нижеуказанной ФПС: а) {,} x0 = ? xx = ? x1 = ? xy = ? x&y = ? 0x = ? ̅ ? 1x = ? б) {} x0 = ? xx = ? x1 = ? xy = ? x&y = ? 0x = ? ̅ ? 1x = ? Лекция 6. Свойства булевых функций 1. Проблема разрешимости булевых функций. 2. Производные от логических функций. 3. Арифметическое представление логических функций. 1. Проблема разрешимости булевых функций Три класса эквивалентности формул булевой алгебры: 1. Тавтологии. 2. Тождественно ложные. 3. Выполнимые. Формула выполнима, если она принимает значение 1 хотя бы на одном наборе входящих в неё переменных, и не является тождественно истинной. Проблема разрешимости – соотнесение некоторой формулы к тому или иному классу. Если существует таблица истинности формулы, то проблема разрешимости решается элементарно. Если таблицы истинности нет, то формула приводится к ДНФ или КНФ, по которым легко определяется тождественная истинность или ложность формулы по простому алгоритму. Алгоритм таков. Сначала рассматривается формула А. Если А 1, то задача решена. Если А 1 не доказано, то рассматривается формула А. Если А 1, то А 0 и задача решена. Если формула не является ни тавтологией, ни тождественно ложной, то делается вывод, что она выполнима. Вспомогательные инструменты. 1. Если ДНФ содержит сумму ЭК + ̅, то эта ДНФ тождественно истинна. ̅, то эта КНФ тождественно 2. Если КНФ содержит конъюнкцию ЭД ложна. Примеры: 1. ( ) ̅ ̅⏟ ̅ ̅ (тавтология) 2. ( ) ⏟( ̅ 3. ( ) ̅ ⏟ ̅̅̅̅̅̅̅̅̅̅̅̅ ( ) ( ̅ ̅) ( ̅ ̅ )( ̅ ̅) ̅ ̅) ( )( ̅ ̅⏟ (̅ ̅ ̅) (тождественно ложная) ̅) ̅ (функция выполнима) ̅ (функция выполнима). 2. Производные от логических функций В математической логике отсутствует понятие предела, так как переменная принимает всего два значения 0 и 1. Поэтому термин производная в математической логике связан с разложением булевой функции в ряд, аналогичный ряду Маклорена в точке ( ) или ряду Тейлора в произвольной точке. Производная первого порядка от булевой функции ( ) по переменной называется сумма по модулю 2 нулевой и единичной остаточных функций ( где ( ) ( ), ) – нулевая остаточная ) – единичная остаточная функция. Производная первого порядка от константы ( ( функция, ) по переменной равна нулю, так как нулевая и единичная функции равны Const независимо от значений аргумента . ( ) ( ) определяет условия Производная первого порядка ( ) , при которых функция ) изменяет значение при ( ( переключении переменной y. При ) тестирование на основе переключений невозможно. В этом случае проводят тестирование по таблице истинности. Свойство производной: ( Смешанной )  . производной от булевой функции ) называется выражение вида ( ( ). Порядок фиксации переменных не существенен. Производная k-го порядка от булевой функции ( ) называется выражение, равное сумме по модулю 2 всех производных первого порядка и смешанных производных второго, третьего, …, k-го порядков: ( ) ∑ ∑ ∑ , где суммирование под знаками суммы производится также по модулю два. Производная k-го порядка определяет условия, при которых функция ( ) изменяет значение при одновременном изменении значений переменных . Пример 1. Пусть ( ) . Первая производная по x ( ) ( )  ̅. Условие изменения значения функции ̅ . Следовательно, функция ( ) при переключении x изменит своё значение тогда, когда . Первая производная по y ) ( (  ) ̅. Условие изменения значения функции . Следовательно, ̅ функция ( ) при переключении y изменит своё значение тогда, когда . Смешанная производная ( ) ̅  . Производная 2-го порядка ( ) Условие   ̅ ̅  изменения ̅̅̅̅̅̅ ̅ ̅ значения переключении аргументов ( ̅) функции ( ) ( ̅ при ( ). одновременном . Следовательно, функция ) ( ) + изменит своё значение тогда, когда переменные x и y равны друг другу, то есть , либо , . Пример 2. ( )  . Первые производные (  ) (  ) ̅ , (  ) (  )  ̅ . Следовательно, при переключении переменной x функция f(x,y) изменит своё значение независимо от значения переменной y. И наоборот. Смешанная производная ( )  . Производная 2-го порядка ( Условие  ) изменения переключении аргументов  значения ( )   функции . при одновременном . Следовательно, функция ( ) никогда не изменит своё значение при одновременном переключении x и y. Поэтому тестирование надо проводить по одной переменной или по таблице истинности. Аналог ряда Мак Лорена. Любая булева функция ( ) представима суммой по модулю 2 значений функции и всех её смешанных производных в точке ( ) в виде ( ) ( ) ∑ ∧ | ∑ ( ∧ | | ∧ ) ( ) . ( ) Суммирование под знаками суммы производится также по модулю 2. Пример 3. Пусть ( ) + . Ряд Мак Лорена ( ( ) ̅ ) ( Пример 4. Пусть ( ( ) ( ̅ )(   )( ) .  . Ряд Мак Лорена ) )( ( ) ) (   ( )  . ) Аналог ряда Тейлора. Любая булева функция ( ) представима суммой по модулю два значений функции и всех её производных в точке ( ) в виде ( ) ( ) ∑( )∧ | ( ∑ ( )( | )∧ ( ( )∧ ) ) | ( . ) 3. Арифметическое представление логических функций Логические функции могут быть представлены посредством арифметических операций сложения, вычитания, умножения над булевыми переменными, интерпретируемыми числами из множества {0,1}. Примеры для инверсии и конъюнкции: ̅ Кроме этого, конъюнкцию можно представить значением условного выражения + , а также функцией минимума ( ). ЛР 5. Исследование свойств логических функций 1. Доказать или опровергнуть выполнимость логических функций: а) ̅̅̅ ̅ ) ̅ ̅ б) ( ) ̅̅̅ ̅ в) ( г) ̅ ̅̅ ̅ д) (̅̅̅̅̅̅̅ ̅ ) (̅̅̅̅̅̅̅ ̅ ̅) ̅ ̅̅̅ ) е) (̅̅̅̅̅̅̅̅ )(̅̅̅̅̅̅̅̅̅̅ 2. Найти производную 2-го порядка функций |, , , . Определить условия, при которых каждая функция изменяет значение при переключении каждого аргумента и всех сразу. 3. Найти арифметическое представление булевых функций +, , , , |, . Лекция 7. Алгебра Жегалкина 1. Определение алгебры Жегалкина. 2. Построение двухразрядного полусумматора в алгебре Жегалкина. 1. Определение алгебры Жегалкина Алгебра Жегалкина задаётся парой (   ), где B – булевый носитель. В алгебре Жегалкина выполняются следующие соотношения:   ; (  )  ;  ;  ̅ ;  ;  ̅; ̅ ̅ ; (  ) . {1,,} – функционально полная система, поэтому остальные логические операции можно выразить базовыми: ̅  ; ̅̅̅̅̅̅̅ ̅̅̅̅̅̅ (  ) (  ) (  ) (  ) ̅ ̅ ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅         ;   ;   ; ̅̅̅̅̅̅̅̅  ; ̅̅̅̅̅̅̅̅  ; 2. Построение двухразрядного полусумматора в алгебре Жегалкина Полусумматор – устройство сложения двух чисел и выставляющее на выходе разряды суммы и выходной перенос. Полусумматор отличается от полного сумматора тем, что не имеет входного переноса. Булева сумма трёх переменных: ̅̅̅̅̅̅̅̅̅̅̅ ̅̅̅̅̅̅̅̅̅ (  ) (  ) (  ) ̅ ̅ ̅ ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅ (  ) (  ) (  )               Построим арифметический полусумматор для двухразрядных двоичных чисел и . Арифметическая сумма и выходной перенос рассчитываются так 𝑐 𝑐 𝑎 𝑎 + 𝑏 𝑏 𝑐 𝑠 𝑠 Таблица истинности для разряда a0 1 1 и переноса b0 1 1 s0 1 1 : c1 1 Выразим функции младшего разряда суммы и переноса :  ; ; Таблица истинности для старшего разряда суммы и переноса c1 1 1 1 1 a1 1 1 1 1 b1 1 1 1 1 s1 1 1 1 1 c2 1 1 1 1 Выразим функции старшего разряда суммы ̅ ̅ ̅̅̅ ̅ ̅̅̅ ̅ ̅ (̅̅̅ ̅(  ) ̅ ( и переноса : ̅) (̅̅̅ ̅ ̅(  ) (̅̅̅̅̅̅̅̅  ) ) ̅ ̅̅̅ ̅ (̅̅̅ ( ) ̅ (̅ ̅ (̅ ) )) ⏟ ⏟   ) (̅̅̅ ̅ ) ̅ ( ⏟ )   ̅ (̅̅̅ ) ⏟ Делаем замену переменных: ; ; формулу для булевой суммы трёх переменных   : ⏟ : ⏟ ⏟ ⏟ ⏟ и применяем  ⏟ ⏟⏟  (  ) Функциональная схема двухразрядного полусумматора HS и его обозначение представлена на рис. 1. Полусумматор отличается от полного сумматора (рис. 2) отсутствием входного переноса p1. Обратите внимание, полусумматоры и сумматоры имеют минимальные схемы только в алгебре Жегалкина. В алгебре Буля эти схемы будут иметь больше логических элементов. b1 b0 a1 a0 s0 =1 & c1 s1 =1 & =1 a0 a1 b0 b1 c2 =1 HS s0 s1 c2 & б) а) Рис. 1. Функциональная схема двухразрядного полусумматора а) и его обозначение б) c0 a0 a1 b0 b1 S s0 s1 c2 Рис. 2. Обозначение двухразрядного полного сумматора Одноразрядные полные сумматоры (рис. 3) построения n-разрядных полных сумматоров (рис. 4). используются bi a i c i si+1 =1 & =1 =1 ci+1 ci ai bi S si+1 ci+1 & а) б) Рис. 3. Функциональная схема одноразрядного полного сумматора а) и его обозначение б) для c0 a0 b0 a1 b1 an-1 bn-1 S0 s1 c1 S1 s2 Сквозные переносы c2 Sn-1 c0 a0 ⁝ an-1 b0 ⁝ bn-1 S ⁝ ⁝ ⁝ б) sn-1 cn-1 c0 а) s0 ⁝ sn-1 cn-1 n-разрядные шины A B n n S n S cn-1 в) Рис. 4. n-разрядный полный сумматор а) его развёрнутое обозначение б) и краткое обозначение в) Функциональная схема (рис. 4–а) самая простая, но самая медленная. Самая быстрая схема – с параллельным переносом, будет рассмотрена при изучении дисциплины «Теоретические основы информатики». ЛР 6. Построение арифметического сумматора в алгебре Жегалкина 1. Построить функциональную схему двухразрядного полного сумматора в алгебре Жегалкина. Разработать его программную модель на языке C#. На вход полного сумматора подаются разряды слагаемых a1, a0, b1, b0, и входной перенос c0. На экран вывести разряды суммы s1, s0 и выходной перенос c2. Раздел 2. Логический вывод Лекция 8. Формальные системы и дедукция 1. Формальные системы. 2. Дедукция. 3. Силлогистика. 1. Формальные системы Формальная система (ФС) – совокупность абстрактных объектов, не связанных с внешним миром, в которой представлены правила оперирования множеством символов только в синтаксической трактовке не имеющих смыслового содержания. Формальная (аксиоматическая) система задаётся четвёркой: 1. Алфавит в виде конечного множества символов. 2. Правила построения формул ФС. 3. Множество аксиом, т.е. формул, не требующих доказательства истинности. 4. Конечное множество правил вывода, которые позволяют получать новые формулы из известных формул. В общем случае A1&A2&…&AnB. Правила вывода позволяют получать новые истинные формулы из аксиом и ранее выведенных формул:  Используя правила вывода можно строить цепочки и деревья вывода, получая при этом множество истинных формул F1…Fm: Цифра над стрелками указывает номер правила вывода. Аксиома – формула, истинность которой в данной ФС принимается без доказательства. Независимая аксиома – аксиома, которая не может быть выведена из других аксиом. Теорема – формула, истинность которой доказана. Доказательство – способ сведения формулы к аксиомам с помощью правил вывода (прямое доказательство): F выводится из F выводится из ̅̅̅ – истинность теоремы доказана – истинность теоремы опровергнута Если прямое доказательство невозможно, то можно попытаться доказать отрицание теоремы, т.е. применить доказательство от противного: ̅ выводится из – истинность теоремы опровергнута ̅ выводится из ̅̅̅ – истинность теоремы доказана Гипотеза – формула, истинность которой пока не доказана и не опровергнута. Теория – множество теорем. Исчисление – ФС, содержащая способы перечисления истинных формул ФС. Интерпретация – распространение исходных положений какой-либо формальной системы на реальный мир. Интерпретация придаёт смысл каждому символу ФС и устанавливает взаимно однозначное соответствие между символами ФС и реальными объектами. Паралогизм – случайная, непреднамеренная ошибка в доказательстве, приводящая к ошибочному выводу. Софизм – намеренно ложное доказательство, приводящее к ошибочному выводу. Парадокс – утверждение о некоторой реальной ситуации, которое не имеет логического объяснения. Апория – логически верное утверждение о некоторой вымышленной ситуации, которая не может существовать в реальности. Антиномия – логически противоречивые утверждения об истинности некоторой формулы, которые в рамках данной ФС одинаково верные. Проблемы создания ФС: 1. Проблема противоречивости. ФС называется непротиворечивой, если в ней недоказуемы никакие две формулы, из которых одна является отрицанием другой. 2. Проблема полноты. ФС считается полной, если любая формула этой ФС может быть либо доказана, либо опровергнута правилами вывода этой ФС. 3. Проблема независимости аксиом. Все аксиомы ФС должны быть независимы. 4. Проблема разрешимости. ФС разрешима, если существует алгоритм, позволяющий для каждой формулы доказать её истинность или ложность. Теоремы Гёделя о неполноте: 1. Первая теорема утверждает, что если формальная арифметика непротиворечива, то в ней существует невыводимая и неопровержимая формула. 2. Вторая теорема утверждает, что если формальная арифметика непротиворечива, то в ней невыводима некоторая формула, содержательно утверждающая непротиворечивость этой арифметики. Таким образом, средствами формальной системы нельзя доказать или опровергнуть утверждения о свойствах этой системы. Теоремы Гёделя замечательны, но они о неполноте бинарной логики. Однако есть исчисление высказываний Гейтинга и алгебры Брауэра (псевдобулевы алгебры). Они этих ограничений не имеют и больше соответствуют миру, в котором мы живём! Основное отличие небинарной логики от бинарной логики заключается в том, что в бинарной логике отсутствует закон исключённого третьего. 2. Дедукция Логический вывод выполняется на основе импликации и использует схемы дедукции, абдукции, традукции или индукции. Импликация описывает связь причины со следствием. У причины может быть несколько следствий и не все они нам известны. У следствия может быть несколько независимых причин и не все они нам известны. Закрытый мир: то, что записано в ФС – истина, иное – ложно. Т.е. все неизвестные/незаписанные причины и следствия объявляются ложными. Закрытый мир используется в системах автоматического логического вывода, например в языке Пролог. Открытый мир: истиной является всё, что записано, а также возможные причины и следствия о которых нам неизвестно или они не записаны. Открытый мир используется в теоретических доказательствах и в повседневных рассуждениях человека. Условное суждение – это суждение с условием, которое выражается связкой «если…». В условном суждении «если А, то В» высказывание «А» называется антецедентом (условием, причиной, посылкой), высказывание «В» называется консеквентом (следствием, заключением). Общее суждение – это суждение обо всех элементах некоторого множества. Частное суждение – это суждение об одном конкретном элементе некоторого множества. Дедукция (лат. deduction – выведение, умозаключение) – логический вывод (умозаключение), в котором частный консеквент выводится из общего антецедента. С помощью дедукции нельзя получить новое знание, открыть закон. Антецедентом дедукции являются общие аксиомы или гипотезы, а консеквентом – частные теоремы. Если антецедент дедукции истинен, то истинен и консеквент. Дедукция – основное средство логического вывода. Условно-категорические умозаключения Условно-категорические умозаключения – это умозаключения, в которых предпосылка содержит условное суждение, а также высказывание, совпадающее с положительным или отрицательным антецедентом или консеквентом этого условного суждения. Формы правильных модусов (видов) условно-категорических заключений:  утверждающий модус (лат. modus ponens – правило вывода) – истинность причины влечёт истинность следствия:  отрицающий модус (лат. modus tollens – вывод от противного) – отрицание следствия влечёт отрицание причины: ̅ ̅ Разделительно-категорические умозаключения Разделительно-категорические умозаключения – это умозаключения, в которых предпосылка содержит разделение предпосылок (дизъюнкцию или исключающую дизъюнкцию), а также высказывание, совпадающее с положительной или отрицательной предпосылкой. Формы правильных модусов разделительно-категорических заключений:  Утверждающе-отрицающий модус (лат. modus ponendo-tollens): ⊕ ⊕ ⊕ ̅ ̅  Отрицающе-утверждающий модус (лат. modus tollendo-ponens): ̅ ̅ Условные умозаключения Условные умозаключения – умозаключения, посылки и заключения которых являются условными суждениями.  Контрапозиция: ̅ ̅ например, если животное млекопитающее, то оно является позвоночным. Следовательно, если какое-либо животное не является позвоночным, то оно не является млекопитающим.  Сложная контрапозиция: ̅ ̅ например, если четыре стороны равны и углы прямые, то это квадрат. Следовательно, если четыре стороны равны, но не квадрат, значит углы не прямые.  Транзитивность: Дилеммы Дилеммы – вид умозаключений, содержащий два условных суждения и одно разделительное. Виды правильных дилемм:  конструктивная простая:  конструктивная сложная:  деструктивная простая:  ̅ ̅ ̅ ̅ ̅ деструктивная сложная: ̅ ̅ 3. Силлогистика Силлогистика (др.-греч. умозаключающий) – теория логического вывода, исследующая умозаключения, состоящие из т. н. категорических высказываний (суждений). В силлогистике рассматриваются, например, выводы заключения из одной посылки (непосредственные умозаключения), «сложные силлогизмы», или полисиллогизмы, имеющие не менее трёх посылок. Однако основное внимание силлогистика уделяет теории категорического силлогизма, имеющего ровно две посылки и одно заключение указанного вида. Классификацию различных форм (модусов) силлогизмов и их обоснование дал основатель логики как науки Аристотель. Простой категорический силлогизм – дедуктивное умозаключение, состоящее из трёх простых высказываний: двух посылок и одного заключения. Посылки силлогизма разделяются на большую (которая содержит предикат заключения) и меньшую (которая содержит субъект заключения). По положению среднего термина силлогизмы делятся на фигуры, а последние по логической форме посылок и заключения – на модусы. В высказывания простого категориального силлогизма входят три термина:    S – субъект заключения (о нём идёт речь), является меньшим термином; P – предикат заключения (высказывание о субъекте), является большим термином; M – средний термин входит в обе посылки, но не входит в заключение. Различают четыре вида простых высказываний:     a – от лат. affirmo – общеутвердительные: «Все люди (S) смертны (P)»; i – от лат. affirmo – частноутвердительные: «Некоторые люди (S) — студенты (P)»; e – от лат. nego – общеотрицательные «Ни один из китов (S) не рыба (P)»; o – от лат. nego – частноотрицательные «Некоторые люди (S) не являются студентами (P)». Для условного буквенного обозначения высказываний используются гласные из латинских слов affirmo (я утверждаю, говорю “да”) и nego (я отрицаю, говорю “нет”). Фигурами силлогизма называются формы силлогизма, отличающиеся расположением среднего термина в посылках: Большая посылка: Меньшая посылка: Заключение: Фигура 1 M–P S–M S–P Фигура 2 P–M S–M S–P Фигура 3 M–P M–S S–P Фигура 4 P–M M–S S–P Здесь каждая посылка и заключение состоят из ровно двух терминов. Как видим, большая и меньшая посылки связаны общим термином M, который не входит в заключение. Например, в силлогизме: Все небесные тела (M) движутся (P). (вид а) Все планеты (S) – это небесные тела (M). (вид а) Все планеты (S) движутся (P). (вид а) первая посылка является простым суждением вида a (общеутвердительным), вторая посылка – это тоже простое суждение вида a, и заключение в данном случае представляет собой простое суждение вида a. Поэтому рассмотренный силлогизм принадлежит фигуре 1 и имеет модус aaa. Силлогизм: Все журналы (P) – периодические издания (M). (вид а) Все книги (S) не являются периодическими изданиями (M). (вид e) Все книги не являются журналами. (вид e) принадлежит фигуре 2 и имеет модус aee. Силлогизм: Все углероды (M) – простые тела (P). (вид а) Все углероды (M) электропроводны (S). (вид а) Некоторые электропроводники (S) – простые тела (P). (вид i) принадлежит фигуре 3 и имеет модус aai. Так как каждая фигура силлогизма содержит три высказывания (две посылки и заключение) и каждое высказывание может быть сформулировано в одном из четырёх видов (a,i,e,o), то всего возможно 4*4*4=64 варианта (модуса) силлогизма. Четыре фигуры силлогизма содержат 64*4=256 модусов. Однако из всех этих 256 модусов только 19 дают достоверные выводы, остальные приводят к вероятностным выводам. Модусы изучались ещё средневековыми школами и для правильных модусов каждой фигуры были придуманы мнемонические имена: Фигура 1 Barbara Celarent Darii Ferio Фигура 2 Cesare Camestres Festino Baroco Фигура 3 Darapti Disamis Datisi Felapton Bocardo Ferison Примеры силлогизмов каждого типа. Barbara Все животные смертны. Все люди – животные. Все люди смертны. Celarent Ни одна рептилия не имеет меха. Все змеи – рептилии. Ни одна змея не имеет меха. Darii Все котята игривые. Некоторые домашние животные – котята. Некоторые домашние животные – игривые. Ferio Ни одна домашняя работа не весела. Некоторое чтение – домашняя работа. Некоторое чтение не весело. Cesare Ни одна здоровая еда не полнит. Все торты полнят. Ни один торт не здоровая еда. Camestres Все лошади имеют вздутие живота. Ни один человек не имеет вздутия живота. Ни один человек не лошадь. Festino Ни один ленивый человек не сдаёт экзамены. Некоторые студенты сдают экзамены. Некоторые студенты не ленивы. Baroco Все информативные вещи полезны. Некоторые сайты не полезны. Некоторые сайты не информативны. Darapti Все фрукты питательны. Все фрукты вкусны. Некоторые вкусные продукты питательны. Disamis Некоторые кружки красивы. Все кружки полезны. Фигура 4 Bramantip Camenes Dimaris Fesapo Fresison Некоторые полезные вещи красивы. Datisi Все прилежные мальчики в этой школе рыжие. Некоторые прилежные мальчики в этой школе – пансионеры. Некоторые пансионеры в этой школе рыжие. Felapton Ни один кувшин в этом шкафу не нов. Все кувшины в этом шкафу треснутые. Некоторые треснутые вещи в этом шкафу не новы. Bocardo Некоторые кошки бесхвосты. Все кошки – млекопитающие. Некоторые млекопитающие бесхвосты. Ferison Ни одно дерево не съедобно. Некоторые деревья зелёные. Некоторые зелёные вещи не съедобны. Bramantip Все яблоки в моём саду полезны. Все полезные фрукты зрелы. Некоторые зрелые фрукты – яблоки в моём саду. Camenes Все яркие цветы ароматны. Ни один ароматный цветок не выращен в помещении. Ни один выращенный в помещении цветок не ярок. Dimaris Некоторые небольшие птицы питаются мёдом. Все питающиеся мёдом птицы цветные. Некоторые цветные птицы небольшие. Fesapo Ни один человек не совершенен. Все совершенные существа мифические. Некоторые мифические существа не люди. Fresison Ни один компетентный человек не ошибается. Некоторые ошибающиеся люди работают здесь. Некоторые работающие здесь люди некомпетентны. Модусы могут быть преобразованы в другие модусы, и любой модус может быть преобразован в один из модусов первой фигуры. Заменой силлогизму служит более простая и мощная логика первого порядка, а также теория кванторов. Лекция 9. Недедуктивный логический вывод 1. Абдукция. 2. Трансдукция. 3. Индукция. 1. Абдукция Абдукция – процедура выдвижения гипотез. Абдукция представляет вид редуктивного вывода с той особенностью, что из условной предпосылки и заключения вытекает вторая предпосылка: т.е. мы предполагаем, что B – истинно. Но, в отличие от дедукции, мы не гарантируем это. Синтаксическим признаком предположения является звёздочка. Предпосылка может быть единственна: Редукция – сведение сложного к более простому. ерлок Холмс использовал именно абдукцию, а не дедукцию. Пример 1:  первая предпосылка: если животное млекопитающее, то оно является позвоночным;  заключение: жираф – позвоночное; с помощью абдукции можно предположить, что вторая посылка истинна:  жираф – млекопитающее. Однако если жирафа заменить рыбой, то предположение рыба – млекопитающее на самом деле будет ложным. Пример 2:  первая предпосылка: если был дождь, то будет урожай;  урожай есть; с помощью абдукции можно предположить, что вторая посылка истинна:  дождь был. На самом деле был искусственный полив, а дождя не было  Абдуктивные рассуждения чаще всего используются для открытия эмпирических законов. Теоретические законы не могут быть открыты с помощью абдукции. 2. Трансдукция (традукция) Трансдуктивное умозаключение (лат. traductio – перемещение) – умозаключение, в котором посылки и заключение являются суждениями одинаковой степени общности, т.е., когда вывод идёт от знания определённой степени общности к новому знанию, но той же степени общности. Традукция в общем виде: ( ) По характеру посылок и вывода трансдукция может быть трёх типов: 1) Заключение от единичного к единичному. 2) Заключение от частного к частному. 3) Заключение от общего к общему. Трансдуктивным умозаключением является аналогия. Аналогия – это такое умозаключение, в результате которого делается вывод о том, что исследуемый предмет, возможно, имеет ещё один признак Х, поскольку остальные известные нам признаки этого предмета сходны с признаками другого предмета, обладающего, кроме того, и признаком Х. ( )( ) ( ) и ( )( ) ( ) Таким образом, аналогия – это логический вывод, в результате которого достигается знание о признаках одного предмета на основании знания того, что этот предмет имеет сходство с другими предметами:    Земля имеет атмосферу, на Земле есть жизнь. Марс имеет атмосферу, следовательно, там есть жизнь. Луна не имеет атмосферы, следовательно, там нет жизни. 3. Индукция Индукция (лат. inductio – наведение, от лат. inducere – влечь за собой, установить) – процесс логического вывода на основе перехода от частного положения к общему. Индуктивное умозаключение связывает частные предпосылки с заключением не строго через законы логики, а скорее через некоторые фактические, психологические или математические представления. Различают полную индукцию – метод доказательства, при котором утверждение доказывается для конечного числа частных случаев, исчерпывающих все возможности, и неполную индукцию – наблюдения за отдельными частными случаями наводят на гипотезу о том, что утверждение присуще всем случаям, которые, конечно же, нуждаются в доказательстве. Полная индукция В полной индукции мы делаем общее заключение о свойстве всего множества после проверки этого свойства у всех элементов множества. Схема полной индукции:  Множество А состоит из элементов: А1, А2, А3, …, Аn.     А1 имеет признак В А2 имеет признак В Все элементы от А3 до Аn также имеют признак В Следовательно, все элементы множества А имеют признак В. Полную индукцию можно применить, когда мы имеем дело с закрытым классом предметов, число элементов в котором является конечным и легко обозримым. В прикладных задачах полная индукция занимает меньше места, чем неполная, так как с полным набором всех случаев человек имеет дело гораздо реже, чем с их неполным набором. Неполная индукция Метод обобщения признаков некоторых элементов для всего множества, в которое они входят. Неполная индукция не является доказательной с точки зрения формальной логики, и может привести к ошибочным заключениям. Вместе с тем, неполная индукция является основным способом получения новых знаний. Схема неполной индукции:      Множество А состоит из элементов: А1, А2, А3, ... Аk, ... Аn. А1 имеет признак В А2 имеет признак В Все элементы от А3 до Аk также имеют признак B Следовательно, вероятно, Аk+1 и остальные элементы множества А имеют признак В. Пример ошибочного результата при неполной индукции:    В Аргентине, Венесуэле и Эквадоре говорят на испанском языке. Аргентина, Венесуэла и Эквадор – латиноамериканские страны. Следовательно, вероятно, в каждой латиноамериканской стране говорят на испанском языке. На самом деле Бразилия говорит на португальском, Гаити – на французском. Методы неполного индуктивного вывода: Метод сходства ( )( ( ) ) Метод различия ( )( ̅ ( ) ( )( ) ̅) Метод остатков ( ) Метод сопутствующих изменений ( ) Стандартные ошибки при неполной индукции:    «Поспешное обобщение» при скудной статистике. «После этого, значит по причине этого». Источник такой ошибки – замена причинной связи временнóй последовательностью событий. «Замена условных посылок безусловными». Например, если в обычных условиях вода замерзает при температуре 0оС, то с изменением этих условий, например, течение воды, примеси в воде или высокое атмосферное давление, температура замерзания понижается. Лекция 10. Исчисление высказываний 1. Язык исчисления высказываний. 2. Методы определение выводимости высказываний. формул исчисления 1. Язык исчисления высказываний Высказывание – повествовательное предложение, о котором в рамках данной ФС можно сказать истинно оно или ложно. Исчисление высказываний задаётся аксиоматической ФС: 1. Алфавит: - бесконечное счётное множество строчными именами; - логические операции:    ; - скобки ( ) Других символов нет. высказываний, обозначаемых 2. Правила построения формул. Формулы обозначаются заглавными буквами. - всякое высказывание есть формула, - если X и Y формулы, то X, (X), XY, XY, XY также формулы. 3. Аксиомы: 1. x  (y  x) (чел  (родчел)) – причина есть у всего 2. (x  (y  z))  ((x  y)  (x  z)) 3. xy  x причин может быть несколько 4. xy  y причин может быть несколько 5. (z  x)  ((z  y)  (z  xy)) следствия произойдут все 6. x  xy у всего есть альтернатива 7. y  xy у всего есть альтернатива 8. (x  z)  ((y  z)  (xy  z)) достаточно одной причины 9. (x  y)  (yx) 10.  ̿ 11. ̿  4. Правила вывода: А  В, А В А  В , В Modus tollendo tollens: А А  В , А  В Исключение абсурда: А Modus ponendo ponens: Специализация: ( x) w( x)  ( X  А)  w( A) (от общего к частному). 2. Методы высказываний определение выводимости формул исчисления 2.1. Редукция позволяет доказывать общезначимость формул исчисления высказываний путём приведения к абсурду. Пример. Докажем общезначимость формулы ) ( )). (( ) ( Предположим, что формула ложна. Импликация ложна в случае 10. Следовательно, должны выполниться две формулы ( ) , ( ) . ( ) Формула выполнится при значениях переменных: ) , , . Подстановка этих значений в формулу ( ) приведёт к противоречию (абсурду): ( . Значит предположение о ложности формулы неверно. Поэтому формула общезначима. 2.2. Резолюция ̅ ) – истинные формулы. Тогда если )и( Пусть две формулы ( X – истина, то B – тоже истина. Если X – ложь, то A – истина. Получаем правило резолюции, т.е. выводимости из двух дизъюнктов нового дизъюнкта ̅ . Новый дизъюнкт называется резольвентой. Дизъюнкт ̅) вида ( называется пустым. Пустой дизъюнкт является признаком невыполнимости множества дизъюнктов. Для использования резолюции нам потребуется представить импликацию в виде инверсии конъюнкции ( ) ( ̅ ) (̿̿̿̿̿̿̿ ̅ ) (̅̅̅̅̅̅̅). Следовательно, для доказательства истинности достаточно ̅̅̅̅̅̅ доказать, что ( ̅) или, что то же самое, ( ̅) . Рассмотрим использование резолюции для доказательства выводимости формулы. Дано: импликация  Необходимо доказать выводимость формулы C, т.е. истинность формулы [  ] Доказательство. 1) Заменим доказательство формулы [  ] ̅] доказательством формулы [ . Другими словами ̅ . надо доказать невыполнимость множества ̅ невыполнимо, если будет 2) Множество найден хотя бы один пустой дизъюнкт. Для этого выполняется алгоритм: аг 1. Если множество S имеет пустой дизъюнкт, то оно невыполнимо и импликация  истинна, останов алгоритма. Иначе – переход к шагу 2. аг 2. Построение резольвенты. Если резольвенту построить нельзя, то множество S выполнимо и импликация  ложна, останов алгоритма. Иначе – переход к шагу 3. аг 3. Добавляем к множеству S резольвенту, полученную на шаге 2. Переходим к шагу 1. ) ( ) (̅ Пример. Докажем истинность формулы ( ̅ ) . )( ) (̅ Для этого на множестве ( ̅ ) ̅ надо построить пустой дизъюнкт (рис. 1). Если построить пустой дизъюнкт невозможно, то исходная формула неверна. 𝑝 𝑝 𝑞 𝑝 𝑟̅ 𝑞̅ 𝑟 𝑟̅ 𝑝̅ 𝑞 𝑝 𝑟̅ Рис. 1. Дерево вывода пустого дизъюнкта Пустой дизъюнкт построен, исходная формула истинна. Алгоритм резолюции недетерминирован. Может существовать множество вариантов получения пустого дизъюнкта. Выбор оптимального варианта получения пустого дизъюнкта является комбинаторной задачей с экспоненциальной сложностью. ЛР 7. Исследование выводимости формул исчисления высказываний Задачи: 1. Доказать или опровергнуть общезначимость формул методом редукции: ) ) а) (( ̅ ̅ ) (( )) (( ); )) ( ); б) (( ̅) ( )) ( ( )). в) (( ̅ ̅ ) ( 2. Доказать или опровергнуть истинность формул методом резолюции: ) ( ) ; а) ( ̅) ( ̅) ( ̅ ) ( ) ( ) ̅; б) ( ̅) ( ) ( ) ( ) ; в) ( ̅) ( ( )) (( ) ) ( ) ̅. г) ( ̅) ( Лекция 11. Логика предикатов 1. Понятие предикатов и операции над ними. (с.12-16) 2. Формальная система логики предикатов. (Гринченков 60-61) 3. Метод резолюций для логики предикатов. (с.16-19) 4. Проблемы аксиоматического исчисления предикатов. 1. Предикаты и операции над ними В исчислении высказываний сведения о мире описывались высказываниями, которые не меняли своего значения, так имели только одно значение – то, что они выражали. По сути, они являются константами со значением истинности {0,1}. Для практических нужд это явно недостаточно, так как для производства даже простейших вычислений необходимы переменные и правила действия над ними. От этого недостатка свободна логика предикатов. Логика предикатов – расширение логики высказываний путём введения предикатов и кванторов над переменными. Одноместный предикат P(x) – произвольная функция переменного x, определенного на множестве M (xM), и принимающая значения из множества B={0,1}. Предикат P(x) можно понимать как высказывание о свойстве объекта x. Множество M, на котором определён предикат, называется предметной областью или областью определения предиката. Переменная x называется предметной переменной. Множество всех xM, при которых P(x)=1, называется множеством истинности предиката IP={x| xM, P(x)=1}. Предикат P(x), определённый на множестве M, называется тождественно истинным, если IP=M, и тождественно ложным, если IP=. В отличие от булевых функций, у которых область определения и область значения являются одной логической областью B={0,1}, предикаты имеют область определения предметную, а область значений – логическую B={0,1}. Примеры. Предикат чётное(x) на множестве целых чисел. Предикат простое(x). n-местный предикат Q(x1,x2,…,xn) – функция n переменных, определённая на множестве M=M1M2…Mn (декартово произведение) и принимающее значения из множества B={0,1}.То есть Q:MB. Переменные x1,x2,…,xn называются предметными переменными. Пример. Предикат больше(x,y). Предикат корни(a,b,c,x1,x2). Предикат Q(x1,x2,…,xn) можно понимать как высказывание об отношении между объектами x1,x2,…,xn. Высказывания можно полагать нульместными предикатами P(). Так как предикаты принимают значения из области B={0,1}, то к ним применимы все операции логики высказываний. Предикат называют тождественно-истинным, если на любом наборе аргументов он принимает значение “истина”. Его реализация очень проста, например неравенство 1>0 является тождественно-истинным предикатом. Предикат называют тождественно-ложным, если на любом наборе аргументов он принимает значение “ложь”. Его реализация также проста, например 1>1. Предикат называют выполнимым, если хотя бы на одной комбинации аргументов он принимает значение “истина”. Конъюнкция двух предикатов P(x) и Q(x) есть новый предикат P(x) & Q(x), который принимает значение 1 тогда, когда каждый из предикатов принимает значение 1. И принимает значение 0 во всех остальных случаях. Областью истинности предиката P(x) & Q(x) является пересечение IP  IQ. Дизъюнкция двух предикатов P(x) и Q(x) есть новый предикат P(x)  Q(x), который принимает значение 0 тогда, когда каждый из предикатов принимает значение 0. И принимает значение 1 во всех остальных случаях. Областью истинности предиката P(x)  Q(x) является объединение IP  IQ. Отрицание предиката P(x) есть новый предикат P(x), который принимает значение 1 тогда, когда P(x) принимает значение 0 и наоборот. Областью истинности предиката P(x) является разность M\IP. Импликация двух предикатов P(x) и Q(x) есть новый предикат P(x)  Q(x), который принимает значение 0 тогда, когда P(x)=1 и Q(x)=0 одновременно, и принимает значение 1 во всех остальных случаях. Кванторные операции Кроме логических операций в логике предикатов вводятся кванторные операции или просто кванторы. Кванторы превращают одноместный предикат в высказывание, т.е. связывают аргумент предиката. Кванторов всего два: квантор всеобщности и квантор существования. Квантор всеобщности . Пусть P(x) – предикат, xM. Под выражением x P(x) понимают высказывание, истинное, если P(x) истинно для каждого xM и ложное в противном случае. Соответствующее словесное выражение звучит так “для всякого x предикат P(x) истинен”. Выражение x P(x) истинно только тогда, когда P(x) – тождественно истинный предикат. Переменная x в предикате P(x) называется свободной переменной. Переменная x в выражении x P(x) называется связанной переменной. Квантор существования . Пусть P(x) – предикат, xM. Под выражением x P(x) понимают высказывание, истинное, если существует элемент xM, для которого P(x) истинно и ложное в противном случае. Соответствующее словесное выражение звучит так “существует x при котором предикат P(x) истинен”. Высказывание x P(x) не зависит от x, так как переменная x связана квантором . Выражение x P(x) ложно только тогда, когда P(x) – тождественно ложный предикат. Кванторные операции применяются и к многоместным предикатам. Применение кванторной операции к двухместному предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат x P(x,y) или x P(x,y), зависящий от y и не зависящий от x. К двухместному предикату можно применить кванторные операции по обеим переменным. Тогда получим восемь высказываний: 1. 2. 3. 4. 5. 6. 7. 8. xy P(x,y) xy P(x,y) xy P(x,y) xy P(x,y) yx P(x,y) yx P(x,y) yx P(x,y) yx P(x,y) Порядок следования кванторов в общем случае существенен и изменяет смысл высказывания. Пусть M(x,y) означает “x есть мать для y”. Тогда yx M(x,y) означает “у каждого человека есть мать”. И это истинное утверждение. А выражение xy M (x,y) означает “существует мать всех людей”. Истинность этого утверждения зависит от множества значений, которые может принимать y. Если это множество братьев и сестёр, то оно истинно, в противном случае – ложно. Один квантор можно выразить через другой: x P(x) = x P(x). x P(x) = x P(x). 2. Формальная система логики предикатов Гринченков 60-61. 3. Метод резолюций для логики предикатов Унификация – процедура нахождения НОУ. Наиболее общий унификатор – множество подстановок, делающих эти предикаты эквивалентными. Подстановка – замена переменной основным или неосновным термом. с.9-12 Унификация предикатов выполняется за три этапа: 1) Проверка равенства имён предикатов. 2) Проверка равенства арности предикатов. 3) Поиск множества подстановок. Если подстановки всех переменных найдены и являются основными термами, то сопоставление с образцом считается успешным, иначе — сопоставления с образцом считается неуспешным и замена переменных найденными значениями не производится. Приведение к множеству дизъюнктов + метод резолюции: с.16-19. 4. Проблемы аксиоматического исчисления предикатов Алгоритмическая разрешимость – проблема отыскания алгоритма, решающего тот или иной класс однотипных задач. Если алгоритмическая проблема разрешима, то алгоритм решения задач построить можно. Если алгоритмическая проблема неразрешима, то алгоритм решения задач построить нельзя. Исчисление противоречиво, если в нём доказуема как формула, так и её отрицание. Система аксиом независима, если каждая аксиома не выводима из других аксиом. Логическая система называется полной в узком смысле, если нельзя без противоречия присоединить к её аксиомам в качестве новой аксиомы никакую не выводимую в ней формулу так, чтобы полученная при этом система была непротиворечивой. Лекция 12. Машина логического вывода 1. Миры вывода. с.21 2. Дизъюнкты Хорна. с.19-20 3. Машина логического вывода (поиск с возвратом). с. 22-28 4. Чистота предикатов и внелогические средства. с.22,36 1. Миры вывода Процедурный смысл выполнения машиной логического вывода правила r(X)  p(X) прост. Если предикат r(X) успешен, то считается, что предикат p(X) тоже успешен. Если же предикат r(X) неуспешен, то считается, что предикат p(X) также неуспешен. Описанное правило отличается от правила вычисления импликации, принятого в математической логике, где при ложной посылке следствие может быть как ложным, так и истинным, то есть истинность следствия при ложной посылке неизвестна. Причина этого отличия кроется в том, что мир вывода в МЛВ замкнут, а мир логического вывода в математической логике открыт. Открытый мир вывода — это мир, правила которого всегда можно изменить или дополнить с целью адекватного описания задачи. Замкнутость вывода в Прологе означает следующее. Всё, о чём описано в программе считается известными сведениями об описываемом мире, известными — значит истинными. Если же каких-то сведений о задаче в программе нет, то они считаются ложными, независимо от их реальной истинности в описываемом мире. Предположение о замкнутости мира существенно упрощает логический вывод в Прологе, замещая неоднозначность типа {"Успех", "Неуспех", "Неизвестно"} дуализмом {"Успех", "Неуспех"}, в котором неизвестно рассматривается как неуспех. Рассмотрим различия замкнутого и открытого миров логического вывода на следующем примере. Пусть есть правило "если дождь, то урожай". И известно, что "дождь был". В замкнутом мире вывода будет сделано заключение, что урожай будет. В открытом мире вывода заключение такое же — урожай будет, так как в обоих мирах из истинной посылки следует истинное заключение. Давайте теперь посмотрим на заключения в случае, когда "дождя не было". В замкнутом мире будет сделано заключение, что урожая не будет. В открытом мире никаких заключений о будущем урожае сделать нельзя. Действительно, ведь можно в открытом мире вывода предположить, что при отсутствии дождя был искусственный полив, тогда урожай будет. Но в закрытом мире вывода Пролога об искусственном поливе никаких явно указанных сведений нет, следовательно, искусственного полива нет. 2. Дизъюнкты Хорна Правило r ( x)  p( x) в математической логике можно представить в форме дизъюнкции r ( x)  p( x) . Почему именно такая дизъюнкция выражает импликацию? Объяснение очень простое. Импликация имеет два взаимоисключающих правила вывода результата:  если причина r (x) успешна, тогда и следствие p (x ) успешно;  если причина r (x) неуспешна, то о следствии ничего заключить нельзя. Первый вариант записывается конъюнкцией r ( x)  p( x) , второй вариант выражается отрицанием r (x) . Результат будет получен либо по первому правилу, либо по второму. Поэтому оба правила составляют дизъюнкцию, которую можно упростить по правилу Блейка-Порецкого: r ( x)  r ( x)  p ( x)  r ( x)  p ( x) Дизъюнкция r ( x)  p( x) всегда имеет только один положительный предикат, то есть предикат без отрицания, тот самый предикат, доказательство которого и описывает правило. Такой дизъюнкт в математической логике называют дизъюнктом Хорна или предложением Хорна. 3. Машина логического вывода с.22-28 + рекурсивные предикаты 4. Чистота предикатов и внелогические средства В теории логического программирования рассматривается понятие чистого Пролога. Чистый Пролог — это логический язык, содержащий только чистые предикаты. Чистые предикаты — это предикаты, значение которых зависит только от их аргументов и не зависит от состояния памяти компьютера. Чистые предикаты не имеют побочных эффектов, т. е. они не читают из памяти какие-либо дополнительные данные и не пишут в неё какие-либо результаты вычислений. В чистом Прологе выполняются все свойства логических операций отрицания, дизъюнкции и конъюнкции. Выше мы рассматривали, что свойство коммутативности относительно конъюнкции и дизъюнкции выполняется и при этом декларативный смысл программы не изменяется. Однако сейчас пора сделать существенную оговорку — коммутативность выполняется только в чистом Прологе. Рассмотреть ввод/вывод, assert/retract. Внелогические средства МЛВ На практике чистый Пролог не применим, так как для реального программирования необходим ряд внелогических предикатов. Внелогические предикаты — это предикаты, значение которых существенно зависит от состояния памяти компьютера и периферийных устройств, или это предикаты, которые изменяет память компьютера и состояние периферийных устройств (ввод/вывод, assert/retract). Внелогические предикаты вызывают побочный эффект, так как имеют доступ по чтению и записи в память компьютера и поэтому являются "нечистыми". Пролог имеет множество внелогических предикатов. Классическим примером являются предикаты ввода и вывода. Предикаты ввода читают информацию из устройств ввода, а предикаты вывода записывают информацию в устройства вывода. Над внелогическими предикатами не выполняется свойство коммутативности относительно конъюнкции и дизъюнкции. Например, конъюнкция простое(X) and write(X) имеет декларативный смысл "вывести на экран число X в случае, если оно простое". А конъюнкция write(X) and простое(X) сначала выводит число X, независимо от того, простое оно или нет, а потом проверяет его простоту. Модифицируемые рассуждения Монотонный вывод – в ходе рассуждений правила вывода не модифицируются. Один раз доказанная теорема остаётся истинной в БЗ навсегда. Немонотонный вывод - в ходе рассуждений правила вывода модифицируются. Введение новых аксиом может уточнить или даже опровергнуть старые аксиомы и, следовательно, теоремы. Однако полученные в результате немонотонного вывода положения не являются общезначимыми, т.е. они могут быть опровергнуты при последующих рассуждениях. Удаление, добавление, изменение предикатов в ходе выполнения логического вывода. Предикаты assert, asserta, retract, retractAll. Показать работу этих предикатов. ЛР 8. Исследование логического вывода Машина логического вывода Пролога (PIE – Prolog Inference Engine) поддерживает: Унарные операции: Унарные функции: Бинарные операции: Бинарные функции: Предикаты: + , – abs (абсолютное значение), trunc (округление в сторону нуля), round (математическое округление), sqrt (квадратный корень) + (сложение или конкатенация строк), – , * , / (вещественное деление), ^ (возведение в степень), div (целочисленное деление), mod (остаток целочисленного деления, знак остатка имеет знак делителя), rem (остаток целочисленного деления, знак остатка имеет знак делимого) min, max (над числами и строками) = (равно или унификация), <, >, =<, <= (меньше или равно), =>, >= (больше или равно), <>, ><, \= (неравно), Задачи: 1. Дано множество точек на декартовой плоскости в виде множества предложений предиката point/2: point(1.0, point(1.0, point(1.0, point(2.0, point(2.0, point(2.0, point(3.0, point(4.0, point(4.0, 1.0). 2.0). 4.0). 1.0). 2.0). 4.0). 2.0). 1.0). 3.0). Требуется вычислить цели: а) вывести на экран координаты X,Y всех точек; б) вывести все точки, сумма координат X и Y которых равна 5; в) вывести все пары точек, симметричных относительно прямой y=x; г) вывести все точки, имеющие чётную координату X и нечётную координату Y; д) вывести все точки, принадлежащие прямой y=0,6x+0,4; е) вывести все точки, находящиеся выше прямой y=0,6x+0,4; ё) вывести все точки, принадлежащие квадрату с центром в точке (2,1) и стороной длиной 2; ж) вывести все точки, лежащие вне круга с центром в точке (1,2) и радиусом 1,2; 2. Дано множество 12 месяцев в виде предложений предиката месяц/3: месяц(1,январь,31). месяц(2,февраль,28). месяц(3,март,31). и т.д. Требуется вычислить цели: а) вывести номера месяцев продолжительностью 31 день; б) вывести суммарную продолжительность летних месяцев; в) вывести имена нечётных месяцев. Раздел 3. Теория алгоритмов Лекция 13. Введение в теорию рекурсивных функций 1. Свойства алгоритмов. 2. Вычислимые функции. 3. Примитивно рекурсивные функции. 1. Свойства алгоритмов Свойства алгоритмов (с. 51-54): 2. Вычислимые функции Функция называется вычислимой, если существует алгоритм, позволяющий вычислять её значения. Простейшие вычислимые функции: (x) = x+1 – оператор сдвига; O(x) = 0 – оператор аннулирования; ( ) , 1mn – оператор проектирования (проецирования). Суперпозиция функций (с. 58) 3. Примитивно рекурсивные функции Схема примитивной рекурсии (с.64) Схема возвратной рекурсии Схема итерации Функция f называется примитивно рекурсивной, если её можно получить конечным числом операций суперпозиции и примитивной рекурсии, исходя из простейших вычислимых функций , O, . ЛР 9. Исследование примитивной рекурсии 1. Построить на языке Haskell с помощью оператора примитивной рекурсии всюду определённую и вычислимую функцию: а) произведения mul(x,y); ( ) б) возведения в степень: . в) усечённого декремента: ( ) г) усечённой разности: ( д) усечённого знака числа: { ) { ( ) { е) модуля разности двух чисел: ( ) ё) равенства: ж) меньше: з) больше: ( ( ) ) ( { { ) { ; Лекция 14. Частично рекурсивные и общерекурсивные функции 1. Операция минимизации. 2. Частично рекурсивные функции. 3. Общерекурсивные функции. 1. Операция минимизации mu0(f,y) = if f(y) == 0 then y else mu0(f,s(y)) mu1(f,x,y) = if f(x,y) == 0 then y else mu1(f,x,s(y)) mu2(f,x1,x2,y) = if f(x1,x2,y) == 0 then y else mu2(f,x1,x2,s(y)) mu3(f,x1,x2,x3,y) = if f(x1,x2,x3,y) == 0 then y else mu3(f,x1,x2,x3,s(y)) Задача 1: найти корни уравнения: h(y) = 64 - y^2 Решение: mu0(h,0) Задача 2: найти корни уравнения: g(x,y) = x - y^2 Решение: mu1(g,64,0) Задача 3: найти корни уравнения: u(a,b,c,y) = a*y^2 + b*y + c Решение: mu3(u,1,-5,6,0) (с.71) 2. Частично рекурсивные функции Функция f называется частично (определённой) рекурсивной, если она может быть получена за конечное число шагов из простейших вычислимых функций , O, при помощи операции суперпозиции, схем примитивной рекурсии и операции минимизации. (с. 75) 3. Общерекурсивные функции Функция называется общерекурсивной, если она частично рекурсивна и всюду определена. (с. 75) ЛР 10. Исследование частично определённой рекурсии 1. С помощью -оператора найти корень уравнения: . 2. С помощью -оператора найти число по его факториалу. 3. С помощью -оператора найти все корни уравнения: + . Лекция 15. Машина Тьюринга (с.99-115) 1. Устройство и принцип действия машины Тьюринга. 2. Классификация машин Тьюринга. 3. Программирование машины Тьюринга. 1. Устройство и принцип действия машины Тьюринга Машина Тьюринга (МТ) – вычислительная модель для автоматического выполнения алгоритма, решающего некоторую массовую проблему. Устройство управления может находиться в одном состоянии из множества состояний . Q – внутренний алфавит МТ конечен и фиксирован. Состояние qz считается конечным состоянием. Лента – бесконечная внешняя память, разбитая на ненумерованные ячейки (ячейки без адреса). В каждой ячейке может быть записан один символ из внешнего алфавита . Во внешнем алфавите должен присутствовать символ пробела, обозначаемый обычно , который записывается в пустых ячейках. На ленте фиксируются исходные и промежуточные данные, а также результат. Так как лента бесконечна, то МТ является моделью, а не реальным устройством. Головка считывания/записи для взаимодействия с ячейкой, расположенной напротив головки. Система команд (программа) МТ содержит команды одного типа: . Здесь:  – текущее состояние устройства управления;  – символ, считанный из ячейки напротив головки;  –состояние устройства управления, в которое оно переходит после чтения символа . – новое состояние или прежнее состояние;  ’ – символ, который записывается в ячейку. может быть новым символом или прежним.  d – команда перемещения головки (R – вправо, L – влево, E – без изменения). Головка считывания/записи выполняет одну команду за ряд элементарных операций:  чтение символа с той ячейки ленты, напротив которой расположена головка;  запись нового значения в эту ячейку;  смещение головки на одну ячейку влево или вправо вдоль ленты или сохранение прежней позиции головки в зависимости от d;  переход устройство управления в новое состояние или сохранение прежнего состояния в зависимости от команды. Реализация указанной последовательности операций называется таком МТ. МТ завершает свою работу при переходе в состояние . Если при исходной информации на ленте B0 МТ завершит свою работу и на ленте будет информация B, то говорят, что МТ применима к В0 и перерабатывает её в В. Если МТ не переходит в состояние qz, то говорят, что МТ не применима к В0. Конкретная МТ задаётся перечислением элементов Q, А и программой (набором команд). Последовательность команд в программе не важна! 2. Классификация машин Тьюринга Одноленточные, многоленточные. Детерминированные, недетерминированные. Программы для МТ могут записываться в виде:  таблицы переходов состояний, в ячейках которой указывается ;  графа переходов состояний, в вершинах которого указываются состояния, а дуги помечены командами . 3. Программирование машины Тьюринга Унарные числа. Пример 1. Определение чётности унарного числа. Пример 2. Инкремент/декремент унарного числа. Бинарные числа. Пример 3. Определение чётности бинарного числа. Десятичные цифры. Пример 4. Инкремент/декремент десятичной цифры i, 0i9. Демонстрация ДМТ на проекторе. ЛР 11. Программирование машины Тьюринга 1. Разработать программу сравнения двух унарных чисел. Возвращаемый результат принадлежит множеству символов . Например, информация на ленте «111?11» перерабатывается к виду «111>11». 2. Разработать программу умножения унарного числа на 2. 3. Разработать программу определения остатка целочисленного деления унарного числа на 2. 4. Разработать программу определения усечённого знака бинарного числа ( ) { . 5. Разработать программу инкремента бинарного числа. 6. Оценить эффективность машины Тьюринга по вычислительной сложности на задачах 1-5. показателю Лекция 16. Нормальные алгоритмы Маркова (с.116-133) 1. Алфавит и словарные подстановки. 2. Нормальный алгоритм Маркова. 3. Примеры алгоритмов. 1. Алфавит и словарные подстановки Алфавит А – непустое конечное множество символов. Слово в алфавите А – конечная последовательность символов этого алфавита. Слово пустое если не имеет ни одного символа. Пусть символы  и  обозначают слова, записанные в алфавите А, не содержащем сами символы  и . Слово  называется композицией слов  и , если  приписана к слову  справа без пробелов. Слово  называется подсловом слова , если  можно представить в виде композиции , где ,  - подходящие (возможно пустые) слова. Подслово  может иметь несколько непересекающихся вхождений в слово , если  можно представить в виде композиции, например, . Подслово =aba, А={a,b}, может иметь несколько пересекающихся вхождений в слово , если =abababa. В данном примере подслово  входит в слово  три раза. Подстановка – замена в слове  первого вхождения подслова  подсловом . Правило этой подстановки записывается так . Пример. Пусть задано слово abababa и правило подстановки abaсс в алфавите А={a,b,c}. Тогда выполнение заданного правила преобразует слово abababa в слово ссbaba. Повторное применение этого правила к полученному слову преобразует его в слово ссbсс. Третий раз заданное правило подстановки не выполнится, так как полученное слово не содержит подслова aba. abababa ссbaba  ссbсс 2. Нормальный алгоритм Маркова Пусть задан алфавит А, исходное слово Р в алфавите А и правила подстановок. Нормальный алгоритм Маркова предписывает следующие действия. 1) Просмотреть правила подстановок в порядке, в котором они заданы, разыскивая левую часть правила в слове Р. Если такого правила не найдётся, то алгоритм останавливается. В противном случае совершить подстановку в слове Р на место вхождения левой части правила её правой части. При этом слово Р преобразуется в слово Р1 в алфавите А. Слово Р1 является результатом первого такта работы машины Маркова. 2) Повторять пункт 1) к результату подстановки до тех пор, пока алгоритм не остановится. Условия останова два: либо ни одно правило подстановки не применимо, либо выполнено последнее правило подстановки. После остановки алгоритма считается, что алгоритм маркова переработал слово Р в слово Рn. Нормальный алгоритм Маркова можно рассматривать наравне с частично рекурсивными функциями и машиной Тьюринга как стандартный способ представления любого алгоритма. Эти три вычислительные модели имеют свои достоинства и недостатки для разных типов задач. Машина нормальных алгоритмов Маркова (ММ) является детерминированной - ДММ. Возможен вариант недетерминированной машины Маркова. 3. Примеры алгоритмов Унарные числа. Пример 1. Определение чётности унарного числа. Пример 2. Инкремент/декремент унарного числа. Бинарные числа. Пример 3. Определение чётности бинарного числа. Десятичные цифры. Пример 4. Инкремент/декремент десятичной цифры i, 0i9. Демонстрация ДММ на проекторе. ЛР 12. Исследование нормальных алгоритмов Маркова 1. Разработать программу сравнения двух унарных чисел. Возвращаемый результат принадлежит множеству символов . Например, информация на ленте «111?11» перерабатывается к виду «111>11». 2. Разработать программу умножения унарного числа на 2. 3. Разработать программу определения остатка целочисленного деления унарного числа на 2. 4. Разработать программу определения усечённого знака бинарного числа ( ) { 5. Разработать программу инкремента бинарного числа. 6. Оценить эффективность нормального алгоритма показателю вычислительной сложности на задачах 1-5. Маркова по Лекция 17. Равнодоступная адресная машина (с.136-151) 1. Устройство и принцип действия. 2. Классификация РАМ. 3. Принцип действия и система команд НРАМ. ЛР 13. Программирование равнодоступной адресной машины 1. Дан массив чисел произвольной длины. Найти максимальный и минимальный элементы массива и вывести их на ленту. 2. Даны два массива А и В, разделённые нулём. Массивы не содержат нулей и имеют произвольный и возможно не равный друг другу размер. Найти одну такую пару чисел , и , для которой выполняется условие + и вывести её на ленту. Иначе на ленту вывести 0. 3. Дан массив произвольной длины. Если на ленте он упорядочен по возрастанию, то вывести 1, иначе 0. 4. Оценить эффективность РАМ по показателю вычислительной сложности на задачах 1-3. Лекция 18. Сложность алгоритмов 1. Проблемы алгоритмической разрешимости. 2. Основные термины и определения сложности алгоритмов. 3. Теоретически закрытые и теоретически открытые задачи. 4. Классификация задач по сложности. 1. Проблемы алгоритмической разрешимости    Неразрешима задача установления истинности произвольной формулы исчисления предикатов. Проблема остановки: можно ли по описанию алгоритма и входным данным установить, завершится ли выполнение алгоритма результативной остановкой? Распознавание эквивалентных алгоритмов. 2. Основные термины и определения сложности алгоритмов Временная и пространственная сложности Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов, чётко описывать их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входа и выхода. Количество элементарных операций, затраченных алгоритмом для решения конкретного экземпляра задачи, зависит не только от размера входных данных, но и от самих данных. Например, количество операций алгоритма сортировки вставками значительно меньше в случае, если входные данные уже отсортированы. Чтобы избежать подобных трудностей, рассматривают понятие временной сложности алгоритма в худшем случае. Временная сложность алгоритма (в худшем случае) — это функция размера входных и выходных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера. В задачах, где размер выхода не превосходит или пропорционален размеру входа, можно рассматривать временную сложность как функцию размера только входных данных. Аналогично понятию временной сложности в худшем случае определяется понятие временная сложность алгоритма в наилучшем случае. Также рассматривают понятие среднее время работы алгоритма, то есть математическое ожидание времени работы алгоритма. Иногда говорят просто: «Временная сложность алгоритма» или «Время работы алгоритма», имея в виду временную сложность алгоритма в худшем, наилучшем или среднем случае (в зависимости от контекста). По аналогии с временной сложностью, определяют пространственную сложность алгоритма, только здесь говорят не о количестве элементарных операций, а об объёме используемой памяти. Асимптотическая сложность Несмотря на то, что функция временной сложности алгоритма в некоторых случаях может быть определена точно, в большинстве случаев искать точное её значение бессмысленно. Дело в том, что, во-первых, точное значение временной сложности зависит от определения элементарных операций (например, сложность можно измерять в количестве арифметических операций, битовых операций или операций на машине Тьюринга), а во-вторых, при увеличении размера входных данных вклад постоянных множителей и слагаемых низших порядков, фигурирующих в выражении для точного времени работы, становится крайне незначительным. Рассмотрение входных данных большого размера и оценка порядка роста времени работы алгоритма приводят к понятию асимптотической сложности алгоритма. При этом алгоритм с меньшей асимптотической сложностью является более эффективным для всех входных данных, за исключением лишь, возможно, данных малого размера. Для записи асимптотической сложности алгоритмов используются асимптотические обозначения: Примеры  «пропылесосить ковёр» требует время, линейно зависящее от его площади, то есть на ковёр, площадь которого больше в два раза, уйдёт в два раза больше времени. Соответственно, при увеличении площади ковра в сто тысяч раз, объем работы увеличивается строго пропорционально – в сто тысяч раз, и т.п.  «найти имя в телефонной книге» требует всего лишь время, логарифмически зависящее от количества записей (N), так как, открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое (за счёт сортировки имён по алфавиту). Таким образом, в книге, толщиной в 1000 страниц, любое имя находится не больше чем за 10 раз (открываний книги).    Вычислительные задачи классифицируются: по теоретически доказанной нижней границе сложности задачи fthlim(n) (если таковая известна) по тривиальной эвристической нижней границе ftr(n) сложности задачи по сложности fAmin(n) наилучшего для данной задачи алгоритма, n – размерность входных данных. Сложность алгоритма - верхняя граница числа операций, необходимых для получения результата. Три класса сложности алгоритмов: 1. Класс (f) задаётся своей нижней границей – функцией f и содержит функции, растущие не медленнее, чем f. 2. Класс O(f) задаётся своей верхней границей – функцией f и содержит функции, растущие не быстрее, чем f. 3. Класс (f) содержит функции одинаковой сложности. Notation for Complexity In later lectures, it will be helpful to have some notation for measuring the growth of functions, a notation that ignores the “low-order terms” that vary from one implementation to another. What follows is the standard notation that computer scientists use for this purpose. Big-O Notation We say f(n) = O(g(n)) if there exist constants a, b such that f(n) < ag(n)+ b for all n. The function g(n) is an upper bound on the growth of f(n). A different way to think of Big-O is that g(n) ”grows” at least as quickly as f(n) as n goes to infinity. f(n) = O(g(n)) is read as ”f(n) belongs to the class of functions that are O(g(n))”. Big-Omega Notation We say f(n) = Ω(g(n)) if there exist a > 0 and b such that f(n) > ag(n) − b for all n. Intuitively, the function f(n) grows at the same rate or more quickly than g(n) as n goes to infinity. Big-Theta Notation We say f(n) = Θ(g(n)) if f(n) = O(g(n)) AND f(n) = Ω(g(n)). Intuitively, the function f(n) grows at the same rate as g(n) as n goes to infinity. Little-o We say f(n) = o(g(n)) if for all a > 0, there exists a b such that f(n) < ag(n)+ b for all n. Intuitively, f(n) grows strictly more slowly than g(n). So f(n) = O(g(n)) but not Θ(g(n)). 3. Теоретически закрытые и теоретически открытые задачи Задачи дискретной оптимизации по соответствию доказанной нижней границы сложности и сложностью решающего алгоритма разделяются на закрытые и открытые задачи. Теоретически закрытые задачи Содержат задачи для которых теоретически доказанная нижняя граница fthlim(n) временной сложности растёт с той же скоростью, что и верхняя граница fAmin(n) числа операций, необходимых для получения результата известным алгоритмом: fAmin(n) = (fthlim(n)). Теоретически открытые задачи Содержат задачи для которых верхняя граница fAmin(n) числа операций, необходимых для получения результата известным алгоритмом выше теоретически доказанной нижней границы fthlim(n) временной сложности fAmin(n) > fthlim(n) или эвристически ожидаемой нижней границы ftr(n) временной сложности fAmin(n) > ftr(n). 4. Классификация задач по сложности Класс P составляют задачи, имеющие полиномиальную границу временной сложности и решаемые полиномиальными алгоритмами. Этот класс задач довольно узок. Список характерных представителей этих задач был расширен в 1979 году Хачияном, который предложил полиномиальный алгоритм решения задач линейного программирования, к которым относятся:  Сортировка множества из n чисел.           Поиск эйлерова цикла на графе из n рёбер. Поиск в списке заданного подсписка. Построение покрывающего дерева минимальной стоимости. Поиск кратчайшего пути на графе. Поиск связанных компонент. Транзитивное замыкание. Максимальное паросочетание. Максимальный поток на графе. Проверка планарности графов. Задачи линейного программирования. Класс E содержит задачи, имеющие экспоненциальную границу временной сложности и решаемые экспоненциальными алгоритмами. К этому классу относятся задачи, в которых требуется перебирать все комбинации исходных данных до тех пор, пока не выполнится требуемое условие задачи. Комбинаторный перебор альтернатив в общем случае представляется экспоненциальной функцией f n (где f – константа или полином от n). Таблица 1. – Рост сложности алгоритмов классов P и E Время (сек.) решения на ЭВМ с быстродействием 10 8 Функция (опер/сек) Класс сложности n = 10 n = 20 n = 30 n = 40 n = 50 n = 60 -7 -7 -7 -7 -7 n 10 210 310 410 510 610-7 n2 10-6 410-6 910-6 1,610-5 2,510-5 3,610-5 P n3 10-5 810-5 2,710-4 6,410-4 1,2510-3 2,1610-3 n5 10-3 3,210-2 2,410-1 1 сек. 3,1 сек. 7,8 сек. 2n 10-5 10-2 10 сек. 2,7 мин. 115 дней 365 лет E n -4 6 3 5,910 34 сек. 23 дня 38 веков 210 веков 1011 веков 100 С другой стороны, полиномиальные алгоритмы со сложностью n или 1099  n 2 тоже не могут считаться эффективными. Наряду с этим существуют экспоненциальные алгоритмы, хорошо зарекомендовавшие себя на практике: симплекс-метод Данцига для решения задач линейного программирования, алгоритм ветвей и границ Лэнда и Дойга, который столь успешно решает задачу о рюкзаке, что многие считают эту задачу легкорешаемой. Однако различие между этими двумя классами задач велико и всегда проявляется при больших значениях n. Таблица 2. – Влияние повышения быстродействия ЭВМ на увеличение размерность входных данных решаемой за 1 час задачи Класс P Функция сложности n Быстродействие ЭВМ (опер/сек) 108 1010 1011 N1 100N1 1000N1 E n2 n3 n5 2n 3n N2 N3 N4 N5 N6 10N2 4,64N3 2,5N4 N5+6,64 N6+4,19 31,6N2 10N3 3,98N4 N5+9,97 N6+6,29 Задачи классов P и E являются теоретически закрытыми задачами, так как для них найдены алгоритмы, решающие эти задачи с временной сложностью, равной теоретически доказанной нижней границе сложности. Большинство известных задач, например, оптимизация загрузки ёмкости, решение систем уравнений в целых числах, описывающих задачи гильотинного одномерного раскроя, и т.п. заранее не могут быть отнесены ни к одному из рассмотренных выше классов. В их условиях не содержатся экспоненциальные исчисления, но полиномиальный алгоритм для их решения до сих пор не найден. Для решения подобных задач применяются экспоненциальные алгоритмы. Таким образом, существует обширный класс задач, который теоретически допускает полиномиальную сложность, но пока ещё не имеет эффективного (т.е. полиномиального) алгоритма. Так как задачи, не попадающие ни в класс P, ни в класс E, составляют большинство известных на практике задач и для них теоретически не найдена нижняя граница сложности, то они классифицируются по сложности их решения на семействе машин Тьюринга. Задачи, решаемые за полиномиальное время на недетерминированной машине Тьюринга (НМТ) с бесконечной памятью отнесены к классу NPзадач. Недетерминизм машины Тьюринга основан на наличии команды ВЫБОР(N). Данная команда позволяет “параллельно” проверить N вариантов с помощью N детерминированных машин Тьюринга (ДМТ), для каждого из которых требуется полиномиальное время. Для внешнего наблюдателя создаётся впечатление, что НМТ за полиномиальное время может правильно угадать единственно верный результат из N альтернатив. Однако число вариантов N ничем не ограничено и может представлять собой экспоненциальную функцию от n. Поэтому, для общего случая, НМТ не реализуема на ЭВМ. В классе NP-задач выделена группа NP-полных задач, для которых справедливы следующие утверждения: - Задача решается за полиномиальное время на НМТ. - Любая NP-задача сводится к данной задаче за полиномиальное время. Процедура сводимости означает переформулировку задачи в термины какой-либо известной задачи, для которой алгоритм решения имеется. Хотя теоретическая сложность NPC задач неизвестна, но предполагается, что они, скорее всего, имеют экспоненциальную сложность, ибо усилия первоклассных математиков последних столетий найти полиномиальный алгоритм ни к чему не привели. Существует класс настолько трудных задач, что для них не найдена не только нижняя граница сложности, но и неизвестен полиномиальный алгоритм для НМТ с бесконечной памятью. Такие задачи названы NP-трудными, ибо к ним можно свести NP-полные задачи за полиномиальное время. Отличительной особенностью NP-трудных задач является то, что даже если каким-либо сторонним способом (например, от оракула) получено решение, то его проверка сама по себе является NP-полной задачей. Как правило, в класс NP-трудных задач входят NP-полные задачи в постановке которых присутствует оптимизация целевой функции. Характерным представителем NP-трудной задачи является задача об оптимальном гамильтоновом цикле (задача коммивояжера), требующая определить оптимальный по длине цикл во множестве n! альтернатив (n – число вершин полного графа). Машины Тьюринга с полиномиальной памятью и неограниченным временем работы расширяют число задач, которые возможно классифицировать по сложности их решения. Задачи, решаемые на таких машинах, выделены в класс PS-задач. Для PS-задач теоретическая сложность пока неизвестна. В классе PS-задач выделена группа PS-полных задач, для которых справедливы следующие утверждения: - Задача решается на НМТ с полиномиальной памятью. - Любая PS-задача сводится к данной задаче за полиномиальное время. P E Теоретическ и закрытые задачи PS PS-полная Теретически открытые задачи NP-трудная Полиномиальная Экспоненциальная Экспоненциальная Полиномиальная на НМТ с бесконечной памятью Полиномиальная на НМТ с бесконечной памятью Полиномиальный алгоритм для НМТ с бесконечной памятью не найден Экспоненциальная на НМТ с полиномиальной памятью Экспоненциальная на НМТ с полиномиальной памятью Неизвестна NP NP-полная Полиномиальная Неизвестна (предположительно экспоненциальная) Неизвестна (предположительно экспоненциальная) Неизвестна Неизвестна (предположительно экспоненциальная) Трудность задач Легкорешаемы е Труднорешаемые Таблица 3. – Классификация задач по временной сложности Сложность задачи Сложность алгоритма Класс (теоретическая (практическая эквивалентности сложность) сложность) Хотя теоретическая сложность PS-полных задач неизвестна, но предполагается, что они, скорее всего, имеют экспоненциальную сложность. Сложность O(1) Комментарий Устойчивое время работы не зависит от размера задачи Очень медленный рост необходимого O(log log n) времени Примеры Ожидаемое время поиска в в хештаблице Ожидаемое время работы интерполирующего поиска n элементов O(log n) Логарифмический рост — удвоение размера задачи увеличивает время работы на постоянную величину Вычисление xn; Двоичный поиск в массиве из n элементов O(n) Линейный рост — удвоение размера задачи удвоит и необходимое время Сложение/вычитание чисел из n цифр; Линейный поиск в массиве из n элементов O(n log n) Сортировка слиянием или Линеаритмичный рост — удвоение кучей n элементов; нижняя граница размера задачи увеличит необходимое сортировки время чуть более чем вдвое сопоставлением n элементов O(n²) Квадратичный рост — удвоение размера задачи увеличивает необходимое время в четыре раза O(n³) Кубичный рост — удвоение размера задачи увеличивает необходимое время Обычное умножение матриц в восемь раз O(cn) Экспоненциальный рост — увеличение размера задачи на 1 приводит к cНекоторые задачи коммивояжёра, кратному увеличению необходимого алгоритмы поиска полным времени; удвоение размера задачи перебором увеличивает необходимое время в квадрат Элементарные алгоритмы сортировки ЛР 14. Исследование сложности алгоритмов 1. Дан массив чисел произвольной длины. Найти максимальный и минимальный элементы массива и вывести их на ленту. 2. Даны два массива А и В, разделённые нулём. Массивы не содержат нулей и имеют произвольный и возможно не равный друг другу размер. Найти одну такую пару чисел , и , для которой выполняется условие + и вывести её на ленту. Иначе на ленту вывести 0. 3. Дан массив произвольной длины. Если на ленте он упорядочен по возрастанию, то вывести 1, иначе 0. 4. Оценить эффективность НРАМ по показателю вычислительной сложности на задачах 1-3. Литература 1. Игошин В.И. Математическая логика: учебное пособие / В.И. Игошин – М.: ИНФРА-М, 2019. – 398 с. Режим доступа: https://znanium.com/bookread2.php?book=987006 2. Игошин В.И. Сборник задач по математической логике и теории алгоритмов: учеб. пособие / В.И. Игошин – М.: КУРС: ИНФРА-М, 2019. – 392 с. Режим доступа: https://znanium.com/bookread2.php?book=986940 3. Пруцков А.В., Волкова Л.Л. Математическая логика и теория алгоритмов: учебник / А.В. Пруцков, В.В. Волкова – М.: КУРС: ИНФРА-М, 2018. – 152 с. Режим доступа: https://znanium.com/bookread2.php?book=956763 Марков Виталий Николаевич МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Конспект лекций Кубанский государственный технологический университет 350072, г. Краснодар, ул. Московская, 2