Логические основы работы ЭВМ
Введение
логика информация алгебра
Любое устройство или механизм, созданный человеком, строится на основе определенных закономерностей его работы, которые будут выделять его через особенности применения и функциональные возможности. Потребность в удовлетворении насущных потребностей является главным стимулом разработки новых видов машин, технологий и т.д. Такая возможность обеспечивается накоплением знаний во многих областях науки и техники, применение которых позволяет создать сначала логические предпосылки новых областей техники, например, логические основы ЭВМ, а затем и воплотить их в новых видах оборудования.
Толчком возникновения ЭВМ стали два движущих мотива: потребность в больших объемах переработки информации и достижения в различных областях науки и техники. Для реализации технической идеи вычислительного устройства были сформулированы логические основы ЭВМ с использованием алгебры логики, определившие набор функций и теоретическую базу. Законы алгебры логики, которая определила логические основы компьютера, сформулировал еще в 19-м веке англичанин Дж. Буль. Фактически, это теоретическая база систем цифровой обработки информации. Ее суть составляют правила логических отношений между числами: конъюнкция, дизъюнкция и другие, что очень похоже на хорошо известные основные соотношения между числами в арифметике - умножение, сложение и т.д. Числа в булевой алгебре имеют двоичное представлением, т.е. изображаются цифрами только 1 и 0. Действия с числами описываются дополнительными символами алгебры логики. Эти элементы математики позволяют комбинацией простейших логических законов описать любую вычислительную задачу или управляющее действие специальными символами, то есть, «написать программу». При помощи устройства ввода эта программа «загружается» в ЭВМ и служит «распоряжением» для нее, которое надлежит выполнить.
1. Основные понятия алгебры логики
Алгебра логики возникла в середине 19 века в трудах английского математика Джорджа Буля. Её создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.
Отцом алгебры логики по праву считается английский математик 19-го столетия Джордж Буль (1815-1864). Именно он построил один из разделов формальной логики в виде некоторой «алгебры», аналогичной алгебре чисел, но не сводящейся к ней. Алгебра в широком смысле слова - наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться не только с числами, но и над другими математическими объектами. Существуют алгебры натуральных чисел, многочленов, векторов, матриц, множеств и т.д.
Большой вклад в становление и развитие алгебры логики внесли Августус де Морган (1806-1871), Уильям Стенли Джевонс (1835-1882), П.С. Порецкий(1846 - 1907), Чарлз Сандерс Пирс (1839-1914), А.А. Марков (1903-1979), А.Н. Колмогоров (1903-1987) и др.
Долгое время алгебра логики была известна достаточно узкому классу специалистов. Прошло почти 100 лет со времени создания алгебры логики Дж. Булем, прежде чем в 1938 Клод Шеннон (1916-2001) показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе функционирования релейно-контактных и электронно-ламповых схем.
Алгебра логики явилась математической основой теории электрических и электронных переключателей схем, используемых в ЭВМ. В компьютерных науках её предпочитают называть не алгеброй логики, а Булевой алгеброй - по имени её создателя.
Алгебра логики изучает свойства функций, у которых и аргументы, и значения принадлежат заданному двухэлементному множеству (например, {0,1}).Иногда вместо термина «алгебра логики» употребляют термин «двузначная логика».
Алгебра логики - предельно важная для цифровых компьютеров тема. И с точки зрения их устройства, схем техники, и с точки зрения их функционирования и программирования поведения.
Действительно, мало-мальски сложное действие невозможно без обратной связи, без анализа условий выполнения. Например, «ЕСЛИ нам хочется пить, ТО мы пьём, ИНАЧЕ мы даже не думаем об этом». «ЕСЛИ компьютер не работает И питание включено, ТО компьютер сгорел». «ЕСЛИ точка левее левой стороны квадрата ИЛИ правее правой, ТО точка расположена не в квадрате». «Ревёт ли зверь в лесу глухом, трубит ли рог, гремит ли гром...». «Кошелёк или жизнь». Помимо манипуляций константами «да» и «нет» логические переменные могут являться результатом применения к числам операторов отношения (меньше, больше, равно и т.п.). В компьютерах булевы переменные представляются (кодируются) битами (разрядами двоичной системы счисления), где 1 означает истину, а 0 - ложь. Манипуляции высказываниями и их комбинациями используются для получения некоего единственного результата, который можно использовать, например, для выбора той или иной последовательности действий. Поскольку логические переменные кодируются по тем же принципам, что и числа, символы и прочая информация, то можно комбинировать операции логики с операциями арифметики для реализации различных алгоритмов.
Таким образом, алгебра логики (другое название - Булева алгебра) - это область математики. Она оперирует величинами, которые могут принимать два значения (булевых значения). Эти два значения могут быть обозначены как угодно, лишь бы по-разному. Самые распространенные варианты:
, 1;F, T;false, true;ложь, истина;Л, И;
При применении булевой алгебры в вычислительной технике, булевы значения - это 0 и 1. Они представляют собой состояние ячейки памяти объёмом в 1бит или наличие/отсутствие напряжения в электрической схеме. Алгебра логики позволяет строить сложные электронные узлы, элементы которых работают согласно этой математической теории. При применении булевой алгебры в логических построениях в математике, булевы значения - это «ложь» и «истина». Они определяют истинность или ложность некоторого высказывания. Под высказываниями понимаются математические формулы. При применении булевой алгебры в повседневных рассуждениях, булевы значения - это также «ложь» и «истина». Они представляют собой оценку истинности или ложности некоторого высказывания. Под высказываниями понимаются фразы, которые удовлетворяют строго определенному списку свойств.
Алгебра логики применяется: 1) для упрощения сложных логических формул и доказательств тождеств; 2) при решении логических задач; 3) в контактных схемах; 4) при доказательствах теорем; 5) в базах данных при составлении запросов.
Объектом логики как науки выступает абстрактное мышление. Логика изучает абстрактное мышление как средство познания объективного мира, исследует формы и законы, в которых происходит отражение мира в процессе мышления. Основными формами абстрактного мышления являются: понятия; суждения; умозаключение;
Понятие - форма мышления, в которой отражаются существенные признаки отдельного предмета или класса однородных предметов: портфель, трапеция, ураганный ветер или группой слов, т.е. словосочетаниями, например: "студент гуманитарного института", "создатель художественных картин", "река Дон", "космический корабль" и др.
Суждение - мысль, в которой что-либо утверждается или отрицается о предметах. Суждения являются повествовательными предложениями, истинными или ложными. Они могут быть простыми и сложными: Весна наступила, и грачи прилетели.
Умозаключение - прием мышления, посредством которого из исходного знания получается новое знание; из одного или нескольких истинных суждений, называемых посылками, мы по определённым правилам вывода получаем заключение. Есть несколько видов умозаключений. Все металлы - простые вещества. Литий - металл. Литий - простое вещество.
Все металлы - вещества. Железо - металл. Железо - вещество.
Чтобы достичь истины при помощи умозаключений, надо соблюдать законы логики.
Формальная логика - наука о законах и формах правильного мышления.
Математическая логика изучает логические связи и отношения, лежащие в основе дедуктивного (логического) вывода.
Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в итовую логику: истинность высказывания обозначается одним битом (0 - ЛОЖЬ, 1 - ИСТИНА); тогда операция ¬ приобретает смысл вычитания из единицы; ∨ - немодульного сложения; & (или ∧) - умножения; ↔ - равенства; ⊕ - в буквальном смысле сложения по модулю 2 (исключающее Или - XOR); ⎪ - не превосходства суммы над 1 (то есть A⎪B = (A + B) <= 1). [
Впоследствии булева алгебра была обобщена от логики высказываний путём введения характерных для логики высказываний аксиом. Это позволило рассматривать, например, логику кубитов, тройственную логику (когда есть три варианта истинности высказывания: «истина», «ложь» и «не определено») и др.
2. Логические основы работы ЭВМ
.1 Логика
Информация, обрабатываемая в ЭВМ, представляется с помощью физических величин, которые могут принимать только два устойчивых состояния и называются «двоичные переменные».
Вычислительные устройства, или, в общем случае, устройства обработки информации, представляют собою совокупность элементарных логических схем, т. е. простых схем, обрабатывающих эти величины.
Логика - это наука о формах и способах мышления.
Основными формами мышления являются:
· понятие,
· высказывание
· умозаключение.
Понятие - фиксирует основные, существенные признаки объекта. Высказывание - это любое предложение, в отношении которого имеет смысл утверждение о его истинности или ложности. При этом считается, что высказывание удовлетворяет закону исключенного третьего, т.е. каждое высказывание или истинно, или ложно и не может быть одновременно и истинным, и ложным.
Для того, чтобы можно было определить истинность или ложность высказываний, не вникая в их содержание, была придумана алгебра высказываний (алгебра логики).
Алгебра логики - это раздел математической логики, значения всех элементов (функций и аргументов) которой определены в двухэлементном множестве: 0 (ложь) и 1 (истина). Алгебра логики оперирует с логическими высказываниями.
В этой алгебре можно производить некоторые логические операции над высказываниями, получая в результате новые составные высказывания. В алгебре логики все высказывания обозначают буквами а, b, с и т.д. Содержание высказываний учитывается только при введении их буквенных обозначений, и в дальнейшем над ними можно производить любые действия, предусмотренные данной алгеброй. Причем если над исходными элементами алгебры выполнены некоторые разрешенные в алгебре логики операции, то результаты операций также будут элементами этой алгебры.
Логическая переменная - это переменная, принимающая состояние, соответствующая одному из двух элементов, например, 0 (ложь) или 1 (истина).
Логические выражение - составное высказывание, которое можно выразить в виде формулы, в которую войдут логические переменные, обозначающие высказывания, и знаки логических операций, обозначающие логические функции.
Для записи составных высказываний в виде логических выражений на формальном языке (языке алгебры логики) в составном высказывании нужно выделить простые высказывания и логические связи между ними. Истинность или ложность составных высказываний можно определять чисто формально, руководствуясь законами алгебры высказываний, не обращаясь к смысловому содержанию высказываний.
2.2 Базовые логические операции
Операция инверсия (отрицания).
Инверсия делает истинное высказывание ложным и наоборот, ложное - истинным. На формальном языке отрицание обозначают чертой над аргументом.
Конъюнкция (логическое умножение, логическое «И»).
Операция логического умножения, соответствующая функции «И», выдает в качестве результата значение, называемое логическим произведением. Результат операции истинен тогда и только тогда, когда истинны все входящие в него простые высказывания.
На формальном языке алгебры логики операция конъюнкции обозначается значком «&» или «^» или «*» (знаком умножения). Например, F = A & B. Аргументы могут принимать значения 1 или 0 и результат тоже только значения 1 или 0. Значение логической функции F можно определить из таблицы истинности этой функции.
Дизъюнкция (логическое сложение, логическое «ИЛИ»).
Операция логического сложения, соответствующая функции «ИЛИ», выдает в качестве результата значение, называемое логической суммой. Результат операции истинен тогда, когда истинно хотя бы одно из входящих в него простых высказываний. На формальном языке алгебры логики операция дизъюнкции обозначается значком «+» или «\/». Например, F = A + B. Аргументы могут принимать значения 1 или 0 и результат тоже только значения 1 или 0. Значение логической функции F можно определить из таблицы истинности этой функции.
Приоритет логических операций.
Приоритет выполнения операций:
. Операция Инверсия (отрицания)
. Операция Конъюнкция (логического умножения)
. Операция Дизъюнкция (логического сложения).
2.3 Другие логические операции
Сложение по модулю 2 ( исключающее «ИЛИ»)
Результат операции истинен тогда, когда истинно только одно из входящих в него простых высказываний, но не оба одновременно.
На формальном языке алгебры логики операция исключающего «ИЛИ» обозначается значком «Å». Например, F = A Å B. Аргументы могут принимать значения 1 или 0 и результат тоже только значения 1 или 0. Значение логической функции F можно определить из таблицы истинности этой функции.
Операция импликация (следование).
Операция импликация равносильна логическому выражению ¬A + B (не А или В). Результат операции ложен тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод (второе высказывание).
На формальном языке алгебры логики операция импликации обозначается значком «→».Например, F = A → B. Аргументы могут принимать значения 1 или 0 и результат тоже только значения 1 или 0. Значение логической функции F можно определить из таблицы истинности этой функции.
Операция эквивалентность (равенство).
Результат операции истинен тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны.
На формальном языке алгебры логики операция эквивалентности обозначается значком «~». Например, F = A ~ B. Аргументы могут принимать значения 1 или 0 и результат тоже только значения 1 или 0. Значение логической функции F можно определить из таблицы истинности этой функции.
Штрих Шеффера.
Результат операции ложен тогда и только тогда, когда оба высказывания одновременно истинны.
На формальном языке алгебры логики операция обозначается значком «|». Например, F = A | B. Аргументы могут принимать значения 1 или 0 и результат тоже только значения 1 или 0. Значение логической функции F можно определить из таблицы истинности этой функции.
Стрелка Пирса.
На формальном языке алгебры логики операция обозначается значком «¯». Например, F = A ¯ B. Аргументы могут принимать значения 1 или 0 и результат тоже только значения 1 или 0. Значение логической функции F можно определить из таблицы истинности этой функции.
2.4 Основные законы логики
Законы логики отражают наиболее важные закономерности логического мышления. В алгебре высказываний законы логики записываются в виде формул, которые позволяют проводить эквивалентные преобразования логических выражений в соответствие с законами логики.
Закон тождества.
Всякое высказывание тождественно самому себе:
А = А
Закон непротиворечия.
Высказывание не может быть одновременно истинным и ложным. Если высказывание А - истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно:
& ¬A = 0
Закон исключенного третьего.
Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение истина:
+ ¬A = 1
Закон двойного отрицания.
Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание:
¬ ¬A = A
2.5 Теоремы Булевой алгебры
. ¬¬х = х
. х + 0 = х
. х + 1 = 1
. х * 1 = х
. х * 0 = 0
. х + х = х
. х * х = х
. х + х * у = х
. х * (х+у) = x
. х + (¬х * у) = х + у
. х * (¬х + у) = х * у
Правило коммутативности. В обычной алгебре слагаемые и множители можно менять местами. В алгебре высказываний можно менять местами логические переменные при операциях логического умножения и логического сложения:
. х + у = у + х
. х * у = у * х
Правило ассоциативности. Если в логическом выражении используются только операция логического умножения или только операция логического сложения, то можно пренебрегать скобками или произвольно их расставлять:
. х + у + а = (х + у) + а = х + (у + а)
. х * у * а = (х * у) *а = х * (у * а)
Правило дистрибутивности. В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые:
. х * (у + а) = х * у + х * а
. х + у * а = (х + у) * (х + а)
Законы де Моргана. Отрицание логической суммы равно логическому произведению отрицаний и отрицание логического произведения равно логической сумме отрицаний:
18. ¬(x + y)= ¬x * ¬y
. ¬(x * y)= ¬x + ¬y
2.6 Минимизация логических функций
Для упрощения логических (булевых) функций используют тождества математической логики, рассмотренные ранее. На самом деле их эффективное использование требует навыков и искусства в манипулировании ими, которые приходят только после определенного опыта подобных преобразований. В то же время существует несколько стандартных приемов, которые в большинстве случаев позволяют упростить достаточно сложные логические формулы.
Упрощение логического выражения начинают обычно с поиска следующих форм: AB + AB , A + AB , A + AB , где A и B обозначают либо сами логические переменные, либо логические произведения множества переменных. Каждое из полученных выражений может быть записано в более простой форме следующим образом:
AB + AB = A(B + B) = A; + AB = A(1+ B) = A; + AB = (A + AB) + AB = A + B.
Возьмем, например, формулу:
f = x × y × z + x × y × z + x × y × z + x × y × z + x × y × z
и попытаемся ее упростить, используя изученные тождества. Группируя первый и четвертый термы, затем третий и пятый, и применяя первое из тождеств , получим:
= x × y + x × y × z + x × z.
Далее выражение упрощается без особой сложности:
= x( y + yz) + xz = x( y + z) + xz = xy + xz + xz = xy + z.
Заключение
Информатика, как никакая другая область знаний, характеризуется чрезвычайно высокой степенью динамики изменений. Кроме того, учитывая ее всепроникающий характер, благодаря которому происходят интеграция знаний, идей, в настоящее время трудно очертить границы информатики.
Информатика и связанные с ней информационные технологии - необходимый атрибут профессиональной пригодности в обществе.
Информатика служит, прежде всего, для формирования определенного мировоззрения в информационной сфере и освоение информационной культуры, т.е. умение целенаправленно работать с информацией, профессионально используя ее для получения, обработки и передачи компьютерную информационную технологию и соответствующие ей технические и программные средства.
Алгебра логики (булева алгебра) - это раздел математики, возникший в XIX веке благодаря усилиям английского математика Джорджа Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор и т. д.). Хотя это не единственная сфера применения данной науки.
Список использованных источников
1)Логические основы работы ЗВМ : методические указания по информатике для студентов всех специальностей / сост. Н. Д. Белова, Н. И. Шадрина. - Хабаровск : Изд-во Тихоокеан. гос. ун-та, 2011. - 16 с.