Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


Кратко охарактеризуем еще одну сферу применения теории булевых функций, выявленную уже во второй половине XX в. Это так называемая теория распознавания образов. На ее примере можно увидеть, как математика пытается своими методами смоделировать еще один вид мыслительной деятельности, свойственный человеческому мозгу, и что при этом снова оказываются задействованы методы математической логики.


Диагностика (распознавание) заболеваний


Начнем с анализа одной конкретной ситуации. Как известно, различные заболевания сопровождаются теми или иными симптомами. Эта связь устанавливается экспериментально на основе многолетних медицинских обследований тысяч больных. С помощью математики эти связи можно определенным образом систематизировать, используя аппарат булевых функций. Предположим, что имеется [math]m[/math] симптомов [math]S_1,S_2,\ldots,S_m[/math] и [math]n[/math] заболеваний [math]T_1,T_2,\ldots,T_n[/math]. Рассмотрим следующие булевы переменные [math](i=1,\ldots,m;~ j=1,\ldots,n):[/math]


[math]x_i = 1[/math], если у больного обнаружен i-й симптом,
[math]x_i = 0[/math], в противном случае;
[math]y_i = 1[/math], если у больного обнаружен j-е заболевание,
[math]y_i = 0[/math], в противном случае.

Тогда связь между симптомами заболеваний и заболеваниями может быть выражена на языке алгебры логики. Например, если заболевание [math]T_1[/math] всегда сопровождается симптомами [math]S_2[/math] и [math]S_3[/math], то булева функция [math]y_1\to (x_2\cdot x_3)[/math] тождественно равна 1. Аналогично, может быть известно, что если обнаружены симптомы [math]S_1,S_4,S_5[/math], то обязательно должно быть заболевание [math]T_2[/math], и, наоборот, это заболевание всегда проявляется в указанных симптомах. Следовательно, тождественно равна 1 булева функция следующего вида: [math]x_1\cdot x_2\cdot x_3\leftrightarrow y_2[/math]. Часто один какой-нибудь симптом (например, высокая температура) сопровождает многие заболевания, булева функция в этом случае


[math]x_1\to (y_1\lor y_2\lor y_3\lor y_4\lor y_5)=1.[/math]

Таким образом, экспериментально устанавливаются следующие булевы равенства:


[math]\begin{aligned}& f_1(x_1,x_2,\ldots,x_m,\, y_1,y_2,\ldots,y_n)=1\,;\\ & f_2(x_1,x_2,\ldots,x_m,\, y_1,y_2,\ldots,y_n)=1\,;\\ &\cdots \cdots \cdots \cdots \cdots \\ & f_k(x_1,x_2,\ldots,x_m,\, y_1,y_2,\ldots,y_n)=1\,. \end{aligned}[/math]

Булевы функции [math]f_1,f_2,\ldots,f_k[/math] называются указаниями. Каждая из них есть, по существу, некоторое составное высказывание относительно причинно-следственной связи между симптомами заболеваний и самими заболеваниями. Из этих равенств следует, что равна 1 и конъюнкция булевых функций [math]f_1,f_2,\ldots,f_k:[/math]


[math]f(x_1,x_2,\ldots,x_m,\, y_1,y_2,\ldots,y_n)= f_1 f_2\ldots f_k=1.[/math]

Это равенство представляет собой своего рода неявное задание функций (заболеваний) [math]y_1,y_2,\ldots,y_n[/math] от аргументов (симптомов) [math]x_1,x_2,\ldots,x_m[/math]. Задача диагностики состоит в том, чтобы явно выявить эти зависимости и применить их к конкретному больному. Для этого можно составить таблицу значений функции [math]f[/math]. Из общего числа строк [math]2^{m+n}[/math] нас будут интересовать в ней лишь те, в которых для всех симптомов, выявленных у исследуемого больного, соответствующее значение [math]x[/math] равно 1. Пусть у больного выявлены симптомы [math]S_1,\,S_2,\,S_3[/math], а общее число симптомов, задействованных в нашем анализе, пять: [math]S_1,\,S_2,\, S_3,\,S_4, \,S_5[/math]. Тогда число строк, представляющих интерес в данном случае, равно четырем. Предположим, что эти строки таковы (для простоты примем, что исследуются три заболевания: [math]T_1,\,T_2,\,T_3[/math] и им соответствуют три переменные: [math]y_1,\,y_2,\,y_3:[/math]


[math]\begin{array}{|c|c|c||c|c|c||c|}\hline x_1 & x_2 & x_3 & y_1 & y_2 & y_3 & f\\\hline 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 1& 0& 1& 1& 1\\ 1& 1& 1& 0& 1& 1& 1\\ 1& 1& 1& 0& 0& 1& 1\\\hline \end{array}[/math]

Анализ выделенных строк показывает, что во всех строках, соответствующих симптомам больного, есть заболевание [math]y_3[/math] (точнее, [math]T_3[/math]) и нет заболевания [math]y_1[/math] (точнее, [math]T_1[/math]), а заболевание [math]y_2[/math] (т.е. [math]T_2[/math]) в одних строках есть, а в других нет. Из этого можно сделать вывод, что у больного нет заболевания [math]T_1[/math], но он определенно страдает заболеванием [math]T_3[/math]. Относительно заболевания [math]T_2[/math] требуются дополнительные исследования. Для этого нужно увеличить число анализируемых симптомов, выявить дополнительные указания [math]f_i[/math]. На практике число столбцов и строк построенной таблицы может оказаться столь большим, что ее анализ будет под силу лишь компьютеру.




Распознавание образов


Нетрудно видеть, что в самых общих чертах ситуация, рассмотренная в предыдущем пункте, может быть охарактеризована следующим образом. Имеется некоторое множество скрытых причин (болезней) и множество наблюдаемых следствий (симптомов). Кроме того, имеются высказывания, связывающие причины и следствия. Требуется, опираясь на эти высказывания, по предъявляемому набору следствий (симптомов, наблюдаемых у данного пациента) определить возможные причины, их породившие (болезни пациента). Во второй половине XX в. сформировалась область прикладной математики, занимающаяся решением подобных проблем. Она получила название теория распознавания образов. В предыдущем пункте показано, как распознавать "образ болезни", но подобная ситуация встречается весьма часто и в других областях науки. В геологии, например, причины труднодоступны, так как это — залегающие на разных глубинах полезные ископаемые. Но следствия сравнительно легко наблюдаемы: это — сопутствующие минералы, выходящие на поверхность, окраска почвы, характер растительности, данные сейсморазведки, аэро- и космической фотосъемки и т.п. В химии скрытые причины — это качественный состав и строение вещества, а наблюдаемые следствия — ответы в тестовых реакциях: помутнение, окраска, запах, выделение теплоты ит.п. В биологии: малодоступные гены контролируют легко наблюдаемые признаки. В криминалистике: скрывшийся преступник оставляет следы, улики, показания свидетелей.


В разных науках такое "распознавание образов" называется по-разному; для рассмотренных это — диагностика, геологическая разведка, анализ, раскрытие преступления и т.д. С точки зрения математики здесь решается одна задача, сформулированная как "распознавание образов". Решать ее в самой общей постановке и призвана математическая теория распознавания образов. Один из методов ее решения опирается на теорию булевых функций, которая позволяет в определенном смысле автоматизировать процесс решения, используя для этой цели ЭВМ.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved