Разные интерпретации одного и того же двоичного числа.

⇐ ПредыдущаяСтр 2 из 3Следующая ⇒

Для примера возьмём число 0b10010101. Если это число рассматривать как беззнаковое целое, то оно равно 149. Если же это число определено как знаковое целое, то оно равно – 107.
Булева алгебра.

Булева алгебра логики - это алгебра, состоящая из нулей и единиц; или истины (TRUE)и лжи (False). В программировании булева алгебра логики встречается очень часто. Например, при создании различных управляющих структур (if, while, for ).

В булевой алгебре определены понятия логических операций, таких как «И». «ИЛИ», «НЕ» и т.д. К примеру, выражение «Стол имеет 4 ножки и стоит на полу» будет правдой, если выполняются оба условия, если же у стола отличное от 4-х количество ножек и/или он установлен не на пол, то выражение ложно. Т.е. если не выполнено одно из условий, то выражение ложно, если выполнены оба, то - правда. Если же в выражении «Стол имеет 4 ножки и стоит на полу» «И» заменить на «ИЛИ», то выражение станет ложью, только если стол одновременно не стоит на полу и у него не 4 ножки. Операция с использованием «И» называется конъюнкция, а с использованием «ИЛИ» - дизъюнкция. Рассмотрим их подробнее.

Конъюнкция

В программировании конъюнкция обозначается обычно как '& & ' или как «AND», и читается как 'И'. Таблица истинности для конъюнкции представлена в таблице 3.

		Таблица 3
		В
	AND	FALSE	TRUE
А	FALSE	FALSE	FALSE
TRUE	FALSE	TRUE

Где А и В – выражения, принимающие значения правда или ложь (TRUE и FALSE соответственно).

Операция конъюнкции ещё называется операцией логического умножения. Это видно, если FALSE заменить на 0, а TRUE на 1. (см. таблицу 4).

		Таблица 4
		В
	AND
А

Дизъюнкция

В программировании дизъюнкция обозначается обычно как '||' или «OR», читается как 'ИЛИ'. Вот таблица истинности для дизъюнкции:

		Таблица 4
		В
	OR	FALSE	TRUE
А	FALSE	FALSE	TRUE
TRUE	TRUE	TRUE

Дизъюнкция также называется логическим сложением.

С тем условием, что 1 AND 1 = 1.

Таблица истинности для дизъюнкции в случае замены FALSE на 0, а TRUE на 1 представлена в таблице 5.

		Таблица 5
		В
	OR
А

Равносильность

Обозначается обычно как '==' (двойной знак равно) (см. таблицу 6). Вот его таблица истинности:

		Таблица 6
		В
	==	FALSE	TRUE
А	FALSE	TRUE	FALSE
TRUE	FALSE	TRUE

Если два значения равны, то условие верно, если не равны, то ложно.

Отрицание

Отрицание является унарной операцией, т.е. выполняется с одним операндом. Обозначается как знак '! '. Таблица истинности представлена в таблице 7:

Таблица 7
А	А!
FALSE	TRUE
TRUE	FALSE

Читается как 'НЕ'. Т.е. (! TRUE = FALSE)

Сложение по модулю 2

Последней важной функцией является сложение по модулю 2. Ещё эта функция называется «исключающее ИЛИ». Обычно эта операция обозначается как «^» или «XOR». Её таблица истинности представлена в таблице 8

		Таблица 8
		В
	XOR	FALSE	TRUE
А	FALSE	FALSE	TRUE
TRUE	TRUE	FALSE

Таблица истинности в которой FALSE заменено на 0, а TRUE на 1, представлена в табл 9.

		Таблица 9
		В
	XOR
А

А как и следует из названия, эта операция представляет собой сложение по модулю 2. Т.е. 1+1=2. Если взять по модулю 2 (остаток от деления на 2), то выражение 1+1=0.

Различные обозначения булевых операций.

Название	Обозначение
Логическое И	AND, &
Побитное И	& &
Логическое ИЛИ	OR, \|
Побитное ИЛИ	\|\|
НЕ	!, NOT, ~,
Сложение по модулю 2	XOR, ^

Приоритет операций

Приоритет булевых операций определён следующим образом:

1. отрицание (! )

2. конъюнкция (И)

3. дизъюнкция (ИЛИ), сложение по модулю 2 (XOR)

Но надёжнее определять порядок выполнения операций с помощью скобок.

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

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

1. Закон двойного отрицания:
not not x = x

2. Закон коммутативности (от перестановки аргументов результат не меняется):
x₁ or x₂ = x₂ or x₁x₁ and x₂ = x₂ and x₁

3. Закон ассоциативности (порядка вычислений):
x₁ or (x₂ or x₃) = (x₁ or x₂) or x₃
x₁ and (x₂ and x₃) = (x₁ and x₂) and x₃

4. Закон дистрибутивности (раскрытия скобок):
x₁ or (x₂ and x₃) = (x₁ or x₂) and (x₁ or x₃)
x₁ and (x₂ or x₃) = (x₁ and x₂) or (x₁ and x₃)

5. Правила де Моргана:
not (x₁ or x₂) = not x₁ and not x₂
not (x₁ and x₂) = not x₁ or not x₂

6. Правила операций с константами 0 и 1:
not 0 = 1, not 1 = 0,
x or 0 = x, x or 1 = 1,
x and 1 = x, x and 0 = 0

7. Правила операций с переменной и её инверсией:
x or not x = 1
x and not x = 0

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

1. Закон поглощения:
x₁ or (x₁ and x₂) = x₁
x₁ and (x₁ or x₂) = x₁

2. Закон идемпотентности (повторное применение не даёт ничего нового):
x or x or... or x = x
x and x and... and x = x

3. На основании закона дистрибутивности, а также 7-го и 6-го законов:
x₁ or (not x₁ and x₂) = x₁ or x₂

Смещение двоичных чисел.

Если представить двоичное число как регистр смещения, то мы можем смещать имеющиеся там значения вправо или влево. При этом если сместить число влево на N разрядов, то его значение увеличится в 2^N раз. При смещении вправо на N разрядов, значение уменьшается в 2^N раз. Т.о. можно легко производить деление и умножение на числа, равные степени двойки. Здесь стоит помнить. Что все биты, выходящие при смещении за разрядность, будут потеряны.

Например, возьмём число 0b110011. Сместим его на 3 разряда вправо. 0b000110. И теперь обратно на 3 разряда влево: 0b110000.

Аналогично, если у вас разрядность числа ограничена 8 битами (1 байт), то при смещении влево могут быть потеряны старшие разряды. Например, возьмём тоже число 0b110011 и сместим его на 3 разряда влево. Получим 0b011000. Смещая обратно, получим: 0b000110. Как видите, в обоих случаях мы потеряли значащие биты.

Карты Карно.

⇐ Предыдущая 123 Следующая ⇒