Embedded Files
В ЕГЭ (но не в учебниках) встречается тип заданий, которые до 2011 года имели один из двух видов:
- при каких значениях переменных a,b,c,... данное выражение становится истинным(ложным);
- сколько различных решений имеет уравнение f(a,b,c,...) = 1 (0)
Это могут быть короткие выражения:
(K ^ L ^ M ) v (⌝L ^ ⌝M ^ N) = 0
(K & L & M ) | (~L & ~M & N)
длинные выражения:
((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)
и системы однотипных или не совсем однотипных выражений.
(см. ниже)
в случае коротких выражений иногда проще всего построить таблицу истинности. Существуют онлайн-построители, например http://programming.dojo.net.nz/study/truth-table-generator/index
также можно писать несложные программы для построения таблиц истинности:
- на Javascript: http://h.dist-learn.spb.ru/7
- на Паскале: http://pascalabc.net/WDE/?file=02380.pas
Проделывать многие операции над логическими выражениями умеет и WolframAlpha:
http://www.wolframalpha.com/input/?i=%28x+%7C%7C+y%29+%26%26+%21%28x+%26%26+y%29
http://www.wolframalpha.com/input/?i=x+xor+y
В целом дело сводится к анализу выражения, попыткам найти скрытую схему в нем.
Далее - выделение в нем системы и разбиение на части. Нахождение выражения с наименьшим числом решений, которые подставляются в другие выражения.
Если это дизъюнкция, то могут быть рассуждения вида "если левая скобка 0, то правая обязана быть 1"
В демонстрационном варианте 2012 г., А ТАКЖЕ в реальных вариантах весны/лета 2011 года появилась новая формулировка:
Алгоритм решения системы с большим числом однотипных уравнений
- преобразовать уравнения, найти что-то с известной таблицей истинности
- проанализовать таблицу истинности. например, если получается XOR то либо первый аргумент 1 либо второй
- метод гипотез: пусть х1 = 0, тогда при х2 = 0 получаем 00ххххххх, при х2 = 1 получаем 01ххххххх
- первое уравнение дает N ветвей решений, нужно посмотреть что у них общего
- так же разобрать второе уравнение, после чего должна проявиться закономерность построения решений
- найти закономерность - определить, на сколько увеличилось число ветвей благодаря второму уравнению
- подсчитать общее количество распространив эту схему до конца системы
- может быть проще увидеть взаимосвязь всех уравнений вместе, как они определяют закономерность построения решения
2012 год
B15
((x1 ≡ x2) ∨ (x3 ≡ x4)) ∧ (¬(x1 ≡ x2) ∨ ¬(x3 ≡ x4)) = 1
((x3 ≡ x4) ∨ (x5 ≡ x6)) ∧ (¬(x3 ≡ x4) ∨ ¬(x5 ≡ x6)) = 1
((x5 ≡ x6) ∨ (x7 ≡ x8)) ∧ (¬(x5 ≡ x6) ∨ ¬(x7 ≡ x8)) = 1
((x7 ≡ x8) ∨ (x9 ≡ x10)) ∧ (¬(x7 ≡ x8) ∨ ¬(x9 ≡ x10)) = 1
Вот два способа рассуждения.
I.
Если обозначить A = x1 ≡ x2, B = x3 ≡ x4 и так далее
то получим: (A ∨ B) ∧ (¬A ∨ ¬B)
или, по закону Де Моргана, (A ∨ B) ∧ ¬(A ∧ B)
это достаточно известная альтернативная формула для исключающего ИЛИ, как и (A ∧ ¬B) ∧ (¬A ∧ B)
A ⊕ B
Тогда система принимает вид:
(x1 ≡ x2) ⊕ (x3 ≡ x4)
(x3 ≡ x4) ⊕ (x5 ≡ x6)
(x5 ≡ x6) ⊕ (x7 ≡ x8)
(x8 ≡ x9) ⊕ (x9 ≡ x10)
Из первого уравнения видно, что либо x1 и x2 одинаковы, либо x3 и x4 одинаковы.
то есть если x1 и x2 одинаковы, то x3 и x4 разные
и наоборот, если x1 и x2 различны, то x3 и x4 одинаковы
Иными словами, рассмотрим наборы при x1 = 0, тогда
если x2 = 0, то левая скобка 1, тогда правая скобка д.б. 0, т.е. либо x3,x4 = 0,1 либо 1,0,
если x2 = 1, то левая скобка 0, тогда правая скобка д.б. 1, т.е. либо x3=x4=0 либо x3=x4=1
получается четыре ветви
теперь рассмотрим наборы при x1 = 1, тогда
если x2 = 0, то ...
если x2 = 1, то ...
получается опять четыре ветви
то есть первое уравнение дает восемь "ветвей" решений
Что даст второе уравнение?
либо x3 и x4 одинаковы, либо либо x5 и x6 одинаковы
в каждой из 8 ветвей на некоторую пару x3,x4 приходится по две пары x5,x6
то есть второе уравнение даст 16 ветвей
Аналогично, третье уравнение даст 32 ветви,
а четвертое уравнение в каждой из них по два итоговых решения.
Итого - 64 решения.
II.
Если смотреть на систему как на целое, то можно получить общий вид цепочек
Пусть верно (x1 ≡x2)
тогда не верно (x3 ≡x4), но верно (x5 ≡x6), не верно (x7 ≡x8) и верно (x9 ≡x10)
т.е. (x1 ≡x2) /\ (x5 ≡x6) /\ (x9 ≡x10)
это наборы вида 00xx00xx00 00xx00xx11
...
11xx11xx11
в которых xx - это 01 или 10
Т.е. в каждом таком решении значения идут парами, если где-то пара одинаковая, то перед ней будет разная, и после будет разная.
8 групп комбинаций, в каждой из которых по 4 возможных значения на местах xx xx 8*4 = 32
И то же самое, если НЕ верно (x1 ≡x2)
Итого 64 решения.
Или можно чуть более наглядно это описать для тех, кто любит переобозначения.
Обозначим A0 = пара 00, A1 = пара 11, B0 = пара 01, B1 = пара 10
После любого A может идти только B и наоборот.
Рассмотрим комбинации по две:
A0B0 A0B1 A1B0 A1B1 B0A0 B0A1 B1A0 B1A1 - их получилось 8.
если их будет по три
то на каждую такую кобминацию будет по две трехбуквенных, то есть 16
если по четыре, то 32
и по пять - 64.
Итого 64 решения.
2014 год
B15
¬(x1 ≡x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0
¬(x2 ≡x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0
…
¬(x8 ≡x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0
Преобразуем уравнения к удобному виду:
¬(x1 ≡x2) = x1 ⊕ x2
(x1 ∧ ¬x3) ∧ (¬x1 ∧ x3) = x1 ⊕ x3
Получается:
(x1 ⊕ x2 ) ^ (x1 ⊕ x3) = 0
(x2 ⊕ x3 ) ^ (x2 ⊕ x4) = 0
...
(x8 ⊕ x9 ) ^ (x8 ⊕ x10) = 0
рассмотрим решения 0ххххххххх
(0 ⊕ x2 ) ^ (0 ⊕ x3) = 0
эти две скобки не должны быть одновременно 1, чтобы конъюнкция была 0
если левая скобка 1, то вторая д.б.0 и наоборот, и еще они могут быть равны 0 одновременно
итак если x2 = 1 то x3 = 0
010xxxxxxx
если правая 1, то левая 0
001ххххххх
а одновременно они нули - это 011ххххх
рассмотрим решения 1ххххххххх
(1 ⊕ x2 ) ^ (1 ⊕ x3) = 0
если х2 = 0, левая скобка 1, правая д.б. 0, т.е. х3 = 1
101ххххххх
если х3 = 0, правая скобка 1, левая д.б.0, т.е. х2 = 1
110ххххххх
и одновременно скобки нули при х2 = х3 = 1
111ххххххх
итак, первое уравнение дает шесть ветвей решений
смотрим второе
010xxxxxxx 001ххххххх 011ххххх
(1 ⊕ 0 ) ^ (1 ⊕ x4) = 0 (0 ⊕ 1 ) ^ (0 ⊕ x4) = 0 (1 ⊕ 1 ) ^ (1 ⊕ x4) = 0
0101хххххх 0010хххххх 0110хххххх
0111хххххх
101ххххххх 110ххххххх 111ххххххх
(1 ⊕ 0 ) ^ (1 ⊕ x4) = 0 (0 ⊕ 1 ) ^ (0 ⊕ x4) = 0 (1 ⊕ 1 ) ^ (1 ⊕ x4) = 0
1010хххххх 1100хххххх 1110хххххх
1111хххххх
итак второе уравнение дало 8 ветвей
третье должно дать 10
4 12
5 14
6 16
7 18
8 20
итак, ответ - 20 решений
Но уравнения в системе могут быть и не однотипны. В этом случае нужно анализировать их взаимосвязь, возможно, пробовать подстановку, пытаться понять закономерность построения решений.
2013 год
B15
(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) ∧ (x2 → x3) ∧ (x3 → x4) = 1
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1
(y1 → x1) ∧ (y2 → x2) ∧ (y3 → x3) ∧ (y4 →x4) = 1
все скобки здесь должны быть истинами
рассмотрим x1 = 1 и y1 = 1
т.е. комбинации 1xxx1xxx
(1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1
(1 → y2) /\ (y2 → y3) /\ (y3 → y4) = 1
(1 → 1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 →x4) = 1
это сразу определяет что x2 = 1, x3 = 1, x4 = 1 и то же для игреков
т.е. из этой ветви годится только решение 11111111
И (*) ВООБЩЕ если xn = 1 то очевидно для всех i xn+i = 1
и то же для всех y
т.е. если встречается 1, то далее все одноименные переменные тоже 1
01110111 например годится, 00110011 и 00010001
это следует из первых двух уравнений
а что дает третье уравнение?
то что если какой-то y=1 то однономерной x с ним тоже будет 1
т.е. ветви решений не симметричны:
годится 01110000 но не годится 00001111
подсчитаем комбинации исходя из этого
11111111
x1110111 (0 и 1)
xx110011 (00, 01 и 11)
xxx10001 (000, 001, 011 и 111)
xxxx0000 (0000, 0001, 0011, 0111, 1111)
Ответ: 15
Вот рекомендации Константина Полякова.
И еще примеры решения конкретных систем: Пример 1, Пример 2
Рассмотрим решение коротких и длинных одиночных уравнений
Два варианта решения:
- таблица истинности (гарантия верного ответа)
- аналитический (упрощение, сведение к системе)
АЛГОРИТМ аналитического решения
- возможно решать противоположную задачу, определив общее число наборов,
- в зависимости от необходимости превратить в конъюнкцию = 1 или дизъюнкцию = 0
- разбить на систему
- согласно таблице истинности описать наборы решений для каждой части системы
- по возможности выбрать ту, где меньше решений
- посмотреть какие решения совпадают, т.е. протестировать решения одной части для другой части
- выкинуть из второй части то, что не является решениями первой части.
- для системы из двух легко воспользоваться формулой количества пересечений.
- иногда довольно легко подсчитать комбинации по их "правилу образования", иногда нагляднее и проще выписать их себе списком (если это в пределах десятка).
Рассмотрим пример: (K V L) → (L ^ M ^ N) = 0
Импликация. Ложна когда первая часть истинна, а вторая ложна. Отсюда система:
(1) (K V L) = 1
(2) (L Λ M Λ N) = 0
Первый вариант рассуждений. Рассмотрим антирешения.
дизъюнкция ложна в 4 случаях: 0000 0001 0010 0011
конъюнкция истинна в 2 случаях: 0111 1111
при этом эти "антирешения" не пересекаются, т.е. получается, что все остальные 16-6 = 10 комбинаций должны подходить обоим уравнениям. Потому что эти 10 комбинаций не содержат ни антирешений первого, ни антирешений второго уравнения.
Второй вариант рассуждений. Выберем уравнение с наименьшим числом решений, это первое (16-4 = 12).
Подставим эти решения во второе. Как это сделать, если у нас нет их полного списка?
Очень просто. Среди этих 12 решений есть 2 антирешения второго, так как она оба НЕ входят в 4 антирешения первого.
Значит их нужно выкинуть. 12-2 = 10
Третий вариант. Объединение множеств решений первого и второго - 16. Решений первого 12, решений второго 14.
А найти надо пересечения. По формуле мощности пересечения множеств
|X ∩ Y| = |X| + |Y| - |X U Y| = 12 + 14 - 16 = 26 - 16 = 10
Ответ: 10 решений.
Таблица истинности: http://programming.dojo.net.nz/study/truth-table-generator/index
~(K | L ) | (L & M & N)
K L M N | ~ ( K | L ) | ( L & M & N )
-------------------------------------------------------
0 0 0 0 | 1 0 0 0 1 0 0 0 0 0
0 0 0 1 | 1 0 0 0 1 0 0 0 0 1
0 0 1 0 | 1 0 0 0 1 0 0 1 0 0
0 0 1 1 | 1 0 0 0 1 0 0 1 0 1
0 1 0 0 | 0 0 1 1 0 1 0 0 0 0
0 1 0 1 | 0 0 1 1 0 1 0 0 0 1
0 1 1 0 | 0 0 1 1 0 1 1 1 0 0
0 1 1 1 | 0 0 1 1 1 1 1 1 1 1
1 0 0 0 | 0 1 1 0 0 0 0 0 0 0
1 0 0 1 | 0 1 1 0 0 0 0 0 0 1
1 0 1 0 | 0 1 1 0 0 0 0 1 0 0
1 0 1 1 | 0 1 1 0 0 0 0 1 0 1
1 1 0 0 | 0 1 1 1 0 1 0 0 0 0
1 1 0 1 | 0 1 1 1 0 1 0 0 0 1
1 1 1 0 | 0 1 1 1 0 1 1 1 0 0
1 1 1 1 | 0 1 1 1 1 1 1 1 1 1
Рассмотрим другой пример: (K v L) & (M v N) = 1
(1) K v L = 1
(2) M v N = 1
Первому не подходят 0000, 0001, 0010, 0011, т.е. решений 12
Второму не подходят 0000, 0100, 1000, 1100, т.е. решений 12
Объединение множеств решений первого и второго - 15,а не 16, так как комбинация 0000 не подходит обоим уравнениям..
|X ∩ Y| = |X| + |Y| - |X U Y| = 12 + 12 - 15 = 24 - 15 = 9
Или можно просто сказать, что уникальных антирешений всей системы 7 - они складываются из антирешений первого, антирешений второго минус 1 (одно) повторение антирешения 0000, 16-7 = 9
Ответ: 9 решений
(K ^ L ^ M ) v (⌝L ^ ⌝M ^ N) = 0
Дизъюнкция равна 0, это система
(1) K ^ L ^ M = 0
(2) ⌝L ^ ⌝M ^ N = 0
16 комбинации всего возможны
антирешения первого: 111х, их два, следовательно 16-2 = 14 решений первого
антирешения второго: х001, их два, следовательно 16-2 = 14 решений второго
антирешения НЕ пересекаются
поэтому решений 14+14 - 16 = 12
(K v L v M ) ^ (⌝L ^ ⌝M ^ N) = 1
(K | L | M ) & (~L & ~M & N)
- K v L v M = 1
- ⌝L ^ ⌝M ^ N = 1
Здесь у второго вообще 2 решения (0001 и 1001), подставляем их в первое, 0001 является антирешением первого.
Ответ: 1 решение
(K ^ L ^ M ) → (⌝M ^ N) = 1
решим сначала (K ^ L ^ M ) → (⌝M ^ N) = 0
- K ^ L ^ M = 1
- ⌝M ^ N = 0
первая
1110
1111
не противоречат ли они второй?
нет.
значит здесь 2 решения
значит у противоположной задачи 16 - 2 = 14 решений
Задания в 2010 году были в два раза длиннее. И переменных там больше.
А вот как объясняются эти задачи в пособиях
Page updated
Google Sites
Report abuse