2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Исследование булевых функций
Сообщение25.01.2010, 21:27 


25/01/10
1
Здравствуйте!
Пишу диплом, суть которого: исследовать множество подмножеств некоторого конечного множества $ \{A,B,C,...\}$. На элементы подмножеств накладывается набор ограничений трех типов (буквы в формулах соответствуют булевым переменным, 1 - входит в подмножество, 0 - в обратном случае):
  1. Исключение: только один из элементов, подпадающий под ограничение, может принадлежать подмножеству
    $ \lnot(a \land  b)\land \lnot(b \land c)\land \lnot(a \land c)$
  2. Причина - следствие: элементы из следствия могут принадлежать подмножеству тогда и только тогда, когда ему принадлежат все элементы предпосылки.
    $(a \land b \land c)\lor\lnot( x \lor y)$
  3. "Хотя бы одно из": Хотя бы один из элементов этого ограничения должен присутствовать в подмножестве.
    $a\lor b \lor c$

Допустимые подмножества должны удовлетворять функциям всего набора ограничений (или соответствующей конъюнкции всех функций).

Цель работы исследовать особые случаи:
  • Вырожденный случай. Единственное допустимое подмножество - пустое
  • Логическое противоречие. Допустимых подмножеств нет
  • Неиспользуемый элемент. Не существует допустимого подмножества, содержащего в себе конкретный элемент исходного множества.

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

Возможно, существуют какие-нибудь работы/исследования на подобную тему, котрые можно положить в основу моего диплома. Если есть такие, подскажите пожалуйста :D Также внимательно выслушаю любую критику

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group