Алгебра логики. История возникновения. Основные положения

Таблица 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) – эта формула  несколько длиннее исходной, но  намного проще полученной в  первый раз. Дальнейшие пути упрощения более сложны и представляют большой интерес для проектировщиков интегральных микросхем, т.к. меньшее число операций требует меньшее число элементов, их которых состоит ИС.

 

6. ПРИМЕНЕНИЕ В ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКЕ

 

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

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

На современном этапе развития экономики и производства, все большей актуальности приобретает проблема оптимизации операций во всех сферах и на всех уровнях хозяйственной деятельности.   Оптимальное распределение всех видов ресурсов позволяет не только сэкономить средства, время и эти же ресурсы, но и открывает дополнительные производственно-экономические возможности.

Поскольку задачи оптимизации очень разнообразны, существует множество методов поиска оптимального решения. Одной из самых актуальных задач оптимизации является задача календарного планирования – планирование времени выполнения работ. На производственных предприятиях разных отраслей и разных мощностей часто возникает необходимость спланировать оптимальным образом график работы цеха за определенный период времени.

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

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):

               (1)

                               (2)

              

                         (3)

               

               (4)

Ограничение – матрица собственно обработки i -го вида продукции в   j -й час на k – ом станке, элементами матрицы являются булевы функции (1, если обрабатывает; 0, если не обрабатывает).   Получение оптимальным образом скомпонованной матрицы обработки является целью задачи.   Ограничение означает, что количество часов в течени и которого обрабатывался i -й вид продукции на k – ом станке должен строго соответствовать технологи (заказу).

Ограничение актуально, если имеется только один станок k –ого типа, способный надлежащим образом обработать продукт, т.е. выполняются условия 3 и 5. В случае , если в цеху имеется более, чем одна машина данного типа, либо станок способен одновременно обрабатывать более, чем одну единицу продукции, в правой части ограничения указываются соответствующая пропускная способность станка/станков (дискретно).

Таким образом, задача планирования графика сводится к тривиальной транспортной задаче. При такой постановке задаче, представляется возможным ввести дополнительные ограничения F i ( x ) i=1... N , экономическим смыслом которых является премия за досрочное изготовление i -го продукта (формула 5):

В этом выражении:

       (5)

Очевидно, что введение в задачу F i ( x ), должно улучшать решение задачи. Таким образом, a i - отрицательное число, исходя из того, что целевая функция стремится к минимуму.

Необходимо отметить, что применение нумерации станков и связанная с этим матрица C ij   позволяет , если это необходимо, задавать технологическую последовательность обработки продукта на разных станках.

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

Естественно было бы выбирать для каждой булевой функции самую простую или одну из самых простых реализующих ее релейно-контактных схем. Поэтому упрощение релейно-контактных схем называется задачей анализа таких схем и является второй важной задачей теории релейно-контактных схем. Две релейно-контактные схемы, составленные из одних и тех же реле, называются равносильными, если одна из них проводит ток тогда и только тогда, когда другая схема проводит ток. Другими словами, две схемы, составленные из одних и тех же реле, равносильны, если они обладают одинаковыми функциями проводимости, зависящими от одних и тех же переменных. Из двух равносильных схем более простой считается та, которая содержит меньшее число контактов. Задача упрощения релейно-контактной схемы состоит в нахождении более простой равносильной ей схемы. Обычно она решается следующим образом. Для данной релейно-контактной схемы записывается ее функция проводимости. Затем эта функция с помощью тождественных преобразований, использующих известные свойства булевых функций, упрощается, т.е. сводится к функции, имеющей меньшее число вхождений переменных, нежели исходная функция. Наконец строится релейно-контактная схема, отвечающая упрощенной булевой функции.

 

ЗАКЛЮЧЕНИЕ

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1. «Компьютер» Ю. Л. Кетков, г. Москва, издательство «Дрофа», 1997 г., 225 стр.

2. «Математика» Ю. Владимиров, г. Москва издательство «Аванта», 1998  г., 346 стр.

3. http://konspektiruem.ru/articles/logic/Sposoby_zadanija_funkcii_logiki/ - Конспектируем.ру. Собрание уникальных  материалов.

4. http://xreferat.ru/54/2115-1-algebra-logiki.html - XReferat. Крупнейшая база рефератов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Челябинск 2012