Алгоритм решения задания 2 ЕГЭ по информатике

Навигация по странице

О задании

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

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

Для решения задания 2 вам нужно знать базовые операции алгебры логики и порядок их выполнения. При решении этого задания с помощью программирования, также стоит внимательно изучить операторы Python, которые позволяют реализовывать соответствующие операции алгебры логики. Причем важно отметить, что порядок выполнения операторов в Python не совпадает с порядком выполнения операций алгебры логики!

Далее мы познакомимся со всеми нужными логическими операциями и рассмотрим их реализацию в Python.

Алгебра логики

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

Рассмотрим подробно, что такое алгебра логики, как она возникла, какие базовые операции ей присущи, и как применять эти знания для решения типичных задач ЕГЭ.

Идеи алгебры логики были заложены Джорджем Булем, английским математиком XIX века. В 1854 году он опубликовал свою работу «Исследование законов мышления», где представил новую систему, которая позволяла описывать логические рассуждения с помощью математических символов. Эта система получила название булевой алгебры.

Буль предложил рассматривать утверждения как переменные, которые могут принимать всего два значения: истину (1) или ложь (0). Он разработал правила для манипуляции этими утверждениями, аналогично тому, как это делается в обычной алгебре чисел. Это открытие стало основой для современной теории цифровых устройств и компьютерных наук.

Логические значения/переменные (булевы значения/переменные) — это фундаментальные элементы алгебры логики, которые могут принимать только два состояния:

Истина (True, 1)
Ложь (False, 0)

История логических значений начинается в Древней Греции. Аристотель (384-322 гг. до н.э.) первым формализовал концепцию истинности и ложности в своих трудах по логике. Он развил учение о категорических суждениях, где каждое утверждение могло быть либо истинным, либо ложным.

В средние века логикой занимались преимущественно философы и теологи. Важный вклад внесли:

Пьер Абеляр (1079-1142) – развил концепцию формальной логики. Абеляр уделял большое внимание анализу структуры высказываний и их логических связей. Он исследовал условные высказывания (например, «если А, то В») и их роль в аргументации.

Уильям Оккам (1285-1347) – разработал принципы логического вывода (см. «Бритва Оккама»). Оккам внес значительный вклад в развитие логики, особенно в области анализа высказываний и теории умозаключений. Он исследовал условные и разделительные суждения, а также разработал методы анализа сложных логических конструкций. В своей работе «Summa Logicae» Оккам систематизировал знания о логике, опираясь на идеи Аристотеля, но привнося свои оригинальные идеи.

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

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

Основные идеи, которые легли в основу булевой алгебры:

Логические переменные могут принимать только два значения: 1 (истина) или 0 (ложь).
Операции над этими переменными подчиняются определённым правилам, аналогичным обычной алгебре.
Эти правила позволяют строить сложные логические выражения и анализировать их поведение.

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

Одним из первых, кто понял потенциал булевой алгебры для технических применений, стал американский учёный Клод Шеннон. В своей магистерской диссертации «Символьный анализ реле и коммутационных цепей» (1937 год), он показал, как булева алгебра может быть использована для проектирования электрических схем.

Однако, по другим данным, тезисы, использованные в работе Шеннона, были ранее сформулированы советским логиком и электротехником В.И. Шестаковым.

В то время инженеры сталкивались с огромной сложностью при проектировании телефонных коммутаторов и других устройств, состоящих из множества переключателей и реле. Эти устройства могли находиться только в двух состояниях: включено или выключено, что напоминало два значения в булевой алгебре — 1 и 0.

Шеннон предложил следующее соответствие:

Состояние «включено» соответствует значению 1.
Состояние «выключено» соответствует значению 0.

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

Конъюнкция (A ∧ B) соответствует последовательному соединению двух переключателей: ток протекает, только если оба переключателя замкнуты.
Дизъюнкция (A ∨ B) соответствует параллельному соединению переключателей: ток протекает, если хотя бы один переключатель замкнут.
Отрицание (¬A) можно реализовать с помощью инвертора: если входное состояние равно 1, выходное будет равно 0, и наоборот.

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

Двоичная система счисления является естественным продолжением идей булевой алгебры. В двоичной системе все числа представляются комбинацией двух цифр: 0 и 1. Это совпадает с двумя возможными состояниями в булевой алгебре — истиной (1) и ложью (0).

Такая связь особенно важна для работы современных компьютеров, поскольку они основаны на цифровой логике. В компьютерах информация хранится и обрабатывается в виде битов, где каждый бит может принимать значение 0 или 1. Логические операции И (AND), ИЛИ (OR) и НЕ (NOT), применяются для манипуляции этими битами.

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

При выполнении арифметических операций (например, сложения) используются специальные логические схемы, называемые полусумматорами и сумматорами. Эти схемы основаны на булевых функциях.
Управление программами и данными осуществляется с помощью сложных логических цепочек, которые также строятся на принципах булевой алгебры.

Благодаря работам Джорджа Буля и Клода Шеннона, алгебра логики стала одним из ключевых инструментов современной технологии. Её влияние простирается от простых бытовых устройств до самых сложных суперкомпьютеров.

Давайте теперь познакомимся с основными операциями алгебры логики.

Операции алгебры логики

Инверсия

Инверсия, также известная как логическое отрицание, — это базовая операция в алгебре логики, которая меняет значение логической переменной на противоположное. Если переменная равна истине (1), её инверсия будет ложью (0), и наоборот.

В разных источниках используется несколько способов записи операции инверсии:

Математический символ: ¬ (читается «не») перед символом или же горизонтальная черта над символом
Программирование: ! или not
В некоторых текстах: ~ (тильда)

Ниже приведена таблица истинности и диаграмма Венна для инверсии.

В языке программирования Python операция инверсии реализуется с помощью оператора not. Этот оператор применяется к логическим выражениям и возвращает противоположное значение.

Рассмотрим инверсию логического значения на таком примере:

a = True
b = not a
print(b)
>>>False

Здесь мы переменной a присвоили логическое значение True. Во второй строке переменной b присваиваем инвертированное оператором not значение переменной a. В конце выводим значение b и получаем ложь (False).

Конъюнкция

Конъюнкция, также известная как логическое умножение, — это базовая операция в алгебре логики, которая истинна только тогда, когда оба её аргумента истинны. Если хотя бы один из аргументов равен лжи (0), результат будет ложью.

Способы записи:

Математический символ: ∧ или * (читается «и»)
Программирование: and
В некоторых текстах: &

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

В языке программирования Python конъюнкция реализуется с помощью оператора and. Этот оператор применяется к двум логическим выражениям и возвращает истину только если оба выражения истинны.

Пример конъюнкции в Python:

a = True
b = False
result = a and b
print(result)
>>>False

Здесь переменной a присвоено значение True, переменной b — False. Оператор and проверяет, что оба значения должны быть истинными, чтобы результат был истинным. Так как одно из значений ложно, результатом является False.

Дизъюнкция

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

Способы записи:

Математический символ: ∨ или + (читается «или»)
Программирование: or
В некоторых текстах: |

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

В языке программирования Python дизъюнкция реализуется с помощью оператора or. Этот оператор применяется к двум логическим выражениям и возвращает истину, если хотя бы одно из выражений истинно.

a = True
b = False
result = a or b
print(result)
>>>True

Здесь переменной a присвоено значение True, переменной b — False. Оператор or проверяет, что хотя бы одно из значений должно быть истинным, чтобы результат был истинным. Поскольку одно из значений истинно, результатом является True.

Импликация

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

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

В математике импликация записывается с помощью символа стрелки →.

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

Как вы уже могли догадаться по третьему абзацу, в Python нет оператора, реализующего функционал импликации. Добиться получения такой операции можно сочетанием операторов not и or.

a = True
b = False
result = not a or b
print(result)
>>>False

Здесь переменной a присвоено значение True, переменной b — False. Импликация A → B эквивалентна выражению ¬A ∨ B. В данном случае результатом является False, так как предпосылка истинна, а следствие ложно.

Но записывать импликацию, используя два оператора, не всегда удобно. Данную операцию можно заменить всего одним оператором. Давайте подумаем каким. Если внимательно посмотреть на таблицу истинности импликации, то можно понять следующее: истина получается только в том случае, если первый операнд (логическое выражение) меньше или равен второму операнду. Тогда импликация A → B будет эквивалентна выражению A <= B.

Убедиться в этом можно на примере такой программы:

a = True
b = False
result = a <= b
print(result)
>>>False

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

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

Способы записи:

Математический символ: ↔ (читается «равносильно») или ≡ (читается «тождественно равно»)
В программировании: == (оператор сравнения)

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

В Python эквивалентность можно проверить с помощью оператора ==. Этот оператор сравнивает два значения и возвращает истину, если они равны.

a = True
b = True
result = a == b
print(result)
>>>True

Здесь переменные a и b равны между собой, поэтому результатом является True. Если значения были бы разными, результат был бы False.

Порядок операций

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

Стандартный приоритет операций в алгебре логики:

Действия в скобках
Инверсия (¬)
Конъюнкция (∧)
Дизъюнкция (∨)
Импликация (→)
Эквивалентность (≡)

Логические операторы в Python имеют такой же приоритет. Но мы помним, что импликация и эквивалентность реализуются не через логические операторы, а через операторы сравнения. Операторы сравнения в Python имеют более высокий приоритет, чем логические операторы!

Стандартный приоритет соответствующих операций в Python:

Действия в скобках
Импликация (<=) или Эквивалентность (==)
Инверсия (not)
Конъюнкция (and)
Дизъюнкция (or)

Если в выражении присутствуют операции с одинаковым приоритетом, они выполняются слева направо.

Для повышения приоритета операции в Python, оборачивайте выражение с ней в скобки.

В качестве примера рассмотрим следующее логическое выражение:

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

Расшифровка выражения:

x ≡ y — эквивалентность между x и y.
¬z — инверсия переменной z.
(x ≡ y) ∧ (¬z) — конъюнкция результата эквивалентности и инверсии.
w → x — импликация между w и x.
((x ≡ y) ∧ (¬z)) ∨ (w → x) — дизъюнкция двух частей.

Порядок операций:

Вычисляем x ≡ y (эквивалентность).
Вычисляем ¬z (инверсия).
Выполняем конъюнкцию (x ≡ y) ∧ (¬z).
Вычисляем w → x (импликация).
Выполняем дизъюнкцию ((x ≡ y) ∧ (¬z)) ∨ (w → x).

В Python это выражение можно записать следующим образом:

result = ((x == y) and (not z)) or ((not w) or x)

или так:

result = ((x == y) and (not z)) or (w <= x)

Порядок операций в Python:

x == y — вычисляем эквивалентность x ≡ y.
not z — вычисляем инверсию ¬z.
(x == y) and (not z) — выполняем конъюнкцию.
not w — вычисляем инверсию ¬w.
(w <= x)— выполняем импликацию w → x.
((x == y) and (not z)) or (w <= x)— выполняем дизъюнкцию.

Вычислим значение этого выражения при таких значениях переменных:

x = Истина
y = Ложь
z = Истина
w = Ложь

Сначала решим вручную:

Вычисляем x≡y:

x ≡ y : ( Истина == Ложь ) = Ложь

Вычисляем ¬z:

¬ z : (¬ Истина )= Ложь

Выполняем конъюнкцию:

(x ≡ y) ∧ (¬ z) : ( Ложь ∧ Ложь ) = Ложь

Вычисляем w → x:

w → x : Истина → Истина = Истина

Выполняем дизъюнкцию:

((x ≡ y) ∧ (¬ z)) ∨ (w → x) : ( Ложь ∨ Истина )= Истина

Представим вычисление значения этого выражения на Python:

# Определение переменных
x = True
y = False
z = True
w = False

# Вычисление выражения
result = ((x == y) and (not z)) or (w <= x)

print(result)
>>>True

В примере выше скобки были уже расставлены в логическом выражении, так что нам было просто реализовать его на Python. Теперь пусть будет такое выражение:

F(x, y, z, w)= x ≡ y ∧ z → w

Здесь первой выполняется конъюнкция, затем импликация и третьей операцией выполняется эквивалентность.

Это выражение в Python мы не можем просто переписать, не расставляя скобок:

result = x == y and z <= w

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

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

result = x == ((y and z) <= w)

Здесь сначала выполняется конъюнкция (y and z), затем импликация ((y and z) <= w) и самой последней выполняется эквивалентность x == ((y and z) <= w).

Алгоритм решения

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

Ручное решение

Формулировка будет следующая:

Задание 200

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

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

Давайте проанализируем логическое выражение. Поскольку нам нужны только ложные значения этой функции, то оба выражения в дизъюнкции (z → ¬ (y → x)) ∨ w должны быть ложны. Значит w всегда принимает ложные значения, как и выражение z → ¬ (y → x).

Давайте начнём составлять свою таблицу истинности (не путайте с той, что представлена в условии). Заполним столбец с известной переменной w.

Переходим к выражению z → ¬ (y → x), оно ложное только тогда, когда z принимает истинные значения. Записываем это в таблицу.

Ложь рассмотренного выражения с импликацией означает, что выражение ¬ (y → x) должно быть ложно. Значит импликация y → x должна возвращать истинные значения. Тогда вспомним таблицу истинности для импликации и перепишем все возможные значения x и y, при которых импликация будет возвращать истину.

Мы заполнили свою таблицу истинности для функции, теперь давайте искать соответствия с предложенной в условии таблицей.

Для переменной w сразу находится соответствие — четвёртый столбец. Только в нём не содержится единиц и может быть 3 нуля.

Единственный оставшийся столбец без нулей отводим под переменную z.

Во втором и третьем столбцах рассмотрим последнюю строку.

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

Задание решено, в ответ пишем буквы в таком порядке: zyxw.

Пример 1

Задание 201

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

Решать эту задачу будем также вручную. Начинаем с составления собственной таблицы истинности.

В выражении мы имеем две дизъюнкции, причем само выражение должно быть ложным. Это означает, что переменная y всегда будет принимать ложные значения.

Выражение y ≡ w должно быть ложным. Следовательно, y и w имеют разные значения.

Отрицание импликации ¬ (x → z), которое должно быть ложным, говорит нам о том, что сама импликация возвращает всегда истину. Тогда переписываем из таблицы истинности импликации те значения для x и z, при которых она истинна (0 и 0, 0 и 1, 1 и 1).

Переходим к сопоставлению нашей таблицы истинности и той, которую не дописал Миша из условия этой задачи. Она очень похожа на прошлую, здесь также есть один пустой столбец, который мы отводим под w и один столбец без единиц, который отводим под y.

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

Дополним всю таблицу значениями и убедимся в правильности её построения.

Теперь мы готовы дать ответ на это задание — zxyw.

Решение перебором

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

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

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

Общий алгоритм можно расписать так:

1. Выводим буквы из условия для удобства print('x y z w')

2. В цикле перебираем все возможные значения переменных (0 и 1)

for x in 0, 1:
    for y in 0, 1:
        for z in 0, 1:
            for w in 0, 1:

3. Переписываем логическую функцию и подставляем её в условие

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

Давайте проверим этот алгоритм на задании с такой формулировкой:

Задание 202

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

Начнем с записи логической функции, она будет записываться так:

f = not (x <= w) or (y <= z) or not y

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

Нам осталось лишь дописать вложенные циклы и вывести значения на экран:

print('x y z w')
for x in 0, 1:
    for y in 0, 1:
        for z in 0, 1:
            for w in 0, 1:
                f = not (x <= w) or (y <= z) or not y
                if not f:
                    print(x, y, z, w)

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

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

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

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

В ответ пишем yxwz.

Пример 2

Задание 203

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

Сразу перейдём к составлению кода для решения данного задания:

print('x y z w')
for x in 0, 1:
    for y in 0, 1:
        for z in 0, 1:
            for w in 0, 1:
                f = (y <= x) and not z and w
                if f:
                    print(x, y, z, w)

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

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

Представим эти значения в виде таблицы.

И вернёмся к таблице истинности из условия, с которой и будем сопоставлять полученные значения. Нам повезло и столбец для переменной x уже полностью заполнен.

Две единицы могут присутствовать только в столбце с переменной w. Так что отводим первый столбец именно под неё. Тогда оставшийся пустой столбец будет для переменной z, а третий столбец отведём для y.

В ответ пишем wxyz.