Отправлено: 27.01.12 16:45. Заголовок: [B15] Система логических уравнений

Дана система
a или ¬b или ¬c и d=1
c или ¬d или ¬e и f=1
e или ¬f или ¬g и h=1
g или ¬h или¬i и j=1
Сколько решений имеет система?
У меня получается ответ 351решение. Рассуждаю так : для первого уравнения получается 13 решений, при добавлении второго _39, третьего - 117, четвертого-351. А в ответе получается 364.

 Отправлено: 06.02.12 17:53. Заголовок: Изучаю ваши материал..

Изучаю ваши материалы и никак не могу понять как делать переход от введённых переменных к исходным.
В третьем примере(из разобранных) для системы с заменой получается 6 решений.
Далее идут след. рассуждения:

цитата:

У нас есть 5 переменных Y1 … Y5, каждая их комбинация дает 2 пары (X1;X2), 2 пары (X3;X4), 2 пары (X5;X6), 2 пары (X7;X8) и 2 пары (X9;X10), то есть всего 2^5 = 32 комбинации исходных переменных. Таким образом, общее количество решений равно 6*32 = 192.

Почему 2^5 даёт нам комбинации исходных переменных, а умножение полученного значения на 6-количество решений?
Если это возможно, то разъяснить пожалуйста поподробнее для человека, который не знает,как находить кол-во возможных вариантов.

 Отправлено: 06.02.12 20:05. Заголовок: PavelG пишет: Почему..

PavelG пишет:

цитата:

Почему 2^5 даёт нам комбинации исходных переменных, а умножение полученного значения на 6-количество решений?

По пунктам:
1) выше (в файле B15.doc) было получено, что после замены переменных система уравнений имеет 6 решений
2) выберем какое-нибудь из этих 6 решений, то есть какие-то значения Y1...Y5, удовлетворяющие системе уравнений
3) пусть Y1=0; вспомним, что Y1=(X1=X2)=0 => X1<>X2; этому условию соответствуют 2 пары (X1,X2) - это (0,1) и (1,0)
4) пусть теперь Y1=1; аналогично находим, что есть две пары (X1,X2), удовлетворяющие этому условию - (0,0) и (1,1)
5) из пп. 3 и 4 следует, что при любому значению Y1 соответствует 2 пары (X1,X2)
6) переменные Y1..Y5 независимы, то есть, X1 и X2 входят только в Y1; X3 и X4 входят только в Y2 и т.д.
7) из п. 6 - любому решению Y1..Y5 соответствует 2 пары (X1;X2), 2 пары (X3;X4), 2 пары (X5;X6), 2 пары (X7;X8) и 2 пары (X9;X10), всего получается 2^5 = 32 комбинаций исходных переменных
8) всего решений уравнения (после замены) - 6 штук, для каждого из них существует 32 комбинации исходных переменных, поэтому общее число решений - 6*32=192.

Если что-то неясно, пишите, какой пункт непонятен.

 Отправлено: 06.02.12 22:08. Заголовок: Спасибо за такой под..

Спасибо за такой подробный ликбез.
Пункты 1-6 были понятны ещё из файла B15, а вот над пп. 7 и 8 до сих пор ломаю голову.
Непонятно само правило нахождения кол-ва возможных вариантов и откуда оно берётся(не только в этом типе задач).
Можно ли как-то этот момент пояснить ещё более подробно(возможно как для для школьников, которые впервые знакомятся с логикой)?
Или есть ли литература, в которой тщательно рассматривается данный вопрос?

 Отправлено: 06.02.12 22:38. Заголовок: PavelG пишет: над пп..

PavelG пишет:

цитата:

над пп. 7 и 8 до сих пор ломаю голову.

п. 7. Представим себе, что есть только две переменных, Y1=(X1=X2) и Y2=(X3=X4). Из п. 5 следует, что любому значению Y1 соответствует 2 пары (X1,X2), при этом X3 и X4 могут быть любыми. Если Y2 никак не ограничено, то для каждой из 2-х пар (X1,X2) существует 4 пары (X3,X4): (0,0), (0,1), (1,0) и (1,1), и общее количество комбинаций (X1,X2,X3,X4) равно 2*4=8.
Но Y2 тоже имеет какое-то известное значение, причем, так же, как и для Y1, при любом заданном значении Y2 существует только 2 (а не 4!) допустимых комбинации (X3,X4), так что общее количество комбинаций (X1,X2,X3,X4) равно 2*2=4.

Аналогично при известных значениях переменных Y1, Y2 и Y3 получаем 2*2*2=8 допустимых комбинаций (X1..X6), а для заданных Y1..Y5 - 2*2*2*2*2=32 комбинации X1..X10.

п. 8 Тут совсем просто. Есть 6 решений Y1..Y5. Для каждого из них (см. п. 7) есть 32 разных комбинации исходных переменных X1..X10. Все они разные. Поэтому всего их 6*32=192.

цитата:

Или есть ли литература, в которой тщательно рассматривается данный вопрос?

Это комбинаторика. Посмотрите файл A7k.doc в материалах для подготовки к ЕГЭ-2011 или любую книжку для школьников по этой теме.

 Отправлено: 07.02.12 13:11. Заголовок: PavelG пишет: над п..

PavelG пишет:

цитата:

над пп. 7 и 8 до сих пор ломаю голову.

Рискну вмешаться в ваш диалог.
Пусть, например, после замены переменных найдено 3 решения (У1,У2, У3,У4). Допустим, одно из решений выглядит так: (0,0,1,0). (Есть еще два каких-то сочетания).
В выбранном решении на первом месте 0, то есть уравнение У1=0 . Ясно, что вместо У1 можно поставить только ноль.
Вспоминаем, что У1=(Х1=Х2). Значит, (Х1=Х2)=0. Это может быть только набор (0,1) или (1,0) (на первом месте значение Х1, на втором Х2).
Итог: уравнение У1=0 имеет ДВА ВАРИАНТА решения в исходных обозначениях.
Подключая следующую переменную У2=(Х3=Х4)=0 мы получаем, что по аналогии У2=0 имеет ДВА ВАРИАНТА решения: набор (0,1) или (1, 0) (на первом месте значение Х3, на втором Х4).
После подключения У2 можно сформировать наборы (Х1,Х2,Х3,Х4) , удовлетворяющие уравнению, различными способами. (0,1,0,1), (0,1,1,0), (1,0,1,0) и (1,0,0,1).
Итог: при подключении второй переменной КАЖДОМУ варианту решения первого уравнения (их 2) подписывается КАЖДЫЙ вариант решения второго уравнения (их 2). Т.о. всего решений, удовлетворяющих системе 4 (они перечислены выше).
Ясно, что при подключении У3=(Х5=Х6)=1 надо к каждому предыдущему решению «подцепить» оба варианта (0,0) и (1,1) (на первом месте значение Х5, на втором Х6). Т.е КАЖДОЕ из 4-х решений «раздваивается»:
(0,1,0,1,0,0), (0,1,1,0,0,0), (1,0,1,0,0,0) (1,0,0,1,0,0)
(0,1,0,1,1,1), (0,1,1,0,1,1), (1,0,1,0,1,1) (1,0,0,1,1,1)
И их становится 8. После подключения У4 «раздвоится» каждое из 8, и т.д.
Значит, если одно решение состоит из 4 переменных, то в исходных переменных оно соответствует 16 вариантам.
Можно сразу сказать, что число вариантов решений в исходных обозначениях вычисляется по формуле 2^n, где n – КОЛИЧЕСТВО переменных в решении.
Теперь вспоминаем, что мы нашли 3 решения и у каждого 16 вариантов. Значит, всего 16*3=48 вариантов решений.

 Отправлено: 12.02.12 13:28. Заголовок: Большое спасибо, нак..

Большое спасибо, наконец понял. Более подробно объяснить,наверное, просто невозможно.

 Отправлено: 18.02.12 10:25. Заголовок: Доброго времени суто..

Доброго времени суток, всем!!!
Дана система
a -> b или c и ¬d=1
c -> d или e и ¬f=1
e ->f или g и ¬h=1
g ->h или i и ¬j=1
i -> j или a и ¬ b =1
Сколько решений имеет система?
Я понимаю, что похожа на систему в начале разговора, но что делать с (a и ¬ b), как его из наборов вытащить?

 Отправлено: 18.02.12 10:26. Заголовок: Светлана пишет: Я по..

Светлана пишет:

цитата:

Я понимаю, что похожа на систему в начале разговора, но что делать с (a и ¬ b), как его из наборов вытащить?

Пожалуйста сформулируйте вопрос внятно.

 Отправлено: 18.02.12 18:57. Заголовок: Поляков Константин ..

Константин Юрьевич, извините за сумбурный вопрос!
Дана система:
a -> b или c и ¬d=1
c -> d или e и ¬f=1
e ->f или g и ¬h=1
g ->h или i и ¬j=1
i -> j или a и ¬ b =1

Если решать ее до 4 выражения, как рассматривали выше, получается 364 набора.
Затем в пятом выражении первое слагаемое (i -> j) - это инверсия для второго слагаемого в четвертом выражении и второе слагаемое (a и ¬ b) - инверсия для первого слагаемого в первом выражении. Как их исключить из общего набора решений.
Все равно сумбурно!! Видимо логика не мое:((

 Отправлено: 18.02.12 19:22. Заголовок: Светлана пишет: Зате..

Светлана пишет:

цитата:

Затем в пятом выражении первое слагаемое (i -> j) - это инверсия для второго слагаемого в четвертом выражении и второе слагаемое (a и ¬ b) - инверсия для первого слагаемого в первом выражении.

Понятно. К системе уравнений, с которой начался топик, добавили еще «замыкание»:

i -> j или a и ¬ b =1 

На мой взгляд, тут проще всего применить подход с заменой переменных (см. ответ PVV). В данном случае он выглядит так:

цитата:

Обозначим в вашей системе k=not(a)+b, l=not(c)+d, m=not(e)+f, n=not(g)+h, o=not(i)+j. (+ соответствует дизъюнкции). Тогда система уравнений может быть записана так: k + not(l) = 1; l + not(m) = 1; m + not(n) = 1; n + not(o) = 1; o + not(k) = 1.

Указанная система уравнений с 5 переменными имеет ровно 2 различных решения: (0;0;0;0;0) и (1;1;1;1;1).
Так как переменные k, l, m, n, o независимы и каждая из них принимает значение 0 в одном случае, а значение 1 - в трех случаях, то получаем, что первое решение полученной системы дает одно решение исходной системы, второе - 243. Сумма этих чисел равна 244.

 Отправлено: 18.02.12 20:20. Заголовок: Спасибо, Константин ..

Спасибо, Константин Юрьевич!!!

 Отправлено: 18.02.12 18:10. Заголовок: Здравствуйте,Констан..

Здравствуйте,Константин.
У вас в файле, который посвящен заданию В15(и в др. тоже), представлено множество различных типов заданий. Какова вероятность встретить на ЕГЭ каждый из приведённых типов, или в этом году буду представлены только системы? А также насколько велика возможность сюрпризов и насколько нынешний демо вариант отражает структуру будущего экзамена (например, по словам моего учитель, системы в прошлом году были даны без предупреждения).
Заранее спасибо за прояснение ситуации.

 Отправлено: 18.02.12 18:21. Заголовок: PavelG пишет: У вас..

PavelG пишет:

цитата:

У вас в файле, который посвящен заданию В15(и в др. тоже), представлено множество различных типов заданий. Какова вероятность встретить на ЕГЭ каждый из приведённых типов, или в этом году буду представлены только системы? А также насколько велика возможность сюрпризов и насколько нынешний демо вариант отражает структуру будущего экзамена (например, по словам моего учитель, системы в прошлом году были даны без предупреждения).

Официальная информация - это интервью с М.А. Ройтбергом, он в конце объясняет, что задания демо-варианта не обязаны совпадать с "боевыми" задачами. То, что реальное задание в В15 будет отличаться от демо-варианта - практически 100%. Это традиция :-). Возможно, будет одно уравнение, а не система. Кто знает подробнее - ничего не расскажет, потому что связан подпиской о неразглашении. Поэтому решайте разные задачи, тренируйтесь. Нужно быть готовым ко всему. :-)

 Отправлено: 20.02.12 12:10. Заголовок: Непонятна фраза

Константин Юрьевич!
Простите, но нельзя ли подробнее объяснить эту фразу из Вашего ответа от 18 февраля на этой ветке форума:
ЦИТАТА: "Так как переменные k, l, m, n, o независимы и каждая из них принимает значение 0 в одном случае, а значение 1 - в трех случаях".
0 в каком случае, значение 1 в трех каких случаях?
С уважением, Абитуриент

 Отправлено: 20.02.12 12:26. Заголовок: Абитуриент пишет: &#..

Абитуриент пишет:

цитата:

"Так как переменные k, l, m, n, o независимы и каждая из них принимает значение 0 в одном случае, а значение 1 - в трех случаях". 0 в каком случае, значение 1 в трех каких случаях?

Вспомним, что k=not(a)+b. Поэтому k=0 при (a,b)=(1,0) и k=1 при (0,0), (0,1) и (1,1).