Теоретический материал

Теоретический материал на тему:

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

Алгебра логики (булева алгебра). В 1847 году английский математик Джордж Буль, преподаватель провинциального университета в маленьком городке Корке на юге Англии разработал алгебру логики. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.

Что же собой представляет алгебра логики? Алгебра логики – раздел математики, изучающий высказывания с точки зрения их логических значений сложных логических высказываний с помощью алгебраических методов и логических операций над ними. Булева алгебра делает это таким образом, что сложное логическое высказывание описывается функцией, результатом вычисления которой может быть либо истина, либо ложь (1, либо 0). При этом аргументы функции (простые высказывания) также могут иметь только два значения: 0, либо 1.

Формы мышления

Первые учения о формах и способах рассуждений возникли в странах древнего Востока (Китай, Индия), но в основе современной логики лежат учения, созданные древнегреческими мыслителями. Основы формальной логики заложил Аристотель, который впервые отделил логические формы мышления (речи) от его содержания.

Мышление всегда осуществляется в каких-то формах. Основными формами мышления являются:

Понятие — это форма мышления, фиксирующая основные, существенные признаки объекта.

Понятие имеет две стороны: содержание и объем. Содержание понятия составляет совокупность существенных признаков объекта. Чтобы раскрыть содержание понятия, следует найти признаки, необходимые и достаточные для выделения данного объекта из множества других объектов.

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

Объем понятия определяется совокупностью предметов, на которые оно распространяется. Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров.

Что такое простое логическое высказывание (суждение)? Это форма мышления, которое может быть истинно (верно) или ложно (два плюс два равно четырем – это истина, два плюс два равно пяти - это ложь). Алгебра логики не касается сути этих высказываний. Если кто-то решит, что высказывание «Земля квадратная» истинно, то алгебра логики это примет как факт. Дело в том, что булева алгебра занимается вычислениями результата сложных логических высказываний на основе заранее известных значений простых высказываний.

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

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

Логические выражения. Логические операции

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

Конъюнкция (умножение) & ()

A&B

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

Дизъюнкция (сложение) V

AVB

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

Отрицание (инверсия) ¬ (Ā)

¬A

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

Импликация (следование) ®

A®B

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

Эквивалентность (равнозначность) «

A«B

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

Исключающая дизъюнкция (исключающее ИЛИ) (XOR)

A XOR B

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

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

Порядок следования логических операций

отрицание (¬), конъюнкция (& () ), дизъюнкция (V), импликация (®), эквивалентность («)

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

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

При построении таблиц истинности целесообразно руководствоваться определенной последовательностью действий.

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

Количество строк =

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

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

1.разделить столбец значений первой переменной на 2 и заполнить верхнюю половину колонки нулями, а нижнюю – единицами;

2.разделить столбец значений второй переменной на 4 и заполнить четверти чередующимися группами нулей и единиц, начиная с группы нулей;

3.продолжить деление столбцов значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами нулей и единиц до тех пор, пока группа нулей (единиц) не будет состоять из одного символа.

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

Пример:

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

Итак, чтобы составить таблицу истинности для логической формулы, надо выполнить следующие шаги:

подсчитать количество переменных n в логическом выражении;
определить число строк в таблице, которое равно Q = 2n
подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество операций;
ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учётом скобок и приоритетов;
заполнить столбцы входных переменных наборами значений;
провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной последовательностью.

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

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

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

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

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

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

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

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

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

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

Законы алгебры логики

Логические выражения можно преобразовывать в соответствии с законами алгебры логики:

Законы рефлексивности
a ∨ a = a
a ∧ a = a
Законы коммутативности
a ∨ b = b ∨ a
a ∧ b = b ∧ a
Законы ассоциативности
(a ∧ b) ∧ c = a ∧ (b ∧ c)
(a ∨ b) ∨ c = a ∨ (b ∨ c)
Законы дистрибутивности
a ∧ (b ∨ c) = a ∧ b ∨ a ∧ c
a ∨ b ∧ c = (a ∨ b) ∧ (a ∨ c)
Закон отрицания отрицания
¬ (¬ a) = a
Законы де Моргана
¬ (a ∧ b) = ¬ a ∨ ¬ b
¬ (a ∨ b) = ¬ a ∧ ¬ b
Законы поглощения
a ∨ a ∧ b = a
a ∧ (a ∨ b) = a

Логические элементы. Вентили

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

Простейший вентиль представляет собой транзисторный инвертор, который преобразует низкое напряжение в высокое или наоборот (высокое в низкое). Это можно представить как преобразование логического нуля в логическую единицу или наоборот. Т.е. получаем вентиль НЕ.

Соединив пару транзисторов различным способом, получают вентили ИЛИ-НЕ и И-НЕ. Эти вентили принимают уже не один, а два и более входных сигнала. Выходной сигнал всегда один и зависит (выдает высокое или низкое напряжение) от входных сигналов. В случае вентиля ИЛИ-НЕ получить высокое напряжение (логическую единицу) можно только при условии низкого напряжении на всех входах. В случае вентиля И-НЕ все наоборот: логическая единица получается, если все входные сигналы будут нулевыми. Как видно, это обратно таким привычным логическим операциям как И и ИЛИ. Однако обычно используются вентили И-НЕ и ИЛИ-НЕ, т.к. их реализация проще: И-НЕ и ИЛИ-НЕ реализуются двумя транзисторами, тогда как логические И и ИЛИ тремя.

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

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