Задача по булевой алгебре... (... поставила меня в тупик :()

[georgy_sh]

Привет Всем!
Извините, если пишу не в тему форума, но все-таки. Сразу предупреждаю, что задачка не по программированию. Вопрос: найти решение системы булевских уравнений.

Вот ссылка на наглядное условие: http://files.buq.ru/%5Cfiles%5C43153246330...acha_info_2.png

Ума не приложу, с чего начать - так что надеюсь только на Вашу помощь!
Заранее благодарю за любую помощь!

Задача со вступительных экзаменов - разве в школе когда-либо такое учили? Просто нет слов

[WolfON]

Можно использовать генетические алгоритмсы для подбора всех параметров.
Но если у тебя мозг работает на частоте ниже 2Ггц, то это займет много времени.

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

К стати, вуз не ЛИТМО случаем?

[Alxn1]

Первое, что на ум пришло - расписать таблицу истинности для левой и правой части первого равенства. Далее, найти строчки, где X4 = 1 и совпадают значения обеих частей первого равенства. Это и будут решения данной системы (может быть оно будет и одно). Так как всего переменных 5, то таблица не такая и большая получится. ( 2^5 = 32 )

[diesel]

!(!(X1+X2)&(!X3+X5))+!X4*(X1*X5+X2*X4)=!X1+X2*!X5

X4=1

X4=1, значить !X4=0, т.е. второе слагаемое в правой части равно нулю и от него ничего не зависит.

Уже гораздо проще. Дальше можно раскрыть скобки.
!(!(X1+X2)*(!X3+X5))=!X1+X2*!X5

!(!X1*!X3+!X1*X5+!X2*!X3+!X2*X5)=X1*X3 + X1*!X5 + X2*X3 +X2*!X5

X1*X3+X1*!X5 + X2*X3=!X1

А вот дальше можно подобрать.
X1 X2 X3 X5
0 0 0 0 0
1 0 0 0 1
0 1 0 0 0
1 1 0 0 1
0 0 1 1 0
1 0 1 1 1
0 1 1 1 1 --> ответ
1 1 1 1 1

Х1 =0; X2=1; X3=1; X5=1 - вроде подходит.

Принцип должен быть понятен - в вычислениях мог ошибиться, все-таки легче это на бумажке думать, а не в текстовом редакторе.

[KiWi]

Мдемс...
При решении использовано:

Код: Выделить всё

!1 = 0
!0 = 1
0 & anything = 0
!(A|B) = !A & !B
подстановка разных значений
A&B = 0 <=> A = 0 || B = 0
A | B = 0 <=> A = 0 & B = 0

Ответы:
0, 0, 0, 1, 0
0, 0, 0, 1, 1
0, 0, 1, 1, 0
0, 0, 1, 1, 1

0, 0, 0, 1, 1
0, 0, 1, 1, 1
0, 1, 0, 1, 1
0, 1, 1, 1, 1

1, 1, 0, 1, 1
1, 1, 1, 1, 1

1, 0, 1, 1, 0


P.S.: не люблю булевую алгебру -- скучная, так что мог накосячить.
P.P.S.: попробовал подставить несколько -- вроде подходят

Знал же, что где-нить, но ошибся -- одно отрицание в условии пропустил

[diesel]

to IFL
Может вы ход решения покажите?

[georgy_sh]

К стати, вуз не ЛИТМО случаем?

ННГУ

[georgy_sh]

Мдемс...
При решении использовано:
!1 = 0
!0 = 1
0 & anything = 0
!( A | B ) = !A & !B
подстановка разных значений
A&B = 0 <=> A = 0 || B = 0
A | B = 0 <=> A = 0 & B = 0

А разве операция "+" это дизъюнкция?
Я в справочнике читал, что это (А + В) исключающее "ИЛИ", то есть логическое сложение. Следовательно для него таблица истинности будет такова:
A B A+B
0 0 0
0 1 1
1 0 1
1 1 0
Справочник: http://psi-logic.shadanakar.org/bool/bool.htm


И еще одна маленькая просьба: не могли бы Вы действительно полностью описывать ход решения, так как это для меня очень важно - в школе сроду такого не проходили

[diesel]

A+B - Это просто "ИЛИ" .. вообще-то
!А - Это "НЕ"
A*B = Это "И"

Свойства можно описать так: !(A+B)*C=!A*C+!B*C - т.е. все так же как и в обычной жизни :)

[georgy_sh]

A+B - Это просто "ИЛИ" .. вообще-то
!А - Это "НЕ"
A*B = Это "И"

Свойства можно описать так: !(A+B)*C=!A*C+!B*C - т.е. все так же как и в обычной жизни

Извините, ошибся с ссылкой - вот верная: http://psi-logic.shadanakar.org/boo/boo.htm
diesel обратите внимание сюда - http://psi-logic.shadanakar.org/boo/boo_02.htm - тут ближе к концу есть таблицы - оттуда я это и взял %)

[KiWi]

to IFL
Может вы ход решения покажите?

На самом деле, если брать моё кривое условие, то пожалуйста....

Правда, сначала по поводу + -- не знаю, я нечто, что проходили под видом булевой алгебры на ИВТ почётно слил...

Вообщем,
Примечание: 1 -- X1, ..., 5 -- X5

Код: Выделить всё

(!(1|2))&(!3|5)|!4&(1&5|2&4) = !1|2&!5
В силу 4 = true, то есть !4 = false имеем:
!1&!2&(!3|5) = !1|2&!5
!1&!2&!3|!1&!2&5 = !1|2&!5
При 1 = true:
2&!5 = false -- есть вполне очевидная вещь
При 1 = false:
!2&!3|!2&5 = 2&!5
 2 = true:
 !5 = false -- ...
 2 = false:
 !3|5 = 0 -- ...

Кстати, по ходу решения у меня возникло сомнение в законности перехода от !(X1+X2)*(!X3+X5) к !X1*!X3+!X1*X5+!X2*!X3+!X2*X5 -- так как !(A|B) != !A|!B

Хотя, посмотрел я справочник -- + в кружочке, обозначающий исключающее "или", на самом деле, абстракная операция :-) помню, как мы когда-то на алгебре занимались кольцами, точками в кружочке и подобным бредом :-)

[diesel]

Извините, ошибся с ссылкой - вот верная: http://psi-logic.shadanakar.org/boo/boo.htm
diesel обратите внимание сюда - http://psi-logic.shadanakar.org/boo/boo_02.htm - тут ближе к концу есть таблицы - оттуда я это и взял %)

Гм .. меня учили что "+" - это ИЛИ ... Если исключающие ИЛИ, то блин тут решение намного сложнее получится .. для него скобки раскрыть не получится ....

to IFL вы там пропустили общее "НЕ" которое для первого слагаемого стоит .. т.е. не (!(1|2))&(!3|5), а !((!(1|2))&(!3|5))

[georgy_sh]

IFL, так что же мне делать?
Выше я кинул ссылку на неплохой, ИМХО, справочник по булевой алгебре( http://psi-logic.shadanakar.org/boo/boo_02.htm - вот, что Вас будет интересовать). Посмотрите, может он Вам пригодится?
--------------
Все равно надеюсь на Вашу помощь!

Извините, ошибся с ссылкой - вот верная: http://psi-logic.shadanakar.org/boo/boo.htm
diesel обратите внимание сюда - http://psi-logic.shadanakar.org/boo/boo_02.htm - тут ближе к концу есть таблицы - оттуда я это и взял %)

Гм .. меня учили что "+" - это ИЛИ ... Если исключающие ИЛИ, то блин тут решение намного сложнее получится .. для него скобки раскрыть не получится ....

Выше я кинул ссылку на справочник - может он глючит?

[KiWi]

to IFL вы там пропустили общее "НЕ" которое для первого слагаемого стоит .. т.е. не (!(1|2))&(!3|5), а !((!(1|2))&(!3|5))

Я, вообщем-то, об этом дописал потом, а перерешивать лень, ибо идея понятна, да и не особо сильно измениться...
Вообщем, предлагаю забить на всё, ибо не моё, не ваше решение в текущем виде неправильны :-)
По поводу

Код: Выделить всё

!(A|B) = !A|!B

Это, на самом деле, можно сравнить с

Код: Выделить всё

(A+B)^2 = A^2 + B^2

-- они оба неправильны :-)

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

Вообщем, !((!(1|2))&(!3|5)) = !(!1&!2&(!3|5)) = 1|2|3&!5, если опять-таки ничего не путаю.

[georgy_sh]

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

Как раз в этом ":ю/*+:?№%:?" /*ну Вы меня поняли*/ справочнике :-) плюс и плюс в кружочке - одно и то же

[diesel]

Как раз в этом ":ю/*+:?№%:?" /*ну Вы меня поняли*/ справочнике :-) плюс и плюс в кружочке - одно и то же

Вообще я бы на вашем месте действительно спросил у препода ... Потому что обозначить можно как угодно ... Справочник действительно удивил ... даже очень удивил ...

[neuralNetwork]

В математической литературе обычно "+" - это "исключающее или", в программистской встречается всё что угодно, в т. ч. и обычное. Здесь, думаю, стоит считать "+" обычным "или", исключающее применяется не слишком часто.
Способ решения: т. к. X4=1, то второе слагаемое в левой части равно 0. Далее можно упростить левую часть:

!(!(X1+X2)*(!X3+X5)) = (X1+X2)+!(!X3+X5) = X1+X2+(X3*!X5).

Использовались формулы де Моргана:

!(X+Y) = !X*!Y,
!(X*Y) = !X+!Y

и правило двойного отрицания:

!!X = X.

Далее строим таблицы истинности для формул в обеих частях равенства и сравниваем их построчно. Те наборы переменных, для которых значения обеих частей окажутся одинаковыми, записываем в ответ.
2He1mut: Мой совет: прочитайте предложенный выше учебник до раздела "сложные формулы" включительно. Этого должно быть достаточно.

[georgy_sh]

В математической литературе обычно "+" - это "исключающее или", в программистской встречается всё что угодно, в т. ч. и обычное. Здесь, думаю, стоит считать "+" обычным "или", исключающее применяется не слишком часто.
Способ решения: т. к. X4=1, то второе слагаемое в левой части равно 0. Далее можно упростить левую часть:

!(!(X1+X2)*(!X3+X5)) = (X1+X2)+!(!X3+X5) = X1+X2+(X3*!X5).

Использовались формулы де Моргана:

!(X+Y) = !X*!Y,
!(X*Y) = !X+!Y

и правило двойного отрицания:

!!X = X.

Далее строим таблицы истинности для формул в обеих частях равенства и сравниваем их построчно. Те наборы переменных, для которых значения обеих частей окажутся одинаковыми, записываем в ответ.
2He1mut: Мой совет: прочитайте предложенный выше учебник до раздела "сложные формулы" включительно. Этого должно быть достаточно.

Спасибо за совет!

[georgy_sh]

Привет Всем!
Странно как-то у меня получилось. Задачи этого типа я решать научился спокойно и "+" действительно "сложение по модулю 2".
На вступительных экзаменах в университете сказали, что "+" - это простое логическое сложение (!) и задачи такого типа надо решать сразу с помощью таблицы истинности (!)
Мда...
[OFFTOP]
Ну да ладно. Кстати, мне удалось поступить в ННГУ на "механико-математический факультет" по специальности "прикладная математика и информатика", так что Всем спасибо за поддержку!
Теперь в Нижнем Новгороде жить буду.
[OFFTOP]

[aLexx programmer]

Термин

логическое сложение

↑

эквивалентен термину

"сложение по модулю 2"

↑

если true и false представлять как 0 и 1.

[georgy_sh]

Термин

логическое сложение

↑

эквивалентен термину

"сложение по модулю 2"

↑

если true и false представлять как 0 и 1.

А как же

Код: Выделить всё

1 плюс 1

и

Код: Выделить всё

1 плюс в кружочке 1

?
Разница есть!!!

[fatboy]

a+b <=> a OR b
a+ в кружочке ( ) b <=> a XOR b

[georgy_sh]

a+b <=> a OR b
a+ в кружочке ( ) b <=> a XOR b

Так оно и есть