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

Астраханский Государственный Университет Факультет цифровых технологий и кибербезопасности Кафедра Информационной безопасности и цифровых технологий «Математическая логика и теория алгоритмов» Методическое пособие по дисциплине для студентов дневного и заочного отделений Астрахань – 2007 г. УДК 004.056 Составитель: Ажмухамедов И.М., к.т.н., доц. кафедры «Информационная безопасность» Рецензент: д.т.н. Попов Г.А., проф., зав. кафедрой «Информационная безопасность» Настоящие пособие предназначено для методического обеспечения проведения лабораторных и контрольных работ по дисциплине «Математическая логика и теория алгоритмов». Приведены краткие сведения по основам логики высказываний, логики предикатов, формальных аксиоматических теорий и теории алгоритмов. Контрольные задания включают упражнения по всем разделам. Приводятся указания к проведению лабораторных работ. Рекомендуется для студентов дневной и заочной формы обучения специальностей «Комплексное обеспечение информационной безопасности автоматизированных систем», «Автоматизированные системы обработки информации и управления», «Прикладная информатика в экономике». © Астраханский государственный технический университет 2 СОДЕРЖАНИЕ Введение Тема 1. Логика высказываний 1.1. Определение высказывания 1.2. Операции над высказываниями. Алгебра высказываний 1.3. Формулы логики высказываний. Равносильность формул 1.4.Запись сложного высказывания в виде формулы логики высказываний 1.5. Тождественно-истинные и тождественно-ложные формулы. Проблема разрешимости 1.6. Формализация рассуждений. Правильные рассуждения Тема 2. Логика предикатов 2.1. Определение предиката. Кванторы 2.2. Формулы логики предикатов. Равносильность формул 2.3. Приведенные и нормальные формулы 2.4. Выражение суждения в виде формулы логики предикатов 2.5. Интерпретация формулы логики предикатов в виде суждения. Выполнимость. Общезначимость Тема 3. Формальные аксиоматические теории (исчисления) 3.1. Принципы построения формальных теорий 3.2. Исчисление высказываний 3.3. Исчисление предикатов 3.4. Автоматическое доказательство теорем. Метод резолюций. Тема 4. Нечеткая логика 4.1. Нечеткие множества 4.2. Нечеткие высказывания 4.3. Нечеткие предикаты Тема 5 Алгоритмы 5.1. Определение алгоритма 5.2. Машина Тьюринга 5.3. Вычислимые по Тьюрингу функции Указания к выполнению лабораторных работ Контрольные задания Список литературы Краткие сведения о математиках 3 ВВЕДЕНИЕ Логика - одна из самых древних наук. Как самостоятельная наука логика оформилась в трудах греческого ученого Аристотеля (384 – 322 г. до н. э.) и стала впоследствии называться формальной или Аристотелевой логикой. С момента своего возникновения и в течение многих веков логика рассматривалась как часть философии. Математическая логика возникла на стыке двух наук: традиционной или философской логики и математики. Идея построения логики на математической основе была впервые выдвинута Лейбницем (1646 – 1716). Окончательно как раздел математики математическая логика сформировалась в работах Д. Буля (1815 – 1864), Г. Фреге (1848 – 1925), Б. Рассела (1872 – 1970), Д. Гильберта (1862 – 1943). Математическая логика есть логика по предмету, математика по методу. Согласно Г.Фреге математическая логика изучает логику математики путем ее дедуктивной формализации. Логика, в отличие от математики (изучающей количественные отношения и пространственные формы) изучает не количественные отношения между объектами. Вопросы математики: «сколько?», «как далеко?», «как долго?» и т.д. (т.е. вопросы о количественных отношениях). Вопросы логики: «что это значит?». «есть ли противоречие в этом суждении?», «каковы основания этого доказательства?» и т.д. (т.е. вопросы о неколичественных отношениях). Логика подразделяется на четкую логику – логика, в которой для интерпретации высказываний используется множество истинностных значений М, и нечеткую логику – логика, истинностные значения высказывания которой интерпретируются нечетким подмножеством заданного множества значений. Логика называется: классической (двузначной), если |M|=2, Например М={0,1}или М={И, Л}; неклассической (многозначной), если |M|>2; бесконечнозначной, если |M|=N (это т. н. счетнозначные логики) или |M|=D (это т.н. контенуальнозначные логики); вероятностной, если истинностные значения М представляются вероятностями (степенями правдоподобия высказываний); темпоральной (временной), если элементы М зависят от времени; 4 модальной, если алфавит ее языка включает связки, интерпретируемые как “возможно, что…” Формальная система – это уточнение понятия аксиоматической теории, характеризующееся представлением последней в виде исчисления. Исчисление – дедуктивная система, т.е. способ задания того или иного множества путем указанных аксиом и правил вывода, каждое из которых описывает, как строить новые элементы из исходных и уже построенных. Математическая логика используется при решении трех групп задач. Во-первых, это формулировка логических рассуждений с помощью специальных символов и изучение этих рассуждений с использованием математического аппарата. Во-вторых, это построение формальных теорий (исчислений) для различных математических объектов на основе аксиоматического метода. В-третьих, это применение аппарата математической логики к различным областям практической деятельности. В настоящее время математическая логика с успехом применяется в радиотехнике, лингвистике, теории автоматического управления, программировании, системах искусственного интеллекта. 5 ТЕМА 1. ЛОГИКА ВЫСКАЗЫВАНИЙ 1.1. Определение высказывания Определение 1.1. Высказыванием называется повествовательное языковое предложение, относительно которого можно сказать истинно оно или ложно. Пример 1.1. Простые (атомарные) истинные высказывания: Вычислительная система есть программно-аппаратный комплекс. 57=35 Простые (атомарные) ложные высказывания: 3 Волк есть дикая кошка. Предложения, не являющиеся высказываниями: Предложения “Всякая женщина друг человека” и “Земля вращается быстро” не являются истинными, но в тоже время не являются и ложными. Поэтому эти предложения не являются высказываниями в классической логике (очевидно, что первое предложение является бессмысленным, а второе – неопределенноистинным); Предложение Х+7=9 не является высказыванием, а есть высказывательная форма (при указании конкретного значения Х становится высказыванием). Пример 1.2. Сложные высказывания: Волга – самая короткая река России и в ней живут киты; Это высказывание, составленное из двух простых ложных высказываний, является сложным (составными, молекулярными) ложным высказыванием. Метавысказывание – это высказывание, субъект которого указывает на другое высказывание. Пример. Пусть имеем высказывание P(a) , тогда высказывание “ P(a) - ложно ” о высказывании P(a) есть метавысказывание. Очевидно, на основе высказывания P(a) можно построить неограниченное количество метавысказываний различной степени сложности. Так, Например, метевысказыванием будет “высказывание “P(a) - ложно” - истинно”. 6 В логике высказываний нас интересует не суть высказывания, а его истинность или ложность. Мы говорим, что существуют два истинностных значения: истина и ложь (И и Л). Двухэлементное множество {И, Л} есть множество истинностных значений. Высказывания будем обозначать большими буквами: A, B, C, X, Y,.. Выражение А = И означает, что высказывание А истинно, а X = Л означает, что высказывание X ложно. 1.2. Операции над высказываниями. Алгебра высказываний Введем операции над высказываниями так же, как мы это делается для булевых функций. Отрицанием высказывания А называется высказывание А, которое истинно тогда и только тогда, когда высказывание А ложно. Чтобы составить отрицание А достаточно в разговорном языке сказать “неверно, что А”. Пример 1.3. А = “Каспаров – чемпион мира по шахматам”. А = “Неверно, что Каспаров – чемпион мира по шахматам”. Отрицание определяется следующей таблицей истинности (табл. 1.1): Таблица 1.1 А А Л И И Л Конъюнкцией двух высказываний А и B называется высказывание А&B, истинное тогда и только тогда, когда истинны оба высказывания А и B. В разговорной речи конъюнкции соответствует союз “и”. Пример 1.4. А = “Треугольник прямоугольный”. B = “Треугольник равнобедренный”. А&B = “Треугольник прямоугольный и равнобедренный”. Конъюнкция определяется следующей таблицей истинности (табл.1.2): Таблица 1.2 А B А&B Л Л Л Л И Л И Л Л И И И 7 Дизъюнкцией двух высказываний А и B называется высказывание А V B, ложное тогда и только тогда, когда ложны оба высказывания А и B. В разговорной речи конъюнкции соответствует союз “или”. Пример 1.5. А = “Иванов юрист”. B = “Иванов экономист”. АVB = “Иванов юрист или экономист”. Дизъюнкция определяется следующей таблицей истинности (табл.1.3): А Л Л И И Таблица 1.3 B AVB Л Л И И Л И И И Импликацией двух высказываний А и B называется высказывание А  B, ложное тогда и только тогда, когда А истинно, а B ложно. Импликации соответствуют следующие выражения разговорной речи: “А влечет за собой B”; или “из А следует B”; или “если А, то B”. Пример 1.6. А = “Треугольник равносторонний”. B = “В треугольнике все углы равны”. А B = “Если треугольник равносторонний, то все углы равны”. Импликация определяется следующей таблицей истинности (табл.1.4): А Л Л И И B Л И Л И Таблица 1.4 АB И И Л И Импликация играет важную роль в логике высказываний. При учете смыслового содержания высказывания (а не только значений истинности), оборот “если, то” подразумевает причинно-следственную связь. Истинность же импликации означает лишь то, что, если истинна посылка, то истинно и заключение. При ложной посылке заключение всегда истинно. Так, истинными являются следующие импликации: “Если в доме 5 этажей, то Иванов живет в квартире 50”; “Если идет снег, то 2  2 = 5”. 8 Пример 1.7. Рассмотрим четыре высказывания: A = “Дважды два четыре” = И; B = “Дважды два пять” = Л; C = “Снег белый” = И; D – “Снег черный” = Л. Образуем четыре импликации: А C = “Если дважды два четыре, то снег белый” = И И = И; B C = “Если дважды два пять, то снег белый” = Л И = И; А D = “Если дважды два четыре, то снег черный” = И Л = Л; B D = “Если дважды два пять, то снег черный” = Л Л = И. Эквивалентностью двух высказываний А и B называется высказывание А  B, истинное тогда и только тогда, когда оба высказывания А и B одновременно истинны или ложны. Говорят, что А эквивалентно B или A имеет место тогда и только тогда, когда имеет место B. Пример 1.8. А = “Треугольник равнобедренный”. B = “В треугольнике углы при основании равны”. А  B = “Треугольник является равнобедренным тогда и только тогда, когда углы при основании равны”. Эквивалентность (табл.1.5): определяется А Л Л И И следующей B Л И Л И таблицей истинности Таблица 1.5 АB И Л Л И Высказывания вместе с определенными для них операциями образуют алгебру высказываний. 9 1.3. Формулы логики высказываний. Равносильность формул Определение 1.2. Формула логики высказываний определяется индуктивно следующим образом: 1. Любая высказывательная переменная, а также константы И, Л есть формула. 2. Если A и B – формулы, то А, AVB, A&B, АB, АB есть формулы. 3. Ничто, кроме указанного в пунктах 1 – 2, не есть формула. Две формулы называются равносильными, если на всех одинаковых наборах переменных значения этих формул совпадают. Равносильность формул A и B будем обозначать: A  B. Для того, чтобы установить равносильность формул, можно составить таблицы значений для каждой формулы и сравнить их. Для равносильных формул эти таблицы совпадают. Другой способ установления равносильности формул заключается в использовании некоторых установленных равносильностей формул логики высказываний. Все законы равносильности логики булевых функций, справедливы и для формул логики высказываний, причем единице соответствует истинностное значение И, а нулю – Л. Приведем эти законы. Для любых формул A, B, C справедливы следующие равносильности: 1. Коммутативность. а) A&B  B&A (для конъюнкции); б) AVB  BVA (для дизъюнкции). 2. Ассоциативность. а) A&(B&C)  (A&C)&C (для конъюнкции); б) AV(BVC)  (AVB)VC (для дизъюнкции). 3. Дистрибутивность. а) A&(BVC)  A&BVA&C (для конъюнкции относительно дизъюнкции); б) AV(B&C)  (AVB)&(AVC) (для дизъюнкции относительно конъюнкции). 4. Закон де Моргана. а) (A&B) AVB (отрицание конъюнкции есть дизъюнкция отрицаний); б) (AVB)  A&B (отрицание дизъюнкции есть конъюнкция отрицаний). 10 5. Идемпотентность. а) A&A  A (для конъюнкции); б) AVA  A (для дизъюнкции). 6. Поглощение. а) A&(AVB)  A (1– ый закон поглощения); б) AVA&B  A (2– ой закон поглощения). 7. Расщепление (склеивание). а)A&B V A&(B)  A (1–ый закон расщепления); б) (AVB) & (AVB)  A (2–ой закон расщепления). 8. Двойное отрицание. (A)  A. 9. Свойства констант. а)A&И  A; б) A&Л  Л; в)AVИ  И; г) AVЛ  A; д) Л И; е) И Л. 10. Закон противоречия. A&A  Л. 11. Закон “исключенного третьего”. AVA  И. 12. AB AVB (A&B). 13. AB  (AB)&(BA)  (A&B) V (A&B)  (АVB)&(AVB). Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа “”. Справедливы также обобщенные законы дистрибутивности и обобщенные законы де Моргана: 14.(A1VA2V...VAn)&(B1VB2V...VBm) A1&B1VA1&B2V...VA1&BmV...VAn&B1VAn&B2V...VAn&Bm. 15.(A1&A2&...&An)V(B1&B2&...&Bm) (A1VB1)&(A1VB2)&...&(A1VBm)&...&(AnVB1)&(AnVB2)&...&(AnVBm). 16. (A1&A2&...&An) A1VA2V...VAn. 17. (A1VA2V...VAn) A1&A2&...&An В равносильностях 1 – 17 в качестве A, B, Ai, Bi могут быть подставлены любые формулы и, в частности, переменные. 11 Пример 1.9. Доказать равносильность формул логики высказываний: (АB) & (A V B)  B. Преобразуем левую часть, последовательно используя равносильности 12, 14, 10, 5а, 9г, 6б: (АB) & (A V B) А V B) & (A V B) А&A V А&B V B&А V B&B А&B V B&А V B  B. Равносильность доказана. 1.4. Запись сложного высказывания в виде формулы логики высказываний Если имеется несколько высказываний, то при помощи логических операций можно образовывать различные новые высказывания. При этом исходные высказывания принято называть простыми, а вновь образованные высказывания – сложными. Пример 1.10. Рассмотрим простые высказывания:. A = "Будет холодное лето". B = "Будет дождливое лето". C = "Будет засушливое лето". D = "Будет хороший урожай". Формула (A&B V C)  D соответствует сложному высказыванию: ''Если будет холодное и дождливое или засушливое лето, урожай будет плохим". Язык логики высказываний удобен для записи математических утверждений. Всякая теорема имеет вид импликации: АB (прямая теорема); BА (обратная теорема); B  А (противоположная теорема). Пример 1.11. A = “Треугольник прямоугольный”. B = “Квадрат одной стороны равен сумме квадратов двух других сторон” А  B (прямая теорема) = “Если треугольник прямоугольный, то квадрат одной стороны равен сумме квадратов двух других сторон”. B  А (обратная теорема) = “Если квадрат одной стороны равен сумме квадратов двух других сторон, то треугольник прямоугольный”. 12 B   А (противоположная теорема) = “Если квадрат одной стороны не равен сумме квадратов двух других сторон, то треугольник не прямоугольный”. В данном случае все три теоремы верны. Равносильность А  B  B  А есть основание метода доказательства от противного. Например, для доказательства теоремы: “Если треугольник равнобедренный, то углы при основании равны” (А  B) достаточно доказать теорему: “Если углы при основании не равны, то треугольник не равнобедренный” (B  А). Используя равносильные преобразования, можно получать различные формулировки одного и того же суждения, а также отрицаний суждений. Пример 1.12. Дано высказывание “Если политик обещает невыполнимое, то он обманывает людей”: а) записать его в виде формулы логики высказываний; б) произвести отрицание данного высказывания, так, чтобы результат не содержал внешних знаков отрицания; полученную при этом формулу записать на естественном языке. Введем следующие высказывания: A = ”Политик обещает невыполнимое”. B = “Политик обманывает людей”. Данное нам высказывание может быть записано в виде формулы: АB. Построим отрицание высказывания, воспользовавшись равносильностью 12: (АB) A&B. На естественном языке это может быть выражено следующим образом: “Политик обещает невыполнимое, но он не обманывает людей”. 13 1.5. Тождественно-истинные и тождественно-ложные формулы. Проблема разрешимости Определение 1.3. Формула называется тождественно-истинной (тавтологией), если для любых наборов переменных она принимает значение И (истина). Определение 1.4. Формула называется тождественно-ложной, если для любых наборов переменных она принимает значение Л (ложь). Определение 1.5. Формула называется выполнимой, если для некоторых наборов переменных она принимает значение И. Проблема разрешимости для логики высказываний заключается в том, чтобы установить, является ли произвольная формула тождественно-истинной. Теорема 1.1. Формула является тождественно-истинной тогда и только тогда, когда в ее КНФ в каждую из элементарных дизъюнкций одновременно входят какая-либо переменная и ее отрицание. Теорема 1.2. Формула является тождественно-ложной тогда и только тогда, когда в ее ДНФ в каждую из элементарных конъюнкций одновременно входят какая-либо переменная и ее отрицание. Следовательно, приведя формулу равносильными преобразованиями к КНФ, можно установить, является ли она тождественно-истинной, а приведя ее к ДНФ, можно установить, является ли она тождественно-ложной. Пример 1.13. Доказать, что формула F = (АB) ((C V А) (C V B)) является тождественно-истинной. Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ: (АB) ((CVА) (CVB)) (АB)V ((CVА) (CVB)) (А&B) V (CVА) V (CV B) (А&B) V (C&А) V (CVB)  (А VC)& (АV А) &(BVC) &(B VА) V (CVB) (АVC)&(BVC)&(BVА)V(CVB) (АVCVCVB)&(BVCVCVB)&(BVАVCVB). В первую дизъюнкцию входят C и C. Во вторую – B и B, C и C. в третью – B и B. Следовательно, на основании теоремы 1.1 можно утверждать, что исходная формула является тождественноистинной. 14 Так как всякой формуле соответствует таблица истинности, то тождественная истинность или тождественная ложность формулы может быть установлена двумя путями: 1) приведением с помощью равносильных преобразований к КНФ или ДНФ; 2) составлением таблицы истинности. Пример 1.14. Установить, является ли тождественно-истинной данная формула логики высказываний: f(A, B) = (А&(АB))  B. 1) Последовательно применяя равносильные преобразования, приведем нашу формулу к КНФ: (А&(АB))B(А&(АVB)B(А&(АVB)BАV((АVB)VB АV(А&B)VB (АVB)VА&B (АVBVА)&(АVBVB). В первую дизъюнкцию входят A и A. Во вторую – B и B, поэтому формула является тождественно истинной, f(A, B)  И. 2) Составим таблицу истинности f (A, B) (таблица 1.6): А Л Л И И B АB Л И И И Л Л И И А&(АB) Л Л Л И Таблица 1.6 (А&(АB))B И И И И Из таблицы 1.6 видно, что f(A, B)  И. 1.6.Формализация рассуждений. Правильные рассуждения Рассуждение – это построение нового высказывания D на основании уже имеющихся высказываний P1, P2, ... , Pn. Высказывания P1, P2, ... , Pn называются посылками, а высказывание D – заключением. Определение 1.6. Рассуждение называется правильным, если из конъюнкции посылок следует заключение, т. е. формула P1& P2& ... & Pn  D тождественно-истинна. Таким образом, если все посылки истинны (т. е. их конъюнкция равна И), то истинное заключение соответствует правильному рассуждению, а ложное заключение – неправильному. При ложности хотя бы одной из посылок независимо от истинностного значения заключения рассуждение будет правильным. 15 Схематически рассуждение изображается следующим образом: P1, P2, ... , Pn D Пример 1.15. Проверить правильность следующих рассуждений: а) “Если книга сложная, то она неинтересная. Эта книга интересная. Значит, она несложная”. Введем высказывания: А = “Книга сложная”; B = “Книга интересная”. Схема рассуждения имеет вид: А  B, B А Докажем, что формула ((А  B) & B) А является тождественно-истинной. Приведем эту формулу к КНФ и воспользуемся теоремой 1.1: ((А  B)&B)  А ((А  B)& B) V A  (A & B) V BV A   (А VB V A)&(AV B V B)  И. Значит, рассуждение правильное. б) “Если будет хорошая погода, я пойду гулять. Если будет плохая погода, я буду читать книгу. Погода будет хорошая. Следовательно, я не буду читать книгу”. Введем высказывания: А = “Будет хорошая погода”; B = “Я пойду гулять”. C = “Я буду читать книгу”. Схема рассуждения имеет вид: А  B, A  С, A. С Найдем КНФ формулы ((А  B) & (A  С) & A)  C: ((А  B) & (A  С) & A) C ((А  B) & (A  С) & A)VC (А  B) V (A  С) VA) V C А & B V A & С VA VC А & B V A VC (А V A VC) & (B V A VC)  B V A VC. Полученная КНФ нашей формулы не содержит одновременно какой-либо переменной и ее отрицания. Следовательно, формула не является тождественно-истинной, а рассуждение не является правильным. 16 Контрольные вопросы к теме 1 1. Как называется сложное высказывание, а) истинное тогда и только тогда, когда все составляющие его простые высказывания истинны? б) истинное тогда и только тогда, когда составляющие его простые высказывания либо вместе истинны, либо вместе ложны? в) истинное тогда и только тогда, когда истинно хотя бы одно из составляющих его простых высказываний? г) ложное тогда и только тогда, когда первое простое высказывание истинно, а второе ложно? Варианты ответа: 1 – дизъюнкция; 2 – конъюнкция; 3 – импликация; 4 – эквивалентность. 2. Какое из следующих утверждений верно: а) Рассуждение является правильным, если из заключения следует конъюнкция посылок. б) Рассуждение является правильным, если из конъюнкции посылок следует заключение. в) Рассуждение является правильным, если конъюнкция посылок и заключения является тождественно-истинной формулой. 3. Какие из следующих утверждений верны: а) Формула является тождественно-истинной тогда и только тогда, когда в ее КНФ в любую элементарную дизъюнкцию одновременно входят какая-либо переменная и ее отрицание. б) Формула является тождественно-истинной тогда и только тогда, когда в ее ДНФ в любую элементарную конъюнкцию одновременно входят какая-либо переменная и ее отрицание. в) Формула является тождественно-ложной тогда и только тогда, когда в ее КНФ в любую элементарную дизъюнкцию одновременно входят какая-либо переменная и ее отрицание. г) Формула является тождественно-ложной тогда и только тогда, когда в ее ДНФ в любую элементарную конъюнкцию одновременно входят какая-либо переменная и ее отрицание. 17 ТЕМА 2. ЛОГИКА ПРЕДИКАТОВ 2.1. Определение предиката. Кванторы Определение 2.1. Предикатом P(x1, x2, ... , xn) называется функция, аргументы которой определены на некотором множестве М, x1, x2, ... , xn  M, а сама она принимает два значения: И (истина) и Л (ложь). Таким образом, предикат осуществляет отображение М  {И, Л}. Переменные x1, x2, ... , xn называются предметными переменными, а множество M – предметной областью. Если все переменные x1, x2, ... , xn принимают конкретные значения, то предикат есть не что иное, как высказывание, Таким образом, высказывание является частным случаем предиката. Можно сказать, что предикат есть высказывание, зависящее от параметров. Пример 2.1. а) P(x) = “x – четное число”. Здесь М – множество целых чисел, x M. б) A(x, y, z) = “x, y, z лежат на одной окружности”. Здесь М – множество точек плоскости, x, y, z M в) B(x, y) = “x старше y”. Здесь M – множество людей, x, y  M. Предикат от n переменных называется n-местным предикатом. Высказывание есть 0-местный предикат. Как видно из примера 2.1, одноместный предикат отражает свойство некоторого объекта, а многоместный предикат выражает отношение между многими объектами. Над предикатами можно производить обычные логические операции и получать при этом другие предикаты. Таким образом, можно говорить об алгебре предикатов. Пример 2.2. Пусть A(x) – предикат “x делится на 3”, а B(x) – предикат “x делится на 2”. Тогда A(x) V B(x) – предикат “x делится на 3 или на 2”, а A(x) & B(x) – предикат “x делится на 3 и на 2”. Кроме операций логики высказываний, в логике предикатов используются особые логические символы – кванторы (были введены немецким математиком Г. Фреге). 18 Квантор общности. Пусть P(x) – некоторый предикат, определенный для каждого x  М. Тогда выражение xP(x) является истинным высказыванием, если P(x) истинно для всякого x  М и ложным в противном случае. Символ x называется квантором общности. Выражение xP(x) читается: “Для всех x имеет место P(x)”. В обычной речи квантору общности соответствуют слова: все, всякий, каждый, любой. Возможно отрицание квантора общности: xP(x): “Не для всех x имеет место P(x)”. Пример 2.3. Пусть P(x) – предикат “x – четное число”. Тогда xP(x) есть высказывание “Всякое x – четное число" = “Все числа – четные", которое истинно на множестве M четных чисел и ложно, если М содержит хотя бы одно нечетное число, Например, если M – множество целых чисел. Отрицание xP(x) есть высказывание “Не всякое x – четное число" = “Не все числа – четные", которое истинно на множестве целых чисел и ложно на множестве четных чисел. Квантор существования. Пусть P(x) – некоторый предикат, x  М. Тогда выражение xP(x) является истинным высказыванием, если P(x) истинно хотя бы для одного x  М и ложным в противном случае. Символ x называется квантором существования. Выражение xP(x) читается: “Существует x, для которого имеет место P(x)”. В обычной речи квантору существования соответствуют слова: некоторый, несколько. Возможно отрицание квантора существования: xP(x): “Не существует x, для которого имеет место P(x)”. Кванторы существования и общности называются двойственными кванторами. Пример 2.4. Пусть, как и в примере 2.3, P(x) – предикат “x – четное число”. Тогда xP(x) есть высказывание “Некоторые x – четные числа” = “Существуют четные числа”, которое истинно на множестве M, содержащем хотя бы одно четное число и ложно, если М содержит только нечетные числа. Высказывание xP(x) = “Неверно, что некоторые x – четные числа” = “Не существует четных чисел” истинно на множестве M, содержащем только нечетные числа и ложно, если М содержит хотя бы одно четное число. 19 Буква x, стоящая справа от квантора, называется кванторной переменной и должна присутствовать обязательно. Переменная, стоящая под знаком квантора, называется также связанной переменной. Несвязанная переменная называется свободной. Выражения xP(x) и xP(x) не зависят от x и имеют вполне определенные значения. Поэтому переименование связанной переменной, т. е. переход, например, от выражения xP(x) к yP(y) не меняет его истинностного значения. Кванторы могут применяться и к многоместным предикатам. При этом число свободных переменных уменьшается на единицу. Одноместный предикат при связывании переменной квантором становится 0-местным предикатом, т. е. высказыванием. 2.2. Формулы логики предикатов. Равносильность формул Определение 2.2. Формула логики предикатов определяется индуктивно следующим образом: 1. Любая формула логики высказываний есть формула логики предикатов. К новым формулам логики предикатов относятся следующие выражения: 2. Предметные переменные x, y, z, ... есть формулы. 3. Предикаты P(x), Q(x, y), ... , а также выражения с кванторами xP(x), xR(x), xyQ(x, y),... есть формулы. 4. Если A и B – формулы, то A, AVB, A&B, AB, AB есть формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными. 5. Ничто, кроме указанного в пунктах 1 – 4, не есть формула. Пусть A – формула, содержащая свободную переменную x. Тогда xA, xA – формулы, причем в первом случае A является областью действия квантора общности, а во втором – областью действия квантора существования. Пример 2.5. 1. Следующие выражения являются предикатов: а) A & B C, где A, B, C – высказывания. б) xyQ(x, y, z) & xyP(x, y, u). формулами логики 20 Проанализируем последовательно это выражение. Предикат Q(x, y, z) – формула; Выражение xyQ(x, y, z) – формула; переменные x, y – связанные, переменная z – свободная. Предикат P(x, y, u) – формула. Выражение xyP(x, y, u) – формула; переменные x, y – связанные, переменная u – свободная. Выражение xyQ(x, y, z) & xyP(x, y, u) – формула; переменные x, y – связанные, переменные z, u – свободные. 2. Выражение xyP(x, y, z) Q(x, y, z) формулой не является. Действительно, выражение xyP(x, y, z) есть формула, в которой переменные x и y связанные, а переменная z свободная. Выражение Q(x, y, z) также формула, но в ней все переменные x, y, z свободные. Определение 2.3. Формулы F и G, определенные на некотором множестве М, называются равносильными на этом множестве, если при любых подстановках констант вместо переменных они принимают одинаковые значения. Определение 2.4. Формулы, равносильные на любых множествах, будем называть просто равносильными. Переход от одних формул к равносильным им другим формулам логики предикатов может быть произведен по следующим правилам: 1. Все равносильности, имеющие место для логики высказываний, переносятся на логику предикатов. Пример 2.6. а) x(A(x) yB(y))x(A(x) V yB(y)). б) xA(x) (B(z) xC(x)) (xA(x)) V B(z) V xC(x). в) (xA(x) yB(y))C(z)  (xA(x)  yB(y)) V C(z)  ((xA(x)) V yB(y) V C(z)xA(x) & (yB(y)) V C(z). 2. Перенос квантора через отрицание. Пусть A – формула, содержащая свободную переменную x. Тогда (xA(x)x(A(x)). (2.1) (xA(x))x(A(x)). (2.2) Правило переноса квантора через знак отрицания можно сформулировать так: знак отрицания можно ввести под знак квантора, заменив квантор на двойственный. Справедливость равносильностей (2.1) и (2.2) вытекает из смысла кванторов. 21 Так, левая часть (2.1) может быть прочитана следующим образом: “Неверно, что для всякого x имеет место A(x). В правой же части (2.1) утверждается: “Существует x, для которого A(x) не имеет места”. Очевидно, что оба утверждения одинаковы. В левой и правой частях (2.2) соответственно содержатся одинаковые утверждения: “Неверно, что существует x, для которого имеет место A(x)” и “Для всех x не имеет места A(х)”. Пользуясь равносильностями (2.1) и (2.2), а также равносильностями логики высказываний, можно для каждой формулы найти такую равносильную ей формулу, в которой знаки отрицания относятся к элементарным высказываниям и элементарным предикатам. Пример 2.7. (x(A(x) yB(y)) (x(A(x) V yB(y)) x((A(x) V yB(y))) x(A(x) & yB(y)) x(A(x) & yB(y)). 3. Вынос квантора за скобки. Пусть формула A(x) содержит переменную x, а формула B не содержит переменной x, и все переменные, связанные в одной формуле, связаны в другой. Тогда xA(x)VBx(A(x)VB). xA(x)&Bx(A(x)&B). xA(x)VBx(A(x)VB). xA(x)&Bx(A(x)&B). (2.3) (2.4) (2.5) (2.6) Докажем формулу (2.3). Пусть формула xA(x) V B истинна на некотором множестве изменения переменных М и при некоторых фиксированных значениях свободных переменных. Тогда либо формула xA(x), либо формула B истинна. Если истинна формула xA(x), то формула A(х) истинна для всякого х, принадлежащего М и, следовательно, формула A(x) V B тоже истинна для всякого х из М. Но тогда истинна формула x(A(x)VB). Если формула xA(x)VB ложна, то ложны формулы xA(x) и B. Следовательно, так как B не зависит от х, для всякого хМ формула A(x) V B ложна. Но тогда ложна формула x(A(x) V B). Равносильности (2.4) – (2.6) доказываются аналогично. 22 4. Дистрибутивность квантора общности относительно конъюнкции и квантора существования относительно дизъюнкции. Пусть формула B, так же, как и формула A, зависит от х. Тогда xA(x) & xB(x)x(A(x) & B(x)). (2.7) xA(x) V xB(x)x(A(x) V B(x)). (2.8) Докажем (2.7). Пусть правая часть (2.7) истинна, т. е. x(A(x)&B(x))= И. Тогда для любого х0М истинно значение A(x0) & B(x0). Поэтому значения A(x0) и B(x0) одновременно истинны для любого х0. Следовательно, истинна формула xA(x) & xB(x). Если же правая часть (2.7) ложна, то для некоторого х0М либо значение A(x0), либо значение B(x0) ложно. Значит, ложно либоxA(x0), либоxB(x0). Следовательно, xA(x) & xB(x) ложно. Равносильность (2.8) доказывается аналогично. Дистрибутивные законы для квантора общности относительно дизъюнкции и квантора существования относительно конъюнкции, вообще говоря, не имеют места, т. е. формулы xA(x)VxB(x) и x(A(x) V B(x)), а также xA(x) & xB(x) и x(A(x) & B(x)) не являются равносильными, хотя они могут быть равносильными на некоторых множествах М. Пример 2.8. Показать, что формулы x(A(x) V B(x)) и xA(x) V xB(x)) не равносильны. Пусть М – множество натуральных чисел, A(х) = “х – четное число”, B(х) = “х – нечетное число”. Тогда x(A(x) V B(x)) = “Всякое натуральное число четное или нечетное” = И. xA(x) = “Всякое натуральное число – четное” = Л, xB(x) = “Всякое натуральное число–нечетное”=Л, xA(x)VxB(x)=“Всякое натуральное число четное или всякое натуральное число нечетное”=Л, т. е. формулы x(A(x) V B(x)) и xA(x) V xB(x) не равносильны. Пример 2.9. Показать, что формулы x(A(x) & B(x)) и xA(x) & xB(x) не равносильны. Пусть A(х) = “У х голубые глаза”, B(х) = “У х черные глаза”. Тогда x(A(x) & B(x)) = “У некоторых голубые и черные глаза” = Л, xA(x) = “У некоторых голубые глаза” = И, xB(x) = “У некоторых черные глаза” = И, xA(x)&xB(x)=“У некоторых голубые, и у некоторых черные глаза” = И, т. е. формулы x(A(x) & B(x)) и xA(x) & xB(x) не равносильны. 23 5. Перестановка одноименных кванторов. xyA(x,y)yxA(x,y). xyA(x,y)yxA(x,y). (2.9) (2.10) Разноименные кванторы переставлять, вообще говоря, нельзя. Пример 2.10. Пусть М – множество натуральных чисел, A(x, y) = “x > y”. а) xyA(x, y) = “Для всех x и y имеет место x > y” = Л; yxA(x, y) = “Для всех у и х имеет место х > y” = Л; xyA(x, y) yxA(x, y). б) xyA(x, y) = “Существуют такие х и у, что х > y” = И; yxA(x, y) = “Существуют такие y и x, что х > y” = И; xyA(x, y) yxA(x, y). в)xyA(x,y)=“Существует такое х, что для любого у имеет место x > y” = Л (утверждается существование максимального числа на множестве натуральных чисел); yxA(x, y) = “Для всякого y существует такое х, что x > y” = И; xyA(x, y)  yxA(x, y). г) A(х, у) = “Книгу х читал человек у”. xyA(x, y) = “Каждую книгу читал кто-нибудь” = И (например, автор книги читал свою книгу); yxA(x, y) = “Существует человек, который читал все книги” = Л; xyA(x, y) yxA(x, y). 6. Переименование связанных переменных. Заменяя связанную переменную формулы A другой переменной, не входящей в эту формулу, всюду: в кванторе и в области действия квантора, получим формулу, равносильную A. Пример 2.11. A = xF(x)  xG(x). Заменяя связанную переменную x на y в первом члене импликации и на z во втором, получим равносильную формулу: B = yF(y)  zG(z). A B. 24 7. В п. 4. была доказана дистрибутивность квантора общности относительно конъюнкции и квантора существования относительно дизъюнкции (тождества (2.7) и (2.8)). Этот факт означает, что в вышеуказанных случаях соответствующие кванторы могут быть вынесены за скобки и помещены впереди формулы, что и демонстрируют тождества (2.7) и (2.8). Рассмотрим теперь случай, когда закон дистрибутивности, вообще говоря не применим. Сначала рассмотрим формулу xA(x) V xB(x) и применим правило переименования переменных. Получим xA(x)VxB(x)xA(x)VyB(y). (2.11) Так как yB(y) не зависит от x, справедлива равносильность (2.3), причем B = yB(y). Поэтому в соответствии с (2.3) можно вынести за скобки x: xA(x)VyB(y)x(A(x)VyB(y)). (2.12) Так как A(x) не зависит от y, справедлива равносильность (2.3), причем на этот раз B = A(x). Поэтому в соответствии с (2.3) можно вынести за скобки y : A(x)VyB(y)y(A(x)VB(y)) (2.13) Учитывая (2.11), (2.12), (2.13), получим: xA(x)VxB(x)xy(A(x)VB(y)). (2.14) Таким образом за скобки выносятся два квантора x и y, а выражение в скобках не содержит знаков квантора. Проведем аналогичные выкладки для формулы xA(x) & xB(x): xA(x)&xB(x)xA(x)&yB(y)x(A(x)&yB(y))xy(A(x)&B(y)). (2.15) Аналогично можно доказать следующие равносильности: xA(x)VxB(x)xy(A(x)VB(y)). (2.16) xA(x)&xB(x)xy(A(x)&B(y)). (2.17) 25 2.3. Приведенные и нормальные формулы Определение 2.5. Формулы, в которых из логических символов имеются только символы &, V и , причем символ  встречается лишь перед символами предикатов, называются приведенными формулами. Пример 2.12. 1. A(x)&B(x, y). 2. xA(x) V xB(x, y). 3. (A(x)&B(x, y)). 4. xA(x)  xB(x, y). 5. (xA(x)  xB(x, y)). Первые две формулы в соответствии с определением являются приведенными, остальные не являются приведенными. В третьей формуле знак отрицания стоит перед формулой, а не перед символами предикатов. В четвертой формуле используется недопустимый для приведенной формулы символ импликации . В пятой формуле знак отрицания стоит перед формулой и используется недопустимый для приведенной формулы символ импликации. Теорема 2.1. Для каждой формулы существует равносильная ей приведенная формула, причем множества свободных и связанных переменных этих формул совпадают. Действительно, пользуясь равносильностями логики высказываний, можно получить формулу, содержащую только символы &, V и Применяя затем правило переноса квантора через знак отрицания, можно получить равносильную приведенную формулу. Такая приведенная формула называется приведенной формулой данной формулы. Строгое доказательство теоремы 2.1 содержится, например, в [6]. Пример 2.13. Рассмотрим третью, четвертую и пятую формулы примера 2.12 и получим для них приведенные формулы. Для третьей формулы по закону де Моргана:  (A(x)&B(x, y)) A(x) V B(x, y). Для четвертой формулы: xA(x)  xB(x, y) xA(x) V xB(x, y) xA(x) V xB(x, y). Для пятой формулы: (xA(x)  xB(x, y))  (xA(x) V xB(x, y)) (xA(x)) & (xB(x, y)) xA(x) & xB(x, y). 26 Определение 2.6. Приведенная формула называется нормальной, если она не содержит символов кванторов или все символы кванторов стоят впереди. Пример 2.14. 1.xy(A(x) V B(x, y)) – нормальная формула. 2.x(A(x))&yB(x, y) – приведенная формула, не являющаяся нормальной. Теорема 2.2. Для каждой приведенной формулы существует равносильная ей нормальная формула. Строгое доказательство теоремы 2.2 приведено в [6]. Алгоритм, позволяющий из приведенной формулы получить равносильную ей нормальную формулу, основан на правиле переименования связанных переменных и использовании равносильностей (2.3) – (2.8), (2.14) и (2.17). Пусть Q – любой из кванторов , . Воспользуемся равносильными преобразованиями (см.предыдущий раздел): QxA(x)VBQx(A(x)VB) (2.18) QxA(x)&BQx(A(x)&B). (2.19) В тождествах (2.18), (2.19) формула B не зависит от x. Q1xA(x)&Q2xB(x)Q1xQ2z(A(x)&B(z)) (2.20) Q1xA(x)VQ2xB(x)Q1xQ2z(A(x)VB(z)) (2.21) Тождества (2.18) и (2.19) есть обобщенная запись равносильных преобразований (2.3) – (2.6), а тождества (2.20) и (2.21) обобщают равносильности (2.14) – (2.17). Мы видим, что тождества (2.18) – (2.21) позволяют поместить кванторы впереди формулы, что и требуется для нормальной формулы. Пример 2.15. Найти равносильную нормальную формулу для приведенной формулы: xyA(x, y) & xu(x, u). В формуле yA(x, y) переменная y связана, поэтому yA(x, y) не зависит от y. Обозначим D(x) = yA(x, y). В формуле uB(x, u) переменная u связана, поэтому uB(x, u) не зависит от u . Обозначим F(x) = uB(x, u). Тогда xyA(x,y)&xuB(x,u) = xD(x) & xF(x). (2.22) Применим равносильность (2.20), имея в виду, что Q1x есть x, а Q2x есть x. Получим xD(x)&xF(x)xz(D(x)&F(z)). (2.23) 27 Рассмотрим формулу D(x)&F(z) = yA(x, y)&uB(z, u). Применив два раза равносильность (2.19), получим yA(x,y)&uB(z,u) y(A(x,y)&uB(z,u)yu(A(x,y)&B(z,u)). (2.24) Учитывая (2.22), (2.23), (2.24), получим окончательно xyA(x,y)&xuB(x,u)xzyu(A(x,y)&B(z,u)). (2.25) В тождестве (2.25) в левой части – исходная формула, а в правой части ее нормальная формула. Теорема 2.3. Для каждой формулы существует равносильная ей нормальная формула. Теорема 2.3. является очевидным следствием теорем 2.1 и 2.2. Пример 2.16. Найти равносильную нормальную формулу для формулы: xyA(x, y)  xuB(x, u). 1. Найдем вначале приведенную формулу, равносильную данной. Избавимся от символа “” xyA(x, y)  xu(x, u)  (xyA(x, y)) V xuB(x, u). Применим равносильности (2.1) и (2.2) (перенос квантора через отрицание): (xyA(x, y)) xyA(x, y), Следовательно, xyA(x,y)xuB(x,u)xyA(x,y)VxuB(x,u). (2.26) Правая часть тождества (2.26) – приведенная формула, равносильная данной. 2. Найдем теперь нормальную формулу, равносильную приведенной формуле xyA(x, y) V xuB(x, u). Проделаем преобразование этой формулы, аналогично предыдущему примеру: xyA(x, y) V xuB(x, u)xyA(x, y) V zuB(z, u) xz(yA(x,y)VuB(z,u)) xzyu(A(x,y)VB(z,u)). (2.27) В правой части (2.27) – нормальная формула, равносильная исходной. 28 2.4. Выражение суждения в виде формулы логики предикатов Существуют две задачи, определяющие связь между суждениями и формулами логики предикатов: 1) выражение суждения в виде формулы логики предикатов; 2) интерпретация формулы логики предикатов. Рассмотрим первую задачу. Суждение – это мысль, в которой утверждается наличие или отсутствие свойств предметов, отношений между предметами. Простым суждением назовем суждение, в котором нельзя выделить часть, в свою очередь являющуюся суждением. Среди простых суждений выделяют атрибутивные суждения и суждения об отношениях. В атрибутивных суждениях выражается наличие или отсутствие у предметов некоторых свойств. Например, "Иванов - спортсмен", "Все сладкоежки любят конфеты", "Ни один студент нашей группы не знает испанский язык", "Некоторые океаны имеют пресную воду". Все атрибутивные суждения можно разделить на следующие типы: "a есть P", "Все S есть P", "Ни один S не есть P", "Некоторые S есть P", "Некоторые S не есть P". Эти суждения следующим образом переводятся на язык логики предикатов: "a есть P" – P(a); "Все S есть P" – x(S(x)  P(x)); "Ни один S не есть P" – x(S(x)  P(x)); "Некоторые S есть P" – x(S(x) & P(x)); "Некоторые S не есть P" – x(A(x) & P(x)). Полезно понять и запомнить следующее правило: если кванторная переменная связана квантором общности (), то в формуле используется знак импликации (), а если кванторная переменная связана квантором существования (), то в формуле используется знак конъюнкции (&). Пример 2.17. Перевести на язык логики предикатов следующие суждения: а) Веста – собака. Заменим имя "Веста" символом "в" и введем предикат P(x) = "x – собака". Наше суждение можно выразить формулой: P(в). б) Всякая логическая функция может быть задана таблицей. 29 Введем предикаты S(x) = "x – логическая функция"; P(x) = "x может быть задана таблицей". Наше суждение можно выразить формулой: x(S(x)  P(x)). в) Ни один народ не хочет войны. Введем предикаты S(x) = "x – народ"; P(x) = "x хочет войны". Наше суждение можно выразить формулой: x(S(x)  P(x)). г) Некоторые журналисты были в космосе. Введем предикаты S(x) = "x – журналист"; P(x) = "x был в космосе". Наше суждение можно выразить формулой: x(S(x) & P(x)). д) Некоторые современники динозавров не вымерли. Введем предикаты S(x) = "x – современник динозавров"; P(x) = "x вымер". Наше суждение можно выразить формулой: x(A(x) & P(x)). Суждения об отношениях выражают отношения между двумя, тремя и т.д. объектами. При переводе этих суждений в формулы используют многоместные предикаты и правила, рассмотренные выше. При переводе отрицаний суждений на язык формул применяется правило переноса квантора через знак отрицания и другие равносильные преобразования. Пример 2.18. Суждение “Некоторые студенты сдали все экзамены” записать в виде формулы логики предикатов. Построить отрицание данного суждения в виде формулы, не содержащей внешних знаков отрицания. Перевести на естественный язык. Введем предикаты: A(x) = “x – студент”; B(y) = “y – экзамен”, C(x, y) = “x сдал экзамен y”. Тогда предложение “Некоторые студенты сдали все экзамены” можно записать в виде следующей формулы: xy (A(x)&B(y)  C(x, y)). Построим отрицание этой формулы, применяя равносильные преобразования: xy(A(x)&B(y)C(x,y)))xy((A(x)&B(y)C(x,y)) xy(A(x)&B(y)& C(x, y)). Это предложение можно прочитать следующим образом: “Каждый студент не сдал хотя бы один экзамен”. Язык логики предикатов удобен для записи математических предложений: определений, теорем, необходимых и достаточных условий (см., например, [5]). 30 Пример 2.19. Записать на языке логики предикатов следующее определение предела числовой последовательности: "Число a является пределом числовой последовательности {an}, если для любого положительного числа  существует такой номер n0, что для всех натуральных чисел n, больших или равных n0, справедливо неравенство: |an - a| < ". Введем предикаты: P() = " > 0"; Q(n) = "n – натуральное число"; R(n, n0) = "n  n0"; S(n, ) = "|an - a| < ". Определение предела последовательности может быть записано следующей формулой: n0n(P()&Q(n)&Q(n0)&R(n, n0)  S(n, )). Пример 2.20. Записать в виде формулы логики предикатов великую теорему Ферма (была доказана в 1996 г. Э. Вайлсом (Andrew Wiles)): «Для любого целого n > 2 не существует натуральных чисел x, y, z, удовлетворяющих равенству: xn+yn = zn». Введем предикаты: N(x) = "x – натуральное число"; M(x) = "x > 2"; P(x, y, z, n) = "xn + yn = zn". Для любых чисел x, y, z, n условие (посылка) теоремы Ферма есть конъюнкция N(x)&N(y)&N(z)&N(n)&M(n), а заключение есть P(x, y, z, n). Поэтому теорема Ферма формулируется следующим образом: xyzn(N(x)&N(y)&N(z)&N(n)&M(n)  P(x, y, z, n)). Если теорема имеет вид x(P(x)  Q(x)), то предикат Q(x) является следствием предиката P(x). При этом предикат Q(x) называется необходимым условием предиката P(x), а предикат P(x) – достаточным условием предиката Q(x). Пример 2.21. Запишем в виде формулы логики предикатов утверждение: "Если число делится на 6, то оно делится на 3". Введем предикаты P(x) = "x делится на 6"; Q(x) = "x делится на 3". Наше утверждение формулируется следующим образом: x(P(x)  Q(x)). Предикат P(x) (делимость на 6) является достаточным условием предиката Q(x) (делимость на 3). Предикат Q(x) (делимость на 3) является необходимым условием предиката P(x) (делимость на 6). 31 2.5. Интерпретация формулы логики предикатов в виде суждения. Выполнимость. Общезначимость Формула есть перевод содержательного рассуждения в формальное рассуждение. Формула имеет смысл только тогда, когда имеется какаянибудь интерпретация входящих в нее символов. Каждая интерпретация состоит в указании множества М изменения предметных переменных и задании отношения между переменными с помощью предикатов. Для данной интерпретации формула представляет собой высказывание, если переменные связаны кванторами, а если есть свободные переменные, то формула есть предикат, который может быть истинным для одних значений переменных из области интерпретации и ложным для других. Пример 2.22. Пусть М – множество целых положительных чисел, и дан предикат A(x, y) = “x  y”. Рассмотрим следующие формулы: 1)A(x, y); 2) yA(x, y); 3) xyA(x, y). Первая формула – это предикат, который является истинным высказыванием для всех пар целых положительных чисел (a, b), таких, что a  b. Вторая формула – предикат “Для всякого целого положительного числа y имеет место x  y”, который является истинным только для x = 1. Третья формула – высказывание “Существует такое x, что для всякого y имеет место x  y”. Оно является истинным и соответствует тому, что на множестве М есть наименьшее число (единица). Пусть задаио множество M изменения предметных переменных формулы A(x1, x2, ... , xn), т. е. (x1, x2, ... , xn)  M. Определение 2.7. Формула A называется выполнимой в данной интерпретации, если существует набор значений переменных (a1,a2,...,an)  M, для которого A(a1, a2, ... , an) = И. Определение 2.8. Формула A называется истинной в данной интерпретации, если A(x1, x2, ... , xn) = И на любом наборе своих переменных (x1, x2, ... , xn)  M. Определение 2.9. Формула A называется общезначимой или тождественно-истинной, если она истинна в каждой интерпретации. 32 Определение 2.10. Формула A называется выполнимой, если существует интерпретация, для которой она выполнима. Проблема разрешимости для логики предикатов, так же, как и для логики высказываний (см. раздел 1.5) заключается в том, чтобы установить, является ли произвольная формула тождественноистинной. Но, если для логики высказываний эта проблема решается положительно, то для логики предикатов неразрешимость этой проблемы устанавливает следующая теорема: Теорема 2.4. (Теорема Черча). Не существует алгоритма, который для любой формулы логики предикатов устанавливает, общезначима она или нет. Однако для одноместных предикатов проблема разрешимости решается положительно. В общем случае выделение общезначимых формул логики предикатов возможно в рамках аксиоматического подхода, который будет рассмотрен ниже (см. раздел 3.3). 33 Контрольные вопросы к теме 2 1. Какие из следующих утверждений верны: а) Предикат есть сложное высказывание, состоящее из простых высказываний. б) Предикат есть высказывание, зависящее от параметров. в) Высказывание есть 0-местный предикат. г) Высказывание есть одноместный предикат. 2. Выберите правильный вариант ответа 1 – 4 для следующих вопросов: а) Обобщением какой операции является связывание квантором общности? б) Обобщением какой операции является связывание квантором существования? Варианты ответа: 1 – дизъюнкция; 2 – конъюнкция; 3 – импликация; 4 – эквивалентность. 3. Какие из следующих формул логики предикатов являются равносильными: а) ¬xA(x) и x(¬A(x)); б) ¬xA(x)) и x¬A(x)); в)x(A(x)VB) и xA(x)VB; г) x(A(x)&B(x)) и xA(x)&xB(x); д)xyA(x,y) и yxA(x,y); е) xyA(x, y) и yxA(x, y); ж) xyA(x, y) и yxA(x, y). 4. Какие из следующих формул логики предикатов являются приведенными и какие – нормальными: а) ¬xA(x)VxyA(x, y); б) yxA(x, y)&yzB(y, z); в) xyz(A(x, y)&B(y, z)). 34 ТЕМА 3. ФОРМАЛЬНЫЕ АКСИОМАТИЧЕСКИЕ ТЕОРИИ (ИСЧИСЛЕНИЯ) 3.1. Принципы построения формальных теорий Формальная аксиоматическая теория считается заданной, если заданы: 1. Символы. Задано некоторое счетное множество символов теории. 2. Формулы. Определено некоторое множество формул, или правильно построенных выражений. Формулы задают язык теории. 2. Аксиомы. Выделяется множество формул, называемых аксиомами теории. Это множество может быть как конечным, так и бесконечным. 4. Правила вывода. Задаются правила вывода как некоторые отношения на множестве формул. Если формулы A1, A2, …, Ak, B находятся в отношении R, то формула B называется непосредственно выводимой из A1, A2, …, Ak по правилу R. Это часто записывается следующим образом: A , A , , A . 1 2 k B Выводом формулы B из множества формул Г = {A1, A2, …, An} называется последовательность формул B1, B2, …, Bm , такая, что Bm есть B, и для любого i, i = 1, 2, …, m, Bi – либо аксиома, либо формула из Г, либо непосредственно выводима из предыдущих формул. B1, B2, …, Bi–1. Это обозначается так: Г ├ B (B есть следствие Г) или A1, A2, …, An ├ B. Формулы A1, A2, …, An называются допущениями или гипотезами, про формулу B говорят, что она выводима из A1, A2, …, An. Если Г – пустое множество, то A – теорема, а ее вывод называется доказательством. В этом случае пишут ├ A. Во всякой формальной теории существуют три проблемы, связанные с системой аксиом: 1) проблема непротиворечивости; 2) проблема независимости; 3) проблема полноты. Для того, чтобы доказать, что система аксиом непротиворечива, необходимо и достаточно доказать, что какова бы ни была формула F, выводимая в рассматриваемой теории, формула ¬F не является выводимой в этой теории. 35 Доказательство независимости системы аксиом состоит в доказательстве невыводимости никакой из аксиом системы из других аксиом. Проблема полноты состоит в доказательстве следующего факта. Какова бы ни была аксиома, не содержащаяся среди аксиом данной теории, добавление ее к исходной системе приводит к тому, что расширенная система аксиом становится противоречивой. 3.2. Исчисление высказываний В соответствии с общими принципами построения формальных систем (исчислений) исчисление высказываний определяется следующим образом. 1 Символы исчисления высказываний включают в себя: а) знаки логических операций , ; б) буквы Xi с целыми положительными индексами i; в) скобки и запятую – ( , ). 2. Формулами исчисления высказываний являются: а) все переменные Xi; б) если A и B – формулы, то A – формула и A  B – формула. Хотя для исчисления высказываний выбраны только два логических символа и  и только два типа формул A и A  B, можно с помощью следующих известных равносильностей ввести и другие логические символы и формулы: A & B  A  B); A V B  A  B; A  B  (( A B)  ( B  A )). 3. Аксиомы исчисления высказываний. Существуют различные системы аксиом исчисления высказываний, обладающие свойствами непротиворечивости, независимости и полноты. Будем использовать следующую систему аксиом: А1. A  (B  A); А2. (A  (B  C))  ((A  B)  (A  C)); А3. (B  A)  ((B  A) B). Непосредственной проверкой можно убедиться, что аксиомы есть тождественно-истинные формулы. Например, для аксиомы А1: A  (B  A)A V B V A  И.  4. Правило вывода в исчислении высказываний одно – modus ponens (m. p.) – правило заключения: A, A ⇒Β , B или A, AB ├B. 36 Аксиомы исчисления высказываний являются формулами. Аксиомы и формулы можно рассматривать как схемы, так что любую входящую в них переменную можно заменять формулами. Пример 3.1. Если в правиле modus ponens переменную B заменить формулой A&B, получим правило вывода A, A  A & B . A& B Всякую выведенную в исчислении высказываний формулу можно рассматривать как правило вывода, которое может быть присоединено к уже имеющимся правилам. Вывод формулы представляет собой последовательность формул, сопровождаемых указаниями, является ли данная формула гипотезой, аксиомой или получена из других формул по некоторому правилу вывода. Принято вначале выписать все гипотезы и слева указывать номер шага вывода. Пример 3.2. Построим вывод формулы A├ B A. (1) A – гипотеза; (2) A (B A) – аксиома А1; (3) A, A  ( B  A) B A – из (1) и (2) по m. p. Очевидно, что любую равносильную формулу можно рассматривать как правило вывода. Например, закон де Моргана может быть представлен как следующее правило вывода: ( A & B ) . AVB Равносильность A B B  A порождает закон контрапозиции: A B . В  А С учетом сказанного перечислим правила вывода исчисления высказываний. 1. Введение конъюнкции: A, B . 2. 3. A& B A& B Удаление конъюнкции: A & B и B A ( A & B) Отрицание конъюнкции: . AVB 4. Введение дизъюнкции: A AVB 5. Удаление дизъюнкции: AVB , A B и . B . AVB и AVB , B . A 37 6. Отрицание дизъюнкции: 7. Введение импликации: 8. Удаление импликации: ( AVB ) A & B A B A B, A   A, A   A B (A  ) A & B A  , B  A A~B A~B A~B B A A B . . (m. p.) и 9. Отрицание импликации: . 10. Введение эквивалентности: 11. Удаление эквивалентности: 12. Введение отрицания: 13. Удаление отрицания: 14. Закон контрапозиции: . . и . A . A A . A A B . В  А Для построения выводов в исчислении высказываний полезной оказывается следующая теорема. Теорема дедукции (без доказательства). Пусть Г – множество формул, A и B – формулы, и имеет место вывод: Г, A ├ B. Тогда имеет место следующий вывод: Г ├ A B. Таким образом, если нужно вывести формулу вида A B из множества формул (возможно, пустого), можно использовать дополнительное допущение A. Важным следствием теоремы дедукции является правило силлогизма (дается без доказательства): Правило силлогизма (транзитивный вывод). A B, B C ├ AC. Рассмотрим примеры построения вывода высказываний. Пример 3.3. а) Обосновать вывод A (B C), A&B ├ C. (1) A  (B C) – гипотеза; (2) A&B – гипотеза; (3) A – из (2) и правила удаления конъюнкции; (4) B C – из (1), (3) и m. p. (5) B – из (2) и правила удаления конъюнкции; (6) C – из (4), (5) и m. p. в исчислении 38 б) Обосновать правильность следующего рассуждения, построив вывод: Если число целое, то оно рациональное, Если число рациональное, то оно действительное. Число целое. Значит, оно действительное. Сначала формализуем наше рассуждение, введя следующие высказывания: A = “число целое”. B = “число рациональное”. C = “число действительное”. Нужно построить следующий вывод: A B, B C, A ├ C. Построим этот вывод. (1) A B – гипотеза; (2) B C – гипотеза; (3) A – гипотеза; (4) A C – из (1) и (2) по правилу силлогизма; (5) C – из (3) и (4) по m. p. в) Обосновать правильность следующего рассуждения, построив вывод: Если бы Иван был умнее Петра, он решил бы эту задачу. Иван не решил эту задачу. Значит, он не умнее Петра. Формализуем наше рассуждение, введя следующие высказывания: A = “Иван умнее Петра”. B = “Иван решил эту задачу”. Построим следующий вывод: A B, B ├ A. (1) A B – гипотеза; (2) B – гипотеза; (3) B A – из (1) по закону контрапозиции; (4) A – из (3) и (2) по m. p. 39 3.3. Исчисление предикатов Исчисление предикатов определяется следующим образом. 1. Символы исчисления предикатов включают в себя: а) символы предметных переменных x1, x2,…, xn, …; б) символы предметных констант a1, a2,…, an, …; в) символы или имена предикатов A 11 , A 12 ,…A kj , …; г) символы или имена функций f 11 , f 12 ,…f kj , …; д) знаки логических операций , е) символы кванторов ,  ; ж) скобки и запятую – ( , ). Верхние индексы указывают число аргументов, а нижние индексы служат для обычной нумерации. 2. Понятие формулы исчисления предикатов определяется в два этапа: 1) Термы: а) предметные переменные x1, x2,…, xn, ... и константы a1, a2,…, an,..; б) если f n – имя функции, а t1, t2,…, tn – термы, то f n(t1, t2,…, tn) – тоже терм. 2) Формулы: а) если An – имя предиката, а t1, t2,…, tn – термы, то An(t1, t2,…, tn) – формула; все вхождения переменных в формулу An(t1, t2,…, tn) являются свободными; б) если A(x) – формула, содержащая свободное вхождение переменной x, то выражения с кванторами xA(x), xA(x) – формулы; в) если A и B – формулы, то A, AB – формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными. Так же, как и в исчислении высказываний, можно ввести знаки других логических операций (&, V, ), используя соответствующие равносильности. Введение в исчисление предикатов термов расширяет правила образования формул, так как предметные переменные в элементарных предикатах могут быть заменены термами. Подстановка терма y в формулу A(x) называется правильной, если и только если: а) y является предметной константой; б) у является предметной переменной, и все вхождения y, полученные в результате подстановки, оказываются свободными в полученной в результате подстановки формуле. Например, в формулу y(P(x, y)  Q(x)) вместо x можно подставить либо константу a: 40 y(P(a, y)  Q(a)), либо переменную z: y(P(z, y)  Q(z)), но нельзя подставить переменную y, так как после подстановки получим формулу: y(P(y, y)  Q(y)), в которой переменная y оказывается связанной. 3. Аксиомы исчисления предикатов. А1. A  (B  A). А2. (A  (B  C))  ((A  B)  (A  C)). А3. (B  A)  ((B  A) B). А4. xA(x) A(y), где формула A(x) не содержит переменной y. А5. A(x)  yA(y), где формула A(x) не содержит переменной y. 4. Правил вывода в исчислении предикатов четыре: П1 – modus ponens (m. p.) – правило заключения: A, A   ; B П2 – правило связывания квантором общности: B  A( x) B  xA( x) , где формула B не содержит переменной x; П3– правило связывания квантором существования: A( x)  B , xA( x)  B где формула B не содержит переменной x; П4 – правило переименования связанной переменной. Связанную переменную в формуле A можно заменить (в кванторе и во всех вхождениях в области действия квантора) другой переменной, не являющейся свободной в A. Например, для формулы xF(x)  xG(x) применяя правило переименования, получим формулу yF(y)  zG(z). Для правил П2 и П3 условие, что формула B не содержит переменной x, является существенным. Это подтверждает следующий пример. Пример 3.4. Даны два предиката: B(x) = "x делится на 6"; A(x) = "x делится на 3". Тогда B(x)A(x) = "Если x делится на 6, то x делится на 3" = И для всех x. Однако B(x)  xA(x) = "Если x делится на 6, то все x делятся на 3" не всегда истинно. Таким образом, применение правила П2 неправомерно, если B зависит от x. 41 Если же к формуле B(x)  A(x) применить правило П3, то получим xB(x)  A(x). После применения правила П2 получим xB(x) xA(x) = "Если некоторые x делится на 6, то все x делятся на 3" = Л. Таким образом, применение правила П3 также неправомерно, если B зависит от x. Для исчисления предикатов верны правила вывода 1 – 14 исчисления высказываний (раздел 3.2). Дополнительные правила вывода для исчисления предикатов следующие: 1. Введение квантора общности: A( y ) , где A(y) – результат xA( x ) правильной подстановки переменной y вместо x в A(x). 2. Удаление квантора общности: xA( x) , где A(y) – результат A( y ) правильной подстановки терма y вместо x в A(x). xA( x) . xA( x) A( y ) существования: , xA( x) 3. Отрицание квантора общности: 4. Введение квантора где A(y) – результат правильной подстановки терма y вместо x в A(x). 5. Удаление квантора существования: yA( y ) , где A(x) – результат A( x) правильной подстановки переменной x вместо y в A(y). 6. Отрицание квантора существования: xA( x) . xA( x) Верна также теорема дедукции. Если Г – множество формул, A и B – формулы, и Г, A ├B. Тогда Г ├ A B. Сформулируем без доказательства важные утверждения для исчисления предикатов Теорема 3.1. Аксиомы исчисления предикатов – общезначимые формулы. Теорема 3.2. Любая выводимая в исчислении предикатов формула является общезначимой. Пример 3.5. Обосновать правильность рассуждения, построив вывод. а) Всякое нечетное натуральное число является разностью квадратов двух натуральных чисел. 5 – натуральное число. Следовательно, 5 – разность квадратов двух натуральных чисел 42 Пусть M – множество натуральных чисел. Введем предикаты: A(x) = “x – нечетное число”. B(x) – “x – разность квадратов двух чисел”. Требуется построить вывод: x(A(x)  B(x)), A(5) ├ B(5). Построим вывод. (1) x(A(x)  B(x)) – гипотеза; (2) A(5) – гипотеза; (3) A(5)  B(5) – из (1) и удаления ; (4) B (5) – из (2) и (3) по m. p. б) Все словари полезны. Все полезные книги высоко ценятся. Следовательно, все словари высоко ценятся. Сначала формализуем наше рассуждение, введя следующие предикаты: A(x) = “x – словарь”. B(x) = “x – полезен”. C(x) = “x высоко ценится”. Требуется построить следующий вывод: x(A(x)  B(x)), x(B(x)  C(x)) ├ x(A(x)  C(x)). Построим этот вывод. (1) x(A(x)  B(x)) – гипотеза; (2) x(B(x)  C(x)) - гипотеза; (3) A(y)  B(y) – из (1) и удаления ; (4) B(y)  C(y) – из (2) и удаления ; (5) A(y)  C(y) – из (3) и (4) по правилу силлогизма; (6) x(A(x)  C(x)) – из (5) и введения . в) Всякий совершеннолетний человек, находящийся в здравом уме, допускается к голосованию. Джон не допущен к голосованию. Значит, он либо несовершеннолетний, либо не находится в здравом уме. Формализуем наше рассуждение, введя следующие предикаты: A(x) = “x – совершеннолетний”. B(x) = “x находится в здравом уме”. C(x) = “x допущен к голосованию”. Введем константу d, обозначающую имя "Джон". Требуется построить следующий вывод: x(A(x)&B(x)  C(x)), C(d))├ A(d) V B(d). 43 Построим этот вывод. (1) x(A(x)&B(x)  C(x))гипотеза; (2) C(d)) гипотеза; (3) A(d)&B(d)  C(d) из (1) и удаления ; (4) C(d)) (A(d)&B(d)) – из (3) и правила контрапозиции; (5) C(d)) A(d) V B(d) – из (4) и отрицания конъюнкции; (7) A(d) V B(d) – из (2) и (5) по m. p. 3.4. Автоматическое доказательство теорем. Метод резолюций. Пусть имеется множество формул Г = {A1, A2, …, An} и формула B. Автоматическим доказательством теоремы B называют алгоритм, который проверяет вывод A1, A2, …, An├ B. (3. 1) Выражение (3.1) можно прочитать следующим образом: «Если посылки A1, A2, …, An истинны, то истинно заключение B.» или «Если причины A1,A2,…,An имели место, то будет иметь место следствие B.» Проблема доказательства в логике состоит в том, чтобы установить, что если истинны формулы A1, A2, …, An, то истинна формула B. В общем случае такой алгоритм построить нельзя. Но для некоторых частных случаев такие алгоритмы существуют. Доказательство теоремы равносильно доказательству общезначимости некоторой формулы. Наиболее эффективно доказательство общезначимости формул осуществляется методом резолюций. Процедура поиска доказательства методом резолюций фактически является процедурой поиска опровержения, т. е. вместо доказательства общезначимости формулы доказывается, что отрицание формулы противоречиво: A  И  A  Л. Введем терминологию, обычно употребляемую при изложении метода резолюций. Литерой будем называть выражения A или A. Литеры A и A называются контрарными, а множество {A, A} – контрарной парой. Дизъюнкт – это дизъюнкция литер (или элементарная дизъюнкция). 44 Пример 3.6. A V B V C – дизъюнкт; A V B – дизъюнкт; A V B & C – не дизъюнкт; A – дизъюнкт. Дизъюнкт называется пустым, (обозначается ), если он не содержит литер. Пустой дизъюнкт всегда ложен, так как в нем нет литер, которые могли бы быть истинными при любых наборах переменных. Рассмотрим применение метода резолюций к исчислению высказываний. Правилом резолюции называют следующее правило вывода: AVB , AVC . (3. 2) BVC Правило (3.2) можно также записать в следующем виде: AVB,AVC├BVC. (3. 3) Правило резолюций можно доказать, используя равносильности логики высказываний: (AVB) & (AVC)  (B V C) = ((AVB) & (AVC)) V (B V C) = = (AVB) V (AVC) V (B V C) = A&B V A&C V (B V C) = = (AV A) & (AV C) & (BV A) & (BV C) V (B V C) = = (AV C) & (BV A) & (BV C) V (B V C) = = (AV C V B V C) & (BV A V B V C) & (BV C V B V C) = И. Итак, при истинных посылках истинно заключение. Правило (3.2) – единственное правило, применяемое в методе резолюций, что позволяет не запоминать многочисленных аксиом и правил вывода. Дизъюнкт BVC называется резольвентой дизъюнктов AVB и AVC по литере A: BVC = resA(AVB и AVC). Если дизъюнкты не содержат контрарных литер, то резольвенты у них не существует. Для дизъюнктов A и A резольвента есть пустой дизъюнкт: resA(A,A)= . 45 Пример 3.7. Пусть F = A V B V C, G = A V B V D. Тогда resA(F, G) = B V C V B V D. resB(F, G) = A V C V A V D. resC(F, G) не существует. Метод резолюций соответствует методу доказательства от противного. Действительно, условие A1, A2, …, An├ B равносильно условию A1, A2, …, An, B├ . Метод резолюций относится к методам непрямого вывода. Изложим процедуру вывода A1, A2, …, An├ B в виде алгоритма. Алгоритм построения вывода методом резолюций. Шаг 1. Формулы A1, A2, …, An и формулу B привести к КНФ. Шаг 2. Составить множество S дизъюнктов формул A1, A2, …, An и B. Шаг 3. Вместо пары дизъюнктов, содержащих контрарные литеры записать их резольвенту по правилу (3.2). Шаг 4. Процесс продолжаем. Если он заканчивается пустым дизъюнктом, то вывод обоснован. Изложенный алгоритм называется резолютивным выводом из S. Возможны три случая: 1. Среди множества дизъюнктов нет содержащих контрарные литеры. Это означает, что формула B не выводима из множества формул A1, A2, …, An. 2. В результате очередного применения правила резолюции получен пустой дизъюнкт. Это означает, что формула B выводима из множества формул A1, A2, …, An . 3. Процесс зацикливается, т. е. получаются все новые и новые резольвенты, среди которых нет пустых. Это ничего не означает. Пример 3.8. В примере 3.3 а) был обоснован вывод A (B C), A&B ├ C. Применим для этого примера метод резолюций. Для этого нужно проверить вывод A  (B C), A&B, C├ . Будем действовать в соответствии с алгоритмом. Шаг 1. Нужно привести к КНФ формулы A  (B C), A&B, C. A (B C)   A V (B C)  A V B VC. Формулы A&B, C уже находятся в КНФ. 46 Шаг 2. Составим множество S дизъюнктов: S = {A V B V C, A, B, C}. Шаг 3. Построим резолютивный вывод из S. Для этого выпишем по порядку все дизъюнкты из S: 1) A V B VC; 2) A; 3) B; 4) C; Вместо пары дизъюнктов, содержащих контрарные литеры запишем их резольвенту (в скобках указаны номера формул, образующих резольвенту): 5) B V C. (1, 2) 6) C. (3, 5) 7) . (4, 6) Вывод заканчивается пустым дизъюнктом, что является обоснованием вывода A (B C), A&B ├ C. Пример 3.9. Записать с помощью формул логики высказываний и решить методом резолюций следующую задачу: «Чтобы хорошо учиться, надо прикладывать усилия. Тот, кто хорошо учится, получает стипендию. В данный момент студент прикладывает усилия. Будет ли он получать стипендию?» Введем следующие высказывания: A = ”студент хорошо учится”. B = ”студент прикладывает усилия”. C = ”студент получает стипендию” Чтобы утвердительно ответить на вопрос задачи: ”Будет ли студент получать стипендию?”, нужно проверить вывод: B  A, A C, B├ C. Будем действовать в соответствии с алгоритмом. Шаг 1. Нужно привести к КНФ формулы B  A, A C, B, C. B  A = B V A, A C = A VC, Формулы B и C уже находятся в КНФ. Шаг 2. Составим множество S дизъюнктов: S = {B V A, A VC, B, C}. Шаг 3. Построим резолютивный вывод из S. Сначала перепищем по порядку дизъюнкты из S: 47 1) B V A. 2) A VC. 3) B. 4) C. Затем вместо пары дизъюнктов, содержащих контрарные литеры запишем их резольвенту: 5) B V C. (1, 2) 6) C. (3, 5) 7) . (4, 6) Таким образом, на вопрос задачи можно ответить утвердительно: ”Студент будет получать стипендию”. Правило резолюций более общее, чем правило modus ponens и производные правила, рассмотренные в п. 3.2. Докажем методом резолюций правило modus ponens. Необходимо построить вывод A, A B├ B. Построим резолютивный вывод. A, A V B├ B. A, A V B, B├ . S = {A, A V B, B}. 1) A. 2) A V B. 3) B. 4) B. (1, 2) 5) . (3, 4) Метод резолюций легко поддается алгоритмизации. Это позволяет использовать его в логических языках, в частности в ПРОЛОГе. Недостатком этого метода является необходимость представления формул в КНФ. Кроме того, автоматическое доказательство теорем методом резолюций основан на переборе и этот перебор может быть настолько большим, что затраты времени на него практически неосуществимы. Эти обстоятельства стимулируют поиски различных модификаций метода резолюций. Приведем еще один пример применения метода резолюций, основанного на попарном переборе дизъюнктов. 48 Пример 3.10. Построим с помощью метода резолюций следующий вывод: A B, C V A, B C├ A, Или, что то же: A B, C V A, B C, A├ . Перепишем все посылки в виде дизъюнктов: A VB, C V A, B VC, A├ . Выпишем по порядку все посылки и начнем их по очереди склеивать по правилу резолюций: 1) A V B 2) C V A 3) B VC 4) A 5) A V C (1, 3) 6) B (1, 4) 7) A V B (2, 3) 8) C. (2, 4) 9) A (2, 5) 10) C (3, 6) 11) B (3, 8) 12) C (4, 5) 13) B (4, 7) 14)  (4, 9) Мы видим, что такая стратегия перебора неэффективна. В данном случае существует более быстрый вывод. Например: 5) B. (1, 4) 6) C. (2, 4) 7) B. (3, 6) 8) . (5, 7) 49 ТЕМА 4. НЕЧЕТКАЯ ЛОГИКА 4.1. Нечеткие множества В 1965 году американский математик Лотфи Заде (L. Zade) опубликовал статью “Нечеткие множества” (“Fuzzy sets”). Было дано новое определение понятия множества, предназначенное для описания сложных плохо определенных систем, в которых наряду с количественными данными присутствуют неоднозначные, субъективные, качественные данные. Понятие множества лежит в основе всех математических конструкций, и статья Заде породила новое научное направление. Произошло “раздвоение” математики, появились нечеткие функции, нечеткие отношения, нечеткие уравнения, нечеткая логика и т. д. Эти понятия широко используются в экспертных системах, системах искусственного интеллекта. Изложим основные понятия нечетких множеств. Определение 4.1. Нечетким множеством A~ на множестве X назовем пару (X, mA), где mA(x) – функция, каждое значение которой mA(x)  [0, 1] интерпретируется как степень принадлежности точки xX множеству A~ . Функция mA – называется функцией принадлежности множества A~ . Для обычного четкого множества A можно положить 1, x  A, mA(x) =  0, x  A. Таким образом, обычное множество является частным случаем нечеткого множества. Функцию принадлежности, как и всякую функцию, можно задавать таблично или аналитически. Пример 4.1. Приведем пример нечеткого множества A~ , которое формализует понятие "несколько", ясного лишь на интуитивном уровне. Пусть X = {1, 2, 3, …, n,…} – множество натуральных чисел, а функция mA(x) задана таблицей: x 1 2 3 4 mA(x) 0 0,1 0,6 0,8 5 1 6 1 7 8 9 0,9 0,7 0,2 10 … 0 … Аналогично можно ввести понятия "много", "мало", "около 100", "почти 20", и т.д. 50 Переменные, значениями которых являются нечеткие множества, называются лингвистическими. Это основной тип переменных в языке людей. Пример 4.2. Пусть X = (0, ) – множество положительных чисел, а функция mA(x) задана формулой: mA(x) = 0, 0  x  50,  1  25   , x  50. 1  2   ( x  50)  График этой функции изображен на рис. 4.1. Рис. 4.1 Если переменную x интерпретировать как возраст, то нечеткое множество A~ соответствует понятию "старый". Аналогично можно ввести понятия "молодой", "средних лет" и т. д. Пример 4.3. Переменная "расстояние" принимает обычно числовые значения. Однако в предложениях естественного языка она может фигурировать как лингвистическая со значениями: "малое", "большое", "среднее", "около 5 км" и т. д. Каждое значение описывается нечетким множеством. Пусть речь идет о поездках на такси по городу. В качестве универсального множества X можно взять отрезок [0, 100] км и задать функцию принадлежности значений так, как показано на рис. 4.2. Рис.4.2 51 Операции с нечеткими множествами Введем операции с нечеткими множествами аналогично операциям с обычными множествами. Пусть A~ и B~ – два нечетких множества с функциями принадлежности mA(x) и mB(x). В табл.4.1 приведены названия основных операций, их лингвистический смысл и формула для определения функции принадлежности множества C~ , которое является результатом соответствующей операции. Таблица 4. 1 Операции ЛингвистиФормула для ческий смысл mC(x) Пересечение и min(mA(x), mB(x)) ~ ~ ~ C = A  B Объединение ~ ~ ~ или max(mA(x), mB(x)). C = A  B Дополнение не 1 – mA(x) Концентрация очень [mA(x)]2 Размывание не очень [mA(x)]1/2 Нечеткое множество называется пустым, если mA(x) = 0 для всех xX. Пример 4.4. ~ Пусть X – множество студентов, A – множество пожилых людей. ~ Множество A – пустое, mA(x) = 0 для всех xX, так как пожилых студентов, вообще говоря, не бывает. Введенные для нечетких множеств операции позволяют конструировать сложные понятия из простых: очень много, не старше и не моложе и т. д. По аналогии с четкими множествами определяется ~ ~ ~ отношение включения множества A в множество B , а именно A является подмножеством B~ тогда и только тогда, когда mA(x)  mB(x) для всех xX. Мы видим, что понятие нечеткого множества носит субъективный характер, такова и его формализация. Результаты, полученные с помощью аппарата алгебры нечетких множеств, должны носить качественный характер. Большей объективности выводов можно добиться, получив оценки функции принадлежности mA(x) путем опроса экспертов. 52 4.2. Нечеткие высказывания Определение 4.2. Нечетким высказыванием называется ~ ~ высказывание A , степень истинности которого ( A ) можно оценить числом из интервала [0, 1], ( A~ )  [0, 1]. Если ( A~ ) = 0,5, то высказывание называется индифферентным. Определение 4.3. Нечеткой высказывательной переменной ~ ~ X называется нечеткое высказывание X , степень истинности которого может меняться в интервале [0, 1]. Так как степень истинности нечеткого высказывания не связана с сутью высказывания, будем в дальнейшем отождествлять нечеткое высказывание с его степенью истинности аналогично тому, как обычное четкое высказывание отождествлялось с его истинностью или ложностью (см. п.1.1). Нечеткие высказывания и степень их истинности ~ ~ ~ будем обозначать большими буквами с тильдой:: A , B , X , и т. д. На множестве нечетких высказываний вводятся логические операции, аналогичные операциям алгебры высказываний. 1. Отрицание нечеткого высказывания:  A~ =1– A~ . (4.1) 2. Конъюнкция нечетких высказываний: ~ ~ ~ ~ (4.2) A & B =min( A , B ). 3. Дизъюнкция нечетких высказываний: ~ ~ ~ ~ A V B =max( A , B ). (4.3) 4. Импликация нечетких высказываний: ~ ~ ~ ~ (4.4) A  B =max(1– A , B ). 5. Эквивалентность нечетких высказываний: ~ ~ ~ ~ ~ ~ (4.5) A  B =min(max(1– A , B ),max( A ,1– B )). Старшинство операций принято в порядке 1) – 5). Пример 4.5. Найти степень истинности высказывания ~ ~ ~ ~ ~ ~ ~ ~ C = ( A V B )  ( A  A & B )) при A = 0,8; B = 0,3. Порядок действий определяется старшинством операций и скобками. 1. A~ & B~ = min(0,8; 0,3) = 0,3. 2. ( A~  A~ & B~ ) = max (1 – 0,8; 0,3) = 0,3. ~ 3. A V B~ = max (0,8; 0,3) = 0,8. 4. C~ = min (max (1 – 0,8; 0,3), max (0,8; 1 – 0,3)) = min(0,3; 0,8) = 0,3. 53 Множество нечетких высказываний вместе с введенными на них операциями образуют алгебру нечетких высказываний. Определение 4.4. Нечеткой логической формулой называется: а) любая нечеткая высказывательная переменная; б) если A~ и B~ – нечеткие логические формулы, то  A~ , A~ & B~ , A~ V B~ , ~ ~ ~ ~ A  B , A  B – тоже нечеткие логические формулы. Определение 4.5. Пусть A~ ( X~ 1, X~ 2, …, X~ n) и B~ ( X~ 1, X~ 2, …, X~ n) – две нечеткие логические формулы. Степенью равносильности формул A~ и ~ B называется величина ( A~ , B~ )= & { A~ (1,2,…,n) B~ (1,2,…,n)} (4.6) (1 , 2 ,..., n ) Здесь логические операции конъюнкции и эквивалентности имеют смысл, определенный выше для логических операций над нечеткими высказываниями, причем конъюнкция берется по всем наборам степеней истинности (1, 2, …,n) нечетких переменных ( X~ 1, X~ 2, …, X~ n). Множество всех наборов степеней истинности (1, 2, …,n) нечетких переменных ( X~ 1, X~ 2, …, X~ n) назовем полной областью определения Cn. Очевидно, что множество Cn имеет мощность континуума в отличие от двузначной логики высказываний, где число всех наборов переменных конечно и равно 2n. Если ( A~ , B~ ) = 0,5, то нечеткие формулы A~ и B~ называются индифферентными. Если ( A~ , B~ ) > 0,5, то нечеткие формулы A~ и B~ называются нечетко равносильными. Если ( A~ , B~ ) < 0,5, то нечеткие формулы A~ и B~ называются нечетко неравносильными. Определение 4.6. Степенью неравносильности формул A~ и B~ называется величина  ( A~ , B~ ) = 1 – ( A~ , B~ ). Пример 4.6 Определить степень равносильности формул. ~ ~ ~ ~ ~ ~ ~ ~ A = X  Y , B =  X & Y при условии, что X и Y принимают значения степеней истинности из множества {0,1; 0,2}. Перечислим все возможные наборы значений X~ и Y~  A1 = {0,1; 0,1}; A2 = {0,1; 0,2}; A3 = {0,2; 0,1}; A4 = {0,2; 0,2}. Запишем формулы A~ и B~ с учетом (4.1), (4.2), (4.4): ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ A = X  Y max (1 – X , Y ); B =  X & Y 1 – X & Y 1 – min( X , Y ). 54 Вычислим формулы A~ и B~ на каждом из четырех наборов A1 – A4: ~ A 1 = max (1 – 0,1; 0.1) = 0,9. ~ A 2 = max (1 – 0,1; 0,2) = 0,9. ~ A 3 = max (1 – 0,2; 0,1) = 0,8. ~ A 4 = max (1 – 0,2; 0,2) = 0,8. ~ B 1 = 1 – min( 0,1; 0.1) = 0,9. ~ B 2 = 1 – min(0,1; 0,2) = 0,9. ~ B 3 = 1 – min(0,2; 0,1) = 0,9. ~ B 4 = 1 – min (0,2; 0,2) = 0,8. Вычислим теперь степень равносильности формул A~ и B~ в соответствии с (4.6): Для этого сначала вычислим A~ (1, 2, …,n)  B~ (1, 2, …,n)} для всех наборов A1 – A4: В соответствии с (4.5) имеем ~ ~ ~ ~ ~ ~ A  B = min (max (1 – A , B ), max ( A , 1 – B )). Поэтому ~ ~ A 1  B 1 = min (max (1 – 0,9;0,9), max (0,9; 1 –0,9)) = 0,9. ~ ~ A 2  B 2 = min (max (1 – 0,9;0,9), max (0,9; 1 –0,9)) = 0,9. ~ ~ A 3  B 3 = min (max (1 – 0,8;0,9), max (0,8; 1 –0,9)) = 0,8. ~ ~ A 4  B 4 = min (max (1 – 0,8;0,8), max (0,8; 1 –0,8)) = 0,8. Окончательно по (4.6) получим ( A~ , B~ ) = &   ( 1 , 2 ,..., n ) { A~ (1, 2 , …,n)  B~ (1,  2, …,n)} =0,9&0,9&0,8&0,8 = min(0,9; 0,9; 0,8; 0,8) = 0,8. Формулы A~ и B~ нечетко равносильны. На других наборах степеней истинности нечетких переменных ~ ~ ~ Y формулы A и B могут быть нечетко неравносильны. = ~ X и Определение 4.7. Пусть A~ ( X~ 1, X~ 2, …, X~ n) и B~ ( X~ 1, X~ 2, …, X~ n) – две нечеткие логические формулы, рассмотренные на некотором множестве M изменения нечетких переменных X~ 1, X~ 2, …, X~ n. Областью нечеткой равносильности формул A~ и B~ называется подмножество множества M, на котором формулы A~ и B~ нечетко равносильны. Пример 4.7. Вернемся к примеру 4.6. Для этого примера множество M состоит из девяти наборов: M = {{0,1; 0,1}; {0,1; 0,2}; {0,2; 0,1}; {0,2; 0,2}}. На каждом наборе формулы A~ и B~ нечетко равносильны, так как ( A~ , B~ ) > 0,5. Поэтому областью нечеткой равносильности будет все множество M. 55 Определение 4.8. Если формула A~ ( X~ 1, X~ 2, …, X~ n) на всех наборах переменных X~ 1, X~ 2, …, X~ n из некоторого множества M имеет степень истинности большую или равную 0,5, то она будет на нем нечетко истинной. Обозначается это так: A~ = И~ . Определение 4.9. Если формула A~ ( X~ 1, X~ 2, …, X~ n) на всех наборах переменных X~ 1, X~ 2, …, X~ n из некоторого множества M имеет степень истинности меньшую или равную 0,5, то она будет на нем нечетко ложной. Обозначается это так: A~ = Л~ . Пример 4.8. Покажем, что X~ V  X~ = И~ и X~ &  X~ = Л~ для всех значений нечеткой переменной X~ : 0  X~  1. Учитывая (4.1), (4.2), (4. 3), имеем ~ ~ ~ ~ ~ ~ X V  X = max ( X ,  X ) = max ( X , 1 – X )  0,5. ~ ~ ~ ~ ~ ~ X &  X = min( X ,  X ) = min( X , 1 – X )  0,5. 4.3. Нечеткие предикаты Определение 4.10. Нечетким предикатом P~ (x1, x2, ... , xn) называется нечеткая формула, переменные которой определены на некотором множестве М, x1, x2, ... , xn  M, а сама она принимает значения из интервала [0, 1]. Нечеткий предикат от n переменных называется n-местным нечетким предикатом. Нечеткое высказывание A~ , задаваемое степенью истинности ( A~ )  [0, 1] является одноместным нечетким предикатом. Пример 4.9. Пусть М = {0, 1, 2, 3}. Зададим нечеткий предикат следующим образом: P~ (x, y) = xy/9. Его значения определяются как: ~ ~ ~ ~ ~ ~ P (0, y) = P (x, 0) = 0; P (1, 1) = 1/9; P (1, 2) = P (2, 1) = 2/9; P (2, 2) = 4/9; P~ (1, 3) = P~ (3, 1) = 1/3; P~ (2, 3) = P~ (3, 2) = 2/3; P~ (3, 3) = 1; Определение 4.11. Нечеткими кванторами ~ и ~ называются логические символы, которые придают включающим их выражениям следующий смысл: ~ ~ ~ ~  P (x1, x2, ... , xn) = & P (x1, x2, ... , xn) = min P (x1, x2, ... , xn). x M xi M ~ ~  P (x1, x2, ... , xn) = V xi M i ~ P (x1, x2, ... , xn) = max P~ (x1, x2, ... , xn). x M i 56 Пример 4.10. Найдем значения степени истинности формул ~ P~ (x, 1) и ~ P~ (x, 1) для примера 4.9: ~ ~ ~ ~ ~ ~  P (x, 1) = min{ P (0, 1); P (1, 1); P (2, 1); P (3, 1)} = min{0; 1/9; 2/9; 1/3} = 0. ~ ~ ~ ~ ~ ~  P (x, 1) = max { P (0, 1); P (1, 1); P (2, 1); P (3, 1)} = max {0; 1/9; 2/9; 1/3} = 1/3. По аналогии с четкими предикатами вводятся также остальные понятия для нечетких предикатов. 57 ТЕМА 5. АЛГОРИТМЫ 5.1. Определение алгоритма Алгоритм можно определить как некоторую процедуру, однозначно приводящую к результату. Это интуитивное определение, которое, однако, позволяет безошибочно определить, является ли рассматриваемый процесс алгоритмом или нет. Примеры алгоритмов: 1. Сортировка массива чисел в порядке возрастания. 2. Вычисление таблицы значений булевой функции, заданной формулой. 3. Вычисление чисел Фибоначчи по рекуррентному соотношению. 4. Решение системы линейных алгебраических уравнений методом исключения Гаусса. Основные требования к алгоритмам 1. Алгоритм применяется к исходным данным и дает результаты. Кроме того, в процессе работы алгоритма могут появляться промежуточные данные. Итак, каждый алгоритм имеет дело с данными: исходными, промежуточными и выходными. Данными могут быть числа, векторы, матрицы, массивы, формулы, рисунки (в графических системах). 2. Данные для своего размещения требуют памяти. Память состоит из ячеек, так что каждая ячейка может содержать один символ алфавита данных. Таким образом, объем данных и требуемая память согласованы. 3. Алгоритм состоит из отдельных элементарных шагов или действий. Причем множество различных шагов, из которых составлен алгоритм, конечно. Типичный пример множества элементарных действий – система команд ЭВМ. 4. Последовательность шагов алгоритма детерминирована, т.е. после каждого шага либо указывается, какой шаг делать дальше, либо дается команда остановки, после чего работа алгоритма считается законченной. 5. Алгоритм должен удовлетворять требованию результативности, т. е. остановки после конечного числа шагов. В таком случае говорят, что алгоритм сходится. Любая практическая задача требует предварительного задания исходных данных. Как правило, можно задать некоторое характерное число n. 58 Например, для задачи сортировки массива чисел по возрастанию n – число чисел в массиве, для задачи решения системы линейных уравнений n – число уравнений. Характерное число задачи определяет размерность задачи как величину массива исходных данных. С ростом характерного числа размерность задачи возрастает. Введем понятие скорости роста функций, зависящих от целочисленного параметра n. Определение 5.1. Функции f(n) и g(n) имеют одинаковую скорость роста, если при достаточно больших n, начиная с некоторого n0, выполняется условие: C1g(n)  f(n)  C2g(n), где C1, C2 – некоторые константы. Определение 5.2. Скорость роста функции f(n) ограничена снизу скоростью роста функции g(n), если при достаточно больших n, начиная с некоторого n0, выполняется условие: C1g(n)  f(n), где C1 – некоторая константа. Определение 5.3. Скорость роста функции f(n) ограничена сверху скоростью роста функции g(n), если при достаточно больших n, начиная с некоторого n0, выполняется условие: f(n)  C2g(n), где C2 – некоторая константа. Определение 5.4. Скорость роста функции f(n) больше скорости роста функции g(n), если для любой сколь угодно большой константы C2 существует некоторое n0, начиная с которого выполняется условие: f(n)  C2g(n). Для того чтобы более наглядно представить скорости роста функций, их сравнивают со скоростями роста хорошо известных функций. В качестве таковых чаще всего используют степенные функции na. При a = 1 скорость роста функции na называют линейной, при a = 2 – квадратичной, при a = 3 – кубической и т. д. Скорость роста вида na называют полиномиальной. Очевидно, что при возрастании a скорость роста тоже увеличивается. Для некоторых функций скорости роста превосходят в пределе при n   любую полиномиальную скорость. Такими функциями являются, Например, 2n, en, n!. Скорости такого типа называют экспоненциальными. Обозначим через r(n) скорость роста размерности задачи. В задаче вычисления таблицы значений булевой функции n переменных скорость роста определяется таблицей значений переменных. 59 Так как различных наборов переменных 2n, а каждый набор состоит из n символов, то размерность задачи равна n2n и скорость роста будет экспоненциальной. В задаче решения системы линейных алгебраических уравнений методом исключения Гаусса наиболее быстро растет число элементов матрицы системы уравнений размером n  n. Поэтому скорость роста размерности этой задачи будет квадратичной, r(n) = n2. Размерность задачи определяет память, необходимую для представления исходных данных в ЭВМ, Кроме того, необходима дополнительная память для размещения промежуточных данных. Величина этой памяти зависит от конкретного алгоритма и ее, как правило, нетрудно рассчитать. Рассмотрим время реализации алгоритма – время счета. Пусть при выполнении некоторого алгоритма выполняются элементарные операции t1, t2, …, tk (арифметические, логические и другие). Среднее время выполнения этих операций обозначим через t1, t2, …, tk. По аналогии с размерностью задачи введем понятие скорости роста числа выполняемых операций в зависимости от характерного числа n. Обозначим их для операций t1, t2, …, tk через g1(n), g2(n), …, gk(n). Без доказательства приведем следующее утверждение. При n   скорость роста общего времени счета T(n) равна максимальной из скоростей роста числа элементарных операций g1(n), g2(n), .., gk(n) независимо от среднего времени их выполнения t1, t2, .., tk. Определение 5.5. Скорость роста общего времени счета T(n) называется вычислительной сложностью или просто сложностью алгоритма. Обозначим сложность алгоритма через f(n). В зависимости от сложности все алгоритмы делятся на несколько классов. Определение 5.6. Полиномиальными называются алгоритмы, сложность которых ограничена некоторым полиномом. Пример 5.1. Рассмотрим задачу определения максимального элемента в массиве из n чисел. Поскольку число операций сравнения постоянно и равно n – 1, сложность алгоритма f(n) = n. Определение 5.7. Экспоненциальными называются алгоритмы, сложность которых при возрастании n превышает полином любой степени. В примерах 5.2 и 5.3 точные алгоритмы имеют экспоненциальную точность. 60 Пример 5.2. Рассмотрим задачу коммивояжёра. Необходимо обойти n городов и вернуться в исходный пункт, так чтобы суммарный путь был минимальным. Количество всех возможных вариантов обхода равно 0.5n! Следовательно, сложность точного решения, основанного на переборе всех вариантов, равна f(n) = n! Пример 5.3. Рассмотрим задачу вычисления конъюнктивной нормальной формы (КНФ) булевой функции n переменных. Количество всех наборов переменных равно 2n. Количество всех операций при переборе всех дизъюнкций пропорционально n2n, следовательно, сложность алгоритма f(n) = n2n. Экспоненциальные алгоритмы практически могут быть реализованы только при малых значениях n (обычно при n < 10). Задачи, для которых существуют точные алгоритмы решения полиномиальной сложности, называются задачами класса P. Задачи, для которых не удается найти точные алгоритмы решения полиномиальной сложности, составляют класс NP. Для многих задач класса NP выполняется свойство сводимости, состоящее в том, что данный алгоритм выражается при помощи полиномиального числа операций через другой алгоритм, имеющий полиномиальную сложность. 5.2. Машина Тьюринга До недавнего времени интуитивного понятия алгоритм было достаточно, и термин алгоритм употреблялся в связи с вычислительной процедурой решения конкретной задачи. Утверждение о существовании алгоритма решения задачи вытекало из описания этого алгоритма. В начале XX века встал вопрос о выводимости и эффективных вычислениях. Понятие алгоритма стало объектом математических исследований и нуждалось в строгом определении. Возникли задачи, по-видимому, не имеющие алгоритмического решения. Первые работы по уточнению понятия алгоритм появились в 1936 – 1937 годах. Это были работы Тьюринга, Поста, Маркова, Чёрча. Было предложено несколько определений понятия алгоритм. Впоследствии было показано, что все они равносильны. Одной из первых и весьма удачных попыток дать точный математический эквивалент интуитивного представления об алгоритме 61 было введение понятия машины Тьюринга в 1937 году, за 9 лет до появления первой ЭВМ. Машина Тьюринга – абстрактная машина. Это математическая модель идеализированного вычислительного устройства. Машина Тьюринга состоит из ленты и управляющего устройства со считывающей и записывающей головки (каретки) (рис. 5.1). Рис. 5.1 Лента жестко закреплена слева и бесконечна справа. Иногда считают, что лента не ограничена справа и слева. Лента разделена на ячейки, которые нумеруются натуральными числами 1, 2, … . В каждую ячейку ленты заносятся символы внешнего алфавита машины Тьюринга A={a0,a1,...an}. (5.1) Один из символов (пробел) соответствует незаполненной, пустой ячейке. Головка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, то стоит против некоторой ячейки ленты; говорят, что головка обозревает эту ячейку. За единицу времени, которая называется шагом, головка может сдвинуться на одну ячейку влево или вправо. Кроме того, головка может также распознать содержимое обозреваемой ячейки, может заносить символ внешнего алфавита в текущую ячейку и может стирать содержимое текущей ячейки или, что то же самое, записывать туда пробел. Управляющее устройство может находиться в одном из множества дискретных состояний: Q={q0,q1,...qm}. (5.2) Множество Q называется внутренним алфавитом машины Тьюринга или алфавитом внутренних состояний. Словом называется последовательность W = ai1,ai2,…,ais символов, записанных в ячейках ленты, где ai1 – символ, находящийся в самой левой непустой ячейке, а ais – символ, находящийся в самой правой непустой ячейке. Количество символов s в слове называется длиной слова. 62 Пусть в некоторый момент времени t на ленте записано слово W, управляющее устройство находится в состоянии qi, а каретка – напротив символа aim слова W. Конфигурацией машины в момент времени t называется последовательность K = ai1, … , ai(m – 1), qi, aim … , ais. Конфигурации в начале и в конце работы называют соответственно начальной и заключительной. Пример 5.4. Пусть на ленте записано слово abcde, управляющее устройство находится в состоянии qi и каретка стоит против символа d. Конфигурация в этом случае запишется так: abcqide. Так как машина Тьюринга имеет конечный алфавит и конечное число внутренних состояний, то очевидно, что она может выполнять конечное число действий. Если управляющее устройство в некоторый момент времени находится в состоянии qi, обозревается символ aj, в следующий момент времени записывается символ ar, управляющее устройство переходит в состояние qk, и каретка сдвигается, то говорят, что машина выполняет команду ajqiarSqk, (5.3) где S – сдвиг, S = L, если сдвиг влево, S = R, если сдвиг вправо, S = C, если каретка остается на месте. Совокупность всех команд, которые может выполнить машина, называется ее программой. Условие однозначности требует, чтобы для любого j и любого i имеется только одна команда вида (5.3). Каждая машина Тьюринга полностью определяется своим алфавитом, внутренними состояниями и программой. Итак, машина Тьюринга есть совокупность M=, (5.4) где A – внешний алфавит (5.1), Q – алфавит внутренних состояний (5.2), P – программа (5.3). Пример 5.5. Машина с внешним алфавитом A = {1, a}, алфавитом внутренних состояний Q = {q1, q2} и программой 1q11Rq1, aq11R q1, из любой начальной конфигурации будет работать бесконечно, заполняя единицами всю ленту вправо от начальной точки. 63 Порядок работы машины Тьюринга часто задается в виде таблицы. В каждый столбец верхней строчки заносятся символы внутреннего алфавита, в каждую строчку первого столбца – символы внешнего алфавита. В ячейках на пересечении других столбцов и строчек помещаются команды. Если на пересечении какой-либо строки и какого-либо столбца мы получим пустую клетку, то это означает, что в данном внутреннем состоянии данный символ встретиться не может. A/Q a0 a1 q0 q1 … qi qn … aj ajKqi … am Формат команды: aKq, где: a – новое содержание текущей ячейки (новый символ внешнего алфавита, который заносится в текущую ячейку); K – команда лентопротяжного механизма машины Тьюринга (влево, вправо, стоп); q – новое внутренне состояние машины Тьюринга. Работа машины на основании заданной программы происходит следующим образом. Предположим, что в данный момент времени машина Тьюринга находится во внутреннем состоянии qi, а в обозреваемой кареткой ячейке ленты находится символ aj. Тогда машина переходит к выполнению команды ajKqi в ячейке, на пересечении столбца qi и строки aj: 1) в текущую ячейку ленты заносится новый символ aj (возможно, тот же самый). 2) происходит сдвиг головки влево (K = влево), или сдвиг головки вправо (K = вправо), или головка остается на месте, т. е. происходит остановка машины (K = стоп). 3) машины переходит в новое внутреннее состояние qi. 64 Возможные случаи останова машины Тьюринга: 1) в ходе выполнения программы машина дойдет до выполнения команды остановки; программа в этом случае считается выполненной, машина останавливается – происходит результативная остановка. 2) машина никогда не останавливается, происходит зацикливание. Пример 5.6. Пусть внешний алфавит A = {0, 1, 2}, а множество внутренних состояний состоит лишь из одного состояния Q = {q0}. Необходимо построить машину Тьюринга, которая в произвольной записи, начиная из любой ячейки, двигаясь вправо, находит первый нуль и останавливается. Такая машина может быть задана таблицей 5.1. a 1 2 Таблица 5.1 q0 0Cq0 1Rq0 2Rq0 Действительно, пусть, Например, вначале машина находится в состоянии 1 1 2 0 1 2 2 Рис. 5.2 Головка обозревает символ 1. В соответствии с табл. 5.2 выполняется команда 1Rq0, т. е. в обозреваемую ячейку записывается тот же самый символ 1 и головка смещается вправо (рис 5.3). 1 1 2 Рис. 5.3 1 2 2 Теперь головка снова обозревает символ 1 и в соответствии с табл. 5.2 выполняется команда 1Rq0, т. е. в обозреваемую ячейку записывается тот же самый символ 1 и головка смещается вправо (рис 5.4). 1 1 2 Рис. 5.4 1 2 2 65 Теперь головка обозревает символ 2 и в соответствии с табл. 5.2 выполняется команда 2Rq0, т. е. в обозреваемую ячейку записывается тот же самый символ 2 и головка смещается вправо (рис 5.5). 1 1 2 0 1 2 2 Рис. 5.5 Теперь головка обозревает символ 0 и в соответствии с табл. 5.2 выполняется команда 0Cq0 т. е. в обозреваемую ячейку записывается тот же самый символ 0 и машина останавливается. Пример 5.7. Построим машину Тьюринга, которая слово АVB) преобразует в слово А&B, а слово А&B) преобразует в слово А VB, что соответствует законам де Моргана. Такая машина может быть задана таблицей 5.2. Внешний алфавит A = { А, B, V, &, (, ), _} (символ _ соответствует пустой ячейке), а множество внутренних состояний состоит лишь из одного состояния Q = {q0}. Таблица 5.2 A q0  _Rq0 A ARq0 B Rq0 V &Rq0 & VRq0 ( Rq0 ) BRq0 _ _Cq0 Данные машины Тьюринга – это слова во внешнем алфавите ленты. На ленте записывается и исходные данные и конечный результат. На ленте могут быть записаны слова, а также последовательности слов. В последнем случае между словами ставится специальный символразделитель, им может быть пробел или символ . Натуральное число a представляется словом 1…1= 1a, состоящим из a единиц. Например, числу 3 соответствует слово 111. Пример 5.8. Построим машину Тьюринга, которая производит сложение двух натуральных чисел a и b. Сложить два числа a и b – это значит слово 1a  1b преобразовать в слово 1 a+b. 66 Это можно сделать, удалив в записи ab символ разделителя  и сдвинув первое слагаемое ко второму. Такая машина может быть задана таблицей 5.3. Внешний алфавит A = {1, , _}, где  – символ разделителя, а _ – символ пустой ячейки (пробел). Множество внутренних состояний состоит из трех состояний Q = {q0, q1, q2}. Таблица 5.3 a q0 Q1 q2 1 _Rq1 1Rq1 1Lq2 * _Rq1 1Lq2 _ _Cq1 _1Rq1 Начальное и конечное состояния ленты для случая a = 2, b = 3 представлено на рис. 5.6 a) и b) a) 1 1  1 1 1 1 1 1 Рис. 5.6 1 1 b) 5.3. Вычислимые по Тьюрингу функции Будем рассматривать функции f от одной или нескольких переменных, заданных на множестве N = {0, 1, 2, …, n, …} натуральных чисел или его подмножествах (частичные функции) и принимающие значения на множестве N. Определение 5.8. Функция f(x1, x2, …, xn) называется вычислимой, если существует алгоритм, позволяющий вычислять ее значения для тех переменных, для которых она определена, и работающий бесконечно, если функция для данного набора переменных не определена. Определение 5.9. Функция f(x1, x2, …, xn) называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая эту функцию. Переменные можно располагать в виде слов с разделителями 11…1 11…1……11…1 Пример 5.9. Запись 111 111 соответствует трем переменным x1, x2, x3, равным, соответственно, 3, 2 и 1. 67 Функция также записывается словом, состоящим из единиц. Пример 5.8 представляет функцию двух переменных f(a, b) = a + b. Тезис Тьюринга. Всякий алгоритм можно реализовать машиной Тьюринга. Тезис Тьюринга доказать нельзя. Это утверждение означает, что математическое понятие вычислимой по Тьюрингу функции является идеальной моделью интуитивного понятия алгоритма. Этот тезис подтверждается опытом. По своему характеру тезис Тьюринга напоминает математические законы механики, которые точно так же не могут быть доказаны, но, открытые Ньютоном, многократно подтверждены опытом. В силу тезиса Тьюринга невозможность построения машины Тьюринга означает отсутствие алгоритма решения данной проблемы. Изучение машин Тьюринга закладывает фундамент алгоритмического мышления, сущность которого состоит в том, что нужно уметь разделять процесс вычисления на простые составляющие шаги. В машине Тьюринга такое разделение доведено до предельной простоты. В современной ЭВМ алгоритмический процесс разделяется не на столь мелкие составляющие, как в машине Тьюринга. Наоборот, есть стремление укрупнить выполняемые машиной процедуры. Например, операция сложения в машине Тьюринга – целая программа, а в ЭВМ это простейшая функция. 68 Ответы на контрольные вопросы Тема 1 1. а) конъюнкция; б) эквивалентность; в) дизъюнкция; г) импликация. 2. б). 3. а), г). Тема 2. 1. б), в). 2. а) конъюнкция: б) дизъюнкция. 3. а), в), д), е). 4. б) – приведенная, в) – нормальная. 69 Указания к выполнению лабораторных работ Лабораторные работы проводятся с помощью системы компьютерного тестирования «МАТЛОГ» (лабораторные работы 1 – 3) и компьютерного интерпретатора машины Тьюринга «АЛГО» (лабораторная работа 4). Лабораторная работа №1. Логика высказываний Для выполнения этой работы требуется изучить следующие разделы логики высказываний: 1. Определение высказывания и операции над высказываниями 3. Формулы логики высказываний. Равносильность формул 5. Запись сложного высказывания в виде формулы логики высказываний 6. Тождественно-истинные, тождественно-ложные и выполнимые формулы 7. Формализация рассуждений. Правильные рассуждения Лабораторная работа №2. Логика предикатов Для выполнения этой работы требуется изучить следующие разделы логики предикатов: 1. Определение предиката 2. Кванторы. 3. Формулы логики предикатов 4. Равносильность формул 5 Приведенные и нормальные формулы 6. Выражение суждения в виде формулы логики предикатов 7. Интерпретация формулы логики предикатов в виде суждения 8. Выполнимость. Общезначимость Лабораторная работа №3. Формальные аксиоматические теории (исчисления). Нечеткая логика Для выполнения этой работы требуется изучить следующие разделы исчисления высказываний, исчисления предикатов и нечеткой логики: 1. Принципы построения формальных теорий 2. Вывод в исчислении высказываний 3. Вывод в исчислении предикатов 4. Метод резолюций. 5. Нечеткие множества 6. Нечеткие высказывания 7. Нечеткие предикаты 70 Лабораторная работа №4. Машина Тьюринга Эта лабораторная работа рассчитана на использование программной системы – интерпретатора машины Тьюринга. Порядок действий при этом следующий. Чтобы приступить к выполнению работы необходимо запустить систему «Алго»; выбрать в главном меню пункт "Интерпретатор"; затем выбрать пункт "Машина Тьюринга". Вся информация о работе с системой может быть получена нажатием кнопки «Помощь». 71 Контрольные задания по курсу "Математическая логика и теория алгоритмов" 1. Раздел «Логика высказываний» Задание 1. Установить, является ли данная формула тождественноистинной. 2. Данное высказывание записать в виде формулы логики высказываний. Построить отрицание данного высказывания в виде формулы, не содержащей внешних знаков отрицания. Перевести на естественный язык. 3. Установить, является ли данное рассуждение правильным, (проверить, следует ли заключение из конъюнкции посылок). Варианты индивидуальных заданий Вариант №1 1. (P  Q)  ((Q  R)  (P  R)). 2. Он и жнец, и швец, и на дуде игрец. 3. Если человек принял какое-то решение, и он правильно воспитан, то он преодолеет все конкурирующие желания. Человек принял решение, но не преодолел конкурирующих желаний. Следовательно, он неправильно воспитан. Вариант №2 1. (P  Q)  ((P  (Q  R))  (P  R)). 2. Идет дождь, и идет снег. 3. Если данное явление психическое, то оно обусловлено внешним воздействием на организм. Если оно физиологическое, то оно тоже обусловлено внешним воздействием на организм. Данное явление не психическое и не физиологическое. Следовательно, оно не обусловлено внешним воздействием на организм. Вариант №3 1. (P  R)  ((Q  R)  ((P V Q)  R)). 2. Он хороший студент или хороший спортсмен. 3. Если подозреваемый совершил кражу, то, либо она была тщательно подготовлена, либо он имел соучастников. Если бы кража была тщательно подготовлена, то, если бы были соучастники, украдено было бы много. Украдено мало. Значит, подозреваемый невиновен. 72 Вариант №4 1. (Q  R)  ((P V Q)  (P V R)). 2. Если стальное колесо нагреть, то его диаметр увеличится. 3. Если курс ценных бумаг растет, или процентная ставка снижается, то падает курс акций. Если процентная ставка снижается, то либо курс акций не падает, либо курс ценных бумаг не растет. Курс акций понижается. Следовательно, снижается процентная ставка. Вариант № 5 1. ((Q V (R  P))  (R & (P  Q))) V R . 2. Если воду охлаждать, то объем ее будет уменьшаться. 3. Либо свидетель не был запуган, либо, если Генри покончил жизнь самоубийством, то записка была найдена. Если свидетель был запуган, то Генри не покончил жизнь самоубийством. Записка была найдена. Следовательно, Генри покончил жизнь самоубийством. Вариант №6 1. ((P  Q)  (Q  R))& P  R. 2. Он учится в институте или на курсах иностранных языков. 3. Если философ – дуалист, то он не материалист. Если он не материалист, то он диалектик или метафизик. Он не метафизик. Следовательно, он диалектик или дуалист. Вариант №7 1. (Q V (R  P))  (R & (P  Q)). 2. Он способный и прилежный. 3. Если капиталовложения останутся постоянными, то возрастут правительственные расходы или возникнет безработица. Если правительственные расходы не возрастут, то налоги будут снижены. Если налоги будут снижены и капиталовложения останутся постоянными, то безработица не возрастет. Безработица не возрастет. Следовательно, правительственные расходы возрастут. Вариант №8 1. (P  Q)  ((Q  R)  (P  R)). 2. Эта книга сложная и неинтересная. 3. Если исходные данные корректны и программа работает правильно, то получается верный результат. Результат неверен. Следовательно, исходные данные некорректны или программа работает неправильно. 73 Вариант №9 1. (P  Q)  ((Q  R)  (P  R)). 2. Он и жнец, и швец, и на дуде игрец. 3. Если цены высоки, то и заработная плата высока. Цены высоки или применяется регулирование цен. Если применяется регулирование цен, то нет инфляции. Наблюдается инфляция. Следовательно, заработная плата высока.. Вариант №10 1. ((Q V (R  P))  (R & (P  Q))) V R. 2. Если воду охлаждать, то объем ее будет уменьшаться. 3. Если я устал, я хочу вернуться домой. Если я голоден, я хочу вернуться домой или пойти в ресторан. Я устал и голоден. Поэтому я хочу вернуться домой. Вариант №11 1. (P  Q)  ((Q  R)  (P  R)). 2. Если число оканчивается нулем, оно делится на 5. 3. Если завтра будет холодно, то я надену теплую куртку, если рукав будет починен. Завтра будет холодно, и рукав не будет починен. Значит, я не надену теплую куртку. Вариант №12 1. (P  Q)  ((P  (Q  R))  (P  R)). 2. Тело, лишенное опоры, падает на землю. 3. Если будет идти снег, машину будет трудно вести. Если будет трудно вести машину, я опоздаю, если не выеду пораньше. Идет снег, и я выеду пораньше. Значит, я не опоздаю. Вариант №13 1. (P  R)  ((Q  R)  ((P V Q)  R)). 2. Иван и Петр знают Федора. 3. Если человек говорит неправду, то он заблуждается или сознательно вводит в заблуждение других. Этот человек говорит неправду и явно не заблуждается. Значит, он сознательно вводит в заблуждение других. Вариант №14 1. (Q  R)  ((P V Q)  (P V R)). 2. Эта книга полезная и интересная. 3. Если бы он был умен, то он увидел бы свою ошибку. Если бы он был искренен, то он признался бы в ней. Однако, он не умен и не искренен. Следовательно, он или не увидит свою ошибку, или не признается в ней. 74 Вариант № 15 1. ((Q V (R  P))  (R & (P  Q))) V R . 2. Этот актер играет в театре и не играет в кино. 3. Если человек является материалистом, то он признает познаваемость мира, Если человек признает познаваемость мира, то он не является агностиком. Следовательно, если человек не является последовательным материалистом, то он – агностик. Вариант №16 1. ((P  Q)  (Q  R))& P  R. 2. Если собаку дразнить, она укусит 3. Если в мире есть справедливость, то злые люди не могут быть счастливы. Если мир есть создание злого гения, то злые люди могут быть счастливы. Значит, если в мире есть справедливость, то мир не может быть созданием злого гения Вариант №17 1. (Q V (R  P))  (R & (P  Q)). 2. Если вы владеете английским языком, вы справитесь с этой работой. 3. Если Иванов работает, то он получает зарплату. Если же Иванов учится, то он получает стипендию. Но Иванов не получает зарплату или не получает стипендию. Следовательно, он не работает или не учится. Вариант №18 1. (P  Q)  ((Q  R)  (P  R)). 2. Если функция нечетная, то ее график симметричен относительно начала координат. 3. Если я лягу спать, то не сдам экзамен. Если я буду заниматься ночью, то тоже не сдам экзамен. Следовательно, я не сдам экзамен. Вариант №19 1. (P  Q)  ((Q  R)  (P  R)). 2. Если число делится на 3, то сумма его цифр делится на 3. 3. Если я пойду завтра на первую лекцию, то должен буду встать рано. Если я пойду вечером на дискотеку, то лягу спать поздно. Если я лягу спать поздно, а встану рано, я буду плохо себя чувствовать. Следовательно, я должен пропустить первую лекцию или не ходить на дискотеку. Вариант №20 1. ((Q V (R  P))  (R & (P  Q))) V R. 75 2. Если слово ставится в начале предложения, то оно пишется с большой буквы. 3. Если x  0 и y  0, то x2 + y2 > 0. Если x = 0 и y = 0, то выражение (x – y):(x + y) не имеет смысла. Неверно, что x2 + y2 > 0. Следовательно, не имеет смысла выражение (x – y):(x + y). Вариант №21 1. (P  Q)  ((Q  R)  (P  R)). 2. Иван и Марья любят друг друга. 3. Если книга, которую я читаю, бесполезная, то она несложная. Если книга сложная, то она неинтересная. Эта книга сложная и интересная. Значит, она полезная. Вариант №22 1. (P  Q)  ((P  (Q  R))  (P  R)). 2. Плох тот солдат, который не мечтает стать генералом. 3. Если завтра будет дождь, я надену плащ. Если будет ветер, я надену куртку. Следовательно, если не будет дождя и ветра, я не надену ни плаща, ни куртки. Вариант №23 1. (P  R)  ((Q  R)  ((P V Q)  R)). 2. Если ряд сходится, то его общий член стремится к нулю. 3. Если он не трус, то он поступит в соответствии с собственными убеждениями. Если он честен, то он не трус. Если он не честен, то он не признает своей ошибки. Он признал свою ошибку. Значит, он не трус. Вариант №24 1. (Q  R)  ((P V Q)  (P V R)). 2. Ни Иван, ни Федор не отличники. 3. Если он упрям, то он может ошибаться. Если он честен, то он не упрям. Если он не упрям, то он не может одновременно не ошибаться и быть честным. Значит, он не упрям. Вариант № 25 1. ((Q V (R  P))  (R & (P  Q))) V R . 2. Либо Иван, либо Петр знают Федора. 3. Если зарплату выдают вовремя, то ожидаются либо выборы, либо акция протеста. Зарплату выдали вовремя. Выборы не ожидаются. Значит, ожидается акция протеста. Вариант № 26 1. (R  P)  ((P  Q)  (R  Q)). 2. Если составить алгоритм и написать программу, то можно решить эту задачу. 76 3. Если человек занимается спортом, то он здоров. Если человек здоров, то он счастлив, Этот человек занимается спортом. Значит, он счастлив. Вариант № 27 1. ((P  Q)  (Q  R)) V R . 2. Вечером мы пойдем на хоккей или будем смотреть его по телевизору. 3. Антон переутомился или болен. Если он переутомился, то он раздражается. Он не раздражается. Следовательно, он болен. Вариант № 28 1. (P&Q  R )V (Q&R  P). 2. Если я не выспался или голоден, я не могу заниматься. 3. Если фирма ориентирована на усиление маркетинга, то она намерена получить крупную прибыль на выпуске новых товаров. Если фирма предусматривает расширение торговой сети, то она намерена получить крупную прибыль от увеличения продаж. Фирма предусматривает усиление маркетинга или собирается расширить торговую сеть, Следовательно, она намерена получить крупную прибыль. Вариант № 29 1. ((P  Q)  (Q  R)) V R . 2. Если налоги не будут снижены, то мелкие производители разорятся и оставят производство. 3. Контракт будет выполнен тогда и только тогда, когда дом будет закончен в феврале. Если дом будет закончен в феврале То мы можем переехать в марте. Контракт будет выполнен, Следовательно, мы можем переехать в марте. Вариант № 30 1.  (P&Q  R)  Q. 2. Если наша команда не займет первое место, мы останемся дома и будем тренироваться. 3. Намеченная программа удастся, если застать противника врасплох или если его позиции плохо защищены. Захватить его врасплох можно, если он беспечен. Он не будет беспечен, если его позиции плохо защищены. Значит, программа не удастся. 77 2. Раздел «Логика предикатов» Задание 1. Установить, является ли данное выражение формулой, а если да, то определить, какие переменные в ней свободные, а какие связанные. 2. Даны предикаты: А(x) и B(x). Записать словами предложенные формулы С и D. 3. Данное суждение записать в виде формулы логики предикатов. Построить отрицание данного суждения в виде формулы, не содержащей внешних знаков отрицания. Перевести на естественный язык. Варианты индивидуальных заданий Вариант №1 1xy(A(x))&B(y, z)). 2. А(x) = "x – торговец подержанными автомобилями"; B(x) = "x – нечестный человек". Записать словами: C = x(A(x)  B(x)); D =  x(B(x) & A(x)). 3. Не всякое действительное число является рациональным. Вариант №2 1.xy(A(x, y)  C(z) &B(y, z))). 2. А(x) = "x – торговец наркотиками"; B(x) = "x – наркоман". Записать словами: C = x(A(x)  B(x)); D = x(A(x)&B(x)). 3. Каждый студент выполнил хотя бы одну лабораторную работу. Вариант №3 1. xy (A(x)  B(y, z)). 2. А(x) = "x – рациональное число"; B(x) = "x – действительное число". Записать словами: C = x(B(x) & A(x)); D = x(A(x)  B(x)). 3. Ни одно четное число, большее 2, не является простым. Вариант №4 1. xy (A(x)&B(y)) C(y, z)). 2. А(x) = "x – политик"; B(x) = "x – мошенник". C = x(A(x) B(x))); D = x(A(x)&B(x)). 3. Выгул собак или кошек запрещен. Вариант № 5 1. xy (A(x, y)&B(y, z))). 78 2. А(x) = "x – рыба"; B(x) = "x – водное животное". С = x(B(x) & A(x)); D = x(A(x) B(x)). 3. Произведение любых двух простых чисел не является простым числом. Вариант №6 1. xy (A(x))&B(y)). 2. А(x) = "x – четное число"; B(x) = "x делится на 6". Записать словами: C = x(B(x) A(x)); D = x((A(x)&B(x))). 3. Всякое положительное число больше всякого отрицательного числа. Вариант №7 1. xy (A(x)) B(y, z)). 2. А(x) = "x – металл"; B(x) = "x – теплопроводен". Записать словами: C = x(B(x) & A(x)); D = x(A(x)  B(x)). 3. Каждый, купивший билет, получит премию. Вариант №8 1. xy (A(x) B(y, z))). 2. А(x) = "x – простое число"; B(x) = "x четное число". Записать словами: C = x(B(x) A(x)); D = x((A(x)&B(x))). 3. Всякое положительное число больше всякого отрицательного числа. Вариант №9 1.xy(A(x, y)) B(y, z)). 2. А(x) = "x – студент"; B(x) = "x – сдал экзамены". Записать словами: C = x(B(x) & A(x)); D = x(A(x)  B(x)). 3. Всякий равносторонний треугольник является равнобедренным. Вариант №10 1. x(y(A(x)&B(y, z)). 2. А(x) = "x - деятельность"; B(x) = "x дает счастье". Записать словами: C = x(B(x) A(x)); D = x((A(x)&B(x))). 3. Некоторые студенты сдали все зачеты. Вариант №11 1(xz(A(x, y)  B(y, z)). 2. А(x) = "x – ученый"; B(x) = "x – мыслит формулами". Записать словами: C = x(A(x)  B(x)); D = x(B(x) & A(x)). 3. Все депутаты голосовали за этот законопроект. 79 Вариант №12 1.(x  z) &(y  x). 2. А(x) = "x – планета"; B(x) = "x светит собственным светом". Записать словами: C = x(A(x)  B(x)); D = x(A(x)&B(x)). 3. Все рыбы живут в воде. Вариант №13 1. A(x) &x B(x). 2. А(x) = "x – педагог"; B(x) = "x – учитель". Записать словами: C = x(B(x) & A(x)); D = x(B(x)  A(x)). 3. Некоторые абитуриенты поступили в институт. Вариант №14 1. x (A(x)  C(x))  x(A(x) B(x, y)). 2. А(x) = "x – морское животное"; B(x) = "x дышит жабрами". C = (x(A(x)  B(x))); D = x(A(x)& B(x)). 3. Студент ответил на некоторые вопросы. Вариант № 15 1. (A(x)  B(x) V (y(y D(y)). 2. А(x) = "x – гриб"; B(x) = "x съедобен". С = x(A(x) & B(x)); D = x(A(x)  B(x)). 3. Автобус останавливается на всех остановках. Вариант №16 1. xz(A(x, y) A(y, z)). 2. А(x) = "x – существительное"; B(x) = "x обозначает предмет". Записать словами: C = x(B(x) A(x)); D = x((A(x)&B(x))). 3. Некоторые зрители не любят некоторых артистов Вариант №17 1. xy A(x, y). 2. А(x) = "x – суждение"; B(x) = "x выражается предложением". Записать словами: C = x(A(x) B(x)); D = x((A(x)&B(x))). 3. В этой местности иногда бывает снег. Вариант №18 1. x,y A(x, y). 2. А(x) = "x – наука"; B(x) = "x гуманитарная". Записать словами: C = x(A(x) B(x)); D = x((A(x)&B(x))). 80 3. Не все металлы твердые. Вариант №19 1.x A(x) V y B(x, y). 2. А(x) = "x – газ"; B(x) = "x бесцветный". Записать словами: C = x(A(x) B(x)); D = x((A(x)&B(x))). 3. Некоторые студенты получают стипендию. Вариант №20 1. xy A(x, y) & B(y, z). 2. А(x) = "x – пассажир"; B(x) = "x платит за проезд". Записать словами: C = x(A(x) B(x)); D = x((A(x)&B(x))). 3. Некоторые книги полезны. Вариант №21 1.p x A(x, z). 2. А(x) = "x – товар"; B(x) = "x ввозится контрабандным путем". Записать словами: C = x(A(x) B(x)); D = x((A(x)&B(x))). 3. Существуют непрерывные функции, которые не являются дифференцируемыми. Вариант №22 1.x A(x, y)  B(y, z). 2. А(x) = "x – пошлина"; B(x) = "x взимается с цены товара". Записать словами: C = x(A(x) B(x)); D = x((A(x)&B(x))). 3. Он ничего не знает. Вариант №23 1. x(y(A(x)  &B(y, z)). 2. А(x) = "x – человек"; B(x) = "x знает, кто такой Альфред Брем". Записать словами: C = x(A(x) B(x)); D = x((A(x)&B(x))). 3. Некоторые пассажиры не платят за проезд. Вариант №24 1. x(y(A(x)&B(y))  C(y, z)). 2. А(x) = "x насекомое"; B(x) = "x беспозвоночное". Записать словами: С = x(A(x) & B(x)); D = x(A(x)  B(x)). 3. Не все полезное приятно. Вариант № 25 1. x(y(A(x, y)&B(y, z))). 2. А(x) = "x – рыба"; B(x) = "x дышит жабрами". Записать словами: C = x(A(x)  B(x)); D = x(A(x)& B(x)). 3. Не всякий газ бесцветен. 81 Вариант №26 1x(A(x, y) V y B(x, y)). 2. А(x) = "x – алгоритм"; B(x) = "x сходится". Записать словами: C = x(A(x)  B(x)); D = x(B(x) & A(x)). 3. Все люди хорошие. Вариант №27 1. x A(x, y)  B(x, y). 2. А(x) = "x – издательство"; B(x) = "x выпускает учебники". Записать словами: C = x(A(x) B(x)); D = x((A(x)&B(x))). 3. Некоторые студенты досрочно сдали экзамены. Вариант №28 1. x (A(x, y) zA(y, z)). 2. А(x) = "x – целое число"; B(x) = "x – рациональное число ". Записать словами: C = x(B(x) A(x)); D = x((A(x)&B(x))). 3. Не все государства подписали это соглашение. Вариант №29 1.xy (A(x, y)) B(y, z)). 2. А(x) = "x – осёл"; B(x) = "x упрям". Записать словами: C = x(B(x) & A(x)); D = x(A(x)  B(x)). 3. Не все спортсмены участвовали в соревновании. Вариант №30 1. xy(A(x, y)  B(y, z)). 2. А(x) = "x – дерево"; B(x) = "x лиственное". Записать словами: C = x(A(x) B(x)); D = x((A(x)&B(x))). 3. Некоторые автобусы не останавливаются на этой остановке. 82 3.1. Раздел «Формальные аксиоматические теории (исчисления)» Задание 1. Установить правильность рассуждения, построив вывод исчисления высказываний. 2. Установить правильность рассуждения, построив вывод исчисления предикатов. 3. Проверить вывод методом резолюций. Варианты индивидуальных заданий Вариант №1 1. Если философ дуалист, то он не материалист. Если он не материалист, то он метафизик. Этот философ дуалист. Следовательно, он метафизик. 2. Каждый студент честен. Джон нечестен. Значит, он не студент. 3. A (B VC), A, B  D, C  D├ D. Вариант №2 1. Если идет дождь, то крыши мокрые. Крыши не мокрые. Следовательно, дождя нет. 2. Каждый, кто силен и умен, добьется успеха. Петр силен и умен. Значит, Петр добьется успеха. 3. A (B VC), A V C, B├ C. Вариант №3 1. Если треугольник равносторонний, то его углы равны. Треугольник равносторонний. Следовательно, его углы равны. 2. Надежда еще не потеряна. Значит, еще не все потеряно. 3. A&C B , A, B  D, C├ D. Вариант №4 1. Если это преступление совершил Смит, то он знает, где находятся похищенные деньги. Смит не знает, где находятся похищенные деньги. Следовательно, он не совершал преступления. 2. Всякий, кто не может решить эту задачу – не математик. Иван не может решить эту задачу. Значит, Иван не математик. 3. A V B, A C, B  D├ C V D. 83 Вариант № 5 1. Если не зафиксировано изъятие следов преступной деятельности в протоколе, то процессуальный порядок следственного действия не соблюден. Процессуальный порядок следственного действия соблюден. Следовательно, изъятие следов преступной деятельности зафиксировано в протоколе. 2. Все металлы теплопроводны. Дерево не теплопроводно. Значит, дерево не металл. 3. A, C, A&C D, D  B├ B. Вариант №6 1. Этот человек инженер или рабочий. Он не инженер. Следовательно, он рабочий. 2. Все медсестры – медицинские работники. Все медицинские работники имеют право на льготы. Следовательно, все медсестры имеют право на льготы. 3. A (B VC), A  B, C├ B. Вариант №7 1. Если студент занимается не систематически, то он не имеет прочных знаний Если он не имеет прочных знаний, то он не будет хорошим специалистом. Следовательно, если студент занимается не систематически, то он не будет хорошим специалистом. 2. Все собаки обладают хорошим обонянием. Джек – собака. Следовательно, Джек обладает хорошим обонянием. 3. A, A (B C), B  D, C ├ D. Вариант №8 1. Это вещество может быть кислотой либо щелочью. Это вещество не щелочь. Следовательно, это кислота. 2. Этому никто не поверит. Значит, судья этому не поверит. 3. (A  C )  (A B)├ A V B. Вариант №9 1. Если прямая касается окружности, то радиус, проведенный в точку касания, перпендикулярен к ней. Радиус окружности не перпендикулярен к этой прямой. Следовательно, прямая не касается окружности. 2. Все натуральные числа – целые. 5 – натуральное число. Значит, 5 – целое число. 3. B VC, C  A, B  D, D A ├ A. 84 Вариант №10 1. Если человек знает геометрию, то он знает теорему Пифагора, Этот человек не знает теорему Пифагора. Следовательно, он не знает геометрию. 2. Всякое положительное целое число есть натуральное число. Число 7 – положительное целое число. Следовательно, 7 – натуральное число. 3. B (D  C), D, C  A V B)├ A V B. Вариант №11 1. Если слово ставится в начале предложения, то оно пишется с большой буквы. Это слово написано с маленькой буквы. Следовательно, это слово не стоит в начале предложения. 2. Все дельфины – киты. Ни один кит не является рыбой Следовательно, все дельфины – не рыбы. 3. B  (C  A), B D, D  C, ├ C. Вариант №12 1. Если функция четная, то ее график симметричен относительно оси OY. График несимметричен относительно оси OY. Следовательно, функция не является четной. 2. Этому никто не поверит. Следовательно, судья этому не поверит. 3. B C  A), B  D, C, D├ A. Вариант №13 1. Если светофор зеленый, то проезд разрешен. Проезд не разрешен. Значит, светофор не зеленый. 2. Всякое четное число, большее 4-х, является суммой двух простых чисел (гипотеза Гольдбаха). 26 – четное число, большее 4-х. Следовательно, 26 является суммой двух простых чисел. 3. C, D  C, A  (B  D), B ├ A  C. Вариант №14 1. Если нет понятых, то обыск производить нельзя. Обыск можно производить. Следовательно, есть понятые. 2. Во всяком равностороннем треугольнике углы равны. В этом треугольнике углы не равны, Следовательно, этот треугольник не равносторонний. 3. C  (B  A), B  D, C ├ A VD. 85 Вариант № 15 1. Плох тот солдат, который не мечтает стать генералом. Этот солдат хороший. Следовательно, он мечтает стать генералом. 2. Все, что имеет причину, не является случайным. Это явление имеет причину, следовательно, это явление не является случайным. 3. A  (C  B), D  A, C ├ D B. Вариант №16 1. Если треугольник равносторонний, то он равнобедренный. Если треугольник равнобедренный, то углы при основании равны. Следовательно, если треугольник равносторонний, то углы при основании равны. 2. Все трусы – эгоисты. Иван – не эгоист. Следовательно, Иван – не трус. 3. A, B C├ (A  C)  B. Вариант №17 1. Если спутник Земли пролетает над Южным полюсом, то он пролетает над Антарктидой. Этот спутник не пролетает над Антарктидой. Следовательно, он не пролетает над Южным полюсом. 2. Все математики обладают способностью к быстрому счету. Все программисты – математики. Следовательно, все программисты обладают способностью к быстрому счету. 3. A  (C  B), D  A, C ├ D B. Вариант №18 1. Петров студент или школьник. Он не школьник. Следовательно, он студент. 2. Все заряженные частицы отклоняются в магнитном поле. Нейтрон не отклоняется в магнитном поле. Следовательно, нейтроны не имеют заряда. 3. A, A (B C), B  D, C ├ D. Вариант №19 1. Если солнце взошло, то настало утро. Утро не настало. Значит, солнце не взошло. 2. Все металлы являются кристаллическими веществами. Все кристаллические вещества имеют определенную температуру плавления. Следовательно, все металлы имеют определенную температуру плавления. 3. B (D  C), D, C  A V B)├ B A. 86 Вариант №20 1. Если Федор победит на соревнованиях, он войдет в сборную страны. Если он войдет в сборную страны, то будет участвовать в чемпионате мира. Следовательно, если Федор победит на соревнованиях, он будет участвовать в чемпионате мира. 2. Все жидкости упруги. Воск не упруг. Следовательно, воск не жидкость. 3. A (B VC), A V C, B├ C. Вариант №21 1. Если эта собака не обучена, ее нельзя отпускать без поводка. Эту собаку можно отпускать без поводка. Значит, эта собака обучена. 2. Все квадраты – ромбы. Эта фигура – не ромб. Следовательно, эта фигура – не квадрат. 3. A&C B , A, D B, C├ D. Вариант №22 1. Если я устал, то не могу готовиться к занятиям. Если я не смогу приготовиться к занятиям, я не напишу контрольную работу. Я устал. Значит, я не напишу контрольную работу. 2. Все студенты нашей группы сдали зачет по математике. Иван не сдал зачет по математике. Следовательно, Иван – не студент нашей группы. 3. B VC, C  A,D B, D A ├ A. Вариант №23 1. Если есть указание директора или его заместителя, пропуск может быть получен. Есть указание заместителя директора. Следовательно, пропуск может быть получен. 2. Все спортсмены имеют хорошее здоровье. У Федора плохое здоровье. Следовательно, Федор – не спортсмен. 3. C, D  C, A  (D B), B ├ A. Вариант №24 1. Если не везет в картах, то везет в любви. Ему не везет в картах. Значит, ему везет в любви. 2. Все врачи давали клятву Гиппократа. Иванов – врач. Следовательно, Иванов давал клятву Гиппократа. 3. A (B VC), A  B, C├ B. 87 Вариант № 25 1. На работу в это учреждение принимают, если пройдешь собеседование и будешь аттестован положительно. Его не приняли. Значит, он либо не прошел собеседование, либо не был положительно аттестован. 2. Все планеты вращаются вокруг своей оси. Земля – планета. Следовательно, Земля вращается вокруг своей оси. 3. C, A&C D, B D├ B. Вариант № 26 1. Если рабочий отсутствовал на работе, он не выполнил задания. Рабочий был на работе. Следовательно, он выполнил задание. 2. В любом издательстве среди книг найдется такая, в которой есть страница, содержащая более двух опечаток. Следовательно, среди книг издательства ”Подкова” есть страница, содержащая более двух опечаток. 3.AVC, C  B, B  A├ A B  C). Вариант №27 1. Если растение лекарственное, его следует охранять. Это растение не подлежит охране. Следовательно, оно не лекарственное. 2. Никакой числовой ряд, у которого общий член не стремится к нулю, не сходится. У этого числового ряда общий член не стремится к нулю. Следовательно, этот числовой ряд не сходится. 3.AC, A  B, C  B, ├ A B  C). Вариант №28 1. Петров женат на Марье Ивановне или Лукерье Ильиничне. Он не женат на Марье Ивановне. Следовательно, он женат на Лукерье Ильиничне. 2. Все планеты – спутники Солнца. Земля – планета. Следовательно, Земля – спутник Солнца. 3. A, A (B C), D  B, C ├ D. Вариант №29 1. Если отклонение параметров превышает стандарты, то требуется корректировка программы или уточнение стандартов. Выявленное отклонение превышает стандарты. Следовательно, требуется корректировка прграммы или уточнение стандаортов. 88 2. Во всяком равнобедренном треугольнике углы при основании равны. В этом треугольнике углы при основании не равны. Следовательно, этот треугольник не равнобедренный. 3. A&C B, B D, A, C├ D. Вариант №30 1. Если диагноз подтвердится, то Ивану придется лечь в больницу. Если Иван ляжет в больницу, то поездку придется отменить. Диагноз подтвердился. Значит, поездку придется отменить. 2. Всякое натуральное число – целое. Это число не целое. Значит, оно не натуральное. 3. B C, C  A,D B, D A ├ A. 89 3.2 Раздел «Нечеткая логика» Задание ~ ~ Определить степень равносильности формул A и B при ~ ~ условии, что X и Y принимают значения степеней истинности из множества {0,2; 0,3}. Варианты индивидуальных заданий № 1 2 3 4 5 6 7 8 9 10 ~ A ~ ~ X  Y ~ ~  X V Y ~ ~ X &Y ~ X ~ ~ Y  X  ~ ~ X  Y  ~ ~ X & Y ~ Y  ~ ~ Y X  ~ X ~ B ~ ~  X & Y ~ ~ X & Y ~ ~ X  Y ~ ~  X V Y ~ ~ X & Y ~ Y ~ X ~ ~  X  Y  ~ ~ X V Y  ~ ~ Y X № 11 12 13 14 15 16 17 18 19 20 ~ A ~ ~ Y & X ~ ~ Y X ~ X ~ ~  X &Y ~ ~ Y V X ~  Y  ~ ~ X  Y  ~ Y ~ ~ X & Y  ~ ~ Y &X ~ B ~ ~  X  Y ~ ~  X V Y ~ ~ X & Y ~ ~ X V Y ~ Y ~ ~  X  Y  ~ ~  X & Y  ~ ~  X  Y  ~ X ~ ~  X V Y № 21 22 23 24 25 26 27 28 29 30 ~ A ~ ~ X  Y ~ ~ Y  X  ~ Y ~ X ~ ~ Y  X  ~ ~  X  Y  ~ Y ~ ~ Y X  ~ Y  ~ ~ Y V X ~ B ~ ~ X V Y ~ ~ Y & X ~ ~ X  Y ~ ~ X V Y ~ ~ X & Y ~ Y  ~ ~  X & Y  ~ ~ X V Y  ~ ~  X  Y  ~ ~ X & Y 90 4. Раздел «Теория алгоритмов» Задание Составить программу машины Тьюринга, которая заданное слово Pвх преобразует в слово Pвых. Варианты индивидуальных заданий № 1 2 3 4 5 6 Pвх 000 000 000 001 001 001 Pвых 0000 0001 111 0010 0011 110 № 7 8 9 10 11 12 Pвх 010 010 010 011 011 011 Pвых 0100 0101 101 1010 1011 010 № 13 14 15 16 17 18 Pвх 100 100 100 101 101 101 Pвых 1000 1001 010 1010 1011 010 № 19 20 21 22 23 24 Pвх 110 110 110 111 111 111 Pвых 1100 1101 001 1110 1111 0001 № 25 26 27 28 29 30 Pвх 000 001 010 011 100 101 Pвых 001 101 0111 0111 011 001 91 Список рекомендованной литературы 1. Акимов О. Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001. 2. Ашинянц Р. А. Логические методы в искусственном интеллекте. – М.: МГАПИ, 1996. 3. Гиндикин С. Г. Алгебра логики в задачах. – М.: Наука, 1972. 4. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. – М.: Энергоиздат, 1988. 5. Лихтарников Л. М., Сукачева Т. Г. Математическая логика. Курс лекций. Задачник-практикум и решения. Изд-во “Лань”, 1999. 6. Нефедов В. Н., Осипова В. А. Курс дискретной математики. – М.: Издательство МАИ, 1992. 7. Новиков П. С. Элементы математической логики. – М.: Наука, 1973. 8. Новиков Ф. А. Дискретная математика для программистов. – СПб.: Питер, 2002. 9. Судоплатов С. В., Овчинникова В. В. Элементы дискретной математики. – М.: ИНФРА – М, Новосибирск: Изд-во НГТУ, 2002. 10. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. – М.: Наука, 1983. 92 Краткие сведения о математиках 1. Аристотель (384 –322 до н. э.) – древнегреческий философ и ученый. Его работы охватывают почти все доступные его времени отрасли знания. Является основателем логики как научной дисциплины. 2. Буль Джордж (1815 – 1864) – английский математик. Основатель математической логики. 3. Гильберт Давид (1862 – 1943) – немецкий математик. Оказал влияние на развитие многих разделов математики. Работал над проблемой создания логических основ математики. 4. Заде Лотфи – американский математик. Разработал основные принципы теории нечетких множеств. 5. Тьюринг Алан Матисон (1912 – 1954) – английский математик. Основные работы по математической логике и вычислительной математике. Ввёл математическое понятие уточнённого абстрактного эквивалента алгоритма, или вычислимой функции (получившее впоследствии название машина Тьюринга). В последние годы жизни работал над математическими проблемами биологии. 6. Фреге Готлоб (1848 – 1825) – немецкий математик. Предложил систему формализованной арифметики на основании разработанного им расширенного исчисления предикатов. 93