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


 

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

1680. Гидравлические вяжущие вещества. Гидравлическая известь. Портландцемент 943.53 KB
  Гидравлическая известь. Сырье, особенности и применение. Портландцемент. Начальная характеристика. Плавление сырьевой смеси. Схема производства цемента сухим способом. Химический и минеральный состав клинкера.
1681. Специальные виды цементов 44.64 KB
  Быстротвердеющий портландцемент (БТЦ). Сверхбыстротвердеющий портландцемент (СБТЦ). Пластифицированный портландцемент. Белый и цветные цементы. Глиноземистый цемент. Расширяющийся портландцемент (РПЦ).
1682. Экономика организаций. Хозяйственная деятельность предприяний 700.66 KB
  Анализ хозяйственной деятельности предприятия. Организационно-правовые формы предприятия и их характеристика. Формы общественной организации производства. Основные производственные фонды. Регулирование заработной платы.
1683. Современные информационные технологии 1.73 MB
  Информация и ее роль в человеческом обществе. Формы адекватности и объем информации. Специальные виды кодирования и криптография. Итология – наука об информационных технологиях. Информационная технология поддержки принятий решений. Современный рынок финансово-экономического прикладного программного обеспечения. Основные программные и аппаратные компоненты сети.
1684. Стандартизация свойств. Физические, механические, физико-химические свойства СМ. Долговечность и надежность 915.29 KB
  Механические свойства. Пластические деформации. Модуль упругости (модуль Юнга). Свойство материала сопротивляться разрушению от действия внутренних напряжений и деформаций. Ударная вязкость. Характеристика размеров твердых частиц и капель жидкости. Свойства пластично-вязкого тела (реологические свойства). Долговечность и надежность.
1685. Управління персоналом організації 1.17 MB
  Роль персоналу в підвищенні ефективності та конкурентоспроможності організації. Групи методів управління персоналом, їх відміність і взаємозв’язок. Характеристика двох підходів до поняття персонал: персонал-витрати і персонал- ресурс. Взаємозв’язок стратегії розвитку організації, стратегії управління персоналом та кадрової політики. Роль сучасних служб персоналу в організації, основні завдання і напрями їх роботи.
1686. Организация учета расчетных операций 58.44 KB
  Организация учета расчетных операций. Учет расчетных отношений с дебиторами и кредиторами. Учет командировочных расходов, связанных с зарубежными поездками. Учет командировочных расчетов.
1687. Расчет усилителя видеоконтрольного устройства 154.88 KB
  Структурная схема усилителя видеоконтрольного устройства. Составление и расчет принципиальной электрической схемы. Расчет каскада с операционным усилителем.
1688. История русского языка. Отличия раннедревнерусской системы от южнославянской 48.71 KB
  Основные отличия раннедревнерусской языковой системы от южнославянской системы, отраженной в старославянских памятниках письменности. История носовых гласных: их возникновение в праславянском языке; звуковое качество в восточнославянской диалектной зоне; время и результаты их утраты. Хронология процесса падения редуцированных в истории русского языка. Диссимиляция и упрощение групп согласных как следствие падения редуцированных.