Интернет-энциклопедия по школьным предметам от Maximum Education. Учебник поможет решить домашнее задание, подготовиться к контрольной и вспомнить прошлые темы.
Логические высказывания
Ранее речь уже шла о том, что под логической переменной может подразумеваться любое высказывание, которое мы можем определить как ложное или истинное. В задании №15 ЕГЭ по информатике, которому посвящен данный раздел теории, логической переменной может быть, например, принадлежность точки некоторому отрезку или справедливость неравенства. Например, переменная x > 10 будет Истинна (т.е. равна 1) для всех чисел, которые строго больше 10, и Ложна (т.е. равна 0) для всех остальных. А переменная B ∈ [2; 4] будет Истинна (т.е. равна 1) только для чисел, расположенных между 2 и 4, и Ложна (т.е. равна 0) для всех прочих.
Для работы с заданием №15 необходимо хорошо разбираться в двух аспектах. Первый – это работа с математической составляющей, которой посвящен урок «Математика в информатике» (см. соответствующий раздел теории). Второй аспект – это преобразование логических выражений, о чем и пойдет речь в тексте ниже.
Формулы де-Моргана. Два главных выражения
Формулами де-Моргана называются две формулы, которые выглядят следующим образом:
¬(A /\ B) = ¬A \/ ¬B и ¬(A \/ B) = ¬A /\ ¬B
Эти выражения справедливы абсолютно всегда и используются, чтобы раскрывать инверсию перед скобкой. Чтобы убедиться, что эти формулы равносильны, достаточно построить для них таблицы истинности. Для первой формулы:
| A | B | ¬(A /\ B) | ¬A \/ ¬B |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
Для второй формулы:
| A | B | ¬(A \/ B) | ¬A /\ ¬B |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
Законы алгебры логики
Далее приведены таблицы истинности для некоторых законов алгебры логики. Более подробный список см. в разделе теории «Тождества математической логики».
Свойства констант:
A /\ 1 = А
| A | 1 | A /\ 1 |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 1 | 1 |
A \/ 1 = 1
| A | 1 | A \/ 1 |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1 | 1 |
A /\ 0 = 0
| A | 0 | A /\ 0 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 0 |
A \/ 0 = A
| A | 0 | A \/ 0 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
Закон двойного отрицания:
¬(¬А) = А
| A | ¬А | ¬(¬А) |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 0 | 1 |
Законы поглощения:
А /\ (A \/ B) = A
| A | B | A \/ B | А /\ (A \/ B) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
А \/ (A /\ B) = A
| A | B | A /\ B | А \/ (A /\ B) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Законы повторения:
А /\ A = A
А \/ A = A
Переместительный закон:
А \/ В = В \/ A
А /\ B = B /\ A
Сочетательный закон:
А /\ (B /\ C) = (А /\ B) /\ C
А \/ (B \/ C) = (А \/ B) \/ C
Распределительный закон:
А /\ (B \/ C) = (А \/ B) /\ (A \/ C)
А \/ (B /\ C) = (А /\ B) \/ (A /\ C)
Поразрядная конъюнкция
Поразрядная конъюнкция – это логическая операция, которая выполняется над цифрами чисел, записанных в двоичной системе счисления. Нули и единицы в двоичной записи при этом воспринимаются как логические нули и единицы. Далее приведен алгоритм вычисления поразрядной конъюнкции:
-
перевести оба числа в двоичную систему;
-
записать разряд под разрядом;
-
дополнить числа незначащими нулями, чтобы количество разрядов было одинаковым;
-
применить конъюнкцию к каждой паре разрядов;
-
в получившемся числе убрать незначащие нули;
-
перевести число обратно в десятичную запись.
Пример вычисления поразрядной конъюнкции для чисел 18 и 43.
Переводим все в двоичную систему и записываем разряд под разрядом:
В двоичной записи числа 43 на один разряд больше, но разряды по номерам должны совпадать, поэтому у 18-ти впереди мы добавляем незначащий ноль, после чего выполняем конъюнкцию:
Получаем, что в двоичной системе счисления результат поразрядной конъюнкции равен 102. Переводим в десятичную:
Ответ: 2.