0
голосов
0
ответов
22 показа
Критерий полноты системы в классе самодвойственных функций
Доказать, что замыкание системы К равно S тогда и только тогда, когда К содержит хотя бы по одной функции из классов S\To, S\T1, S\L, S\M.
0
голосов
0
ответов
12 показов
Получение самодвойственной функции из не линейной функции
Доказать, что из всякой не линейной самодвойственной функции можно с помощью операции отождествления переменных получить нелинейную самодвойственную ф ...
0
голосов
0
ответов
14 показов
Базис класса
Обязательно ли базис замкнутого класса булевых функций должен состоять из не более, чем четырех функций(по аналогии с базисом всех булевых функций)?
0
голосов
0
ответов
27 показов
Раскраска ребер графа
Для заданного графа G=(V, E) построить булеву формулу полиномиального размера, которая истинна тогда и только тогда, когда существует раскраска ребер ...
0
голосов
0
ответов
31 показ
Существует ли полиномиальный алгоритм
Предположим P!=NP. Существует ли полиномиальный алгоритм, который по заданной формуле f определяет > или =2 число выполняющих условий (satisfying a ...
1
голос
1
ответ
56 показов
Размер независимого множества в графе
Граф (без петель и кратных ребер) имеет 10 вершин и 20 ребер. Какой максимальный возможный размер независимого множества в таком графе ?
0
голосов
0
ответов
24 показа
Булева формула только из импликаций
Предположим, булева формула А состоит из переменных с использованием только импликаций. Может ли отрицание А быть тавтологией ? Если да, то привести п ...
0
голосов
1
ответ
25 показов
Замкнутость предполного класса
Класс функций К называется предполным в классе М, если он не является полным в М, и становится таковым при добавлении любой одной функции из М\К. Дока ...
0
голосов
1
ответ
35 показов
Конечность базиса замкнутого класса
Доказать, что если замкнутый класс имеет конечный базис, то всякий базис этого класса конечен.
0
голосов
0
ответов
38 показов
Сколько существует неизоморфных лесов с четырьмя вершинами (свободное дерево также считается лесом)?
Сколько существует неизоморфных лесов с четырьмя вершинами (свободное дерево также считается лесом)? Подскажите, пожалуйста
0
голосов
0
ответов
57 показов
Каково минимальное число ребер в графе?
Каково минимальное число ребер в графе с восемью вершинами и тремя компонентами связности? Подскажите, пожалуйста
1
голос
1
ответ
64 показа
Найти длину наименьшего пути
Граф K6 состоит из 6 вершин, каждая пара которых соединена ребром. Найдите наименьшую длину пути, проходящего по всем рёбрам этого графа. (напомним, ч ...
0
голосов
0
ответов
37 показов
Замыкание класса [закрыт]
Пусть m(x1, x2, x3)=x1x2+x1x3+x2x3(функция голосования). Доказать, что S=[(не)x1, x1+x2+x3, m(x1,x2,x3)]. (S-класс самодвойственных функций).
0
голосов
0
ответов
240 показов
Докажите, что в любом турнире есть вершина, из которой достижима любая вершина турнира. [закрыт]
Можно ли сказать, что задача сводится к доказательству гамильтонова пути?Имеется в виду ориентированный граф.
-1
голосов
0
ответов
51 показ
Теория графов
Дана таблица 100 х 2 (где 100 строк и 2 столбца), которая заполнена числами 0, 1, ..., 9 и выполнены следующие условия: 1) все строки различны; 2) нел ...
1790 вопросов
Связанные метки
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.