Сдай ЕГЭ! Бесплатные материалы для подготовки каждую неделю!
null
Нажимая на кнопку, вы даете согласие на обработку своих персональных данных согласно 152-ФЗ. Подробнее
banner
Slider
previous arrow
next arrow
Slider

Задание 2. Построение таблиц истинности логических выражений. Строки с пропущенными значениями

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

Алгебра логики (булева алгебра) — это раздел математики, который занимается операциями и правилами, применяемыми к логическим выражениям. В алгебре логики рассматриваются высказывания, которые могут быть либо истинными, либо ложными, и на основе таких высказываний выполняются различные логические операции, такие как «и», «или», «не» и другие.

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

Примеры логических высказываний: «Сегодня идет дождь» (которое может быть истинным или ложным в зависимости от погоды), «5 больше 3» (всегда истинное) или «2 умножить на 3 равно 7» (всегда ложное). Напротив, фразы вроде «Какой красивый день!» или «Я хочу мороженое» не являются логическими высказываниями, так как у них нет определенного значения истинности.

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

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

1. Конъюнкция (логическое «И»)

Обозначения: A ∧ B, A ⋅ B, A & B, A ∩ B, A and B, AB

Конъюнкция, или логическое «И», — это операция, которая возвращает истинное значение только тогда, когда оба высказывания истинны. Если хотя бы одно из высказываний ложно, то и результат будет ложным.

Пример:

• A: «Сегодня солнечно» (истина)

• B: «Температура выше 20°C» (истина)

Результат A ∧ B: истина, если оба утверждения верны, в противном случае — ложь.

Таблица истинности для операции конъюнкции:

2. Дизъюнкция (логическое «ИЛИ»)

Обозначения: A ∨ B, A + B, A ∪ B, A or B

Дизъюнкция, или логическое «ИЛИ», возвращает истину, если хотя бы одно из высказываний истинно. Ложь получается только тогда, когда оба высказывания ложны.

Пример:

• A: «Сегодня солнечно» (истина)

• B: «Сегодня идет дождь» (ложь)

Результат A ∨ B: истина, так как хотя бы одно из утверждений истинно.

Таблица истинности для операции дизъюнкции:

3. Отрицание (логическое «НЕ»)

Обозначения: ¬A, ∼A, Ā, NOT A

Отрицание, или логическое «НЕ», меняет значение истинности высказывания на противоположное. Если исходное высказывание истинно, то результат его отрицания будет ложным, и наоборот.

Пример:

• A: «Сегодня солнечно» (истина)

• Результат ¬A: ложь (т. к. исходное высказывание было истинным).

Таблица истинности для операции отрицания:

4. Импликация (логическое «ЕСЛИ..., ТО...»)

Обозначения: A→B, A⇒B, A⊃B

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

Пример:

• A: «Если идет дождь» (истина)

• B: «Значит, улица мокрая» (истина)

Результат A→B: истина, потому что в случае дождя улица действительно мокрая.

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

5. Эквиваленция (логическое «РАВНОЗНАЧНОСТЬ»)

Обозначения: A↔B, A⇔B, A≡B

Эквиваленция — это операция, которая возвращает истину, когда оба высказывания имеют одинаковое значение истинности (оба истинны или оба ложны). Если значения истинности высказываний различны, эквиваленция будет ложной.

Пример:

• A: «Сегодня пятница» (истина)

• B: «Завтра суббота» (истина)

Результат A↔B: истина, так как оба утверждения истинны.

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

Также для решения задачи очень важно помнить про порядок выполнения логических операций:

Отрицание («НЕ», ¬) — выполняется первым, так как меняет значение истинности конкретного высказывания.

Конъюнкция («И», ∧) — выполняется следующим, объединяя высказывания так, что результат будет истинен только если оба операнда истинны.

Дизъюнкция («ИЛИ», ∨) — идет после конъюнкции, объединяя высказывания так, что результат будет истинен, если хотя бы одно из них истинно.

Импликация («ЕСЛИ..., ТО...», →) — выполняется после конъюнкции и дизъюнкции, связывая условие и следствие.

Эквиваленция («РАВНОЗНАЧНОСТЬ», ⇔) — выполняется последней, проверяя равенство значений истинности двух высказываний.

Также для решения этого задания могут понадобиться основные законы алгебры логики:

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

1. Определи количество переменных: сначала определите, сколько логических переменных используется в выражении (например, A, B, C).

2. Найди число строк: для n переменных потребуется 2^n строк, поскольку каждая переменная может принимать одно из двух значений (0 или 1), и нужно учитывать все возможные комбинации. Например, для двух переменных A и B потребуется 2^2 = 4 строки, а для трех переменных 2^3 = 8.

3. Заполни колонки переменных: создайте отдельные колонки для каждой переменной и начните заполнять их значениями 0 и 1. Распределяйте значения так, чтобы каждая переменная менялась с разной частотой:

o Для первой переменной чередуйте значения через одну строку (0, 1, 0, 1...).

o Для второй — через две строки (0, 0, 1, 1...).

o Для третьей — через четыре строки (0, 0, 0, 0, 1, 1, 1, 1...), и так далее.

4. Вычисли промежуточные результаты: если логическое выражение сложное и содержит несколько операций, добавьте столбцы для промежуточных операций, таких как ¬A, A ∧ B, A ∨ B, и заполните их значениями для каждой строки. Не забывайте про порядок выполнения логических операций!

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

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

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

Перейдём к примеру решения прототипов задач:

Разберём задачу №2 ЕГЭ 2024 из демоверсии ФИПИ:

Миша заполнял таблицу истинности логической функции F:

(x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w

но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Способ 1: программирование (python)

С помощью программы мы будем перебирать все возможные комбинации нулей и единиц (каждая наша переменная соответствует 0 или 1) и выводить те комбинации, при которых наша функция F будет равно 0 (требуется в условии в последнем столбце).

1. Нам нужно понять, каким символам в python соответствуют наши логические операции:

Отрицание («НЕ», ¬) — в языке программирования это просто not
Конъюнкция («И», ∧) — в python мы напишем and
Дизъюнкция («ИЛИ», ∨) — соответствует or
Импликация («ЕСЛИ..., ТО...», →) — пишем <= (почему это правда можно понять, составив таблицу истинности для <=, она будет совпадать с таблицей истинности для импликации)
Эквиваленция («РАВНОЗНАЧНОСТЬ», ≡) — в языке программирования это будет ==

2. Открываем нашу среду разработки (IDLE или PyCharm)

3. Пишем шаблонный код:

В первой строчке мы просто выводим наши переменные, чтобы было удобно определять, какой столбец соответствует какой переменной.

Дальше идёт вложенный цикл, в котором мы перебираем значения для каждой переменной (range (2) – это массив, который состоит из 2х значений: 0 и 1, которые и требуются для решения задачи).

Переписываем выражение из условия задачи, используя инструменты языка программирования, не забываем, как в python выглядят наши логические операции. В цикле if проверяем, равно ли наше выражение 0 (требуется по условию) и выводим только те строчки таблицы истинности, которые соответствуют нашему условию.

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

4. Смотрим на вывод нашей программы:

5. Сейчас нам нужно сопоставить таблицу из условия с результатом выполнения нашего кода:

Заметим, что в первых двух столбцах в условии совпадают значения (0, 0 и 1, 1), но в нашей программе таких совпадений несколько, тогда мы можем просто предположить, что нужные нам переменные это w и z:

Внесём в таблицу эти значения:

6. Тогда теперь мы видим, что последнему столбцу может соответствовать только переменная x, так как у y не может быть два нуля, следовательно в третьем столбце остаётся y:

7. Обязательно сравниваем получившуюся таблицу с результатом нашей программы! Видим, что они совпадают, значит мы предположили верно, пишем ответ. Если вдруг наши таблицы не совпадают, то мы предположили неверно, смотрим, какие варианты могут быть ещё и решаем заново.

Ответ: wzyx

Способ 2: аналитический

Мы просто перепишем наше выражение, используя тот факт, что конъюнкция (∧) – это логическое умножение, дизъюнкция (∨) – это логическое сложение, а для остальных операций будем перебирать все возможные комбинации.

1. Перепишем выражение из условия:

(x * ¬y) + (y == z) + ¬w = 0

2. Перебираем все возможные варианты:

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

3. ¬w = 0, тогда w всегда должно быть равно 1.

(y == z) = 0, тогда или y = 1, z = 0, или наоборот (смотрим таблицу истинности для эквиваленции)

(x * ¬y) = 0, тогда или x = 0, ¬y = 1 (y = 0), или x = 0, ¬y = 0 (y = 1), или x = 1, ¬y = 0 (y = 1)

4. Но нам важно помнить, что наши переменные в каждом слагаемом в одном случае – это всё ещё одна переменная, то есть если в первом слагаемом y = 0, то во втором он не может стать равным 1!

5. Составляем таблицу истинности:

6. Аналогично предыдущему способу решения сопоставляем таблички, пишем ответ.

Ответ: wzyx

 

Разберём задание с основной волны (08.06.24) прошлого года:

Миша заполнял таблицу истинности логической функции F = (y → ¬(x → z)) ∨ w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Решим программированием:

1. Набираем программу, аккуратно переписывая выражение из условия, правильно расставляя скобки и обращая внимание, что наша функция должна быть равна 0 (столбец F). Помним, что импликация заменяется <=:

2. Сравниваем вывод программы с таблицей из условия:

3. Предположим, что первому столбцу соответствует x (поскольку 0 и 1 содержат только столбцы x и z), тогда второму столбцу будет соответствовать z.

4. Столбец y содержит только единицы, значит он может быть только 3-м, ну и остаётся w на 4-й позиции.

5. Заполняем таблицу и сравниваем, с результатом работы нашей программы:

6. Мы видим, что получившаяся таблица совпадает с выводом программы, значит мы предположили верно, если бы мы ошиблись в предположении переменные x и z нужно было бы поменять местами.

Ответ: xzyw

Дальше разберём задание из варианта с основной волны 19.06.24 (Центр):

Миша заполнял таблицу истинности логической функции

F = ¬(x → z) ∨ (y ≡ w) ∨ y

но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Решим аналитикой:

1. Перепишем выражение из условия, используя тот факт, что конъюнкция (∧) – это логическое умножение, дизъюнкция (∨) – это логическое сложение, а для остальных операций будем перебирать все возможные комбинации:

¬ (x <= z) + (y == w) + y = 0

2. Перебираем все возможные варианты:

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

3. y всегда равен 0; (y == w) = 0, тогда они всегда должны отличаться: y = 0, w = 1 или наоборот; (¬ (x <= z)) = 0, тогда (x <= z) = 1, т.е. если x = 1, z = 1, если x = 0, z = 0 или 1.

4. Составляем нашу таблицу, но нам важно помнить, что наши переменные в каждом слагаемом в одном случае – это всё ещё одна переменная, то есть если в первом слагаемом y = 0, то во втором он не может стать равным 1!

5. Сопоставляем табличку с условием, видим, что на 4-й позиции находится w (т.к. там должны быть только единицы), на 3-й позиции y (т.к. там должны быть только нули); теперь мы видим, что когда в первом столбце стоит 1, во втором должен быть 0, такое возможно только в том случае, если z находится на первой позиции, а x на второй.

6. Заполняем таблицу из условия, сравниваем с нашей, пишем ответ.

Ответ: zxyw

Ещё одно задание из варианта с основной волны, но регион Сибирь:

Миша заполнял таблицу истинности логической функции

(¬x ∧ y ∧ z ∧ ¬w) ∨ (¬x ∧ y ∧ ¬z ∧ ¬w) ∨ (x ∧ y ∧ z ∧ ¬w)

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

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Решим программированием:

1. Набираем программу, аккуратно переписывая выражение из условия, правильно расставляя скобки и обращая внимание, что наша функция должна быть равна 1 (столбец F):

2. Сравниваем вывод программы с таблицей из условия:

3. Сопоставляем табличку с условием, видим, что на 4-й позиции находится y (т.к. там должны быть только единицы), на 2-й позиции w (т.к. там должны быть только нули); теперь мы видим, что когда в первом столбце стоит 0, в третьем должна быть 1, такое возможно только в том случае, если x находится на первой позиции, а z на третьей.

4. Заполняем таблицу и сравниваем, с результатом работы нашей программы:

Ответ: xwzy

 

Задание с основной волны 04.07.24:

Миша заполнял таблицу истинности логической функции

F = (z → ¬(y → x)) ∨ w

но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Решим аналитикой:

1. Перепишем выражение из условия, используя тот факт, что конъюнкция (∧) – это логическое умножение, дизъюнкция (∨) – это логическое сложение, а для остальных операций будем перебирать все возможные комбинации:

(z <= ¬ (y <= x)) + w = 0

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

3. w всегда равен 0; (z <= ¬ (y <= x)) = 0, тогда если z = 0:

1)¬ (y <= x) = 0 или 2) ¬ (y <= x) = 1:

1) y <= x = 1, тогда если y = 0, x = 0 или 1, если y = 1, x = 1;

2) y <= x = 0, тогда если y = 0, x не существует (вариант нам не подходит), а если y = 1, x = 0

4. Если z = 1: ¬ (y <= x) = 1, тогда смотрим вариант 2 выше.

4. Составляем нашу таблицу, но нам важно помнить, что наши переменные в каждом слагаемом в одном случае – это всё ещё одна переменная, то есть если в первом слагаемом y = 0, то во втором он не может стать равным 1!

5. Сопоставляем табличку с условием, видим, что на 1-й позиции находится z (т.к. там должны быть только единицы), на 4-й позиции w (т.к. там должны быть только нули); теперь мы видим, что когда во втором столбце стоит 0, в третьем должна быть 1, такое возможно только в том случае, если y находится на второй позиции, а x на третьей.

6. Заполняем таблицу из условия, сравниваем с нашей, пишем ответ.

Ответ: zyxw

 

Посмотрим вторую досрочную волну 2023-го года:

Миша заполнял таблицу истинности логической функции

F = ¬(y ∧ ¬x) ∧ ¬(x ≡ z) ∧ w

но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z. В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Решим программированием:

1. Набираем программу, аккуратно переписывая выражение из условия, правильно расставляя скобки и обращая внимание, что наша функция должна быть равна 1 (столбец F):

2. Сравниваем вывод программы с таблицей из условия:

3. Видим, что последнему столбцу соответствует w (т.к. должны быть только единицы). Предположим, что на 1-й позиции стоит y (должно быть 2 нуля), тогда на 3-й стоит z (должно быть 2 нуля), а на 2-й стоит x.

4. Заполняем таблицу и сравниваем, с результатом работы нашей программы:

5. Мы видим, что получившаяся таблица совпадает с выводом программы, значит мы предположили верно, если бы мы ошиблись в предположении переменные y и z нужно было бы поменять местами.

Ответ: yxzw

 

Основная волна 2023 (вторая):

Миша заполнял таблицу истинности логической функции

F = (y → x) ∧ ¬z ∧ w

но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Решим аналитикой:

1. Перепишем выражение из условия, используя тот факт, что конъюнкция (∧) – это логическое умножение, дизъюнкция (∨) – это логическое сложение, а для остальных операций будем перебирать все возможные комбинации:

(y <= x) * ¬z * w = 1

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

3. w всегда равен 1; z всегда равен 0 (т.к. ¬z = 1); (y <= x) = 1, тогда если y = 0, x = 0 или 1, если x = 1, y = 1

4. Составляем нашу таблицу, но нам важно помнить, что наши переменные в каждом слагаемом в одном случае – это всё ещё одна переменная, то есть если в первом слагаемом y = 0, то во втором он не может стать равным 1!

5. Сопоставляем табличку с условием, видим, что на 4-й позиции находится z (т.к. там должны быть только нули), на 2-й позиции x (т.к. там должны быть 2 единицы и ноль); теперь мы видим, что на 1-й позиции может быть только w (одни единицы), на 3-й позиции остаётся y.

6. Заполняем таблицу из условия, сравниваем с нашей, пишем ответ.

Ответ: wxyz

 

Основная волна 2023 (третья):

Миша заполнял таблицу истинности логической функции

F = (x → (z ≡ w)) ∨ ¬(y → w)

но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Решим программированием:

1. Набираем программу, аккуратно переписывая выражение из условия, правильно расставляя скобки и обращая внимание, что наша функция должна быть равна 0 (столбец F):

2. Сравниваем вывод программы с таблицей из условия:

3. Видим, что последнему столбцу соответствует x (т.к. должны быть только единицы). Предположим, что на 3-й позиции стоит y (должно быть 2 нуля), тогда на 2-й стоит w (т.к. когда y = 0, w = 0, а когда y = 1, w тоже = 1), а на 1-й стоит z.

4. Заполняем таблицу и сравниваем, с результатом работы нашей программы:

5. Мы видим, что получившаяся таблица совпадает с выводом программы, значит мы предположили верно, если бы мы ошиблись в предположении переменные y и z нужно было бы поменять местами.

Ответ: zwyx

Для второй задачи ЕГЭ по информатике все прототипы примерно одинаковые, их решения не будут сильно отличаться, важно быть внимательным и в конце обязательно сравнить получившуюся таблицу с таблицей из условия.

Что важно знать:

1. Выучить шаблон кода.

2. Запомнить таблицы истинности для каждой логической операции.

3. Запомнить порядок выполнения операций.

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

o «НЕ» — not

o «И» — and

o «ИЛИ» — or

o Импликация — <= (можно использовать для простоты, так как ≤\leq≤ соответствует логике импликации)

o Эквиваленция — ==

Шаблон для запоминания порядка операций:

Можно запомнить порядок выполнения операций с помощью аналогии с математикой. Например: сначала выполняется отрицание (как изменение знака в алгебре), затем идут операции конъюнкции и дизъюнкции, затем — импликация и эквиваленция. Чтобы избежать ошибок, лучше всегда использовать скобки, особенно в длинных выражениях.

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

Удачи на экзамене!

 

Поделиться страницей

Это полезно

Теория вероятностей на ЕГЭ-2025 по математике
В варианте ЕГЭ-2025 две задачи по теории вероятностей — это №4 и №5. По заданию 5 в Интернете почти нет доступных материалов. Но в нашем бесплатном мини-курсе все это есть.
ЕГЭ Математика
Олимпиада ОММО:
100 баллов за 5 задач