Алгебра логики. История возникновения. Основные положения
Федеральное агентство по образованию Российской Федерации
Государственное образовательное учреждение высшего профессионального образования
«Южно-Уральский государственный университет»
Факультет «Механико-технологический»
Кафедра «Автоматизация механосборочного процесса»
Алгебра
логики. История возникновения. Основные
положения.
РЕФЕРАТ
по дисциплине «Информатика»
Проверил,
(доцент)
_______________ Абросимов Е.Н.
_______________ 20__ г.
Автор
работы
студент группы МТ-177
_______________ Безменов К.Э.
_______________ 20__ г.
Реферат защищен
с оценкой (прописью, цифрой)
_____________________
_______________ 20__ г.
Аннотация
Безменов К.Э., Алгебра логики. История возникновения. Основные положения., Челябинск: ЮУрГУ, МТ-177, 2012, 20 с, 4 рис., 4 табл., библиографический список – 5 наим.
Цель реферата – выяснить суть алгебры логики, основных методов работы с логическими операторами, роль логики в вычислительной технике и информатике. Для выполнения этой работы потребовалось найти методические материалы по теме, решить некоторые опытные задачи и сделать выводы. Предмет исследования - операции над логическими функциями.
Оглавление
Введение
Понятие логики как науки появилось ещё в XIX в., т.е. задолго до появления науки информатики и компьютеров. Элементы математической логики можно найти уже в работах древнегреческих философов. В XVII в. Г. В. Лейбниц высказал идею о том, что рассуждения могут быть сведены к механическому выполнению определенных действий по установленным правилам. Однако как самостоятельный раздел математики логика начала формироваться только с середины XIX в..
Для того чтобы рассуждать, человеку необходим какой-либо язык. Не удивительно, что математическая логика начиналась с анализа того, как говорят и пишут люди на естественных языках. Этот анализ привёл к тому, что выяснилось существование формулировок, которые невозможно разделить на истинные и ложные, но, тем не менее, выглядят осмысленным образом. Это приводило к возникновению парадоксов, в том числе в одной из фундаментальных наук математики. Тогда было решено создать искусственные формальные языки, лишённого «вольностей» языка естественного.
ВОЗНИКНОВЕНИЕ ЛОГИКИ
Понятие логики как науки появилось ещё в XIX в., т.е. задолго до появления науки информатики и компьютеров. Элементы математической логики можно найти уже в работах древнегреческих философов. В XVII в. Г. В. Лейбниц высказал идею о том, что рассуждения могут быть сведены к механическому выполнению определенных действий по установленным правилам. Однако как самостоятельный раздел математики логика начала формироваться только с середины XIX в..
Для того чтобы рассуждать, человеку необходим какой-либо язык. Не удивительно, что математическая логика начиналась с анализа того, как говорят и пишут люди на естественных языках. Этот анализ привёл к тому, что выяснилось существование формулировок, которые невозможно разделить на истинные и ложные, но, тем не менее, выглядят осмысленным образом. Это приводило к возникновению парадоксов, в том числе в одной из фундаментальных наук математики. Тогда было решено создать искусственные формальные языки, лишённого «вольностей» языка естественного.
БУЛЕВЫ ФУНКЦИИ
Пусть имеется некоторый набор высказываний, о которых можно говорить определённо, что они истинные или ложные. Обозначим их латинскими буквами A, B, C, D … .
Если у нас есть два простых предложения, то из них образовать новое, сложносочинённое предложение с помощью союзов «или» либо «и». В математической логике для этой цели используются специальные символы:
- знак дизъюнкции v
- знак конъюнкции & (иногда используется ^)
Таким образом, из утверждений A, B с помощью знаков дизъюнкции и конъюнкции получим новые утверждения:
- A v B («A или B»)
- A & B («A и B»)
Утверждение A v B считается истинным тогда и только тогда, когда истинно хотя бы одно из исходных утверждений; утверждение A & B – когда истинны оба утверждения.
Дизъюнкцию и конъюнкцию можно рассматривать как особые операции, определённые не на числах, а на логических значениях ИСТИНА и ЛОЖЬ. Для этих операций существуют таблицы, подобные таблице умножения. (табл. 1, 2)
A |
B |
A v B |
ИСТИНА ИСТИНА ЛОЖЬ ЛОЖЬ |
ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ |
ИСТИНА ИСТИНА ИСТИНА ЛОЖЬ |
Таблица 2
A |
B |
A & B |
ИСТИНА ИСТИНА ЛОЖЬ ЛОЖЬ |
ИСТИНА ЛОЖЬ ИСТИНА ЛОЖЬ |
ИСТИНА ЛОЖЬ ЛОЖЬ ЛОЖЬ |
Логические значения ИСТИНА и ЛОЖЬ называют также булевыми значениями – в честь английского математика Джорджа Буля, который в XIX в. заложил основы современной математической логики. Функции с булевыми аргументами называют булевыми функциями. Всего булевых функций от 2 переменных – 16. Для всех булевых функций от двух переменных имеются соответствующие конструкции на русском языке. В информатике в основном используются следующие булевы функции:
- логическое ИЛИ (дизъюнкция)
- логическое И (конъюнкция)
-
логическое отрицание («НЕ», обозначается
~ и противоположно своему
- исключающее ИЛИ
Из этих основных складываются комбинированные функции: ИЛИ-НЕ, И-НЕ. Именно они получили наибольшее распространение в логической электронике, в компьютерах.
СПОСОБЫ ЗАДАНИЯ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ
Логической функцией называется зависимость поведения выходных логических величин от изменения входных логических величин. Задачей алгебры логики является поиск математического или функционального представления логических функций с целью ее непосредственного использования для управления объектом или процессом. Имеются различные способы представления логических взаимодействий.
Табличный способ. При этом способе функция задается в виде таблицы истинности, представляющей собой совокупность всех комбинацийвходных переменных (левые столбцы) и соответствующих им значений функции (правый столбец).
Таблица истинности содержит 2n строк, n+m столбцов (количество входов n+количество выходов m).
Например: пусть требуется задать функцию двух переменных, т.е. дискретное устройство на два входа и на один выход, следовательно, число столбцов = 2+1, а число строк = 4. (табл. 3)
Таблица 3
x |
y |
A |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
Таблицы истинности возможно составить по условиям задания. Задание на управление для выше приведенного примера может выглядеть следующим образом: лампа А горит только тогда, когда одновременно нажаты обе кнопки x и y.
Таблицы истинности позволяют автоматизировать поиск искомой логической функции в математическом виде.
Словесно-аналитический способ задания функции алгебры логики. При этом способе функция задается в виде аналитического выражения.В левой части высказывания указывается действие управляемого привода (или исполнительного устройства), а в правой части- условие, при котором выполняется это действие.
Аналитическое выражение задается в возможно более краткой форме. Некоторые подразумеваемые слова могут опускаться, например, такие как «кнопка», «нажать», «активен» и другие. Название датчиков и кнопок возможно заменять их схемным обозначением. При этом указание на датчик означает то, что этот датчик изменил свое состояние на активное (логическая 1). Ударение делается на союзы предложения, которые, в большинстве случаев, указывают на логическое действие.
Графические способы. Для графического описания логических взаимодействий можно использовать разные способы, предлагаемые стандартом IEC 848: шаговая, временная диаграмма, логические функциональные схемы, функциональный план.
При взаимодействии нескольких приводов наиболее наглядным средством установления логических взаимосвязей является шаговая диаграмма. (рис. 1)
Рисунок 1
В шаговой диаграмме различают линии состояния или положения привода (в данном случае это линия, описывающая перемещение цилиндра) и линии управляющих сигналов. Отличием от временной диаграммы является то, вместо временной оси здесь использованы шаги- условные временные отрезки. Длина шага не пропорциональна реальному времени, а связанна с одним действием управляемого объекта. Сигналы взаимодействуют друг с другом (сливание потоков информации) по определенному логическому закону. Каждое логическое действие имеет собственное обозначение. Достоинством шаговой диаграммы является наглядность связей взаимодействия приводов и сигналов управления между собой во времени.
Рисунок 2
Временные диаграммы важны для изображения динамически изменяющихся процессов. Горизонтальная ось является временной. Временные диаграммы удобны для изображения динамических процессов, которые быстро изменяются во времени. Они позволяют визуально анализировать реакцию выходных величин на изменение входных. (рис. 2)
Из диаграммы следует, что лампа Н1 «горит» тогда, когда нажата кнопка S1 и не нажата кнопка S2.
Лампа Н2 «горит» тогда, когда нажата кнопка S2 и не нажата кнопка S1.
Логические функциональные блок-схемы состоят из логически связанных между собой отдельных функциональных блоков, которые являются обозначениями элементарных логических функций. (рис. 3)
Рисунок 3
Логические функциональные блок-схемы обладают всеми достоинствами графического изображения- это наглядность связей логических функциональных блоков. Недостатком данных схем является сложность прослеживания изменения сигналов во времени. Логические функциональные блок-схемы являются одним из самых распространенных языков программирования в промышленности. Напомним, что целью алгебры логики является получение математического или функционального изображения функции.
Функциональный план является графическим средством отображения по-шагового управления процессом. Весь процесс управления разбит на отдельные шаги (минимальные части процесса управления), которые осуществляются при выполнении определенных условий. Функциональный план является языком программирования. (рис. 4)
Рисунок 4
Математическое представление алгебры логики. Элементарные логические действия можно представить с помощью специальных или арифметических символов (AND:Ù, · ;OR: Ú, +; NO:a`), обозначающих логические действия. Используя законы алгебры логики, возможны преобразования математических выражений логических функций.
Представление логического взаимодействия в электротехнике. Логические взаимодействия сигналов возможно реализовать через определенное соединение контактов. Существует язык программирования, который использует логические свойства соединения контактов.
ПРЕОБРАЗОВАНИЕ ВЫРАЖЕНИЙ, СОСТОЯЩИХ ИЗ БУЛЕВЫХ ФУНКЦИЙ
В математической логике преобразование выше указанных выражений проводится для различных целей – от упрощения исходного до доказательства утверждений. В информатике же оно используется в основном для упрощения, ведь при производстве цифровой электроники, как и любого другого товара, требуются наименьшие затраты. Для упрощения булевых выражений используются те же методы, что и при упрощении алгебраических. Для начала была проведена аналогия между алгебраическими операторами от двух аргументов (сложение, вычитание, умножение и т.д.) и булевыми. Было выяснено, что умножение и логическое «И» обладают сходными свойствами:
- от перестановки мест аргументов результат не изменяется
A & B = B & A
- существует следующий закон
A & (B & C) = (A & B) & C
Также существуют некоторые тождества, опирающиеся на особые свойства функции, например:
1) A & (~A) = ЛОЖЬ
2) (~A) & (~B) = ~ (A v B)
Аналогично, сложение и логическое «ИЛИ»:
- от перестановки мест
A v B = B v A
- существует следующий закон
(A v B) v С = A v (B v C)
- можно выносить общий множитель за скобки
(A & B) v (С & B) = B & (A v C)
И также некоторые собственные законы:
1) A v (~A) = ИСТИНА
2) (~A) v (~B) = ~ (A & B)
Когда вычисляется значение булевого выражения, то выполняется определённая очерёдность действий: на очерёдность влияют скобки, сначала считаются «И», затем «ИЛИ». Благодаря этой очерёдности возможно создание электронных цифровых схем.
НАХОЖДЕНИЕ ИСХОДНОГО ВЫРАЖЕНИЯ
В отличие от алгебраических выражений, булевы можно восстановить, зная их аргументы и соответственные им значения. Пусть нам дана булева функция от 3 переменных (табл. 4):
Таблица 4
X1 |
X2 |
X3 |
F |
0 1 0 1 0 1 0 1 |
0 0 1 1 0 0 1 1 |
0 0 0 0 1 1 1 1 |
0 0 0 1 0 1 0 1 |
Составим для неё таблицу и условимся обозначать ИСТИНУ - 1, а ЛОЖЬ – 0.
Для начала выпишем все аргументы функции, при которых функция равна 1.
Это:
F (1, 1, 0) = 1
F (1, 0, 1) = 1
F (1, 1, 1) = 1
Теперь запишем 3 таких выражения (функция принимает значение 1 три раза), что они принимают значение 1 только при вышеуказанных значениях.
X1 & X2 & (~X3)
X1 & (~X2) & X3
X1 & X2 & X3
И запишем их логическую сумму:
(X1 & X2 & (~X3)) v (X1 & (~X2) & X3) v (X1 & X2 & X3) – это выражение принимает значение 1 при тех же значениях, что и исходная функция. Полученное выражение можно упростить.
(X1 & X2 & (~X3)) v (X1 & (~X2) & X3) v (X1 & X2 & X3) =
= X1 & ((X2 & (~X3)) v ((~X2) & X3) v (X2 & X3)) =
= X1 & ((X2 & (~X3)) v X3 & ((~X2) v X2)) =
= X1 & ((X2 & (~X3)) v X3) – эта формула несколько длиннее исходной, но намного проще полученной в первый раз. Дальнейшие пути упрощения более сложны и представляют большой интерес для проектировщиков интегральных микросхем, т.к. меньшее число операций требует меньшее число элементов, их которых состоит ИС.
ПРИМЕНЕНИЕ В ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКЕ
После изготовления первого компьютера стало ясно, что при его производстве возможно использование только цифровых технологий – ограничение сигналов связи единицей и нулём для большей надёжности и простоты архитектуры ПК. Благодаря своей бинарной природе, математическая логика получила широкое распространение в ВТ и информатике. Были созданы электронные эквиваленты логических функций, что позволило применять методы упрощения булевых выражений к упрощению электрической схемы. Кроме того, благодаря возможности нахождения исходной функции по таблице позволило сократить время поиска необходимой логической схемы.
В программировании логика незаменима как строгий язык и служит для описания сложных утверждений, значение которых может определить компьютер.
На современном этапе развития экономики и производства, все большей актуальности приобретает проблема оптимизации операций во всех сферах и на всех уровнях хозяйственной деятельности. Оптимальное распределение всех видов ресурсов позволяет не только сэкономить средства, время и эти же ресурсы, но и открывает дополнительные производственно-экономические возможности.
Поскольку задачи оптимизации очень разнообразны, существует множество методов поиска оптимального решения. Одной из самых актуальных задач оптимизации является задача календарного планирования – планирование времени выполнения работ. На производственных предприятиях разных отраслей и разных мощностей часто возникает необходимость спланировать оптимальным образом график работы цеха за определенный период времени.
Несмотря на существования большого числа алгоритмов решения задач календарного планирования, наиболее распространенными являются эвристические методы. В данной работе будет рассмотрен новый метод календарного планирования, применяющий булевы функции. Для решения задачи планирования загрузки оборудования, методом, приведенным ниже необходимо выполнение следующих условий:
1) каждая машина (станок) эксплуатируется в течение периода времени, т. е. исключается остановка или поломка машины;
2) каждая операция может
3) на участке имеется только один станок данного типа;
4) следующая операция на этом
же станке может выполняться
только после полного завершени
5) каждый станок в данный момент времени может выполнять не более одной операции.
Далее представлена модель загрузки станков, параметрами которой являются:
M – разнообразие станков в цехе, C k ij , i=1...N, j=1…T – матрица издержек за час работы k -го вида станка, где C ij – матрица издержек обработки i -го вида продукции в j -й час работы станка. В данной работе будет рассмотрен случай, когда в цехе имеется по одному станку каждого типа, т.е. выполняется условие 3. X k ij – матриця переходів з компонентами : X k ij = 1, если k –й станок обрабатывает i -й вид продукции в j -й час, k =1... M , X k ij = 0, если не обрабатывает, V k ij – матрица заказа ( определяет количество часов, необходимых для обработки i -го вида продукции на k -м станке).
Тогда задача минимизации времени на изготовление единицы продукции может быть сформулирована так (формулы 1,2,3,4):
Ограничение – матрица собственно обработки i -го вида продукции в j -й час на k – ом станке, элементами матрицы являются булевы функции (1, если обрабатывает; 0, если не обрабатывает). Получение оптимальным образом скомпонованной матрицы обработки является целью задачи. Ограничение означает, что количество часов в течени и которого обрабатывался i -й вид продукции на k – ом станке должен строго соответствовать технологи (заказу).
Ограничение актуально, если имеется только один станок k –ого типа, способный надлежащим образом обработать продукт, т.е. выполняются условия 3 и 5. В случае , если в цеху имеется более, чем одна машина данного типа, либо станок способен одновременно обрабатывать более, чем одну единицу продукции, в правой части ограничения указываются соответствующая пропускная способность станка/станков (дискретно).
Таким образом, задача планирования графика сводится к тривиальной транспортной задаче. При такой постановке задаче, представляется возможным ввести дополнительные ограничения F i ( x ) i=1... N , экономическим смыслом которых является премия за досрочное изготовление i -го продукта (формула 5):
В этом выражении:
Очевидно, что введение в задачу F i ( x ), должно улучшать решение задачи. Таким образом, a i - отрицательное число, исходя из того, что целевая функция стремится к минимуму.
Необходимо отметить, что применение нумерации станков и связанная с этим матрица C ij позволяет , если это необходимо, задавать технологическую последовательность обработки продукта на разных станках.
Составление релейно-контактных схем с заданными условиями работы называется задачей синтеза релейно-контактных схем и является первой важной задачей, состоящей в том, что требуется построить схему, которая проводила бы электрический ток лишь при вполне определенных задаваемых условиях.
Естественно было бы выбирать для каждой булевой функции самую простую или одну из самых простых реализующих ее релейно-контактных схем. Поэтому упрощение релейно-контактных схем называется задачей анализа таких схем и является второй важной задачей теории релейно-контактных схем. Две релейно-контактные схемы, составленные из одних и тех же реле, называются равносильными, если одна из них проводит ток тогда и только тогда, когда другая схема проводит ток. Другими словами, две схемы, составленные из одних и тех же реле, равносильны, если они обладают одинаковыми функциями проводимости, зависящими от одних и тех же переменных. Из двух равносильных схем более простой считается та, которая содержит меньшее число контактов. Задача упрощения релейно-контактной схемы состоит в нахождении более простой равносильной ей схемы. Обычно она решается следующим образом. Для данной релейно-контактной схемы записывается ее функция проводимости. Затем эта функция с помощью тождественных преобразований, использующих известные свойства булевых функций, упрощается, т.е. сводится к функции, имеющей меньшее число вхождений переменных, нежели исходная функция. Наконец строится релейно-контактная схема, отвечающая упрощенной булевой функции.
ЗАКЛЮЧЕНИЕ
Итак, логика возникла задолго до появления компьютеров и возникла она в результате необходимости в строгом формальном языке. Были построены функции – удобное средство для построения сложных утверждений и проверки их истинности. Оказалось, что такие функции обладают аналогичными свойствами с алгебраическими операторами. Это дало возможность упрощать исходные выражения. Особое свойство логических выражений – возможность их нахождения по значениям. Это получило широкое распространение в цифровой электронике, где используются логические элементы, и программировании.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. «Компьютер» Ю. Л. Кетков, г. Москва, издательство «Дрофа», 1997 г., 225 стр.
2. «Математика» Ю. Владимиров, г. Москва издательство «Аванта», 1998 г., 346 стр.
3. http://konspektiruem.ru/
4. http://xreferat.ru/54/2115-1-
Челябинск 2012
- Алгебра логики: основные понятия и законы. Понятие функционально полной системы логических элементов
- Алгебралық және трансценденттік теңдеуді шешу әдістері
- Алгебралық тұжырымдау туралы түсінік
- Алгебра матриц
- Алгебра оқиғасы. Ықтималдылығы.Ықтималдықтың қасиеттері
- Алгокольное отравление
- Алгоритимге кириспе
- Алгебра высказывавнии
- Алгебра және анализ бастамалары
- Алгебраические линии и их порядок
- Алгебраические числа
- Алгебраически метод решения задач на построение
- Алгебра і початки аналізу
- Алгебра логики высказываний
