SEMINAR5 (Семинары)

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им М.В. ЛОМОНОСОВА

ФАКУЛЬТЕТ ВОЕННОЙ ПОДГОТОВКИ

Кафедра войск ПВО

«УТВЕРЖДАЮ»

Начальник военной кафедры Войск ПВО

полковник И. Калашников

«_____» _______________ 199___г.

Методическая разработка

для проведения занятий по разделу:

«Математические методы моделирования исследований боевых действий войск и анализа сложных систем (моделей операций)»

профиль ВУС 530700

ТЕМА: 18 Применение методов алгебры логики к решению задач обработки информации специального характера

ЗАНЯТИЕ: 3¸4

Обсуждена на заседании цикла 24

«__» __________ 1997 г.

ПРОТОКОЛ ___________________

Москва 1997 г.

Учебная и воспитательная цели:

Дать студентам понятие о возможности применения формального аппарата булевой алгебры к задачам обработки смысловой информации. Научить применять аппарат булевой алгебры и привить практические навыки в постановке, формализации и решении задач обработки смысловой информации в АСУ военного назначения.

Привить навыки изложения материала по теме у доски. Организовать методический разбор их объяснения материала личному составу.

Организационно-методические указания:

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

1. Основные формулы булевой алгебры.

2. Изображающие числа и базис.

3. Представление булевых функций в совершенной дизъюнктивной и конъюнктивной нормальной форме.

4. Восстановление булевой функции по изображающему числу.

5. Логическая зависимость и независимость булевых функций.

После опроса, на который затратить 25-30 мин., подвести итог и остановиться на тех вопросах, которые студенты усвоили плохо.

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

Далее сформулировать условия задачи обработки разведанных с помощью перестановочной матрицы. Вызвать студентов для ее решения. На это затратить время порядка 65 минут.

Рассмотреть на конкретной задаче вопросы проверки противоречивости, зависимости и избыточности высказываний. Сформулировать условия задачи и решить ее силами студентов, затратив на решение 45 минут.

Задание на самостоятельную работу.

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

Занятия 3,4. Обработка смысловой информации с использованием булевой алгебры.

Время: 4 часа.

Учебная и воспитательная цели:

Дать практику применения аппарата булевой алгебры к задачам обработки разведанных. Привить навыки в постановке, формализации и решения задач обработки смысловой информации в АСУ.

Привить навыки проведения занятий с подчиненными по теме.

Методика проведения занятия:

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

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

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

Для объяснения материала учебного вопроса № 4 целесообразно дать задание на самоподготовку.

Краткое содержание занятий 3,4.

Учебный вопрос № 1.

Общая формулировка задачи обработки смысловой информации.

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

А) Основные понятия алгебры логики.

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

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

Область алгебры логики состоит из множества высказываний.

Высказыванием называется законченное предложение, которое может иметь два значения истинности: либо быть истинным, либо быть ложным. Обозначение высказываний: .

Из простых высказываний при помощи операций:

образуются сложные высказывания или булевские функции.

Основные формулы булевой алгебры

1. правило абсорбации.

2. правило коммутативности

3. Ошибка! Ошибка внедренного объекта. ассоциативность

4. дистрибутивность

5. правило Моргана

Б) Изображающие числа и базис.

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

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

Для элементов базис содержит строк и столбцов. Так для одного элемента базисом будет

Для двух элементов базисом будет

Для трех элементов базисом будет

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

Будем считать эти числа номерами колонок базиса. Если колонки базиса упорядочены в записи в возрастающем порядке их номеров слева направо, то базис называется стандартным. Все другие базисы нестандартные.

Для элементов существует столько различных базисов, сколько можно составить перестановок из колонок.

Стандартный базис для элементов обозначается в .

Строки базиса называются изображающими числами соответствующих элементов и обозначаются знаком .

Например, найти изображающее число б.ф. в стандартном базисе в .

В) Нахождение изображающих чисел булевых функций.

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

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

Совершенная дизъюнктивная нормальная форма булевой функции является суммой элементарных произведений.

Например:

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

Например, восстановить б.ф. по изображающему числу : . Единицы стоят на местах. Для этих позиций стандартного базиса находим

.

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

К.Н.Ф. представляет собой произведение элементарных сумм:

и т.д.

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

Например, число имеет нули в и разрядах, поэтому