Задачи демоверсий ЕГЭ по теме "Логика"

Задачи демоверсий ЕГЭ по теме "Логика"

Рассмотрим подробно (с решениями) несколько задач из раздела «Логика» демонстрационных версий разных лет ЕГЭ по информатикe Это задачи требующие знания логических функций, методов построения таблиц истинности.

Задача 1

Дан фрагмент таблицы истинности. Какая из трех приведенных функций соответствует этому фрагменту?

x1	x2	x3	x4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

1.   (X1→X2) ∧ ¬ X3 ∨X4

2.   (X1∧X2) ∨ (¬ X3 ∧X4)

3.   ¬X1∨X2 ∨ (X3 ∧X4)

Ответ: Функция под номером 3.

Решение:

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

Задача 2:

Какое из приведенных чисел удовлетворяет условию: (цифры, начиная со старшего разряда, идут в порядке убывания) → (число - четное) ∧ (младшая цифра - четная) ∧ (старшая цифра - нечетная) Если таких чисел несколько, укажите наибольшее.

1.   13579

2.   97531

3.   24678

4.   15386

Ответ: условию удовлетворяет число под номером 4.

Решение:

Первые два числа условию не удовлетворяют уже по той причине, что младшая цифра является нечетной. Конъюнкция условий ложна, если один из членов конъюнкции ложен. Для третьего числа не выполняется условие для старшей цифры. Для четвертого числа выполняются условия, накладываемые на младшую и старшую цифры числа. Первый член конъюнкции также истинен, поскольку импликация истинна, если ее посылка ложна, что имеет место в данном случае.

Задача 3:

Два свидетеля дали следующие показания:

5.   Первый свидетель: Если А виновен, то В и подавно виновен, а С - невиновен.

6.   Второй свидетель: Виновны двое. А точно виновен и виновен один из оставшихся, но кто именно сказать не могу.

Какие заключения о виновности А, В и С можно сделать на основании свидетельских показаний?

Ответ: Из свидетельских показаний следует, что А и В виновны, а С - невиновен.

Решение:

Конечно, ответ можно дать, основываясь на здравом смысле. Но давайте рассмотрим, как это можно сделать строго и формально. Первое, что нужно сделать - это формализовать высказывания. Введем три логические переменные - А, В и С, каждая из которых имеет значение true (1), если соответствующий подозреваемый виновен. Тогда показания первого свидетеля задаются формулой:

A→(B∧¬C))

Показания второго свидетеля задаются формулой:

A ∧ ((B ∧¬C) ∨ (¬B /∧ C))

Показания обоих свидетелей полагаются истинными и представляют конъюнкцию соответствующих формул.

Построим таблицу истинности для этих показаний:

Таблица истинности. Показания

< 

A	B	C	F1	F2	F1 ∧ F2
0	0	0	0	1	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Суммарные cвидетельские показания истинны только в одном случае, приводящие к однозначному ответу - А и В виновны, а С - невиновен.

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

Логические уравнения и системы уравнений

Пусть F(x1, x2, …xn) - логическая функция от n переменных. Логическое уравнение имеет вид:

F(x1, x2, …xn) = С,

Константа С имеет значение 1 или 0.

Логическое уравнение может иметь от 0 до 2n различных решений. Если С равно 1, то решениями являются все те наборы переменных из таблицы истинности, на которых функция F принимает значение истина (1). Оставшиеся наборы являются решениями уравнения при C, равном нулю. Можно всегда рассматривать только уравнения вида:

F(x1, x2, …xn) = 1

Действительно, пусть задано уравнение:

F(x1, x2, …xn) = 0

В этом случае можно перейти к эквивалентному уравнению:

F(x1, x2, …xn) = 1

Рассмотрим систему из k логических уравнений:

F1(x1, x2, …xn) = 1

F2(x1, x2, …xn) = 1 …

Fk(x1, x2, …xn) = 1

Решением системы является набор переменных, на котором выполняются все уравнения системы. В терминах логических функций для получения решения системы логических уравнений следует найти набор, на котором истинна логическая функция Ф, представляющая конъюнкцию исходных функций F:

Ф = F1 ∧ F2 ∧… Fk

Если число переменных невелико, например, менее 5, то нетрудно построить таблицу истинности для функции Ф, что позволяет сказать, сколько решений имеет система и каковы наборы, дающие решения. В некоторых задачах ЕГЭ по нахождению решений системы логических уравнений число переменных доходит до значения 10. Тогда построить таблицу истинности становится практически неразрешимой задачей. Для решения задачи требуется другой подход. Для произвольной системы уравнений не существует общего способа, отличного от перебора, позволяющего решать такие задачи. В предлагаемых на экзамене задачах решение обычно основано на учете специфики системы уравнений. Повторяю, кроме перебора всех вариантов набора переменных, общего способа решения задачи нет. Решение нужно строить исходя из специфики системы. Часто полезно провести предварительное упрощение системы уравнений, используя известные законы логики. Другой полезный прием решения этой задачи состоит в следующем. Нам интересны не все наборы, а только те, на которых функция Ф имеет значение 1. Вместо построения полной таблицы истинности будем строить ее аналог - бинарное дерево решений. Каждая ветвь этого дерева соответствует одному решению и задает набор, на котором функция Ф имеет значение 1. Число ветвей в дереве решений совпадает с числом решений системы уравнений. Что такое бинарное дерево решений и как оно строится, поясню на примерах нескольких задач.

Задача 4

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют системе из двух уравнений?

(x1→x2) ∧(x2→x3) ∧(x3→x4) ∧(x4→x5 ) = 1

(y1→y2) ∧(y2→y3) ∧(y3→y4) ∧(y4→y5 ) = 1

Ответ Система имеет 36 различных решений.

Решение:

Найдем число решений для первого уравнения, зависящего от 5 переменных - x1, x2, …x5. Первое уравнение можно в свою очередь рассматривать как систему из 5 уравнений. Как было показано, система уравнений фактически представляет конъюнкцию логических функций. Справедливо и обратное утверждение, - конъюнкцию условий можно рассматривать как систему уравнений.

Построим дерево решений для импликации (x1→x2) - первого члена конъюнкции, который можно рассматривать как первое уравнение. Вот как выглядит графическое изображение этого дерева:

Рисунок - Дерево решений задачи 4

Дерево состоит из двух уровней по числу переменных уравнения. Первый уровень описывает первую переменную X1. Две ветви этого уровня отражают возможные значения этой переменной - 1 и 0. На втором уровне ветви дерева отражают только те возможные значения переменной X2, для которых уравнение принимает значение истина. Поскольку уравнение задает импликацию, то ветвь, на которой X1 имеет значение 1, требует, чтобы на этой ветви X2 имело значение 1. Ветвь, на которой X1 имеет значение 0, порождает две ветви со значениями X2, равными 0 и 1. Построенное дерево задает три решения, на которых импликация X1 ? X2 принимает значение 1. На каждой ветви выписан соответствующий набор значений переменных, дающий решение уравнения.

Вот эти наборы: {(1, 1), (0, 1), (0, 0)}

Продолжим построение дерева решений, добавляя следующее уравнение, следующую импликацию X2 X3. Специфика нашей системы уравнений в том, что каждое новое уравнение системы использует одну переменную из предыдущего уравнения, добавляя одну новую переменную. Поскольку переменная X2 уже имеет значения на дереве, то на всех ветвях, где переменная X2 имеет значение 1, переменная X3 также будет иметь значение 1. Для таких ветвей построение дерева продолжается на следующий уровень, но новые ветви не появляются. Единственная ветвь, где переменная X2 имеет значение 0, даст разветвление на две ветви, где переменная X3 получит значения 0 и 1. Таким образом, каждое добавление нового уравнения, учитывая его специфику, добавляет одно решение. Исходное первое уравнение:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5 ) = 1 имеет 6 решений. Вот как выглядит полное дерево решений для этого уравнения:

Рисунок - Дерево решений задачи 4 полное

Второе уравнение нашей системы аналогично первому:

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

Разница лишь в том, что в уравнении используются переменные Y. Это уравнение также имеет 6 решений. Поскольку каждое решение для переменных Xi может быть скомбинировано с каждым решением для переменных Yj, то общее число решений равно 36.

Заметьте, построенное дерево решений дает не только число решений (по числу ветвей), но и сами решения, выписанные на каждой ветви дерева.

Задача 5

Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?

(x1→x2) ∧(x2→x3) ∧(x3→x4) ∧(x4→x5 ) = 1

(y1→y2) ∧(y2→y3) ∧(y3→y4) ∧(y4→y5 ) = 1

(x1→y1) = 1

Ответ31

Решение:

Эта задача является модификацией предыдущей задачи. Разница в том, что добавляется еще одно уравнение, связывающее переменные X и Y.

Из уравнения X1 ? Y1 следует, что когда X1 имеет значение 1(одно такое решение существует), то и Y1 имеет значение 1. Таким образом, существует один набор, на котором X1 и Y1 имеют значения 1. При X1, равном 0, Y1 может иметь любое значение, как 0, так и 1. Поэтому каждому набору с X1, равном 0, а таких наборов 5, соответствует все 6 наборов с переменными Y. Следовательно, общее число решений равно 31.

Задача 6

Сколько решений имеет уравнение:

(¬X1 ∨ X2) (¬X2 ∨ X3) (¬X3 ∨ X4) ∧(¬X4 ∨ X5) ∧(¬X5 ∨ X1) = 1

Ответ: 2

Решение:

Вспоминания основные эквивалентности, запишем наше уравнение в виде:

(X1 → X2) ∧(X2 → X3) ∧(X3 → X4) ∧(X4 → X5) ∧(X5 → X1) = 1

Циклическая цепочка импликаций означает тождественность переменных, так что наше уравнение эквивалентно уравнению:

X1≡X2≡X3≡X4≡X5 = 1

Это уравнение имеет два решения, когда все Xi равны либо 1, либо 0.

Задача 7

Сколько решений имеет уравнение:

(X1 → X2) ∧(X2 → X3) ∧(X3 → X4) ∧(X4 → X2) ∧(X4→ X5) = 1

Ответ4

Решение:

Oт циклических импликаций перейдем к тождествам, переписав уравнение в виде:

(X1 → X2) ∧(X2≡X3≡X4) ∧(X4→ X5) = 1

Построим дерево решений для этого уравнения:

Рисунок - Дерево решений задачи 7

Задача 8

Сколько решений имеет следующая система уравнений?

((X1≡X2) ∧(X3≡X4)) ∧(¬(X1≡X2) /\¬(X3≡X4)) = 0

((X3≡X4) ∧(X5≡X6)) ∧(¬(X3≡X4) /\¬(X5≡X6)) = 0

((X5≡X6) ∧(X7≡X8)) ∧(¬(X5≡X6) /\¬(X7≡X8)) = 0

((X7≡X8) ∧(X9≡X10)) ∧(¬(X7≡X8) /\¬(X9≡X10)) = 0

Ответ : 31

Решение:

64

Перейдем от 10 переменных к 5 переменным, введя следующую замену переменных:

Y1 = (X1≡X2); Y2 = (X3≡X4); Y3 = (X5≡X6); Y4 = (X7≡X8); Y5 = (X9≡X10);

Тогда первое уравнение примет вид:

(Y1 ∨ Y2 ) ∧(¬Y1 ∨ ¬Y2 ) = 0

Уравнение можно упростить, записав его в виде:

(Y1≡Y2) = 0

Переходя к традиционной форме, запишем систему после упрощений в виде:

¬(Y1≡Y2) = 1

¬(Y2≡Y3) = 1

¬(Y3≡Y4) = 1

¬(Y4≡Y5) = 1

Дерево решений для этой системы простое и состоит из двух ветвей с чередующимися значениями переменных: Возвращаясь к исходным переменным X, заметим, что каждому значению переменной Y соответствует 2 значения переменных X, поэтому каждое решение в переменных Y порождает 25 решений в переменных X. Две ветви порождают 2 * 25 решений, так что общее число решений равно 64.

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

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

Если задачу трудно решить вручную, то можно поручить решение задачи компьютеру, написав соответствующую программу решения уравнений и систем уравнений.

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

Как это ни странно, но задача нахождения решений систем логических уравнений является сложной и для компьютера, оказывается и у компьютера есть свои пределы. Компьютер может достаточно просто справиться с задачами, где число переменных 20 -30, но начнет надолго задумываться на задачах большего размера. Дело в том, что функция 2n, задающая число наборов, является экспонентой, быстро растущей с увеличением n. Настолько быстро, что обычный персональный компьютер за сутки не справится с задачей, у которой 40 переменных.