Таблицы истинности: как решать задачи по информатике

Логика и таблицы истинности в информатике

Логика — одна из самых важных тем в школьной информатике. Она встречается в контрольных, ОГЭ и ЕГЭ, а также помогает понимать условия в программировании.

Кратко о теме

В этой статье разберём:

что такое логическое высказывание;
какие бывают логические операции;
что такое таблица истинности;
как строить таблицы истинности;
как решать логические выражения;
как использовать логику в Python;
частые ошибки учеников.

Что такое логика в информатике

В информатике логика помогает работать с выражениями, которые могут быть только:

истинными;
ложными.

То есть результат логического выражения всегда один из двух:

Значение	Обозначение	Смысл
Истина	1	Условие выполняется
Ложь	0	Условие не выполняется

Пример логического высказывания

Высказывание:

5 > 3

является истинным.

Значит, его значение:

$$ 1 $$

Высказывание:

7 < 2

является ложным.

Значит, его значение:

$$ 0 $$

Что такое высказывание

Высказывание — это предложение, про которое можно точно сказать: оно истинное или ложное.

Примеры высказываний

Высказывание	Истинно или ложно
10 больше 5	Истина
3 равно 8	Ложь
Москва — столица России	Истина
2 + 2 = 5	Ложь

Не каждое предложение является высказыванием

Например:

Открой тетрадь.

Это не высказывание, потому что нельзя сказать, истинно оно или ложно.

Какой сегодня день?

Это тоже не высказывание, потому что это вопрос.

Логические переменные

В логике часто используют переменные:

$$ A,\ B,\ C $$

Каждая логическая переменная может принимать только два значения:

Значение	Смысл
1	Истина
0	Ложь

Например:

A = 1

Это значит, что высказывание A истинно.

B = 0

Это значит, что высказывание B ложно.

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

В школьной информатике чаще всего встречаются операции:

Операция	Название	Обозначение
НЕ	Отрицание	$\neg A$
И	Конъюнкция	$A \land B$
ИЛИ	Дизъюнкция	$A \lor B$
Импликация	Следование	$A \rightarrow B$
Эквивалентность	Равносильность	$A \equiv B$

Операция НЕ

НЕ меняет значение на противоположное.

Если было истинно, станет ложно. Если было ложно, станет истинно.

Обозначается так:

$$ \neg A $$

Читается:

не A

Таблица истинности для НЕ

A	$\neg A$
0	1
1	0

Пример

Пусть:

A = 1

Тогда:

$$ \neg A = 0 $$

Если:

A = 0

Тогда:

$$ \neg A = 1 $$

Операция И

И истинно только тогда, когда оба условия истинны.

Обозначается так:

$$ A \land B $$

Читается:

A и B

Таблица истинности для И

A	B	$A \land B$
0	0	0
0	1	0
1	0	0
1	1	1

Простое правило

Операция И даёт 1 только в одном случае:

1 И 1 = 1

Во всех остальных случаях результат 0.

Пример из жизни

Высказывание:

Ученик сделал домашнее задание И выучил правило.

Оно истинно только тогда, когда выполнены оба условия:

домашнее задание сделано;
правило выучено.

Если хотя бы одно условие не выполнено, всё высказывание ложно.

Операция ИЛИ

ИЛИ истинно тогда, когда хотя бы одно условие истинно.

Обозначается так:

$$ A \lor B $$

Читается:

A или B

Таблица истинности для ИЛИ

A	B	$A \lor B$
0	0	0
0	1	1
1	0	1
1	1	1

Простое правило

Операция ИЛИ даёт 0 только в одном случае:

0 ИЛИ 0 = 0

Во всех остальных случаях результат 1.

Пример из жизни

Высказывание:

Ученик получил 5 по математике ИЛИ по информатике.

Оно истинно, если ученик получил 5 хотя бы по одному предмету.

Операция импликация

Импликация — это логическая операция "если ..., то ...".

Обозначается так:

$$ A \rightarrow B $$

Читается:

если A, то B

Таблица истинности для импликации

A	B	$A \rightarrow B$
0	0	1
0	1	1
1	0	0
1	1	1

Главное правило импликации

Импликация ложна только в одном случае:

A = 1, B = 0

То есть:

из истины следует ложь

Пример

Высказывание:

Если ученик хорошо подготовился, то он написал контрольную.

Оно будет ложным только тогда, когда:

ученик хорошо подготовился;
но контрольную не написал.

Операция эквивалентность

Эквивалентность истинна тогда, когда значения двух выражений одинаковые.

Обозначается так:

$$ A \equiv B $$

Читается:

A равносильно B

или:

A тогда и только тогда, когда B

Таблица истинности для эквивалентности

A	B	$A \equiv B$
0	0	1
0	1	0
1	0	0
1	1	1

Простое правило

Эквивалентность даёт 1, если значения одинаковые:

0 и 0 → 1
1 и 1 → 1

Если значения разные, результат 0.

Приоритет логических операций

Логические операции выполняются не в любом порядке.

Сначала выполняются операции с более высоким приоритетом.

Приоритет	Операция
1	Скобки
2	НЕ
3	И
4	ИЛИ
5	Импликация
6	Эквивалентность

Пример

Дано выражение:

$$ \neg A \land B $$

Сначала выполняется:

$$ \neg A $$

Потом:

$$ \neg A \land B $$

Почему важны скобки

Выражения:

$$ \neg A \land B $$

$$ \neg(A \land B) $$

имеют разный смысл.

В первом случае отрицается только A.

Во втором случае отрицается всё выражение:

$$ A \land B $$

Что такое таблица истинности

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

Таблица истинности помогает понять, когда выражение истинно, а когда ложно.

Сколько строк в таблице истинности

Если в выражении одна переменная, то строк:

$$ 2^1 = 2 $$

Если две переменные:

$$ 2^2 = 4 $$

Если три переменные:

$$ 2^3 = 8 $$

Если четыре переменные:

$$ 2^4 = 16 $$

Формула

Если в выражении n переменных, то в таблице истинности будет:

$$ 2^n $$

строк.

Пример

Если есть переменные:

$$ A,\ B,\ C $$

то переменных 3.

Значит, строк будет:

$$ 2^3 = 8 $$

Как заполнять значения переменных

Для двух переменных таблица обычно выглядит так:

A	B
0	0
0	1
1	0
1	1

Для трёх переменных:

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

Как построить таблицу истинности

Алгоритм:

Определить все переменные.
Посчитать количество строк по формуле $2^n$.
Записать все возможные наборы значений переменных.
Разбить выражение на части.
Посчитать каждую часть.
Найти итоговый результат.

Пример 1

Построим таблицу истинности для выражения:

$$ A \land B $$

Шаг 1. Записываем все значения A и B

A	B
0	0
0	1
1	0
1	1

Шаг 2. Считаем $A \land B$

A	B	$A \land B$
0	0	0
0	1	0
1	0	0
1	1	1

Ответ

Выражение:

$$ A \land B $$

истинно только в одном случае:

A = 1 и B = 1

Пример 2

Построим таблицу истинности для выражения:

$$ A \lor B $$

Таблица

A	B	$A \lor B$
0	0	0
0	1	1
1	0	1
1	1	1

Ответ

Выражение:

$$ A \lor B $$

ложно только в одном случае:

A = 0 и B = 0

Пример 3

Построим таблицу истинности для выражения:

$$ \neg A \land B $$

Шаг 1. Записываем A и B

A	B
0	0
0	1
1	0
1	1

Шаг 2. Добавляем столбец $\neg A$

A	B	$\neg A$
0	0	1
0	1	1
1	0	0
1	1	0

Шаг 3. Считаем $\neg A \land B$

A	B	$\neg A$	$\neg A \land B$
0	0	1	0
0	1	1	1
1	0	0	0
1	1	0	0

Ответ

Выражение:

$$ \neg A \land B $$

истинно только в одном случае:

A = 0 и B = 1

Пример 4

Построим таблицу истинности для выражения:

$$ (A \lor B) \land \neg C $$

Здесь три переменные:

$$ A,\ B,\ C $$

Значит, строк будет:

$$ 2^3 = 8 $$

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

A	B	C	$A \lor B$	$\neg C$	$(A \lor B) \land \neg C$
0	0	0	0	1	0
0	0	1	0	0	0
0	1	0	1	1	1
0	1	1	1	0	0
1	0	0	1	1	1
1	0	1	1	0	0
1	1	0	1	1	1
1	1	1	1	0	0

Ответ

Выражение истинно в трёх случаях:

A = 0, B = 1, C = 0
A = 1, B = 0, C = 0
A = 1, B = 1, C = 0

Логика в Python

В Python тоже есть логические операции.

Логика	Python
НЕ	`not`
И	`and`
ИЛИ	`or`

Пример с and

a = 5

if a > 0 and a < 10:
    print("Число подходит")

Здесь проверяются два условия:

a > 0

a < 10

Оператор and требует, чтобы оба условия были истинными.

Пример с or

a = 15

if a < 0 or a > 10:
    print("Число не входит в диапазон от 0 до 10")

Оператор or требует, чтобы хотя бы одно условие было истинным.

Пример с not

is_raining = False

if not is_raining:
    print("Можно идти гулять")

Если is_raining = False, то not is_raining будет равно True.

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

Python можно использовать для проверки логических выражений.

Таблица истинности для И

for A in [0, 1]:
    for B in [0, 1]:
        result = A and B
        print(A, B, int(result))

Результат:

Таблица истинности для ИЛИ

for A in [0, 1]:
    for B in [0, 1]:
        result = A or B
        print(A, B, int(result))

Результат:

Таблица истинности для НЕ

for A in [0, 1]:
    result = not A
    print(A, int(result))

Результат:

0 1
1 0

Как решать задачи на логику

Обычно в задачах нужно:

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

Пример задачи

Дано выражение:

$$ A \land \neg B $$

Найдите, при каких значениях A и B оно истинно.

Решение

Строим таблицу:

A	B	$\neg B$	$A \land \neg B$
0	0	1	0
0	1	0	0
1	0	1	1
1	1	0	0

Ответ

Выражение истинно только при:

A = 1, B = 0

Частые ошибки учеников

Ошибка 1. Путать И и ИЛИ

Операция И требует выполнения всех условий.

1 И 1 = 1

Операция ИЛИ требует выполнения хотя бы одного условия.

1 ИЛИ 0 = 1

Ошибка 2. Забывать про приоритет операций

Например:

$$ \neg A \land B $$

Сначала выполняется:

$$ \neg A $$

и только потом:

$$ \land B $$

Ошибка 3. Неправильно считать количество строк

Если переменных 3, строк не 3, а:

$$ 2^3 = 8 $$

Если переменных 4, строк:

$$ 2^4 = 16 $$

Ошибка 4. Путать импликацию

Импликация:

$$ A \rightarrow B $$

ложна только в одном случае:

A = 1, B = 0

Во всех остальных случаях она истинна.

Мини-шпаргалка

НЕ

A	$\neg A$
0	1
1	0

И

A	B	$A \land B$
0	0	0
0	1	0
1	0	0
1	1	1

ИЛИ

A	B	$A \lor B$
0	0	0
0	1	1
1	0	1
1	1	1

Импликация

A	B	$A \rightarrow B$
0	0	1
0	1	1
1	0	0
1	1	1

Эквивалентность

A	B	$A \equiv B$
0	0	1
0	1	0
1	0	0
1	1	1

Мини-практика

Попробуйте решить самостоятельно.

Задание 1

Постройте таблицу истинности для выражения:

$$ A \lor \neg B $$

Задание 2

Найдите, при каких значениях A и B выражение истинно:

$$ A \land B $$

Задание 3

Сколько строк будет в таблице истинности для выражения с четырьмя переменными?

$$ A,\ B,\ C,\ D $$

Задание 4

Постройте таблицу истинности для выражения:

$$ \neg A \lor B $$

Ответы

Ответ к заданию 1

Выражение:

$$ A \lor \neg B $$

A	B	$\neg B$	$A \lor \neg B$
0	0	1	1
0	1	0	0
1	0	1	1
1	1	0	1

Ответ к заданию 2

Выражение:

$$ A \land B $$

истинно только тогда, когда:

A = 1 и B = 1

Ответ к заданию 3

Если переменных 4, то строк будет:

$$ 2^4 = 16 $$

Ответ:

16 строк

Ответ к заданию 4

Выражение:

$$ \neg A \lor B $$

A	B	$\neg A$	$\neg A \lor B$
0	0	1	1
0	1	1	1
1	0	0	0
1	1	0	1

Главное, что нужно запомнить

Операция	Когда истинна
НЕ	Меняет значение на противоположное
И	Когда оба условия истинны
ИЛИ	Когда хотя бы одно условие истинно
Импликация	Ложна только при $1 \rightarrow 0$
Эквивалентность	Когда значения одинаковые

Вывод

Логика и таблицы истинности помогают понять, как компьютер проверяет условия.

Эта тема важна для:

школьной информатики;
контрольных работ;
ОГЭ;
ЕГЭ;
программирования на Python.

Чтобы хорошо решать задачи по логике, нужно уметь:

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

Если освоить таблицы истинности, многие задачи по информатике станут намного проще.