2014 dxdy logo

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

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




 
 Исследование булевых функций
Сообщение25.01.2010, 21:27 
Здравствуйте!
Пишу диплом, суть которого: исследовать множество подмножеств некоторого конечного множества $ \{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