Планета Информатики

Алгебра логики и логические основы компьютера

Алгебра логики

Алгебра логики, или булева алгебра, – это раздел математики, возникший в XIX веке благодаря работам английского математика Джорджа Буля. Поначалу булева алгебра не имела практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем.

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

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

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

Фразы "два больше одного", "5.8 является целым числом" будем считать примерами простых логических высказываний. Анализируя эти высказывания, мы делаем вывод, что первая фраза правдивая, вторая – ложная. Это и есть результат выполнения простого логического выражения.

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

Логические операции. Дизъюнкция, конъюнкция и отрицание

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

Как мы решаем, что нам сказали правду или нет? Логически, где-то неосознанно, исходя из предыдущего жизненного опыта, мы понимает, что правда при союзе "и" наступает в случае истинности обоих простых высказываний. Стоит одному стать ложью и все сложное высказывание будет таковым. А вот при связке "либо" должно быть правдой только одно простое высказывание, и тогда все выражение станет истинным.

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

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

Базовыми операциями являются конъюнкция И, дизъюнкция ИЛИ и отрицание НЕ. Часто конъюнкцию обозначают &, дизъюнкцию - ||, а отрицание - чертой над переменной, обозначающей высказывание.

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

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

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

Таблицы истинности

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

Логические основы компьютера

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

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

Переключательные схемы

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

Вентили, триггеры и сумматоры

Вентиль представляет собой логический элемент, который принимает одни двоичные значения и выдает другие в зависимости от своей реализации. Так, например, есть вентили, реализующие логическое умножение (конъюнкцию), сложение (дизъюнкцию) и отрицание.

Триггеры и сумматоры – это относительно сложные устройства, состоящие из более простых элементов – вентилей.

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

Сумматоры широко используются в арифметико-логических устройствах (АЛУ) процессора и выполняют суммирование двоичных разрядов.