Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
KP ATP-131 / Курсовая работа. Иванов А.В..doc
Скачиваний:
30
Добавлен:
31.05.2015
Размер:
336.9 Кб
Скачать

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

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

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

«Упрощенная схема управления лифтом»

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

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

Воронеж 2013 г.

Содержание

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

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

Практическая часть.………………………………………………………………………7

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

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

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

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

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

Булева алгебра

Булева алгебра — раздел математики, изучающий логические выражения и операции. Логические выражения представляют собой высказывания — некоторые утверждения, которым всегда можно сопоставить одно из двух логических значений: ложь или истина (их можно обозначать как 0 и 1, F и T, false и true).

Для сравнения, элементарная алгебра занимается арифметическими выражениями и операциями.

Булева алгебра получила свое название в честь своего создателя Джорджа Буля (1854 г.), являющегося одним из предтеч математической логики.

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

Высказывания

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

Москва — столица России.

5>3.

2+3=6.

Первое и второе выказывания истинны, третье — ложно. В логических выражениях высказывания, как правило, обозначаются заглавными латинскими буквами: A, B, C…

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

Логические операции

Логические операции булевой алгебры подобны арифметическим операциям элементарной алгебры. Если последние применяются к числам, то первые — к логическим значениям соответствующих высказываний. Составные высказывания можно получать с помощью логических операций так же, как в элементарной алгебре — формулы. И, если известны значения исходных высказываний, значение составного высказывания можно вычислить, прибегая лишь к формальным правилам. Уравнения, составленные в алгебре логики можно формально решать. Все это обеспечивает широкие возможности по применению математического аппарата к суждениям из реальной жизни (там, где не хватает аппарата булевой алгебры, применяются более сложные методы математической логики, в частности, исчисление предикатов первого порядка и др.).

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

Основные логические операции

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

Отрицание НЕ

Отрицание — операция, применяемая к одному операнду, т.е. унарная операция. Выражение не A записывается как ¬A, A¯¯¯ или !A. Операции отрицания задается следующей таблицей истинности:

A

¬A

0

1

1

0

Соответственно, операции отрицания можно дать следующее истолкование: истинность выражения, построенного с помощью отрицания, противоположна истинности исходного выражения. Если A истинно, ¬A ложно, и наоборот.

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

Логическое И

Логическое И (конъюнкция) — операция, применяемая к двум операндам, т.е. бинарная операция. Выражение A и B записывается как A∧B, A⋅B или A&&B. Конъюнкция задается следующей таблицей истинности:

A

B

A∧B

0

0

0

0

1

0

1

0

0

1

1

1

Логическое И, как не сложно понять из названия, образует выражение, которое истинно только тогда, когда истинны оба исходных выражения, входящих в его соста: и первое, ивторое.

Операция конъюнкции подобна умножению. Это легко заметить по таблицы истинности. Конъюнкция дает такой же результат, как если бы мы просто перемножали ее операнды.

Логическое ИЛИ

Логическое ИЛИ (дизъюнкция) — еще одна бинарная операция. Выражение A или B записывается как A∨B, A+B или A||B. Дизъюнкция задается следующей таблицей истинности:

A

B

A∨B

0

0

0

0

1

1

1

0

1

1

1

1

Логическое ИЛИ образует выражение, которое истинно тогда, когда истинно хотя бы одно исходных выражение, входящее в его состав: или первое, или второе.

Операция дизъюнкции подобна сложению. Как и в случае с конъюнкцией, это можно заметить по таблице истинности. Единственным исключением тут является правило 1+1=1, а не 2, как можно было бы ожидать. Но это нормальное явление, учитывая, что пространство логических значений ограничено нулем и единицей.

Производные логические операции

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

Исключающее ИЛИ

Операция исключающего ИЛИ похожа на обычную дизъюнкцию. Ее обозначают как A⊕B или A^B. Операция задается следующей таблицей истинности:

A

B

A⊕B

0

0

0

0

1

1

1

0

1

1

1

0

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

Высказывание вида A⊕B в логическом выражении можно заменить на A∧¬B∨B∧¬A.

Операция импликации

Бинарная операция импликации выражается связками если… , то, из … следует, влечет. Операция записывается как A→B или A⇒B и задается следующей таблицей истинности:

A

B

A→B

0

0

1

0

1

1

1

0

0

1

1

1

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

Высказывание вида A→B в логическом выражении можно заменить на ¬A∨B, при этом оно останется тождественно исходному, то есть будет истинно или ложно ровно в тех же самых случаях, что и оригинальное.

Операция эквивалентности

Данная операция выражается связками тогда и только тогда, необходимо и достаточно, равносильно. Операция имеет следующие обозначения: A≡B, A⇔B, A==B. Таблица истинности выглядит так:

A

B

A≡B

0

0

1

0

1

0

1

0

0

1

1

1

Выражение, образованное эквивалентностью, истинно, если истинность обоих операндов совпадает.

Эквивалентность можно заменить на две импликации, а те, в свою очередь, раскрыть по правилам, указанным выше. Получится, что высказывание вида A≡B можно заменить на A∧B∨¬A∧¬B.

Приоритеты операций

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

Приоритеты логических операций

Отрицание

Конъюнкция

Дизъюнкция, исключающее ИЛИ

Импликация, эквивалентность

Законы булевой алгебры

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

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

Ассоциативность

Ассоциативность конъюнкции и дизъюнкции выражается следующими формулами:

(A∧B)∧C=A∧(B∧C)=A∧B∧C,

(A∨B)∨C=A∨(B∨C)=A∨B∨C.

На практике это означает, что можно опускать те скобки, которые определяют, в каком порядке должна выполняться конъюнкция в выражениях вида A1∧A2∧⋯∧An и дизъюнкция в выражениях вида A1∨A2∨⋯∨An.

Коммутативность

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

Конъюнкция и дизъюнкция являются коммутативными операциями:

A∧B=B∧A,

A∨B=B∨A.

Дистрибутивность

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

A∧(B∨C)=A∧B∨A∧C,

A∨B∧C=(A∨B)∧(A∨C).

Свойства единицы и нуля

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

A∧0=0,A∧1=A,

A∨0=A,A∨1=1.

Идемпотентность

Операция называется идемнотентной, если, применяя ее к двум равным операндам, получается тот же самый операнд. Идемпотентность позволяет «выкидывать» лишние повторные применения операции из формулы. Конъюнкция и дизъюнкция идемпотентны:

A∧A=A,

A∨A=A.

Поглощение

Если к выражению применяется с одним и тем же операндом сначала одна операция, а потом, с тем же самым операндом, поглощающая ее, то значение выражения поглощается, становясь равно операнду. Таким образом поглощающие друг друга пары операций можно «выкидывать» во время упрощения. Конъюнкция и дизъюнкция поглощают друг друга:

A∧B∨B=B,

(A∨B)∧B=B.

Законы де Моргана

Законы де Моргана позволяют применять отрицания к целой скобке, позволяя перейти к так называемым тесным отрицаниям, когда ни одно отрицание не стоит перед скобкой.

¬(A∧B)=¬A∨¬B,

¬(A∨B)=¬A∧¬B.

Дополнение

Отрицание операнда называется его дополнением. Конъюнкция или дизъюнкция операнда со своим дополнением дает однозначные результат независимо от значения операнда:

A∧¬A=0,

A∨¬A=1.

Двойное отрицание

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

¬¬A=A.

Булевы функции

Определение. Переменная x называется булевой, если она способна принимать только два значения 0 и 1. В качестве примера интерпретации такого рода переменных может выступать обычный настенный выключатель света на два положения. Здесь 1 соответствует положению переключателя вверх и 0 — положению вниз. Определение. Функция f(x1,x2,…,xn) называется булевой (или логической, или функцией алгебры логики, или переключательной), если все ее аргументы x[i] являются булевыми, а сама функция также может принимать только два значения 0 и 1. Множество всех булевых функций от переменных x1,x2,…,xn обозначают через P2.

Способы задания булевых функций

Способы задания булевых функций не отличаются от способов задания обычных функций анализа. К таковым способам задания стандартно относятся: 1) табличный; 2) графический; 3) аналитический.

(1) Табличный способ задания

Пусть w=f(x1,x2,…,xn) — булева функция n аргументов. Область определения данной функции можно рассматривать и как множество упорядоченных наборов (или векторов, или двоичных наборов) D={x1,x2,…,xn | xi ∈ {0,1}, i=1,2,…,n}, на каждом из которых функция принимает одно из двух значений: w ∈ {0,1}. Количество таких наборов (x1,x2,…,xn), согласно правилу прямого произведения, равно |D|=

В качестве примера рассмотрим табличное представление булевой функции трех аргументов w=f(x,y,z), где w,x,y,z  ∈ {0,1}. Область определения функции — это множество двоичных наборов D={(x,y,z), |  x,y,z ∈ {0,1}}. Их число есть |D|=2^3=8, а количество таких функций равно 2^|D|=2^2^3=256. Значения функции f(x,y,z) удобно представить в виде табл. 1.3, где перечислены всевозможные наборы из нулей и единиц длины 3 и для каждогонабора указано значение функции fi ∈ {0,1} на этом наборе.

В таблицах, аналогичных табл. 1.3 обычно употребляется расположение наборов, соответствующих порядку естественного роста двоичных чисел 0,1,…2^n-1, в примере n=3. Определение. Таблицы значений булевых функций, подобные табл. 1.3, называются таблицами истинности булевых функций. Название таблиц происходит от интерпретации значений 1 — истина (TRUE), 0 — ложь (FALSE).

(2) Графический способ задания

Рассмотрим графическое представление булевой функции трех аргументов w=f(x,y,z), заданной таблично (табл. 1.3). Заметим, что множество наборов области определения функции D={(x,y,z) , | x,y,z ∈ {0,1}} является множеством координат точек вершин единичного трехмерного куба (рис. 1.2). Очевидный способ графического представления булевой функции — это отметить каким-то образом вершины куба, в которых функция принимает значение 1. Именно так на рис. 1.2 и сделано. В соответствии с таблицей значений (табл. 1.3) отмечены вершины, в которых булева функция равна 1.

Замечание. Очевидно, что область определения булевой функции n аргументов w=f(x1,x2,…,xn) составляется из наборов координат точек вершин единичного n-мерного куба.

(3) Аналитический способ задания

Приведем таблицы истинности, обозначения и названия булевых функций одного и двух аргументов. В табл. 1.4 представлены все (их 2^2^1=4) функции одного аргумента, в табл. 1.5 — все функции двух аргументов (их 2^2^2=16).

Таблица 1.4

x

0 1

Обозначение

Название

0

0 0

0

Нуль, const 0

1

0 1

x

Повторение x

2

1 0

¬x, x

Отрицание x, не x

3

1 1

1

Единица, const 1

Функции 0 и 1 называются соответственно тождественным нулем и тождественной единицей. Иногда эти функции 0 и 1 рассматривают как функции, зависящие от пустого множества переменных.

Таблица 1.5

x у

0 0 1 1 0 1 0 1

Обозначение

Название

0

0 0 0 0

0

Нуль, const 0

1

0 0 0 1

x•y,x∧y,x&y

Конъюнкция

2

0 0 1 0

yx,x•y

Запрет по x

3

0 0 1 1

x

Повторение x

4

0 1 0 0

x, x•y

Запрет по y

5

0 1 0 1

y

Повторение y

6

0 1 1 0

x⊕y

Сумма по модулю 2

7

0 1 1 1

x∨y

Дизъюнкция

8

1 0 0 0

x↓y

Стрелка Пирса

9

1 0 0 1

x~y

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

10

1 0 1 0

¬y, y

Отрицание y

11

1 0 1 1

y→x, y⇒x, y⊃x

Импликация от y к x

12

1 1 0 0

¬x, x

Отрицание x

13

1 1 0 1

x→y, x⇒y, x⊃y

Импликация от x к y

14

1 1 1 0

x|y

Штрих Шеффера

15

1 1 1 1

1

Единица, const 1

Функции одного и двух аргументов, представленные в таблицах 1.4 и 1.5, называются элементарными.

Символы ¬, |, ↓, ∧, , ∨, →, ⊕, ~, участвующие в обозначениях элементарных функций, называются логическими связками (операциями) или функциональными символами.