Перейти к содержанию

Булева логика

IGCSE Computer Science · Тема 10

Видеоурок по этой теме Открыть страницу видео
8:32

Булева логика

Внимательно посмотрите на этот чип. Внутри него нет ничего умного. Он не умеет думать. Внутри находятся миллионы крошечных переключателей, и каждый может находиться только в одном из двух…

Озвучивание на английском · переключаемые субтитры на английском и китайском языках

Программа
Кандидаты должны уметь: Примечания и рекомендации
1 Распознавать и использовать стандартные символы для логических вентилей • См. раздел 4 для символов логических вентилей
2 Определить и понять функции логических вентилей • Включая: – НЕ – И – ИЛИ – NAND – NOR – XOR (EOR) – двоичный выход, получаемый из всех возможных двоичных входов • «НЕ» — это вентиль с одним входом • Все остальные вентили ограничены двумя входами
3 (a) Использовать логические вентили для создания заданных логических схем на основе: (i) постановки задачи (ii) логического выражения (iii) таблицы истинности (b) Заполнить таблицу истинности на основе: (i) постановки задачи (ii) логического выражения (iii) логической схемы • Схема должна быть нарисована для данной постановки задачи без упрощений • Логические схемы будут ограничены максимум тремя входами и одним выходом • Пример таблицы истинности с тремя входами для заполнения: A B C Выход | 0 0 0 | 0 0 1 | 0 1 0 | 0 1 1 | 1 0 0 | 1 0 1 | 1 1 0 | 1 1 1
(c) Написать логическое выражение на основе: (i) постановки задачи (ii) логической схемы (iii) таблицы истинности

Источник: Программа Cambridge International

10.1

Что такое булева логика?

Булева логика работает со значениями, которые могут быть либо истинными, либо ложными. В электронике они обозначаются как 1 (истина) и 0 (ложь). Логический вентиль принимает один или несколько таких входов и дает один выход, следуя фиксированному правилу.

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

Электронная схема, собранная на макетной плате
Логические вентили строятся на основе электронных схем, таких как эта, где каждый вентиль переключается между 1 и 0
10.2

Шесть логических вентилей

Работа логической схемы: полубитный сумматор

Вы должны знать шесть вентилей. NOT имеет один вход; все остальные имеют два входа (A и B).

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

Вентиль NOT

Вентиль NOT инвертирует вход. Выход равен 1, когда вход равен 0.

A Выход
0 1
1 0

Вентиль AND

Вентиль AND выдает выход 1 только тогда, когда оба входа равны 1.

Таблица истинности для И: только 1 И 1 дает 1
AND выдает 1 только тогда, когда оба входа равны 1
A B Выход
0 0 0
0 1 0
1 0 0
1 1 1

Вентиль OR

Вентиль OR выдает выход 1, когда хотя бы один вход равен 1.

Таблица истинности для ИЛИ: 0 ИЛИ 0 дает 0, остальные дают 1
OR выдает 1, когда хотя бы один вход равен 1
A B Выход
0 0 0
0 1 1
1 0 1
1 1 1

Вентиль NAND

Вентиль NAND — это AND, за которым следует NOT. Выход является противоположным выходу AND.

A B Выход
0 0 1
0 1 1
1 0 1
1 1 0

Вентиль NOR

Вентиль NOR — это OR, за которым следует NOT. Выход является противоположным выходу OR.

A B Выход
0 0 1
0 1 0
1 0 0
1 1 0

Вентиль XOR

Вентиль XOR (исключающее ИЛИ) выдает выход 1, когда входы различны.

A B Выход
0 0 0
0 1 1
1 0 1
1 1 0
Исследовать

Логические вентили

Переключите входы и выберите вентиль, чтобы увидеть его выходной сигнал — AND (И), OR (ИЛИ), NOT (НЕ), NAND (НЕ-И), NOR (НЕ-ИЛИ), XOR (исключающее ИЛИ).

English Русский
Boolean logic/ˈbuːlɪən ˈlɒdʒɪk/ булева логика
logic gate/ˈlɒdʒɪk ɡeɪt/ логические вентили
truth table/truːθ ˈteɪbl/ таблица истинности
NOT gate/nɒt ɡeɪt/ НЕ-ворота
AND gate/ænd ɡeɪt/ И-ворота
OR gate/ɔː ɡeɪt/ ИЛИ-ворота
NAND gate/nænd ɡeɪt/ NAND-ворота
NOR gate/nɔː ɡeɪt/ NOR-ворота
XOR gate/ˈeksɔː ɡeɪt/ вентиль исключающего ИЛИ
logic expression/ˈlɒdʒɪk ekˈspreʃn/ логическое выражение
10.3

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

Логическое выражение описывает схему с помощью букв и слов названий вентилей. Обычный способ записи вентилей:

Вентиль Словами
NOT A НЕ A
A AND B A И B
A OR B A ИЛИ B
A NAND B A NAND B, то же, что NOT (A AND B)
A NOR B A NOR B, то же, что NOT (A OR B)
A XOR B A XOR B

Например, выражение (A AND B) OR (NOT C) означает: выполнить A И B, выполнить НЕ C, затем объединить два результата через ИЛИ.

Выражение X = A И B ИЛИ НЕ C, нарисованное как схема: вентиль И принимает A и B, вентиль НЕ принимает C, а вентиль ИЛИ объединяет их в выход X
Выражение X = (A И B) ИЛИ (НЕ C), нарисованное как логическая схема
Исследовать

Таблицы истинности

Постройте таблицу истинности для AND, OR, XOR и NOT — логическую основу любого выражения.

10.4

Логические схемы

Логическая схема соединяет вентили вместе для выполнения задачи. Выход одного вентиля может стать входом другого. На IGCSE схема имеет до трех входов и один выход.

Логическая схема: вентиль И, принимающий входы A и B, подает сигнал на один из входов вентиля ИЛИ, другой вход которого — C, давая выход X
Построение схемы для X = (A И B) ИЛИ C — выход вентиля AND подается на вентиль OR

Вы должны уметь переходить между четырьмя формами:

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

От формулировки задачи к схеме

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

Сигнализация (X) срабатывает, когда дверь открыта (A) И система включена (B).

Это X = A AND B, поэтому вы рисуете один вентиль AND с входами A и B.

На другие логические элементы указывают следующие слова:

В условии сказано… Логический элемент
«либо A, либо B, но не оба», «ровно один из» XOR
«ни A, ни B» NOR
«не одновременно A и B» NAND
«A выключен», «A не включён» NOT A

Например, «свет в зале (X) включён, когда ровно один из двух выключателей (A, B) поднят» записывается как X = A XOR B; «сигнальная лампа (X) горит, когда не нажаты ни тормоз (A), ни сцепление (B)» записывается как X = A NOR B.

Заполнение таблицы истинности по схеме или выражению

Чтобы заполнить таблицу истинности:

  1. Распишите все комбинации входов. Для трех входов будет 8 строк (от 000 до 111).
  2. Определите выход каждого вентиля по порядку, по одному столбцу за раз.
  3. Последний столбец — это финальный выход.
Три входа дают 2 × 2 × 2 = 8 строк; восемь комбинаций перечислены путем подсчета вверх в двоичной системе от 000 до 111, при этом последний столбец меняется на противоположный в каждой строке
Три входа дают восемь строк: каждая комбинация посчитана в двоичной системе
A B C A И B (A И B) ИЛИ C
0 0 0 0 0
0 0 1 0 1
0 1 0 0 0
0 1 1 0 1
1 0 0 0 0
1 0 1 0 1
1 1 0 1 1
1 1 1 1 1

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

Разбор примера. Заполните таблицу истинности для X = (A AND B) OR (NOT C) для строки A = 1, B = 0, C = 0. Работайте от скобок наружу, один вентиль за другим. Сначала A AND B = 1 И 0 = 0, потому что для И нужны оба входа равными 1. Затем NOT C = НЕ 0 = 1. Наконец, ИЛИ два результата: 0 ИЛИ 1 = 1. Таким образом, X = 1. Выделяйте каждому промежуточному вентилю отдельный столбец, вместо того чтобы пытаться решить всё выражение за один шаг: при трех входах есть $2^3 = 8$ строк, и именно эти промежуточные столбцы содержат баллы даже при ошибке в финальном ответе.

Разобранный пример (все четыре формы). Вентилятор теплицы (X) включается, если температура высокая (T) и окно не открыто (W), или если влажность высокая (H).

Шаг 1: выражение. «и окно не открыто» — это T AND NOT W; «или» соединяет H: X = (T AND NOT W) OR H.

Шаг 2: схема. W проходит через элемент НЕ; его выход и T поступают на элемент И; выход элемента И и H поступают на элемент ИЛИ.

Логическая схема для X = (T AND NOT W) OR H: вход W проходит через элемент НЕ; T и NOT W поступают на элемент И; выход элемента И и вход H поступают на элемент ИЛИ, выходом которого является X
Вентилятор теплицы: один элемент НЕ, один элемент И и один элемент ИЛИ

Шаг 3: таблица истинности. Восемь строк, с рабочим столбцом для каждого элемента:

T W H NOT W T AND NOT W X
0 0 0 1 0 0
0 0 1 1 0 1
0 1 0 0 0 0
0 1 1 0 0 1
1 0 0 1 1 1
1 0 1 1 1 1
1 1 0 0 0 0
1 1 1 0 0 1

**Шаг 4: проверка по тексту.**Whenever H = 1 вентилятор включен (строки 2, 4, 6, 8); иначе он включен только при T = 1, W = 0 (строка 5). Пять строк дают X = 1.

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

Разобранный пример (от схемы к выражению). В схеме A и B подаются на элемент NAND; B и C — на элемент XOR; выходы этих двух элементов подаются на элемент AND, выход которого обозначен X. Запишите выражение. По ходу работы обозначайте каждый провод: выход NAND — (A NAND B), выход XOR — (B XOR C), следовательно, X = (A NAND B) AND (B XOR C). Для строки A = 1, B = 1, C = 0: A NAND B = 0 (оба входа равны 1), поэтому X = 0 независимо от результата XOR.

От таблицы истинности к выражению или схеме

Рассматривайте только строки, в которых выход равен 1. Для каждой такой строки запишите входы, соединённые оператором AND, поставив NOT перед каждым входом, равным 0. Затем соедините выражения для строк оператором OR.

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

A B C X
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0

X = 1 в двух строках. Строка 0 1 1: A равно 0, поэтому получается (NOT A AND B) AND C. Строка 1 1 0: C равно 0, поэтому получается (A AND B) AND NOT C. Соедините их оператором OR:

X = ((NOT A AND B) AND C) OR ((A AND B) AND NOT C)

Схема следует выражению: два элемента NOT (для A и C), четыре двухвходовых элемента AND (для выражения каждой строки нужны два, поскольку у элементов не более двух входов) и один элемент OR для объединения двух выражений. Проверьте одну строку: для 0 1 1 первое выражение равно (1 AND 1) AND 1 = 1, поэтому X = 1, как в таблице.

Логическая схема по таблице истинности: входы A, B и C расположены на вертикальных линиях. A проходит через элемент NOT на элемент AND вместе с B, выход которого поступает на второй элемент AND вместе с C. A и B поступают на третий элемент AND, выход которого поступает на четвёртый элемент AND вместе с NOT C. Выходы второго и четвёртого элементов AND поступают на элемент OR, выход которого обозначен X
Одно выражение с AND для каждой строки, где X = 1; выражения соединены элементом OR

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

English Русский
logic circuit/ˈlɒdʒɪk ˈsɜːkɪt/ логическая схема
problem statement/ˈprɒbləm ˈsteɪtmənt/ формулировка задачи
10.5

Советы для экзамена

  • Выучите все шесть вентилей и их таблицы истинности: NOT (НЕ), AND (И), OR (ИЛИ), NAND (НЕ-И), NOR (НЕ-ИЛИ), XOR (исключающее ИЛИ; выход равен 1, когда входы различаются).
  • Составьте таблицу истинности с всеми входными строками (2 входа → 4 строки, 3 входа → 8), считая по двоичной системе, и добавьте рабочий столбец для каждого вентиля.
  • Преобразуйте условие задачи в логическое выражение, выделяя слова AND / OR / NOT, затем нарисуйте его точно так, как оно написано — не упрощайте его.
  • NAND и NOR дают противоположный выход по сравнению с AND и OR; маленький кружок на выходе вентиля означает инверсию результата.
  • В таблице истинности возьмите каждую строку с выходом 1, соедините её входы оператором AND (с NOT для каждого 0), затем соедините выражения для строк оператором OR.
  • «Ровно один» или «но не оба» означает XOR; «ни … ни» означает NOR.

Интерактивные уроки по этой теме

Пройдите его шаг за шагом с упражнениями мгновенной проверки.

Архив экзаменационных работ

Больше тем в IGCSE Computer Science

Войти или создать аккаунт

IGCSE, A-Level & AP