что такое поразрядная конъюнкция

Задание 12. Краткие теоретические сведения

1. Все адреса, используемые в современных компьютерных сетях – это 32-разрядные двоичные числа.

адрес_сети = адрес_узла & маска.

Пример 1. Пусть X = 1101; Y = 1011. Тогда X&Y = 1001 (только в первом и последнем разряде и в X, и в Y стоит 1).

Пример 2. Пусть X = 1101; Y = 0011. Тогда X&Y = 0001

Пример 3. Пусть X = 1111 1101; Y = 1010 0011. Тогда X&Y = 1010 0001

Пример 4. Пусть X = 1111 1111; Y = 1010 0011. Тогда X&Y = 1010 0011

Для любого 8-разрядного числа Y выполнено: 11111111 & Y = Y

Пример 5. Пусть X = 0000 0000; Y = 1010 0011. Тогда X&Y = 0000 0000

Для любого 8-разрядного числа Y выполнено: 00000000 & Y = 00000000

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

A & 255 = A

A & 0 = 0

4. При выполнении задания B11 полезно учитывать следующее.

Поэтому третье слева число в маске может принимать только такие значения:

. 128 = 1000 0000₂ = 255-127

. 192 = 1100 0000₂ = 128+64 = 255 – 63

. 224 = 1110 0000₂ = 128+64 + 32 = 255 – 31

. 240 = 1111 0000₂ = 128+64 + 32 + 16 = 255 – 15

. 248 = 1111 1000₂ = 128+64 + 32 + 16 + 8 = 255 – 7

. 252 = 1111 1100₂ = 128+64 + 32 + 16 + 8 +4 = 255 – 3

. 254 = 1111 1110₂ = 128+64 + 32 + 16 + 8 +4 +2 = 255 – 1

. 255 = 1111 1111₂ = 128+64 + 32 + 16 + 8 +4 +2 + 1

— первое и второе число в адресе сети те же, что и в адресе узла сети;

— четвертое – всегда 0;

— третье получается из третьего числа адресе узла сети обнулением определенного количества младших разрядов. Например, если третье число в маске подсети равно 248, то обнуляются три младших разряда третьего числа адреса узла подсети.

Источник

Что такое поразрядная конъюнкция

Примечание: Перед поразрядным сравнением операнды number1 и number2 округляются до меньшего целого.

/* присвоение 00000001, 00000011 */

/* возвращает 1 (00000001) */

Поразрядное исключающее ИЛИ

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

analog = number1 ^ number2;

Примечание: Перед поразрядным сравнением операнды number1 и number2 округляются до меньшего целого.

/* присвоение 00000001, 00000011 */

Val = Num1 ^ Num2;

/* возвращает 2 (00000010) */

Дизъюнкция

analog = number1 | number2;

Примечание: Перед поразрядным сравнением операнды number1 и number2 округляются до меньшего целого.

/* присвоение 00000001, 00000011 */

Val = Num1 | Num2;

/* возвращает 3 (00000011) */

Логическое И

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

discrete = number1 && number2;

Логическое ИЛИ

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

discrete = number1 || number2;

Val = Num1 || Num2;

Val = Num1 || Num2;

/* возвращает 0 */

Источник

Побитовая конъюнкция

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наименьшего неотрицательного целого числа \(A\) формула \((x\&25 \neq 0) \to ((x\&17 = 0) \to (x\&A \neq 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\) )?

Переведем в двоичную систему счисления известные числа: 17 = 10001, 25 = 11001.

Известно, что, чтобы данная импликация была равна 1, на тех местах, где в двоичной записи 25 стоят единички, в двоичной записи \(Z_<17 \; or A>\) должны тоже стоять единички.

Мы ищем наименьшее неотрицательное целое число \(A.\) Значит, где вместо звездочек можно ставить нули, — будем ставить. Двигаемся справа налево. На место первой звездочки можно поставить 0 — единичка уже есть в записи числа 17. На втором месте все равно, что ставить, — в записи 25 на этом месте 0. Ставим 0. Аналогично ставим на третье место. Теперь посмотрим на четвертое: в записи 25 — стоит 1, а вот в записи 17 — 0. Значит, на четвертом месте в числе \(A\) должна быть единичка. Аналогично заканчиваем ставить знаки. Никаких лишних разрядов впереди числа добавлять не будем — мы ищем наименьшее.

Итак, получили 1000. Это число в двоичной системе счисления. В десятичной — 8.

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наибольшего неотрицательного целого числа \(A\) формула \((x\&A \neq 0) \to ((x\&11 = 0) \to (x\&17 \neq 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\) )?

Теперь воспользуемся тем же, только в обратную сторону. Запишем выражение так: \(Z_ <11>\wedge Z_ <17>\to Z_.\)

\(Z_<11 \; or 17>\) мы можем сразу вычислить. Так как \(11 = 1011_<2>, \; 17 = 10001_<2>,\) можем выполнить поразрядное сложение:

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

Таким образом, единица может стоять на тех местах, где она стоит в двоичной записи числа слева — необязательно, но если где-то и стоит, то только там. Но вспомним, что мы ищем максимальное \(A\) : значит, мы хотим, чтобы в \(A\) было как можно больше единиц. А так как единицы могут быть только на тех местах, где стоят единицы в \(11011,\) наибольшее возможное \(A,\) — это и есть \(11011_ <2>= 27_<10>.\)

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наименьшего неотрицательного целого числа \(A\) формула \(((x\&17 \neq 0) \wedge (x\&57 \neq 0)) \to ((x\&A \neq 0) \wedge (x\&17 \neq 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\) )?

Знаем, что \(a \to (b \vee c) = a \to b \vee a \to c.\) Тогда получаем \(Z_ \to Z_ <17>\vee Z_ \to Z_<57>.\)

Мы хотим, чтобы данное выражение всегда было равно 1. Для этого нужно, чтобы или \(Z_ \to Z_ <17>= 1,\) или \(Z_ \to Z_ <57>= 1.\)

Помним, что импликация истинна, если на тех местах, где в двоичной записи числа справа стоят единицы, стоят единицы и в двоичной записи числа слева, то есть наименьшее неотрицательное целое \(A\) — это и есть число справа, то есть 17 в первом случае и 57 во втором. Мы ищем наименьшее число — то есть нам подходит 17.

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наименьшего неотрицательного целого числа \(A\) формула \(((x\&29 \neq 0) \wedge (x\&18 \neq 0)) \to ((x\&A \neq 0) \wedge (x\&29 \neq 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\) )?

Знаем, что \(a \to (b \vee c) = a \to b \vee a \to c.\) Тогда получаем \(Z_ \to Z_ <29>\vee Z_ \to Z_<18>.\)

Мы хотим, чтобы данное выражение всегда было равно 1. Для этого нужно, чтобы или \(Z_ \to Z_ <29>= 1,\) или \(Z_ \to Z_ <18>= 1.\)

Помним, что импликация истинна, если на тех местах, где в двоичной записи числа справа стоят единицы, стоят единицы и в двоичной записи числа слева, то есть наименьшее неотрицательное целое \(A\) — это и есть число справа, то есть 29 в первом случае и 18 во втором. Мы ищем наименьшее число — то есть нам подходит 18.

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наибольшего неотрицательного целого числа \(A\) формула \(((x\&23 = 0) \vee (x\&17 = 0)) \to ((x\&58 \neq 0) \to (x\&A = 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\) )?

\(23 = 10111_<2>, 17 = 10001_<2>.\) Тогда посчитаем \(23 \& 17:\)

Мы сразу можем определить, истинна ли \(Z_ <17>\to Z_<58>.\)

\(\begin 17 = 010001\\ 58 = 111010\\ \end\)

Нет, не истинна, т.к. на первом месте, например, в двоичной записи 17 стоит 0, а на первом в двоичной записи 58 — 1. Значит, нужно, чтобы истинна была импликация \(Z_ <17>\to Z_.\)

Мы ищем наибольшее \(A.\) Чтобы импликация истинна, на тех местах, где в двоичной записи A стоят единицы, стоят единицы и в двоичной записи 17. То есть больше единиц, чем есть в 17, в записи \(A\) быть не может. Тогда наибольшее \(A\) — это и есть само 17.

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наибольшего неотрицательного целого числа \(A\) формула \(((x\&17 \neq 0) \vee (x\&A \neq 0)) \to (x\&17 \neq 0) \vee ((x\&A \neq 0) \wedge (x\&41 = 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\) )?

Мы можем сразу посмотреть, верно ли \(Z_ <17>\to Z_<41>.\) Напомним, что мы ищем наибольшее целое неотрицательное \(A\) такое, что данное выражение истинно.

Импликация истинна, если на всех местах, где в двоичной записи 41 стоит единица, стоит единица на том же месте в двоичной записи 17. Это не так. Импликация ложна. Значит, должно быть истинно \(Z_ <17>\to Z_.\)

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

Обозначим через \(m\&n\) поразрядную конъюнкцию неотрицательных целых чисел \(m\) и \(n.\) Так, например, \(14\&5 = 11102\&01012 = 0100_2 = 4.\)

Для какого наибольшего неотрицательного целого числа \(A\) формула \(((x\&24 \neq 0) \vee (x\&A \neq 0)) \to (x\&24 \neq 0) \vee ((x\&A \neq 0) \wedge (x\&47 = 0))\) тождественно истинна (т.е. принимает значение \(1\) при любом неотрицательном целом значении переменной \(x\) )?

Мы ищем наибольшее \(A\) такое, что данное выражение истинно. Истинно ли \(Z_ <24>\to Z_<47>\) мы можем проверить сразу.

Источник

Поразрядная конъюнкция. Задача №18 из ЕГЭ по информатике

Поразрядная конъюнкция. Задача №18 из ЕГЭ по информатике.

Задача №18 является заданием повышенной сложности и проверят знание основных понятий и законов математической логики. Это задание за многолетнюю историю ЕГЭ претерпевало ряд изменений. Сначала это была задача на нахождение минимальной/максимальной длины отрезка, затем мы работали с элементами множеств, далее появились битовые цепочки и делители, наконец, последнее на сегодняшний день – поразрядные конъюнкции.

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

Итак, во всех заданиях на поразрядную конъюнкцию ищут либо наименьшее, либо наибольшее десятичное число А, такое, что заданное выражение будет тождественно истинно при любом натуральном значении переменной Х. Рассмотрим оба вида заданий1.

1) Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?

Решение.
Сначала преобразуем выражение, избавившись от импликации по формуле A>B = A+B

Всё выражение будет истинным, когда хотя бы одна из трёх его составляющих будет истинна.

Перейдём к двоичной записи чисел.

Теперь будем побитово подбирать такое минимальное А, чтобы наше выражение было верным.

Аналогично рассматриваем следующий бит. Для 49: 0=0 сразу даёт истину, так что соответствующий бит А опять равен «0».

Ещё два бита дают уже рассмотренную ситуацию, получаем:

Последний бит даёт истину для 33: 1? 0, поэтому 5-ый бит А равен «0»

Итак, получили А=100002=1610

2) Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наибольшее натуральное число A, такое что выражение

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X)?

Как и в задании на поиск минимального значения сначала преобразуем выражение. Получим:

Перейдём к двоичной записи чисел.

Так же как и в 1-ом задании, будем побитово рассматривать каждое выражение. Если какое-либо из них даёт истину, то в соответствующий бит А мы можем поставить что угодно, но так как мы ищем максимальное значение, то будем ставить «1». В противном случае, бит А должен быть равен «0», так как истинность всего выражения должна будет обеспечить конъюнкция X & A = 0.

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

Источник

Поразрядные (битовые) операции

Логические операции

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

· !— логическое отрицание (логическое НЕ);

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

Пусть, например, имеется математическое неравенство: 0 x) или (х > 0) && (x x > 10должно выглядеть следующим образом: (0 > x) || (10 10).

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

—сдвиг влево

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

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

unsigned a = 20, n = 3, r;

r = a > n;

cout > n

Значение r: 0 0 … 0 0 0 0 0 0 0 1 0 = 2

Операция сдвига влево осуществляет перемещение битов левого операнда a в сторону больших разрядов на количество разрядов, равное значению правого операнда n. Это эквивалентно умножению значения a на 2 в степени n(20 * 8 = 160).

Операция сдвига вправо осуществляет перемещение битов левого операнда a в сторону меньших разрядов на количество разрядов, равное значению правого операнда n. Это эквивалентно делению значения a на 2 в степени n(целочисленное деление 20 / 8 = 2).

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

Операндами этих операций целочисленных типов данных. Результат также целочисленный.

Операция побитовое отрицание (

) осуществляет инвертирование всех байтов двоичного представления своего операнда. Например:

Источник