Форум программистов, компьютерный форум, киберфорум
Наши страницы
Мат. логика и множества
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.74/27: Рейтинг темы: голосов - 27, средняя оценка - 4.74
Мила=)
4 / 4 / 0
Регистрация: 15.05.2010
Сообщений: 39
1

полнота класса булевых функций

13.07.2011, 17:01. Просмотров 4820. Ответов 1
Метки нет (Все метки)

Является ли полным класс булевых функций.
0
Изображения
 
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.07.2011, 17:01
Ответы с готовыми решениями:

Замкнутые классы и полнота систем булевых функций. Минимизация функций алгебры логики
1. Проверить, полна ли система функций А. 2. По заданной д.н.ф. D с помощью...

Полнота системы функций
Здравствуйте. Вся суть на фото. Своих наработок предоставить не могу, т.к. не...

Доказать свойство булевых функций от n аргументов и полных систем функций
Докажите, что среди булевых функций от n аргументов имеется ровно ...

Нахождение производных булевых функций и доказательство полноты системы функций
1) Найти все производные следующей булевой функции. 2) Доказать полноту...

Решение задач с применением булевых функций. Для каждой из функций заданных формулой составить: сднф и скнф
http://www.cyberforum.ru/attachment.php?attachmentid=345772&stc=1&d=1387707019...

1
v1cont
42 / 42 / 15
Регистрация: 23.09.2009
Сообщений: 63
25.07.2011, 09:39 2
На самом деле все просто и доступно, если покопаться в Инете
http://freddycrueger.livejournal.com/3506.html
{↓,+}
Если так:
f1(x,y) = x↓y = ¬x¬y
f2(x,y) = x+y = x v y

Воспользуемся критерием Поста. Проверим каждую из этих функций на принадлежность к замкнутым классам P0, P1, L, S, M.
1) P0 - класс функций, сохраняющих нуль (т.е если f(0,0,...,0)=0, то f принадлежит этому классу). Проверяем
f1(0,0) = 1
f2(0,0) = 0
2) P1 - класс функций, сохраняющих единицу (т.е если f(1,1,...,1)=1, то f принадлежит этому классу).
f1(1,1) = 0
f2(1,1) = 1
3)L-класс фунций, представимы линейным многочленом Жегалкина.
f1(x,y) = ¬x¬y = xy + x + y + 1 - нелинейный многочлен - не принадлежит
f2(x,y) = x v y = xy + x + y - нелинейный многочлен - не принадлежит
4) S - класс самодвойственных функций. То есть функций, для которых выполняется:
f(x1,x2,...,xn)=¬f(¬x1,¬x2,...,¬xn)
Самодвойственность проще всего определять по таблице значений функции.
f3 = ¬f1(¬x,¬y) = ¬(¬(¬x)¬(¬y)) = ¬(xy) = ¬x v ¬y
f4 = ¬f2(¬x,¬y) = ¬(¬x v ¬y) = xy
__________________
x y | f1 | f2 |f3 | f4 |
----|---|---|---|---|
0 0 | 1 | 0 | 1 | 0 |
0 1 | 0 | 1 | 1 | 0 |
1 0 | 0 | 1 | 1 | 0 |
1 1 | 0 | 1 | 0 | 1 |
--------------------
f1 ≠ f3, f2 ≠ f4

5) M -класс монотонных функций.
Функция f называется монотонной, если для любых наборов значений переменных (α1,α2,...,αn) и (β1,β2,...,βn), таких что (α1,α2,...,αn)≤(β1,β2,...,βn), выполняется f(α1,α2,...,αn)≤f(β1,β2,...,βn).
f1 - не монотонна, f2 - монотонна.

Теперь, когда мы проверили все функции на принадлежность к этим пяти классам, можно построить таблицу Поста.

F |P0|P1| L |S | M|
-------------------
f1| - | - | - | - |- |
f2|+ | + | - | - |+ |

Согласно критерию Поста, чтобы система функций была полна, необходимо и достаточно, чтобы в каждом столбце таблицы Поста был хотя бы один минус.

Значит, наша система функций полна.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.07.2011, 09:39

Классы булевых функций
Ребят, не могу решить задачу: Является ли множество всех равновесных функций...

Минимизация булевых функций
Разложить по переменной x и представить в СДНФ и СКНФ следующие функции: ...

Минимизация Булевых функций
Нужно осуществить минимизацию Булевых функций несколькими методами: Метод...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru