Рубрики

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 65

Двойственное число булевой функции f (x1, x2,…, xn, +, ∙, ′), записанное как F D , является тем же выражением
как у F с + и. местами. F называется самодвойственным, если F = F D. Количество самодвойственных
функции с n булевыми переменными
(А) 2 н
(Б) 2 н-1
(С) 2 2 н
(D) 2 2 н-1

Ответ: (D)
Пояснение: Вопрос требует нет: самодвойственных функций для n переменных.

Принцип двойственности: любая теорема или тождество в булевой алгебре остается верной, если 0 и 1 поменялись местами и. и + поменялись местами.

Есть два свойства для самодвойственных функций:
1. Он нейтрален (нет minterms = нет maxterms)
2. Одна функция не содержит двух взаимоисключающих терминов.

Учитывая вышеперечисленные свойства.
Если у нас есть n-переменная, то у нас есть 2 ^ n minterms / maxterms
Из 2 ^ n minterms / maxterms существует (2 ^ n) / 2 взаимоисключающих пары. то есть 2 ^ (н-1)

Таким образом, у нас есть 2 ^ (n-1) пар, которые можно использовать для создания самодуальных функций.
Итак, по Основному принципу подсчета, потому что каждая пара в 2 ^ (n-1) имеет два варианта.

Нет самодвойственных функций из n-переменных = 2 * 2 * 2… 2 ^ (n-1) раз

= 2 ^ (2 ^ (n-1))

или пример, если n = 3
У нас есть minterms как (000,001,010,…, 111)
Взаимоисключающими парами являются (0,7), (1,6), (2,5), (3,4)
Пары являются взаимоисключающими, поскольку они не могут выполнять двойственную функцию.

Итак, здесь у нас есть 2 * 2 * 2 * 2 функции, т.е. 16.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2014- (Set-2) | Вопрос 65

0.00 (0%) 0 votes