Урок 10логика и компьютер. логические операции. диаграммы эйлера-венна§18. логика и компьютер. §19. логические операции. §20. диаграммы

Размер таблиц истинности

Если имеется n входных переменных, то существует 2 n возможных комбинаций их истинностных значений. Данная функция может выдавать истину или ложь для каждой комбинации, поэтому количество различных функций от n переменных равно двойной экспоненте 2 2 n .

Таблицы истинности для функций трех и более переменных приводятся редко.

Побитовое исключающее ИЛИ (^)

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

Таблица истинности для этой операции выглядит так:

В следующем примере поразрядное исключающее ИЛИ выполняется для чисел 38 и 3:

Выполнить код »
Скрыть результаты

Этот пример отличается от предыдущего только тем, что второй бит результата обнуляется, поскольку в обоих операндах он равен 1. Все остальные единичные биты переходят в результат, потому что у них нет пары. В итоге, получаем 100101₂, или 37₁₀.

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

Выполнить код »
Скрыть результаты

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

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

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

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

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

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

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

(5

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

В любом другом случае результатом будет False

Обратите внимание, что операнды заключаются в круглые скобки

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

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

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

Побитовые операторы присваивания

Как и в случае с арифметическими операторами присваивания, язык C++ предоставляет побитовые операторы присваивания для облегчения внесения изменений в переменные.

Например, вместо мы можем написать .

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

Выполняет операцию «Исключающее ИЛИ» над каждой парой бит.

Исключающее ИЛИ равно 1, если только или только , но не оба одновременно .

Таблица истинности для исключающего ИЛИ:

Как видно, оно даёт 1, если ЛИБО слева , ЛИБО справа , но не одновременно. Поэтому его и называют «исключающее ИЛИ».

Пример:

Исключающее ИЛИ в шифровании

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

Иначе говоря, верна формула: .

Пусть Вася хочет передать Пете секретную информацию . Эта информация заранее превращена в число, например строка интерпретируется как последовательность кодов символов.

Вася и Петя заранее договариваются о числовом ключе шифрования .

Алгоритм:

• Вася берёт двоичное представление и делает операцию . При необходимости бьётся на части, равные по длине , чтобы можно было провести побитовое ИЛИ для каждой части. В JavaScript оператор работает с 32-битными целыми числами, так что нужно разбить на последовательность таких чисел.
• Результат отправляется Пете, это шифровка.

Например, пусть в очередное число равно , а ключ равен .

• Петя, получив очередное число шифровки , применяет к нему такую же операцию .
• Результатом будет исходное число .

В нашем случае:

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

Чётность в 32-разрядных двойных словах

Ну а если надо определить чётность в 32-разрядном числе?

Тогда число разбивается на четыре байта, и поочерёдно с этими байтами выполняется операция исключающего ИЛИ.

Например, мы разбили 32-разрядное число B на четыре байта
B0, B1, B2, B3,
где В0 — это младший байт.

Тогда для определения чётности числа В нам надо будет использовать следующую формулу:

Но в ассемблере такая запись недопустима. Поэтому придётся немного подумать.

Ну и напоследок о происхождении мнемоники XOR. В английском языке
есть слово eXception — исключение. Сокращением от этого слова
является буква Х (так повелось). Вы наверняка встречали такое в
рекламе или в названии продуктов, производители которых претендуют (ну или думают,
что претендуют) на исключительность. Например, Лада XRAY, Sony XPeria и т.п.
Так что XOR — это аббревиатура, собранная из двух слов — eXception OR — исключающее ИЛИ.

Приложения

Пример принципиальной схемы полусумматора

Пример полной схемы сумматора

Элементы XOR и элементы AND — две наиболее часто используемые структуры в приложениях СБИС .

Использует дополнительно

Логический вентиль XOR может использоваться как однобитовый сумматор, который складывает любые два бита для вывода одного бита. Например, если мы добавим 1 плюс 1 в двоичном формате , мы ожидаем двухбитного ответа, 10 (т.е. 2 в десятичном формате ). Поскольку завершающий бит суммы в этом выходе достигается с помощью XOR, предыдущий бит переноса вычисляется с помощью логического элемента AND . Это основной принцип в . Немного более крупная схема может быть объединена в цепочку, чтобы складывать более длинные двоичные числа.

Генератор псевдослучайных чисел

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

Обнаружение корреляции и последовательности

Элементы XOR выдают 0, когда оба входа совпадают. При поиске определенного битового шаблона или последовательности PRN в очень длинной последовательности данных можно использовать серию вентилей XOR для параллельного сравнения строки битов из последовательности данных с целевой последовательностью. Затем можно подсчитать количество выходов 0, чтобы определить, насколько хорошо последовательность данных соответствует целевой последовательности. Корреляторы используются во многих устройствах связи, таких как приемники и декодеры CDMA, для исправления ошибок и канальных кодов. В приемнике CDMA корреляторы используются для извлечения полярности конкретной последовательности PRN из объединенного набора последовательностей PRN.

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

1110100101 (data)
11010      (target)
00111      (XOR) 2 zero bits

1110100101
 11010
 00000     5 zero bits

1110100101
  11010
  01110    2 zero bits

1110100101
   11010
   10011   2 zero bits

1110100101
    11010
    01000  4 zero bits

1110100101
     11010
     11111 0 zero bits

Matches by offset:

  .
  :     :
: : : : :  
-----------
0 1 2 3 4 5

В этом примере наилучшее совпадение происходит, когда целевая последовательность смещена на 1 бит и все пять битов совпадают. При смещении на 5 бит последовательность точно совпадает с обратной. Глядя на разницу между количеством единиц и нулей, которые выходят из банка логических элементов XOR, легко увидеть, где происходит последовательность и является ли она инвертированной. Более длинные последовательности легче обнаружить, чем короткие.

Полезность в криптографии

Основная причина, по которой XOR так полезен в криптографии, заключается в том, что он «идеально сбалансирован»; для данного ввода открытого текста 0 или 1 результат зашифрованного текста с равной вероятностью будет либо 0, либо 1 для действительно случайного бита ключа.

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

Другие логические операции, такие как И или ИЛИ , не имеют такого сопоставления (например, AND создаст три нуля и одну единицу, поэтому знание того, что данный бит зашифрованного текста равен 0, означает, что существует 2/3 шанса, что исходный открытый текст bit был 0, в отличие от идеального шанса 1/2 в случае XOR)

Зачем нужны побитовые операторы?

В далеком прошлом компьютерной памяти было очень мало и ею сильно дорожили. Это было стимулом максимально разумно использовать каждый доступный бит. Например, в логическом типе данных bool есть всего лишь два возможных значения (true и false), которые могут быть представлены одним битом, но по факту занимают целый байт памяти! А это, в свою очередь, из-за того, что переменные используют уникальные адреса памяти, а они выделяются только в байтах. Переменная bool занимает 1 бит, а другие 7 бит — тратятся впустую.

Используя побитовые операторы, можно создавать функции, которые позволят уместить 8 значений типа bool в переменную размером 1 байт, что значительно сэкономит потребление памяти. В прошлом такой трюк был очень популярен. Но сегодня, по крайней мере, в прикладном программировании, это не так.

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

В языке С++ есть 6 побитовых операторов:

В побитовых операциях следует использовать только целочисленные типы данных unsigned, так как C++ не всегда гарантирует корректную работу побитовых операторов с целочисленными типами signed.

Правило: При работе с побитовыми операторами используйте целочисленные типы данных unsigned.

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

Примеры задач с решениями по этой теме Пройти тестирование по теме Контрольная по теме

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

Логическое выражение — составные высказывания в виде формулы.

Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак «=».

Алгоритм построения  таблицы  истинности:

1.подсчитать количество переменных n в логическом выражении;

2. определить число строк в таблице по формуле m=2n, где n — количество переменных;

3. подсчитать количество логических операций в формуле;

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

5. определить количество столбцов: число переменных + число операций;

6. выписать наборы входных переменных;

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

Заполнение таблицы:

1.разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»;

2.разделить колонку  значений  второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»;

3.продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа.

Пример 1. Для формулы  A/\ (B \/ ¬B /\¬C) постройте  таблицу истинности.

 Количество логических переменных 3, следовательно, количество строк — 23 = 8.

Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов — 3 + 5 = 8.

Пример 2. Определите истинность  логического выражения  F(А, В) = (А\/ В)/\(¬А\/¬В) .

1. В выражении две переменные А и В (n=2).

2.  m_строк=2n, m=22=4 строки.

3. В формуле 5 логических операций.

4. Расставляем порядок действий

1) А\/ В;  2) ¬А;  3) ¬В;  4) ¬А\/¬В;  5) (А\/ В)/\(¬А\/¬В).

5. К_{столбцов}=n+5=2+5=7 столбцов.

 Вывод: логическое выражение принимает значение истина при наборах F(0,1)=1 и F(1,0)=1.

Пример 3. Построёте таблицу истинности для логического выражения

F = (A\/ B) /\ ¬С

1. В данной функции три логические переменные – А, В, С
2. количество строк таблицы = 23 =8
3. В формуле 3 логические операции.
4. Расставляем порядок действий

1) А\/ В;  2) ¬С; 3) (AVB) /\ ¬С  .

1. количество столбцов таблицы = 3 + 3 = 6

Пример 4.  Определите истинность формулы: F = ((С \/В) =>  В) /\ (А /\ В) => В.

Построим таблицу истинности этой формулы.

Ответ: формула является тождественно истинной.

Пример 5. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.

Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F?

 1) ¬X/\¬Y/\Z                      2) ¬X\/¬Y\/Z                  3) X\/Y\/¬Z              4) X\/Y\/Z

 Решение (вариант 1, через таблицы истинности):

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

 Очевидно, что значения заданной функции F совпадают со значениями выражения X\/Y\/¬Z. Следовательно, правильный ответ – 3.

Ответ: 3

 Решение (Вариант 2):

Чтобы не строить таблицу истинности для каждого выражения, можно просто перепроверить предложенные ответы по заданной таблице истинности. Т.е. в каждую из четырех предложенных функций последовательно подставлять значения переменных X, Y  и Z, из заданной таблицы истинности и вычислять значения логического выражения. Если значения вычисляемого выражения совпадут со значением F во всех трех строчках заданной таблицы, то это и есть искомое выражение.

 Рассмотрим данный конкретный пример:

1)первое заданное выражение  ¬X/\¬Y/\Z = 0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы;

2)второе заданное выражение ¬X\/¬Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует  второй строке таблицы;

3)третье выражение   X\/Y\/¬Z    соответствует F при всех предложенных комбинациях X,Y и Z;

4)четвертое выражение X\/Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.

Ответ: 3

Операторы, допускающие логическое значение NULL

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

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

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

Эта семантика описывается в следующей таблице:

Поведение этих операторов отличается от типичного поведения операторов, допускающих значение NULL. Как правило, оператор, который определяется для операндов типа значения, можно также использовать с соответствующими операндами типа, допускающего значение NULL. Такой оператор возвращает , если какой-либо из операндов имеет значение . При этом операторы и могут возвращать отличное от NULL значение, даже если один из операндов имеет значение . См. подробнее о поведении операторов, допускающих значение NULL, в разделе в статье Типы, допускающие значение NULL.

Вы также можете также использовать операторы и с операндами , как показано в следующем примере:

Условные логические операторы и не поддерживают операнды типа .

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

Мы уже с ним сталкивались на уроке №34.

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

bool bTooLarge = (x > 100); // переменная bTooLarge будет true, если x > 100
if (!bTooLarge)
// Делаем что-нибудь с x
else
// Выводим ошибку

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

#include <iostream>

int main()
{
int x = 5;
int y = 7;

if (!x == y)
std::cout << «x does not equal y»;
else
std::cout << «x equals y»;

return 0;
}

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

Но ведь не равно , как это возможно? Поскольку приоритет логического оператора НЕ выше, чем приоритет оператора равенства, то выражение обрабатывается как . Так как — это , то — это . Условие ложное, поэтому выполняется часть else!

Напоминание: Любое ненулевое целое значение в логическом контексте является true. Так как , то вычисляется как true, а вот , т.е. . Использование целых чисел в логических операциях подобным образом может запутать не только пользователя, но и самого разработчика, поэтому так не рекомендуется делать!

Правильный способ написания программы, приведенной выше:

#include <iostream>

int main()
{
int x = 5;
int y = 7;

if (!(x == y))
std::cout << «x does not equal y»;
else
std::cout << «x equals y»;

return 0;
}

Сначала обрабатывается , а затем уже оператор НЕ изменяет результат на противоположный.

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

Битовые операции

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

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

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

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

Альтернативы

Схема ворот XOR с использованием трех смешанных ворот

Если вентиль определенного типа недоступен, схема, реализующая ту же функцию, может быть построена из других доступных вентилей. Схема, реализующая функцию XOR, может быть тривиально построена из элемента XNOR, за которым следует элемент NOT . Если мы рассмотрим это выражение , мы можем построить схему логического элемента XOR напрямую, используя вентили AND, OR и NOT . Однако для этого подхода требуется пять ворот трех разных типов.
(А⋅B¯)+(А¯⋅B){\ displaystyle (A \ cdot {\ overline {B}}) + ({\ overline {A}} \ cdot B)}

В качестве альтернативы, если доступны разные вентили, мы можем применить булеву алгебру для преобразования, как указано выше, и применить закон де Моргана к последнему члену, чтобы получить, что может быть реализовано с использованием только трех вентилей, как показано справа.
(А⋅B¯)+(А¯⋅B)≡(А+B)⋅(А¯+B¯){\ Displaystyle (A \ cdot {\ overline {B}}) + ({\ overline {A}} \ cdot B) \ Equiv (A + B) \ cdot ({\ overline {A}} + {\ overline { B}})}(А+B)⋅(А⋅B)¯{\ Displaystyle (А + В) \ cdot {\ overline {(А \ cdot B)}}}

Схема затвора XOR может быть сделана из четырех вентилей NAND . Фактически, вентили И-НЕ и ИЛИ-ИЛИ являются так называемыми «универсальными вентилями», и любая логическая функция может быть построена только на основе логики И-НЕ или логики ИЛИ-ИЛИ . Если четыре логических элемента И-НЕ заменяются вентилями ИЛИ-ИЛИ , это приводит к вентилю ИСКЛЮЧАЮЩЕЕ ИЛИ , который может быть преобразован в вентиль ИСКЛЮЧАЮЩЕЕ ИЛИ путем инвертирования выхода или одного из входов (например, с помощью пятого вентиля ИЛИ-ИЛИ ).

Описание[править]

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

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

Список операторов

В следующей таблице перечислены все побитовые операторы.
Далее операторы разобраны более подробно.

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

1. Операнды преобразуются в 32-битные целые числа, представленные последовательностью битов. Дробная часть, если она есть, отбрасывается.
2. Для бинарных операторов – каждый бит в первом операнде рассматривается вместе с соответствующим битом второго операнда: первый бит с первым, второй со вторым и т.п. Оператор применяется к каждой паре бит, давая соответствующий бит результата.
3. Получившаяся в результате последовательность бит интерпретируется как обычное число.

Посмотрим, как работают операторы, на примерах.

Вспомогательные функции parseInt, toString

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

• – переводит строку с двоичной записью числа в число.
• – получает для числа запись в 2-ной системе в виде строки.

Например:

Без них перевод в двоичную систему и обратно был бы куда менее удобен.
Более подробно они разбираются в главе Числа.

Как задать логическую функцию

Есть множество способов задать булеву функцию:

• таблица истинности
• характеристические множества
• вектор значений
• матрица Грея
• формулы

Рассмотрим некоторые из них:

Чтобы задать функцию через вектор значений необходимо записать вектор из 2 n нулей и единиц, где n – число аргументов, от которых зависит функция. Например, функцию двух аргументов можно задать так: 0001 (операция И), 0111 (операция ИЛИ).

Чтобы задать функцию в виде формулы, необходимо записать математическое выражение, состоящее из аргументов функции и логических операций. Например, можно задать такую функцию: a∧b ∨ b∧c ∨ a∧c

~ (Побитовое НЕ)

Производит операцию НЕ над каждым битом, заменяя его на обратный ему.

Таблица истинности для НЕ:

Пример:

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

Например:

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

Оператор сдвигает первый операнд на указанное число битов влево. Лишние биты отбрасываются, справа добавляются нулевые биты.

Например, даст :

Операция сдвинула и отбросила два левых нулевых бита и добавила справа два новых нулевых.

Левый сдвиг почти равен умножению на 2

Битовый сдвиг обычно имеет тот же эффект, что и умножение на два раз, например:

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

Этот оператор сдвигает биты вправо, отбрасывая лишние. При этом слева добавляется копия крайнего-левого бита.

Знак числа (представленный крайним-левым битом) при этом не меняется, так как новый крайний-левый бит имеет то же значение, что и исходном числе.

Поэтому он назван «переносящим знак».

Например, даст :

Операция сдвинула вправо и отбросила два правых бита и добавила слева две копии первого бита .

Аналогично, даст :

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

Правый сдвиг почти равен целочисленному делению на 2

Битовый сдвиг обычно имеет тот же результат, что и целочисленное деление на два раз:

Этот оператор сдвигает биты первого операнда вправо. Лишние биты справа отбрасываются. Слева добавляются нулевые биты.

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

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

Для отрицательных чисел – результат работы разный. Например, даст , в отличие от (даёт ):

Пример задания

Пусть необходимо построить таблицу для логического выражения F = (A → B) * (A + B). Эта формула состоит из двух логических переменных A и B и нескольких операций. Начинают построение с определения строк. Используя формулу 2n+1 для рассматриваемого примера можно установить, что их число будет: x = 22 + 1 = 5.

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

1. Импликация в первой скобке.
2. Инверсия во второй скобке переменной A.
3. Отрицание во второй скобке неизвестной B.
4. Сложение во втором члене.
5. Конъюнкция.

В итоге получится, что столбцов будет: Y = 2 + 5 = 7. Теперь нужно построить таблицу 7Х5. В шапку первого и второго столбца вписывают переменные, а затем операции над ними. Затем в строках, соответствующих A и B нужно записать всё, что с ними может произойти. В итоге останется только правильно посчитать последний столбец.

Для этого нужно использовать законы. Необходимо выполнить логическое умножение значений в скобках. Первой и второй строчке будет соответствовать операция произведения один на один, что в ответе даст единицу. Третьей и четвёртой — ноль на один, что в итоге даст ноль. Последний столбец является главным для рассматриваемой логической функции. По нему можно узнать значение логической функции для любых форм переменных A и B.

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

Например, заданно выражение (x + y + z) * (x + y). По сути, оно записано в совершенно нормальной конъюнктивной форме. Но для приведения его к этому виду нужно, чтобы во втором выражении стояла z

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

Добавить ноль через z можно, как ноль умножить на НЕ z. В итоге получится выражение (x + y + z) * (x + y + z + z), для которого, используя алгоритм составить таблицу уже не так и сложно.

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

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

Таблица истинности для этой операции выглядит так:

В следующем примере поразрядное И выполняется для чисел 38 и 3:

Выполнить код »
Скрыть результаты

Как видите, только в одной позиции биты обоих операндов равны 1. Из-за этого
все остальные биты результата обнуляются, что в итоге дает 000010.
Как результат, получаем 000010₂, или 2₁₀.

Итоги

• Побитовые операторы работают с числами на самом низком уровне – уровне отдельных битов, поэтому в JavaScript они выполняются гораздо быстрее, чем другие операторы или методы.
• Специальные значения NaN и Infinity в поразрядных операциях интерпретируются как О.
• Если побитовые операторы применяются к нечисловому значению, то оно сначало автома­тически преобразуется в число с помощью функции Number() и только затем вы­полняется операция.
• Побитовое НЕ просто инвертирует все биты операнда, а затем новое значение уменьшает на 1.
• С помощью двух побитовых НЕ можно округлить значение операнда или математического выражения.
• Побитовое И вернёт единицу только в том случае, если биты обоих операндов в этой позиции равны 1.
• Побитовое ИЛИ возвращает 1, если хотя бы один бит равен 1, и О, если оба бита равны О.
• Побитовое исключающее ИЛИ возвращает 1, только если один бит равен 1, и О, если оба бита равны 1.
• Оператор сдвига влево
• Оператор сдвига вправо с сохранением знака сдвигает все биты числа вправо на указанное количество позиций. Если операнд положительный, то пустые места слева заполняются нулями. Если же изначально мы работаем с отрицательным числом, то все пустые места заполняются единицами.
• Сдвиг вправо с заполнением нулями сдвигает все биты числа вправо на указанное количество позиций. В отличие от сдвига вправо с со­хранением знака , теперь пустые биты заполняются нулями независимо от знакового бита.

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

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

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

#include <iostream>

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

return 0;
}

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

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

Похожие записи:

Как выставить зажигание с помощью стробоскопа? Сигнализация действия защиты и автоматики Подключение потолочного светильника со светодиодами Маркировка smd компонентов: кодовые обозначения Как сделать веб-приложение для вашего собственного bluetooth low energy девайса? Как подключить усилитель в машине