71835

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

Курсовая

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

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

Русский

2014-11-13

262.5 KB

3 чел.

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

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

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

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

Выполнил: студент гр. АТР-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


 

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

66950. Букварю 436 років 167 KB
  Діти повинні відгадати назви цих казок користуючись допомогою залу і викласти аркуші за кольорами веселки від червоного до фіолетового Діти: А де ж вона Тут лиш шматочки Казкар: У цьому дітки й заморочка Пісня 3. Діти відгадують назви казок та викладають стежку...
66951. Чари кохання (літературний вечір за інтимною лірикою Т.Шевченка, Лесі Українки, І.Франка, Л.Костенко, В.Симоненка) 52.5 KB
  Мета: - поширити знання учнів про інтимну лірику, розкрити світ почуттів і пристрастей, створений поетичним словом великих майстрів; - розвивати творчі здібності учнів; - виховувати інтерес до поетичної творчості письменників; чистоту й благородство почуттів.
66952. Чарівний світ недосяжних романтичних мрій 61 KB
  Мета проекту Дослідити яскраве явище культури романтизм та визначити причини його виникнення. Ідея проекту Представники романтичного стилю XIX ст. Завдання проекту: Досліджувати мистецькі твори романтичного напрямку; Знайти видові романтичні паралелізмі в мистецтві...
66953. «Чашка, повна благодаті» Напої здоров’я. Чай 82 KB
  Мета: розширення кругозору учнів про чай як про напій здоров’я, що є складовою частиною культури харчування, познайомити з цілющими властивостями чаю, географією чаю, секретами заварювання, утвердження здорового способу життя.
66954. Мій рідний край - Донбас 66 KB
  Мета: Формувати в учнів інтерес до навчання; засвоїти слова за темою; вчити розповідати про символи Української держави та їх значення; розвивати прагнення бути свідомим громадянином України, її патріотом. Розвивати пізнавальні інтереси.
66956. Правила дорожного движения 282.5 KB
  Цель: научить детей ориентироваться по дорожным знакам, соблюдать правила дорожного движения. Воспитывать умение быть вежливыми, внимательными друг к другу на дороге. Ход мероприятия: 1 Ведущий. Взошло ласковое теплое солнышко, запели звонкие песни птицы и огласили начало нового дня.
66957. Привитие интереса к учебе, развитие гуманитарных представлений на уроке 162 KB
  Первое направление предусматривает организацию учебно-воспитательного процесса в соответствии с условиями способствующими всестороннему развитию ребенка получению им высокого уровня знаний при сохранении его здоровья на уроках применение здоровьесберегающих технологий привлечение...
66958. ЕКОЛОГІЧНА КАТАСТРОФА В УКРАЇНІ. ДЗВОНИ ЧОРНОБИЛЯ НАМ НАГАДУЮТЬ… 81 KB
  Мета проекту. Розширити знання дітей про трагедію віку – вибух на Чорнобильській АЕС, наголосити про потенційну небезпеку радіації для усього живого, розповісти про ліквідаторів аварії на Чорнобильській АЕС, показати, що чужої біди немає. Вчити застосовувати у повсякденному житті елементарні радіаційно-гігієнічні навички.