Установите соответствие (название - обозначение)

А) Эквивалентность

Б) Инверсия

В) Неравнозначность

Г) Импликация

Д) Отрицание импликации

1)

2) Å

3) «

4) ®

5)

 

Установите соответствие (название - обозначение)

А) Конъюнктивная нормальная форма

Б) Дизъюнктивная нормальная форма

В) Произвольная форма

Г) Совершенная дизъюнктивная нормальная форма

Д) Совершенная конъюнктивная нормальная форма

1) (x₁ & x₃) Ú (x₁ & ) Ú (  & x₃)

2) (x₁ Ú x₂) & (x₁ Ú ) & (  Ú x₂)

3) (x₁ & x₂) Ú (x₁ & ) Ú (  & x₂)

4) (x₁ Ú x₃) & (x₁ Ú ) & (  Ú x₃)

5)

 

КРИТЕРИИ ОЦЕНКИ

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

85 – 100% правильных ответов – оценка «отлично»;

70 – 85% правильных ответов – оценка «хорошо»;

55 – 70% правильных ответов – оценка «удовлетворительно»;

менее 55% правильных ответов – оценка «неудовлетворительно».

 

ГЛОССАРИЙ к МОДУЛЮ 3

Булева алгебра образуется из множества всех БФ вместе с операциями отрицания, конъюнкции и дизъюнкции.

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

Высказывание - это любое утверждение, в отношении которого можно сказать, что оно либо истинно, либо ложно.

Дизъюнктивной нормальной формой БФ называется функция, представляющая собой дизъюнкцию конечного числа конъюнкций, каждая из которых содержит простые переменные в прямой или инверсной форме; но не более одного раза для каждой конъюнкции.

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

Конъюнктивная нормальная форма БФ - конъюнкция некоторого числа дизъюнкций, содержащих не повторяющиеся в рамках каждой конъюнкции переменные в прямой или инверсной форме.

Логические функции (ЛФ) – это составные логические высказывания на основе логических переменных.

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

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

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

Минимальная форма БФ – это форма, которая не допускает никаких сокращений.

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

Минимальным покрытием называется покрытие, соответствующее минимальной форме.

Минитерм – это конституента единицы.

Минитерм (n-1)го ранга j_n-1 — это результат склеивания двух минитермов n-го ранга т.е. j_n-1 = j_n-1x_i+j_n-1Øx_i.

Операция обобщенного склеивания: ac Ú b  = ac Ú b  Ú ab.

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

Простые импликанты – это минитермы сокращенной ДНФ.

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

Совершенной конъюнктивной нормальной формой БФ(СКНФ) называется логическая функция, представленная в конъюнктивной нормальной форме, при условии, что каждая составляющая ее элементарная дизъюнкция содержит все возможные переменные в прямой или инверсной форме.

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

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

Стрелка Пирса - приводится к виду  и называется операцией ИЛИ - НЕ.

Теорема о функциональной полноте - для того, чтобы БФ была полной, необходимо и достаточно, чтобы она включала хотя бы одну функцию: несохраняющую константу 0, несохраняющую константу 1, несамодвойственную, немонотонную.

Штрих Шеффера - можно привести к виду  и называется операцией И - НЕ.

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

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

У. Джеймс

МОДУЛЬ 4. ОСНОВЫ Теории ГРАФОв                 (2 кредита)

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

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

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

1) знание основных понятий теории графов;

2) умение оценивать и определять временную сложность алгоритмов решения задач на графах;

3) знание основных определений и понятий теории графов;

4) умение составлять формализованное описание и математическую постановку основных задач на графах;

5) знание основных тождеств, теорем и законов теории графов;

6) практические навыки использования основных графовых алгоритмов для решения различных оптимизационных задач.

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

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

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

М. Клайн

Глава 15. введение в теорию графов

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

Цели

Освоив эту главу, студенты должны:

· знать способы задания графов;

· уметь выполнять операции над графами;

· уметь строить матрицы инцидентности, смежности и списки, а также переходить от одной формы представления графа к другой;

· уметь строить платоновы графы;

· определять для любого вида графа его двойственный;

· знать определение нечеткого графа и различать нечеткие неориентированные графы первого и второго рода;

· строить подграфы и суграфы на смешанном графе, мультиграфе;

· определять маршруты, цепи, циклы в произвольном графе;

· определять компоненты связности графа;

· выполнять разбиение графа;

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

· определять кратчайшие пути в графе на основе алгоритмов Дейкстры и Форда.