Как доказать ассоциативность сложения по модулю 2?

[larkova_alina]

Как доказать ассоциативность сложения по модулю 2?
$(a \oplus b) \oplus c = a \oplus (b \oplus c)$
Можно это доказать не прибегая к составлению таблиц истинности?

[xmaister]

А что такое $\oplus$ по определнию?

[larkova_alina]

$a \oplus b $ означает, что $a \neq b$, или что тоже самое, верно только a или только b.

[xmaister]

Нет, тут что-то бессмысленное написано. Формально мы можем определить $\oplus:\mathbb{N}\times\mathbb{N}\to\{0,1\}$, так что $\oplus (n,m)=1\Leftrightarrow 2\not |n+m$

[larkova_alina]

xmaister, я имела сложение по модулю 2 в булевой алгебре.

[xmaister]

Дык не важно же, тогда будем рассматривать $\oplus:\{0,1\}^2\to\{0,1\}$, график отображения определим аналогичным образом.

Тут сложение аналогично сложению в поле $\mathbb{F}_2$

[larkova_alina]

Ну а как доказать ассоциативность то?

-- 15.11.2012, 22:58 --

Вот так правильно:
$a \oplus b =1 $ означает, что $a \neq b$, или что тоже самое, верно только a или только b.

[arseniiv]

Ну и переведите гомоморфно в него. Ай, поздно переводить.

А если по-простому и без таблицы истинности, перепишите его через конъюнкцию, дизъюнкцию и отрицание, а там ясно как преобразовывать. Потом правую часть так же (если к ней сразу не приведётся).

(Хотя таблица истинности в восемь строк — вроде бы не великая беда…)

[Aritaborian]

arseniiv в сообщении #645130 писал(а):

Хотя таблица истинности в восемь строк — вроде бы не великая беда

Кто знает, может, по условию задачи запрещено использовать таблицы истинности.

[xmaister]

$2|(a\oplus b)+ c\Leftrightarrow (a\oplus b)\equiv c\pmod2\Leftrightarrow a+b\equiv c\pmod2\Leftrightarrow a+c\equiv b\pmod2\Leftrightarrow 2|a+(b\oplus c)$

[arseniiv]

Aritaborian, да, потому в скобках.

Интересно, а подстановка значений вместо одной из переменных (скажем, $b$) будет ли считаться использованием таблицы истинности?

[larkova_alina]

$a \oplus (b \oplus c)$
$(a \vee ((b \vee c) \wedge \neg (b\wedge c))) \wedge \neg (a \wedge ((b \vee c) \wedge \neg (b \wedge c)))$
...........................................
$(a \vee c \vee b)\wedge (a \vee \neg b \vee \neg c) \wedge (c \vee \neg b \vee \neg a) \wedge (\neg a \vee \neg c \vee \neg b).$
В последнее выражение $a$ и $c$ входят симметрично.

[arseniiv]

larkova_alina в сообщении #645143 писал(а):

$(a \vee c \vee b)\wedge (a \vee \neg b \vee \neg c) \wedge (c \vee \neg b \vee \neg a) \wedge (\neg a \vee \neg c \vee \neg b).$

Не та последняя дизъюнкция.

[larkova_alina]

arseniiv, а по моему все верно. Уже три раза проверила.

[arseniiv]

Это у вас, как видите, СКНФ. Каждая имеющаяся дизъюнкция в ней соответствует нулю в определённом месте таблицы истинности реализуемой ею функции, а каждая отсутствующая — единице.

Сумма по модулю 2 равна нулю тогда, когда просто сумма — чётная (это на любое количество слагаемых можно обобщить). Итак, нули должны быть там, где количество аргументов, равных 1, чётное — это либо там, где они все нулевые, либо там, где два из них единичны, а один нулевой. Последняя же дизъюнкция соответствует набору $(1, 1, 1)$, но $(1\oplus1)\oplus1 \ne 0$.