Построение и анализ таблиц истинности логических выражений

• Тема: Системы счисления и двоичное представление информации в памяти компьютера.

1 (базовый уровень, время – 1 мин)

Решение:

• для решения достаточно знать двоичные коды чисел от 1 до 7, поскольку для перевода восьмеричного числа в двоичную систему можно достаточно каждую цифру отдельно записать в виде тройки двоичных (триады):
• 1731 8 = 001 111 011 001 2
• в этой записи 7 единиц
• Ответ: 7

Ещё пример задания:

Р-05. Укажите наименьшее четырёхзначное восьмеричное число, двоичная запись которого содержит 5 единиц. В ответе запишите только само восьмеричное число, основание системы счисления указывать не нужно.

Решение:

• вообще, минимальное двоичное число, содержащее 5 единиц – это 11111 2 , но в восьмеричной системе оно записывается как 37 – двухзначное число
• минимальное четырёхзначное восьмеричное число – 1000 8 = 1 000 000 000 2 , для решения задачи в конце этого числа нужно заменить четыре нуля на единицы:

1 000 001 111 2 = 1017 8

• Ответ: 1017

Ещё пример задания:

Р-04. Сколько единиц в двоичной записи десятичного числа 519?

Решение:

• проще всего представить заданное число в виде суммы степеней числа 2:

519 = 512 + 7 = 2 9 + 4 + 3 = 2 9 + 2 2 + 2 + 1 = 2 9 + 2 2 + 2 1 + 2 0

• количество единиц в двоичной записи числа равно количеству слагаемых в таком разложении
• Ответ: 4

Ещё пример задания:

Р-03. Даны 4 числа, они записаны с использованием различных систем счисления. Укажите среди этих чисел то, в двоичной записи которого содержится ровно 6 единиц. Если таких чисел несколько, укажите наибольшее из них.

1) 63 10 * 4 10 2) F8 16 + 1 10 3) 333 8 4) 11100111 2

Решение:

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

63­ 10 = 111111­ 2 4 10 = 100­ 2

в первом числе ровно 6 единиц, умножение на второе добавляет в конец два нуля:

63­ 10 * 4 10 = 111111­ 2 * 100­ 2 = 111111­00 2

то есть в этом числе 6 единиц

Решение: (продолжение)

3) для второго варианта воспользуемся связью между шестнадцатеричной и двоичной системами счисления: каждую цифру шестнадцатеричного числа можно переводить отдельно в тетраду (4 двоичных цифры):

F­ 16 = 1111­ 2 8 16 = 100­0 2 F8 16 = 1111 1000 2

после добавления единицы F8 16 + 1 = 1111 1001 2 также получаем число, содержащее ровно 6 единиц, но оно меньше, чем число в первом варианте ответа

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

333 8 = 011 011 011­ 2 = 11011011 2

это число тоже содержит 6 единиц, но меньше, чем число в первом варианте ответа

5) последнее число 11100111 2 уже записано в двоичной системе, оно тоже содержит ровно 6 единиц, но меньше первого числа

6) таким образом, все 4 числа, указанные в вариантах ответов содержат ровно 6 единиц, но наибольшее из них – первое

7) Ответ: 1.

Ещё пример задания:

Р-02. Сколько единиц в двоичной записи числа 1025?

1) 1 2) 2 3) 10 4) 11

Решение (разложение на сумму степеней двойки):

• тут очень полезно знать наизусть таблицу степеней двойки, где 1024 = 2 10 и 1 = 2 0
• таким образом, 1025= 1024 + 1 = 2 10 + 2 0
• вспоминая, как переводится число из двоичной системы в десятичную (значение каждой цифры умножается на 2 в степени, равной её разряду), понимаем, что в двоичной записи числа ровно столько единиц, сколько в приведенной сумме различных степеней двойки , то есть, 2
• Ответ: 2

Выводы:

• есть несколько способов решения, «каждый выбирает для себя»;
• наиболее сложные вычисления – при переводе всех чисел в десятичную систему, можно легко ошибиться;
• сравнивать числа в двоичной системе сложно, также легко ошибиться;
• видимо, в этой задаче наиболее простой вариант – использовать восьмеричную систему, нужно просто запомнить двоичные записи чисел от 0 до 7 и аккуратно все сделать;
• в других задачах может быть так, что выгоднее переводить все в десятичную или шестнадцатеричную систему счисления.

Еще пример задания:

Р-00. Для хранения целого числа со знаком используется один байт. Сколько единиц содержит внутреннее представление числа (-78) ?

1) 3 2) 4 3) 5 4) 6

Решение:

• переводим число 78 – 1=77 в двоичную систему счисления:

77 = 64 + 8 + 4 + 1 = 2 6 + 2 3 + 2 2 + 2 0 = 1001101 2

2) по условию число занимает в памяти 1 байт = 8 бит, поэтому нужно представить число с помощью 8 разрядов

3) чтобы получилось всего 8 разрядов (бит), добавляем впереди один ноль:

77 = 01001101 2

4) делаем инверсию битов (заменяем везде 0 на 1 и 1 на 0):

01001101 2 → 10110010 2

это и есть число (-78) в двоичном дополнительно коде

5) в записи этого числа 4 единицы

6) таким образом, верный ответ – 2 .