Связь между алгеброй логики и двоичным кодированием

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже две: "1" и "0".

1. Основные понятия математической логики

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

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

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Для обозначения истины (истинного высказывания) используется символ 1, а для обозначения лжи (ложного высказывания) используется символ 0. Привести примеры ложных и истинных высказываний.

Рассмотрим примеры логических высказываний (см. Таблицу 1):

Таблица 1. Примеры логических выражений

Слова и словосочетания «не», «и», «или», «если…то», «тогда и только тогда» называют логическими связками. Высказывания бывают элементарные и составные.

Москва - столица России - Элементарное высказывание.

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

Пример обозначения логических высказываний.

А – высказывание «В четверг был дождь»,

В – высказывание «В пятницу было солнечно», то составное высказывание «В четверг был дождь, а в пятницу было солнечно», можно записать в виде:

А и В.

Здесь А, В – логические высказывания (могут быть либо истинными, либо ложными), и – логическая связка.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение (см. Таблицу 2): Таблица 2. Логические связки

№	Логическая связка	Название	Обозна-чение	Высказы-вание	Математическая запись
	и	конъюнкция логическое умножение	Ù, & *, And	A и В	A Ù B, A & B A * B, A And B
	или	дизъюнкция логическое сложение	Ú +, Or	A или В	A Ú B A + B, A Or B
	не	инверсия, логическое отрицание	, , Not	не А	А, , Not A
	Если…то	импликация, логическое следование	→, Þ	Если A, то В	A → B A Þ B
	тогда и только тогда	эквивалентность, равносильность, логическое тождество	«, º Û, ~	А тогда и только тогда, когда В	А«В, АºВ АÛВ, А~В

Импликацию можно выразить через дизъюнкцию и отрицание:

Эквивалентность можно выразить через отрицание, дизъюнкцию и конъюнкцию:

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

Таблица 3. Таблица истинности

При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету:

1. действия в скобках
2. инверсия (отрицание);
3. конъюнкция (умножение);
4. дизъюнкция (сложение):
5. импликация (следование)
6. эквивалентность (равносильность).