Исключающее «или»

Таблицы истинности для основных двоичных логических функций

В программировании:

• Конъюнкция = AND = И = ∧{\displaystyle \land } = &
• Дизъюнкция = OR = ИЛИ = ∨{\displaystyle \lor } = |
• Сложение по модулю 2 = XOR = ИСКЛЮЧАЮЩЕЕ ИЛИ = ⊕{\displaystyle \oplus } = ~
• Отрицание = NOT = НЕ = ¬{\displaystyle \neg } = !

Практические применения

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

1. увеличение размера регистров, в которых битовые операции выполняются не по одной, а сразу на множестве 8, 16, 32, 64 битах
2. экспериментальные устройства, где обобщают битовые операции с двоичной системы, на троичные и прочие системы счисления (так например, разработана теория работы с четверичной системой (ДНК-компьютер), так же делаются исследования в области квантового компьютера).

Физическая реализация битовых операций

Реализация битовых операций может в принципе быть любой: механической (в том числе гидравлической и пневматической), химической, тепловой, электрической, магнитной и электромагнитной (диапазоны — ИК, видимый оптический, УФ и далее по убыванию длин волн), а также в виде комбинаций, например, электромеханической.

В первой половине XX века до изобретения транзисторов применяли электромеханические реле и электронные лампы.

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

Наиболее распространены электронные реализации битовых операций при помощи транзисторов, например резисторно-транзисторная логика (РТЛ), диодно-транзисторная логика (ДТЛ), эмиттерно-связанная логика (ЭСЛ), транзисторно-транзисторная логика (ТТЛ), N-МОП-логика, КМОП-логика и др.

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

Схемы аппаратной логики

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

Битовые операции применяются в знакогенераторах и графических адаптерах; особенно велика была их роль в адаптере EGA в режимах с 16 цветами — хитроумное сочетание аппаратной логики адаптера с логическими командами центрального процессора позволяет рассматривать EGA как первый в истории графический ускоритель.

Использование в программировании

Благодаря реализации в арифметическом логическом устройстве (АЛУ) процессора многие регистровые битовые операции аппаратно доступны в языках низкого уровня. В большинстве процессоров реализованы в качестве инструкции регистровый НЕ; регистровые двухаргументные И, ИЛИ, исключающее ИЛИ; проверка равенства нулю (см. выше); три типа битовых сдвигов, а также циклические битовые сдвиги.

Регистровая операция И используется для:

• проверки бита на 0 или 1
• установки 0 в указанный бит (сброса бита)

Регистровая операция ИЛИ используется для:

установки 1 в указанный бит

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

Сдвиг влево/вправо используется для умножения/целочисленного деления на 2 и выделения отдельных битов.

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

Булева логика

В булевой логике импликация — это функция двух переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества {,1}{\displaystyle \{0,1\}}. Результат также принадлежит множеству {,1}{\displaystyle \{0,1\}}. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений ,1{\displaystyle 0,1} может использоваться любая другая пара подходящих символов, например false,true{\displaystyle \operatorname {false} ,\operatorname {true} } или F,T{\displaystyle F,T} или «ложь», «истина».

Правило:

Импликация как булева функция ложна лишь тогда, когда посылка истинна, а следствие ложно. Иными словами, импликация A→B{\displaystyle A\to B} это сокращённая запись для выражения ¬A∨B{\displaystyle \neg A\lor B}.

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

прямая импликация
(от a к b) (материальная импликация (англ.)русск., материальный кондиционал (англ.)русск.)

a{\displaystyle a}	b{\displaystyle b}	a→b,a⩽b{\displaystyle a\to b,a\leqslant b}
{\displaystyle 0}	{\displaystyle 0}	1{\displaystyle 1}
{\displaystyle 0}	1{\displaystyle 1}	1{\displaystyle 1}
1{\displaystyle 1}	{\displaystyle 0}	{\displaystyle 0}
1{\displaystyle 1}	1{\displaystyle 1}	1{\displaystyle 1}

• если первый операнд не больше второго операнда, то 1,
• если a⩽b{\displaystyle a\leqslant b}, то истинно (1).

«Житейский» смысл импликации.
Для более лёгкого понимания смысла прямой импликации и запоминания её таблицы истинности может пригодиться житейская модель:

А — начальник. Он может приказать «работай» (1) или сказать «делай что хочешь» (0).

В — подчинённый. Он может работать (1) или бездельничать (0).

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

обратная импликация (от b к a, A∨(¬B){\displaystyle A\lor (\neg B)})

a{\displaystyle a}	b{\displaystyle b}	a←b,a⩾b{\displaystyle a\leftarrow b,a\geqslant b}
{\displaystyle 0}	{\displaystyle 0}	1{\displaystyle 1}
{\displaystyle 0}	1{\displaystyle 1}	{\displaystyle 0}
1{\displaystyle 1}	{\displaystyle 0}	1{\displaystyle 1}
1{\displaystyle 1}	1{\displaystyle 1}	1{\displaystyle 1}

• если первый операнд не меньше второго операнда, то 1,
• если a⩾b{\displaystyle a\geqslant b}, то истинно (1).

Обратная импликация — отрицание (негация, инверсия) обнаружения увеличения (перехода от 0 к 1, инкремента).

отрицание (инверсия, негация) прямой импликации

a{\displaystyle a}	b{\displaystyle b}	¬(a→b),a>b{\displaystyle \lnot (a\to b),a>b}
{\displaystyle 0}	{\displaystyle 0}	{\displaystyle 0}
{\displaystyle 0}	1{\displaystyle 1}	{\displaystyle 0}
1{\displaystyle 1}	{\displaystyle 0}	1{\displaystyle 1}
1{\displaystyle 1}	1{\displaystyle 1}	{\displaystyle 0}

• если первый операнд больше второго операнда, то 1,
• если a>b{\displaystyle a>b}, то истинно (1).

отрицание (инверсия, негация) обратной импликации (¬A∧B{\displaystyle \lnot A\land B}),
разряд займа в .

a{\displaystyle a}	b{\displaystyle b}	¬(a←b),a<b{\displaystyle \lnot (a\leftarrow b),a<b}
{\displaystyle 0}	{\displaystyle 0}	{\displaystyle 0}
{\displaystyle 0}	1{\displaystyle 1}	1{\displaystyle 1}
1{\displaystyle 1}	{\displaystyle 0}	{\displaystyle 0}
1{\displaystyle 1}	1{\displaystyle 1}	{\displaystyle 0}

• если первый операнд меньше второго операнда, то 1,
• если a<b{\displaystyle a<b}, то истинно (1).

Другими словами, две импликации (прямая и обратная) и две их инверсии — это четыре оператора отношений. Результат операций зависит от перемены мест операндов.

Логические операторы в VBA Excel

Оператор «Not»

«Not» – это оператор логического отрицания (инверсия), который возвращает True, если условие является ложным, и, наоборот, возвращает False, если условие является истинным.

Синтаксис:

Таблица значений:

Оператор «And»

«And» – это оператор логического умножения (логическое И, конъюнкция), который возвращает значение True, если оба условия являются истинными.

Синтаксис:

Таблица значений:

Оператор «Or»

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

Синтаксис:

Таблица значений:

Оператор «Xor»

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

Синтаксис:

Таблица значений:

Оператор «Eqv»

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

Синтаксис:

Таблица значений:

Оператор «Imp»

«Imp» – это оператор логической импликации, который возвращает значение False, если первое (левое) условие является истинным, а второе (правое) условие является ложным, в остальных случаях возвращает True.

Синтаксис:

Таблица значений:

SHA-2 и SHA-256

SHA-2 — это семейство алгоритмов с общей идеей хеширования данных. SHA-256 устанавливает дополнительные константы, которые определяют поведение алгоритма SHA-2. Одной из таких констант является размер вывода. «256» и «512» относятся к соответствующим размерам выходных данных в битах.

Мы рассмотрим пример работы SHA-256.

SHA-256 «hello world». Шаг 1. Предварительная обработка

1. Преобразуем «hello world» в двоичный вид:

2. Добавим одну единицу:

3. Заполняем нулями до тех пор, пока данные не станут кратны 512 без последних 64 бит (в нашем случае 448 бит):

4. Добавим 64 бита в конец, где 64 бита — целое число с порядком байтов big-endian, обозначающее длину входных данных в двоичном виде. В нашем случае 88, в двоичном виде — «1011000».

Теперь у нас есть ввод, который всегда будет без остатка делиться на 512.

Шаг 2. Инициализация значений хеша (h)

Создадим 8 значений хеша. Это константы, представляющие первые 32 бита дробных частей квадратных корней первых 8 простых чисел: 2, 3, 5, 7, 11, 13, 17, 19.

Шаг 3. Инициализация округлённых констант (k)

Создадим ещё немного констант, на этот раз их 64. Каждое значение — это первые 32 бита дробных частей кубических корней первых 64 простых чисел (2–311).

Шаг 4. Основной цикл

Следующие шаги будут выполняться для каждого 512-битного «куска» входных данных. Наша тестовая фраза «hello world» довольно короткая, поэтому «кусок» всего один. На каждой итерации цикла мы будем изменять значения хеш-функций –, чтобы получить окончательный результат.

Шаг 5. Создаём очередь сообщений (w)

1. Копируем входные данные из шага 1 в новый массив, где каждая запись является 32-битным словом:

2. Добавляем ещё 48 слов, инициализированных нулями, чтобы получить массив :

3. Изменяем нулевые индексы в конце массива, используя следующий алгоритм:

• For from :

Давайте посмотрим, как это работает для :

Это оставляет нам 64 слова в нашей очереди сообщений ():

Шаг 6. Цикл сжатия

1. Инициализируем переменные и установим их равными текущим значениям хеша соответственно. .
2. Запустим цикл сжатия, который будет изменять значения a…h . Цикл выглядит следующим образом:

Давайте пройдём первую итерацию. Сложение рассчитывается по модулю 2^32:

Все расчёты выполняются ещё 63 раза, изменяя переменные …. В итоге мы должны получить следующее:

Шаг 7. Изменяем окончательные значения

После цикла сжатия, но ещё внутри основного цикла, мы модифицируем значения хеша, добавляя к ним соответствующие переменные …. Как обычно, всё сложение происходит по модулю 2^32.

Шаг 8. Получаем финальный хеш

И последний важный шаг — собираем всё вместе.

Готово! Мы выполнили каждый шаг SHA-2 (SHA-256) (без некоторых итераций).

Булевы типы

Результатом логического выражения всегда является булево (логическое) значение. Булев тип данных (boolean) может принимать только два значения (true или false). Эти величины упорядочены следующим образом: false < true. Это значит, что данные булевого типа являются не только результатом операций отношения, но и могут выступать в роли операндов операции отношения. Также к ним можно применять функции ord, succ, pred, процедуры inc и dec.

Значение типа boolean занимает в памяти 1 байт.

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

var 
bboolean; 
wbwordbool; 
begin 
b= false; 
b= pred(b); 
writeln(b,' ',ord(b)); // TRUE 255 
writeln(b=true); // TRUE 
 
wb= false; 
wb= pred(wb); 
writeln(wb,' ',ord(wb)); // TRUE -1 
 
b= true; 
b= succ(b); 
writeln(b,' ',ord(b)); // TRUE 2 
 
wb= true; 
wb= succ(wb); 
writeln(wb,' ',ord(wb)); // FALSE 0 
end.

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

С помощью логических операторов можно формировать сложные логические выражения. Логические операторы часто применяются по отношению к простым логическим выражениям.

В языке программирования Pascal предусмотрены следующие логические операции:

true xor true = false
true xor false = true
false xor true = true
false xor false = false

• Конъюнкция (логическое умножение, пересечение) — and. Выражение a and b дает значение true только в том случае, если a и b имеют значение true. Во всех остальных случаях значения выражения a and b дает false.

  true and true = true
  true and false = false
  false and true = false
  false and false = false

• Дизъюнкция (логическое сложение, объединение) – or. Выражение a or b дает значение false только в том случае, если a и b имеют значение false. Во всех остальных случаях результат – true.

  true or true = true
  true or false = true
  false or true = true
  false or false = false

• Отрицание (инверсия) – not. Выражение not a имеет значение, противоположное значению a.

  not true = false
  not false = true

• Исключающее ИЛИ – xor. Выражение a xor b дает значение true только в том случае, когда только один из операндов имеет значение true.

Последовательность выполнения логических операторов: not, and, or.

В языке Паскаль сначала выполняются логические операторы (and, or, xor, not), а уже потом операторы отношений (>, >=, <, <=, <>, =), поэтому не нужно забывать расставлять скобки в сложных логических выражениях.

Сложные булевы выражения могут не обрабатываться до конца, если продолжение вычислений не изменит результат. Если булево выражение в обязательном порядке нужно обрабатывать до конца, то это обеспечивается включением директивы компиляции {B+}.

Стандартные булевские функции

• odd(x) = true, если x нечетный (x целый тип);
• eoln(x) = true, если встретился конец строки текстового файла x;
• eof(x) = true, если встретился конец файла x.

В остальных случаях эти функции принимают значение false.

Что!? Разве операторы > используются не для вывода и ввода данных?

И для этого тоже.

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

#include <iostream>

int main()
{
unsigned int x = 4;
x = x << 1; // оператор << используется для побитового сдвига влево
std::cout << x; // оператор << используется для вывода данных в консоль

return 0;
}

Результат выполнения программы:

А как компилятор понимает, когда нужно применить оператор побитового сдвига влево, а когда выводить данные? Всё очень просто. переопределяет значение оператора по умолчанию на новое (вывод данных в консоль). Когда компилятор видит, что левым операндом оператора является std::cout, то он понимает, что должен произойти вывод данных. Если левым операндом является переменная целочисленного типа данных, то компилятор понимает, что должен произойти побитовый сдвиг влево (операция по умолчанию).