Двоїстість і самодвоїстих булевих функцій, it- starter

Двійковий набір, протилежний заданому завжди можна отримати операцією поразрядного заперечення (в сенсі поразрядной операції not мови ТурбоПаскаль) цього заданого набору.

Наприклад, для <0010 1111> протилежним набором буде <1101 0000> і, звичайно, навпаки. Тобто набори <0010 1111> і <1101 0000> протилежні (один одному).

Слід звернути особливу увагу на те, що у визначенні 1 мова йде не тільки про протилежних двійкових наборах значень змінних функцій f і g. але і про протилежні значеннях самих функційf і g на цих наборах (f (...) = not g (...)).

Розглянемо безліч всіх БФ арності n і бінарне відношення подвійності на цій множині. Будь-які дві ф-ції f n і g n знаходяться в цьому відношенні (належать йому), тоді і тільки тоді, коли g n двоїста до f n.

Очевидно, це стосується не рефлексивно. не транзитивній (покажіть це!), але зате симетрично.

Тобто якщо відношення подвійності позначити, наприклад, через '

', То для будь-яких БФ f n і g n з розглянутого безлічі завжди істинна імплікація: (g n

Це дозволяє нам говорити просто про (взаємної) подвійності / НЕ подвійності будь-яких двох розглянутих n-місних функцій, узятих в довільному порядку.

З урахуванням сказаного, можна дати наступне визначення (взаємної) подвійності БФ.

Визначення 2. Дві булеві функції однаковою арності називаються подвійними один до одного. якщо вони на всіх протилежних наборах приймають протилежні значення.

Зауважимо, що вимога однаковою арності в наведених визначеннях не є принциповим, тому що (І ми це вже повинні не тільки знати, а й уміти показати!) Будь-які дві БФ можна завжди привести до однієї і тієї ж арності додаванням, якщо необхідно, фіктивних змінних.

Побудова двоїстих функцій.

Введемо стандартне позначення. Булеву функцію, двоїсту f будемо позначати як f *.

Нехай ф-ція f задана таблицею зі стандартним упорядкуванням рядків. Покажемо, як по цій таблиці для f можна побудувати так само впорядковану таблицю для f *.

1. Розгорнути стовпець значень f n навколо центральної його точки на 180 o (останнє значення в стовпці стане 1-м, передостаннє - 2-м і т.д.);
2. Виконати поразрядное заперечення значень розгорнутого шпальти (тобто замінити в ньому нулі на одиниці, а одиниці на нулі);
3. Отриманий в результаті зазначених вище дій стовпець записати в стандартно впорядковану таблицю як стовпець значень функції f *.

Обгрунтування цього алгоритму надається Новомосковсктелю. Розглянемо приклад.

Я сумніваюся, але ставлення подвійності, якщо має місце f (a1, ..., an) = not g (not a1, ..., not an), що не рефлексивно, тому що
f (a1, ..., an) не дорівнює not f (not a1, ..., not an) і
g (a1, ..., an) не дорівнює not g (not a1, ..., not an)?
Наприклад, f = (0001)
f (0 1) = 0
not (f (1 0)) = 1.
Це відношення симетрично, тому що g (a1, ..., an) = not f (not a1, ..., not an). У симетричності можна переконатися, побудувавши двоїсту функцію f * для деякої функції f і двоїсту функцію f ** для f *. f ** буде збігатися з f.
З транзитивності я теж сумніваюся. Якщо f (a1, ..., an) = not g (not a1, ..., not an), то g (a1, ..., an) = not f (not a1, ..., not an). Тобто f двоїста функція до g в силу симетричності. Але по транзитивності має виконуватися f (a1, ..., an) = not f (not a1, ..., not an), а це не вірно в силу не рефлексивності.

Приклади самодвоїстих функцій:
f (x) = (0 1)
f (x, y) = (0 1 0 1)
f (x, y) = (1 0 1 0)
f (x, y) = (0 0 1 1)
f (x, y) = (1 1 0 0)
f (x, y, z) = (0 1 0 1 0 1 0 1)
f (x, y, z) = (1 0 1 0 1 0 1 0)
f (x, y, z) = (0 0 0 0 1 1 1 1)
f (x, y, z) = (1 1 1 1 0 0 0 0)
f (x, y, z) = (0 0 1 1 0 0 1 1)
f (x, y, z) = (1 1 0 0 1 1 0 0)
Стовпець самодвоїстих функції дорівнює стовпчику якої-небудь змінної або заперечення стовпця будь-якої змінної? Але тоді виходить, що всі інші змінні фіктивні і їх можна викреслити, і функція зведеться функції від однієї змінної.