Решение задач «Для каждого класса Поста проверьте, существует ли функция»,
Дискретная математика в Новосибирске

Для каждого класса Поста проверьте, существует ли функция, которая лежит в этом классе Поста, но не лежит ни в одном из четырех других. Для каждого класса Поста проверьте, существует ли функция, которая не лежит в этом классе Поста, но лежит в четырех остальных. Будем говорить, что функция существенно зависит от переменной xi , если существует два набора аргументов, различающихся только значением xi , на которых функция принимает различные значения. Сколько существует булевых функций от n аргументов, существенно зависящих от всех аргументов? Достаточно привести рекуррентную формулу. Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая лежит во всех 5 классах Поста. Приведите пример функции, существенно зависящей хотя бы от 3 аргументов, которая не лежит ни в одном классе Поста. Булева функция f(x1,x2,…,xn) называется форсируемой, если существует такое назначение xi=const , что для любых значений других переменных значение функции является константой. Например, x1?x2 является форсируемой, поскольку при x1=0 значение функции равно 0 для любого значения x2 . Для каждой функции от двух переменных определите, является ли она форсируемой. Булева функция называется симметричной, если ее значение не меняется при любой перестановке ее переменных. Сколько существует симметричных функций от n переменных? Какие симметричные булевы функции являются пороговыми? Докажите, что любую функцию от n переменных можно представить с использованием стрелки Пирса формулой, длиной не больше чем 2n?poly(n) , где poly(n) - полином, общий для всех функций Докажите, что любую монотонную функцию можно выразить через "и", "или", 0 и 1. Докажите, что любую монотонную самодвойственую функцию можно выразить через медиану Говорят, что формула находится в 2-КНФ (или форме Крома). если она имеет вид (t11?t12)?(t21?t22)?… , где tij представляет собой либо переменную, либо ее отрицание (в каждом клозе ровно две переменных или отрицания переменной). Докажите, что если булеву функцию f можно задать в форме Крома (в виде 2-КНФ), то выполнено следствие: f(x1,...,xn)=f(y1,...,yn)=f(z1,...,zn)=1 ?f(?x1,y1,z1?,...,?xn,yn,zn?)=1 Докажите, что если выполнено следствие: f(x1,...,xn)=f(y1,...,yn)=f(z1,...,zn)=1 ?f(?x1,y1,z1?,...,?xn,yn,zn?)=1 , то булеву функцию f можно задать в форме Крома. Докажите, что если булеву функцию f можно задать в форме Хорна, то выполнено следствие: f(x1,...,xn)=f(y1,...,yn)=1?f(x1?y1,...,xn?yn)=1 Докажите, что если выполнено следствие: f(x1,...,xn)=f(y1,...,yn)=1?f(x1?y1,...,xn?yn)=1 , то булеву функцию f можно задать в форме Хорна Докажите, что x0?x1?…?x2m=?¬x0,s1,s2,…,s2m? , где sj=?x0,xj,xj+1,…,xj+m?1,¬xj+m,¬xj+m+1,…,¬xj+2m?1? , для удобства x2m+k обозначет то же, что и xk для k?1 . Докажите, что биномиальный коэффициент Ckn нечетен тогда и только тогда, когда в двоичной записи k единицы стоят только на тех позициях, где в двоичной записи n также находятся единицы (иначе говоря, двоичная запись k доминируется двоичной записью n как двоичным вектором). Изучите и докажите "метод треугольника" построения полинома Жегалкина по таблице истинности.