Логические формулы

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

Пример:

x, у, x1, y1, xk, уn

Презентация "Булевы функции"

Логической формулой является:

1) любая логическая переменная, а также каждая из двух логических констант — 0 (ложь) и 1 (истина); 

2) если А и В — формулы, то и А*В — тоже формулы, где знак «*» означает любую из логических бинарных операций.

Пример: 

(х & у) → z 

Формуле приписывается одно из двух значений >— 0 или 1.

Формулы А и B, зависящие от одного и того же набора переменных x1, x2, х3, … xn, называют равносильными или эквивалентными, если на любом наборе значений переменных x1, х2, х3, … xn они имеют одинаковые значения.

Пример: А = В

Битовые сдвиги и операции

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

Би́товый сдвиг — изменение позиций битов в слове на одну и ту же величину.

Большинство компьютеров не могут напрямую адресовать биты, которые содержатся группами по 8, 16, 32 или 64 битов в словах. Для обеспечения работы с битами существует множество машинных инструкций, включающие различные типы сдвигов. Все сдвиги похожи друг на друга поведением средних битов, которые просто сдвигаются влево или вправо на определённую величину. Однако, поведение крайних битов, которые уходят из слова и которые появляются в слове, зависит от типа сдвига.

В электронике битовые сдвиги осуществляются в регистрах сдвига.

Логический сдвиг

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

Арифметический сдвиг

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

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

Циклический сдвиг

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

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