Основы булевой алгебры
план-конспект занятия по информатике и икт (10 класс) на тему

Основы булевой алгебры

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

Алгебра логики — часть математической логики, значения всех элементов которой определены в двухэлементном множестве, а именно «Истина» («True») и «Ложь» («False»), т.е. 1 либо 0.

Логика, как наука о законах и формах мышления, изучает абстрактное мышление как средство познания объективного мира.

Основными формами абстрактного мышления являются:

• ПОНЯТИЯ
• СУЖДЕНИЯ
• УМОЗАКЛЮЧЕНИЯ

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

СУЖДЕНИЕ — мысль, в которой что-либо утверждается или отрицается о предметах. Суждения являются истинными или ложными повествовательными предложениями. Они могут быть простыми и сложными. Например: «Травка зеленеет»; «Солнышко греет»; «Травка зеленеет, и солнышко греет».

УМОЗАКЛЮЧЕНИЕ — прием мышления, посредством которого из исходного знания получается новое знание; из одного или нескольких истинных суждений, называемых посылками, мы по определенным правилам вывода получаем заключение.

Все металлы — простые вещества.

Литий — металл.

Литий — простое вещество.

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

Формальная логика — наука о законах и формах мышления.

Математическая логика изучает логические связи и отношения, лежащие в основе дедуктивного (логического) вывода.

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

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

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

Высказывание — это повествовательное предложение, о котором можно сказать, истинно оно или ложно.

Примеры:

Завтра будет дождь. Может быть истинным или ложным.

Земля — планета Солнечной системы. Истинно

4 + 6 < 5 ложно

2 * 2 = 4 истинно

Всякий квадрат есть параллелограмм. Истинно

Всякий параллелограмм есть квадрат. Ложно

6 * 6 = 30 ложно

Высказывания, приведенные выше, являются простыми. Сложные высказывания получаются путем объединения простых высказываний связками — союзами И, ИЛИ и частицей НЕ. Значение истинности сложных высказываний зависит от истинности входящих в них простых высказываний и от объединяющих их связок.

Операции сравнения

Операции сравнения называют еще операциями отношения (relation operations), поскольку в них осуществляется оценка взаимосвязи (отношений) двух операндов. Под операндом понимается то, над чем выполняется операция.

Результат сравнения может быть либо истинным, либо ложным (Тruе или False). Приоритет операций сравнения ниже, чем у арифметических операций.

Логические операции

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

Простейший логический оператор — NOT. Он предшествует единственному операнду и возвращает его логическую противоположность — иначе говоря, «отрицает» операнд. Например, выражение NOT False дает в результате Тruе (булево значение, обратное False); а выражение NOT (4 < 3) — Тruе, так как условие (4 < 3) ложно. Кроме того, этот оператор обладает наивысшим приоритетом по сравнению с остальными булевыми операторами. Кстати, операция отрицания является унарной, или одноместной, в отличие от остальных логических операций, являющихся бинарными, или двуместными, то есть выполняющими действия с двумя операндами.

Следующий (в порядке убывания приоритета) оператор — AND. Он возвращает True, только если оба операнда имеют значение True. По смыслу он соответствует английскому слову and (русскому и), что можно проиллюстрировать, например, таким утверждением: «Он получит эту должность, только если знает английский и разбирается в компьютерах».

Оператор OR возвращает True, если любой из двух операндов True или если оба True. И в этом случае логический смысл оператора совпадает с соответствующим словом в языке: «Я куплю этого кота, если он не дороже 50 долларов или если он — сиамской породы».

Пример 1. Определить, что сумма баллов S, набранная студентом на тестировании находится в пределах 100 баллов, то есть принадлежит интервалу [60,100]÷60   :

S >= 60 AND S <= 100. 

Пример 2. Определить, что сумма баллов S, набранная студентом на тестировании не входит 100 баллов, то есть находится вне интервала [60,100]÷в пределы 60    :

NOT (S >= 60 AND S <= 100);

или, что даёт тот же самый результат  S < 60 OR S > 100.

Для алгебры логики выполняются следующие законы:

1) сочетательный:

(а OR b) OR с = а OR (b OR с);

(а AND b) AND с = а AND (b AND с);

2) переместительный:

а OR b = b OR а;

а AND b = b AND а;

3) распределительный:

а AND (b OR с) = а AND b OR а AND с;

а OR b AND с = (а OR b) AND (а OR с).

Пример выполнения работы

Задание

Вычислить логическое выражение.

Y = (38 OR &H1C) AND &H15 IMP NOT &O5

Y1=1 Y2=10100 Y3=1111111111111011 Y4=111110

Решение

Переводим все операнды в двоичную систему счисления:

 38(10) = 100110(2)

1С(16) = 11100(2)

15(16) = 10101(2)

5 (8) = 101(2)

Указываем приоритет выполнения операций:

Y = (38 OR &H1C) AND &H15 IMP NOT &O5

Определяем результат выполнения каждой операции побитно, используя для представления операндов шестнадцатиразрядный дополнительный код:
1) 38 OR &H1C

2) NOT &O5

3) (38 OR &H1C) AND &H15

4) (38 OR &H1C) AND &H15 IMP NOT &O5

Результат

Y = Y3 = 1111111111111011(2) = 177773(8) = FFFB(16) = -5(10)

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