Разбор задач по теме «Алгебра логики»
[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
Алгебра логики: основные понятия
Алгебра логики - раздел математики. Она оперирует логическими высказываниями.
Логическое высказывание - любое предложение в повествовательной форме, о котором можно однозначно сказать, истинно оно или ложно. Примеры логических высказываний:
"Москва - столица России" (высказывание истинно).
"После зимы наступает осень" (высказывание ложно).
Простое высказывание - логическое высказывание, состоящее из одного утверждения.
Сложное высказывание - логическое высказывание, состоящее из нескольких утверждения, объединенных с помощью "связок": союзов "и", "или (либо)", частицы "не", связки "если, то" и др. Примеры сложных высказываний:
1. "Иван сдает экзамен по физике и информатике".
Высказывание содержит два утвеждения, объединенных "и":
Утверждение1: "Иван сдает экзамен по физике".
Утверждение2: "Иван сдает экзамен по информатике".
2. "Игорь решил записаться в секцию по воллейболу или баскетболу".
Высказывание содержит два утвеждения, объединенных "или":
Утверждение1: "Игорь решил записаться в секцию по воллейболу".
Утверждение2: "Игорь решил записаться в секцию по баскетболу".
3. "Если Илья будет много готовиться самостоятельно и будет заниматься с репетитором, то он поступит в ВУЗ".
Высказывание содержит три утвеждения, объединенных связкой "если, то" и союзом "и":
Утверждение1: "Илья будет много готовиться самостоятельно".
Утверждение2: "Илья будет заниматься с репетитором".
Утверждение2: "Илья поступит в ВУЗ".
Логические операции - "связки": союзы и частицы естественного языка, образующие из простых высказываний сложные, представленные в формальном виде . Подробно основные логические операции рассмотрены в [ Cкачайте файл, чтобы посмотреть ссылку ].
Логическое выражение - простое или сложное логическое высказывание, представленное в формальном виде. Примеры логических выражений:
простое: A,
сложное: AVBC,
где A, B, C - утверждения;
·, V, - логические операции.
Законы алгебры логики - законы, позволяющие преобразовывать логические выражения. Основные законы рассмотрены в этой [ Cкачайте файл, чтобы посмотреть ссылку ].
Логическая переменная - переменная, которая может принимать значение 1 (истина) или 0 (ложь).
Логическая функция - функция, аргументы и значение которой могут принимать значение 1 (истина) или 0 (ложь).
Таблица истинности - таблица, которая используется для описания логических функций, в частности отдельных логических операций. [ Cкачайте файл, чтобы посмотреть ссылку ]
Диаграммы Эйлера-Венна - диаграммы, которые служат для наглядного представления всех вариантов пересечения нескольких множеств. В качестве множеств могут использоваться простые логические высказывания. Диаграмма строится для логического высказывания, которое содержит от одного до трех утверждений
О том, как строить такие диаграммы, можно прочесть в статье: [ Cкачайте файл, чтобы посмотреть ссылку ]. Типовые задачи на множества подробно разобраны в статье [ Cкачайте файл, чтобы посмотреть ссылку ].
Логические операции
Чаще всего используются следующие логические операции:
инверсия (отрицание, логическое не),
конъюнкция (логическое и),
дизъюнкция (логическое или),
импликация (следование),
эквивалентность (тождество).
Рассмотрим каждую из них подробно. Для описания используем [ Cкачайте файл, чтобы посмотреть ссылку ] и таблицы истинности.
Логическая операция/соответствие в русском языке
Обозначение
Диаграмма Эйлера-Венна
Таблица истинности
инверсия (отрицание, логическое "НЕ")/"...не...", "неверно, что..."
¬
[ Cкачайте файл, чтобы посмотреть картинку ]
A
¬A
0
1
1
0
конъюнкция (логическое "И")/"...и..."
·, &
[ Cкачайте файл, чтобы посмотреть картинку ]
A
B
A
·B
0
0
0
0
1
0
1
0
0
1
1
1
дизъюнкция (логическое "ИЛИ")"...или...", "...либо..."
V
[ Cкачайте файл, чтобы посмотреть картинку ]
A
B
AVB
0
0
0
0
1
1
1
0
1
1
1
1
импликация (следование)/"если...,то...", "когда..., тогда..."
[ Cкачайте файл, чтобы посмотреть картинку ]
A
B
AB
0
0
1
0
1
1
1
0
0
1
1
1
эквивалентность (тождество)"тогда и только тогда, когда"
,
·
[ Cкачайте файл, чтобы посмотреть картинку ]
A
B
AB
0
0
1
0
1
0
1
0
0
1
1
1
Основные логические операции: инверсия, конъюнкция, дизъюнкция.
Остальные логические операции можно выразить через них:
AB=¬AVB;
AB=(A
·B)V(¬A
·¬B).
Порядок выполнения логических операций в выражении (от наибольшего приоритета к наименьшему):
инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность.
Пример:
AV¬B
·CDE.
Порядок выполнения:
¬B
(¬B)
·C
AV((¬B)
·C)
(AV((¬B)
·C))D
((AV((¬B)
·C))D)E
Законы алгебры логики и операции с константами
Законы алгебры логики:
Название закона
Формулы
Закон коммутативности
AVB=BVAA
·B=B
·A
Закон ассоциативности
(AVB)VC=AV(BVC)(A
·B)
·C=A
·(B
·C)
Закон дистрибутивности
AV(B
·C)=(AVB)
·(AVC)A
·(BVC)=(A
·B)V(A
·C)
Закон двойного отрицания
¬(¬A)=A
Закон де Моргана
¬(AVB)=¬A
·¬B¬(A
·B)=¬AV¬B
Закон исключения третьего
AV¬A=1
Закон непротиворечивости
A
·¬A=0
Закон идемпотентности
AVA=AA
·A=A
Закон поглощения
AVA
·B=AA
·(AVB)=A
Операции с константами:
операции с нулем
¬0=1AV0=AA
·0=0
операции с единицей
¬1=0AV1=1A
·1=A
Перейти к статье: [ Cкачайте файл, чтобы посмотреть ссылку ]
Диаграммы Эйлера-Венна
Диаграмма Эйлера-Венна - наглядное средство для работы со множествами. На этих диаграммах изображаются все возможные варианты пересечения множеств. Количество пересечений (областей) n определяется по формуле:
n=2N,
где N - количество множеств.
Таким образом, если в задаче используется два множества, то n=22=4, если три множества, то n=23=8, если четыре множества, то n=24=16. Поэтому диаграммы Эйлера-Венна используются в основном для двух или трех множеств.
Множества изображаются в виде кругов (если используется 2-3 множества) и эллипсов (если используется 4 множества), помещенных в прямоугольник (универсум).
Универсальное множество (универсум) U (в контексте задачи) - множество, содержащее все элементы рассматриваемой задачи: элементы всех множеств задачи и элементы, не входящие в них.
Пустое множество Ш (в контексте задачи) - множество, не содержащее ни одного элемента рассматриваемой задачи.
На диаграмме строят пересекающиеся множества, заключают их в универсум. Выделяют области, количество которых равно количеству пересечений.
Диаграммы Эйлера-Венна также используются для визуального представления логических операций.
Разберем примеры построения диаграмм Эйлера-Венна для двух и трех множеств.
Пример 1
Пусть есть следующие множества чисел:
А={1,2,3,4}
В={3,4,5,6}
Универсум U={0,1,2,3,4,5,6}
Диаграммы Эйлера-Венна для двух множеств А и В:
[ Cкачайте файл, чтобы посмотреть картинку ]
Определим области, и числа которые им принадлежат:
А
B
Обозначениеобласти
Числа
0
0
0)
0
0
1
1)
5,6
1
0
2)
1,2
1
1
3)
3,4
Пример 2
Пусть есть следующие множества чисел:
А={1,2,3,4}
В={3,4,5,6}
С={1,3,6,7}
Универсум U={0,1,2,3,4,5,6,7}
Диаграммы Эйлера-Венна для трех множеств А, В, С:
[ Cкачайте файл, чтобы посмотреть картинку ]
Определим области, и числа которые им принадлежат:
А
B
C
Обозначениеобласти
Числа
0
0
0
0)
0
0
0
1
1)
7
0
1
0
2)
5
0
1
1
3)
6
1
0
0
4)
2
1
0
1
5)
1
1
1
0
6)
4
1
1
1
7)
3
Пример 3
Пусть есть следующие множества чисел:
А={0,1,2,3,4,5,6,7}
В={3,4,5,7,8,9,10,13}
С={0,2,3,7,8,10,11,12}
D={0,3,4,6,9,10,11,14}
Универсум U={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
Диаграммы Эйлера-Венна для четырех множеств А, В, С, D:
[ Cкачайте файл, чтобы посмотреть картинку ]
Определим области, и числа которые им принадлежат:
А
B
C
D
Обозначениеобласти
Числа
0
0
0
0
0)
15
0
0
0
1
1)
14
0
0
1
0
2)
12
0
0
1
1
3)
11
0
1
0
0
4)
13
0
1
0
1
5)
9
0
1
1
0
6)
8
0
1
1
1
7)
10
1
0
0
0
8)
1
1
0
0
1
9)
6
1
0
1
0
10)
2
1
0
1
1
11)
0
1
1
0
0
12)
5
1
1
0
1
13)
4
1
1
1
0
14)
7
1
1
1
1
15)
3
Если Вы хотите порешать типовые задач на множества, то перейдите к статье:[ Cкачайте файл, чтобы посмотреть ссылку ]. Там подробно разобрано 5 задач.
Разбор задачи A3 (демо ЕГЭ 2013)
Дан фрагмент таблицы истинности выражения F.
№ области
x1
x2
x3
x4
x5
x6
x7
F
1
1
1
0
1
1
1
1
0
2
1
0
1
0
1
1
0
0
3
0
1
0
1
1
0
0
1
Каким из приведённых ниже выражений может быть F?
¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7
¬x1 \/ x2 \/ ¬x3 \/ x4 \/ ¬x5 \/ ¬x6 \/ x7
x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7
x1 \/ ¬x2 \/ x3 \/ ¬x4 \/ ¬x5 \/ x6 \/ ¬x7
Решение:
Сначала определим, как связаны переменные в F: с помощью конъюнкции (
·) или дизъюнкции (V).
Если выражение содержит только конъюнкции, то оно может быть истинно только на одной области.
В данном случае F истинна (равна 1) на одной области (область №3 в таблице выше), поэтому начнем с проверки выражений, содержащих конъюнкции. Это вариант 1 и вариант 3.
x1
x2
x3
x4
x5
x6
x7
F
F=¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7(вариант 1)
F=x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7(вариант 3)
1
1
0
1
1
1
1
0
0
·1
·1
·1
·1
·0
·0=0
1
·0
·0
·0
·1
·1
·0=0
1
0
1
0
1
1
0
0
0
·0
·0
·0
·1
·0
·1=0
1
·1
·1
·1
·1
·1
·1=1
0
1
0
1
1
0
0
1
1
·1
·1
·1
·1
·1
·1=1
Получили вариант 1: ¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7
Разбор задачи A3 (демо ЕГЭ 2012)
Время выполнения-2 мин, уровень сложности-базовый
Дан фрагмент таблицы истинности выражения F:
X
Y
Z
F
0
0
0
0
0
0
1
0
1
1
1
1
Каким выражением может быть F?
X /\ Y /\ Z
¬X \/ ¬Y \/ Z
X \/ Y \/ Z
¬X /\ ¬Y /\ ¬Z
Решение:
Будем решать подстановкой предлагаемых вариантов.
F=X
·Y
·Z=1 только в случае,когда X,Y,Z=1. В остальных случаях F=0. Проверяем по таблице. Подходит.
F=¬XV¬YVZ. Подставляем значения из таблицы:
1V1V0=1.F=0. Следовательно, не подходит.
F=XVYVZ=0 тольков случае,когда X,Y,Z=0.В остальных случаях F=1. Проверяем по таблице. Не подходит.
F=¬X
·¬Y
·¬Z. Подставляем значения из таблицы:
1
·1
·1=1.F=0. Следовательно, не подходит.
Разбор задачи A9 (демо ЕГЭ 2011)
Время выполнения-2 мин, уровень сложности-базовый
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.Дан фрагмент таблицы истинности выражения F:
X
Y
Z
F
0
1
1
0
1
1
1
1
0
0
1
1
Какое выражение соответствует F?
X /\ ¬Y /\ ¬Z
¬X /\ ¬Y /\ Z
¬X \/ ¬Y \/ Z
X \/ ¬Y \/ ¬Z
Решение:
Будем решать подстановкой предлагаемых вариантов.
F=X
·¬Y
·¬Z.Подставляем значения из таблицы:
0
·0
·0=0. F=0.
1
·0
·0=0. F=1.Следовательно, не подходит.
F=¬X
·¬Y
·Z. Подставляем значения из таблицы:
1
·0
·1=0.F=0.
0
·0
·1=0. F=1.Следовательно, не подходит.
F=¬XV¬YVZ. Подставляем значения из таблицы:
1V0V1=1.F=0.Следовательно, не подходит.
F=XV¬YV¬Z.Подставляем значения из таблицы:
0V0V0=0.F=0.
1V0V0=1.F=1.
0V1V0=1.F=1.
Следовательно, F=XV¬YV¬Z подходит.
Разбор задачи A9 (демо ЕГЭ 2010)
Уровень сложности-базовый
Дан фрагмент таблицы истинности выражения F:
X
Y
Z
F
1
1
1
1
1
1
0
1
1
0
1
1
Каким выражением может быть F?
X /\ Y /\ Z
¬X \/ ¬Y \/ Z
X \/ Y \/ Z
X /\ Y /\ ¬Z
Решение:
Будем решать подстановкой предлагаемых вариантов.
F=X
·Y
·Z=1 только в случае,когда X,Y,Z=1. В остальных случаях F=0. Проверяем по таблице. Не подходит.
F=¬XV¬YVZ.Подставляем значения из таблицы:
0V0V1=1.F=1.
0V0V0=0.F=1.Следовательно, не подходит.
F=XVYVZ=0 тольков случае,когда X,Y,Z=0.В остальных случаях F=1. Проверяем по таблице. Подходит.
F=¬X
·¬Y
·¬Z.Подставляем значения из таблицы:
0
·0
·0=0.F=1. Следовательно, не подходит.
Разбор задачи A9 (демо ЕГЭ 2009)
Время выполнения-2 мин, уровень сложности-базовый
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.Дан фрагмент таблицы истинности выражения F:
X
Y
Z
F
1
0
0
1
0
0
0
1
1
1
1
0
Какое выражение соответствует F?
¬X /\ ¬Y /\ ¬Z
X /\ Y /\ Z
X \/ Y \/ Z
¬X \/ ¬Y \/ ¬Z
Решение:
Будем решать подстановкой предлагаемых вариантов.
F=¬X
·¬Y
·¬Z.Подставляем значения из таблицы:
0
·1
·1=0.F=1. Следовательно, не подходит.
F=X
·Y
·Z=1 только в случае,когда X,Y,Z=1. В остальных случаях F=0. Проверяем по таблице. Не подходит.
F=XVYVZ=0 тольков случае,когда X,Y,Z=0.В остальных случаях F=1. Проверяем по таблице. Не подходит.
F=¬XV¬YV¬Z.Преобразуем:¬(X
·Y
·Z). ¬(X
·Y
·Z)=0 только в случае, когда X,Y,Z=1.В остальных случаях F=1. Проверяем по таблице. Подходит.
Разбор задачи B12 (демо ЕГЭ 2013)
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос
Найдено страниц(в тысячах)
Фрегат | Эсминец
3400
Фрегат & Эсминец
900
Фрегат
2100
Какое количество страниц (в тысячах) будет найдено по запросу Эсминец? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Ответ: 2200
Решение:
Изобразим запросы в виде [ Cкачайте файл, чтобы посмотреть ссылку ].
Запрос "Фрегат" обозначим символом "Ф", "Эсминец" - символом "Э".
[ Cкачайте файл, чтобы посмотреть картинку ]
Э=(Ф|Э)-Ф+(Ф&Э)=3400-2100+900=2200.
Разбор задачи A10 (демо ЕГЭ 2011)
Время выполнения-1 мин, уровень сложности-базовый
Укажите, какое логическое выражение равносильно выражению A \/ ¬( ¬B \/ ¬C):
¬A \/ B \/ ¬C
A \/ (B /\ C)
A \/ B \/ C
A \/ ¬B \/ ¬C
Решение:
AV¬(¬BV¬C)=A¬¬(B
·C)-вынесли за скобки операцию отрицания
AV¬¬(B
·C)=AV(B
·C)-двойное отрицание логического выражения дает просто выражение.
Получилось: AV(B
·C).
Разбор задачи A8 (демо ЕГЭ 2010)
Уровень сложности-базовый
Какое логическое выражение равносильно выражению ¬ (¬A \/ ¬B) /\ C
¬A \/ B \/ ¬C
A /\ B /\ C
(A \/ B) /\ C
(¬A /\ ¬B) \/ ¬C
Решение:
¬(¬АV¬B)
·C=¬¬(A
·B)
·C-вынесли отрицание за скобки
¬¬(A
·B)
·C=A
·B
·C-двойное отрицание логического выражения дает просто выражение.
Получилось: A
·B
·C.
Разбор задачи A8 (демо ЕГЭ 2009)
Укажите, какое логическое выражение равносильно выражению A /\ ¬ (¬B \/ C).
¬A \/ ¬B \/ ¬C
A /\ ¬B /\ ¬C
A /\ B /\ ¬C
A /\ ¬B /\ C
Решение:
A
·¬(¬BVC)=A
·¬¬(B
·¬C)-вынесли отрицание за скобки
A
·¬¬(B
·¬C)=A
·B
·¬C-двойное отрицание логического выражения дает просто выражение.
Получилось: A
·B
·¬C.
Разбор задачи A8 (демо ЕГЭ 2009)
Укажите, какое логическое выражение равносильно выражению A /\ ¬ (¬B \/ C).
¬A \/ ¬B \/ ¬C
A /\ ¬B /\ ¬C
A /\ B /\ ¬C
A /\ ¬B /\ C
Решение:
A
·¬(¬BVC)=A
·¬¬(B
·¬C)-вынесли отрицание за скобки
A
·¬¬(B
·¬C)=A
·B
·¬C-двойное отрицание логического выражения дает просто выражение.
Получилось: A
·B
·¬C.
Разбор задачи A10 (демо ЕГЭ 2013)
На числовой прямой даны два отрезка: P = [2, 10] и Q = [6, 14]. Выберите такой отрезок A, что формула ( (x
· А) (x
· P) ) \/ (x
· Q) тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
[0, 3]
[3, 11]
[11, 15]
[15, 17]
Решение:
Нужно решить уравнение: ( (x
· А) (x
· P) ) \/ (x
· Q)=1.
1 способ
Будем решать методом от противного. Пусть ( (x
· А) (x
· P) ) \/ (x
· Q)=0.
Преобразуем данное уравнение в систему уравнений:
[ Cкачайте файл, чтобы посмотреть картинку ]
Отрезки P и Q нам заданы, изобразим их:
[ Cкачайте файл, чтобы посмотреть картинку ]
Mы можем решить уравнения (2) и (3) в системе. x
·P=0 => x
·P. Аналогично, x
·Q.
[ Cкачайте файл, чтобы посмотреть картинку ]
Получили интервал: (
·
·;2)
·[14;+
·).
Мы решали методом от противного, поэтому инвертируем полученный интервал: [2;14].
Рассмотрим предложенные варианты:
[0, 3] - не подходит;
[3, 11] - подходит, т.к. [3, 11] включен в [2;14];
[11, 15] - не подходит;
[15, 17] - не подходит;
Получили, А
·[3; 11]
2 способ
Решим уравнение: ( (x
· А) (x
· P) ) \/ (x
· Q)=1 методом подстановки.
В уравнение вместо P, Q впишем сами отрезки: [2, 10] и [6, 14].
(x
· А)=1 для всех вариантов.
Вариант ответа
Интервал A
Значения x для проверки(границы интервала)
((x
· А) (x
· [2, 10]) ) \/ (x
· [6, 14])
1
[0, 3]
0,3
(10)V0=0(11)V0=1
2
[3, 11]
3,11
1(10)V1=1
3
[11, 15]
11,15
1(10)V0=0
4
[15, 17]
15,17
0(10)V0=0
В таблице розовым выделен искомый интервал.
Разбор задачи A15 (демо ЕГЭ 2011)
Время выполнения-2 мин, уровень сложности-повышенный
Какое из приведенных имен удовлетворяет логическому условию:¬ (последняя буква гласная первая буква согласная) /\ вторая буква согласная
ИРИНА
АРТЕМ
СТЕПАН
МАРИЯ
Решение:
Имя должно удовлетворять условию, значит, F=1.
Заменим выражения на логические переменные:
последняя буква гласная-А
первая буква согласная-В
вторая буква согласная-С
¬(AB)
·C=1.
Расставляем приоритеты логических операций. Сначала должна выполняться отрицание, затем конъюнкция.Чтобы выражение было равно 1,необходимо, чтобы ¬(AB)=1 и C=1.
Преобразуем первое выражение:¬(AB)=1. Отрицание логического выражения истинно, когда ложно это логическое выражение:(AB)=0
Рассмотрим (AB)=0. Импликация равна 0 только в одном случае, когда A=1,B=0.
Таблица истинности для AB:
А
В
AB
0
0
1
0
1
1
1
0
0
1
1
1
Поэтому имя должно удовлетворять условиям: А=1,В=0,С=1.
Теперь будем проверять каждое имя.
ИРИНА: А=1,В=0,С=1.Следовательно,это имя подходит.
АРТЕМ: А=0,В=0,С=1.Следовательно,это имя не подходит.
СТЕПАН: А=0,В=1,С=1.Следовательно,это имя не подходит.
МАРИЯ: А=1,В=1,С=0.Следовательно,это имя не подходит.
Разбор задачи A7 (демо ЕГЭ 2010)
Уровень сложности-повышенный
Какое из приведенных имен удовлетворяет логическому условию¬ (первая буква гласная вторая буква гласная) /\ последняя буква гласная
ИРИНА
МАКСИМ
АРТЕМ
МАРИЯ
Решение:
Имя должно удовлетворять условию, значит, F=1.
Заменим выражения на логические переменные:
первая буква гласная-А
вторая буква гласная-В
последняя буква гласная -С
¬(AB)
·C=1.
Расставляем приоритеты логических операций. Сначала должна выполняться отрицание, затем конъюнкция.Чтобы выражение было равно 1,необходимо, чтобы ¬(AB)=1 и C=1.
Преобразуем первое выражение:¬(AB)=1. Отрицание логического выражения истинно, когда ложно это логическое выражение:(AB)=0
Рассмотрим (AB)=0. Импликация равна 0 только в одном случае, когда A=1,B=0.
Таблица истинности для AB:
А
В
AB
0
0
1
0
1
1
1
0
0
1
1
1
Поэтому имя должно удовлетворять условиям: А=1,В=0,С=1.
Теперь будем проверять каждое имя.
ИРИНА: А=1,В=0,С=1. Следовательно,это имя подходит.
МАКСИМ: А=0,В=1,С=0. Следовательно,это имя не подходит.
АРТЕМ: А=1,В=0,С=0. Следовательно,это имя не подходит.
МАРИЯ: А=0,В=1,С=1. Следовательно,это имя не подходит.
Разбор задачи A7 (демо ЕГЭ 2009)
Время выполнения-3 мин, уровень сложности-повышенный
Для какого из указанных значений X истинно высказывание ¬ ((X>2) (X>3))?
1
2
3
4
Решение:
Высказывание истинно,значит, F=1
Заменим выражения:
(X>2) - A.
(X>3) - B.
Получим логическое выражение:
¬(AB)=1.
Отрицание логического выражения истинно, когда ложно это логическое выражение:(AB)=0.
Рассмотрим (AB)=0. Импликация равна 0 только в одном случае, когда A=1,B=0.
Таблица истинности для AB:
А
В
AB
0
0
1
0
1
1
1
0
0
1
1
1
Поэтому должны удовлетворяться условия: А=1,В=0.
Переходим обратно к неравенствам:
(X>2)=1
(X>3)=0
Поэтому X>2 и X
·3.
[ Cкачайте файл, чтобы посмотреть картинку ]
X принадлежит (2,3]
В ответе перечислены цифры:1,2,3,4. 1 и 4 не входят в область, 2-выколота. Подходит только цифра 3.
Разбор задачи A10 (демо ЕГЭ 2012)
Время выполнения-2 мин, уровень сложности-повышенный
Какое из приведённых имён удовлетворяет логическому условию:(первая буква согласная вторая буква согласная) /\ (предпоследняя буква гласная последняя буква гласная)?
КРИСТИНА
МАКСИМ
СТЕПАН
МАРИЯ
Решение:
Имя должно удовлетворять условию, значит, F=1.
Заменим выражения на логические переменные:
первая буква согласная-А
вторая буква согласная-В
предпоследняя буква гласная-С
последняя буква гласная-D
(AB)
·(CD)=1.
Расставляем приоритеты логических операций. Сначала должна выполняться конъюнкция.Чтобы выражение было равно 1,необходимо, чтобы (AB)=1 и (CD)=1.
Теперь рассмотрим импликации. В каждой из них есть по 3 возможных варианта, когда импликация равна 1.
AB=1.
А
В
AB
0
0
1
0
1
1
1
0
0
1
1
1
CD=1.
C
D
СD
0
0
1
0
1
1
1
0
0
1
1
1
Теперь будем проверять каждое имя.
КРИСТИНА: А=1,В=1,С=0,D=1.AB=1.CD=1.Следовательно,это имя подходит.
МАКСИМ: А=1,В=0,С=1,D=0.AB=0.CD=0.Следовательно,это имя не подходит.
СТЕПАН: А=1,В=1,С=1,D=0.AB=1.CD=0.Следовательно,это имя не подходит.
МАРИЯ: А=1,В=0,С=1,D=1.AB=0.CD=1.Следовательно,это имя не подходит.
Разбор задачи B12 (демо ЕГЭ 2012)
Время выполнения-2 мин, уровень сложности-повышенный
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&».В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос
Найдено страниц(в тысячах)
Шахматы | Теннис
7770
Теннис
5500
Шахматы & Теннис
1000
Какое количество страниц (в тысячах) будет найдено по запросу Шахматы?Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Ответ: 3270
Решение:
Изобразим запросы в виде [ Cкачайте файл, чтобы посмотреть ссылку ].
Запрос "Шахматы" обозначим символом "Ш", "Теннис" - символом "Т".
[ Cкачайте файл, чтобы посмотреть картинку ]
Ш=(Ш|Т)-Т+(Ш&Т)=7770-5500+1000=3270.
Разбор задачи B9 (демо ЕГЭ 2011)
Время выполнения-3 мин, уровень сложности-повышенный
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&».В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос
Найдено страниц(в тысячах)
Крейсер | Линкор
7000
Крейсер
4800
Линкор
4500
Какое количество страниц (в тысячах) будет найдено по запросу Крейсер & Линкор ?Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Ответ: 2300
Решение:
Изобразим запросы в виде диаграмм Эйлера-Венна. Запрос "Крейсер" обозначим символом "К", "Линкор" - символом "Л".
[ Cкачайте файл, чтобы посмотреть картинку ]
К&Л=К+Л-К|Л=4800+4500-7000=2300.
Разбор задачи B7 (демо ЕГЭ 2011)
Время выполнения-8 мин, уровень сложности-повышенный
Девять школьников, остававшихся в классе на перемене, были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал, были получены следующие ответы:Володя: «Это сделал Саша».Аня: «Володя лжет!»Егор: «Маша разбила».Саша: «Аня говорит неправду!»Рома: «Разбила либо Маша, либо Нина»Маша: «Это я разбила!»Нина: «Маша не разбивала!»Коля: «Ни Маша, ни Нина этого не делали».Олег: «Нина не разбивала!»Кто разбил окно, если известно, что из этих девяти высказываний истинны только три?Ответ запишите в виде первой буквы имени.
Ответ: Н
Решение:
Найдем, какие имена в ответах упоминаются чаще всего. Это имена: Маша (упоминается 4 раза) и Нина (упоминается 3 раза).
Введем обозначение: "+"-говорит правду(высказывание истинно), "-"-лжет(высказывание ложно).
Пусть Маша разбила, тогда:
Володя- Аня+ Егор+ Саша- Рома+ Маша+ Нина- Коля- Олег+.
Получили 5 истинных высказываний (выделены розовым). Это не удовлетворяет условию. Должно быть 3 истинных высказывания.
Пусть Нина разбила, тогда:
Володя- Аня+ Егор- Саша- Рома+ Маша- Нина+ Коля- Олег-.
Получили 3 истинных высказываний (выделены розовым). Это удовлетворяет условию.
Получили, что окно разбила Нина или Н.
Разбор задачи B10 (демо ЕГЭ 2010)
Уровень сложности-повышенный
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – &.
№
Запрос
1
канарейки | щеглы | содержание
2
канарейки & содержание
3
канарейки & щеглы & содержание
4
разведение & содержание & канарейки & щеглы
Ответ: 4321
Решение:
Изобразим запросы в виде диаграмм Эйлера-Венна. Запрос "канарейки" обозначим символом "К", "щеглы" - символом "Щ", "содержание"-символом "С", "разведение"-символом "Р".
[ Cкачайте файл, чтобы посмотреть картинку ]
Из рисунка видно,что при запросе Р&С&К&Щ-количество страниц будет минимальным, далее по возрастанию страниц: К&Щ&С, К&С и последнее(максимальное количество страниц)-К|Щ|С. Получается: 4,3,2,1.
Разбор задачи B10 (демо ЕГЭ 2009)
Время выполнения-3 мин, уровень сложности-повышенный
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – &.
№
Запрос
1
принтеры & сканеры & продажа
2
принтеры & продажа
3
принтеры | продажа
4
принтеры | сканеры | продажа
Ответ: 1234
Решение:
Изобразим запросы в виде диаграмм Эйлера-Венна. Запрос "принтеры" обозначим символами "Прн", "сканеры" - символом "С", "продажа"-символами "Прд".
[ Cкачайте файл, чтобы посмотреть картинку ]
Из рисунка видно,что минимальное количество страниц дает запрос: Прн&С&Прд. Далее по возрастанию страниц идут запросы: Прн&Прд, Прн|Прд и последнее(максимальное количество страниц)-Прн|С|Прд. Получается: 1,2,3,4.
Разбор задачи B15 (демо ЕГЭ 2013)
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2 y3, y4, которые удовлетворяют всем перечисленным ниже условиям? (x1 x2) /\ (x2 x3) /\ (x3 x4) = 1 (¬y1 \/ y2) /\ (¬y2 \/ y3) /\ (¬y3 \/ y4) = 1 (y1 x1) /\ (y2 x2) /\ (y3 x3) /\ (y4 x4) = 1 В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, y1, y2 y3, y4, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Ответ: 15
Решение:
Преобразуем систему уравнений к виду:
(x1 x2) /\ (x2 x3) /\ (x3 x4) = 1 (1)
(y1 y2) /\ (y2 y3) /\ (y3 y4) = 1 (2)
(y1 x1) /\ (y2 x2) /\ (y3 x3) /\ (y4 x4) = 1 (3)
Розовым выделено уравнение, которое было преобразовано. ¬y1 \/ y2=y1 y2. Аналогично и для остальных частей данного уравнения.
Решим уравнение (1).
1 способ
Уравнение (1) содержит импликации (), связанные конъюнкцией (/\). Соответственно, чтобы уравнение было истинно, все входящие импликации должны быть истинны:
x1 x2=1,
x2 x3=1,
x3 x4=1.
Таблица истинности для импликации на примере x1 x2:
x1
x2
x1x2
0
0
1
0
1
1
1
0
0
1
1
1
Розовым выделена комбинация, когда импликация ложна. Видно, что в ней идут подряд "1" и "0". Выпишем комбинации для x1x2x3x4, в которых не встречается подряд "1" и "0", чтобы импликации x1 x2, x2 x3, x3 x4 не были равны 0-ю.
x1
x2
x3
x4
0
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
1
1
1
1
Получили 5 комбинаций.
2 способ
Решим методом от противного. Рассмотрим случаи, когда уравнение (x1 x2) /\ (x2 x3) /\ (x3 x4)=0.
Импликация ложна, когда посылка истинна, а следствие ложно. Таблица истинности приведена выше:
Исходя из этого определим случаи, когда импликация ложна.
Если x1 x2=0:
x1
x2
x3
x4
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
x1=1, x2=0,
x3 и x4 - 0 или 1, поэтому они дают 22=4 комбинации.
Если x2 x3=0:
x1
x2
x3
x4
0
1
0
0
0
1
0
1
1
1
0
0
1
1
0
1
x2=1, x3=0,
x1 и x4 - 0 или 1, поэтому они дают 4 комбинации.
Если x3 x4=0:
x1
x2
x3
x4
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
0
x3=1, x4=0,
x1 и x2 - 0 или 1, поэтому они дают 4 комбинации.
Получили 4*3=12 комбинаций.
Также нужно учеть повторные комбинации. В данном случае повторная комбинация одна: 1010. В таблицах выше такая комбинация выделена синей рамкой. Она встретилась 2 раза, поэтому общее число комбинаций с учетом повторов:
12
·1=11.
Мы решали уравнение методом от противного. Теперь перейдем к исходному уравнению.
Общее число комбинаций при 4-х переменных: 24=16. 16-11=5 комбинаций.
Перейдем к уравнению (2):
(y1 y2) /\ (y2 y3) /\ (y3 y4) = 1.
Это уравнение содержит переменные y1, y2, y3, y4, которые не связаны с уравнением (1). Уравнения (1) и (2) независимы друг от друга. Но вид уравнения (2) аналогичен виду уравнения (1), которое мы решили выше. Поэтому получаем 5 комбинаций.
y1
y2
y3
y4
0
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
1
1
1
1
Добавим к системе уравнение (3):
(y1 x1) /\ (y2 x2) /\ (y3 x3) /\ (y4 x4) = 1
Выпишем рядом решения уравнений (1) и (2)
y1
y2
y3
y4
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
Будем решать систему уравнений методом от противного. Уравнение (3) равно 0-ю.
y1 x1=0:
y1=1, x1=0
y1
y2
y3
y4
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
Получили 4 комбинации.
y2 x2=0:
y2=1, x2=0. Строку 1111 (y1y2y3y4) не берем во избежания повторов.
y1
y2
y3
y4
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
Получили 3 комбинации.
y3 x3=0
y3=1, x3=0. Строки 1111, 0111 (y1y2y3y4) не берем во избежания повторов.
y1
y2
y3
y4
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
Получили 2-е комбинации.
y4 x4=0
y4=1, x4=0. Строки 1111, 0111, 0011 (y1y2y3y4) не берем во избежания повторов.
y1
y2
y3
y4
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
Получили 1-у комбинацию.
Всего комбинаций: 4+3+2+1=10.
Мы решали систему уравнений методом от противного. Теперь перейдем к исходной системе.
Общее число комбинаций: 5*5=25. Уравнения (1) и (2) дают по 5 независимых комбинаций.
25-10=15 комбинаций.
Разбор задачи B15 (демо ЕГЭ 2012)
Время выполнения-10 мин, уровень сложности-высокий
Сколько существует различных наборов значений логических переменных x1,x2, ... x9, x10, которые удовлетворяют всем перечисленным ниже условиям?
((x1
· x2) \/ (x3
· x4)) /\ (¬(x1
· x2) \/ ¬(x3
· x4)) =1((x3
· x4) \/ (x5
· x6)) /\ (¬(x3
· x4) \/ ¬(x5
· x6)) =1...((x7
· x8) \/ (x9
· x10)) /\ (¬(x7
· x8) \/ ¬(x9
· x10)) =1
В ответе не нужно перечислять все различные наборы значений x1, x2, ... x9, x10, при которых выполнена данная система
Ответ: 64
Решение:
Проведем замену:
(x1
· x2)=y1
(x3
· x4)=y2
(x5
· x6)=y3
(x7
· x8)=y4
(x9
· x10)=y5
Перепишем систему уравнений с учетом замены:
(y1Vy2)
·(¬y1V¬y2)=1
(y2Vy3)
·(¬y2V¬y3)=1
....
(y4Vy5)
·(¬y4V¬y5)=1
Решим первое уравнение (y1Vy2)
·(¬y1V¬y2)=1.Преобразуем логическое выражение (y1Vy2)
·(¬y1V¬y2):
(y1Vy2)
·(¬y1V¬y2)=(y1
·¬y1)V(y1
·¬y2)V(y2
·¬y1)V(y2
·¬y2)=0V(y1
·¬y2)V(y2
·¬y1)V0=(y1
·¬y2)V(y2
·¬y1).
Отобразим логическое выражение (y1
·¬y2)V(y2
·¬y1) с помощью диаграммы Эйлера-Венна:
[ Cкачайте файл, чтобы посмотреть картинку ]
Видно по рисунку,что это инверсия эквиваленции: ¬(y1
·y2) или ¬(y1y2).
Перепишем уравнение: ¬(y1
·y2)=1. Отсюда (y1
·y2)=0. Такое уравнение имеет 2 решения:y1=1,y2=0 или y1=0,y2=1.
Рассмотрим 2-ое уравнение. С учетом преобразований оно становится таким:¬(y2
·y3)=1.
Решим систему из двух уравнений:
¬(y1
·y2)=1
¬(y2
·y3)=1
Перепишем систему в одно уравнение:¬(y1
·y2)
·¬(y2
·y3)=1.
Преобразуем ¬(y1
·y2)
·¬(y2
·y3):
¬(y1
·y2)
·¬(y2
·y3)=¬( (y1
·y2)V(y2
·y3) )-выносим отрицание за скобки.
Уравнение примет вид:¬( (y1
·y2)V(y2
·y3) )=1. Отсюда (y1
·y2)V(y2
·y3)=0.
Логическое выражение выполняется, только когда (y1
·y2)=0 и (y2
·y3)=0.
Пусть y2=0.
y1
·0=0-выполняется при y1=1.
0
·y3=0-выполняется при y3=1.
Получаем одно решение:y2=0,y1=1,y3=1.
Пусть y2=1.
y1
·1=0-выполняется при y1=0.
0
·y3=0-выполняется при y3=0.
Получаем одно решение:y2=1,y1=0,y3=0.
Общее число решений при двух уравнениях системы:1+1=2 решения.
Таким образом,при добавлении одного уравнения к самому первому уравнению не меняется число решений, остается равным двум. Следовательно, добавление остальных уравнений не изменит общее количество решений. Остается два решения.
Теперь перейдем к поиску количества решений, используя обратную подстановку для y.
y1=(x1
· x2)-для каждого из значений y1 есть два решения. Например,если y=0,то x1=0,x2=1 или x1=1,x2=0.
y2=(x3
· x4)-для каждого из значений y2 есть два решения.
Аналогично и для остальных:y3,y4,y5. Пары решений (x1,x2),(x3,x4),(x5,x6),(x7,x8),(x9,x10) - не зависят друг от друга, поэтому комбинаций решений равно 25=32.(основание равно 2,т.к. каждая пара дает два решения, а степень равна 5,т.к. у нас есть 5 пар).
В данном случае мы не учли, что и y1,y2,y3,y4,y5 дают нам в два раза больше решений.
Общее количество решений:32*2=64 решения.
Разбор задачи B10 (демо ЕГЭ 2011)
Время выполнения-10 мин, уровень сложности-высокий
Сколько различных решений имеет уравнение
((J K) (M /\ N /\ L)) /\ ((J /\ ¬K) ¬(M /\ N /\ L)) /\ (M J) = 1,
где J, K, L, M, N – логические переменные?В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Ответ: 8
Решение:
((J K) (M
· N
· L))
· ((J
· ¬K) ¬(M
· N
· L))
· (M J) = 1
Преобразуем выражение ((J K) (M
· N
· L))
· ((J
· ¬K) ¬(M
· N
· L))
· (M J):
Сначала преобразуем: (J
· ¬K) ¬(M
· N
· L).
(J
· ¬K) ¬(M
· N
· L)=¬(¬JVK) ¬(M
· N
· L)-вынесли отрицание за скобки
¬(¬JVK) ¬(M
· N
· L)=¬(JK) ¬(M
· N
· L)-воспользовались формулой перевода импликации.
Подставим это в выражение( (J K) (M
· N
· L))
· ((J
· ¬K) ¬(M
· N
· L)), получим:
( (J K) (M
· N
· L))
· (¬(JK) ¬(M
· N
· L)).
Проведем замену:
(J K)=P
(M
· N
· L)=Q
Получим при замене:
(PQ)
· (¬P¬Q)
Изобразим это логическое выражение с помощью диаграмм Эйлера-Венна:
[ Cкачайте файл, чтобы посмотреть картинку ]
Из рисунка видно,что это логическая операция эквиваленция:PQ.
Проведем обратную замену:
PQ=(J K)(M
· N
· L).
Выпишем уравнение с учетом преобразований:
((J K)(M
· N
· L))
· (M J) = 1.
Уравнение равно 1,когда (J K)(M
· N
· L)=1 и (M J)=1-логическое умножение дает 1,когда оба логических операнда равны 1.
(J K)(M
· N
· L) дает 2 решения:
(J K)=1,(M
· N
· L)=1 или (J K)=0,(M
· N
· L)=0-логическая эквиваленция дает 1,когда оба операнда одинаковы(оба равны 0 или 1)
Получаем 2 системы уравнений:
1-ая система: (J K)=1,(M
· N
· L)=1,(M J)=1.
2-ая система: (J K)=0,(M
· N
· L)=0,(M J)=1.
M J=1 выполняется в 3-х случаях: M=0,J=0 или M=0,J=1, или M=1,J=1.
Решаем 1-ую систему уравнений.
M=0,J=0
0 K=1. Выполняется при любом K.
0
· N
· L=1-при любом N,M не выполняется. Поэтому решений с M=0,J=0 нет. Также нет решений и при M=0,J=1 по той же причине,что и выше.
M=1,J=1
1 K=1-выполняется при K=1.
1
· N
· L=1 выполняется при N=1 и L=1.
Поэтому получаем одно решение: M=1,J=1,K=1,N=1 и L=1.
Решаем 2-ую систему уравнений.
M=0,J=0
0 K=0 - при K не выполняется. Поэтому решений с M=0,J=0 нет.
M=0,J=1
1 K=0. Выполняется при K=0.
0
· N
· L=0-выполняется при любых N,L. Поэтому получаем четыре решения(22=4)
M=1,J=1
1 K=0. Выполняется при K=0.
1
· N
· L=0-не выполняется только при N=1,L=1. В трех остальных случаях выполняется. Поэтому получаем три решения.
Подсчитываем,сколько всего решений получается:1+4+3=8 решений.
Разбор задачи B4 (демо ЕГЭ 2010)
Уровень сложности-высокий
Сколько различных решений имеет уравнение
J /\ ¬K /\ L /\ ¬M /\ (N \/ ¬N) = 0
где J, K, L, M, N – логические переменные?В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.
Ответ: 30
Решение:
Упростим выражение J
·¬K
·L
·¬M
·(NV¬N):
J
·¬K
·L
·¬M
·(NV¬N) = J
·¬K
·L
·¬M
·1-логическое сложение логической переменой и ее отрицания дает 1.
J
·¬K
·L
·¬M
·1 = J
·¬K
·L
·¬M-логическое умножение логического выражения на 1 дает логическое выражение.
Получили, что N-независимая логическая переменная. Она может быть равно 0 или 1. Т.е. дает 2 варианта.
Получим преобразованное уравнение:
F = J
·¬K
·L
·¬M = 0.
Общее количество решений равно 24=16, т.к. у нас 4 зависимых логических переменных:J,K,L,M.
F=1 в единственном случае,когда все логические переменные равны 1, т.е.:
J=1,¬K=1,L=1, ¬M=1 или J=1,K=0,L=1, M=0. Это одно решение.
Нам нужно найти количество решений, когда F=0.
16-1=15-общее количество решений без учета переменной N.
Учитывая N,получим:15*2=30 решений.
Разбор задачи B7 (демо ЕГЭ 2011)
Время выполнения-8 мин, уровень сложности-повышенный
Девять школьников, остававшихся в классе на перемене, были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал, были получены следующие ответы:Володя: «Это сделал Саша».Аня: «Володя лжет!»Егор: «Маша разбила».Саша: «Аня говорит неправду!»Рома: «Разбила либо Маша, либо Нина»Маша: «Это я разбила!»Нина: «Маша не разбивала!»Коля: «Ни Маша, ни Нина этого не делали».Олег: «Нина не разбивала!»Кто разбил окно, если известно, что из этих девяти высказываний истинны только три?Ответ запишите в виде первой буквы имени.
Ответ: Н
Решение:
Найдем, какие имена в ответах упоминаются чаще всего. Это имена: Маша (упоминается 4 раза) и Нина (упоминается 3 раза).
Введем обозначение: "+"-говорит правду(высказывание истинно), "-"-лжет(высказывание ложно).
Пусть Маша разбила, тогда:
Володя- Аня+ Егор+ Саша- Рома+ Маша+ Нина- Коля- Олег+.
Получили 5 истинных высказываний (выделены розовым). Это не удовлетворяет условию. Должно быть 3 истинных высказывания.
Пусть Нина разбила, тогда:
Володя- Аня+ Егор- Саша- Рома+ Маша- Нина+ Коля- Олег-.
Получили 3 истинных высказываний (выделены розовым). Это удовлетворяет условию.
Получили, что окно разбила Нина или Н.
логический оператор, конъюнкция, логическое "и"логический оператор, дизъюнкция, логическое "или"логический оператор, импликация, следованиеHP LaserJet 1020
[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
Алгебра логики: основные понятия
Алгебра логики - раздел математики. Она оперирует логическими высказываниями.
Логическое высказывание - любое предложение в повествовательной форме, о котором можно однозначно сказать, истинно оно или ложно. Примеры логических высказываний:
"Москва - столица России" (высказывание истинно).
"После зимы наступает осень" (высказывание ложно).
Простое высказывание - логическое высказывание, состоящее из одного утверждения.
Сложное высказывание - логическое высказывание, состоящее из нескольких утверждения, объединенных с помощью "связок": союзов "и", "или (либо)", частицы "не", связки "если, то" и др. Примеры сложных высказываний:
1. "Иван сдает экзамен по физике и информатике".
Высказывание содержит два утвеждения, объединенных "и":
Утверждение1: "Иван сдает экзамен по физике".
Утверждение2: "Иван сдает экзамен по информатике".
2. "Игорь решил записаться в секцию по воллейболу или баскетболу".
Высказывание содержит два утвеждения, объединенных "или":
Утверждение1: "Игорь решил записаться в секцию по воллейболу".
Утверждение2: "Игорь решил записаться в секцию по баскетболу".
3. "Если Илья будет много готовиться самостоятельно и будет заниматься с репетитором, то он поступит в ВУЗ".
Высказывание содержит три утвеждения, объединенных связкой "если, то" и союзом "и":
Утверждение1: "Илья будет много готовиться самостоятельно".
Утверждение2: "Илья будет заниматься с репетитором".
Утверждение2: "Илья поступит в ВУЗ".
Логические операции - "связки": союзы и частицы естественного языка, образующие из простых высказываний сложные, представленные в формальном виде . Подробно основные логические операции рассмотрены в [ Cкачайте файл, чтобы посмотреть ссылку ].
Логическое выражение - простое или сложное логическое высказывание, представленное в формальном виде. Примеры логических выражений:
простое: A,
сложное: AVBC,
где A, B, C - утверждения;
·, V, - логические операции.
Законы алгебры логики - законы, позволяющие преобразовывать логические выражения. Основные законы рассмотрены в этой [ Cкачайте файл, чтобы посмотреть ссылку ].
Логическая переменная - переменная, которая может принимать значение 1 (истина) или 0 (ложь).
Логическая функция - функция, аргументы и значение которой могут принимать значение 1 (истина) или 0 (ложь).
Таблица истинности - таблица, которая используется для описания логических функций, в частности отдельных логических операций. [ Cкачайте файл, чтобы посмотреть ссылку ]
Диаграммы Эйлера-Венна - диаграммы, которые служат для наглядного представления всех вариантов пересечения нескольких множеств. В качестве множеств могут использоваться простые логические высказывания. Диаграмма строится для логического высказывания, которое содержит от одного до трех утверждений
О том, как строить такие диаграммы, можно прочесть в статье: [ Cкачайте файл, чтобы посмотреть ссылку ]. Типовые задачи на множества подробно разобраны в статье [ Cкачайте файл, чтобы посмотреть ссылку ].
Логические операции
Чаще всего используются следующие логические операции:
инверсия (отрицание, логическое не),
конъюнкция (логическое и),
дизъюнкция (логическое или),
импликация (следование),
эквивалентность (тождество).
Рассмотрим каждую из них подробно. Для описания используем [ Cкачайте файл, чтобы посмотреть ссылку ] и таблицы истинности.
Логическая операция/соответствие в русском языке
Обозначение
Диаграмма Эйлера-Венна
Таблица истинности
инверсия (отрицание, логическое "НЕ")/"...не...", "неверно, что..."
¬
[ Cкачайте файл, чтобы посмотреть картинку ]
A
¬A
0
1
1
0
конъюнкция (логическое "И")/"...и..."
·, &
[ Cкачайте файл, чтобы посмотреть картинку ]
A
B
A
·B
0
0
0
0
1
0
1
0
0
1
1
1
дизъюнкция (логическое "ИЛИ")"...или...", "...либо..."
V
[ Cкачайте файл, чтобы посмотреть картинку ]
A
B
AVB
0
0
0
0
1
1
1
0
1
1
1
1
импликация (следование)/"если...,то...", "когда..., тогда..."
[ Cкачайте файл, чтобы посмотреть картинку ]
A
B
AB
0
0
1
0
1
1
1
0
0
1
1
1
эквивалентность (тождество)"тогда и только тогда, когда"
,
·
[ Cкачайте файл, чтобы посмотреть картинку ]
A
B
AB
0
0
1
0
1
0
1
0
0
1
1
1
Основные логические операции: инверсия, конъюнкция, дизъюнкция.
Остальные логические операции можно выразить через них:
AB=¬AVB;
AB=(A
·B)V(¬A
·¬B).
Порядок выполнения логических операций в выражении (от наибольшего приоритета к наименьшему):
инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность.
Пример:
AV¬B
·CDE.
Порядок выполнения:
¬B
(¬B)
·C
AV((¬B)
·C)
(AV((¬B)
·C))D
((AV((¬B)
·C))D)E
Законы алгебры логики и операции с константами
Законы алгебры логики:
Название закона
Формулы
Закон коммутативности
AVB=BVAA
·B=B
·A
Закон ассоциативности
(AVB)VC=AV(BVC)(A
·B)
·C=A
·(B
·C)
Закон дистрибутивности
AV(B
·C)=(AVB)
·(AVC)A
·(BVC)=(A
·B)V(A
·C)
Закон двойного отрицания
¬(¬A)=A
Закон де Моргана
¬(AVB)=¬A
·¬B¬(A
·B)=¬AV¬B
Закон исключения третьего
AV¬A=1
Закон непротиворечивости
A
·¬A=0
Закон идемпотентности
AVA=AA
·A=A
Закон поглощения
AVA
·B=AA
·(AVB)=A
Операции с константами:
операции с нулем
¬0=1AV0=AA
·0=0
операции с единицей
¬1=0AV1=1A
·1=A
Перейти к статье: [ Cкачайте файл, чтобы посмотреть ссылку ]
Диаграммы Эйлера-Венна
Диаграмма Эйлера-Венна - наглядное средство для работы со множествами. На этих диаграммах изображаются все возможные варианты пересечения множеств. Количество пересечений (областей) n определяется по формуле:
n=2N,
где N - количество множеств.
Таким образом, если в задаче используется два множества, то n=22=4, если три множества, то n=23=8, если четыре множества, то n=24=16. Поэтому диаграммы Эйлера-Венна используются в основном для двух или трех множеств.
Множества изображаются в виде кругов (если используется 2-3 множества) и эллипсов (если используется 4 множества), помещенных в прямоугольник (универсум).
Универсальное множество (универсум) U (в контексте задачи) - множество, содержащее все элементы рассматриваемой задачи: элементы всех множеств задачи и элементы, не входящие в них.
Пустое множество Ш (в контексте задачи) - множество, не содержащее ни одного элемента рассматриваемой задачи.
На диаграмме строят пересекающиеся множества, заключают их в универсум. Выделяют области, количество которых равно количеству пересечений.
Диаграммы Эйлера-Венна также используются для визуального представления логических операций.
Разберем примеры построения диаграмм Эйлера-Венна для двух и трех множеств.
Пример 1
Пусть есть следующие множества чисел:
А={1,2,3,4}
В={3,4,5,6}
Универсум U={0,1,2,3,4,5,6}
Диаграммы Эйлера-Венна для двух множеств А и В:
[ Cкачайте файл, чтобы посмотреть картинку ]
Определим области, и числа которые им принадлежат:
А
B
Обозначениеобласти
Числа
0
0
0)
0
0
1
1)
5,6
1
0
2)
1,2
1
1
3)
3,4
Пример 2
Пусть есть следующие множества чисел:
А={1,2,3,4}
В={3,4,5,6}
С={1,3,6,7}
Универсум U={0,1,2,3,4,5,6,7}
Диаграммы Эйлера-Венна для трех множеств А, В, С:
[ Cкачайте файл, чтобы посмотреть картинку ]
Определим области, и числа которые им принадлежат:
А
B
C
Обозначениеобласти
Числа
0
0
0
0)
0
0
0
1
1)
7
0
1
0
2)
5
0
1
1
3)
6
1
0
0
4)
2
1
0
1
5)
1
1
1
0
6)
4
1
1
1
7)
3
Пример 3
Пусть есть следующие множества чисел:
А={0,1,2,3,4,5,6,7}
В={3,4,5,7,8,9,10,13}
С={0,2,3,7,8,10,11,12}
D={0,3,4,6,9,10,11,14}
Универсум U={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
Диаграммы Эйлера-Венна для четырех множеств А, В, С, D:
[ Cкачайте файл, чтобы посмотреть картинку ]
Определим области, и числа которые им принадлежат:
А
B
C
D
Обозначениеобласти
Числа
0
0
0
0
0)
15
0
0
0
1
1)
14
0
0
1
0
2)
12
0
0
1
1
3)
11
0
1
0
0
4)
13
0
1
0
1
5)
9
0
1
1
0
6)
8
0
1
1
1
7)
10
1
0
0
0
8)
1
1
0
0
1
9)
6
1
0
1
0
10)
2
1
0
1
1
11)
0
1
1
0
0
12)
5
1
1
0
1
13)
4
1
1
1
0
14)
7
1
1
1
1
15)
3
Если Вы хотите порешать типовые задач на множества, то перейдите к статье:[ Cкачайте файл, чтобы посмотреть ссылку ]. Там подробно разобрано 5 задач.
Разбор задачи A3 (демо ЕГЭ 2013)
Дан фрагмент таблицы истинности выражения F.
№ области
x1
x2
x3
x4
x5
x6
x7
F
1
1
1
0
1
1
1
1
0
2
1
0
1
0
1
1
0
0
3
0
1
0
1
1
0
0
1
Каким из приведённых ниже выражений может быть F?
¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7
¬x1 \/ x2 \/ ¬x3 \/ x4 \/ ¬x5 \/ ¬x6 \/ x7
x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7
x1 \/ ¬x2 \/ x3 \/ ¬x4 \/ ¬x5 \/ x6 \/ ¬x7
Решение:
Сначала определим, как связаны переменные в F: с помощью конъюнкции (
·) или дизъюнкции (V).
Если выражение содержит только конъюнкции, то оно может быть истинно только на одной области.
В данном случае F истинна (равна 1) на одной области (область №3 в таблице выше), поэтому начнем с проверки выражений, содержащих конъюнкции. Это вариант 1 и вариант 3.
x1
x2
x3
x4
x5
x6
x7
F
F=¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7(вариант 1)
F=x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7(вариант 3)
1
1
0
1
1
1
1
0
0
·1
·1
·1
·1
·0
·0=0
1
·0
·0
·0
·1
·1
·0=0
1
0
1
0
1
1
0
0
0
·0
·0
·0
·1
·0
·1=0
1
·1
·1
·1
·1
·1
·1=1
0
1
0
1
1
0
0
1
1
·1
·1
·1
·1
·1
·1=1
Получили вариант 1: ¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7
Разбор задачи A3 (демо ЕГЭ 2012)
Время выполнения-2 мин, уровень сложности-базовый
Дан фрагмент таблицы истинности выражения F:
X
Y
Z
F
0
0
0
0
0
0
1
0
1
1
1
1
Каким выражением может быть F?
X /\ Y /\ Z
¬X \/ ¬Y \/ Z
X \/ Y \/ Z
¬X /\ ¬Y /\ ¬Z
Решение:
Будем решать подстановкой предлагаемых вариантов.
F=X
·Y
·Z=1 только в случае,когда X,Y,Z=1. В остальных случаях F=0. Проверяем по таблице. Подходит.
F=¬XV¬YVZ. Подставляем значения из таблицы:
1V1V0=1.F=0. Следовательно, не подходит.
F=XVYVZ=0 тольков случае,когда X,Y,Z=0.В остальных случаях F=1. Проверяем по таблице. Не подходит.
F=¬X
·¬Y
·¬Z. Подставляем значения из таблицы:
1
·1
·1=1.F=0. Следовательно, не подходит.
Разбор задачи A9 (демо ЕГЭ 2011)
Время выполнения-2 мин, уровень сложности-базовый
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.Дан фрагмент таблицы истинности выражения F:
X
Y
Z
F
0
1
1
0
1
1
1
1
0
0
1
1
Какое выражение соответствует F?
X /\ ¬Y /\ ¬Z
¬X /\ ¬Y /\ Z
¬X \/ ¬Y \/ Z
X \/ ¬Y \/ ¬Z
Решение:
Будем решать подстановкой предлагаемых вариантов.
F=X
·¬Y
·¬Z.Подставляем значения из таблицы:
0
·0
·0=0. F=0.
1
·0
·0=0. F=1.Следовательно, не подходит.
F=¬X
·¬Y
·Z. Подставляем значения из таблицы:
1
·0
·1=0.F=0.
0
·0
·1=0. F=1.Следовательно, не подходит.
F=¬XV¬YVZ. Подставляем значения из таблицы:
1V0V1=1.F=0.Следовательно, не подходит.
F=XV¬YV¬Z.Подставляем значения из таблицы:
0V0V0=0.F=0.
1V0V0=1.F=1.
0V1V0=1.F=1.
Следовательно, F=XV¬YV¬Z подходит.
Разбор задачи A9 (демо ЕГЭ 2010)
Уровень сложности-базовый
Дан фрагмент таблицы истинности выражения F:
X
Y
Z
F
1
1
1
1
1
1
0
1
1
0
1
1
Каким выражением может быть F?
X /\ Y /\ Z
¬X \/ ¬Y \/ Z
X \/ Y \/ Z
X /\ Y /\ ¬Z
Решение:
Будем решать подстановкой предлагаемых вариантов.
F=X
·Y
·Z=1 только в случае,когда X,Y,Z=1. В остальных случаях F=0. Проверяем по таблице. Не подходит.
F=¬XV¬YVZ.Подставляем значения из таблицы:
0V0V1=1.F=1.
0V0V0=0.F=1.Следовательно, не подходит.
F=XVYVZ=0 тольков случае,когда X,Y,Z=0.В остальных случаях F=1. Проверяем по таблице. Подходит.
F=¬X
·¬Y
·¬Z.Подставляем значения из таблицы:
0
·0
·0=0.F=1. Следовательно, не подходит.
Разбор задачи A9 (демо ЕГЭ 2009)
Время выполнения-2 мин, уровень сложности-базовый
Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.Дан фрагмент таблицы истинности выражения F:
X
Y
Z
F
1
0
0
1
0
0
0
1
1
1
1
0
Какое выражение соответствует F?
¬X /\ ¬Y /\ ¬Z
X /\ Y /\ Z
X \/ Y \/ Z
¬X \/ ¬Y \/ ¬Z
Решение:
Будем решать подстановкой предлагаемых вариантов.
F=¬X
·¬Y
·¬Z.Подставляем значения из таблицы:
0
·1
·1=0.F=1. Следовательно, не подходит.
F=X
·Y
·Z=1 только в случае,когда X,Y,Z=1. В остальных случаях F=0. Проверяем по таблице. Не подходит.
F=XVYVZ=0 тольков случае,когда X,Y,Z=0.В остальных случаях F=1. Проверяем по таблице. Не подходит.
F=¬XV¬YV¬Z.Преобразуем:¬(X
·Y
·Z). ¬(X
·Y
·Z)=0 только в случае, когда X,Y,Z=1.В остальных случаях F=1. Проверяем по таблице. Подходит.
Разбор задачи B12 (демо ЕГЭ 2013)
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос
Найдено страниц(в тысячах)
Фрегат | Эсминец
3400
Фрегат & Эсминец
900
Фрегат
2100
Какое количество страниц (в тысячах) будет найдено по запросу Эсминец? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Ответ: 2200
Решение:
Изобразим запросы в виде [ Cкачайте файл, чтобы посмотреть ссылку ].
Запрос "Фрегат" обозначим символом "Ф", "Эсминец" - символом "Э".
[ Cкачайте файл, чтобы посмотреть картинку ]
Э=(Ф|Э)-Ф+(Ф&Э)=3400-2100+900=2200.
Разбор задачи A10 (демо ЕГЭ 2011)
Время выполнения-1 мин, уровень сложности-базовый
Укажите, какое логическое выражение равносильно выражению A \/ ¬( ¬B \/ ¬C):
¬A \/ B \/ ¬C
A \/ (B /\ C)
A \/ B \/ C
A \/ ¬B \/ ¬C
Решение:
AV¬(¬BV¬C)=A¬¬(B
·C)-вынесли за скобки операцию отрицания
AV¬¬(B
·C)=AV(B
·C)-двойное отрицание логического выражения дает просто выражение.
Получилось: AV(B
·C).
Разбор задачи A8 (демо ЕГЭ 2010)
Уровень сложности-базовый
Какое логическое выражение равносильно выражению ¬ (¬A \/ ¬B) /\ C
¬A \/ B \/ ¬C
A /\ B /\ C
(A \/ B) /\ C
(¬A /\ ¬B) \/ ¬C
Решение:
¬(¬АV¬B)
·C=¬¬(A
·B)
·C-вынесли отрицание за скобки
¬¬(A
·B)
·C=A
·B
·C-двойное отрицание логического выражения дает просто выражение.
Получилось: A
·B
·C.
Разбор задачи A8 (демо ЕГЭ 2009)
Укажите, какое логическое выражение равносильно выражению A /\ ¬ (¬B \/ C).
¬A \/ ¬B \/ ¬C
A /\ ¬B /\ ¬C
A /\ B /\ ¬C
A /\ ¬B /\ C
Решение:
A
·¬(¬BVC)=A
·¬¬(B
·¬C)-вынесли отрицание за скобки
A
·¬¬(B
·¬C)=A
·B
·¬C-двойное отрицание логического выражения дает просто выражение.
Получилось: A
·B
·¬C.
Разбор задачи A8 (демо ЕГЭ 2009)
Укажите, какое логическое выражение равносильно выражению A /\ ¬ (¬B \/ C).
¬A \/ ¬B \/ ¬C
A /\ ¬B /\ ¬C
A /\ B /\ ¬C
A /\ ¬B /\ C
Решение:
A
·¬(¬BVC)=A
·¬¬(B
·¬C)-вынесли отрицание за скобки
A
·¬¬(B
·¬C)=A
·B
·¬C-двойное отрицание логического выражения дает просто выражение.
Получилось: A
·B
·¬C.
Разбор задачи A10 (демо ЕГЭ 2013)
На числовой прямой даны два отрезка: P = [2, 10] и Q = [6, 14]. Выберите такой отрезок A, что формула ( (x
· А) (x
· P) ) \/ (x
· Q) тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
[0, 3]
[3, 11]
[11, 15]
[15, 17]
Решение:
Нужно решить уравнение: ( (x
· А) (x
· P) ) \/ (x
· Q)=1.
1 способ
Будем решать методом от противного. Пусть ( (x
· А) (x
· P) ) \/ (x
· Q)=0.
Преобразуем данное уравнение в систему уравнений:
[ Cкачайте файл, чтобы посмотреть картинку ]
Отрезки P и Q нам заданы, изобразим их:
[ Cкачайте файл, чтобы посмотреть картинку ]
Mы можем решить уравнения (2) и (3) в системе. x
·P=0 => x
·P. Аналогично, x
·Q.
[ Cкачайте файл, чтобы посмотреть картинку ]
Получили интервал: (
·
·;2)
·[14;+
·).
Мы решали методом от противного, поэтому инвертируем полученный интервал: [2;14].
Рассмотрим предложенные варианты:
[0, 3] - не подходит;
[3, 11] - подходит, т.к. [3, 11] включен в [2;14];
[11, 15] - не подходит;
[15, 17] - не подходит;
Получили, А
·[3; 11]
2 способ
Решим уравнение: ( (x
· А) (x
· P) ) \/ (x
· Q)=1 методом подстановки.
В уравнение вместо P, Q впишем сами отрезки: [2, 10] и [6, 14].
(x
· А)=1 для всех вариантов.
Вариант ответа
Интервал A
Значения x для проверки(границы интервала)
((x
· А) (x
· [2, 10]) ) \/ (x
· [6, 14])
1
[0, 3]
0,3
(10)V0=0(11)V0=1
2
[3, 11]
3,11
1(10)V1=1
3
[11, 15]
11,15
1(10)V0=0
4
[15, 17]
15,17
0(10)V0=0
В таблице розовым выделен искомый интервал.
Разбор задачи A15 (демо ЕГЭ 2011)
Время выполнения-2 мин, уровень сложности-повышенный
Какое из приведенных имен удовлетворяет логическому условию:¬ (последняя буква гласная первая буква согласная) /\ вторая буква согласная
ИРИНА
АРТЕМ
СТЕПАН
МАРИЯ
Решение:
Имя должно удовлетворять условию, значит, F=1.
Заменим выражения на логические переменные:
последняя буква гласная-А
первая буква согласная-В
вторая буква согласная-С
¬(AB)
·C=1.
Расставляем приоритеты логических операций. Сначала должна выполняться отрицание, затем конъюнкция.Чтобы выражение было равно 1,необходимо, чтобы ¬(AB)=1 и C=1.
Преобразуем первое выражение:¬(AB)=1. Отрицание логического выражения истинно, когда ложно это логическое выражение:(AB)=0
Рассмотрим (AB)=0. Импликация равна 0 только в одном случае, когда A=1,B=0.
Таблица истинности для AB:
А
В
AB
0
0
1
0
1
1
1
0
0
1
1
1
Поэтому имя должно удовлетворять условиям: А=1,В=0,С=1.
Теперь будем проверять каждое имя.
ИРИНА: А=1,В=0,С=1.Следовательно,это имя подходит.
АРТЕМ: А=0,В=0,С=1.Следовательно,это имя не подходит.
СТЕПАН: А=0,В=1,С=1.Следовательно,это имя не подходит.
МАРИЯ: А=1,В=1,С=0.Следовательно,это имя не подходит.
Разбор задачи A7 (демо ЕГЭ 2010)
Уровень сложности-повышенный
Какое из приведенных имен удовлетворяет логическому условию¬ (первая буква гласная вторая буква гласная) /\ последняя буква гласная
ИРИНА
МАКСИМ
АРТЕМ
МАРИЯ
Решение:
Имя должно удовлетворять условию, значит, F=1.
Заменим выражения на логические переменные:
первая буква гласная-А
вторая буква гласная-В
последняя буква гласная -С
¬(AB)
·C=1.
Расставляем приоритеты логических операций. Сначала должна выполняться отрицание, затем конъюнкция.Чтобы выражение было равно 1,необходимо, чтобы ¬(AB)=1 и C=1.
Преобразуем первое выражение:¬(AB)=1. Отрицание логического выражения истинно, когда ложно это логическое выражение:(AB)=0
Рассмотрим (AB)=0. Импликация равна 0 только в одном случае, когда A=1,B=0.
Таблица истинности для AB:
А
В
AB
0
0
1
0
1
1
1
0
0
1
1
1
Поэтому имя должно удовлетворять условиям: А=1,В=0,С=1.
Теперь будем проверять каждое имя.
ИРИНА: А=1,В=0,С=1. Следовательно,это имя подходит.
МАКСИМ: А=0,В=1,С=0. Следовательно,это имя не подходит.
АРТЕМ: А=1,В=0,С=0. Следовательно,это имя не подходит.
МАРИЯ: А=0,В=1,С=1. Следовательно,это имя не подходит.
Разбор задачи A7 (демо ЕГЭ 2009)
Время выполнения-3 мин, уровень сложности-повышенный
Для какого из указанных значений X истинно высказывание ¬ ((X>2) (X>3))?
1
2
3
4
Решение:
Высказывание истинно,значит, F=1
Заменим выражения:
(X>2) - A.
(X>3) - B.
Получим логическое выражение:
¬(AB)=1.
Отрицание логического выражения истинно, когда ложно это логическое выражение:(AB)=0.
Рассмотрим (AB)=0. Импликация равна 0 только в одном случае, когда A=1,B=0.
Таблица истинности для AB:
А
В
AB
0
0
1
0
1
1
1
0
0
1
1
1
Поэтому должны удовлетворяться условия: А=1,В=0.
Переходим обратно к неравенствам:
(X>2)=1
(X>3)=0
Поэтому X>2 и X
·3.
[ Cкачайте файл, чтобы посмотреть картинку ]
X принадлежит (2,3]
В ответе перечислены цифры:1,2,3,4. 1 и 4 не входят в область, 2-выколота. Подходит только цифра 3.
Разбор задачи A10 (демо ЕГЭ 2012)
Время выполнения-2 мин, уровень сложности-повышенный
Какое из приведённых имён удовлетворяет логическому условию:(первая буква согласная вторая буква согласная) /\ (предпоследняя буква гласная последняя буква гласная)?
КРИСТИНА
МАКСИМ
СТЕПАН
МАРИЯ
Решение:
Имя должно удовлетворять условию, значит, F=1.
Заменим выражения на логические переменные:
первая буква согласная-А
вторая буква согласная-В
предпоследняя буква гласная-С
последняя буква гласная-D
(AB)
·(CD)=1.
Расставляем приоритеты логических операций. Сначала должна выполняться конъюнкция.Чтобы выражение было равно 1,необходимо, чтобы (AB)=1 и (CD)=1.
Теперь рассмотрим импликации. В каждой из них есть по 3 возможных варианта, когда импликация равна 1.
AB=1.
А
В
AB
0
0
1
0
1
1
1
0
0
1
1
1
CD=1.
C
D
СD
0
0
1
0
1
1
1
0
0
1
1
1
Теперь будем проверять каждое имя.
КРИСТИНА: А=1,В=1,С=0,D=1.AB=1.CD=1.Следовательно,это имя подходит.
МАКСИМ: А=1,В=0,С=1,D=0.AB=0.CD=0.Следовательно,это имя не подходит.
СТЕПАН: А=1,В=1,С=1,D=0.AB=1.CD=0.Следовательно,это имя не подходит.
МАРИЯ: А=1,В=0,С=1,D=1.AB=0.CD=1.Следовательно,это имя не подходит.
Разбор задачи B12 (демо ЕГЭ 2012)
Время выполнения-2 мин, уровень сложности-повышенный
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&».В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос
Найдено страниц(в тысячах)
Шахматы | Теннис
7770
Теннис
5500
Шахматы & Теннис
1000
Какое количество страниц (в тысячах) будет найдено по запросу Шахматы?Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Ответ: 3270
Решение:
Изобразим запросы в виде [ Cкачайте файл, чтобы посмотреть ссылку ].
Запрос "Шахматы" обозначим символом "Ш", "Теннис" - символом "Т".
[ Cкачайте файл, чтобы посмотреть картинку ]
Ш=(Ш|Т)-Т+(Ш&Т)=7770-5500+1000=3270.
Разбор задачи B9 (демо ЕГЭ 2011)
Время выполнения-3 мин, уровень сложности-повышенный
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&».В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
Запрос
Найдено страниц(в тысячах)
Крейсер | Линкор
7000
Крейсер
4800
Линкор
4500
Какое количество страниц (в тысячах) будет найдено по запросу Крейсер & Линкор ?Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Ответ: 2300
Решение:
Изобразим запросы в виде диаграмм Эйлера-Венна. Запрос "Крейсер" обозначим символом "К", "Линкор" - символом "Л".
[ Cкачайте файл, чтобы посмотреть картинку ]
К&Л=К+Л-К|Л=4800+4500-7000=2300.
Разбор задачи B7 (демо ЕГЭ 2011)
Время выполнения-8 мин, уровень сложности-повышенный
Девять школьников, остававшихся в классе на перемене, были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал, были получены следующие ответы:Володя: «Это сделал Саша».Аня: «Володя лжет!»Егор: «Маша разбила».Саша: «Аня говорит неправду!»Рома: «Разбила либо Маша, либо Нина»Маша: «Это я разбила!»Нина: «Маша не разбивала!»Коля: «Ни Маша, ни Нина этого не делали».Олег: «Нина не разбивала!»Кто разбил окно, если известно, что из этих девяти высказываний истинны только три?Ответ запишите в виде первой буквы имени.
Ответ: Н
Решение:
Найдем, какие имена в ответах упоминаются чаще всего. Это имена: Маша (упоминается 4 раза) и Нина (упоминается 3 раза).
Введем обозначение: "+"-говорит правду(высказывание истинно), "-"-лжет(высказывание ложно).
Пусть Маша разбила, тогда:
Володя- Аня+ Егор+ Саша- Рома+ Маша+ Нина- Коля- Олег+.
Получили 5 истинных высказываний (выделены розовым). Это не удовлетворяет условию. Должно быть 3 истинных высказывания.
Пусть Нина разбила, тогда:
Володя- Аня+ Егор- Саша- Рома+ Маша- Нина+ Коля- Олег-.
Получили 3 истинных высказываний (выделены розовым). Это удовлетворяет условию.
Получили, что окно разбила Нина или Н.
Разбор задачи B10 (демо ЕГЭ 2010)
Уровень сложности-повышенный
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – &.
№
Запрос
1
канарейки | щеглы | содержание
2
канарейки & содержание
3
канарейки & щеглы & содержание
4
разведение & содержание & канарейки & щеглы
Ответ: 4321
Решение:
Изобразим запросы в виде диаграмм Эйлера-Венна. Запрос "канарейки" обозначим символом "К", "щеглы" - символом "Щ", "содержание"-символом "С", "разведение"-символом "Р".
[ Cкачайте файл, чтобы посмотреть картинку ]
Из рисунка видно,что при запросе Р&С&К&Щ-количество страниц будет минимальным, далее по возрастанию страниц: К&Щ&С, К&С и последнее(максимальное количество страниц)-К|Щ|С. Получается: 4,3,2,1.
Разбор задачи B10 (демо ЕГЭ 2009)
Время выполнения-3 мин, уровень сложности-повышенный
В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – &.
№
Запрос
1
принтеры & сканеры & продажа
2
принтеры & продажа
3
принтеры | продажа
4
принтеры | сканеры | продажа
Ответ: 1234
Решение:
Изобразим запросы в виде диаграмм Эйлера-Венна. Запрос "принтеры" обозначим символами "Прн", "сканеры" - символом "С", "продажа"-символами "Прд".
[ Cкачайте файл, чтобы посмотреть картинку ]
Из рисунка видно,что минимальное количество страниц дает запрос: Прн&С&Прд. Далее по возрастанию страниц идут запросы: Прн&Прд, Прн|Прд и последнее(максимальное количество страниц)-Прн|С|Прд. Получается: 1,2,3,4.
Разбор задачи B15 (демо ЕГЭ 2013)
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2 y3, y4, которые удовлетворяют всем перечисленным ниже условиям? (x1 x2) /\ (x2 x3) /\ (x3 x4) = 1 (¬y1 \/ y2) /\ (¬y2 \/ y3) /\ (¬y3 \/ y4) = 1 (y1 x1) /\ (y2 x2) /\ (y3 x3) /\ (y4 x4) = 1 В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, y1, y2 y3, y4, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Ответ: 15
Решение:
Преобразуем систему уравнений к виду:
(x1 x2) /\ (x2 x3) /\ (x3 x4) = 1 (1)
(y1 y2) /\ (y2 y3) /\ (y3 y4) = 1 (2)
(y1 x1) /\ (y2 x2) /\ (y3 x3) /\ (y4 x4) = 1 (3)
Розовым выделено уравнение, которое было преобразовано. ¬y1 \/ y2=y1 y2. Аналогично и для остальных частей данного уравнения.
Решим уравнение (1).
1 способ
Уравнение (1) содержит импликации (), связанные конъюнкцией (/\). Соответственно, чтобы уравнение было истинно, все входящие импликации должны быть истинны:
x1 x2=1,
x2 x3=1,
x3 x4=1.
Таблица истинности для импликации на примере x1 x2:
x1
x2
x1x2
0
0
1
0
1
1
1
0
0
1
1
1
Розовым выделена комбинация, когда импликация ложна. Видно, что в ней идут подряд "1" и "0". Выпишем комбинации для x1x2x3x4, в которых не встречается подряд "1" и "0", чтобы импликации x1 x2, x2 x3, x3 x4 не были равны 0-ю.
x1
x2
x3
x4
0
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
1
1
1
1
Получили 5 комбинаций.
2 способ
Решим методом от противного. Рассмотрим случаи, когда уравнение (x1 x2) /\ (x2 x3) /\ (x3 x4)=0.
Импликация ложна, когда посылка истинна, а следствие ложно. Таблица истинности приведена выше:
Исходя из этого определим случаи, когда импликация ложна.
Если x1 x2=0:
x1
x2
x3
x4
1
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
x1=1, x2=0,
x3 и x4 - 0 или 1, поэтому они дают 22=4 комбинации.
Если x2 x3=0:
x1
x2
x3
x4
0
1
0
0
0
1
0
1
1
1
0
0
1
1
0
1
x2=1, x3=0,
x1 и x4 - 0 или 1, поэтому они дают 4 комбинации.
Если x3 x4=0:
x1
x2
x3
x4
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
0
x3=1, x4=0,
x1 и x2 - 0 или 1, поэтому они дают 4 комбинации.
Получили 4*3=12 комбинаций.
Также нужно учеть повторные комбинации. В данном случае повторная комбинация одна: 1010. В таблицах выше такая комбинация выделена синей рамкой. Она встретилась 2 раза, поэтому общее число комбинаций с учетом повторов:
12
·1=11.
Мы решали уравнение методом от противного. Теперь перейдем к исходному уравнению.
Общее число комбинаций при 4-х переменных: 24=16. 16-11=5 комбинаций.
Перейдем к уравнению (2):
(y1 y2) /\ (y2 y3) /\ (y3 y4) = 1.
Это уравнение содержит переменные y1, y2, y3, y4, которые не связаны с уравнением (1). Уравнения (1) и (2) независимы друг от друга. Но вид уравнения (2) аналогичен виду уравнения (1), которое мы решили выше. Поэтому получаем 5 комбинаций.
y1
y2
y3
y4
0
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
1
1
1
1
Добавим к системе уравнение (3):
(y1 x1) /\ (y2 x2) /\ (y3 x3) /\ (y4 x4) = 1
Выпишем рядом решения уравнений (1) и (2)
y1
y2
y3
y4
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
Будем решать систему уравнений методом от противного. Уравнение (3) равно 0-ю.
y1 x1=0:
y1=1, x1=0
y1
y2
y3
y4
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
Получили 4 комбинации.
y2 x2=0:
y2=1, x2=0. Строку 1111 (y1y2y3y4) не берем во избежания повторов.
y1
y2
y3
y4
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
Получили 3 комбинации.
y3 x3=0
y3=1, x3=0. Строки 1111, 0111 (y1y2y3y4) не берем во избежания повторов.
y1
y2
y3
y4
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
Получили 2-е комбинации.
y4 x4=0
y4=1, x4=0. Строки 1111, 0111, 0011 (y1y2y3y4) не берем во избежания повторов.
y1
y2
y3
y4
x1
x2
x3
x4
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
Получили 1-у комбинацию.
Всего комбинаций: 4+3+2+1=10.
Мы решали систему уравнений методом от противного. Теперь перейдем к исходной системе.
Общее число комбинаций: 5*5=25. Уравнения (1) и (2) дают по 5 независимых комбинаций.
25-10=15 комбинаций.
Разбор задачи B15 (демо ЕГЭ 2012)
Время выполнения-10 мин, уровень сложности-высокий
Сколько существует различных наборов значений логических переменных x1,x2, ... x9, x10, которые удовлетворяют всем перечисленным ниже условиям?
((x1
· x2) \/ (x3
· x4)) /\ (¬(x1
· x2) \/ ¬(x3
· x4)) =1((x3
· x4) \/ (x5
· x6)) /\ (¬(x3
· x4) \/ ¬(x5
· x6)) =1...((x7
· x8) \/ (x9
· x10)) /\ (¬(x7
· x8) \/ ¬(x9
· x10)) =1
В ответе не нужно перечислять все различные наборы значений x1, x2, ... x9, x10, при которых выполнена данная система
Ответ: 64
Решение:
Проведем замену:
(x1
· x2)=y1
(x3
· x4)=y2
(x5
· x6)=y3
(x7
· x8)=y4
(x9
· x10)=y5
Перепишем систему уравнений с учетом замены:
(y1Vy2)
·(¬y1V¬y2)=1
(y2Vy3)
·(¬y2V¬y3)=1
....
(y4Vy5)
·(¬y4V¬y5)=1
Решим первое уравнение (y1Vy2)
·(¬y1V¬y2)=1.Преобразуем логическое выражение (y1Vy2)
·(¬y1V¬y2):
(y1Vy2)
·(¬y1V¬y2)=(y1
·¬y1)V(y1
·¬y2)V(y2
·¬y1)V(y2
·¬y2)=0V(y1
·¬y2)V(y2
·¬y1)V0=(y1
·¬y2)V(y2
·¬y1).
Отобразим логическое выражение (y1
·¬y2)V(y2
·¬y1) с помощью диаграммы Эйлера-Венна:
[ Cкачайте файл, чтобы посмотреть картинку ]
Видно по рисунку,что это инверсия эквиваленции: ¬(y1
·y2) или ¬(y1y2).
Перепишем уравнение: ¬(y1
·y2)=1. Отсюда (y1
·y2)=0. Такое уравнение имеет 2 решения:y1=1,y2=0 или y1=0,y2=1.
Рассмотрим 2-ое уравнение. С учетом преобразований оно становится таким:¬(y2
·y3)=1.
Решим систему из двух уравнений:
¬(y1
·y2)=1
¬(y2
·y3)=1
Перепишем систему в одно уравнение:¬(y1
·y2)
·¬(y2
·y3)=1.
Преобразуем ¬(y1
·y2)
·¬(y2
·y3):
¬(y1
·y2)
·¬(y2
·y3)=¬( (y1
·y2)V(y2
·y3) )-выносим отрицание за скобки.
Уравнение примет вид:¬( (y1
·y2)V(y2
·y3) )=1. Отсюда (y1
·y2)V(y2
·y3)=0.
Логическое выражение выполняется, только когда (y1
·y2)=0 и (y2
·y3)=0.
Пусть y2=0.
y1
·0=0-выполняется при y1=1.
0
·y3=0-выполняется при y3=1.
Получаем одно решение:y2=0,y1=1,y3=1.
Пусть y2=1.
y1
·1=0-выполняется при y1=0.
0
·y3=0-выполняется при y3=0.
Получаем одно решение:y2=1,y1=0,y3=0.
Общее число решений при двух уравнениях системы:1+1=2 решения.
Таким образом,при добавлении одного уравнения к самому первому уравнению не меняется число решений, остается равным двум. Следовательно, добавление остальных уравнений не изменит общее количество решений. Остается два решения.
Теперь перейдем к поиску количества решений, используя обратную подстановку для y.
y1=(x1
· x2)-для каждого из значений y1 есть два решения. Например,если y=0,то x1=0,x2=1 или x1=1,x2=0.
y2=(x3
· x4)-для каждого из значений y2 есть два решения.
Аналогично и для остальных:y3,y4,y5. Пары решений (x1,x2),(x3,x4),(x5,x6),(x7,x8),(x9,x10) - не зависят друг от друга, поэтому комбинаций решений равно 25=32.(основание равно 2,т.к. каждая пара дает два решения, а степень равна 5,т.к. у нас есть 5 пар).
В данном случае мы не учли, что и y1,y2,y3,y4,y5 дают нам в два раза больше решений.
Общее количество решений:32*2=64 решения.
Разбор задачи B10 (демо ЕГЭ 2011)
Время выполнения-10 мин, уровень сложности-высокий
Сколько различных решений имеет уравнение
((J K) (M /\ N /\ L)) /\ ((J /\ ¬K) ¬(M /\ N /\ L)) /\ (M J) = 1,
где J, K, L, M, N – логические переменные?В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Ответ: 8
Решение:
((J K) (M
· N
· L))
· ((J
· ¬K) ¬(M
· N
· L))
· (M J) = 1
Преобразуем выражение ((J K) (M
· N
· L))
· ((J
· ¬K) ¬(M
· N
· L))
· (M J):
Сначала преобразуем: (J
· ¬K) ¬(M
· N
· L).
(J
· ¬K) ¬(M
· N
· L)=¬(¬JVK) ¬(M
· N
· L)-вынесли отрицание за скобки
¬(¬JVK) ¬(M
· N
· L)=¬(JK) ¬(M
· N
· L)-воспользовались формулой перевода импликации.
Подставим это в выражение( (J K) (M
· N
· L))
· ((J
· ¬K) ¬(M
· N
· L)), получим:
( (J K) (M
· N
· L))
· (¬(JK) ¬(M
· N
· L)).
Проведем замену:
(J K)=P
(M
· N
· L)=Q
Получим при замене:
(PQ)
· (¬P¬Q)
Изобразим это логическое выражение с помощью диаграмм Эйлера-Венна:
[ Cкачайте файл, чтобы посмотреть картинку ]
Из рисунка видно,что это логическая операция эквиваленция:PQ.
Проведем обратную замену:
PQ=(J K)(M
· N
· L).
Выпишем уравнение с учетом преобразований:
((J K)(M
· N
· L))
· (M J) = 1.
Уравнение равно 1,когда (J K)(M
· N
· L)=1 и (M J)=1-логическое умножение дает 1,когда оба логических операнда равны 1.
(J K)(M
· N
· L) дает 2 решения:
(J K)=1,(M
· N
· L)=1 или (J K)=0,(M
· N
· L)=0-логическая эквиваленция дает 1,когда оба операнда одинаковы(оба равны 0 или 1)
Получаем 2 системы уравнений:
1-ая система: (J K)=1,(M
· N
· L)=1,(M J)=1.
2-ая система: (J K)=0,(M
· N
· L)=0,(M J)=1.
M J=1 выполняется в 3-х случаях: M=0,J=0 или M=0,J=1, или M=1,J=1.
Решаем 1-ую систему уравнений.
M=0,J=0
0 K=1. Выполняется при любом K.
0
· N
· L=1-при любом N,M не выполняется. Поэтому решений с M=0,J=0 нет. Также нет решений и при M=0,J=1 по той же причине,что и выше.
M=1,J=1
1 K=1-выполняется при K=1.
1
· N
· L=1 выполняется при N=1 и L=1.
Поэтому получаем одно решение: M=1,J=1,K=1,N=1 и L=1.
Решаем 2-ую систему уравнений.
M=0,J=0
0 K=0 - при K не выполняется. Поэтому решений с M=0,J=0 нет.
M=0,J=1
1 K=0. Выполняется при K=0.
0
· N
· L=0-выполняется при любых N,L. Поэтому получаем четыре решения(22=4)
M=1,J=1
1 K=0. Выполняется при K=0.
1
· N
· L=0-не выполняется только при N=1,L=1. В трех остальных случаях выполняется. Поэтому получаем три решения.
Подсчитываем,сколько всего решений получается:1+4+3=8 решений.
Разбор задачи B4 (демо ЕГЭ 2010)
Уровень сложности-высокий
Сколько различных решений имеет уравнение
J /\ ¬K /\ L /\ ¬M /\ (N \/ ¬N) = 0
где J, K, L, M, N – логические переменные?В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.
Ответ: 30
Решение:
Упростим выражение J
·¬K
·L
·¬M
·(NV¬N):
J
·¬K
·L
·¬M
·(NV¬N) = J
·¬K
·L
·¬M
·1-логическое сложение логической переменой и ее отрицания дает 1.
J
·¬K
·L
·¬M
·1 = J
·¬K
·L
·¬M-логическое умножение логического выражения на 1 дает логическое выражение.
Получили, что N-независимая логическая переменная. Она может быть равно 0 или 1. Т.е. дает 2 варианта.
Получим преобразованное уравнение:
F = J
·¬K
·L
·¬M = 0.
Общее количество решений равно 24=16, т.к. у нас 4 зависимых логических переменных:J,K,L,M.
F=1 в единственном случае,когда все логические переменные равны 1, т.е.:
J=1,¬K=1,L=1, ¬M=1 или J=1,K=0,L=1, M=0. Это одно решение.
Нам нужно найти количество решений, когда F=0.
16-1=15-общее количество решений без учета переменной N.
Учитывая N,получим:15*2=30 решений.
Разбор задачи B7 (демо ЕГЭ 2011)
Время выполнения-8 мин, уровень сложности-повышенный
Девять школьников, остававшихся в классе на перемене, были вызваны к директору. Один из них разбил окно в кабинете. На вопрос директора, кто это сделал, были получены следующие ответы:Володя: «Это сделал Саша».Аня: «Володя лжет!»Егор: «Маша разбила».Саша: «Аня говорит неправду!»Рома: «Разбила либо Маша, либо Нина»Маша: «Это я разбила!»Нина: «Маша не разбивала!»Коля: «Ни Маша, ни Нина этого не делали».Олег: «Нина не разбивала!»Кто разбил окно, если известно, что из этих девяти высказываний истинны только три?Ответ запишите в виде первой буквы имени.
Ответ: Н
Решение:
Найдем, какие имена в ответах упоминаются чаще всего. Это имена: Маша (упоминается 4 раза) и Нина (упоминается 3 раза).
Введем обозначение: "+"-говорит правду(высказывание истинно), "-"-лжет(высказывание ложно).
Пусть Маша разбила, тогда:
Володя- Аня+ Егор+ Саша- Рома+ Маша+ Нина- Коля- Олег+.
Получили 5 истинных высказываний (выделены розовым). Это не удовлетворяет условию. Должно быть 3 истинных высказывания.
Пусть Нина разбила, тогда:
Володя- Аня+ Егор- Саша- Рома+ Маша- Нина+ Коля- Олег-.
Получили 3 истинных высказываний (выделены розовым). Это удовлетворяет условию.
Получили, что окно разбила Нина или Н.
логический оператор, конъюнкция, логическое "и"логический оператор, дизъюнкция, логическое "или"логический оператор, импликация, следованиеHP LaserJet 1020