Логические основы компьютера

Информатика · Информационные процессы

Высказывание — утверждение, о котором можно сказать, истинно оно (1) или ложно (0). Основные операции: инверсия ¬A (НЕ) меняет значение на противоположное; конъюнкция A ∧ B (И) истинна, только когда истинны оба высказывания; дизъюнкция A ∨ B (ИЛИ) ложна, только когда ложны оба. Ещё три: импликация A → B («если…, то…») ложна только при A = 1, B = 0; эквиваленция A ≡ B истинна при одинаковых значениях; исключающее ИЛИ A ⊕ B — при разных.

Таблица истинности показывает значение выражения при всех наборах переменных. Для n переменных в ней 2ⁿ строк: для двух — 4, для трёх — 8, для четырёх — 16. Порядок действий: скобки, затем НЕ, потом И, в конце ИЛИ. Пример: (A ∨ B) ∧ ¬C при A = 0, B = 1, C = 0: A ∨ B = 1; ¬C = 1; 1 ∧ 1 = 1.

Законы логики помогают упрощать выражения. Двойное отрицание: ¬¬A = A. Законы де Моргана: ¬(A ∧ B) = ¬A ∨ ¬B и ¬(A ∨ B) = ¬A ∧ ¬B (отрицание «раздаётся», а знак операции меняется). Поглощение: A ∧ (A ∨ B) = A и A ∨ (A ∧ B) = A. Импликацию заменяют так: A → B = ¬A ∨ B.

Логические элементы — электронные схемы, выполняющие эти операции: конъюнктор (И), дизъюнктор (ИЛИ), инвертор (НЕ), а также И-НЕ и ИЛИ-НЕ. Из них собраны сумматоры и ячейки памяти (триггеры). Та же логика работает в поисковых запросах: «A & B» — страницы с обоими словами, «A | B» — хотя бы с одним; их количество связано формулой |A ∪ B| = |A| + |B| − |A ∩ B|. Пример: 300 + 200 − 50 = 450.

Главное

Ловушка на тесте

Импликация с ложной посылкой ИСТИННА: 0 → 0 = 1 и 0 → 1 = 1. Это противоречит бытовой интуиции, поэтому здесь ошибаются чаще всего. И не путайте обычное ИЛИ с исключающим: 1 ∨ 1 = 1, но 1 ⊕ 1 = 0.

Проверь себя

1. один верный ответ

В кодировке, где каждый символ занимает 16 бит, слово «Қазақстан» имеет объём

  1. A. 18 байт
  2. B. 9 байт
  3. C. 144 байт
  4. D. 72 байт
Показать ответ и разбор

Верный ответ: A

Разбор: В слове 9 букв, каждая — 16 бит = 2 байта: 9 · 2 = 18 байт. 144 — объём в битах, 9 байт было бы в однобайтовой кодировке.

2. один верный ответ

В таблице ASCII латинские буквы идут по алфавиту подряд, код буквы A равен 65. Код буквы E равен

  1. A. 69
  2. B. 68
  3. C. 70
  4. D. 5
Показать ответ и разбор

Верный ответ: A

Разбор: A — 65, B — 66, C — 67, D — 68, E — 69: буква E стоит на 4 позиции дальше A. 5 — это номер буквы в алфавите, а не её код.

3. один верный ответ

Какое наименьшее количество бит нужно, чтобы закодировать 100 различных значений?

  1. A. 7
  2. B. 6
  3. C. 10
  4. D. 100
Показать ответ и разбор

Верный ответ: A

Разбор: Нужно наименьшее i, при котором 2ⁱ ≥ 100: 2⁶ = 64 — мало, 2⁷ = 128 — достаточно. Ответ: 7 бит.

Открыть конспект в тренажёре →Бесплатно, без регистрации