71835

Автоматическая мышь ищет выход из лабиринта

Курсовая

Математика и математический анализ

Переменные, которые могут принимать только два значения 0 и 1 называются логическими переменными (или просто переменными). Заметим, что логическая переменная х может подразумевать под числом 0 некоторое высказывание, которое ложно, и под числом 1 высказывание, которое истинно.

Русский

2014-11-13

262.5 KB

4 чел.

ГОУВПО «Воронежский государственный технический университет»        Факультет энергетики и систем управления                                                         Кафедра высшей математики и физико-математического моделирования

Курсовая работа

по дисциплине дискретная математика на тему:

«Автоматическая мышь ищет выход из лабиринта»

Выполнил: студент гр. АТР-131                                                                                          Аверьянов Павел

Принял: доц. Купцов В. С.

Воронеж 2013 г.

Содержание

Условие задачи…………………………………………………………………………….3

Теоретическое введение…………………………………………………………………..4

Решение.………………………………………………………………………………….10

Заключение……………………………………………………………………………….17

Список литературы………………………………………………………………………18


Условие задачи

Робот, представленный автоматической мышью, ищет выход из лабиринта.

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


Теоретическое введение

    Основные логические функции

Логической ( булевой) функцией (или просто функцией) n переменных y = f(x1x2xnназывается такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.

Переменные, которые могут принимать только два значения 0 и 1 называются логическими переменными (или просто переменными). Заметим, что логическая переменная х может подразумевать под числом 0 некоторое высказывание, которое ложно, и под числом 1 высказывание, которое истинно. Например, высказывание “Волга впадает в Каспийское море” является истинным и, значит, с точки зрения дискретной математики принимает значение 1, а высказывание “в неделе 8 дней” является ложным, и переменная, которая заменяет это высказывание, принимает значение 0. Имеется много высказываний, которые либо истинны, либо ложны, но о которых мы не знаем, что имеет место на самом деле. Например, высказывание “студент Петров (имеется в виду конкретный человек) имеет дома компьютер”. Такого рода высказывания требуют проверки (конечно, если нам важен этот факт). Поэтому считаем, что переменная, заменяющая это высказывание может принимать значение 0 или 1.

Из определения логической функции следует, что функция п переменных – это отображение Еп в Е, которое можно задать непосредственно таблицей, называемой таблицей истинности данной функции. Например, функция трех переменных f(x,y,z) может определяться следующей таблицей истинности.

 

x

y

z

f(x,y,z)

0

0

0

1

0

0

1

0

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

0

1

1

1

0

Это означает, что f(0,0,0) = 1, f(0,0,1) = 0, f(0,1,0) = 1 и т. д.

Перечислим 7 важнейших функций:

1) конъюнкция (функция И)

Заметим, что конъюнкция – это фактически обычное умножение (нулей и единиц). Иногда эту функцию обозначают x&y или xÙy;

2) дизъюнкция (функция или)

3) импликация (следование)

Иногда импликацию обозначают x É или x ® y    (читается “из следует y”).

Это очень важная функция, особенно в логике. Ее можно рассматривать следующим образом: если х = 0 (т. е. х “ложно”), то из этого факта можно вывести и “ложь”, и “истину” (и это будет правильно), если у = 1 (т. е. у“истинно”), то истина выводится и из “лжи” и из “истины”, и это тоже правильно. Только вывод “из истины ложь” является неверным. Заметим, что любая теорема всегда фактически содержит эту логическую функцию;

4) сложение по модулю 2 (здесь и далее, если не оговорено противное, знаком “+” мы будем обозначать такое сложение):

5) эквивалентность или подобие

Эта f= 1 тогда и только тогда, когда х = у. Заметим, что будем применять оба обозначения: ху (в основном при изучении функций) и х~ у (когда речь будет идти о логических операциях);

6) штрих Шеффера

Иногда эту функцию называют “не и” (так как она равна отрицанию конъюнкции);

7) стрелка Пирса (иногда эту функцию называют штрих Лукасевича)

Эта функция является отрицанием дизъюнкции и поэтому иногда ее называют “не или”.

Заметим, что свойства последних двух функций (как будет видно далее) похожи между собой и, может быть, поэтому в литературе их часто путают (т. е. называют f8 штрихом Шеффера, а f14  стрелкой Пирса).

Три оставшиеся функции, (f2 , f4 и f11) особого значения в дискретной математике не имеют.

Свойства конъюнкции, дизъюнкции и отрицания

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

Конъюнкцией n переменных f (x1, x2, …, xn) = x1 x2…xназывается функция, которая принимает значение 1, если и только если все переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0).

Дизъюнкцией n переменных f (x1x2, …, xn) = x1Ú x2Ú … Ú xn называется такая функция, которая равна 0 если и только если все переменные равны 0 (и, значит, равна 1 тогда и только тогда, когда хотя бы одна переменная равна 1).

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

Будем обозначать через  (x1x2… xn) новую функцию, которая на наборе переменных x1x2, …, xn принимает значение, противоположное f(x1x2, …, xn).

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

1. Универсальные границы:

xÚ1 = 1; xÚ0 = х; х1 = х; х0 = 0.

2. Ассоциативность конъюнкции и дизъюнкции:

x(yz) = (xy)z; x Ú (y Ú z) = (Ú y)Ú z.

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

3. Поглощение (“целое поглощает часть”):

хÚ ху = х(1Ú у) = х.

4. Два распределительных закона:

х (yÚ z) = x y Ú x zхÚ (y z) = (xÚ y)(xÚ z),

оба свойства могут быть доказаны простым рассуждением (например, если х = 0, тогда по свойству 1 справа выражение равно 0 и слева тоже 0, если х = 1, то справа стоит yÚ z и слева будет то же самое).

5. Правила де Моргана:

оба эти правила обобщаются на любое число переменных:

6. Правило Блейка:

Пусть Ки К какие-то логические функции, тогда

что легко доказывается справа налево:

Следствием правила Блейка являются два правила обобщенного поглощения:

Заметим, что правила Блейка и следствия из него часто используются для упрощения дизъюнкции (см. разд. 5)

Замечание. Конъюнкция, дизъюнкция, отрицание были определены для объектов, принимающих лишь два значения 0 и 1. Однако бывают случаи, когда можно ввести такие операции для некоторых других объектов (эти операции также называют иногда конъюнкцией, дизъюнкцией и отрицанием), для которых также выполнены свойства 1–6. В этом случае говорят, что на этих объектах введена булева алгебра.

Напримерпусть W– некоторое множество точек (или элементарных событий в теории вероятности), Â – множество подмножеств из W . Если AB принадлежат Â , то можно ввести сумму множеств (дизъюнкцию) A+B = AÚB(равную объединению точек из А и В), произведение множеств (конъюнкцию) АВ = АÙ В (равное набору точек, входящих и в А, и в B одновременно) и дополнение (отрицание А), т. е. – множество точек из W , не входящих в А. Тогда для этих операций (и это легко проверить) будут выполнены свойства 1–6. Таким образом, множество всех подмножеств из W является булевой алгеброй.

ДНФ, СДНФ, КНФ, СКНФ

Простой конъюнкцией называется конъюнкция одной или нескольких переменныхпри этом каждая переменная встречается не более одного раза (либо самалибо ее отрицание).

Например,     является простой конъюнкцией,

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций.

Например, выражение         является ДНФ.

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

Например, выражение       является ДНФ, но не СДНФ. Выражение        является СДНФ.

Аналогичные определения (с заменой конъюнкции на дизъюнкцию и наоборот) верны для КНФ и СКНФ. Приведем точные формулировки.

Простой дизъюнкцией называется дизъюнкция одной или нескольких переменныхпри этом каждая переменная входит не более одного раза (либо самалибо ее отрицание). Например, выражение        – простая дизъюнкция,

Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций ( например выражение             – КНФ).

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

Например, выражение               является СКНФ.

                                                   

                                                          Решение

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

Приоритеты поворота:

  1.  Лево
  2.  Прямо
  3.  Право
  4.  Назад

Зададим лабиринт и положение робота.

Возьмем произвольный лабиринт и поместим туда мышь.

Теперь, представляя вид лабиринта и зная положение мыши, напишем алгоритм движения робота. Мышь определяет с помощью датчиков свободные направления движения, затем делает, если нужно поворот. После чего совершает один шаг.

Алгоритм движения.

Пункт характеризует:

  •  Свободный ход по порядку приоритетности.
  •  Поворот мыши, если необходим.
  •  Движение.

Алгоритм:

Робот находится в начальной точке пути

Шаг 1:

  •  Налево – свободно
  •  Поворот 90˚
  •  Движение вперед

Шаг 2:

  •  Налево – тупик
  •  Прямо – свободно
  •  Движение вперед

Шаг 3:

  •  Налево – тупик
  •  Прямо – свободно
  •  Движение вперед

Шаг 4:

  •  Налево – тупик
  •  Прямо – свободно
  •  Движение вперед

Шаг 5:

  •  Налево – тупик
  •  Прямо – тупик
  •  Направо – свободно
  •  Поворот 90˚
  •  Движение вперед

Шаг 6:

  •  Налево – тупик
  •  Прямо – свободно
  •  Движение вперед

Шаг 7:

  •  Налево – тупик
  •  Прямо – тупик
  •  Направо – свободно
  •  Поворот 90˚
  •  Движение вперед

Шаг 8:

  •  Налево – тупик
  •  Прямо – тупик
  •  Направо – тупик
  •  Назад – свободно
  •  Поворот 180˚
  •  Движение вперед

Шаг 9:

  •  Налево – свободно
  •  Поворот 90˚
  •  Движение вперед

Шаг 10:

  •  Налево – свободно
  •  Поворот 90˚
  •  Движение вперед

Шаг 11:

  •  Налево – тупик
  •  Прямо – свободно
  •  Движение вперед

Шаг 12:

  •  Налево – свободно
  •  Поворот 90˚
  •  Движение вперед

Шаг 13:

  •  Налево – тупик
  •  Прямо – свободно
  •  Движение вперед

Шаг 14:

  •  Налево – свободно
  •  Поворот 90˚
  •  Движение вперед

Шаг 15:

  •  Налево – тупик
  •  Прямо – свободно
  •  Движение вперед

Шаг 16:

  •  Налево – тупик
  •  Прямо – тупик
  •  Направо – свободно
  •  Поворот на 90˚
  •  Движение вперед

Шаг 17:

  •  Налево – свободно
  •  Поворот 90˚
  •  Движение вперед

Выход! Робот выехал за пределы лабиринта.

Изобразим движение мыши в лабиринте:

Зададим переменные соответствующие сигналу принимаемому датчиком:

  •  Лево – свободно = X1
  •  Прямо – свободно = X2
  •  Право – свободно = X3
  •  Назад – свободно = X4

Теперь зададим переменные соответствующие направлению движения:

  •  Лево = A
  •  Прямо = B
  •  Право = C
  •  Назад = D

Составим таблицы истинности.

Приоритетность сигнала датчика:                  Движение в зависимости от сигнала:

                                                                

На основе данных в таблицах, составим функции управления движением:

A = X1˅(XX̅2)˅(XX̅3)˅(XX̅4) = X1

B = X2˅(XX̅3)˅(XX̅4) = X2

C = X3˅(XX̅4) = X3

D = X4
                                                          
Заключение

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

«Дискретная математика»  Ф.А. Новиков

«Дискретная математика и комбинаторика»  Джеймс А. Андерсон

«Дискретная математика в примерах и задачах» В.В. Тишин

PAGE   \* MERGEFORMAT16


 

А также другие работы, которые могут Вас заинтересовать

21236. ЗАЩИТА ГЕНЕРАТОРОВ 139 KB
  Защита должна действовать на отключение. Ток до 5 А считается безопасным и защита должна действовать на сигнал при токах более 5 А на отключение. Защита должна действовать на отключение.
21237. ЗАЩИТА ТРАНСФОРМАТОРОВ И АВТОТРАНСФОРМАТОРОВ 451.5 KB
  2 Межвитковые замыкания в одной фазе защита должна действовать на отключение. 3 Замыкания на землю защита действует на отключение или на сигнал. Ненормальные режимы: 1 Протекания сверхтоков при внешнем КЗ защита должна действовать на селективное отключение.
21238. ЗАЩИТА ВЫСОКОВОЛЬТНЫХ ЭЛЕКТРОДВИГАТЕЛЕЙ 155 KB
  Междуфазные КЗ сопровождаются сверхтоками поэтому защита должна действовать на отключение. Используется токовая защита до 5 МВт свыше 5 МВТ продольная дифференциальная защита. 2 Замыкания на землю сопровождаются малым током однако во избежание разрушения стали двигателя устанавливается защита на отключение. 3 Витковые замыкания сопровождаются сверхтоками однако особая защита не устанавливается вследствие дороговизны так как если витковые замыкания развиваются то переходят в междуфазные КЗ или КЗ на землю и отключаются...
21239. УСТРОЙСТВА АВТОМАТИЧЕСКОГО УПРАВЛЕНИЯ 344 KB
  АВТОМАТИЧЕСКОЕ ПОВТОРНОЕ ВКЛЮЧЕНИЕ АПВ. называется устройством автоматического повторного включения или сокращённо АПВ. Далее АПВ рассматривается для линии электропередачи. Если после повторного включения линия остается в работе то говорят что цикл АПВ был успешным если отключается вновь то цикл АПВ был неуспешным.
21240. АВТОМАТИЧЕСКОЕ ВКЛЮЧЕНИЕ РЕЗЕРВА 170 KB
  Чтобы повысить надёжность электроснабжения нагрузок питающихся по разомкнутым схемам применяют нормально отключенные резервные источники питания которые включаются вручную или устройствами АВР в случае потери рабочего источника. Успешность АВР составляет 90  95 . Поэтому устройства АВР служат мощным средством повышения надёжности электроснабжения. Выбор параметра пуска схемы АВР Схема автоматического включения резерва должна производить включение резервного элемента при вполне определенных условиях.
21241. УСТРОЙСТВА АВТОМАТИЧЕСКОГО РЕГУЛИРОВАНИЯ 177.5 KB
  При регулировании по возмущению регулирующее воздействие не зависит от величины возмущения и определяется лишь самим событием появления возмущения.1 ХАРАКТЕРИСТИКИ РЕГУЛИРОВАНИЯ Статическая характеристика зависимость регулируемой величины от возмущающего воздействия в установившемся режиме. Данная характеристика обеспечивает постоянство регулируемой величины.
21242. ОСНОВНЫЕ ВИДЫ ПРОТИВОАВАРИЙНОЙ АВТОМАТИКИ В ЭЭС 46 KB
  3 АЧР автоматическая частотная разгрузка. Лист 2 АВТОМАТИКА ЧАСТОТНОЙ РАЗГРУЗКИ АЧР Снижение частоты в энергосистеме всего на несколько герц может привести к полному расстройству работы ЭЭС. ТРЕБОВАНИЯ К АЧР 1 Отключаемая мощность должна быть достаточной для ликвидации наибольшего из возможных дефицитов мощности. 2 АЧР должна полностью исключать возможность появления лавин частоты то есть должна быть исключена возможность понижения частоты ниже порога 45 Гц.
21243. РЕЛЕЙНАЯ ЗАЩИТА И АВТОМАТИКА. ЧАСТЬ 1 (РЕЛЕЙНАЯ ЗАЩИТА И АВТОМАТИКА РАСПРЕДЕЛИТЕЛЬНЫХ СЕТЕЙ) 249.5 KB
  ЧАСТЬ 1 РЕЛЕЙНАЯ ЗАЩИТА И АВТОМАТИКА РАСПРЕДЕЛИТЕЛЬНЫХ СЕТЕЙ Книги: Чернобровов Н. Релейная защита. Расчёт релейной защиты и автоматики распределительных сетей. Первую задачу решают устройства релейной защиты РЗ и резервирования отказов выключателя УРОВ.