УМКД «Элементы математической логики»


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный университет» (ДВФУ)
Филиал ДВФУ в г. Арсеньеве
СОГЛАСОВАНО УТВЕРЖДАЮ
зам.директора по УР колледжа филиала ДВФУ директор колледжа филиала ДВФУ в г. Арсеньеве в г.Арсеньеве
_________________ Е.Е.Пригарина _________________С.И. Белова
«___» ________________201_г. «___» ________________201_г.
УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ДИСЦИПЛИНЫ
«_Элементы математической логики__»
Специальность_230401 Информационные системы (по отраслям)__________
Шифр и название специальности
Форма обучения (очная)
ПЦК №2 Математических, общих естественно научных дисциплин и специальных дисциплин (по специальности 230401).
Наименование ПЦК
Курс 2_ семестр 4 _
Теоретическое обучение 48_ час.
Практические занятия _20_ час.
Семинарские занятия _0_ час.
Лабораторные работы _0_ час.
Всего часов аудиторной нагрузки 68 _ час
Максимальная нагрузка 102 часа
Самостоятельная работа 34__ час.
Зачет __ семестр
Экзамен 4___ семестр
Рабочая программа составлена в соответствии с требованиями федерального государственного образовательного стандарта среднего профессионального образования, утвержденного Минобрнауки Российской Федерации от 23.06.2010_№_688
(дата)
Рабочая программа обсуждена на заседании ПЦК №2 Математических, общих естественно научных дисциплин и специальных дисциплин (по специальности 230401) протокол от ___________
Председатель ПЦК № 2___________ И.С.Чухно (подпись) (и.о. фамилия)
Составитель(ли) преподаватель ____________ И.С. Чухно
(должность) (подпись) (и.о. фамилия)
ДАЛЬНЕВОСТОЧНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
Положения об учебно-методических комплексах дисциплин образовательных программ среднего профессионального образования.
Разработчик
Чухно И.C. Идентификационный номер Лист
Учебно-методический комплекс дисциплины «Элементы математической логики» разработан для студентов 2 курса по специальности 230401 Информационные системы (по отраслям) в соответствии с требованиями ФГОС СПО по данной специальности и положением об учебно-методических комплексах дисциплин образовательных программ среднего профессионального образования.
Общая трудоёмкость освоения дисциплины по очной форме обучения 102 часа.
Учебным планом предусмотрены теоретическое обучение 48 час. самостоятельная работа студента 34 час.
Дисциплина реализуется на 2 курсе в 4 семестре.
Изучение дисциплины необходимо «Элементы математической логики» для: вооружения учащихся математическими знаниями, необходимыми для изучения ряда общенаучных дисциплин и дисциплин профессионального цикла;
создания фундамента математического образования, необходимого для получения профессиональных компетенций;
воспитания математической культуры и понимания роли математики в различных сферах профессиональной деятельности.
Дисциплина «Элементы математической логики» логически и содержательно связана с такими курсами, как «Математика», «Информатика» и др.
Дисциплина направлена на формирование общепрофессиональных компетенций выпускника.
Учебно-методический комплекс включает в себя:
рабочую учебную программу дисциплины и планы;
конспекты уроков;
материалы для организации самостоятельной работы студентов;
контрольно-оценочные средства (тесты, индивидуальные задания, экзаменационные задания и вопросы);
глоссарий
список литературы
Достоинством данного УМКД является список ссылок на интернет-ресурсы, включающие учебники, задачники, примеры решений. В разделе «Контрольно-оценочные средства» представлены наборы индивидуальных заданий.
Автор-составитель учебно-методического комплекса
Преподаватель математики И.С.Чухно
Председатель ПЦК№2 И.C. ЧухноМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный университет» (ДВФУ)
Филиал ДВФУ в г. Арсеньеве
СОГЛАСОВАНО УТВЕРЖДАЮ
директор колледжа филиала ДВФУ Врио директора филиала ДВФУ
в г. Арсеньеве в г.Арсеньеве
_________________ C.И.Белова _________________С.В.Чикризов«___» ________________201_г. «___» ________________201_г.
РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ
«Элементы математической логики»
Специальность ___230401 Информационные системы (по отраслям)___________
Шифр и название специальности
Форма обучения (очная)
ПЦК №2 Математических, общих естественно научных дисциплин и специальных дисциплин (по специальности 230401).
Наименование ПЦК
Курс 2_, семестр 4 _
Теоретическое обучение 48_ час.
Практические занятия _20_ час.
Семинарские занятия _0_ час.
Лабораторные работы _0_ час.
Всего часов аудиторной нагрузки 68 _ час
Самостоятельная работа 34__ час.
Максимальная нагрузка 102 часа
Зачет __ семестр
Экзамен 4___ семестр
Рабочая программа составлена в соответствии с требованиями федерального государственного образовательного стандарта среднего профессионального образования, утвержденного
Минобрнауки Российской Федерации от 23.06.2010_№_688
(дата)
Рабочая программа обсуждена на заседании ПЦК №2 Математических, общих естественно научных дисциплин и специальных дисциплин (по специальности 230401)
протокол от ____________ № _________
Председатель ПЦК № 2___________ И.С.Чухно (подпись) (и.о. фамилия)
Составитель(ли) преподаватель ____________ И.С. Чухно
(должность) (подпись) (и.о. фамилия)

Рабочая программа пересмотрена на заседании ПЦК
Протокол от «___» ___________________ 20__г. №____
Председатель ПЦК _________________ _____________________
(подпись) (и.о. фамилия)

Изменений нет.
Рабочая программа пересмотрена на заседании ПЦК
Протокол от «___» ___________________ 20__г. №____
Председатель ПЦК _________________ _____________________
(подпись) (и.о. фамилия)

Изменений нет.
СОДЕРЖАНИЕ
ПАСПОРТ РАБОЧЕЙ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ 4
СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ 6
УСЛОВИЯ РЕАЛИЗАЦИИ УЧЕБНОЙ ДИСЦИПЛИНЫ 9
КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ 10
Паспорт программы учебной дисциплины
«Элементы математической логики»
1.1 Область применения рабочей программы
Рабочая программа учебной дисциплины Элементы математической логики является частью основной профессиональной образовательной программы в соответствии с ФГОС СПО по специальности 230401 Информационные системы (по отраслям), входящей в состав укрупненной группы специальностей 230000 Информатика и вычислительная техника, по направлению подготовки 230400 Информационные системы и технологии
1.2. Место дисциплины в структуре основной профессиональной образовательной программы: программа входит в общеобразовательный цикл
1.3. Цели и задачи дисциплины – требования к результатам освоения дисциплины:
В результате освоения дисциплины обучающийся должен уметь:
формулировать задачи логического характера и применять средства математической логики для их решения;
В результате освоения дисциплины обучающийся должен знать:
основные принципы математической логики, теории множеств и теории алгоритмов;
формулы алгебры высказываний;
методы минимизации алгебраических преобразований;
основы языка и алгебры предикатов
В результате освоения дисциплины должен быть сформированы компетенции
ОК 1. Понимать сущность и социальную значимость своей будущей профессии, проявлять к ней устойчивый интерес
ОК 2. Организовывать собственную деятельность , выбирая типовые методы и способы выполнения профессиональных задач, оценивать их эффективность и качество.
ОК 3. Принимать решения в стандартных и нестандартных ситуациях и нести за них ответственность
ОК 4. Осуществлять поиск и использование информации, необходимой для эффективного выполнения профессиональных задач, профессионального и личностного развития
ОК 5. Использовать информационно-коммуникационные технологии в профессиональной деятельности.
ОК 6. Работать в коллективе и команде, эффективно общаться с коллегами, руководством, потребителями
ОК 7. Брать на себя ответственность за работу членов команды (подчиненных), результат выполнения заданий.
ОК 8. Самостоятельно определять задачи профессионального и личностного развития, заниматься самообразованием, осознанно планировать повышение квалификации
ОК 9. Ориентироваться в условиях частой смены технологий в профессиональной деятельности.
ОК 10. Исполнять воинскую обязанность , в том числе с применением полученных профессиональных знаний (для юношей)
ПК 1.1 Собирать данные для анализа использования и функционирования информационной системы, участвовать в составлении отчетной документации, принимать участие в разработке проектной документации на модификацию информационной системы.
ПК 1.2. Взаимодействовать со специалистами смежного профиля при разработке методов, средств и технологий применения объектов профессиональной деятельности
ПК 1.4. Участвовать в экспериментальном тестировании информационной системы на этапе опытной эксплуатации, фиксировать выявленные ошибки кодирования в разрабатываемых модулях информационной системы.
ПК 2.3. Применять методики тестирования разрабатываемых приложений

1.4. Рекомендуемое количество часов на освоение программы дисциплины:
максимальной учебной нагрузки обучающегося 102 часов, в том числе:
обязательной аудиторной учебной нагрузки обучающегося 68 часов;
самостоятельной работы обучающегося 34 часов.


СТРУКТУРА И ПРИМЕРНОЕ СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ
«Элементы математической логики»
2.1. Объем учебной дисциплины и виды учебной работы
Вид учебной работы Количество часов
Максимальная учебная нагрузка (всего) 102
Обязательная аудиторная учебная нагрузка (всего) 68
в том числе: теоретическое обучение 48
практические занятия 20
Самостоятельная работа обучающегося (всего) 34
в том числе: выполнение реферата -
работа с учебной и справочной литературой -
созданий презентаций -
Итоговая аттестация в форме письменного экзамена
2.2. Тематический план и содержание учебной дисциплины «Элементы математической логики»
Наименование разделов и тем Содержание учебного материала, лабораторные работы и практические занятия, самостоятельная работа учащихся Объем часов Уровень усвоения
Тема 1. Общие понятия теории множеств. Язык теории множеств. (16)
Понятие «множество», элемент множества
Изображение множеств (круги Эйлера, диаграммы Венна)
Понятие «подмножества» 6 1
Практическое занятие № 1, тема: «Изображение множеств» 2 3
Универсальное множество
Равные множества
Мощность множества 6 1,2
Практическое занятие № 2, тема: «Язык теории множеств» 2 3
2. Основные операции над множествами (3) Введение операций над множествами
Свойство операций над множествами
Теоретико-множественные операции и их связь с логическими операциями: включение, объединение, пересечение, разность, дополнение множеств 4 1
Практическая работа № 3, тема: «Операции над множествами» 2 3
3. Формулы логики (6) Алгебра логики
Высказывания и высказывательные формы
Отрицание высказываний
Конъюнкция и дизъюнкция 8 1,2
Практическое занятие № 4, тема: «Алгебра логики» 2 3
Союзы языка и логические операции (язык и логика)
Импликация, эквиваленция, сумма по модулю
Таблицы истинности 6 1,2
Практическая работа № 5, тема: «Таблицы истинности» 2 3
4. Законы логики. Равносильные преобразования. (4) Формулы алгебры логики
Составление таблиц истинности для формул. 4 1
Практическое занятие № 6, тема: «Формулы алгебры логики» 2 3
Равносильные преобразования
Упрощение формул 4 1
Практическая работа № 7, тема: «Упрощение формул» 2 3
5. Графы Полный граф
Степень вершины. Формула Эйлера. 4 1
Практическая работа № 8, тема: «Графы»
Практическая работа № 9, тема: «Формулы Эйлера» 4 3
6. Релейно-контактные схемы Определение и составление РКС по формуле.
Упрощение РКС. Эквивалентные РКС 4 1,2
Практическое занятие № 10, тема: «Упрощение РКС» 2 3
3. условия реализации программы дисциплины
3.1. Требования к минимальному материально-техническому обеспечению
Реализация учебной дисциплины требует наличия учебного кабинета математики.
3.1.1. Оборудование кабинета математики:
посадочные места студентов;
рабочее место преподавателя;
комплект учебно-наглядных пособий «Математика».
Технические средства обучения:
мультимедийный проектор;
ноутбук;
проекционный экран;
компьютерная техника для обучающихся с наличием лицензионного программного обеспечения;
сервер;
блок питания;
источник бесперебойного питания;
колонки.
3.2. Информационное обеспечение обучения
Основные источники:
Игошин, В.И. Математическая логика и теория алгоритмов./ В.И.Игошина - М.: Издательский центр «Академия», 2009.
Спирин, М.С., Дискретная математика./ М.С.Спирин, П.А. Спирина, М.: Издательский центр «Академия», 2010.
Дополнительные источники:
Березина, Л.Ю. Графы и их применение: Пособие для учителей. / Л.Ю.Березина – М.:Просвещение, 2010.- 143 с. С ил.
Альхова, З.Н. Внеклассная работа по математике. / З.Н.Альхова, А.В.Махеев – Саратов: «Лицей», 2009 г.
Интернет-ресурсы
Дискретная математика: Учебное пособие / С.А. Канцедал. - М.: ИД ФОРУМ: НИЦ Инфра-М, 2013. - 224 с.: 60x90 1/16. - (Профессиональное образование). (переплет) ISBN 978-5-8199-0304-9, 700 экз. znanium http://znanium.com/bookread.php?book=424101http://znanium.com/catalog.php?bookinfo=447828 – Кочетков, Е.С. Теория вероятностей и математическая статистика: учебник / Е.С. Кочетков, С.О. Смерчинская, В.В. Соколов. - 2-e изд., испр. и перераб. - М.: Форум: НИЦ ИНФРА-М, 2014. – 240с.
http://znanium.com/bookread.php?book=128290 Компьютерный практикум по курсу "Информатика".: учебное пособие / В.Т. Безручко. - 3-e изд., перераб. и доп. - М.: ФОРУМ: ИНФРА-М, 2009. - 386 с.: 60x90 1/16 +СD ROM. - (Высшее образование). (п, cd rom) ISBN 978-5-8199-0330-8, 2000 экз.
Информационные технологии управления : учебник / Б.В. Черников. – 2-e изд., перераб. и доп. – М. : ИД ФОРУМ: НИЦ Инфра-М, 2013. – 368 с. : ил. : http://znanium.com/bookread.php?book=373345
Румянцева, Е.Л. Информационные технологии : учеб. пособие / Е.Л. Румянцева, В.В. Слюсарь; под ред. Л.Г. Гагариной. – М. : ИД ФОРУМ: НИЦ Инфра-М, 2013. – 256 с. : ил. : http://znanium.com/bookread.php?book=3924104. Контроль и оценка результатов
освоения Дисциплины
Контроль и оценка результатов освоения учебной дисциплины осуществляется преподавателем в процессе проведения аудиторных занятий, тестирования, а также выполнения обучающимися индивидуальных и групповых заданий, практических работ.
Результаты обучения
(освоенные умения, усвоенные знания) Формы и методы контроля
и оценки результатов обучения
умения:
формулировать задачи логического характера и применять средства математической логики для их решения
Защита практических работ, внеаудиторная самостоятельная работа, тесты, контрольные работы
знания:
формулы алгебры высказываний; Защита практических работ, внеаудиторная самостоятельная работа.
методы минимизации алгебраических преобразований; Защита практических работ, внеаудиторная самостоятельная работа, контрольная работа
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение «Дальневосточный федеральный университет»
Филиал федерального государственного автономного образовательного учреждения
высшего профессионального образования
«Дальневосточный федеральный университет» в г. Арсеньеве, СПО
УТВЕРЖДАЮ
Зам. директора по УР
__________ _подпись
«_____»_______20 г.


КАЛЕНДАРНО-ТЕМАТИЧЕСКИЙ
ПЛАН РАБОТЫ ПРЕПОДАВАТЕЛЯ
Наименование предмета - Элементы математической логики
Специальность_ 230401 Информационные системы (по отраслям) _
Преподаватель - Чухно И.С.
Общее количество часов по учебному плану __68__час.
Теоретическое обучение ______48 час.
Практические занятия __20__ час.
Самостоятельная работа _35__ час. ____
Итого: __105__час.
План преподавателя составлен на основании рабочей программы, утвержденной зам. директора филиала ДВФУ в г.Арсеньеве
План преподавателя рассмотрен и обсужден предметной цикловой комиссией обще-профессиональных дисциплин № 2 для групп 11С-2211 на 2014/2015 гг.
«______»_______201 г. Протокол № _________на 201 год
Председатель предметной цикловой комиссии №2 И.С.Чухно_______Подпись
№ занятий Дата
проведения Вид
занятий Тема занятий и содержание излагаемого материала Количество часов на тему Наглядные пособия и приборы для проведения занятий Учебники,
учебные пособия, литература Краткое содержание домашних заданий Межпредметные связи
Тема 1. Общие понятия теории множеств. Язык теории множеств. (16)
1 лекция Понятие «множество», элемент множества 2 Метод. разработка конспект математика
2 лекция Изображение множеств (круги Эйлера, диаграммы Венна) 2 Метод. разработка конспект математика
3 лекция Понятие «подмножества» 2 ИВЦ (ПК) Метод. разработка конспект математика
практика Практическое занятие № 1 2 4 лекция Универсальное множество 2 Метод. разработка конспект математика
5 лекция Равные множества 2 Метод. разработка конспект математика
6 лекция Мощность множества 2 Метод. разработка конспект математика
практика Практическое занятие № 2 2 2. Основные операции над множествами (3)
7 лекция Введение операций над множествами 2 Метод. разработка конспект математика
8 лекция Свойство операций над множествами 2 Метод. разработка конспект математика
9 лекция Теоретико-множественные операции и их связь с логическими операциями: включение, объединение, пересечение, разность, дополнение множеств Метод. разработка конспект математика
практика Практическая работа № 3 2 3. Формулы логики (6)
10 лекция Алгебра логики 2 Метод. разработка конспект информатика
11 лекция Высказывания и высказывательные формы 2 Метод. разработка конспект информатика
12 лекция Отрицание высказываний 2 Метод. разработка конспект информатика
13 лекция Конъюнкция и дизъюнкция 2 Метод. разработка конспект информатика
практика Практическое занятие № 4 2 14 лекция Союзы языка и логические операции (язык и логика) 2 Метод. разработка конспект информатика
15 лекция Импликация, эквиваленция, сумма по модулю 2 Метод. разработка конспект информатика
16 лекция Таблицы истинности 2 Метод. разработка конспект информатика
практика Практическая работа № 5 2 4. Законы логики. Равносильные преобразования. (4)
17 лекция Формулы алгебры логики 2 Метод. разработка конспект информатика
18 лекция Составление таблиц истинности для формул. 2 Метод. разработка конспект информатика
практика Практическое занятие № 6 2 19 лекция Равносильные преобразования 2 Метод. разработка конспект информатика
20 лекция Упрощение формул 2 Метод. разработка конспект информатика
практика Практическая работа № 7 2 5. Графы
21 лекция Полный граф 2 Метод. разработка конспект информатика
практика Практическое занятие № 8 2 22 лекция Степень вершины. Формула Эйлера. 2 Метод. разработка конспект информатика
практика Практическая работа № 9 2 6. Релейно-контактные схемы
23 Лекция Определение и составление РКС по формуле. 2 Метод. разработка конспект информатика
24 лекция Упрощение РКС. Эквивалентные РКС 2 Метод. разработка конспект информатика
практика Практическое занятие № 10 2 На самостоятельное изучение: (34 часа)
История развитая математической логики (2 ч)
Задачи курса «математическая логика ». (2 ч)
Область использования логических представлений. (4 ч)
Имена ученых в области математической логики. (2 ч)
Этапы развития математической логики. (2 ч)
Декартово произведение множеств (6 ч)
Свойства декартова произведения множеств. (10 ч)
Способы (правила) формального представления высказываний, построения новых высказываний из имеющихся с помощью логически правильных преобразований (6 ч)
ДАЛЬНЕВОСТОЧНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
Положение об учебно-методических комплексах дисциплин образовательных программ среднего профессионального образования
Разработчики
Идентификационный номер Лист
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный университет» (ДВФУ)
Филиал ДВФУ в г. Арсеньеве
КОНСПЕКТЫ ЛЕКЦИЙ
По дисциплине - Элементы математической логики
Специальность_ 230401 Информационные системы (по отраслям) _
1. алгебра МНОЖЕСТВ
1.1. Понятие множества. Обозначение принадлежности
Математическое понятие множества постепенно выделилось из привычных представлений о совокупности, собрании, классе, семействе и т. д. В 1872 г. Георг Кантор, создатель теории множеств, определил множество как «объединение в одно целое объектов, хорошо различаемых нашей интуицией или нашей мыслью». В первом издании «Теории множеств» Бурбаки, появившемся в 1939 г., в сводке результатов можно найти следующее предложение: «Множество образуется из элементов, обладающих некоторыми свойствами и находящихся в некоторых отношениях между собой или с элементами других множеств».
Объекты, сущности или элементы, составляющие множество, обозначаются строчными латинскими буквами: х, а,...; множество часто обозначают прописными латинскими буквами Е, N, ... . Знак обозначает вхождение или принадлежность; х Е читается: «элемент х принадлежит множеству Е», или короче: «х—элемент множества Е». Следует различать «общий элемент» х множества Е, т. е. произвольный элемент, характеризующийся единственным свойством «принадлежать множеству», и конкретные элементы а, b, c,..., каждый из которых отличен от остальных. Если х не принадлежит Е, будем писать х Е, что читается «х не является элементом множества Е» или «х не принадлежит множеству Е». Если множество содержит конечное число элементов, говорят, что оно конечно; в противном случае множество называется бесконечным. Множество Е, состоящее из элементов а, b,..., записывается
Е= [а. b........}.Примеры. 1) Множество четных цифр Р={2, 4,6,8}.
2) Множество трехзначных чисел в двоичной системе:
В3 = {000, 001, 010, 011, 100, 101, 110, 111}.
1.2. Способы задания множеств
1) Множество может быть задано перечислением всех его элементов.
Пример. Множество цифр: {0,1,..., 9}.
2) Обобщение первого способа состоит в том, что каждый элемент задаваемого множества определяется по некоторому элементу уже известного множества.
Пример. Считая известным множество целых чисел
Z = {....-3.-2,-1, 0. 1, 2, 3,...},
определим множество степеней числа 2
{…, 2-3, 2-2, 2-1, 20, 21, 22, 23, …}
3) Другой способ задания множеств — описание ограничительного свойства, выделяющего элементы множества Е среди элементов более широкого, или основного (универсального, универсума), множества U. Множество Е называется частью, или подмножеством множества U.
Пример. Пусть дано множество N натуральных чисел N = {1, 2, 3,...}. Рассмотрим совокупность всех тех элементов этого множества, которые делятся на 2 (ограничительное и характеризующее свойство); полученное множество есть множество четных чисел Р={2, 4, 6,...}.
4) В дальнейшем мы увидим также, что новые множества задаются при помощи некоторых операций над множествами.
1.3. Множество подмножеств. Включение
Пусть U — основное множество. Основное, или фундаментальное, множество в математике может быть образовано всеми элементами какого-нибудь определенного типа.
Пример. Множество прямых плоскости, множество простых чисел и т. д.
Два свойства, эквивалентные относительно основного множества, определяют одну и ту же часть этого множества, и обратно. Множество элементов U, обладающих свойством х Е, очевидно, совпадает с Е.
Пример. Пусть I — множество нечетных чисел в десятичной системе
I = {1, 3, 5, 7, 9, 11, 13. 15, 17, 19....};
за основное множество примем множество N натуральных чисел. Можно определить множество нечетных чисел исходя из свойства оканчиваться на нечетную десятичную цифру 1, 3, 5, 7 или 9 (Р1); то же множество соответствует свойству не делиться на 2 (Р2). Свойства P1 и P2 эквивалентны относительно N и задают множество нечетных чисел, подмножество основного множества N.
Обратимся теперь к свойству не быть целым числом (Р3), соответствующее этому свойству подмножество основного множества N не содержит ни одного элемента; такое множество будем называть пустым и обозначать .
Таким образом, свойства, присущие некоторым элементам множества U, могут служить для задания подмножеств этого множества; свойство, отличное от всех свойств элементов U, порождает пустое множество, пустое подмножество множества U. Напротив, наибольшее подмножество, т. е. само множество U, может быть задано любым свойством, присущим всем элементам основного множества.
Пусть А и В - два подмножества основного множества U. Если все элементы из А принадлежат В, то говорят, что А содержится (или включено) в В; употребляются также выражения; В содержит A, или А есть часть множества В. В этом случае будем писать А В или В A.
Пример. Множество Р четных чисел содержится в множестве N натуральных чисел: РN.
При задании множества путем перечисления элементов или установления соответствия с элементами ранее изученного множества, мы можем сформулировать характеристические свойства общего элемента подмножества Е основного множества U; эти формулировки будут теоремами, требующими доказательства; способ задания Е — аналитический.
Наоборот, если мы знаем характеристические свойства общего элемента подмножества Е, то мы можем определить, какие элементы основного множества U принадлежат этому подмножеству: речь идет о параметризации подмножества Е: такой способ задания является синтетическим.
Из соотношений А В и В С следует соотношение A С; следовательно, отношение включения транзитивно. Заметим, что из А В и B A следует А = В, и наоборот. Действительно, два множества равны (идентичны), если они состоят из одних и тех же элементов.
Иногда вводят понятия собственного и несобственного подмножества. Множество B называется собственным подмножеством множества A, если оно отлично от A и от .
В этом случае пишут A B, если возможен случай A = B (в этом случае A называется несобственным подмножеством множества В), и А В, если В содержит хотя бы один элемент, не принадлежащий A. При такой системе обозначений невозможен случай, когда А В и B A одновременно.
Свойства подмножеств:
Пустое множество является подмножеством любого множества:
Всякое множество является своим собственным подмножеством:
Два множества называются равными, если они содержат одни и те же элементы и количество этих элементов одинаково.
или или .
Множеством подмножеств некоторого основного или произвольного множества Е называется множество, элементами которого являются подмножества множества Е. Это множество P(Е) включает в качестве элементов пустое множество 0 и само множество Е; каждый отдельный элемент Е есть также подмножество множества Е.
Пример. Е ={а, b, с};
P(Е)={{}, {а}, {b}, {с}, {а, b}, {а, с}, {b, с}, {а, b, с,}}.
Теорема: Конечное множество, содержащее n элементов, имеет 2n подмножеств.
Доказательство: Пусть и пусть BA. Поставим ему в соответствие набор длины n из 0 и 1, устроенный так: если элемент aiB, то на i-ом месте ставим 1, в противном случае - 0.
A: …

В: 1 0 … 0
Каждому подмножеству множества А соответствует свой набор. И наоборот, по всякому набору нулей и единиц можно выписать множество, являющееся подмножеством А. Таким образом, между всеми подмножествами A и п-местными наборами 0 и 1 существует взаимно однозначное соответствие, т.е. подмножеств столько же, сколько таких наборов. Поскольку на каждое из п мест можно поставить либо 0, либо 1, то общее количество п-местных наборов равно , а следовательно, и подмножеств 2n.

1.4. Основные операции над множествами
Дополнение:
Дополнение множества A - множество, состоящее из всех элементов универсума, не принадлежащих A.

Пересечение:
Пересечение множеств A и B - множество, состоящее из всех элементов, принадлежащих одновременно и A, и B.
3) объединение:
Объединение множеств A и B - множество, состоящее из элементов, принадлежащих хотя бы одному из указанных множеств.
Дизъюнктивная сумма (симметрическая разность):

Дизъюнктивная сумма множеств A и B - это множество, состоящее из элементов, принадлежащих либо только A, либо только B.
Разность:
Разность множеств A и B - это множество, состоящее из элементов, принадлежащих A, но не принадлежащих B.
1.5. Свойства операций над множествами
Операции над множествами, сформулированные в (1.4) обладают некоторыми свойствами, приведенными в табл. 1. Эти свойства выражаются совокупностью тождеств, справедливых независимо от конкретного содержания входящих в них множеств, являющихся подмножествами некоторого универсума U.
Таблица 1
Основные свойства операций над множествами
1а) 1б) 2а) 2б) 3а) 3б) 4а) 4б) 5а) 5б) 6а) 6б) 7а) 7б) 8а) 8б) 9а) 9б) 10а) 10б) 11)
12)
13) - закон двойного отрицания
14)
15)
16)
17) (А + В) + С = А + (В + С)
18) А + = + А
19)=
20)
Тождества (1а)-(3а) выражают соответственно коммутативный, ассоциативный и дистрибутивный законы для объединения, а тождества (1б)-(3б) - те же законы для пересечения. Соотношения (4а)-(7а) определяют свойства пустого множества и универсума U относительно объединения, а соотношения (4б)-(7б) - относительно пересечения.
Выражения (8а) и (8б), называемые законами идемпотентности, позволяют записывать формулы с множествами без коэффициентов и показателей степени. Зависимости (9а) и (9б) представляют законы поглощения, а (10а) и (10б) - законы де Моргана.
Соотношения (11)-(20) отражают свойства дополнения, разности, дизъюнктивной суммы, включения и равенства.
Первые десять свойств в табл. 1 представлены парами двойственных (дуальных) соотношений, одно из которых получается заменой в другом символов: на и на , а также на U и U на . Соответствующие пары символов , и , U называются двойственными (дуальными) символами.
При замене в любой теореме входящих в нее символов дуальными получим новое предложение, которое также является теоремой (принцип двойственности или дуальности). Тождество (11) не изменяется при замене символов дуальными, поэтому его называют самодвойственным.
1.6. Декартово произведение множеств
Декартово произведение множеств A и B – это множество упорядоченных пар, первый элемент которых принадлежит A, а второй – принадлежит B.

Пример.


Свойства декартова произведения:
- некоммутативность= - ассоциативность
Свойство ассоциативности позволяет использовать сокращенную запись для декартова произведения нескольких множеств:

- дистрибутивность относительно объединения
- дистрибутивность относительно пересечения
- дистрибутивность относительно разности
Доказательство: Докажем, например, дистрибутивность декартова произведения относительно операции пересечения множеств.
;
,,
Особым случаем декартова произведения является произведение множества самого на себя. В этом случае говорят о декартовом квадрате множества или декартовой n-ой степени множества А.
;
Пример.
Теорема. Если множество A содержит n элементов, а B – m элементов, т.е.: , то содержит элементов.
Лекция : «Множество. Алгебра множеств»
Введем обозначения:
N (или ω) –множество натуральных чисел;
Z – множество целых чисел;
Q – множество рациональных чисел;
R – множество действительных (вещественных) чисел;
С – множество комплексных чисел.
X R – элемент X принадлежит множеству R.
Равные множества – множества, состоящие из одинаковых элементов.
A = B – множество А равно множеству B.
Ø – пустое множество.
A C – Множество А является подмножеством множества С.
Если AC и A C, то A C (строго).
Если A C и C A, то A = С.
Пустое множество Ø является подмножеством любого множества.
Универсальное множество (универсум) U содержит в себе все множества и любое множество является подмножеством универсального множества.
Можно записать следующее: ØNZQRCU.Множества A и B называются эквивалентными (обозначается A~B), если биекция f: A↔B (или по другому y=f(x) и x=f(y), при yA и xB).
Мощностью множества A называется класс всех множеств, эквивалентных множеству A (обозначается ).
Существуют конечные и бесконечные множества. Пусть множество A состоит из n элементов. Это множество называется конечным. Число n называется мощностью данного множества. =n.
Множество натуральных чисел мощность является счетным (т.е. все элементы можно пронумеровать). Если A~N, то мощность =N.
Если A~, т.е. A={1,2,4,8,…, ,…}, то множество A называется континуальным (или континуумом). Мощность .
Основное правило комбинаторики (показано на примере)
Пусть имеется палочка, разделенная на 3 части. Первую ее часть можно раскрасить n способами, вторую – m, третью – k. Всего способов раскраски палочки – n*m*k.
Аналогично с множествами
U = {a1,a2… an-1, an}
Пусть U = {a1, a2, a3}
Выпишем множество всех подмножеств множества U.
P(U) = {0, a1, a2, a3, a1a2, a1a3, a2a3, a1a2a3}.
Мощность множества U равна 3, а мощность P(U) равна 8.
Методом математической индукции доказывается, что при произвольной мощности n множества U, мощность множества P(U) равна 2n.
Операции над множествами
Объединение множеств (AB). Элемент, принадлежащий полученному множеству, принадлежит множеству A ИЛИ множеству В.
Пересечение множеств (AB). Элемент, принадлежащий полученному множеству, принадлежит множеству A и множеству В.
Дополнение множества А. (С = ) – не А. Все элементы, принадлежащие универсальному множеству, не принадлежащие множеству А.
Свойства операций над множествами
A B = B A; AB = BA – коммутативность.
(AB)C =A(BC), A(BC)=(AB)C – ассоциативность.
(AB)C = (AC)(BC), (AB)C=(AC)(BC) – дистрибутивность.
Поглощение A A = A, A A = A.
Существование универсальных границ.
А Ø = A; A Ø = Ø; A U = U; A U = A
6. Двойное дополнение
7. Ø
8. Законы двойственности или закон Де – Моргана

Пересечение множеств
Объединение множеств





Дополнение множества




Назначение курса.
Данный курс служит формированию знаний и умений, которые образуют теоретический фундамент, необходимый для постановки и решения задач в области информатики, для корректного понимания ограничений, возникающих при создании вычислительных структур, алгоритмов и программ обработки информации.
Новые разделы курса дискретной математики, хотя и реализованы в виде учебных программ и циклов лекций, пока не существуют в виде монографий, по крайней мере, на русском языке, так как курс дискретной математики для технических вузов ориентирован на старые прикладные задачи, которые приходилось решать инженерам. В частности в математической логике это была минимизация логических схем, которая сегодня потеряла актуальность.
Интересно отметить, что теория синтеза логических схем, пройдя почти полный "биологический цикл" на глазах одного поколения исследователей, представляет собой весьма поучительный пример того, как сильно подвержены моральному старению отрасли технических наук, слабо связанные с фундаментальной наукой. Ещё 10 лет назад все технические журналы были заполнены статьями по минимизации и синтезу логических схем. Большинство методов минимизации, разработанных учёными, сейчас забыты и не востребованы практикой. А те идеи, которые в то время считались сугубо теоретическими, нашли практическое применение в современной технике. Например, нечёткая логика, сети Петри и теория алгоритмов выдержали проверку временем и находят широкое применение в различных областях кибернетики и программирования, таких как системное программирование, сложность вычисления и искусственный интеллект.
Математическая логика и теория алгоритмов стала центральным разделом дискретной математики. Однако в отличие от большинства монографий на русском языке в курсе лекций эти вопросы изложены как средство решения практических, инженерных задач.
Как известно, по истечении каждого десятилетия элементная база компьютеров, операционные системы, средства доступа и сами программы меняются коренным образом. Однако структуры и алгоритмы, лежащие в их основе, остаются неизменными в течение гораздо большего времени. Эти основы стали закладываться тысячелетия назад, когда разработана формальная логика и разработаны первые алгоритмы.
Математическая логика и теория алгоритмов традиционно относятся к фундаментальной науке и считаются мало связанными с практикой и трудными для понимания. Действительно, когда Дж. Буль создал математический аппарат булевой алгебры, он долго не находил практического применения, однако в 20-ом столетии именно этот математический аппарат позволил спроектировать все узлы ЭВМ. Следовательно, первый из этих предрассудков успешно опровергается развитием вычислительной техники.
Что же касается предрассудка о трудности понимания этой дисциплины, то он в значительной степени происходит оттого, что книги по математической логике и теории алгоритмов написаны математиками для математиков.
Сейчас, когда возможности вычислительной техники многократно возросли, а самих персональных компьютеров значительно больше, чем людей, умеющих их эффективно использовать, понимание того, что можно и что нельзя сделать с помощью современной вычислительной техники приобретает исключительное значение.
Именно общая теория алгоритмов показала, что есть задачи неразрешимые ни при каком увеличении мощности вычислительных средств, а её бурно развивающаяся ветвь - теория сложности вычислений постепенно приводит к пониманию того, что бывают задачи разрешимые, но объективно-сложные, причём сложность их может оказаться в некотором смысле абсолютной, т.е. практически недоступной для современных ЭВМ.
В данном курсе ставились следующие задачи:
1. Изложить все рассматриваемые вопросы по возможности как можно более просто, но не проще чем это требуется для специалиста высшей квалификации.
2. Практические проблемы проектирования и анализа информационных систем являются отправной точкой, а формальный аппарат – средством систематического решения этих проблем. По нашему глубокому убеждению, студент – это не сосуд, который надо наполнить, а факел, который надо зажечь.
3. Каждый раздел курса содержит вопросы для самопроверки. Для усвоения данного курса студент обязан ответить на все эти вопросы.
В результате освоения данного курса студент на основе ясного понимания соответствующих теоретических разделов должен уметь:
- реализовывать простейший вид логического преобразования информации в произвольном базисе логических функций;
- выделять в доказательных рассуждениях естественного языка логическую структуру, строить схемы формальных доказательств и проверять их правильность.
1.2 Логические представления
Логические представления — описание исследуемой системы, процесса, явления в виде совокупности сложных высказываний, составленных из простых (элементарных) высказываний и логических связок между ними. Логические представления и их составляющие характеризуются определенными свойствами и набором допустимых преобразований над ними (операций, правил вывода и т.п.), реализующих разработанные в формальной (математической) логике правильные методы рассуждений - законы логики.
Способы (правила) формального представления высказываний, построения новых высказываний из имеющихся с помощью логически правильных преобразований, а также способы (методы) установления истинности или ложности высказываний изучаются в математической логике. Современная математическая логика включает два основных раздела: логику высказываний и охватывающую ее логику предикатов (рис. 1.1), для построения которых существуют два подхода (языка), образующих два варианта формальной логики: алгебру логики и логические исчисления. Между основными понятиями этих языков формальной логики имеет место взаимно однозначное соответствие. Их изоморфизм обеспечивается в конечном итоге единством законов логики, лежащих в основе допустимых преобразований.
Рис. 1.1
Основными объектами традиционных разделов логики являются высказывания.
Высказывание - повествовательное предложение (утверждение, суждение), о котором имеет смысл говорить, что оно истинно или ложно. Все научные знания (законы и явления физики, химии, биологии и др., математические теоремы и т.п.), события повседневной жизни, ситуации, возникающие в экономике и процессах управления, формулируются в виде высказываний. Повелительные и вопросительные предложения не являются высказываниями.
Примеры высказываний: "Дважды два - четыре", "Мы живем в XXI веке", "Рубль - российская валюта", "Алеша - брат Олега", "Операции объединения, пересечения и дополнения являются булевыми операциями над множествами", "Человек смертен", "От перестановки мест слагаемых сумма не меняется", "Сегодня понедельник", "Если идет дождь, вам следует взять зонт".
Для того чтобы далее оперировать этими предложениями как высказываниями, мы обязаны знать относительно каждого из них, истинно оно или ложно, т.е. знать их истинностное значение (истинность). Заметим, что в ряде случаев истинность или ложность высказывания зависит от того, какую конкретную реальность (систему, процесс, явление) мы пытаемся с его помощью описать. В таком случае говорят, что данное высказывание истинно (или ложно) в данной интерпретации (контексте). Далее предполагаем, что контекст задан и высказывание имеет определенное истинностное значение.
1.3 История развитая математической логики
Логика как наука сформировалась в 4 в. до н.э. Ее создал греческий ученый Аристотель.
Слово «логика» происходит от греческого "логос", что с одной стороны означает "слово" или "изложение", а с другой мышление. В толковом словаре Ожегова С.И. сказано: "Логика наука о законах мышления и его формах". В 17 в. немецкий ученый Лейбниц задумал создать новую науку, которая была бы «искусством исчисления истины». В этой логике, по мысли Лейбница, каждому высказыванию соответствовал бы символ, а рассуждения имели бы вид вычислений. Эта идея Лейбница, не встретив понимания современников, не получила распространения и развития и осталась гениальной догадкой.
Только в середине 19 в. ирландский математик Джордж Буль воплотил идею Лейбница. В 1854 году им была написана работа "Исследование законов мышления" (Investigation the laws of thought), которая заложила основы алгебры логики, в которой действуют законы, схожие с законами обычной алгебры, но буквами обозначаются не числа, а высказывания. На языке булевой алгебры можно описать рассуждения и "вычислить" их результаты. Однако ею охватываются далеко не все рассуждения, а лишь определенный тип их, поэтому алгебру Буля считают исчислением высказываний.
Алгебра логики Буля явилась зародышем новой науки – математической логики. В отличии от нее, логику Аристотеля называют традиционной формальной логикой. В названии "математическая логика" отражены две особенности этой науки: во-первых, математическая логика - это логика, использующая язык и методы математики; во-вторых, математическая логика вызвана к жизни потребностями математики.
В конце 19 в. созданная Георгом Кантором теория множеств представлялась надежным фундаментом для всей математики, в том числе и математической логики, по крайней, мере, для исчисления высказываний (алгебры Буля), т.к. оказалось, что алгебра Кантора (теория множеств) изоморфна алгебре Буля.
Математическая логика сама стала областью математики, поначалу казавшейся в высшей степени абстрактной и бесконечно далекой от практических приложений. Однако эта область недолго оставалась уделом "чистых" математиков. В начале 20 в. (1910 г.) русский ученый Эренфест П.С. указал на возможность применения аппарата булевой алгебры в телефонной связи для описания переключательных цепей. В 1938-1940 г. почти одновременно появились работы советского ученого Шестакова В. И., американского ученого Шеннона и японских ученых Накасимы и Хакадзавы о применении математической логики в цифровой технике. Первая монография, посвященная использованию математической логики при проектировании цифровой аппаратуры, была опубликована в СССР советским ученым Гавриловым М.А. в 1950 г. Чрезвычайно важна роль математической логики в развитии современной микропроцессорной техники: она используется в проектировании аппаратных средств ЭВМ, в разработке всех языков программирования и в конструировании дискретных устройств автоматики.
Большой вклад в развитие математической логики сделали ученые разных стран: профессор Казанского Университета Порецкий П.С., де-Морган, Пирс, Тьюринг, Колмогоров А.Н., Гейдель К. и др.
1.4 Вопросы для самопроверки.
1. Сформулируйте задачи курса «математическая логика и теория алгоритмов».
2. Назовите области использования логических представлений.
3. Назовите имена ученых в области математической логики.
4. Назовите этапы развития математической логики.
§2. Операции над множествами.
Рассмотрим некоторые операции над множествами.
2.1 Пересечение множеств.
Пусть даны два множества: А={a; b; c; d} иB={c; d; e}.образуем новое множество Р, состоящее из всех элементов, принадлежащих одновременно и множеству А, и множеству В, т.е. Р={c;d}. Тогда говорят, что множество Р является пересечением множеств А и В.
Определение 1.4
Пересечением множеств А и В называется множество, состоящее их всех тех и только тех элементов, которые принадлежат множествам А и В одновременно.
Символически пересечение множеств А и В обозначается так: АВ, где символ - знак пересечения множеств. Используя характеристическое свойство, определение 1.4 можно записать следующим образом:
Р=АВ= {x xA и xB}={x xA xB}. (1)
Таким образом, (1) есть характеристическое свойство пересечения двух множеств.
Союз “и” иногда заменяют фигурной скобкой, и тогда (1) будет иметь вид:
(2)
Для обозначения одновременной принадлежности множеству А и множеству В используется также знак (конъюнкция, или логическое “и”):
xAB xA xB(2а)
Читаются выражения (2) и (2а) одинаково: если х принадлежит пересечению множеств А и В, то х принадлежит как множеству А, так и множеству В.
Если мы имеем ситуацию, когда х не принадлежит пересечению множеств А и В, то это означает, что х не принадлежит или множеству А, или множеству В.
Символически это может быть записано так:
(3)
где квадратная скобка заменяет союз “или”.
В символической записи союз “или” может быть заменен также знаком (дизъюнкция, логическое “или”):
хАВ хА хВ. (3а)
Читаются выражения (3) и (3а) одинаково: если х не принадлежит пересечению множеств А и В, то х не принадлежит или множеству А, или множеству В.
Графическая иллюстрация вариантов пересечения двух множеств приведена на рис. 710 (пересечение заштриховано).
U
Р=A=B
А
U
Р=B
А
Р=
В
U
А
РВ
U

рис. 7 рис. 8 рис. 9рис. 10
2.2 Объединение множеств.
Множества А и В входят в их объединение только один раз. Это вполне соответствует толкованию множества, принятому в математике: ни один элемент не может содержаться в множестве несколько раз.
Определение 1.5
Объединением двух множеств А и В называется такое множество С, которое состоит из всех тех элементов, которые принадлежат хотя бы одному из множеств А или В.
Символически объединение двух множеств А и В обозначается так:
А В, где - символ объединения множеств. Определение 1.5 можно записать с помощью характеристического свойства:
С= А В={x xA или xB}.(4)
Союз “или” иногда заменяют квадратной скобкой
(5)
а также знаком дизъюнкции
х А В хА хВ. (5а)
Читаются эти знаки одинаково: если элемент х принадлежит объединению двух множеств А и В, то он принадлежит множеству А или множеству В.
Если же элемент х не принадлежит объединению множеств А и В, то он не принадлежит ни множеству А, ни множеству В. Символически это может быть записано так:
(6)
или
x AB xA xB.(6а)
Графически варианты объединения двух множеств показаны на рис. 11÷14 (объединение заштриховано).
А
U
B
А
В
U
А
В
U
U
С=A=B

рис. 11 рис. 12 рис. 13 рис. 14
Отметим некоторые очевидные свойства операции объединения двух множеств:
АА=А, А=А, АU=U.(7)
Замечание1.
Если А1, А2,…, Аn – несколько множеств, то аналогично тому, как это делалось для двух множеств, определяется их пересечение, т.е. составляется множество, представляющее их общую часть:
Р= А1 А2… Аn={x x Ai, i=},
Где символ (квантор всеобщности) заменяет слово “все”, и, таким образом, мы символически обозначили ту часть множеств Ai, которая принадлежит каждому множеству одновременно.
Замечание 2.
Если А1, А2,…, Аn – несколько множеств, то аналогично тому, как это делалось для двух множеств, определяется их объединение – составляется множество, состоящее из элементов, которые принадлежат хотя бы одному их них:
C= A1A2…An={x xA1 или xA2 или …или xAn}.
Замечание 3.
Если в выражении есть знаки и и нет скобок, то сначала выполняется операция пересечения, а потом – операция объединения (аналог сложению и умножению в арифметике).
2.3 Разность множеств.
Определение 1.6
Разностью двух множеств А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат множеству А и не принадлежат множеству В.
Символически разность двух множеств обозначается так:
А В, где символ является знаком разности для множеств. С помощью характеристического свойства запишем определение 1.6 следующим образом:
C=A B={x xA и xB}(8)
Или
(9)
а также xAB xA xB.(9а)
Пример 1.
Если E1={2; 4; 6} и E2={6; 8; 10}, то E3=E1E2={2; 4}, E4=E2E1={8;10}.
Пример 2.
Если M1={x1; x2; x3}, M2={y1; y2}, то M3=M1M2={ x1; x2; x3},
M4=M2M1={y1; y2}.
Пример 3.
Если K1={1; 3; 5; 7; 9}, K2={5; 7; 1}, то K3=K1K2={3; 9}, K4=K2K1=.

Графическое представление вариантов разности двух множеств А и В показано на рис. 15÷18, где множество А В заштриховано.
U
A\B=Ø
A=B
А
U
B
А
В
U
А
В
U

рис. 15 рис. 16 рис. 17 рис. 18
2.4 Дополнение к множеству.
Определение 1.7
Пусть В А. Множество всех элементов множества А, не принадлежащих множеству В, называют дополнением к множеству В и обозначают или .
Если ясно, о каком множестве идёт речь, то индекс А опускается и пишут или .
Определение 1.8
Пусть А – некоторое множество, являющееся частью универсального (основного) множества U. Дополнением множества А называется множество, состоящее из всех тех и только тех элементов их множества U, которые не принадлежат А. Его обозначают или .
Это определение может быть записано в виде:
= {x xA}.(10)
Графически дополнения (соответственно определениям 1.7 и 1.8) изображены на рис. 19 и 20 соответственно, на которых дополнения заштрихованы.
U
U

A

A

B

рис. 19рис. 20
Основные законы алгебры логики
В алгебре логики введена система аксиом, определяющая свойства и отношения основных операции, т.е. таких действий, с помощью которых из конечного числа некоторых заданных элементов алгебры строятся новые элементы.
Алгебра логики строится на определенной системе аксиом.
Постулаты алгебры логики1. Существуют такие 0 и 1, что =1 и =0. Необходимо отметить, что цифры 0 и 1 не выражают здесь количественных соотношений и являются не числами, а символами и, следовательно, алгебра логики является не алгеброй чисел, а алгеброй состояний.
2. Переменная может принимать лишь одно из двух возможных значений
x = 0, если, x 1
x = 1 если, x 0
3. Действия с константами
0 0 = 01 1 = 1
1 1 = 10 0 = 0
1 0 = 00 1 = 1
0 1 = 01 0 = 1
Каждая из приведенных аксиом состоит из двух частей, что соответствует правилу инверсии, которое заключается в том, что любая аксиома может быть преобразована в другую одновременной заменой цифра 0 на цифру 1 и операции умножения на сложение, и наоборот.
На основании этих аксиом выводятся все теоремы, выражающие основные законы алгебры логики.
Законы алгебры логики. Теоремы одной переменной1. Закон, тождества Х=Х. Необходимо, чтобы мысль, заключенная в высказывании не менялась в течение всего рассуждения.
2. Закон нулевого множества:
0 а = 0
0 а = а
0 а b … x = 0
Т.е. произведение любого числа переменных обращается в нуль, если какая-либо одна переменная имеет значение "0" независимо от значения других переменных.
3. Закон универсального множества:
1 а = а
1 а = 1
1 а b … z = 1
4. Закон тавтологии, повторения (идемпотентности):
а а … а = а
а а … а = а
Истина, повторенная несколько раз, все равно, остается только истиной.
5. Закон двойной инверсии (инволютивности): . Отрицание отрицания равносильно утверждению.
6. Законы дополнительности:
а) закон логического противоречия . Произведение любой переменной и ее отрицания всегда ложно (утверждение "речка движется и не движется" всегда ложно);
б) закон исключенного третьего . Сумма любой переменной и ее отрицания всегда истинна: "Студент или сдаст экзамен или не сдаст". "Паду ли я стрелой пронзенный, иль мимо пролетит она".
Теоремы для двух и трех переменных7. Коммутативные (переместительные) законы:
а b = b а
а b = b а
От перемены мест слагаемых сумма не меняется.
8. Ассоциативные (сочетательные) законы:
а (b c) = (a b) c ассоциативность конъюнкции.
а (b c) = (а b) c ассоциативность дизъюнкции.
Для записи умножения или сложения скобки можно опустить.
9. Дистрибутивные (распределительные) законы:
а) умножение относительно сложения
а (b c) = а b а c
а (b + с) = аb + ас (в обычной алгебре)
б) сложение относительно умножения
a b c = (a b) (a c)
a+bc (a+b) (a+c) (в обычной алгебре)
10. Законы инверсии (правило де Моргана)

11. Обобщение законов де Моргана, предложенное Шенноном:

т.е. инверсия дизъюнкции и конъюнкции получается заменой каждой переменной ее инверсией и одновременно взаимной заменой символов суммы и произведения.
12. Законы поглощения

13. Закон контрапозиции . Согласно закону контрапозиции два высказывания вида и одновременно истинны или одновременно ложны. Вместо заданной теоремы можно доказать обратно противоположную теорему. Например. "Если m2 нечетно, то m - нечетно". Докажем что если m четно, то m2 четно. Действительно, если m = 2n, то m2 = 4n2.
14. Закон транзитивности импликации (закон силлогизма).
(а b) (b с) ( а с)
15. Закон транзитивности эквиваленции.
(а b) (b с) ( а с)
16. Закон противоположности.
(а b) (а b)
17. Законы склеивания (распространения).

3.4 Тавтологии. Равносильные формулы
ПФ, значения которых для любого набора переменных есть 1 (соответственно 0) будем называть тождественно истинными формулами, или тавтологиями (тождественно-ложными ПФ или противоречием).
Тавтологии играют в логике особо важную роль как формулы, отражающие логическую структуру предложений, истинных в силу одной только этой структуры. Для доказательства того, что ПФ является тавтологией достаточно построить таблицу истинности для этой ПФ. Перечислим некоторые основные тавтологии или законы логики. Обозначим | = А, что А тавтология. Справедливость | = и вытекает из определений:
1. | = х х - закон тождества
2. | = 0 - закон противоречия
3. | = 1 - закон исключенного третьего
4. | = х - закон двойного отрицания
5. | = = - закон идемпотентности
6. -законы де Моргана
7. | = - закон контрапозиции
8. | = - закон транзитивности импликации (закон силлогизма)
9. | = - закон противоположности
10.| = - закон транзитивности эквиваленции
Законы 1-3 выражают законы формальной логики, выведенные Аристотелем. Закон тождества требует, чтобы мысль, заключенная в высказывании не изменялась в течении всего рассуждения. Закон противоречия говорит, что одна и та же мысль не может быть одновременно и истинной и ложной.
В силу законов идемпотентности в алгебре логики нет показателей степени и коэффициентов (idem - "то же", potentia - сила).
Смысл законов де Моргана можно выразить так: отрицание дизъюнкции равно конъюнкции отрицаний и vice versa. Согласно закону контрапозиции два предложения вида и одновременно истинны или одновременно ложны.
Две ПФ и назовем равносильными, если для любых наборов они принимают одинаковые значения.
Это обозначается АВ и читается "А равносильно В" (равносильность рефлексивна, симметрична и транзитивна).
Теорема 1. А В тогда и только тогда, когда | = А В. Убедимся, что теорема верна, если докажем необходимость: если АВ, то | = А В; достаточность: если | = А В, то А В. Справедливость этих утверждений вытекает непосредственно из определений.
Принцип двойственности: Если две формулы, (не содержащие знаков , и ) равносильны, то двойственные ил формулы равносильны.
Две формулы называются двойственными, если каждую из них можно получить из другой заменой , , 1, 0 соответственно на , , 0 и 1 (X 0 = Х 1).
Обратные и противоположные теоремы. Для каждого предложения, формализованного импликацией А В, можно составить три таких предложения В А, и . Предложение В А называется обратным данному, предложения противоположным данному и обратно противоположным. Для всякой теоремы вида "если А, то В" можно сформулировать обратное ей предложение "если В, то А". Однако не для всякой теоремы предложение ей обратное является истинным. Например: "если два прямоугольника конгруэнтны, то их площади равны", обратное: "Если площади двух прямоугольников равны, то они конгруэнтны" - неверно. Если А В теорема, то А есть достаточное условие В, а В необходимое условие А. Если оба взаимообратных предложения А В и В А теоремы, т.е. предложение А В теорема, то В является необходимым и достаточным условием А, а А достаточным и необходимым условием В (если два квадрата конгруэнтны...). Если А В теорема, а В А нет, то А - достаточное, но не необходимое условие В, а В - необходимое, но не достаточное условие А.
Для всякой теоремы А В, можно составить противоположное предложение , которое может быть истинным, но может и не быть истинным. Чтобы убедиться в этом, надо составить таблицу истинности.
Согласно закону контрапозиции два предложения вида одновременно истинны или ложны. Вместо данной теоремы можно доказать обратно противоположную.
6 Вопросы для самопроверки
1. Составьте таблицы истинности для формул:
а) б)
в) г)
д)
x y
0 0 1 0 0 1 1
0 1 1 1 0 1 1
1 0 0 1 0 1 1
1 1 0 1 1 0 1
3.2. Установите с помощью таблиц истинности какие из следующих формул - тавтологии:
а) б)
в) г)
д) е)
3. На основании каких законов логики получены следующие соотношения? Докажите их с помощью таблиц истинности :
; ; ; ; ; ; ; ; ; ; ; ;
4. Какие из данных формул равносильны:
а) б) в) г)
д) е) ж) з)
5. Полиция задержала 4 гангстеров, подозреваемых в краже автомобиля: Анри, Луи, Жоржа и Тома. При допросе они дали следующие показания: Анри: «Это был Луи», Луи: «Это сделал Том», Жорж: «Это не я», Том: «Луи лжет, говоря, что это я». Дополнительное расследование показало, что правду сказал только один из них. Кто украл машину?
Конспект урока на тему: «Основы логики: построение таблиц истинности».
Данный урок третий в рамках темы «Основы логики». Предполагается, что обучающиеся уже знакомы с основными определениями и логическими операциями.
Цели урока:
создание условий для формирования знаний по построению таблиц истинности для сложных выражений;
Задачи:
изучить принципы построения таблиц истинности для сложных выражений;
способствовать развитию логического мышления;
Тип урока:
урок совершенствования знаний, умений и навыков;
целевого применения усвоенного.
Вид урока: лекция.
Используемое оборудование: 
компьютер;
приложение Microsoft Office PowerPoint 2003 и выше;
мультимедиа проектор.
План урока:
Организационный момент (2 мин)
Опрос по материалу прошлого урока (5 мин)
Представление нового материала (15 мин)
Выполнение практического задания (5 мин)
Подведение итогов урока. Задание на дом (3 мин)
Ход урока:
Организационный момент.
Приветствие учащихся. Проверка присутствующих. Настрой на урок.
Опрос по материалу прошлого урока.
На прошлом уроке мы с вами познакомились с основными логическими операциями. Обучающимся предлагается ответить на следующие вопросы:
Что такое сложное высказывание?
Сколько Вы знаете базовых логических операций? (5)
Перечислите названия базовых логических операций. (Коньюнкция, Дизъюнкция, Инверсия, Импликация, Эквивалентность)
Какими знаками обозначается логическое умножение? (& и )
Как называется логическое отрицание и что оно выполняет?
Представление нового материала.
На данном этапе используется презентация (слайды 2-6).
При изучении работы различных устройств компьютера приходится рассматривать такие его логические элементы, в которых реализуются сложные логические выражения. Поэтому необходимо научиться определять результат этих выражений, то есть строить для них таблицы истинности.
Таблица истинности – это таблица, в левой части которой записывается набор аргументов, а в правой части - соответствующие значения логической функции.
Таблица истинности – это таблица, определяющая значение сложного высказывания при всех возможных значениях простых высказываний.
Алгоритм построения таблиц истинности для сложных выражений следующий:
Определить количество переменных (простых выражений);
Определить количество логических операций и последовательность их выполнения.
Определить количество строк:
количество строк = 2ª + строка для заголовка,
где a – количество логических переменных.
Определить количество столбцов: количество столбцов = количество переменных + количество логических операций;
Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций.
Рассмотрим пример построения таблицы истинности для следующего сложного (составного) логического выражения:
А & (B V C)
Решение:
Простые выражения (логические переменные): А, В, С; (3)
Количество логических операций:
¬ А - инверсия;
B C - операция дизъюнкции;
¬ А & (B C). операция конъюнкции. Всего: 3
Количество строк: на входе три простых высказывания: А, В, С, поэтому a=3 и количество строк = 2³ +1 = 9.
Количество столбцов: 3+3=6
Заполняем столбцы с учетом таблиц истинности логических операций.

Выполнение практического задания.
После объяснения нового материала обучающимся предлагается самостоятельно построить таблицу истинности для логического выражения (слайды 7-8):
D = А V B & C

Подведение итогов урока. Задание на дом.
Ответы на вопросы учащихся. Подведение итога урока. Выставление оценок.
Домашнее задание (слайд 9).
Используемые учебники и учебные пособия:
Светлов В.А. Современная логика: Учебное пособие. - СПб.: Питер, 2006. - 400 с.
Ивлев Ю.В. Логика: Учебник. – М.: Проспект, 2008. – 304 с.
Бочаров В.А., Маркин В.И. Основы логики: Учебник. –М.: Инфра-М, Форум, 2009.
ЛОГИКА. Учебное пособие. Издание 2-е: Москва, Издательство «Знание», 1998
 
Построение таблиц истинности сложных высказываний.
Приоритет логических операций
1) инверсия 2) конъюнкция 3) дизъюнкция 4) импликация и эквивалентность
Как составить таблицу истинности?
Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.
Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре:
(0, 0),     (0, 1),     (1, 0),     (1, 1).
Если формула содержит три переменные, то возможных наборов значений переменных восемь (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).
Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.
Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.
Примеры.
1. Составим таблицу истинности для формулы , которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы. В результате получим таблицу:
Переменные Промежуточные логические формулы Формула

0 0 1 0 0 1 1 1
0 1 1 1 1 0 1 1
1 0 0 0 1 0 0 1
1 1 0 0 1 0 0 1
Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной.
2. Таблица истинности для формулы :
Переменные Промежуточные логические формулы Формула

0 0 0 1 1 0 0
0 1 1 0 0 0 0
1 0 1 0 1 1 0
1 1 1 0 0 0 0
Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 0, то есть является тождественно ложной.
3. Таблица истинности для формулы :
Переменные Промежуточные логические формулы Формула

0 0 0 1 1 0 1 0 0
0 0 1 1 1 0 1 1 1
0 1 0 0 0 1 1 0 1
0 1 1 0 0 1 1 1 1
1 0 0 1 1 0 0 0 0
1 0 1 1 1 0 0 0 0
1 1 0 0 1 0 0 0 0
1 1 1 0 1 0 0 0 0
Из таблицы видно, что формула в некоторых случаях принимает значение 1, а в некоторых — 0, то есть является выполнимой.
Пример1:
Вася спросил у мамы: «Можно пойти в кино или на футбол?» Мама ответила отрицательно. Как поступить мальчику?
( А В) = А В (Закон де Моргана)
Проверим правильность этого закона с помощью таблицы истинности.
Пример2:
В классе оказалось разбито стекло. Учитель объясняет директору: это сделал Коля или Саша. Но Саша этого не делал, т.к. в это время сдавал мне зачет. Следовательно, это сделал Коля.
Решение: Формализуем данное сложное высказывание.
К – это сделал Коля
С – это сделал Саша
Кол-во простых высказываний n = 2.
Форма высказывания: Е = ( К C ) & С К
Определить количество строк и столбцов в таблице истинности.
Т.к. каждое из простых высказываний может принимать всего два значения (0 или 1), то количество разных комбинаций значений n высказываний – 2 n .
Количество строк в таблице = 2 n + строка на заголовок.
Количество столбцов в таблице равно сумме количества простых высказываний (n) и количества разных логических операций, входящих в сложное высказывание.
В нашем примере: количество строк - 22 + 1 = 5 ,
столбцов – 2 + 4 = 6
Начертить таблицу и заполнить заголовок
Первая строка – номера столбцов.
Вторая строка промежуточные формулы и соответствующие им условные записи операций над значениями .
Заполнить первые n столбцов.
В нашем примере сначала заполняем 1-й и 2-й столбцы.
Заполнить остальные столбцы.
В соответствии с таблицами истинности соответствующих логических операций, причем при заполнении каждого столбца операции выполняются над значениями одного или двух столбцов, расположенных левее заполняемого.
Итак, вычисляем значения 3-го столбца по значениям 2-го, потом значения 4-го – по значениям 1-го и 2-го…
К С С К C ( К C ) & С ( К C ) & С К
1 1 0 1 0 1
0 1 0 1 0 1
1 0 1 1 1 1
0 0 1 0 0 1
Вывод: получили в последнем столбце все единицы. Значит, значение сложного высказывания истинно при любых значениях простых высказываний К и С. Следовательно, учитель рассуждал логически правильно.
Тема: Логические высказывания и логические операции.
Цели урока:
Сформировать понятия: логическое высказывание, логические величины, логические операции.
Учащиеся должны знать: значение понятий: логическое высказывание, логические величины, логические операции.
Учащиеся должны уметь:
приводить примеры логических высказываний;
называть логические величины, логические операции.
Ход урока
Занятие сопровождается компьютерной презентацией. (Приложение)
I. Оргмомент
На прошлом уроке мы с вами говорили о науке Логике. Мы уже знаем, что в науке логика есть несколько разделов. Один из разделов - Алгебра высказываний.
Запишем заголовок: Алгебра высказываний.
II. Объяснение нового материала
(Слайд 1)
ВЫСКАЗЫВАНИЕ - это повествовательное предложение, о котором можно сказать, что оно или истинно или ложно.
• Например:
Земля - планета Солнечной системы. (Истинно.)
2 + 8 < 5 (Ложно.)
5 · 5 = 25 (Истинно.)
Всякий квадрат есть параллелограмм. (Истинно.)
Каждый параллелограмм есть квадрат. (Ложно.)
2 · 2 = 5 (Ложно.)
• Не всякое предложение является высказыванием.
1) Восклицательные и вопросительные предложения высказываниями не являются.
- «Какого цвета этот дом?»
- «Пейте томатный сок!»
- «Стоп!»
2) Не являются высказываниями и определения.
«Назовем медианой отрезок, соединяющий вершину треугольника с серединой противоположной стороны».
Определения не бывают истинными или ложными, они лишь фиксируют принятое использование терминов.
3) Не являются высказываниями и предложения типа «Он сероглаз» или «х- 4х + 3=0» - в них не указано, о каком человеке идет речь или для какого числа х верно равенство. Такие предложения называютсявысказывательными формами.
• Высказывательная форма - это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями.
(Слайд 2)
• В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть только 0 или 1. Если высказывание истинно, то его значение равно 1, если ложно - 0.
• Простые высказывания назвали логическими переменными и для простоты записи их обозначают латинскими буквами: А, В, С…
Луна является спутником Земли. А = 1
Москва – столица Германии. В = 0
• Сложные высказывания называются логическими функциями. Значения логической функции также может принимать значения только 0 или 1.
Запишем заголовок:
БАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
(Слайд 3)
В алгебре высказываний, как и в обычной алгебре, вводится ряд операций. Логические связки И, ИЛИ и НЕ заменяются логическими операциями: конъюнкцией, дизъюнкцией и инверсией. Это основные логические операции, при помощи которых можно записать любую логическую функцию.
(Слайд 4)
КОГДА ИЗ ТРУБЫ ПОЛЬЕТСЯ ВОДА?
(Слайд 5)
ЛОГИЧЕСКОЕ УМНОЖЕНИЕ
Обозначим каждое из высказываний латинскими буквами.
А – «Сегодня светит солнце».
В – «Сегодня идет дождь».
Соединим с помощью союза И, получим сложное высказывание. Это и будет логическое умножение.
Запишем определение: Логическое умножение (конъюнкция) образуется соединением двух (или более) высказываний в одно с помощью союза «и».Составим таблицу истинности.(Слайд 6)
Обозначение: &, ^, *.
Союз в естественном языке: и.
Зададим в таблице все варианты, когда высказывания могут быть либо истинными – 1, либо ложными – 0. Теперь посмотрим, что получим в итоге?
Рассмотрим другой вариант: КОГДА ИЗ ТРУБЫ ПОЛЬЕТСЯ ВОДА?
(Слайд 7)
(Слайд 8) ЛОГИЧЕСКОЕ СЛОЖЕНИЕ
Снова обозначим каждое из высказываний латинскими буквами.
А – На стоянке находится «Мерседес».
В – На стоянке находится «Жигули».
Соединим с помощью союза ИЛИ, получим сложное высказывание. Это и будет логическое сложение.
Запишем определение: Логическое сложение (дизъюнкция) образуется соединением двух (или более) высказываний в одно с помощью союза «или».
Составим таблицу истинности. (Слайд 9)
Обозначение: +, V.
Союз в естественном языке: или.
(Слайд 10)
Посмотрите, как проще запомнить дизъюнкцию и конъюнкцию.
В слове дизъюнкция две буквы И, значит ИЛИ, а в слове конъюнкция одна буква И, значит И.
Следующая операция: ЛОГИЧЕСКОЕ ОТРИЦАНИЕ. (Слайд 11)
Снова обозначим каждое из высказываний латинскими буквами.
Запишем определение: Логическое отрицание (инверсия) образуется из высказывания с помощью добавления частицы «не» к сказуемому или использования оборота речи «неверно, что…».
Составим таблицу истинности. (Слайд 12)
Обозначение: ¬.
Союз в естественном языке: не; неверно, что…
Следующая операция: ЛОГИЧЕСКОЕ СЛЕДОВАНИЕ. (Слайд 13)
Обозначение: →.
Союз в естественном языке: если…, то….
Запишем определение: Логическое следование (импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если…, то…».
Составим таблицу истинности. (Слайд 14)
III. Итог урока
Сегодня мы с вами рассмотрели логические высказывания и логические операции. У кого есть вопросы по данной теме?
«Графы»
Графом (G) будем называть тройку объектов (V, X, )
V – множество n вершин.
X – конечное множество ребер.
- функция инцидентности, которая каждому элементу множества X ставит в соответствие пару элементов из множества V.
задана на множестве X.
Если в значении функции инцидентности допускается перестановка вершин, то граф называется неориентированным. В противном случае граф называется ориентированным (Орграф).
Vj – начало ребра
Vk – его конец
xi) = (Vj, Vk) – ребро инцидентно в вершине Vj и в вершине Vk.
Если одной и той же паре вершин инцидентно несколько ребер, то ребра называются кратными.
Если на ребре xi0
(x0) = (Vj0, Vj0),
то ребро называется петлей.
Способы задания графов
Аналитический
Если вершине не инцидентно никакое ребро, то эта вершина называется изолированной.
Выписываются все ребра и пишутся напротив две пары вершин, которым они инцидентны.
В конце выписываются все изолированные вершины.
Геометрический
Каждая вершина графа задается точкой. А ребра, инцидентные паре вершин – кривой.
Желательно рисовать кривые без пересечения. Если пересечения существуют, то их надо отличать от вершин.

С помощью матрицы инцидентности
A(m*n)
m = [V] – число вершин
n = [X}- число ребер
а) Неориентированные графы
Aij = {0, если Vi не инцидентно xj, 1, если Vi инцидентно xj)
б) Орграфы
Aij = {0, если Vi не инцидентно xj, -1, если Vi - начало xj, 1, если Vi - конец xj)
Для петель нужны дополнительные предположения.
Матрица смежности (задается одинаково для всех графов)
B(m*m) m = [V]
Bij равно числу ребер, инцидентных паре вершин (oi, oj)
Если граф не ориентирован, то матрица симметрична.
Граф, в котором нет кратных ребер и петель, называется простым.
Простой граф называется полным, если любой паре его вершин инцидентно одно ребро.
Дальше все о неориентированных графах.
K1 – полный граф с одной вершиной

K2 – с двумя


K3 – с тремя

K4 – полный граф с четырьмя вершинами

K5 – полный пятивершинник






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






Полный двудольный граф.
Маршруты, циклы, связности.
Маршрутом в графе называется чередующаяся последовательность вершин и ребер, начинающаяся и заканчивающаяся вершинами, такую, что каждое ребро в нем соединяет только те вершины, между которыми оно стоит.
Будем говорить, что этот маршрут соединяет первую и последнюю вершину. Если существует маршрут, то последняя вершина называется достижимой из первой вершины.
Маршрут, в котором нет повторяющихся ребер, называется цепью.
Маршрут, в котором нет повторяющихся вершин (кроме первой и последней), называется простой цепью.
Если в простой цепи первая и последняя вершины совпадают, то она называется циклом.
Граф называется связным, если любая вершина достижима из любой другой вершины. В противном случае граф называется несвязным. Несвязный граф распадается на несколько частей, каждая из которых является связным графом.
Эти части называются компонентами связности.
Ребро называется циклическим, если оно входит хотя бы в один цикл графа. В противном случае ребро называется ациклическим.
Утверждение.
Если из связного графа удалить циклическое ребро, то вновь полученный граф останется связным, а если удалить ациклическое ребро, то граф распадется на два компонента связности.
Связный граф, у которого все ребра ациклические, называется деревом.
Несвязный граф, компонентами связности которого являются деревья, лесом.
Свойства деревьев.
Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы число вершин было больше числа ребер на один.
Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом.
Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.
Лекция 12: «Эйлеровы графы»







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




Для любого графа xi, соединяющего 2 вершины проводим новую плоскость, содержащую эту прямую, а ребро рисуем на плоскости.
Граф будет планарным, если существует его укладка на сфере.




Доказательство следует из взаимно однозначного соответствия точек на сфере с точками плоскости из стереографических проекций.
Следствие. Граф любого выпуклого многогранника планарен.
Ребра плоского графа разбивают плоскость на несколько частей, одна из которых бесконечна. Эти части и являются гранями плоского графа.
Теорема Эйлера о плоских графах.
Формула Эйлера.
Для плоского графа справедливо соотношение.
M – N + P = 2.

Докажем индукцией по числу граней
P = 1
Если P = 1, то граф – дерево. В нем нет ни одного цикла. У дерева число вершин больше числа ребер на 1.
M = N + 1
N + 1 – N + 1 = 2 – справедливо.
Пусть p = k, и утверждение верно.
Тогда оно верно и при P= k+1
Берем ребро графа, отделяющее бесконечную грань от внутренних и удаляем это ребро из графа. Т.к. оно циклическое, то в новом графе g1 (он также будет связным) число вершин M останется прежним.
N1 = N – 1
P1 = P – 1
M = M
k + 1-1 = k
Для g1 справедливо предположение индукции.
M1 + N1 + P1 = 2
M – N – 1 + K = 2
M – N + K – 1 = 2
M – N + P = 2
Что и требовалось доказать.
Следствие 1.
Для плоского связного простого графа справедливо соотношение
n <= 3*(m-2)
Следствие 2.
Для плоского связного простого графа без треугольных граней справедливо соотношение
n <= 2*(m-2)
Следствие 3.
Граф K5 – непланарен.


m > 2
И если бы он был плоским, то для него было бы справедливо следствие 1.
N <= 3*(m-2)
10 <= 9 – неверно.
Противоречие. Значит, он не может быть нарисован плоским.
Следствие 4.
Граф K3-3 непланарен.




Нет треугольных граней.
Если бы он был плоским, то для него было бы справедливо следствие 2.
9 <= 2*(6-2)
9 <= 8 – неверно.
Противоречие из предположения, что он не может быть плоским.
Операцией разбиения ребра графа называется следующая процедура:
Ребро удаляется из графа, и в граф добавляется новая вершина, соединенная новыми ребрами с концами данного ребра.
Два графа называются гомеоморфными, если каждый из них может быть получен из одного и того же графа путем применения конечного числа раз операции разбиения ребер.
Теорема Понтрягина – Куратовского.
Чтобы граф был планарным, необходимо и достаточно, чтобы он не содержал гомеоморфных подграфов.
Лекция 13: «Сети. Пути в орграфах. Остовы минимальной длины»
Определение. Двуполюсной сетью называется связный граф без петель с двумя выделенными вершинами, которые называются полюсами.





Полюса

Двуполюсная сеть называется сильно связанной (связной), если через любое ребро проходит простая цепь, соединяющая полюса. В ней нет повторяющихся вершин.
Параллельная сеть – сеть вида




Последовательная сеть – сеть вида

П (пи) сети – последовательно-параллельные сети
Примеры П-сетей




Такая сеть называется мостиковой.
Контактными схемами называются сильносвязные двуполюсные сети, каждому ребру которой поставлено в соответствие x или NOT(x).
X Not Y
Not Z



ZNot X
Любой контактной схеме (КС) можно поставить в соответствие булеву функцию (функцию проводимости) по правилу:
Для любой простой цепи, соединяющей полюса, записываем ЭК тех переменных, которыми помечены ребра этой цепи.
Затем берем дизъюнкцию всех ЭК. Получим искомую функцию проводимости.
Если в контактной схеме будут стоять переключатели (релейные контакты), которые будем считать замкнутыми, если выражение, стоящее у ребра равно 1 или в противном случае разомкнутыми, то при подаче на полюса разности потенциалов (электрического тока) контактная схема будет проводить ток при таких и только при таких состояниях контактов, при которых значение функции равно 1.
Минимальной контактной схемой для функции называется контактная схема, для которой эта функция является функцией проводимости. Эта схема содержит наименьшее число ребер.
Чтобы построить минимальную КС, надо выписать минимальную ДНФ для данной функции, упростить путем вынесения за скобки, нарисовать П-сеть, реализующую КС для функции и постараться найти мостиковые соединения.
Минимальные пути в графах
Путем в графе (в орграфе) называется маршрут, движение по которому любого ребра проходит в соответствии с направлением этого ребра.
Контуром в орграфе называется замкнутый путь, в котором вершины не повторяются (кроме первой и последней).
Орграф, в котором нет ни одного контура, называется бесконтурным.
Первая задача о минимальном пути.
Дан граф. Выделено две вершины. Найти путь из одной вершины в другую, состоящий из наименьшего числа ребер.
Введем обозначения
Г(V) – множество вершин, в которые можно попасть из вершины V, пройдя только по одному ребру в его направлении.
Г-1(V) – множество вершин, из которых можно попасть в вершину V, пройдя только по одному ребру.
Алгоритм.
Исходной вершине A присваиваем метку 0.
Любому Г(А), которые еще не имели меток, присваиваем метку М = 1.
Для любой V, принадлежащей Г(А) находим Г(V) и любой V, принадлежащему Г(V), если она не имела метку, даем метку 2.
И так далее до тех пор, пока конечная вершина не получит метку.
Выбираем путь по Г-1(V).
Может произойти такое, что пути из А в В нет вообще.
Тогда на некотором шаге при обратном ходе нужной вершины нет.
Вторая задача.
Если каждому ребру поставить в соответствие некоторое целое положительное число, называемое его длиной и требуется найти путь из А в В, такой, что i = minimum. (r или l – длина ребра)
Алгоритм будет следующий.
Метка для ребра А 
Для Vi i = +(бесконечность) – очень большое число, большее суммы всех длин ребер всего графа.
L(Vi, Vj) – длина ребра, идущего из вершины Vi в Vj. Направление важно.
Для любого ребра из графа проверяем выполнение неравенства.
j - i > L(Vi, Vj) *
Если это неравенство выполняется, то меняем метку j на новую.
j = i + L(Vi, Vj) и так до тех пор, пока выполняется *.
Если * нигде не выполняется, то та метка, которая будет стоять у вершины В и будет равна длине минимального пути из А в В, а сам путь строится движением назад из В в А.
Г-1(В) Существует такое ребро Vi1, для которого выполнено равенство.
b - i1 = L(Vi1,B)
Затем Г-1(V1) Существует V2, где V1) - V2) = L(V1, V2) и т.д. пока не вернемся в вершину А.
Путь минимальной длины найден.
Остов графа минимальной длины.
Остов – дерево, содержащее все вершины графа и какие-то из его ребер.
Если каждому ребру графа поставлена в соответствие его длина, то требуется найти такой остов, сумма длин ребер которого минимальна.
Алгоритм
Перенумеруем все ребра графа в порядке возрастания их длин.
Просматриваем ребра, начиная с первого. Если x1 не является петлей, мы его включаем в остов и переходим к следующему ребру. Если оно не является петлей и не образует с уже имеющимися ребрами цикла, мы его включаем в остов. И так до тех пор, пока не рассмотрим все ребра.
Остов минимальной длины найден.
1. Методические рекомендации к теме “Графы”.
Понятие графа целесообразно вводить после того, как разобрано несколько задач, подобных задаче 1, решающее соображение в которых – графическое представление. Важно, чтобы ученики сразу осознали, что один и тот же граф может быть нарисован разными способами. Строгое определение графа, на мой взгляд, давать не нужно, т.к. оно слишком громоздко и это только затруднит обсуждение. На первых порах хватит и интуитивного понятия. При обсуждении понятия изоморфизма можно решить несколько упражнений на определение изоморфных и неизоморфных графов. Одно из центральных мест темы – теорема о четности числа нечетных вершин. Важно, чтобы ученики до конца разобрались в ее доказательстве и научились применять к решению задач. При разборе нескольких задач рекомендую не ссылаться на теорему, а фактически повторять ее доказательство. Чрезвычайно важно также понятие связности графа. Содержательным соображением здесь является рассмотрение компоненты связности, на это необходимо обратить особое внимание. Эйлеровы графы – тема почти игровая.
Первая и главная цель, которую нужно преследовать при изучении графов, –научить школьников видеть граф в условии задачи и грамотно переводить условие на язык теории графов. Не стоят рассказывать обе всем на нескольких занятиях подряд. Лучше разнести занятия по времени на 2–3 учебных года. (Прилагается разработка занятия “Понятие графа. Применение графов к решению задач” в 6 классе).
2. Теоретический материал к теме “Графы”.
Введение
Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач. В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Мы же обсудим только самые основные понятия, свойства графов и некоторые способы решения задач.
Понятие графа
Рассмотрим две задачи.
Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.
Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.

Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу ?
Решение: Занумеруем последовательно клетки доски:

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

Мы рассмотрели две непохожие задачи. Однако решения этих двух задач объединяет общая идея – графическое представление решения. При этом и картинки, нарисованные для каждой задачи, оказались похожими: каждая картинка – это несколько точек, некоторые из которых соединены линиями.
Такие картинки и называются графами. Точки при этом называются вершинами, а линии – ребрами графа. Заметим, что не каждая картинка такого вида будет называться графом. Например. если вас попросят нарисовать в тетради пятиугольник, то такой рисунок графом не будет. Будем называть что рисунок такого вида, как в предыдущих задачах, графом, если есть какая-то конкретная задача для которой такой рисунок построен.
Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.
Степени вершин и подсчет числа ребер графа
Запишем еще одно определение: Степенью вершины графа называется количество выходящих из нее ребер. В связи с этим, вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной.
С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу.
Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими ?
Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.
Ответ. Соединить телефоны таким образом невозможно.
Теорема: Любой граф содержит четное число нечетных вершин.
Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.
Связность графа
Есть еще одно важное понятие, относящееся к графам – понятие связности.
Граф называется связным, если из любые две его вершины можно соединить путем, т.е. непрерывной последовательностью ребер. Существует целый ряд задач, решение которых основано на понятии связности графа.
Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.
Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.
Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”
Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:

Каждый такой отдельный кусок называется компонентой связности графа. Каждая компонента связности представляет собой связный граф и для нее выполняются все утверждения, которые мы доказали для связных графов. Рассмотрим пример задачи, в которой используется компонента связности:
Задача 5. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.
Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.
Графы Эйлера
Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.
Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ?

Решение. Если мы будем рисовать граф так, как сказано в условии, то в каждую вершину, кроме начальной и конечной, мы войдем столько же раз, сколько выйдем из нее. То есть все вершины графа, кроме двух должны быть четными. В нашем же графе имеется три нечетные вершины, поэтому его нельзя нарисовать указанным в условии способом.
Сейчас мы доказали теорему об Эйлеровых графах:
Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.
И в заключение – задача о Кенигсбергских мостах.
Задача 7. На рисунке изображена схема мостов города Кенигсберга.
Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?

3. Задачи к теме “Графы”
Понятие графа.
1. На квадратной доске 3x3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?

Рис. 1
Рис. 2
Решение. Занумеруем клетки доски, как показано на рисунке:

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

При любой последовательности ходов конями порядок их следования, очевидно, измениться не может. Поэтому переставить коней требуемым образом невозможно.
2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9 ?
Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.
Степени вершин и подсчет числа ребер.
3. В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.
Решение. Подсчитаем общее количество выходящих городов дорог – 100 . 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.
4. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей ?
Ответ. Нет (теорема о четности числа нечетных вершин).
5. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?
Ответ. Нет, не может.
6. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?
Решение. Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2 (см. задачу 3). Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.
7. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.
Доказательство непосредственно следует из теоремы о четности числа нечетных вершин графа.
Связность.
8. В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого.
Доказательство. Рассмотрим компоненту связности, в которую входит один из городов, дорогу между которыми закрыли. По теореме о четности числа нечетных вершин в нее входит и второй город. А значит по-прежнему можно найти маршрут и добраться из одного из этих городов в другой.
Графы Эйлера.
9. Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту розно 1 раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист
а) не с него начал и не на нем закончил?б) с него начал, но не на нем закончил?в) с него начал и на нем закончил?
10. На рисунке изображен парк, разделенный на несколько частей заборами. Можно ли прогуляться по парку и его окрестностям так, чтобы перелезть через каждый забор розно 1 раз?

ГРАФЫ И ИХ ПРИМЕНЕНИЕ ПРИ РЕШЕНИИ ЗАДАЧ
Задачи, приводящие к графам
1. Женя, Дима, Максим и Алеша сыграли между собой по одной партии в шахматы. Сколько всего партий было сыграно?
Решение:
Женя сыграл партию с Димой, партию с Максимом и партию с Алешей - всего три партии. Дима также сыграл три партии - с Женей, Максимом и Алешей. Но партию Димы с Женей мы уже посчитали. Остается добавить одну партию, которую сыграли Максим с Алешей. Поэтому искомое число партий равно значению выражения 3+2+1.
Проще решить эту задачу с помощью рисунка.

Каждая линия обозначает сыгранную партию. Всего на схеме 6 линий, значит всего сыграно 6 партий.
2. Вася, Коля, Петя, Аня и Наташа - лучшие лыжники в пятом классе. Для участия в соревнованиях нужно выбрать из них одного мальчика и одну девочку. Сколькими способами это можно сделать?
Решение:
Эту задачу можно решить с помощью следующей схемы.
Ответ: 6 способов.
3. Пятеро ученых, участвовавших в научной конференции, обменялись рукопожатиями. Сколько всего было сделано рукопожатий?
На прощание эти ученые обменялись визитными карточками. Сколько карточек было передано из рук в руки?
Решение:
Ответ: 10 рукопожатий, 20 визитных карточек.
4. Как вы помните, охотник за мертвыми душами Павел Иванович Чичиков побывал у известных вам помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжогло, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их (рис. 1.1). Установите, какое имение кому принадлежит, если ни по одной из дорог Чичиков не проезжал более одного раза.
Решение. По схеме видно, что путешествие Чичиков начал с имения Е, а кончил имением О. Замечаем, что в имения В и С ведут только по две дороги, поэтому по этим дорогам Чичиков должен был проехать. Отметим их жирной линией. Определены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и AM Чичиков не ездил. Перечеркнем их (рис. 1.2К Отметим жирной линией ED; перечеркнем DK. Перечеркнем МО И МН отметим жирной линией МF; перечеркнем FO; отметим жирной линией FH, НК и КО. Найдем единственно возможный при данном условии маршрут.
Подведем первый итог: задача решена в ходе преобразования картинки. С рисунка остается только считать ответ: имение Е принадлежит Манилову, D — Коробочке, С — Ноздреву, А — Собакевичу, В — Плюшкину, М — Тентетникову, F — Бетрищеву, Н — Петуху, К — Констанжогло, О — Кошкареву.


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

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

Дополнением графа Г называется граф Г с теми же вершинами, что и граф Г, и с теми и только теми ребрами, которые необходимо добавить к графу Г, чтобы получился полный граф.
Степенью вершины называется число ребер графа, которым принадлежит эта вершина.
Вершина называется нечетной, если ее степень — число нечетное. Вершина называется четной, если ее степень — число четное.
Путем от А1 до Аn в графе называется такая последовательность ребер ведущая от А1 до Аn , в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза.
Циклом называется путь, в котором совпадают его начальная и конечная вершины.
Длиной пути называется число ребер этого пути.
Длиной цикла называется число ребер в этом цикле.
Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.
3429000561340457200561340Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их.
В графе вершины А и В — связные, а вершины А и Н — несвязные.
Граф называется связным, если каждые две вершины его связные.
Граф называется несвязным, если хотя бы две вершины его несвязные.
Деревом называется всякий связный граф, не имеющий циклов.

Вершина дерева, степень которой равна единице, называется висячей вершиной (на рисунке висячие вершины выдел закрашенными кружками).
Лесом называется несвязный граф, представляющий объединение деревьев.
34290012065
Решение задач с помощью графов
Задача 1. Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания?
Решение. Каждого из этой компании изобразим на рисунке кружком. Если двое знакомы, соединим соответствующие кружки отрезком. Оказывается, что такие ситуации не только возможны, но все их можно описать аналогичными схемами. Из рассматриваемой компании нельзя выделить ни «четырехугольник», ни «треугольник», поскольку тогда из оставшихся нельзя будет составить компанию, удовлетворяющую условию, т. е. схема знакомства единственная.
226695-489585
Задача2. Девять шахматистов проводят турнир в один круг (каждый из участников должен сыграть с каждым из остальных по одному разу). Покажите, что в любой момент найдутся двое, закончившие одинаковое число партий.
Решение. Переведем условие задачи на язык графов. Каждому из шахматистов поставим в соответствие вершину графа, соединим ребрами попарно вершины, соответствующие шахматистам, уже сыгравшим между собой партию. Получим граф с девятью вершинами. Степени его вершин равняются числу партий, сыгранных соответствующими игроками. Покажем, что во всяком графе с девятью вершинами всегда найдутся хотя бы две вершины одинаковой степени.
Каждая вершина графа с девятью вершинами может иметь степень, равную 0, 1, 2,…,7, 8. Предположим, что существует граф Г, все вершины которого имеют разную степень, т. е. каждое из чисел последовательности 0, 1, 2 7, 8 является степенью одной и только одной из его вершин. Но этого не может быть. Действительно, если в графе есть вершина А степени 0, то в нем не найдется вершина В со степенью 8, так как эта вершина В должна быть соединена ребрами со всеми остальными вершинами графа, в том числе и с А. Иначе говоря, в графе с девятью вершинами не могут быть одновременно вершины степени 0 и 8. Следовательно, найдутся хотя бы две вершины, степени которых равны между собой.
Вернемся к задаче. Доказано, что в любой момент найдутся хотя бы двое, сыгравшие одинаковое число партий.
Задача 3. Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими?
Решение.
Участника этой компании изобразим вершиной графа, а отношение знакомства между двумя участниками - ребром. Изобразим графы, которые могут соответствовать такой компании.
0107950
Итак, ситуация, рассмотренная в задаче, вполне возможна. Но случай, рассмотренный на втором рисунке, соответствует не одной, а двум компаниям, участники одной из них не знакомы с участниками другой.
Граф, изображенный на первом рисунке связный, так как из каждой вершины по ребрам можно попасть в любую другую. Делаем вывод, что в этом случае каждый через своих знакомых может познакомиться со всеми остальными.
Во втором случае получились два простых цикла, не сцепленные между собой в вершинах.
Задача 4. Кубок по настольному теннису разыгрывается по олимпийской системе. Встречи проводятся без ничьих. К очередному туру допускается только победившая в предыдущем туре команда. Проигравшие выбывают из игры. Для завоевания кубка команда должна победить во всех турах.
На участие в розыгрыше кубка поданы заявки от 16 команд. Схема проведения игр изображается графом на рисунке.
208915167640

Вершины нижнего «яруса» дерева (закрашенные) интерпретируем как команды, участвующие в розыгрыше кубка, вершины второго снизу яруса — как команды-победительницы в одной шестнадцатой финала, вершины третьего яруса — как команды победительницы в одной восьмой финала и т.д.
Какую информацию можно получить с помощью этого дерева?
Непосредственно с него считываются:
число всех участников розыгрыша кубка (число закрашенных вершин);
число этапов проведения розыгрыша (число ярусов из вершин в дереве не считая нижнего);
число команд, участвовавших в одной восьмой финала, в одной четвертой финала, в одной второй финала (число вершин соответственно в четвертом сверху ярусе, в третьем сверху ярусе, во втором сверху ярусе);
число матчей, которые придется сыграть командам для выявления обладателя кубка (число незакрашенных вершин в графе). Кстати, это число легко определяется и без дерева. (В каждом матче выбывает одна команда. Для того чтобы была выявлена команда-победительница остальные должны выбыть из соревнования. Поэтому число матчей равно числу команд без одной, а именно 15.)
Задача 5. Вершины графа обозначают населенные пункты, ребра – дороги. Сколькими способами можно выбрать путь из А в С? Сколькими способами можно доехать из А в С, затем вернуться обратно, если нельзя проезжать дважды по одной и той же дороге?
Решение:

5 · 3=15 способами можно выбрать путь из А в С.
5 · 3 · 2 ·4 =120 способами можно доехать из А в С, затем вернуться обратно, если нельзя проезжать дважды по одной и той же дороге.
Задача 6. На гору ведут 5 дорог. Сколькими способами можно выбрать маршрут для того, чтобы подняться на гору, а затем спуститься с неё? Как изменится ответ, если нельзя подниматься и спускаться по одной и той же дороге?
Решение:
5 · 5=25 способами можно выбрать маршрут для того, чтобы подняться на гору, а затем спуститься с неё.
5 · 4 =20 способами можно выбрать маршрут для того, чтобы подняться на гору, а затем спуститься с неё, если нельзя подниматься и спускаться по одной и той же дороге.

Тема 1. Сведения из истории графов. Граф и его элементы.
В этой теме приводится характеристика «Геометрии положений» (топологии), данная Эйлером в связи с решением исторической задачи о кенигсбергских мостах; формулируются основные понятия теории графов.
Исследование задачи о мостах Кенигсберга Эйлер в 1736 г представил в Петербургскую Академию Наук. Работа начинается определением той области математики, к которой относятся подобные вопросы:
«Кроме той области геометрии, которая рассматривает величины, и способы измерения… Лейбниц первым упомянул о «геометрии положения», она занимается только расположением частей фигуры друг относительно друга, отвлекаясь от их размеров. Недавно мне пришлось слышать об одной задаче, относящейся к геометрии положения, и я решил изложить здесь в виде примера найденный мной способ решения этой задачи».
Далее Эйлер обосновывает невозможность решения этой задачи.
- Понятие графа и его элементов. Примеры графов. Полный граф. Четность вершины графа. Основные теоремы теории графов.
Если все вершины графа четные, граф можно начертить одним росчерком. Порядок движения любой.
Граф с двумя нечетными вершинами можно начертить одним росчерком, начиная движение с одной и заканчивая на другой нечетной вершине.
Граф с более чем двумя нечетными вершинами нельзя начертить одним росчерком.
228600723265Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых (примеры графов изображены на рисунке).
С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло- и электросети. Помогают графы в решении математических и экономических задач.
Познакомимся с основными понятиями теории графов при решении несложной задачи.
Задача: Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями. Сколько всего рукопожатий было сделано? Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени (рис.2), а производимому рукопожатию — отрезок или часть кривой, соединяющая конкретные точки — имена (рис. 3).
Нулевой граф с пятью вершинами Неполный граф с пятью вершинами
Точки А, Б, В, Г, Д называются вершинами графа, а отрезки линий, соединяющие эти точки — ребрами графа. При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными; Длины отрезков и расположение точек произвольны. Например, все три фигуры на рисунке изображают один и тот же граф. Рассмотрим процесс соединения точек А, Б, В, Г, Д ребрами. 1. Ситуация, соответствующая моменту, когда рукопожатия еще не совершались, представляет собой точечную схему, изображенную на рисунке 2. Такая схема, состоящая из «изолированных» вершин, называется нулевым графом. 2. Ситуация, когда совершены еще не все рукопожатия, может схематически быть изображена, например, с помощью рисунка З: пожали руки А и Б, А и Г, Д и Г, В и Д. Следующий момент, когда добавятся, например, пожатия рук А и В, Г и Б, попробуйте изобразить сами.Графы, в которых не построены все возможные ребра , называются неполными графами. 3. На рисунке 4 изображен граф, соответствующий всем совершенным рукопожатиям. Этот граф является полным графом.
Полный граф с пятью вершинами Если подсчитать число ребер графа, изображенного на рисунке 4, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.
Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2
Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2:Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.
Тема 2. Эйлеров и Гамильтонов циклы. Задачи о мостах. Рисование фигур единым росчерком.
Учащимся дается понятие об эйлеровом и гамильтоновом циклах.
Цикл в графе, содержащий каждое ребро один раз, называется эйлеровым; цикл называется гамильтоновым, если он содержит каждую вершину один раз. Условие существования эйлерова цикла: граф должен быть связным, каждая его вершина должна иметь четную локальную степень.
Граф может быть и эйлеровым, и гамильтоновым, или одним из них, или ни тем ни другим.
К рассмотрению предлагаются различные задачи о мостах и их вариации, рассматриваются головоломки на рисование фигур единым росчерком; выполняются графические и творческие работы, самостоятельная работа.
Учащимся предлагается составление аналогичных задач с учетом свойств графов.
Рассматриваются задачи на «маршруты путешествий» и «осмотр достопримечательностей»
Рассматривается математическая постановка игры Гамильтона и ее близость к практическим задачам, например, об эффективном использовании подвижного состава или оборудования. Предполагается проведение конкурса на самую красивую графическую или текстовую задачу.
Тема 3. История лабиринтов.
Происхождение задач о лабиринтах относится к глубокой древности и теряется во мраке времен.
Слово «лабиринт» (греческое) означает «ходы в подземельях».
Решению задачи о лабиринтах предпосылаются исторические справки – чтобы показать интерес к этой задаче и дать наглядное представление о существовавших и существующих лабиринтах.
Возможен ли безвыходный лабиринт?
Задача о прохождении лабиринта приобретает практический интерес, поскольку устройство линий электропередач, канализации, сетей дорог, каналов и т.д. – все это более или менее сложные лабиринты.
Начало решению вопроса о существовании безвыходных лабиринтов положено Эйлером. Результаты его изысканий привели к заключению, что нет безвыходных лабиринтов.
Учащиеся знакомятся с геометрической постановкой задачи о лабиринтах; решают общую задачу, выполняют поисковые задания.
Нарисовав соответствующий лабиринту граф, используют способ обхода всех ребер для нахождения выхода.
Решение (т.е. маршрут, ведущий к цели) каждого лабиринта может быть найдено одним их трех сравнительно простых методов.
Первый метод – МЕТОД ПРОБ И ОШИБОК. Выбирайте любой путь, а если он заведет вас в тупик, то возвращайтесь назад и начинайте все сначала.
Второй метод – МЕТОД ЗАЧЕРКИВАНИЯ ТУПИКОВ. Начнем последовательно зачеркивать тупики, т.е. маршруты, не имеющие ответвлений и заканчивающиеся перегородкой. Незачеркнутая часть коридоров будет выходом или маршрутом от входа к выходу или к центру.
Третий метод – ПРАВИЛО ОДНОЙ РУКИ. Оно состоит в том, что по лабиринту надо двигаться, не отрывая одной руки (правой или левой) от стены.
Тема 4. Задача четырех красок.
Учащиеся знакомятся с задачей раскраски карты. Задача известна достаточно давно, но в качестве теоремы или задачи впервые была выдвинута Мебиусом в 1840 году. Суть задачи в следующем.
Для всякой карты достаточно четырех различных красок, чтобы любые две области, имеющие общую границу, не были окрашены одним цветом; причем все равно, сколько областей, как причудливы их очертания и как сложно их взаимное расположение.
Прослеживается аналогия этой задачи с Эйлеровой задачей о мостах, задачей о лабиринтах.
Учащимися формулируются условия возможности раскраски двумя красками, тремя, условия «правильной раскраски».
Учащиеся выполняют большое количество практических заданий, создают и раскрашивают собственные карты.
Тема тем более актуальна, что предположение о 4-х красках никто не доказал, но никто и не опроверг.
Впервые над этим вопросом задумались картографы в середине прошлого века. Не найдя ответа, они обратились к математикам. Доказано, что любую карту можно правильно раскрасить пятью красками, а так же показано, что существуют карты, которые нельзя правильно раскрасить в три цвета. Не доказано, что любую карту можно правильно раскрасить четырьмя красками, но не найдена ни одна карта, которую нельзя было бы раскрасить четырьмя красками.
Тема 5. Графы с цветными ребрами и их свойства.
Тема рассматривает графы, соответствующие таким ситуациям, при котором каждая пара каких-либо элементов множества находится между собой в каком-либо, но только одном отношении.
Например, среди участников чемпионата в какой-то момент есть и уже сыгравшие, и еще не сыгравшие друг с другом. Или: среди множества стран есть установившие и не установившие дипломатические отношения.
Для наглядности на рисунках ребра, соответствующие разным отношениям, окрашивают разным цветом. Свойства графов формулируются в ходе решения задач.
Тема 6. Понятие дерева в теории графов.
Знакомство учащихся с важным классом графов, называемых деревьями, предваряется упражнениями типа: «Нарисуйте граф с семью вершинами и шестью ребрами, не имеющий ни одного цикла».
Деревья определяются как графы, не имеющие циклов. Это одно из наиболее часто встречающихся в теории графов понятий, одновременно простое и удобное в обращении.
Вводятся понятия, связанные с деревьями, рассматриваются особенности деревьев и возможности их использования при решении самых разнородных задач – таких, как подсчет изомеров химического соединения, отыскание кратчайшего пути, комбинаторные задачи, вероятностные задачи, а также использование деревьев в генетике.
Кроме того, обобщается применение деревьев при описании различных вариантов игр и сочетаний или разбиений композиций.
Ребра графов, являющегося деревом, иногда называют ветвями дерева, а само дерево – деревом вариантов. Вычерчивать дерево полезно, когда требуется записать все существующие комбинации элементов.
Данная тема предполагает задания поискового и исследовательского характера.
Тема 7. Графы и логические задачи.
Обобщается возможность применения графов при решении некоторых типов логических задач; рассматриваются задачи на переливание, взвешивание, организацию круговых турниров и прочее. Проводится конкурс решения задач, выполняется текстовая работа.
Тема 8. Сетевые графы.
Данная тема показывает построение сети сложного комплекса работ, определение по сети самого ответственного участка; формирует навык определения времени завершения работ и поиска резервов времени.
Все вводимые в этой теме понятия имеют естественную природу; рассматривается комплекс работ, достаточно близкий и знакомый учащимся. Учащиеся знакомятся с основными правилами построения сетевых графиков, что помогает рациональному планированию. Тема допускает разделение расчетной и графической работ между группами учащихся.
Наиболее удачной формой занятия по данной теме можно считать деловую игру.
Тема 9. Применение теории графов в различных областях науки и техники.
Целью данного занятия является ознакомление учащихся с применением теории графов в различных областях науки и техники. Работа исследовательских и поисковых групп освещает вопросы использования графов в сетевом планировании, математической экономике, физике и электротехнике, биологии, химии, генетике и так далее.
Занятие проводится в виде пресс-конференции или круглого стола. Организуется стендовая защита поисковых и исследовательских работ.
Основные логические связи.
Будем называть высказывание простым (элементарным), если оно рассматривается нами как некое неделимое целое (аналогично атому или элементу множества). Обычно к ним относят высказывания, не содержащие логических связок. Сложным (составным) называется высказывание, составленное из простых с помощью логических связок.
В естественном языке (при вербальном описании явления) роль связок при составлении сложных предложений из простых играют грамматические средства: союзы "и", "или", "не"; слова "если ..., то", "либо ... либо" (в разделительном смысле), "тогда и только тогда, когда" и др. В логике высказываний логические связки, используемые для составления сложных высказываний, обязаны быть определенными точно. Рассмотрим основные логические связки.
Отрицание (логическая связь "не")Записывается Р=Ā или в виде P= ¬A (Читается "Р есть не А"). Отрицанием называется сложное логическое высказывание Р, которое истинно, если А ложно и наоборот. Эта логическая связь может быть проиллюстрирована табл. 3.1, в которой показаны значения истинности сложного высказывания Р в зависимости от значения истинности составляющего его простого высказывания А. Логический элемент «не» в схемах управления часто называется таблица 2.1 схемах управления, часто называется инвертором. Условное обозначение инвертора показано на рис. 2.1. Также ниже (рис. 2.2) приведена диаграмма Венна.

Табл. 2. SEQ Табл._ \* ARABIC 1

Рис. 2. SEQ Рис._ \* ARABIC \s 2 1 Условное обозначение инвертора

Рис. 2. SEQ Рис._ \* ARABIC \s 2 2

Рис. 2. SEQ Рис._ \* ARABIC \s 2 3 Диаграмма Венна (отрицание)
Отрицание является простейшей логической операцией и единственной логической операцией, выполняемой над одним аргументом.
Заметим, что последовательное выполнение двух операций отрицания Ā приводит к исходному значению А.
Конъюнкция
Р = А  В; Р = А & В. (Читается Р есть А и В). Конъюнкция - сложное логическое высказывание, которое истинно только в случае истинности всех составляющих высказываний, в противном случае ложно. Эта логическая связь проиллюстрирована табл. 2.2.

Табл. 2. SEQ Табл._ \* ARABIC 2
В схемах управления логическая операция конъюнкция реализуется в схеме совпадения, показанной на рис. 2.4. Операция конъюнкция часто называется логическим умножением или логической связью "и".

Рис. 2. SEQ Рис._ \* ARABIC \s 2 4 Условное обозначение логического элемента "и"

Рис. 2. SEQ Рис._ \* ARABIC \s 2 5 Диаграмма Венна (конъюнкция)
Рис. 3.1 Условное обозначение инвертора
Заметим, что A  0 = 0; A  Ā = 0; A  1 = A.
ДизъюнкцияР = А  В (читается Р есть А или В). Дизъюнкция - это сложное логическое высказывание, которое ложно только в случае ложности всех составляющих высказываний, в противном случае истинно (vel - или (лат.)).
Дизъюнкция проиллюстрирована табл. 2.3.

Табл. 2. SEQ Табл._ \* ARABIC 3
Операция дизъюнкции часто называется логическим сложением, а также логической операцией "ИЛИ". Схему, воспроизводящую операцию логического сложения обычно называют собирательной схемой. Она изображена на рисунке 2.6.

Рис. 2. SEQ Рис._ \* ARABIC \s 2 6 Условное обозначение логического элемента "ИЛИ"

Рис. 2. SEQ Рис._ \* ARABIC \s 2 7

Рис. 2. SEQ Рис._ \* ARABIC \s 2 8 Диаграмма Венна (дизъюнкция)
Заметим, что A  1 = 1; A  Ā = 1.
Из двух простых высказываний при помощи логических связей можно образовать 16 логических высказываний. Но отрицание, конъюнкция и дизъюнкция являются основными логическими связями, так как все остальные можно образовать из основных логических связей.
Импликация.Импликацией высказываний А и В называется высказывание, обозначенное символами А  В, которое ложно тогда и только тогда, когда А истинно, а В ложно. Читается А влечет В либо "А имплицирует В", импликация - это логическая операция, соответствующая союзу "если... то". Запись А  В означает то же, что и высказывание : "если А то В", "из А вытекает В" "А есть достаточное условие для В", для того чтобы А необходимо, чтобы В ", "В есть необходимое условие для А", " для того чтобы В, достаточно чтобы А". Сравним такие предложения :
1. Если число n делится на 4, то оно делится на 2.
2. Если Иванов увлечен математикой, то Петров ничем не интересуется.
Очевидно, что смысл союза "если... то" в этих предложениях различный. Определение импликации, представленное таблицей истинности,

соответствует смыслу союза, "если... то" в первом предложении. В импликации А  В первый член А называется антецедентом (от лат. antecedens - предшествующий), а второй член В - консеквентом (от лат. consequens - последующий). Из определения импликации следует, что :
1. Импликация с ложным антецедентом всегда истинна.
2. Импликация с истинным консеквентом всегда истинна.
3. Импликация ложна тогда и только тогда, когда ее антецендент истинный, а консеквент ложный.
Принятое определение импликации соответствует употреблению союза "если... то" в предложении "Если будет хорошая погода, то я приду к тебе в гости", которое вы расцените как ложь в том случае, когда погода хорошая, а приятель к вам не придет.
Вместе с тем определение импликации вынуждает считать истинным предложения как "Если 2х2=4, то Москва столица России"; "Если 2х2=5, то я самая красивая девушка России". Это связано с тем, что определениями логических операций смысл составляющих высказываний не учитывается, они рассматриваются как объекты, обладающие единственным свойством - быть истинными либо ложными.

Рис. 2. SEQ Рис._ \* ARABIC \s 2 9 диаграма Венна (импликация)
Эквиваленция или равнозначностьЭквивалвниией высказываний А и В называется высказывание, обозначаемое символом А  В (или ,), которое истинно тогда и только тогда, когда значения истинности высказываний А и В совпадают. (см. таблицу).
Логическая операция, называемая эквивалентностью, соответствует союзу "тогда и только тогда, когда" и читается "А эквивалентно В", "Для того, чтобы А необходимо и достаточно, чтобы В".
Когда мы говорим "А только тогда, когда В" то имеем в виду, что оба предложения А и В одновременно истинны, либо одновременно ложны. Например, говоря: "Я поеду в Ленинград тогда и только тогда, когда ты поедешь в Киев", мы утверждаем, что-либо произойдет и то и другое, либо ни того, ни другого. Можно доказать используя таблицу истинности, что для любых высказываний А и В высказывание (А  В) = 1 тогда и только тогда, когда (А  В) = 1 и (В  А) = 1.
Это утверждение используется при доказательстве теорем вида А  В. Одним из способов доказательства истинности высказывания А  В является доказательство истинности высказывания А  В (необходимость) и истинности высказывания В  А (достаточность).
Высказывания А и В называются равносильными., если (А  В) = 1 говорят, что формулы F1 и F2 равносильны, если их эквиваленция F1  F2 - тавтология (тождественно истинное высказывание).

Рис. 2. SEQ Рис._ \* ARABIC \s 2 10 Диаграмма Венна (эквиваленция)
Запись F1 F2 читается : "формула F1 равносильна формуле F2"
А  В (А В) (В А)
Равносильность есть отношение между формулами (также как равенство отношение между числами, параллельность - отношение между прямыми). Отношение равносильности обладает следующими свойствами:
а) рефлективности F F
б) симметричности: если F1 F2 то F2 F1
в) транзитивности: если F1F2и F2 F3, то F1 F3
Таким образом, в математической логике для записи более сложных высказываний используются следующие логические операции над простыми высказываниями:
НЕ

ИЛИ
влечет
совпадает.
Логическое выражение служит для задания вычислительного процесса нахождения логического значения, подобно тому, как в математике арифметическое выражение служит для задания правил вычисления некоторого числового значения. Напомним, что логическое выражение может иметь только одно из двух возможных значений true (1) или false (0).
Все рассмотренные логические операции иллюстрируются в сводной таблице ##, где булевские числа true и false заменены 1 и 0 соответственно.

Порядок старшинства логических операций следующий: , &, , , .
Для изменения порядка выполнения логических операций используются круглые скобки. В первую очередь выполняются операции в скобках, затем все остальные логические операции в порядке старшинства слева направо.
2.5 Вопросы для самопроверки.
1. В данных составных предложениях выделите составляющие их элементарные предложения и логические связки:
а) диагонали ромба взаимно перпендикулярны и делят его углы пополам;
б) треугольник является равносторонним тогда и только тогда, когда все его углы конгруэнтны.
2. Определите значение истинности высказываний A, B, C, D, если:
а) А (2 * 2) = 4 – истинное высказывание;
б) В (2 * 2) = 4 – ложно;
в) С (2 * 2) = 5 – истинно;
г) В (2 * 2) = 5 – ложно;
3. Изобразите на координатной плоскости множество точек, координаты которых обращают следующие высказывательные формы в истинные высказывания :
а) (х > 0) (у > 0), б) (х > 0) (у < 0), в) (х < 0) (у < 0)
г) (х = 0) (у = 0), д) (х = 0) (у = 0), е) (х > 0) (у > 0)
ж) (х > 0) (у = 0), з) (х > 0) (у < 0).
4. Сформулируйте и запишите в вида конъюнкции или дизъюнкции условие истинности каждого предложения :
а) ab 0, б) ab = 0, в) а2 + b2 = 0, г) а / b = 0, д) | а | > 2, е) | а | < 2
5. Следующие предложения запишите без знака отрицания :

6. Определите значения истинности следующих высказываний :
а) если 12 делится на 6, то 12 делится на 3;
б) если 11 делится на 6, то 11 делится на 3;
в) если 15 делится на 6, то 15 делится на 3;
г) если 15 делится на 3. то 15 делится на 6;
д) если Париж расположен на Темзе, то белые медведи живут в Африке;
е) 12 делится на 6 тогда и только тогда, когда 12 делится на 3;
ж) 11 делится на 6 тогда и только тогда, когда 11 делится на 3;
з) 15 делится на 6 тогда и только тогда, когда 15 делится на 3.
7. Пусть через А обозначено высказывание "9 делится на З", а через В - высказывание "10 делится на З". Определите значения истинности следующих высказываний:
; ; ; ; ; ; ; ; ; ; .
8. Определите значение истинности высказываний A, B, C, D в предложениях, а, б, д, е из которых истинны, а в, г, ж, з – ложны:
а) Если 4 нечетное число, то А;
б) Если В, то 4 нечетное число;
в) Если 4 четное число, то С;
г) Если D, то 4 нечетное число;
д) А (2 < 3);
е) В (2 > 3);
ж) С (2 < 3);
з) D (2 > 3).
9. Придумайте по два примера : а) истинной импликации с истинным антецедентом; б) истинной импликации с ложным консеквентом; в) ложной импликации; г) истинной эквивалентности; д) ложной эквивалентности.
10. Сформулируйте в виде импликации: "Диагонали ромба взаимно перпендикулярны", "Во всяком треугольнике сумма внутренних углов равна 180°".
11. Найдется ли такой день недели, когда: а) утверждение "Если сегодня понедельник, то завтра пятница" истинно; б) "Если сегодня понедельник, то завтра вторник" ложно.
12. Известно, что если число делится на 6, оно делится на 3 и 2. Сформулируйте это в виде импликации.
Задача №1. В соревнованиях по гимнастике на первенство школы участвуют Алла, Валя, Таня и Даша. Болельщики высказали предположения о возможных победителях:
1: «Первой будет Таня, Валя будет второй».
2: «Второй будет Таня, Даша – третьей».
3: «Алла будет второй, Даша – четвертой».
По окончании соревнований оказалось, что в каждом предположении только одно из высказываний истинно, другое же ложно. Какое место на соревнованиях заняла каждая из девочек, если все они оказались на разных местах?
Решение. Решение логической задачи с помощью рассуждений
Сначала предположим, что в первом предложении первое высказывание истинно, а второе ложно, т.е. Таня заняла первое место. Тогда во втором предложении первое высказывание ложно, а второе истинно, т.е. Даша заняла третье место. Тогда в третьем предложении второе высказывание ложно, а первое истинно, т.е. Алла заняла второе место. Тогда четвертое место заняла Валя, и поскольку мы выяснили, что в первом предложении второе высказывание ложно, то получается, что наше исходное предположение было верным.
Для полноты решения рассмотрим вариант, когда в первом предложении первое высказывание ложно, а второе истинно, т.е. Валя заняла второе место. Тогда во втором предложении первое высказывание ложно, а второе истинно, т.е. Даша заняла третье место. В третьем предложении первое высказывание ложно (так как в нашем предположении Валя заняла второе место), значит, истинно второе высказывание, т.е. Даша заняла четвертое место. Получили противоречие (Даша заняла третье место и Даша заняла второе место), которое доказывает, что наше исходное предположение было неверно. Итак, Таня заняла первое место, Алла - второе, Даша - третье, Валя - четвертое.
Решение логической задачи средствами алгебры логики
В условии задачи приведены высказывания болельщиков о возможных победителях и известно, что каждый из них один раз сказал правду, а один раз ошибся. Решение задачи заключается в том, что необходимо найти истинное высказывание, отвечающее на вопрос задачи.
Введем буквенные обозначения всех высказываний, задающих условие задачи:
T1 — «Таня будет первой»; W2 — «Валя будет второй»; T2 —«Таня будет второй»; D3 — «Даша будет третьей»; A2 — «Алла будет второй»; D4 —«Даша будет четвертой».
Запишем сложные высказывания болельщиков, учитывая, что каждый из них один раз был прав, а другой – ошибся.
1 болельщик: «Первой будет Таня, Валя будет второй». Можно перефразировать это высказывание так: «Таня будет первой, а Валя не будет второй или Таня не будет первой, а Валя будет второй». Запишем данное высказывание по правилам алгебры логики: . Мы получили истинное высказывание, поэтому его можно приравнять 1 (1- истина, 0 – ложь): .
2 болельщик: «Второй будет Таня, Даша – третьей» —
3 болельщик: «Алла будет второй, Даша – четвертой» —
Таким образом, мы получили систему логических уравнений:

Помним, что в условии сказано: в каждом предположении одно высказывание истинно, другое — ложно. Следует учесть и то, что ни одно место не было разделено участниками. Это условие можно задать формулами:
A2W20 или (4)
T2A20 или (5)
T2W20 или (6)
То обстоятельство, что ни один участник не может занять два разных места, задано формулами (7) и (8).
D3D40 или (7)
T1T20 или (8)
Система уравнений решается умножением одного уравнения на другое и нахождением истинного выражения. Уравнения (4)-(8) используем при упрощении логических выражений.
Умножая уравнение (1) на (2), получим (9):
(9)
Умножаем полученное уравнение (9) на (3), получаем:
Ответ: полученное выражение свидетельствует о том, что Таня заняла первое место; Даша - третье; Алла – второе, а Валя - четвертое.Графический способ решения логической задачи.
Графический способ решения логических задач заключается в вычерчивании «дерева логических условий». «Дерево» выражает в виде простого чертежа логическую взаимосвязь между данными высказываниями. Каждому простому высказыванию (с отрицанием или без) на дереве соответствует одна ветвь. Логической сумме (дизъюнкции) на логическом дереве соответствует «разветвление» ветвей, логическому произведению (конъюнкция) — «следование» ветвей друг за другом.
Для вычерчивания графического дерева задачи №1 обратимся к высказываниям болельщиков (или можно воспользоваться уравнениями (1), (2), (3)).

Рис.6.
Проанализируем каждую ветвь. Для этого для каждой пронумерованной ветви выписываем формулу. Каждая ветвь состоит из последовательно соединенных частей, что соответствует логической операции конъюнкция.
Ветвь 1: . Полученная формула принимает ложное значение , т.к. T1T20, A2T20
Ветвь 2: т.к. T1T20, D3D4 0
Ветвь 3:
Ветвь 4: , т.к. D3D4 0
Ветвь 5: , т.к. W2T20, T2A2, W22
Ветвь 6: , т.к. W22
Ветвь 7: , т.к. W22
Ветвь 8: , т.к. D3D4
Итак, только выражение ветви 3 эквивалентно 1:
Из этого выражения следует: Таня - первая; Алла - вторая; Даша - третья; Валя - четвертая.
Решение логических задач на ЭВМ.
Решить задачу на ЭВМ, значит найти истинное логическое выражение, отвечающее на поставленный в задаче вопрос. Чтобы это выполнить, необходимо перебрать все возможные значения T1, W2 , T2, D3, A2, D4 и выбрать истинное значение основной функции (F), которая равна логическому произведению уравнений (1)-(8).
Учитывая, что каждое простое высказывание (T1, W2 , T2, D3, A2, D4) может принимать только два значения истина (1) и ложь (0), то в алгоритме и программе будут использованы вложенные циклы с параметром (начальное значение параметра цикла равно 0, конечное – 1). По правилам алгоритмического языка записываются выражения (1)-(8). В случае, если F принимает значение 1 (истина), то мы выводим на экран сообщение о том, какие значения принимают T1, W2, T2, D3, A2, D4.
Алгоритм.
алг Задача № 1 (цел T1, W2, T2, D3, A2, D4, F)
арг T1, W2, T2, D3, A2, D4
рез F
нач цел F1, F2, F3, F4, F5, F6, F7, F8
нц для T1 от 0 до 1 шаг 1
нц для W2 от 0 до 1 шаг 1
нц для T2 от 0 до 1 шаг 1
нц для D3 от 0 до 1 шаг 1
нц для A2 от 0 до 1 шаг 1
нц для D4 от 0 до 1 шаг 1
F1:=(T1 и не W2) или (не T1 и W2)
F2:=(T2 и не D3) или (не T2 и D3)
F3:=(A2 и не D4) или (не A2 и D4)
F4:=не(A2 и W2)
F5:=не (T2 и A2)
F6:=не (T2 и W2)
F7:=не (D3 и D4)
F8:=не (T1 и T2)
F:=F1 и F2 и F3 и F4 и F5 и F6 и F7 и F8
если F=1
то вывод F, T1, W2, T2, D3, A2, D4
все
кц
кц
кц
кц
кц
кц
кон
Программа на Паскале:
PROGRAM LOGIKA1;
USES CRT;
VAR T1, W2, T2, D3,A2, D4, F1, F2, F3, F4, F5, F6, F7, F8, F:
INTEGER;
BEGIN
CLRSCR;
FOR T1:=0 TO 1 DO BEGIN
FOR W2:=0 TO 1 DO BEGIN
FOR T2:=0 TO 1 DO BEGIN
FOR D3:=0 TO 1 DO BEGIN
FOR A2:=0 TO 1 DO BEGIN
FOR D4:=0 TO 1 DO BEGIN
F1:=(T1 AND NOT W2) OR (NOT T1 AND W2);
F2:=(T2 AND NOT D3) OR (NOT T2 AND D3);
F3:=(A2 AND NOT D4) OR (NOT A2 AND D4);
F4:=NOT(A2 AND W2);
F5:=NOT(T2 AND A2);
F6:=NOT(T2 AND W2);
F7:=NOT(D3 AND D4);
F8:=NOT(T1 AND T2);
F:=F1 AND F2 AND F3 AND F4 AND F5 AND F6 AND F7 AND F8;
IF F=1 THEN BEGIN WRITELN(' F ','T1 ','W2 ','T2 ','D3 ','A2',' D4 ');
WRITELN(F:3, T1:3,W2:3,T2:3,D3:3,A2:3,D4:3); END;
END; END; END; END; END; END;
END.
В результате работы ЭВМ по программе будет выведен текст:

Это означает, что F=1, T1=1, W2=0, T2=0, D3=1, A2=1, D4=0. На основе введенных обозначений получаем, Таня заняла первое место, Алла – второе, Даша – третье, а Валя – четвертое.
Решение логических задач с помощью электронных таблиц.
Нам необходимо найти истинное логическое выражение, соответствующее условию задачи. Как уже было сказано выше, задача сводится к перебору всех возможных комбинаций и определению истинного выражения F.
Технология работы.
1. Подпишем колонки, для этого в ячейки A1:F1 поместим текстовую информацию «T1, W2 , T2, D3, A2, D4».
2. В ячейки A2:F65 вводим все возможные наборы значений для T1, W2, T2, D3, A2, D4 (надо помнить, что это значения 1 (истина) и 0 (ложь)).
3. В ячейках G2:G65 вычисляем выражение (1). Для этого в ячейку G2 помещаем формулу =ИЛИ(И(A2;НЕ(B2));И(НЕ(A2);B2)), а затем копируем эту формулу в ячейки G3:G65.
5. В ячейках H2:H65 вычисляем выражение (2) — =ИЛИ(И(C2;НЕ(D2));И(НЕ(C2);D2)).
6. В ячейках I2:I65 – вычисляем выражение (3) — =ИЛИ(И(E2;НЕ(F2));И(НЕ(E2);F2)).
7. В ячейках J2:N65 – формулы (4)-(8):
=НЕ(И(E2;B2))
=НЕ(И(C2;E2))
=НЕ(И(C2;B2))
=НЕ(И(D2;F2))
=НЕ(И(A2;C2))
8. В ячейках O2:O65 — общее выражение =И(G2;H2;I2;J2;K2;L2;M2;N2), т.е. вычислено логическое умножение (1) ∙ (2) ∙(3) ∙ (4) ∙ (5) ∙ (6) ∙ (7) ∙ (8).


В строке 40 функция F приняла значение истина, это и есть полученный результат.

Домашнее задание.
Задача 2. В спортивных соревнованиях принимали участие пять пионерских команд: "Вымпел", "Метеор", "Нептун", "Старт" и "Чайка". Об их итогах соревнования имеется пять высказываний:
1) Второе место занял "Вымпел", a "Cтарт" оказался на третьем.
2) Хорошо выступала команда "Нептун", она стала победителем, а "Чайка" вышла на второе место.
3) Да нет же, " Чайка" заняла только третье место, а "Нептун"- был последним.
4) Первое место по праву завоевал "Cтарт", а "Метеор" был четвертым.
5) Да, "Метеор" действительно был четвертым, а "Вымпел" был вторым.
Известно, что команды не делили места между собой и что в каждом высказывании одно утверждение правильное, а другое нет.
Как распределились места между командами?
2.1. Основные понятия теории графов. Применение ее при решении логических задач.
В математике определение графа дается так:
Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)
Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3)
Графы, в которых построены все возможные ребра, называются полными графами. (рис.4)

Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.
Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.
На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А. На рисунке : Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.
рис.5
3295659525
Задача №1.
Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
Решение:
Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию — отрезок или часть кривой, соединяющая конкретные точки — имена.

Если подсчитать число ребер графа, изображенного на рисунке справа, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.
Задача №2.
В одном дворе живут четыре друга. Вадим и шофер старше Сергея, Николай и слесарь занимаются боксом, электрик-младший из друзей.
По вечерам Андрей и токарь играют в домино против Сергея и электрика.
Определите профессию каждого из друзей.
Решение. Составим граф из 4 друзей и 4 профессий. Пунктирными линиями отметим невозможные связи, а сплошной - соответствие имени и профессии. Если от каждой вершины выходить 3 пунктирных линии, то четвертая линия должна быть сплошной.

В С Н А


Ш С Т Э
Задача №3.
В небольшом городке живут пять друзей: Иванов, Петренко, Сидорчук, Гришин и Капустин. Профессии у них разные: один из них маляр, другой- мельник, третий- плотник, четвертый-почтальон, а пятый- парикмахер.
Петренко и Гришин никогда не держали в руках малярной кисти.
Иванов и Гришин собираются посетить мельницу, на которой работает их товарищ. Петренко и Капустин живут в одном доме с почтальоном.
Сидорчук был недавно в ЗАГСе одним из свидетелей, когда Петренко и дочь парикмахера сочетались законным браком. Иванов и Петренко каждое воскресенье играют в городки с плотником и маляром.
Гришин и Капустин по субботам обязательно встречаются в парикмахерской, где работает их друг. Почтальон предпочитает бриться сам. Кто есть кто?
Решение.
Иванов Петренко Сидорчук Гришин Капустин



маляр мельник плотник почтальон парикмахер
2.2. Эйлеровы пути. Построение фигуры одним росчерком.
Сформулируем некоторые закономерности, присущие определенным графам.
Закономерность 1.
Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.
Доказательство:
Эта закономерность очевидна уже после рассмотрения любого полного графа. Каждая вершина соединена ребром с каждой вершиной, кроме самой себя, т. е. из каждой вершины графа, имеющего n вершин, исходит n—1 ребро, что и требовалось доказать.
Закономерность 2.
Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.
Эта закономерность справедлива не только для полного, но и для любого графа.
Доказательство:
Действительно, каждое ребро графа связывает две вершины. Значит, если будем складывать число степеней всех вершин графа, то получим удвоенное число ребер 2R (R — число ребер графа), т. к. каждое ребро было подсчитано дважды, что и требовалось доказать.
Теорема.
Число нечетных вершин любого графа четно. Доказательство:
Рассмотрим произвольный граф Г. Пусть в этом графе число вершин, степень которых 1, равна К1; число вершин, степень которых 2, равно K2; ...; число вершин, степень которых n, равно Кn. Тогда сумму степеней вершин этого графа можно записать какK1 + 2К2 + ЗК3 + ...+ nКn. С другой стороны: если число ребер графа R, то из закономерности 2 известно, что сумма степеней всех вершин графа равна 2R. Тогда можно записать равенствоK1 + 2К2 + ЗК3 + ... + nКn = 2R. Выделим в левой части равенства сумму, равную числу нечетных вершин графа (К1 + К3 + ...):K1 + 2К2 + ЗК3 + 4К4 + 5К5 + ... + nКn = 2R, (К1 + К3 + К5 +...) + (2K2 + 2K3 +4K4 + 4К5 + ...)=2R Вторая скобка- четное число как сумма четных чисел. Полученная сумма (2R) четное число. Отсюда (К1 + К3 + К5 +...)-четное число.
Что и требовалось доказать.
Задача №4.
Можно ли 25 приборов соединить проводами так, чтобы каждый прибор был соединен ровно с пятью другими?
Решение .
Невозможно. В таком графе было бы нечетное число вершин нечетной степени.
Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2.Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2:Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.
Задача №5.
В первенстве класса по настольному теннису 6 участников: Андрей, Борис Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис – с Андреем, Галиной; Виктор – с Галиной, Дмитрием, Еленой; Галина – с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось?
Решение:
Построим граф. Сыгранные игры отметим синими линиями, красными дополним до полного графа. Получим, что сыграно 7 игр, а осталось – 8. Можно проверить: в графе 6 вершин тогда всего ребер 6*5/2=15 (7+8).

Эйлеровы графы.
Эйлеров путь - путь в графе, проходящий через каждое ребро ровно один раз.
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. (рис.6) Такими графы названы в честь учёного Леонарда Эйлера.
рис.6 (эйлеровы графы)
Закономерность 3 (вытекает из рассмотренной нами теоремы).Невозможно начертить граф с нечетным числом нечетных вершин. Закономерность 4.
Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине. Закономерность 5.
Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них. Закономерность 6.
Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.
Задача № 6 о кенигсбергских мостах.
3577590379095-70485626745Рукава реки Прегель, на берегу которой расположен город Кенигсберг, образовывали два острова. В эту эпоху четыре образовавшихся участка суши (правый и левый берег и два острова) соединяло семь мостов так, как это показано на рисунке. Горожане, гуляя по городу, пытались составить маршрут, чтобы он проходил по каждому мосту ровно один раз.
Решение.
Эту задачу решил Леонард Эйлер. Он построил следующий граф и получил, что все четыре вершины нечетные, то есть нельзя пройти по всем мостам один раз и закончить путь там, где он был начат.
Задача № 7.
Четыре острова соединены между собой и с берегами реки 14 мостами так, как это показано на рисунке. Можно ли за одну прогулку обойти все эти мосты, побывав на каждом из них один раз?
Решение. Построим граф. Имеются две нечетные вершины В и С. Следовательно за одну прогулку можно обойти все мосты, побывав на каждом из них один раз. При этом прогулку надо начинать с острова В и заканчивать на острове С или наоборот.
53340139065
533400635
Задача №8.
Можно ли нарисовать графы, изображенные на рисунках, не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

Решение:
Можно, т. к. только 2 нечетные вершины.
Нельзя, т. к. 4 нечетные вершины.
4777740155575Задача №9.
Говорят, что Магомет вместо подписи (он был неграмотен) описывал одним росчерком состоящий из двух рогов луны знак, представленный на рисунке. Возможно ли это?
Решение. Да, потому что в данном случае мы имеем дело с вершинами четного порядка.
Задача №10. Муха в банке.
Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру? Подпрыгивать и перелетать с места на место не разрешается.
Решение.
Ребра и вершины образуют граф, все 8 вершин которого имеют 3 степень, и, следовательно, требуемый обход невозможен.
Задача № 11.
Попробуйте построить данные фигуры одним росчерком.

2.3. Плоские графы.
Интересующая меня задача «о трёх домах и трёх колодцах» подтолкнула развитие теории графов. Граф, который можно нарисовать на плоскости так, чтобы его рёбра не пересекались нигде, кроме вершин, называются плоским или планарным.
Эйлер доказал теорему, которая даёт отрицательный ответ на вопрос этой задачи.
Теорема Эйлера.
Если граф, имеющий n вершин и m ребер,- плоский, тогда справедливо равенство n-m+p=2, где p количество непересекающихся частей (их называют гранями), на которые этот граф разбивает плоскость.
Доказательство.
Граф «три дома и три колодца» имеет шесть вершин и девять рёбер. Если он плоский, количество граней p должно быть равно p = n – m + 2 = 9 - 6 + 2 = 5. Но так как никакие два дома или два колодца не соединены между собой, каждая грань имеет, по меньшей мере, четыре ребра. Получим неравенство 2n ≥ 4p(каждое ребро считается два раза), откуда получаем ложное неравенство 18 ≥ 20. Аналогично доказывается, что полный пятивершинный граф также не может быть плоским.
Теорема Понтрягина – Куратовского.
Граф является плоским тогда и только тогда, когда он не содержит графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами.


ДАЛЬНЕВОСТОЧНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
Положение об учебно-методических комплексах дисциплин образовательных программ среднего профессионального образования
Разработчики
Идентификационный номер Лист
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный университет» (ДВФУ)
Филиал ДВФУ в г. Арсеньеве
ПРАКТИЧЕСКИЕ РАБОТЫ
по дисциплине «Элементы математической логики»
Специальность «Информационные системы (по отраслям)»
Практическая работа № 1
Тема: Множества. Элементы множеств.
Цель: Научиться составлять высказывания используя логические связки. Научиться изображать множества элементов графически
В-1
Что такое силлогизм?
Приведите примеры составных высказываний, используя логические связки «И»
Дайте определение «конъюнкции»
Дайте определение пересечения множеств,
Дано У={1;2;3;4;5;6;7;8;9} Х={2; 4; 6; 8 }
Найти Х∩ У, Х U У
Изобразите геометрически (кругами) множества D={10,11,12,…, 98,99} F={10,20,…, 90}
На корабле «Пиратское счастье» несколько кошек, несколько матросов, кок и одноногий капитан. У всех них вместе взятых 15 голов и 41 нога. Сколько кошек было на корабле?
Пусть а= «эта звездная ночь», а в= «эта холодная ночь». Выразите следующие формулы на обычном языке:
1). А и b
Что нужно изменить в условии, чтобы высказывания изменили истинность ложностью.
В-2
Что такое силлогизм?
Приведите примеры составных высказываний, используя логические связки«ИЛИ»
Дайте определение «дизъюнкции»
Дайте определение объединение множеств
Дано У={1;2;3;4;5;6;7;8;9} Х={2; 4; 6; 8 }
Найти Х\У, У\Х
Изобразите геометрически (кругами) множества D={10,11,12,…, 98,99} F={10,20,…, 90}
На корабле «Пиратское счастье» несколько кошек, несколько матросов, кок и одноногий капитан. У всех них вместе взятых 15 голов и 41 нога. Сколько кошек было на корабле?
Пусть а= «эта звездная ночь», а в= «эта холодная ночь». Выразите следующие формулы на обычном языке:
1). А или b
Что нужно изменить в условии, чтобы высказывания изменили истинность ложностью.
Практическая работа № 2
Тема: «Множества. Круги Эйлера»
Цель: Научиться графически решать задачи с помощью множеств.
Варииант-1
1.
Если E1={2; 4; 6} и E2={6; 8; 10}. то E1\E2 ; E2\E1 ; E1 ∩E2 E1 UE2
2
Если K1={1; 3; 5; 7; 9}, K2={5; 7; 1}. Найти K1 \K2, K2\K1, K1∩K2, K1 UK2
3
Из 40 опрошенных человек 32 любят молоко, 21 – лимонад, а 15 – и молоко, и лимонад. Сколько человек не любят ни молоко, ни лимонад?
4
В воскресенье 19 учеников нашего класса побывали в планетарии, 10 – в цирке и 6 – в музее. Планетарий и цирк посетили 5 учеников; планетарий и музей – трое, в цирке и музее был один человек. Сколько учеников в нашем классе, если никто не успел посетить все три места, а трое вообще никуда не ходили?
Варииант-2
1
Если M1={x1; x2; x3}, M2={y1; y2}. Найти M1\M2,
M2\M1 M1∩M2 M1UM2
2
Если K1={1; 3; 5; 7; 9}, K2={5; 7; 1}. Найти K1 \K2, K2\K1, K1∩K2, K1 UK2
3
В детском лагере отдыхало 70 ребят. Из них 20 занимаются в драмкружке, 32 поют в хоре, 22 увлекаются спортом. В драмкружке 10 ребят из хора, в хоре 6 спортсменов, в драмкружке 8 спортсменов, а 3 спортсмена посещают и драмкружок, и хор. Сколько ребят не поют в хоре, не увлекаются спортом и не занимаются в драмкружке? Сколько ребят заняты спортом?
4
Из сотрудников фирмы 16 побывали во Франции, 10 – в Италии, 6 – в Англии. В Англии и Италии – пятеро, в Англии и Франции – 6, во всех трёх странах – 5 сотрудников. Сколько человек посетили и Италию, и Францию, если всего в фирме работает 19 человек, и каждый их них побывал хотя бы в одной из названных стран?
Практическая работа № 3
Тема: Операции над множествами
Цель: Научиться применять теоретико-множественные операции включения, объединения, пересечения при решении задач
Задача 1
Из 40 опрошенных человек 32 любят молоко, 21-лимонад, а 15 – и молоко, и лимонад. Сколько человек не любят ни молоко, ни лимонад?
Задача 2
В воскресенье 19 учеников нашего класса побывали в планетарии, 10 – в цирке и 6 – в музее. Планетарий и цирк посетили 5 учеников; планетарий и музей – трое, в цирке и музее был один человек. Сколько учеников в нашем классе, если никто не успел посетить все три места, а трое вообще никуда не ходили?
Задача 3
В детском лагере отдыхало 70 ребят. Из них 20 занимаются в драмкружке, 32 поют в хоре, 22 увлекаются спортом. В драмкружке 10 ребят из хора, в хоре 6 спортсменов, в драмкружке 8 спортсменов, а 3 спортсмена посещаемость и драмкружок, и хор. Сколько ребят не поют в хоре, не увлекаются спортом и не занимаются в драмкружке? Сколько ребят заняты спортом?
Задача 4
Из сотрудников фирмы 16 побывали во Франции , 10 – в Италии, 6 – в Англии. В Англии и Италии – пятеро, в Англии и Франции – 6, во всех трех странах – 5 сотрудников. Сколько человек посетило и Италию, и Францию, если всего в фирме работает 19 человек, и каждый из них побывал хотя бы в одной из названных стран?
Практическая работа № 4
Тема: Алгебра логики
Цель: Научиться составлять таблицы истинности для данной формулы, используя законы алгебры логики
Вариант-1
1. Составьте таблицы истинности для формул:
а) решение
x y
0 0 1 0 0 1 1
0 1 1 1 0 1 1
1 0 0 1 0 1 1
1 1 0 1 1 0 1
б)
в)
3.2. Установите с помощью таблиц истинности какие из следующих формул - тавтологии:
а)
в)
д)
3. На основании каких законов логики получены следующие соотношения? Докажите их с помощью таблиц истинности :
; ;
4. Какие из данных формул равносильны:
а) б) в) г)
д) е) ж) з)
Вариант-2
1. Составьте таблицы истинности для формул:
а) решение
x y
0 0 1 0 0 1 1
0 1 1 1 0 1 1
1 0 0 1 0 1 1
1 1 0 1 1 0 1
б)
в)
3.2. Установите с помощью таблиц истинности какие из следующих формул - тавтологии:
а)
б)
в)
3. На основании каких законов логики получены следующие соотношения? Докажите их с помощью таблиц истинности :
; ;
4. Какие из данных формул равносильны:
а) б) в) г)
д) е) ж) з)
Практическая работа № 5
Тема: "ИСТИННОСТЬ ВЫСКАЗЫВАНИЙ. ЭКВИВАЛЕНТНОСТИ".
Цель: Научиться доказывать эквивалентность высказываний с помощью таблиц истинности
Докажите эквивалентность:

2. Докажите, является ли данное высказывание тавтологией:

3. Установите истинность высказывания:

4. Для формулы придумайте формализуемое ею высказывание:

5. Данное высказывание преобразуйте в эквивалентное, но уже не содержащее отрицаний сложных высказываний:

6. Упростите:

Практическая работа № 6
Тема "Формулы алгебры логики".
Цель: Составление таблиц истинности для формул
Докажите эквивалентность:
Докажите, является ли данное высказывание тавтологией:

Установите истинность высказывания:

Для формулы придумайте формализуемое ею высказывание:

Данное высказывание преобразуйте в эквивалентное, но уже не содержащее отрицаний сложных высказываний:

Упростите:
Практическая работа № 7
Тема: Равносильные преобразования
Цель: Научиться упрощать выражения используя формулы алгебры логики.
Вариант №1.
Докажите эквивалентность:

Докажите, является ли данное высказывание тавтологией:

Установите истинность высказывания:

Для формулы придумайте формализуемое ею высказывание:

Данное высказывание преобразуйте в эквивалентное, но уже не содержащее отрицаний сложных высказываний:

6. Упростите:

Вариант №2.
1. Докажите эквивалентность:

Докажите, является ли данное высказывание тавтологией:

Установите истинность высказывания:

Для формулы придумайте формализуемое ею высказывание:

Данное высказывание преобразуйте в эквивалентное, но уже не содержащее отрицаний сложных высказываний:

Упростите:

Практическая работа Тема:«Графы»
Цель работы: обучение построению графовых схем;
Задание 1
Нарисовать ориентированный граф (блок-схему) проверки учителем пачки тетрадей. В систему команд входят команды: проверить работу, взять тетрадь из пачки; выставить оценку, выяснить, остались ли еще не проверенные тетради.
Задание 2
Построить родословное дерево потомков Владимира Мономаха.
Потомки Владимира Мономаха
Владимир Мономах умер в 1125 г. Он оставил четырех сыновей: Мстислава (год смерти — 1132), Ярополка (1139), Вячеслава Туровского (1154) и Юрия Долгорукого (1157). После Мстислава остались три сына: Изяслав Волынский (1154), Всеволод Новгородский (1138) и Ростислав Смоленский (1168). У Изяслава Волынского был сын Мстислав (1170), у Мстислава — сын Роман (1205), у Романа — Даниил Галицкий (1264). Ростислав Смоленский имел четырех сыновей: Романа (1180), Рюрика (1215), Давида (1197) и Мстислава Храброго (1180). После Романа Ростиславича остался сын Мстислав Киевский (1224), после Мстислава Храброго — сын Мстислав Удалой (1228). Юрий Долгорукий имел трех сыновей: Андрея Боголюбского (1175), Михаила (1177) и Всеволода (1212). Сыновьями Всеволода были Константин (1217), Юрий (1238) и Ярослав (1246). У Ярослава Всеволодовича было три сына: Александр Невский (1263), Андрей Суздальский (1264) и Ярослав Тверской (1272). Сыновья Александра Невского: Димитрий Переяславский (1294), Андрей Городецкий (1304) и Даниил Московский (1303). У Андрея Суздальского был сын Василий (годы его жизни неизвестны), у Ярослава Тверского — сын Михаил (1318).
Глядя на полученное дерево, ответьте на вопрос: сколько поколений князей оно отражает?
Задание 3
На острове Буяне четыре государства, каждое из которых граничит с тремя другими. Нарисуйте карту острова. Рассмотрите все варианты.
Практическая работа № 9
Тема: Графы
Цель: Научиться чертить полные графы одним росчерком,
решать задачи табличным способом
Скольким ребрам принадлежит вершина в полном графе с n вершинами,
n=3, n=5, n=k?
Существует ли полный граф с семью ребрами?
Сколько ребер в полном графе с n вершинами, если
n =3, n=4, n=5?
Попробуйте, не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии, вычертить следующие фигуры.

В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что:
Вода и молоко не в бутылке.
Сосуд с лимонадом стоит между кувшином и сосудом с квасом.
В банке не лимонад и не вода.
Стакан стоит между банкой и сосудом с молоком.
В каком сосуде находится, какая из жидкостей?
Шесть школьников участвуют в круговом шахматном турнире. Доказать, что среди них найдутся три участника, которые уже провели все встречи между собой или еще не сыграли друг с другом ни одной партии.
Сколько различных способов обедов П.И.Чичиков мог насчитать из блюд, выставленных на столе у П.П.Петуха, если бы на каждый обед выбирать одно холодное блюдо, одно первое, одно второе, одно третье? На столе у П.П.Петуха на этот раз были выставлены студень с хреном, красная икра, свежепосоленная рыба; на первое – уха из стерляди, щи с грибами; на второе – осетрина жаренная, теленок жареный на вертеле; на третье – арбузы, груши.
Какое наименьшее число переливаний необходимо для того, чтобы с помощью 7-и 11-литровых сосудов и крана с водой отмерить 2 литра?
Сколько существует различных трехзначных чисел, в записи которых участвуют лишь цифры 1, 2, 3 и 4?
В семье четверо детей. Им 5, 8, 13 и 15 лет. Зовут их Аня, Боря, Вера и Галя. Сколько лет каждому ребенку, если одна девочка ходит в детский сад, Аня старше Бори, а сумма лет Ани и Веры делится на три?
Практическая работа № 10
Тема: Рылейно-контактные схемы
Цель: Научиться применять законы математической логики при составлении и упрощении рылейно-контактных схем
1.Составить таблицы истинности для формул.
2. Установить эквивалентность формул с помощью таблиц истинности . и
Упростить формулы.
4.Упростить схемы.







1









2



ДАЛЬНЕВОСТОЧНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
Положение об учебно-методических комплексах дисциплин образовательных программ среднего профессионального образования
Разработчики
Идентификационный номер Лист
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
«Дальневосточный федеральный университет» (ДВФУ)
Филиал ДВФУ в г. Арсеньеве
ГЛОССАРИЙ
по дисциплине «Элементы математической логики»
Специальность «Информационные системы (по отраслям)»
А
Алгебра Буля — исторически первый раздел математической логики, разработанный ирландским логиком и математиком Дж. Булем в середине XIX в. Буль применил алгебраические методы для решения логических задач и сформулировал на языке алгебры некоторые фундаментальные законы мышления. Алгоритм (Алгорифм) — (от Algorithmi — латинизированная форма имени выдающегося среднеазиатского ученого АльХорезми) — конечный набор правил, позволяющих чисто механически решать любую конкретную задачу из некоторого класса однотипных задач
Ациклический граф — граф без циклов.
Б
Бессмысленное — языковое выражение, не отвечающее требованиям синтаксиса или семантики языка. Б. представляет собой конфликт с правилами языка, выход за рамки установок, регламентирующих общение людей с помощью языка. 
Биграф — см. двудольный граф.
В
Вывод Логический — рассуждение, в ходе которого из к.л. исходных суждений — посылок — с помощью логических правил получают заключение — новое суждение. Высказывание — грамматически правильное повествовательное предложение, взятое вместе с выражаемым им смыслом. 
Вершина, Узел — базовое понятие: точка, где могут сходиться/выходить рёбра и/или дуги. Множество вершин графа G обозначается V(G).
Высота дерева — наибольшая длина пути от корня к листу.
Г
Геометрический граф — плоская фигура из вершин — точек плоскости и рёбер — линий, соединяющих некоторые пары вершин. Может представлять многими способами всякий граф.
Гиперграф — совокупность из множества вершин и множества гиперрёбер (подмножество n-й евклидовой степени множества вершин, то есть гиперрёбра соединяют произвольное количество вершин).
Грань — область, ограниченная рёбрами в плоском графе, и не содержащая внутри себя вершин и рёбер графа. Внешняя часть плоскости тоже образует грань.
Граф — базовое понятие. Включает множество вершин и множество рёбер, являющееся подмножеством декартова квадрата множества вершин (то есть каждое ребро соединяет ровно две вершины).
Д
Диаграммы Венна — геометрическое наглядное представление отношений между классами (объемами понятий) в булевой алгебре с помощью кругов или иных фигур. Диалектическая Логика — название философской теории, пытавшейся выявить, систематизировать и обосновать в качестве универсальных основные особенности мышления коллективистического общества (средневекового феодального общества, тоталитарного общества и др.). Основной принцип Д.л. (ее «ядро») провозглашает сближение и отождествление противоположностей: имеющегося в разуме и существующего в действительности, количества и качества, исторического и логического, свободы и необходимости и т. д. Дизъюнкция — (от лат. disjunctio — разобщение, различение) — логическая операция — аналог употребления союза «или» в обычном языке, с помощью которой из двух или более исходных суждений строится новое суждение. 
Граф-звезда — полный двудольный граф .
И
Изолированная вершина — вершина, степень которой равна 0 (то есть нет ребер инцидентных ей).
К
Клетка — регулярный граф наименьшего обхвата для заданной степени вершин.
Плоский граф — геометрический граф, в котором никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины (не пересекаются). Является уложенным графом на плоскости.
Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножествоинцидентных им рёбер. (ср. Суграф.) По отношению к подграфу исходный граф называется суперграфомПолный граф — граф, в котором для каждой пары вершин , существует ребро, инцидентное  и инцидентное (каждая вершина соединена ребром с любой другой вершиной).
Р
Расстояние между вершинами — длина кратчайшей цепи (в орграфе пути), соединяющей заданные вершины. Если такой цепи (пути) не существует, расстояние полагается равным бесконечности.
Ребро — базовое понятие. Ребро соединяет две вершины графа.
С
Самодвойственный граф — граф, изоморфный своему двойственному графу.
Связность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.
Связный граф — граф, в котором все вершины связаны.
Сечение графа — множество рёбер, удаление которых делит граф на два изолированных подграфа, один из которых, в частности, может быть тривиальным графом.
У
Узел — то же, что и Вершина.
Э
Эйлеров граф — это граф, в котором существует цикл, содержащий все рёбра графа по одному разу (вершины могут повторяться).

Приложенные файлы

  • docx matlog.chuhno.doc
    Чухно Ирина Сергеевна
    Размер файла: 2 MB Загрузок: 18