Логические операции и логические элементы

Узнай об истинных и ложных высказываниях, операциях И, ИЛИ, НЕ, таблицах истинности и о том, как компьютер складывает числа с помощью логических элементов.

  • 8…10 классы
  • 16 мин
  • 10 вопросов
  • Урок 18 из 59

В этом уроке ты узнаешь

  • Находить результат операций И, ИЛИ, НЕ и исключающего ИЛИ
  • Строить и читать таблицы истинности
  • Вычислять значение логического выражения
  • Объяснять, как логические элементы используются в компьютере

Эльвин говорит друзьям: «Если в субботу будет хорошая погода и я закончу уроки, пойду на Приморский бульвар». В этой фразе два условия, соединённых словом «и». Компьютер принимает решения точно так же — соединяет простые условия логическими операциями. Только вместо «да» и «нет» он использует 1 и 0.

Высказывания: истина и ложь

ВысказываниеОпределение

Утверждение, о котором можно однозначно сказать, истинно оно или ложно. Истинному высказыванию приписывают значение 1, ложному — 0.

Например, «Баку — столица Азербайджана» — истинное высказывание (1), а «5 > 8» — ложное (0). «Какая сегодня погода?» — вовсе не высказывание: вопрос не может быть ни истинным, ни ложным.

Чтобы читать дальше, зарегистрируйся бесплатно

Остальные разделы урока, тест и заметки открываются с аккаунтом Educora. Регистрация занимает минуту, а прогресс сохраняется на всех твоих устройствах.

Основные логические операции

  • НЕ (инверсия, NOT) меняет значение на противоположное: НЕ 1 = 0, НЕ 0 = 1.
  • И (конъюнкция, AND) даёт 1, только когда оба высказывания истинны.
  • ИЛИ (дизъюнкция, OR) даёт 1, когда истинно хотя бы одно высказывание.
  • Исключающее ИЛИ (XOR) даёт 1, только когда истинно ровно одно высказывание, то есть когда входы различны.
Простое объяснение

Эти операции легко представить с обычными выключателями и лампой. Замкнутый выключатель — 1, разомкнутый — 0; горящая лампа — 1, погасшая — 0.

ОперацияКартинка из жизни
И (AND)Два выключателя друг за другом (последовательно): лампа горит, только когда замкнуты оба
ИЛИ (OR)Два выключателя рядом (параллельно): лампа горит, если замкнут хотя бы один
НЕ (NOT)Кнопка «наоборот»: нажмёшь — свет гаснет, отпустишь — загорается
XORСвет на лестнице: выключатели внизу и наверху, и щелчок любого из них меняет состояние лампы

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

ABA И BA ИЛИ BA XOR B
00000
01011
10011
11110
Таблица истинности операций с двумя входами
Простое объяснение
  1. Посчитай случаи

    У n входов 2ⁿ случаев: два входа — 4 строки, три входа — 8 строк.

  2. Запиши строки двоичным счётом

    Записывай входы так, будто считаешь в двоичной системе: 00, 01, 10, 11 — так ни один случай не потеряется.

  3. Заполняй столбец за столбцом

    И работает как обычное умножение: 1 · 1 = 1, остальное даёт 0. ИЛИ отвечает на вопрос «есть ли хотя бы одна 1?»

AНЕ A
01
10
У операции НЕ всего один вход
Углублённо

В математике и во многих учебниках эти операции записывают символами: A ∧ B (И), A ∨ B (ИЛИ), ¬A (НЕ), A ⊕ B (исключающее ИЛИ). Для них выполняются законы алгебры логики, и каждый закон можно проверить таблицей истинности из 4 или 8 строк. Одни похожи на обычную алгебру, другие — нет: например, у второго распределительного закона нет аналога для чисел (a + b · c ≠ (a + b) · (a + c)).

ЗаконФормула
ПереместительныйA ∧ B = B ∧ A, A ∨ B = B ∨ A
РаспределительныйA ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C), A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)
Законы де Моргана¬(A ∧ B) = ¬A ∨ ¬B, ¬(A ∨ B) = ¬A ∧ ¬B
ПоглощениеA ∨ (A ∧ B) = A, A ∧ (A ∨ B) = A
Дополнение и двойное отрицаниеA ∨ ¬A = 1, A ∧ ¬A = 0, ¬¬A = A
ИдемпотентностьA ∧ A = A, A ∨ A = A
Основные законы алгебры логики. Каждый из них проверяется таблицей истинности.

Логические элементы

Внутри компьютера логические операции выполняют логические элементы (вентили). Это крошечные электронные схемы из транзисторов: на входы подаются сигналы 0 или 1, а на выходе получается результат. В современном процессоре миллиарды транзисторов, и собранные из них элементы складывают числа, сравнивают их и хранят в памяти.

Интерактив

Загрузка симуляции…
Меняй входы A и B: элемент И выдаёт 1, только когда оба входа равны 1.

Кроме основных элементов широко используются их сочетания: И-НЕ (NAND) инвертирует результат И, а ИЛИ-НЕ (NOR) — результат ИЛИ. Интересно, что из одних только элементов И-НЕ можно собрать любую другую логическую схему.

Простое объяснение

Есть ещё два элемента. И-НЕ (NAND) означает «не оба сразу»: он переворачивает ответ И. ИЛИ-НЕ (NOR) означает «ни один»: он переворачивает ответ ИЛИ. Интересно, что из одних только элементов И-НЕ можно собрать любую другую логическую схему — как построить целый дом из кирпичей одного вида.

ABA И BNANDNOR
00011
01010
10010
11100
NAND даёт 0, только когда оба входа равны 1, а NOR даёт 1, только когда оба входа равны 0.
Углублённо

Всё из NAND

Задача

Используя только элементы NAND, постройте НЕ, И, ИЛИ и XOR. Сколько элементов нужно для XOR?

Показать решениеСкрыть решение

Решение

НЕ A = NAND(A, A), так как ¬(A ∧ A) = ¬A.
A И B = НЕ NAND(A, B) = NAND(N, N), где N = NAND(A, B).
A ИЛИ B = NAND(¬A, ¬B) — по закону де Моргана ¬(¬A ∧ ¬B) = A ∨ B.
XOR: пусть N = NAND(A, B); тогда A ⊕ B = NAND(NAND(A, N), NAND(B, N)) — всего 4 элемента. Таблица истинности это подтверждает: во всех четырёх случаях результат совпадает с A ⊕ B.
Благодаря этому свойству микросхемы часто собирают из элементов одного вида.

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

Операции соединяются в логические выражения. Если скобок нет, сначала выполняется НЕ, затем И, а последним — ИЛИ; это похоже на то, как в математике умножение выполняется раньше сложения.

Простое объяснение

Выражение без скобок читай как в математике: НЕ похоже на минус перед буквой и выполняется первым, И похоже на умножение, а ИЛИ — на сложение. Поэтому НЕ A ИЛИ B И C читается как (НЕ A) ИЛИ (B И C) — как −a + b · c.

Вычисли по порядку

Задача

Найди значение выражения НЕ A ИЛИ B И C при A = 1, B = 1, C = 0.

Показать решениеСкрыть решение

Решение

1) НЕ A = НЕ 1 = 0.
2) B И C = 1 И 0 = 0.
3) 0 ИЛИ 0 = 0.
Порядок: НЕ → И → ИЛИ.

Пример: значение выражения

Задача

Найди значение выражения (A ИЛИ B) И НЕ C при A = 1, B = 0, C = 1.

Показать решениеСкрыть решение

Решение

1) Скобки: A ИЛИ B = 1 ИЛИ 0 = 1.
2) НЕ C = НЕ 1 = 0.
3) 1 И 0 = 0.
Выражение ложно, так как один из входов операции И равен 0.
Углублённо

Бывает и обратная задача: дана таблица истинности, нужно найти формулу. Универсальный способ: для каждой строки, где результат равен 1, соедини переменные этой строки знаком ∧ (перед переменной, равной 0, поставь ¬), соедини такие слагаемые знаком ∨ и упрости по законам алгебры логики. В таблице с n переменными 2ⁿ строк, поэтому различных функций 2^(2ⁿ): для двух переменных — 16.

От таблицы к формуле

Задача

Функция F задана так: F(0, 0) = 1, F(0, 1) = 1, F(1, 0) = 0, F(1, 1) = 1. Найдите для F самую короткую формулу.

Показать решениеСкрыть решение

Решение

Строки с результатом 1: A = 0, B = 0; A = 0, B = 1; A = 1, B = 1.
F = (¬A ∧ ¬B) ∨ (¬A ∧ B) ∨ (A ∧ B).
В первых двух слагаемых выносим ¬A за скобки: ¬A ∧ (¬B ∨ B) = ¬A ∧ 1 = ¬A.
F = ¬A ∨ (A ∧ B) = (¬A ∨ A) ∧ (¬A ∨ B) = ¬A ∨ B (второй распределительный закон).
Эта функция — импликация A → B («если A, то B»): она ложна только при A = 1, B = 0.

Как компьютер складывает? Полусумматор

Задача

Нужно сложить два бита A и B. Какие элементы дают цифру суммы (S) и перенос в следующий разряд (C)?

Показать решениеСкрыть решение

Решение

Выпишем все случаи:
0 + 0 = 00₂ → S = 0, C = 0
0 + 1 = 01₂ → S = 1, C = 0
1 + 0 = 01₂ → S = 1, C = 0
1 + 1 = 10₂ → S = 0, C = 1
Столбец S совпадает с таблицей исключающего ИЛИ, а столбец C — с таблицей И.
Значит, S = A XOR B, C = A И B. Соединяя такие схемы, процессор складывает числа любой длины.
Простое объяснение
Углублённо

Полусумматор умеет складывать только самый правый разряд: он не учитывает перенос из предыдущего разряда. У полного сумматора три входа — A, B и входящий перенос Cin: S = A ⊕ B ⊕ Cin, Cout = (A ∧ B) ∨ (Cin ∧ (A ⊕ B)). Он собирается из двух полусумматоров и одного элемента ИЛИ. Соединив цепочкой 8 полных сумматоров, получим схему, складывающую 8-битные числа, — простейшую часть арифметико-логического устройства (АЛУ) процессора.

ABCinSCout
00000
00110
01010
01101
10010
10101
11001
11111
Таблица истинности полного сумматора: S — последняя цифра суммы трёх битов, Cout — перенос. Например, 1 + 1 + 1 = 11₂: S = 1, Cout = 1.

Интерактив

Загрузка симуляции…
Элемент XOR выдаёт 1, когда входы различны, — это цифра суммы в полусумматоре.
Python
print('A B | AND OR XOR')
for a in (0, 1):
    for b in (0, 1):
        print(f'{a} {b} |  {a & b}   {a | b}   {a ^ b}')
Ожидаемый результат
A B | AND OR XOR
0 0 |  0   0   0
0 1 |  0   1   1
1 0 |  0   1   1
1 1 |  1   1   0
В Python над битами & выполняет И, | — ИЛИ, а ^ — исключающее ИЛИ. Программа сама строит всю таблицу истинности.

Запомни

  • Высказывание либо истинно (1), либо ложно (0).
  • И даёт 1, только когда оба входа равны 1; ИЛИ — когда хотя бы один вход равен 1.
  • НЕ меняет значение на противоположное, а XOR даёт 1, когда входы различны.
  • Без скобок порядок такой: НЕ, затем И, затем ИЛИ.
  • Логические элементы строятся из транзисторов; XOR и И вместе складывают два бита.
Заметил ошибку или неточность в уроке?

Проверь себя

Вопросов: 10. Каждый правильный ответ приносит XP.

Вопрос 1 / 10

Вопрос 1 / 10. Когда выражение A И B равно 1?