Обозначается оборотом речи «либо…, либо…» Составное утверждение «либо A, либо B» считается истинным, когда истинно либо A, либо B, но не оба сразу; в противном случае составное утверждение ложно.

Т.е. результат истинен (равен 1), если A не равно B (A≠B).

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

1. истинно, если истинно или , или оба сразу.

2. истинно, если истинно или , но не оба сразу.

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

5. Импликация (логическое следование) образуется соединением двух высказываний в одно с помощью оборота речи «если …, то ….».

Запись: А®В

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

Т.е. если из 1 следует 0, то результат – 0, в остальных случаях – 1.

Например, высказывание «Если число делится на 10, то оно делится на 5» истинно, т.к. истинны и первое и второе высказывание.

Высказывание «Если число делится на 10, то оно делится на 3» ложно, т.к. из истинной предпосылки делается ложный вывод.

"Данный четырёхугольник - квадрат" (А ) и "Около данного четырёхугольника можно описать окружность" (В ). Тогда составное высказывание , читается как "Если данный четырёхугольник квадрат, то около него можно описать окружность".

В обычной речи связка "если..., то" описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться "бессмысленностью" импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, такими: "если президент США - демократ, то в Африке водятся жирафы", "если арбуз - ягода, то в бензоколонке есть бензин".

6. Эквивалентность (логическое равенство, ~ º Û) образуется соединением двух высказываний в одно с помощью оборота речи « …тогда и только тогда, когда...»

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

Например, высказывание «Компьютер может производить вычисления тогда и только тогда, когда он включен» и «Компьютер не может производить вычисления тогда и только тогда, когда он не включен» - истинны, поскольку оба простых высказывания одновременно истинны.


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

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

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

Отразим выше рассмотренные логические операции в таблице истинности:

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

Докажем, что операция импликация А®В равносильна логическому выражению:

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

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

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

Точки Значение Значение Требуемый выход
0 0 0
1 0 1
0 1 1
1 1 0

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

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

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

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

Точки Значение Значение Требуемый выход
0 0 0 0 0 0
1 0 1 1 0 1
0 1 1 0 1 1
1 1 0 0 0 0

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

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

В этой статье мы поговорим о некоторых битовых операциях. Рассмотрим основные из них: 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 логические операции следует запомнить в первую очередь, т. к. с их помощью можно получить практически любой возможный результат. Также существуют такие операции, как << (побитовый сдвиг влево) и >> (побитовый сдвиг вправо).

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

Операнды в данном случае подаются - на вход логического элемента поступают сигналы в форме напряжения высокого или низкого уровня, которые и служат по сути входными данными. Так, напряжение высокого уровня - это логическая единица 1 - обозначает истинное значение операнда, а напряжение низкого уровня 0 - значение ложное. 1 - ИСТИНА, 0 - ЛОЖЬ.

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

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

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

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

Логический элемент «И» - конъюнкция, логическое умножение, AND


«И» - логический элемент, выполняющий над входными данными операцию конъюнкции или логического умножения. Данный элемент может иметь от 2 до 8 (наиболее распространены в производстве элементы «И» с 2, 3, 4 и 8 входами) входов и один выход.

Условные обозначения логических элементов «И» с разным количеством входов приведены на рисунке. В тексте логический элемент «И» с тем или иным числом входов обозначается как «2И», «4И» и т. д. - элемент «И» с двумя входами, с четырьмя входами и т. д.


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

На западных схемах значок элемента «И» имеет прямую черту на входе и закругление на выходе. На отечественных схемах - прямоугольник с символом «&».

Логический элемент «ИЛИ» - дизъюнкция, логическое сложение, OR


«ИЛИ» - логический элемент, выполняющий над входными данными операцию дизъюнкции или логического сложения. Он так же как и элемент «И» выпускается с двумя, тремя, четырьмя и т. д. входами и с одним выходом. Условные обозначения логических элементов «ИЛИ» с различным количеством входов показаны на рисунке. Обозначаются данные элементы так: 2ИЛИ, 3ИЛИ, 4ИЛИ и т. д.


Таблица истинности для элемента «2ИЛИ» показывает, что для появления на выходе логической единицы, достаточно чтобы логическая единица была на первом входе ИЛИ на втором входе. Если логические единицы будут сразу на двух входах, на выходе также будет единица.

На западных схемах значок элемента «ИЛИ» имеет закругление на входе и закругление с заострением на выходе. На отечественных схемах - прямоугольник с символом «1».

Логический элемент «НЕ» - отрицание, инвертор, NOT

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

Таблица истинности для инвертора показывает, что высокий потенциал на входе даёт низкий потенциал на выходе и наоборот.

На западных схемах значок элемента «НЕ» имеет форму треугольника с кружочком на выходе. На отечественных схемах - прямоугольник с символом «1», с кружком на выходе.

Логический элемент «И-НЕ» - конъюнкция (логическое умножение) с отрицанием, NAND

«И-НЕ» - логический элемент, выполняющий над входными данными операцию логического сложения, и затем операцию логического отрицания, результат подается на выход. Другими словами, это в принципе элемент «И», дополненный элементом «НЕ». На рисунке приведено условное обозначение логического элемента «2И-НЕ».


Таблица истинности для элемента «И-НЕ» противоположна таблице для элемента «И». Вместо трех нулей и единицы - три единицы и ноль. Элемент «И-НЕ» называют еще «элемент Шеффера» в честь математика Генри Мориса Шеффера, впервые отметившего значимость этой в 1913 году. Обозначается как «И», только с кружочком на выходе.

Логический элемент «ИЛИ-НЕ» - дизъюнкция (логическое сложение) с отрицанием, NOR

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


Таблица истинности для элемента «ИЛИ-НЕ» противоположна таблице для элемента «ИЛИ». Высокий потенциал на выходе получается лишь в одном случае - на оба входа подаются одновременно низкие потенциалы. Обозначается как «ИЛИ», только с кружочком на выходе, обозначающим инверсию.

Логический элемент «исключающее ИЛИ» - сложение по модулю 2, XOR

«исключающее ИЛИ» - логический элемент, выполняющий над входными данными операцию логического сложения по модулю 2, имеет два входа и один выход. Часто данные элементы применяют в схемах контроля. На рисунке приведено условное обозначение данного элемента.

Изображение в западных схемах - как у «ИЛИ» с дополнительной изогнутой полоской на стороне входа, в отечественной - как «ИЛИ», только вместо «1» будет написано «=1».


Этот логический элемент еще называют «неравнозначность». Высокий уровень напряжения будет на выходе лишь тогда, когда сигналы на входе не равны (на одном единица, на другом ноль или на одном ноль, а на другом единица) если даже на входе будут одновременно две единицы, на выходе будет ноль - в этом отличие от «ИЛИ». Данные элементы логики широко применяются в сумматорах.

Операция исключающее ИЛИ (неравнозначность, сложение по модулю два) обозначается символом и отличается от логического ИЛИ только приA=1 и B=1.

Таким образом, неравнозначность двух высказываний Х1 и Х2 называют такое высказывание Y, которое истинно тогда и только тогда, когда одно из этих высказываний истинно, а другое ложно.

Определение данной операции может быть записано в виде таблицы истинности (таблица 6):

Таблица 6 – Таблица истинности операции «ИСКЛЮЧАЮЩЕЕ ИЛИ»

Как видно из таблицы 6, логика работы элемента соответствует его названию.

Это тот же элемент «ИЛИ» с одним небольшим отличием. Если значение на обоих входах равно логической единице, то на выходе элемента «ИСКЛЮЧАЮЩЕЕ ИЛИ», в отличие от элемента «ИЛИ», не единица, а ноль.

Операция «ИСКЛЮЧАЮЩЕЕ ИЛИ» фактически сравнивает на совпадение два двоичных разряда.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет своё название и обозначение (таблица 7).

Таблица 7 – Основные логические операции

Обозначение

операции

Читается

Название операции

Альтернативные обозначения

Отрицание (инверсия)

Черта сверху

Конъюнкция (логическое умножение)

Дизъюнкция (логическое сложение)

Если … то

Импликация

Тогда и только тогда

Эквиваленция

Либо … либо

ИСКЛЮЧАЮЩЕЕ ИЛИ (сложение по модулю 2)

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

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

При вычислении значения логического выражения принят определённый порядок выполнения логических операций.

1. Инверсия.

2. Конъюнкция.

3. Дизъюнкция.

4. Импликация.

5. Эквивалентность.

Для изменения указанного порядка выполнения операций используются скобки.

  1. Логические выражения и таблицы истинности

    1. Логические выражения

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

Для записи составного высказывания в виде логического выражения на формальном языке (языке алгебры логики) в составном высказывании нужно выделить простые высказывания и логические связи между ними.

Запишем в форме логического выражения составное высказывание «(2·2=5 или 2∙2=4) и (2∙2≠5 или 2∙2 ≠4)».

Проанализируем составное высказывание. Оно содержит два простых высказывания:

А = «2 2=5»-ложно (0),

В = «2 2=4»-истинно (1).

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

«(А или В ) и (Ā или В )».

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

инверсия, конъюнкция, дизъюнкция.

Для изменения указанного порядка могут использоваться скобки:

F = (A v В ) & (Ā v В ).

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

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

F = (A v В) & (Ā v В) = (0 v 1) & (1 v 0) = 1 & 1 = 1.

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

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

Простые высказывания обозначаются переменными (например, A и B).

При построении таблиц истинности целесообразно руководствоваться определённой последовательностью действий:

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

количество строк = 2 n .

В нашем случае логическая функция

имеет 2 переменные и, следовательно, количество строк в таблице истинности должно быть равно 4;

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

В нашем случае количество переменных равно двум: А и В, а количество логических операций - пяти (таблица 8), то есть количество столбцов таблицы истинности равно семи;

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

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

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

Таблица 8 – Таблица истинности логической функции