Что такое логика в информатике
Раздел информатики, который называют алгеброй логики, работает с высказываниями. Высказывание — это утверждение, про которое можно точно сказать: истинно оно (1) или ложно (0). «7 > 3» — высказывание, а «Который час» — нет.
Из простых высказываний собирают сложные с помощью логических операций. Такие задания встречаются в нескольких видах:
- таблицы истинности для выражений вроде (A ∨ B) & ¬C;
- проверка высказывания на данных: например, для какой фамилии истинно «первая буква согласная И количество гласных чётно»;
- запросы к поисковому серверу и подсчёт найденных страниц;
- задачи на логику про места, рост, адреса, где нужно составить модель;
- схемы электрических цепей, например лампочка, которая загорается при большинстве голосов.
Логические операции и законы логики
Основных операций пять. Запомни, когда каждая даёт 1:
- НЕ (¬A, инверсия): меняет значение на противоположное.
- И (A & B, конъюнкция): истинно, только когда истинны оба высказывания.
- ИЛИ (A ∨ B, дизъюнкция): истинно, когда истинно хотя бы одно, в том числе оба сразу.
- Импликация (A → B, «если A, то B»): ложна только в одном случае, когда A = 1, а B = 0.
- Эквиваленция (A ≡ B): истинна, когда A и B равны.
Порядок выполнения: сначала скобки, потом НЕ, затем И, затем ИЛИ, затем импликация и эквиваленция.
Законы логики помогают упрощать выражения, не строя таблицу:
- ¬¬A = A
- A & ¬A = 0 и A ∨ ¬A = 1
- ¬(A & B) = ¬A ∨ ¬B и ¬(A ∨ B) = ¬A & ¬B (законы де Моргана)
- A ∨ A & B = A (поглощение)
Те же операции стоят за условиями в алгоритмах и исполнителях: когда пишешь «если a > 0 и b > 0», ты используешь И.
Как построить таблицу истинности: разбор
Задание: построить таблицу истинности для F = (A ∨ ¬B) & C.
Шаг 1. Считаем переменные: A, B, C, их три. Строк будет 2³ = 8, это все наборы от 000 до 111.
Шаг 2. Определяем порядок действий: сначала ¬B, потом A ∨ ¬B, потом И с C. Под каждое действие делаем отдельный столбец.
Шаг 3. Заполняем строки (A B C → ¬B → A ∨ ¬B → F):
- 000 → 1 → 1 → 0
- 001 → 1 → 1 → 1
- 010 → 0 → 0 → 0
- 011 → 0 → 0 → 0
- 100 → 1 → 1 → 0
- 101 → 1 → 1 → 1
- 110 → 0 → 1 → 0
- 111 → 0 → 1 → 1
Шаг 4. Проверяем: C = 0 в строке даёт F = 0 сразу, потому что в конъюнкции один из множителей ложен. Это быстрая проверка, что столбец заполнен верно. Итог: F = 1 в трёх строках, 001, 101 и 111.
Запросы к поисковому серверу и задачи на логику
В таких заданиях символ «|» означает ИЛИ, а «&» означает И. Запрос с ИЛИ находит больше страниц, запрос с И меньше. Главная формула: N(A | B) = N(A) + N(B) − N(A & B), потому что страницы, где есть оба слова, при сложении посчитаны дважды. Подробнее о том, как устроен поиск, написано в теме компьютерные сети и интернет.
Пример. По запросу «кошка | собака» найдено 900 тысяч страниц, по запросу «кошка» 600, по запросу «собака» 500. Сколько страниц по запросу «кошка & собака»? Подставляем: 900 = 600 + 500 − x, откуда x = 200 тысяч.
Задачи на логику про рост, места на соревнованиях или адреса решают через информационную модель: таблицу или цепочку неравенств. Например: «Оля старше Веры, но младше Нины, а Вера старше Тани». Получается цепочка Нина > Оля > Вера > Таня, и сразу видно, кто стоит рядом с Верой. В задачах про места выписывают таблицу «страна — место» и вычёркивают клетки по тем предположениям, которые заведомо ложны.
Где ошибаются чаще всего
- ИЛИ понимают как «либо одно, либо другое». В логике A ∨ B истинно и при A = 1, B = 1. Исключающего «либо» здесь нет.
- Путают порядок операций. В выражении A ∨ B & C сначала считают B & C, а потом ИЛИ. Если расставить скобки по-другому, ответ изменится.
- Ошибаются с импликацией. A → B ложна только при A = 1 и B = 0. При A = 0 она истинна, что бы ни стояло в B.
- Неверно раскрывают отрицание. ¬(A & B) не равно ¬A & ¬B. Правильно: ¬A ∨ ¬B, то есть при отрицании И меняется на ИЛИ.
- Складывают страницы в запросах без вычитания пересечения. Для «|» нужно вычесть число страниц по запросу с «&».
Какие задания по теме присылают ученики
Чаще всего присылают таблицы истинности для формул с тремя переменными, в том числе с импликацией и эквиваленцией, и задания про запросы к поисковому серверу с подсчётом страниц. Встречаются также логические модели про места на соревнованиях, задача про адрес, определение, какому столбцу таблицы соответствует переменная, и проектирование цепи для голосования.
Можно найти в списке выше похожее задание и посмотреть, как оно решено по шагам. Если своего не нашлось, сфотографируй условие и отправь: ты получишь решение с ходом, который можно сверить со своей работой.