Булевы операции очень близки (хотя и не тождественны) логическим связкам в классической логике. Бит можно рассматривать как логическое суждение — его значениями являются 1 «истина» и 0 «ложь». При такой интерпретации известные в логике связки конъюнкции, дизъюнкции, импликации, отрицания и другие имеют представление на языке битов. И наоборот, битовые операции легко описываются на языке исчисления высказываний.
Однако, связкам математической логики более соответствуют логические операции в т.ч. в программировании, нежели собственно битовые операции.
Булевы операции как основа цифровой техники
Перечисление битовых операций
«(Логическое) И» (and) — аналог конъюнкции в логике. Иногда называется логическим умножением.
В булевой логике:
В языке C: &
Выдаёт 1 если оба входа равны 1, в противном случае 0. Если один из аргументов равен 1, то результат «И» равен другому. Если один из аргументов равен 0, то результат «И» равен 0 независимо от значения другого аргумента.
«(Логическое) НЕ» (not), инвертирование — аналог отрицания в логике.
В булевой логике:
В языке C:
Данная унарная операция (с одним входом) заменяет 0 на 1 и наоборот. Реализующий её элемент называется инвертором.
«(Логическое) ИЛИ» (or) — аналог дизъюнкции в логике.
В булевой логике:
В языке C: |
Выдаёт 1 если и только если хотя бы один из входов равен 1. Операция, двойственная AND: при инвертировании выхода и всех входов (т.е. при замене 0 и 1 местами) «И» и «ИЛИ» взаимно превращается друг в друга.
Исключающее ИЛИ
«Исключающее ИЛИ» (xor), «сложение по модулю 2» — аналог исключающего ИЛИ в логике.
В булевой логике:
В языке C: ^
Если один из аргументов равен 0, то результат равен другому. Если один из аргументов равен 1, то результат равен отрицанию другого аргумента. Первое русское название операции обусловлено тем, что результат данной операции отличается от результата «ИЛИ» только в одном случае из 4 случаев входа — обоих 1 (случай одновременной истинности аргументов «исключается»). Ещё в русской грамматике значение данной логической связки передаётся союзом «либо».
Второе название — тем, что действительно является сложением в кольце вычетов по модулю 2, из чего следуют некоторые интересные свойства. Например, в отличие от вышеописанных «И» и «ИЛИ» данная операция является обратимой, или инволютивной: .
Операции от многих аргументов
Операции «И», «ИЛИ» и «исключающее ИЛИ» являются не только коммутативными, но и ассоциативными, и потому легко обобщаются на случай нескольких аргументов (входов).
Прочие бинарные операции
«ИЛИ-НЕ» (nor), она же «стрелка Пирса».
Стрелка Пирса является результатом инвертирования результата «ИЛИ» своих аргументов, выдаёт значение 1 только когда оба входа 0.
«И-НЕ» (nand), она же «штрих Шеффера».
В булевой логике:
Импликация («если-то») — аналог импликации в логике.
В булевой логике:
Совпадает с «ИЛИ» с инвертированным первым аргументом, выдаёт значение 0 только когда первый вход 1 а второй — 0. Данная операция не является коммутативной, в отличие от всех вышеописанных бинарных операций. Её можно понимать как арифметическое (меньше или равно).
Эквиваленция. Выдаёт 1 если и только если оба аргумента равны между собой. Является результатом инвертирования результата «исключающего ИЛИ» своих аргументов. Она же и двойственна исключающему «ИЛИ» в вышеописанном смысле.
Сводная таблица истинности булевых операций
Название
И/AND
НЕ/NOT
ИЛИ/OR
искл. ИЛИ/XOR
импл.
стрелка Пирса
штрих Шеффера
x
y
& ()
x ()
| ()
^ ()
()
0
0
0
1
0
0
1
1
1
0
1
0
1
1
1
1
0
1
1
0
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
0
Операции над битовыми векторами
Обобщение операций на булеву алгебру
Битовые сдвиги
К битовым операциям также относят битовые сдвиги. При сдвиге значения битов копируются в соседние по направлению сдвига. Различают несколько видов сдвигов — логический, арифметический и циклический, в зависимости от обработки крайних битов.
Также различают сдвиг влево (в направлении от младшего бита к старшему) и вправо (в направлении от старшего бита к младшему).
Арифметический сдвиг (правый)
Циклический сдвиг через перенос
Логический сдвиг
При логическом сдвиге значение последнего бита по направлению сдвига теряется (копируясь в бит переноса), а первый приобретает нулевое значение.
Логические сдвиги влево и вправо используются для быстрого умножения и деления на 2, соответственно.
Арифметический сдвиг
Арифметический сдвиг аналогичен логическому, но значение слова считается знаковым числом представленному дополнительным кодом. Так при правом сдвиге старший бит сохраняет свое значение. Левый арифметический сдвиг идентичен логическому.
Циклический сдвиг
При циклическом сдвиге, значение последнего бита по направлению сдвига копируется в первый бит (и копируется в бит переноса).
Также различают циклический сдвиг через бит переноса — при нем первый бит по направлению сдвига получает значение из бита переноса, а значение последнего бита сдвигается в бит переноса.
2-адическая интерпретация
Целое число, записанное (в дополнительном коде) в бесконечный (в сторону положительных степеней двойки) двоичный регистр является естественным объектом для теории p-адических чисел при . Множество целых 2-адических чисел (т.е. произвольных бесконечных битовых последовательностей) может быть рассмотрено как булева алгебра точно так же как и множество значений битового регистра конечной длины. Все вышеперечисленные битовые операции оказываются непрерывными отображениями. Хотя практическое программирование не располагает регистрами бесконечной длины, это не мешает использовать данный теоретический факт в криптографии для создания быстродействующих алгоритмов шифрования.
Практические применения
Физическая реализация битовых операций
В квантовых вычислениях из перечисленных булевых операций реализуются только НЕ и искл. ИЛИ (с некоторыми оговорками). Квантовых аналогов И, ИЛИ и т.д. не существует.
Схемы аппаратной логики
Результат операции ИЛИ-НЕ или ИЛИ ото всех битов двоичного регистра проверяет, равно ли значение регистра нулю; то же самое взятое от выхода искл. ИЛИ двух регистров проверяет равенство их значений между собой.
Использование в программировании
Регистровая операция И используется для сброса конкретного бита, ИЛИ — для установки, искл. ИЛИ — для инвертирования (т.е. для проведения операции НЕ над конкретным битом с сохранением остальных нетронутыми). Регистровый И с последующей проверкой равенства нулю используется для чтения значения конкретного бита.
Операция И также используется для наложения маски — например, в IP-адресации (хотя не только).
Программирование в значительной степени связано с доказуемостью, с выводимостью. Мы должны иметь возможность понимать совсем не простое, проходящее через множество ветвлений поведение программ во время их выполнения. Человек физически не в состоянии проследить за мириадами базисных операций, выполняемых компьютером.
В принципе, все может быть выведено из текста программы простыми рассуждениями. Если бы существовала наука выводимости, она оказала бы нам существенную помощь.
Логика – математическая логика, если быть более точным, – самостоятельная наука, таковой является и ее ветвь «Логика в информатике «, которой посвящены многие учебники и отдельные курсы. Я надеюсь, что такой курс вами уже пройден или будет пройден. Эта лекция вводит основные понятия логики, необходимые в программировании. Хотя логика пользуется заслуженной славой как наука о выводимости, нам она нужна для более ограниченных целей – для понимания той части выводимости, которая базируется на условиях. Логика даст нам прочную основу для выражения и понимания условий, появляющихся в контрактах и в операторах программы.
Существуют ровно две булевские константы (boolean constants), также называемые «булевскими или истинностными значениями «, которые будем записывать в виде True и False для совместимости с нашим языком программирования, хотя логики часто пишут просто T и F, а электротехники предпочитают обозначать их как 1 и 0.
В языке программирования булевские операции, подобно булевским константам, задаются ключевыми словами. В математических текстах знаки операций обычно задаются отдельными символами, не все из которых присутствуют на клавиатуре компьютера. Приведем соответствие между ключевыми словами и общеупотребительными символами в математике:
Ключевое слово Eiffel
Общеупотребительные математические символы
not
¬ или
or
∨ или |
and
∧ или &
=
↔ или =
implies
=>
В Eiffel булевские константы, переменные и выражения имеют тип BOOLEAN, определенный классом, подобно всем типам. Класс BOOLEAN является библиотечным классом, доступным для просмотра в EiffelStudio; там вы можете увидеть все булевские операции, обсуждаемые в этой лекции.
Отрицание
Операция not задает отрицание – замену булевского значения его противоположностью, где True и False противоположны друг другу.
Из таблицы истинности следуют важные свойства этой операции.
Теоремы: «Свойства отрицания»
Дизъюнкция
a
b
a or b
True
True
True
True
False
True
False
True
True
False
False
False
Слово » or » заимствовано из естественного языка в его неисключительном смысле, как в предложении «Тот, кто придумал эту инструкцию, глуп или слеп», что не исключает, что оба случая могут иметь место.
Создавая объект в сцене, необходимо учитывать особенности его геометрии. Несмотря на то что один и тот же трехмерный объект всегда можно смоделировать несколькими способами, как правило, существует один, который является наиболее быстрым и удобным.
Опытный аниматор с первого взгляда на эскиз будущей модели определяет способ моделирования объекта, однако начинающему пользователю это не всегда под силу.
Одним из наиболее удобных и быстрых способов моделирования является создание трехмерных объектов при помощи булевых операций.
Например, если два объекта пересекаются, на их основе можно создать третий объект, который будет представлять собой результат сложения, вычитания или пересечения исходных объектов.
Модели, создаваемые в трехмерной графике, можно условно разделить на две группы — органические и неорганические. К первой категории относятся объекты живой природы, такие как растения, животные, люди, ко второй — элементы архитектуры, а также предметы, созданные человеком (автомобили, техника и др.).
Разница подходов к моделированию объектов первой и второй группы столь велика, что в зависимости от конкретных задач для реализации проекта могут использоваться различные пакеты для работы с трехмерной графикой.
Поскольку в 3ds max основной акцент делается на моделирование неорганических объектов, то есть архитектурную визуализацию и разработку компьютерных игр, то булевыe операции — это незаменимый инструмент для каждого пользователя 3ds max.
С другой стороны, они совсем не подходят для создания большинства органических объектов. Например, смоделировать лицо человека при помощи булевых операций практически невозможно.
Рассмотрим булевыe операции. На рис. 3.51 представлено исходное изображение. В 3ds max 7 доступны четыре типа булевых операций.
Рис. 3.51. Расположение объектов перед выполнением булевых операций
Рис. 3.52. Объекты после выполнения булевой операции Union (Сложение)
Рис. 3.53. Объекты после выполнения булевой операции Intersection (Пересечение)
Рис. 3.54. Объекты после выполнения булевой операции Subtraction (Исключение)
Рис. 3.55. Объекты после выполнения булевой операции Cut (Вычитание)
Булевы операции выполняются следующим образом.
1. Выделите первый объект, который будет участвовать в образовании конечной модели.
2. Перейдите на вкладку Create (Создание) командной панели, выберите в категории Geometry (Геометрия) строку Compound Objects (Составные объекты) и нажмите кнопку Boolean (Булева операция) (рис. 3.56).
3. Установите параметры булевой операции.
4. Воспользуйтесь кнопкой Pick Operand В (Выбрать операнд), чтобы выбрать второй объект, который будет участвовать в операции.
Рис. 3.56. Настройки объекта Boolean (Булева операция)
Моделирование с использованием булевых операций подробно рассмотрено в разд. «Урок 6. Моделирование винта».
Битовые операции, иногда также булевы или логические операции [1] — операции над битами, применяемые в программировании и цифровой технике, изучаемые в дискретной математике и математической логике.
Содержание
Введение
Булевы операции и математическая логика
Булевы операции очень близки (хотя и не тождественны) логическим связкам в классической логике. Бит можно рассматривать как логическое суждение — его значениями являются 1 «истина» и 0 «ложь». При такой интерпретации известные в логике связки конъюнкции, дизъюнкции, импликации, отрицания и другие имеют представление на языке битов. И наоборот, битовые операции легко описываются на языке исчисления высказываний.
Однако, связкам математической логики более соответствуют логические операции в т.ч. в программировании, нежели собственно битовые операции.
Булевы операции как основа цифровой техники
Булевы операции лежат в основе обработки цифровых сигналов. А именно, посредством них мы можем из одного или нескольких сигналов на входе получить новый сигнал, который в свою очередь может быть подан на вход одной или нескольким таким операциям. По сути, именно булевы операции в сочетании с запоминающими элементами (напр. триггерами) реализуют всё богатство возможностей современной цифровой техники.
Список битовых операций
«(Логическое) И» (and) — аналог конъюнкции в логике. Иногда называется логическим умножением.
В булевой логике:
В языке C: &
Выдаёт 1 если оба входа равны 1, в противном случае 0. Если один из аргументов равен 1, то результат «И» равен другому. Если один из аргументов равен 0, то результат «И» равен 0 независимо от значения другого аргумента.
«(Логическое) НЕ» (not), инвертирование — аналог отрицания в логике.
В булевой логике:
В языке C:
Данная унарная операция (с одним входом) заменяет 0 на 1 и наоборот. Реализующий её элемент называется инвертором.
«(Логическое) ИЛИ» (or) — аналог дизъюнкции в логике.
В булевой логике:
В языке C: |
Выдаёт 1 если и только если хотя бы один из входов равен 1. Операция, двойственная AND: при инвертировании выхода и всех входов (т.е. при замене 0 и 1 местами) «И» и «ИЛИ» взаимно превращается друг в друга.
Исключающее ИЛИ
«Исключающее ИЛИ» (xor), «сложение по модулю 2» — аналог исключающего ИЛИ в логике.
В булевой логике:
В языке C: ^
Если один из аргументов равен 0, то результат равен другому. Если один из аргументов равен 1, то результат равен отрицанию другого аргумента. Первое русское название операции обусловлено тем, что результат данной операции отличается от результата «ИЛИ» только в одном случае из 4 случаев входа — обоих 1 (случай одновременной истинности аргументов «исключается»). Ещё в русской грамматике значение данной логической связки передаётся союзом «либо».
Второе название — тем, что действительно является сложением в кольце вычетов по модулю 2, из чего следуют некоторые интересные свойства. Например, в отличие от вышеописанных «И» и «ИЛИ» данная операция является обратимой, или инволютивной: .
В графике «исключающее ИЛИ» применяется при выводе спрайтов на картинку — повторное её применение убирает спрайт с картинки. Благодаря инволютивности же эта операция нашла применение в криптографии как простейшая реализация идеального шифра (шифра Вернама). «Исключающее ИЛИ» также может использоваться для обмена двух переменных, используя алгоритм обмена при помощи исключающего ИЛИ.
Операции от многих аргументов
Операции «И», «ИЛИ» и «исключающее ИЛИ» являются не только коммутативными, но и ассоциативными, и потому легко обобщаются на случай нескольких аргументов (входов).
Прочие бинарные операции
В булевой логике:
Стрелка Пирса является результатом инвертирования результата «ИЛИ» своих аргументов, выдаёт значение 1 только когда оба входа 0.
«И-НЕ» (nand), или «штрих Шеффера».
В булевой логике:
Двойственная стрелке Пирса операция: является результатом инвертирования результата «И» своих аргументов, выдаёт значение 0 только когда оба входа 1. Известна простотой реализации в ТТЛ.
Импликация («если-то») — аналог импликации в логике.
В булевой логике:
Совпадает с «ИЛИ» с инвертированным первым аргументом, выдаёт значение 0 только когда первый вход 1 а второй — 0. Данная операция не является коммутативной, в отличие от всех вышеописанных бинарных операций. Её можно понимать как арифметическое (меньше или равно).
Эквиваленция. Выдаёт 1 если и только если оба аргумента равны между собой. Является результатом инвертирования результата «исключающего ИЛИ» своих аргументов. Она же и двойственна исключающему «ИЛИ» в вышеописанном смысле.
Сводная таблица истинности булевых операций
Название→ Аргументы
И (AND)
НЕ (NOT)
ИЛИ (OR)
искл. ИЛИ(XOR)
импликация
стрелка Пирса
штрих Шеффера
x
y
() (x&y)
() (
x)
() (x|y)
() (x^y)
() ((
x)|y)
((
y))
(
(x&y))
0
0
0
1
0
0
1
1
1
0
1
0
1
1
1
1
0
1
1
0
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
0
Операции над битовыми векторами
Обобщение операций на булеву алгебру
Тем не менее, ничто не мешает рассматривать эти регистры именно как битовые векторы и проводить булевые операции покомпонентно (бит номер k значения есть результат операция от битов номер k аргументов). Кстати, математически говоря, булевы операции распространяются таким образом на произвольную булеву алгебру. Таким образом мы получаем операции побитового И, ИЛИ, НЕ, искл. ИЛИ и т. д. Как арифметические, данные операции не обладают хорошими свойствами за исключением побитового НЕ, которое для чисел в дополнительном коде совпадает с вычитанием из −1 (
Битовые сдвиги
К битовым операциям также относят битовые сдвиги. При сдвиге значения битов копируются в соседние по направлению сдвига. Различают несколько видов сдвигов — логический, арифметический и циклический, в зависимости от обработки крайних битов.
Также различают сдвиг влево (в направлении от младшего бита к старшему) и вправо (в направлении от старшего бита к младшему).
Логический сдвиг
При логическом сдвиге значение последнего бита по направлению сдвига теряется (копируясь в бит переноса), а первый приобретает нулевое значение.
Логические сдвиги влево и вправо используются для быстрого умножения и деления на 2, соответственно.
Арифметический сдвиг
Арифметический сдвиг аналогичен логическому, но значение слова считается знаковым числом представленному дополнительным кодом. Так при правом сдвиге старший бит сохраняет свое значение. Левый арифметический сдвиг идентичен логическому.
Циклический сдвиг
При циклическом сдвиге, значение последнего бита по направлению сдвига копируется в первый бит (и копируется в бит переноса).
Также различают циклический сдвиг через бит переноса — при нем первый бит по направлению сдвига получает значение из бита переноса, а значение последнего бита сдвигается в бит переноса.
2-адическая интерпретация
Практические применения
Физическая реализация битовых операций
Реализация битовых операций может в принципе быть любой: механической, электромеханической, гидравлической, пневматической, оптической и даже химической.
В первой половине XX века вместо транзисторов применяли электромеханические реле и электронные лампы.
В пожароопасных и взрывоопасных условиях до сих пор применяют пневматические логические устройства (пневмоника).
В квантовых вычислениях из перечисленных булевых операций реализуются только НЕ и искл. ИЛИ (с некоторыми оговорками). Квантовых аналогов И, ИЛИ и т.д. не существует.
Схемы аппаратной логики
Результат операции ИЛИ-НЕ или ИЛИ ото всех битов двоичного регистра проверяет, равно ли значение регистра нулю; то же самое взятое от выхода искл. ИЛИ двух регистров проверяет равенство их значений между собой.
Битовые операции применяются в знакогенераторах и графических адаптерах; особенно велика была их роль в адаптере графический ускоритель.
Использование в программировании
Благодаря реализации в арифметическом логическом устройстве (АЛУ) процессора многие их регистровые битовые операции аппаратно доступны в языках низкого уровня. В большинстве процессоров реализованы в качестве инструкции регистровый НЕ; регистровые двухаргументные И, ИЛИ, исключающее ИЛИ; проверка равенства нулю (см. выше); три типа битовых сдвигов, а также циклические битовые сдвиги.
Регистровая операция И используется для сброса конкретных битов по битовой маске, ИЛИ — для установки, исключающее ИЛИ — для инвертирования битов регистра по маске.
Так, например, в сетевых интернет-технологиях операция И между значением IP-адреса и значением маски подсети используется для определения принадлежности данного адреса к подсети.
См. также
Примечания
Полезное
Смотреть что такое «Булевы операции» в других словарях:
Битовые операции — Не следует путать с булевой функцией. Битовая операция в программировании некоторые операции над цепочками битов. В программировании, как правило, рассматриваются лишь некоторые виды этих операций: логические побитовые операции и… … Википедия
ЛОГИЧЕСКИЕ ОПЕРАЦИИ — логич. операторы, логич. связки, функции, преобразующие выражения логич. исчислений (формальных логич. систем); подразделяются на пропозициональные (сен тенциональные) связки, с помощью которых образуются выражения логики высказываний, и… … Философская энциклопедия
Битовая операция — Битовые операции, иногда также булевы или логические операции[1] операции над битами, применяемые в программировании и цифровой технике, изучаемые в дискретной математике и математической логике. Содержание 1 Введение 1.1 … Википедия
Инвертор (логический элемент) — Битовые операции, иногда также булевы или логические операции[1] операции над битами, применяемые в программировании и цифровой технике, изучаемые в дискретной математике и математической логике. Содержание 1 Введение 1.1 … Википедия
Булева алгебра — Эта статья об алгебраической системе. О разделе математической логики, изучающем высказывания и операции над ними, см. Алгебра логики. Булевой алгеброй[1][2][3] называется непустое множество A с двумя бинарными операциями (аналог конъюнкции),… … Википедия
IARP — International Aging Research Portfolio URL … Википедия
БУЛЕВА АЛГЕБРА — булева решетк а, частично упорядоченное множество специального вида. Б. а. наз. дистрибутивная решетка (дистрибутивная структура), имеющая наибольший элемент 1 единицу Б. а., наименьший элемент 0 нуль Б. а. и содержащая вместе с каждым своим… … Математическая энциклопедия
Матрица достижимости — простого ориентированого графа бинарная матрица замыкания по транзитивности отношения (оно задаётся матрицей смежности графа). Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.… … Википедия
Векторная графика — Пример, показывающий разницу между векторной, фрактальной и растровой графикой при увеличении. a: исходное векторное изображение; b: иллюстрация, увеличенная в 8 раз как векторное изображение; c: иллюст … Википедия
.
(меньше или равно).
) 
) 
) 
) 
(
) 
