- •Раздел 1. Алгебраические структуры Тема 1.1. Бинарные операции и их свойства
- •Тема 1.2. Алгебраические структуры
- •Тема 1.3. Основные свойства групп
- •Тема 1.4. Поля и кольца
- •Раздел 2. Алгебра множеств Тема 2.1. Основные определения теории множеств
- •Тема 2.2. Подмножество, понятие универсального множества
- •Тема 2.3. Операции над множествами
- •Раздел 3. Основные теоремы комбинаторики
- •Тема 3.1. Метод математической индукции
- •Тема 3.2. Основные принципы комбинаторики
- •Раздел 4. Комбинаторные объекты Тема 4.1. Сочетания
- •Тема 4.2. Размещения и перестановки
- •Раздел 5. Полиномиальные тождества Тема 5.1. Бином Ньютона
- •Тема 5.2. Понятие о методе рекуррентных соотношений
- •Тема 5.3. Метод производящих функций
- •Тема 5.4. Метод траекторий
- •Тема 5.5. Примеры комбинаторных задач
- •Раздел 6. Соответствие, отношение, отображение Тема 6.1. Понятие кортежа. Декартово произведение множеств
- •Тема 6.2. Определения и свойства
- •Тема 6.3. Типы отношений
- •Пересечение и объединение отношений
- •Композиция отображений и отношений
- •Тема 6.5. Решётки
- •Тема 6.4. Верхняя и нижняя границы множества.
- •Раздел 7. Операции булевой алгебры Тема 7.1.Понятие высказывания, простые и составные высказывания
- •Тема 7.2.Операции на множестве высказываний
- •Отрицание
- •Конъюнкция
- •Дизъюнкция
- •«Исключающее или»
- •Импликация
- •Эквивалентность
- •Штрих Шеффера
- •Раздел 8. Законы и тождества Булевой алгебры Тема 8.1.Формулы Булевой алгебры
- •Тема 8.2.Законы и тождества Булевой алгебры
- •Тема 8.3.Составление формулы по заданной таблице истинности
- •Тема 8.4. Двойственность
- •Тема 8.5.Булева алгебра и теория множеств
- •Тема 8.6.Днф, интервалы и покрытия
- •Раздел 9. Функциональная полнота. Алгебра Жегалкина
- •Тема 9.1.Функционально полные системы
- •Тема 9.2.Алгебра Жегалкина и линейные функции
- •Тема 9.3.Замкнутые классы. Монотонные функции
- •Тема 9.4.Теоремы о функциональной полноте
- •Раздел 10. Хорновские формулы
- •Тема 10.1.Задача получения продукции
- •Тема 10.2.Решение задачи о продукции
- •Алгоритм замыкание(X,f)
- •Алгоритм ПрямаяВолна(X,y,f)
- •Алгоритм БыстроеЗамыкание(X,f)
- •Раздел 11. Теория релейно-контактных схем Тема 11.1.Основные понятия
- •Тема 11.2.Основные задачи теории релейно-контактных схем
- •Тема 11.3.Построение машины голосования
- •Тема 11.4.Двоичный сумматор
- •Тема 11.5.Методы упрощения логических выражений. Методы решения логических задач
- •Раздел 12. Логика предикатов Тема 12.1.Определение предиката
- •Тема 12.2.Логические операции над предикатами
- •Тема 12.3.Кванторы
- •Тема 12.4. Истинные формулы и эквивалентные соотношения
- •Тема 12.5.Доказательства в логике предикатов
- •Раздел 13. Теория графов
- •Тема 13.1.Основные определения теории графов
- •Тема 13.2. Способы задания графов
- •Тема 13.3. Отношения порядка и эквивалентности на графе
- •Тема 13.4. Числовые характеристики графа
- •Тема 13.5.Изоморфизм графов
- •Раздел 14. Проблемы достижимости на графах Тема 14.1.Граф достижимости
- •Тема 14.2.Взаимная достижимость, компоненты сильной связности и базы графа
- •Раздел 15. Некоторые классы графов Тема 15.1.Деревья
- •Тема 15.2. Обход графа
- •Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.
- •Раздел 16. Машина Тьюринга
- •Тема 16.1. Формальное описание машины Тьюринга
- •Тема 16.2. Примеры построения машины Тьюринга
- •Тема 16.3. Свойства машины Тьюринга как алгоритма
- •Раздел 17. Машина Поста
- •Тема 17.1. Теоретическая часть. Состав машины Поста
- •Тема 17.2. Применимость программ. Определение результата выполнения программ
- •Раздел 18. Основные понятия теории автоматов Тема 18.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации
- •Тема 18.2. Способы задания конечного автомата
- •Тема 18.3. Эквивалентные автоматы
- •Тема 18.4. Автоматы Мура и Мили
- •Тема 18.5. Примеры синтеза автоматов
Тема 11.5.Методы упрощения логических выражений. Методы решения логических задач
Рассмотрим пример решения логической задачи.
Пример 11.2:
После обсуждения состава участников экспедиции решено, что должны выполняться два условия:
если поедет Арбузов, то должны ехать Брюквин или Вишневский;
если поедут Арбузов и Вишневский то поедет Брюквин.
Составить логическую формулу принятия решения в символической форме, упростить полученную формулу и сформулировать по ней новое условие формирования экспедиции.
Введём переменные и соответствующие им элементарные высказывания.
- поедет Арбузов;
- поедет Брюквин;
- поедет Вишневский.
Тогда выработанные условия формирования экспедиции будут выглядеть следующим образом:
Составим общую формулу и упростим выражение
т.е. если поедет Арбузов, то поедет Вишневский.
Пример 11.3:
Если завтра будет хорошая погода, то мы пойдем на пляж или поедем в лес. Составим формулу нашего поведения на завтра.
– хорошая погода
– мы пойдем на пляж
– мы поедем в лес
Теперь построим отрицание этой фразы
т.о. получим высказывание «Завтра будет хорошая погода, и мы не пойдем в лес и на пляж».
Желающие могут построить таблицу истинности и проверить это утверждение.
Пример 11.4:
По подозрению в совершенном преступлении, задержаны Браун, Джон и Смит. Один из них уважаемый в городе старик, второй чиновник, а третий известный мошенник. В ходе следствия старик говорил правду, мошенник лгал, а третий задержанный в одном случае говорил правду, а в другом лгал.
Вот что они говорили:
Браун: «Я совершил это. Джон не виноват»
Джон: «Браун не виноват. Преступник Смит»
Смит: «Я не виноват. Виноват Браун»
Опишем эти высказывания формально:
- преступление совершил Браун;
- преступление совершил Джон;
- преступление совершил Смит.
Тогда их слова описываются следующими выражениями:
Браун:
Джон:
Смит:
Т.к. по условиям задачи две из этих & ложны и одна истинна, то
Составим таблицу истинности
NN | |||||||
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
3 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
5 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
6 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
7 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
8 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
Исключим из рассмотрения те наборы, на которых (по условию задачи одна из & - истинна, следовательно,) 1, 3, 8
Исключим случай 5, т.к. в нем две & истинны, что противоречит условию задачи.
В случаях 4, 6, 7 у нас в начальном наборе две 1 , т.е. 2 преступника, а по условию задачи он один.
Остаётся только случай 2 , т.е. преступник Смит, и оба его высказывания ложны.
следовательно– ложно и- истинно
– Джон уважаемый старик
Остаётся, что Браун чиновник, и поскольку – ложно , то– истинно.
Пользуясь законами и тождествами булевой алгебры можно упрощать логические выражения.
Пример 11.5:
Упражнение:
Раздел 12. Логика предикатов Тема 12.1.Определение предиката
Утверждения, которые можно сформулировать с помощью средств логики высказываний всегда относятся к конкретным свойствам конкретных предметов, объектов, ситуаций. Мы уже сталкивались с примерами таких утверждений: «Сегодня идёт дождь», «Вася любит Олю», «Если А – преступник, то В – не виновен», «Если цена на нефть растёт и страна продаёт нефть, то растут и доходы её бюджета» и т.п. Эти утверждения строятся из элементарных высказываний с помощью логических операций. Например, последнее из приведённых утверждений может быть формально записано как .
где ,и– это переменные, обозначающие, соответственно, высказывания «цена на нефть растёт», «страна продаёт нефть» и «растут и доходы бюджета».
Для того, чтобы высказывать более общие точные утверждения о свойствах классов (множеств) объектов, предметов, ситуаций, нужен более богатый формальный язык. Им является язык логики предикатов.
Прежде, чем переходить к формальным определениям, приведём некоторые содержательные примеры используемых понятий: объектов, свойств, отношений и операций (функций).
Объекты: люди, предприятия, числа, цвета, футбольные матчи, экзамены, дома, столы, компьютеры, фигуры, студенты, ...
Свойства: зелёный, тяжёлый, голубоглазый, победный, девятиэтажный, деревянный, отличник, ...
Отношения: «... является братом ...», «... занимает должность ... с зарплатой ...», «... больше чем ...», «... находится внутри ...», «... любит ...», «... имеет цвет ...», «... случится после ...», «... владеет ...», и т.п.
Функции: «отец ...», «лучший_ друг ...», «вдвое_больший_ чем ...», «сумма ... и ...», «группа_студента ...», «самый_любимый_кинофильм ...», ...
В примерах отношений и функций многоточиями отмечены места, где должны стоять объекты, к которым они относятся.
Даже этих небольших перечислений достаточно, чтобы понять, что язык логики предикатов позволяет описать почти любой факт и сформулировать нужное утверждение о той или иной рассматриваемой предметной области. Вот несколько простых примеров:
«Предикат» с английского переводится как сказуемое. Но говорить «логика сказуемых» – себя не уважать. Формально предикатом называется функция, аргументами которой могут быть произвольные объекты из некоторого множества, а значения функции «истина» или «ложь». Предикат можно рассматривать как расширение понятия высказывания.
Пример 12.1:
Вместо трёх высказываний: «Маша любит кашу», «Даша любит кашу», «Саша любит кашу» можно написать один предикат: «Икс любит кашу» и договориться, что вместо неизвестного Икс могут быть либо Маша, либо Даша, либо Саша. Подстановка вместо Икс имени конкретного ребёнка превращает предикат в обычное высказывание.
Определение:Пусть– произвольные переменные. Эти переменные будем называтьпредметными. Пусть наборы переменныхвыбираются из множества, которое будем называтьпредметной областью. Предикатом местности(- местным предикатом), определённым на предметной области, называют отображение множестваво множество высказываний.
Обозначение: –- местный предикат, определённый на.
Дадим другое определение предиката.
Определение: - местный предикат– это связное повествовательное предложение, содержащеепеременных и обладающее следующим свойством: при фиксации значений всех переменных о нём (предложении) можно сказать, истинно оно или ложно.
Пример 12.2:
а). = «Натуральное числоделится (без остатка) на натуральное число» – двуместный предикат, определённый на множестве пар натуральных чисел.
Очевидно ,.
б). – одноместный предикат, определённый на.
Ясно, что ,и вообще предикат– тождественно ложен, т.е. при любом значениеполучим.
в). – трёхместный предикат, определённый на.
,
Определение:Пусть–-местный предикат, определённый на.–множество ложности предиката. (т.е. множество ложности предиката– это множество тех, при которых значение истинности предиката равно нулю).
– множество истинности предиката. (т.е. множество истинности – это множество тех, при которых значение истинности предиката равно 1).
Определение:Предикат, определённый на, называетсятождественно истинным, если его значение истинности равно единице при всех возможных значениях (или, коротко,); тождественно ложным, если его значение истинности равно нулю при всех возможных значениях(или, коротко,); нетривиально выполнимым, если его значения истинности могут быть равными как единице, так и нулю (или, коротко,;.
Пример 12.3:
Изобразим в предикат
Поверхность и внутренность изображенного параболоида вращения – множество истинности предиката (т.к. значения; внешность параболоида – множество ложности(т.к..