Часто, для того чтобы продемонстрировать ограниченные возможности однослойных персептронов при решении задач прибегают к рассмотрению так называемой проблемы XOR – исключающего ИЛИ .

Суть задачи заключаются в следующем. Дана логическая функция XOR – исключающее ИЛИ. Это функция от двух аргументов, каждый из которых может быть нулем или единицей. Она принимает значение , когда один из аргументов равен единице, но не оба, иначе . Проблему можно проиллюстрировать с помощью однослойной однонейронной системы с двумя входами, показанной на рисунке ниже.

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

Один нейрон с двумя входами может сформировать решающую поверхность в виде произвольной прямой. Для того, чтобы сеть реализовала функцию XOR, заданную таблицей выше, нужно расположить прямую так, чтобы точки были с одной стороны прямой, а точки – с другой. Попытавшись нарисовать такую прямую на рисунке ниже, убеждаемся, что это невозможно. Это означает, что какие бы значения ни приписывались весам и порогу, однослойная нейронная сеть неспособна воспроизвести соотношение между входом и выходом, требуемое для представления функции XOR.

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

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

Тогда результат работы такой нейронной сети можно представить в виде следующей таблицы:

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

Нейронная сеть, используемая в этой статье для решения задачи XOR, примитивна и не использует всех возможностей многослойных сетей. Очевидно, что многослойные нейронные сети обладают большей представляющей мощностью, чем однослойные, только в случае присутствия нелинейности. А в данной сети применена пороговая линейная функция активации. Такую сеть нельзя будет обучить, например, применив алгоритм обратного распространения ошибки.

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

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

Логический оператор AND

Синтаксис:
Операнд_1 AND Операнд_2

Оператор AND выполняет логическую конъюнкцию .

Результатом данной операции является значение True, только когда оба операнда имеют значение True, иначе - False.

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

Оператор AND можно использовать для нескольких операндов:

(5 3) AND (5=6) результатом будет False

Независимо от количества операндов результатом логической операции AND будет True только в том случае, когда все операнды выражения будут иметь значение True. В любом другом случае результатом будет False. Обратите внимание, что операнды заключаются в круглые скобки. VBA сначала вычисляет значение каждого операнда внутри скобок, а затем уже все выражение полностью.

Логический оператор OR

Синтаксис:
Операнд_1 OR Операнд_2

Оператор OR выполняет логическую дизъюнкцию .

Результатом данной операции является значение True, если хотя бы один из операндов имеет значение True, иначе - False.

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

Оператор OR можно использовать для нескольких операндов:

(5 3) OR (5=6) результатом будет True

Независимо от количества операндов результатом логической операции OR будет всегда True в том случае, если хотя бы один из операндов выражения будет иметь значение True. Иначе результатом будет False.

Операторы AND и OR можно комбинировать:

((5 3)) OR (5=6) результатом будет True

Логический оператор NOT

Синтаксис:
NOT Операнд

Оператор NOT выполняет логическое отрицание .

Оператор NOT использует только один операнд.

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

Операторы AND OR NOT можно комбинировать:

((5 3)) OR NOT (5=6) результатом будет True

Логический оператор XOR

Синтаксис:
Операнд_1 XOR Операнд_2

Оператор XOR выполняет логическое исключение .

Результатом данной операции является значение True, если операнды имеют разные значения, иначе - False.

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

((5 3)) OR NOT (5=6) XOR (5=5) результатом будет False

Логический оператор EQV

Синтаксис:
Операнд_1 EQV Операнд_2

Оператор EQV - это оператор логической эквивалентности .

Результатом данной операции является значение True, если операнды имеют одинаковые значения, иначе - False.

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

((5 3)) OR NOT (5=6) EQV (5=5) результатом будет True

Логический оператор IMP

Синтаксис:
Операнд_1 IMP Операнд_2

Оператор IMP выполняет логическую операцию импликации .

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

((5 3)) OR NOT (5=6) IMP (5=5) результатом будет True

Логический оператор IMP наименее интуитивно понятный из всех логических операторов. К счастью, необходимость в его применении возникает довольно редко.

В этой статье мы поговорим о некоторых битовых операциях. Рассмотрим основные из них: XOR (исключающее ИЛИ), AND (И), NOT (НЕ) а также OR (ИЛИ).

Как известно, минимальной единицей измерения информации является бит , который хранит одно из 2-х значений: 0 (False , ложь) либо 1 (True , истина). Таким образом, битовая ячейка может одновременно находиться лишь в одном из двух возможных состояний.

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

Логическая операция AND (и)

AND обозначается знаком & .

Оператор AND выполняется с 2-мя битами, возьмём, к примеру, a и b. Результат выполнения операции AND равен 1, если a и b равняются 1. В остальных случаях результат равен 0. Например, с помощью AND вы можете узнать, чётное число или нет.

Посмотрите на таблицу истинности операции AND:

Логическая операция OR (ИЛИ)

Обозначается знаком | .

Оператор OR также выполняется с 2-мя битами (a и b). Результат равен 0, если a и b равны 0, иначе он равен 1. Смотрим таблицу истинности.

Логическая операция XOR (исключающее ИЛИ)

Оператор XOR обозначается ^ .

XOR выполняется с 2-мя битами (a и b). Результат выполнения операции XOR (исключающее ИЛИ ) равен 1, когда один из битов b или a равен 1. В остальных ситуациях результат применения оператора XOR равен 0.

Таблица истинности логической операции для XOR (исключающее ИЛИ) выглядит так:

Используя XOR (исключающее ИЛИ), вы можете поменять значения 2-х переменных одинакового типа данных, не используя временную переменную. А ещё, посредством XOR можно зашифровать текст, например:

String msg = "This is a message"; char message = msg.toCharArray(); String key = ".*)"; String encryptedString = new String(); for(int i = 0; i< message.length; i++){ encryptedString += message[i]^key.toCharArray(); }

Согласен, XOR - далеко не самый надёжный метод шифрования, но это не значит, что его нельзя сделать частью какого-либо шифровального алгоритма.

Логическая операция NOT (НЕ)

Это побитовое отрицание, поэтому выполняется с одним битом и обозначается ~ .

Результат зависит от состояния бита. Если он в нулевом состоянии, то итог операции - единица и наоборот. Всё предельно просто.

Эти 4 логические операции следует запомнить в первую очередь, т. к. с их помощью можно получить практически любой возможный результат. Также существуют такие операции, как << (побитовый сдвиг влево) и >> (побитовый сдвиг вправо).

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

Введение

Побитовые операторы проводят операции непосредственно на битах числа, поэтому числа в примерах будут в двоичной системе счисления.

Я расскажу о следующих побитовых операторах:

• | (Побитовое ИЛИ (OR)),
• & (Побитовое И (AND)),
• ^ (Исключающее ИЛИ (XOR)),
• ~ (Побитовое отрицание (NOT)),
• << (Побитовый сдвиг влево),
• >> (Побитовый сдвиг вправо).

Битовые операции изучаются в дискретной математике, а также лежат в основе цифровой техники, так как на них основана логика работы логических вентилей - базовых элементов цифровых схем. В дискретной математике, как и в цифровой технике, для описания их работы используются таблицы истинности. Таблицы истинности, как мне кажется, значительно облегчают понимание битовых операций, поэтому я приведу их в этой статье. Их, тем не менее, почти не используют в объяснениях побитовых операторов высокоуровневых языков программирования.

О битовых операторах вам также необходимо знать:

1. Некоторые побитовые операторы похожи на операторы, с которыми вы наверняка знакомы (&&, ||). Это потому, что они на самом деле в чем-то похожи. Тем не менее, путать их ни в коем случае нельзя.
2. Большинство битовых операций являются операциями составного присваивания.

Побитовое ИЛИ (OR)

Побитовое ИЛИ действует эквивалентно логическому ИЛИ, но примененному к каждой паре битов двоичного числа. Двоичный разряд результата равен 0 только тогда, когда оба соответствующих бита в равны 0. Во всех других случаях двоичный результат равен 1. То есть, если у нас есть следующая таблица истинности:

38 | 53 будет таким:

В итоге мы получаем 110111 2 , или 55 10 .

Побитовое И (AND)

Побитовое И - это что-то вроде операции, противоположной побитовому ИЛИ. Двоичный разряд результата равен 1 только тогда, когда оба соответствующих бита операндов равны 1. Другими словами, можно сказать, двоичные разряды получившегося числа - это результат умножения соответствующих битов операнда: 1х1 = 1, 1х0 = 0. Побитовому И соответствует следующая таблица истинности:

Пример работы побитового И на выражении 38 & 53:

Как результат, получаем 100100 2 , или 36 10 .

С помощью побитового оператора И можно проверить, является ли число четным или нечетным. Для целых чисел, если младший бит равен 1, то число нечетное (основываясь на преобразовании двоичных чисел в десятичные). Зачем это нужно, если можно просто использовать %2 ? На моем компьютере, например, &1 выполняется на 66% быстрее. Довольно неплохое повышение производительности, скажу я вам.

Исключающее ИЛИ (XOR)

Разница между исключающим ИЛИ и побитовым ИЛИ в том, что для получения 1 только один бит в паре может быть 1:

Например, выражение 138^43 будет равно…

… 10100001 2 , или 160 10

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

Также с помощью исключающего ИЛИ можно зашифровать текст. Для этого нужно лишь итерировать через все символы, и ^ их с символом-ключом. Для более сложного шифра можно использовать строку символов:

String msg = "This is a message"; char message = msg.toCharArray(); String key = ".*)"; String encryptedString = new String(); for(int i = 0; i< message.length; i++){ encryptedString += message[i]^key.toCharArray(); }

Исключающее ИЛИ не самый надежный способ шифровки, но его можно сделать частью шифровального алгоритма.

Побитовое отрицание (NOT)

Побитовое отрицание инвертирует все биты операнда. То есть, то что было 1 станет 0, и наоборот.

Вот, например, операция ~52:

Результатом будет 203 10

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

Дополнительный код

Здесь мне стоит рассказать вам немного о способе представления отрицательных целых чисел в ЭВМ, а именно о дополнительном коде (two’s complement). Не вдаваясь в подробности, он нужен для облегчения арифметики двоичных чисел.

Главное, что вам нужно знать о числах, записанных в дополнительном коде - это то, что старший разряд является знаковым. Если он равен 0, то число положительное и совпадает с представлением этого числа в прямом коде, а если 1 - то оно отрицательное. То есть, 10111101 - отрицательное число, а 01000011 - положительное.

Чтобы преобразовать отрицательное число в дополнительный код, нужно инвертировать все биты числа (то есть, по сути, использовать побитовое отрицание) и добавить к результату 1.

Например, если мы имеем 109:

Представленным выше методом мы получаем -109 в дополнительном коде.
Только что было представлено очень упрощенное объяснение дополнительного кода, и я настоятельно советую вам детальнее изучить эту тему.

Побитовый сдвиг влево

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

Интересной особенностью сдвига влево на N позиций является то, что это эквивалентно умножению числа на 2 N . Таким образом, 43<<4 == 43*Math.pow(2,4) . Использование сдвига влево вместо Math.pow обеспечит неплохой прирост производительности.

Побитовый сдвиг вправо

Как вы могли догадаться, >> сдвигает биты операнда на обозначенное количество битов вправо.

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

Так как побитовый сдвиг вправо - это операция, противоположная побитовому сдвигу влево, несложно догадаться, что сдвиг числа вправо на N количество позиций также делит это число на 2 N . Опять же, это выполняется намного быстрее обычного деления.

Вывод

Итак, теперь вы знаете больше о битовых операциях и не боитесь их. Могу предположить, что вы не будете использовать >>1 при каждом делении на 2. Тем не менее, битовые операции неплохо иметь в своем арсенале, и теперь вы сможете воспользоваться ими в случае надобности или же ответить на каверзный вопрос на собеседовании.

Простейшие логические операции относятся к двузначной логике. Их 4 штуки: “НЕ”, “И”, “ИЛИ”, “XOR”. Также для обозначения этих операций используют разные значки (“~”, “&” и т.п.).

При записи логических формул вместо слов “истина” и “ложь” обычно используют стандартные международные обозначения:
Вместо “истина” пишут: true, T, t, 1.
Вместо “ложь” пишут: false, F, f, 0.

“НЕ”

Операция “НЕ” преобразует истину в ложь, а ложь в истину:

НЕ true = false
НЕ false = true

У этой операции бывают разные другие названия: “логическое НЕ”, “отрицание”, “логическое отрицание”, “инверсия”, “логическая инверсия”. Для международных обозначений вместо “НЕ” пишут “NOT”.

В естественном языке этой операции соответствует добавление слов “неправда, что...” в начале высказывания. Например:

Применение операции “НЕ” к высказыванию (1):

“Неправда, что Сурков должен мне денег”. (2)

Если высказывание (1) ложно, то высказывание (2) истинно. Если высказывание (2) ложно, то высказывание (1) истинно.

Нетрудно понять, что двойное применение “НЕ” возвращает нас к прежней истинности.

“Неправда, что неправда, что Сурков должен мне денег”. (3)

Истинность высказывания (3) всегда совпадает с истинностью высказывания (1).

“И”

Операция “И” применяется к двум высказываниям. Ее результат “истина”, только если оба высказывания истинны (а иначе “ложь”):

false И false = false
false И true = false
true И false = false
true И true = true

У этой операции бывают разные другие названия: “логическое И”, “конъюнкция”, “логическое умножение”. Для международных обозначений вместо “И” пишут “AND”.

В естественном языке этой операции соответствует вставка союза “и” между высказываниями. Например:

“Сурков должен мне денег”. (1)
“Петров должен мне денег”. (2)

Применение операции “И” к высказываниям (1) и (2):

“Сурков должен мне денег, и Петров должен мне денег”. (3)

Эту фразу можно сократить, сохранив прежний смысл:

“Сурков и Петров должны мне денег”. (3)

Высказывание (3) истинно только тогда, когда истинны оба высказывания: (1) и (2). Если хотя бы одно из них ложно, то результат тоже ложен. Если оба ложны – тоже.

То есть, если Петров мне денег не задолжал, а задолжал только Сурков, тогда высказывание (3) не будет “полуправдой” или “полуложью”, а будет просто ложью.

“ИЛИ”

Операция “ИЛИ” применяется к двум высказываниям. Ее результат “истина”, если хотя бы одно высказывание истинно (а иначе “ложь”):

false ИЛИ false = false
false ИЛИ true = true
true ИЛИ false = true
true ИЛИ true = true

У этой операции бывают разные другие названия: “логическое ИЛИ”, “включающее ИЛИ”, “дизъюнкция”, “логическое сложение”. Для международных обозначений вместо “ИЛИ” пишут “OR”.
В естественном языке этой операции соответствует вставка союза “или” между высказываниями, но... не всегда (см. ниже об операции “XOR”). Например:

“Я хочу попить”. (1)
“Я хочу поесть”. (2)

Применение операции “ИЛИ” к высказываниям (1) и (2):

“Я хочу попить, или я хочу поесть”. (3)

По-русски звучит правильно, но коряво, и эту фразу можно сократить, сохранив прежний смысл:

“Я хочу попить или поесть ”. (3)

Высказывание (3) истинно тогда, когда истинно хотя бы одно из высказываний (1) и (2), а можно оба. Если оба высказывания ложны, то результат тоже ложен.

То есть, если я хочу есть, но не пить, тогда высказывание (3) истинно. Если я не прочь и поесть, и попить, выказывание (3) тоже истинно. Ложно оно тогда, когдя я не хочу ни того, ни другого.

“XOR”

Операция “XOR” применяется к двум высказываниям. Ее результат “истина”, если ровно одно из высказываний истинно (а иначе “ложь”):

false XOR false = false
false XOR true = true
true XOR false = true
true XOR true = false

У этой операции бывают разные другие названия: “исключающее ИЛИ”, “сложение по модулю 2”, “логическое сложение по модулю 2”. “XOR” – это международное обозначение, общепринятого “русского” аналога нет.

В естественном языке этой операции соответствует вставка союза “или” между высказываниями – так же, как в случае с операцией “ИЛИ”. Например:

“Я собираюсь просить прибавки к зарплате”. (1)
“Я попытаюсь сэкономить ”. (2)

Применение операции “XOR” к высказываниям (1) и (2):

“Я собираюсь просить прибавки к зарплате или я попытаюсь сэкономить”. (3)

Сокращенно:

“Я собираюсь просить прибавки к зарплате или попытаюсь сэкономить”. (3)

Высказывание (3) истинно тогда, когда истинно ровно одно из высказываний (1) и (2). Если я не собираюсь ни просить прибавки, ни экономить, тогда фраза ложна. Также, я имел в виду, что не собираюсь делать и то, и другое одновременно.

Обратите внимание на разницу между операциями “ИЛИ” и “XOR”. Она заключается только в последнем правиле:

true ИЛИ true = true
true XOR true = false

В естественном языке обе операции изображаются одним и тем же союзом “или”. Это – пример неоднозначности естественного языка. Если помните, омонимы и многозначные слова могут иметь больше одного значения. Союз “или” именно такой: он имеет два возможных значения. Первое выражается логической операцией “ИЛИ”, второе – логической операцией “XOR”.

В английском языке существуют те же проблемы: союз “or” имеет те же два значения. А вот древним римлянам было проще, так как в латыни есть два разных слова: “vel” (операция “ИЛИ”) и “aut” (операция “XOR”).

Поскольку разница между операциями “ИЛИ” и “XOR” невелика (всего одно последнее правило), то иногда эта разница не имеет значения. Иногда о том, что имеется в виду, можно догадаться по интонации, или по контексту. Иногда определить точный смысл так и не удается.