Раздел «Информационные процессы» в спецификации НЦТ

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

Главное по теме

Высказывание бывает только истинным (1) или ложным (0).
НЕ меняет значение на противоположное. И (конъюнкция) даёт 1, только если оба равны 1. ИЛИ (дизъюнкция) даёт 0, только если оба равны 0.
Исключающее ИЛИ (XOR) даёт 1, когда значения разные. Эквивалентность даёт 1, когда значения одинаковые.
Импликация A → B («если A, то B») ложна только в одном случае: A = 1, B = 0.
Порядок выполнения: скобки, НЕ, И, ИЛИ, импликация, эквивалентность.
Законы де Моргана: НЕ(A И B) = НЕ A ИЛИ НЕ B; НЕ(A ИЛИ B) = НЕ A И НЕ B.
Двойное отрицание: НЕ НЕ A = A. Закон поглощения: A ИЛИ (A И B) = A.
Таблица истинности для n переменных содержит 2ⁿ строк (для 3 переменных - 8).
В поисковых запросах ИЛИ расширяет результат (находит больше страниц), И сужает.
Логические элементы компьютера: И, ИЛИ, НЕ; из них собирают сумматор и память.
Импликация A → B равносильна НЕ A ИЛИ B. Проверка: при A = 1 и B = 0 получается 0 ИЛИ 0 = 0, а во всех остальных случаях 1.
XOR нескольких переменных истинно, когда среди них нечётное число единиц. Для A XOR B XOR C это 4 набора из 8.
Поиск: число страниц по запросу «A ИЛИ B» равно N(A) + N(B) − N(A И B). Общие страницы считаются дважды, поэтому одну такую долю вычитают.

Задания с разбором

1.Сколько строк в таблице истинности функции от 3 переменных?

1Каждая переменная принимает 2 значения: 0 или 1.
2Наборов 2 · 2 · 2 = 2³.
32³ = 8.

Ответ: 8 строк

2.Найдите значение ¬A ∨ B при A = 1, B = 0.

1¬A = ¬1 = 0.
2Подставляем: 0 ∨ 0.
3ИЛИ даёт 1, только если есть хотя бы одна единица. Здесь её нет.

Ответ: 0

3.Одинаковы ли выражения ¬(A ∧ B) и ¬A ∧ ¬B? Проверьте на A = 1, B = 0.

1Первое: A ∧ B = 1 ∧ 0 = 0, затем ¬0 = 1.
2Второе: ¬A = 0, ¬B = 1, значит 0 ∧ 1 = 0.
3Результаты 1 и 0 различаются. Отрицание нельзя просто раздать по скобкам, не поменяв знак операции.

Ответ: нет, выражения разные

Где теряют баллы

Логические операции и таблицы истинности
Ловушка: Путают приоритет: сначала НЕ, потом И, потом ИЛИ; импликацию считают ложной, когда посылка ложна.
Как решать: A → B ложна только при A = 1, B = 0. A ∧ B истинна, только когда оба 1. A ∨ B ложна, только когда оба 0.
Логические элементы и схемы
Ловушка: Конъюнктор (И) путают с дизъюнктором (ИЛИ); инвертор считают элементом с двумя входами.
Как решать: Конъюнктор И: сигнал, когда на всех входах 1. Дизъюнктор ИЛИ: хотя бы на одном. Инвертор НЕ: один вход, меняет сигнал на противоположный.

Объяснение простыми словами

Представь, что мама говорит: «Пойдёшь гулять, если сделаешь уроки И вынесешь мусор». Чтобы пойти гулять, тебе нужно выполнить оба условия сразу. А если бы она сказала «уроки ИЛИ мусор», хватило бы одного. Так в жизни работает логика, и компьютер работает по тем же правилам, только с нулями и единицами. Разберём, как с этим обращаться, чтобы уверенно решать задачи ЕНТ.

Логика работает с высказываниями. Высказывание - это утверждение, которое либо истинно, либо ложно. «Астана - столица Казахстана» истинно, «2 больше 5» ложно. Вопрос «Который час?» и приказ «Открой окно» высказываниями не являются. Истину обозначают единицей, ложь нулём, а переменные, которые принимают эти значения, называют логическими.

Дальше в Biik: продолжение объяснения, видеоразбор и проверка из 8 заданий по этой теме.

Доучи тему до конца в Biik

План на каждый день, видеоразборы, проверка из 8 заданий после каждой темы, пробник ЕНТ раз в месяц и ИИ-репетитор, который отвечает на вопросы. 3 дня бесплатно, без карты.

Начать бесплатно Пройти диагностику

Диагностика покажет, сколько баллов тебе не хватает до гранта и где именно. 30 заданий после короткой бесплатной регистрации.

Термины

Высказывание: Утверждение, про которое можно точно сказать, истинно оно или ложно.
Логическая переменная: Величина, принимающая значение 0 (ложь) или 1 (истина).
Отрицание (НЕ): Операция, меняющая истину на ложь и наоборот.
Конъюнкция (И): Логическое умножение: результат истинный, только если истинны оба высказывания.
Дизъюнкция (ИЛИ): Логическое сложение: результат истинный, если истинно хотя бы одно высказывание.
Исключающее ИЛИ (XOR): Результат истинный, когда значения высказываний различаются.
Импликация: Операция «если A, то B»; ложна только когда A истинно, а B ложно.
Эквивалентность: Операция, истинная когда оба высказывания имеют одинаковое значение.
Таблица истинности: Таблица, показывающая значения выражения при всех возможных значениях переменных.
Логическое выражение: Запись из переменных и логических операций, значение которой 0 или 1.
Приоритет операций: Порядок выполнения: скобки, НЕ, И, ИЛИ, импликация, эквивалентность.
Закон де Моргана: Правило раскрытия отрицания над скобкой: НЕ меняет И на ИЛИ и наоборот.
Тождественно истинное выражение: Выражение, которое истинно при любых значениях переменных (тавтология).
Тождественно ложное выражение: Выражение, которое ложно при любых значениях переменных.
Равносильные выражения: Выражения с одинаковыми таблицами истинности.
Логический элемент: Электронная схема, реализующая логическую операцию, например элемент И.
Сумматор: Схема из логических элементов, складывающая двоичные числа.
Круги Эйлера: Схема множеств в виде кругов, помогающая решать задачи на поисковые запросы.
Операция сравнения: Сравнение чисел, результат которого истина или ложь, например x больше 5.
Формула включений и исключений: N(A ИЛИ B) = N(A) + N(B) − N(A И B): страницы, где есть оба слова, учитываются один раз.

Все темы: Информатика