Булева алгебра и составление условий

Одной из сфер применения булевой алгебры может быть составление условий для ветвлений в алгоритмах программ. Благоразумно прибегать к ней, когда необходимо составить довольно сложное условие, содержащее множество простых условий.
Покажу на примере. Предположим, нам надо построить ветвление исходя из того, является ли B больше, чем A, но меньше, чем C. Т.е.: A<B<C. Рассуждая аналитически, мы прийдём к выводу, что B одновременно должно быть и больше A, и меньше C. Таким образом получаем 2 условия: B>A, B<C. При этом на их "одновременность" должна указывать связка И. Получаем: (B>A) И (B<C).
Тот же самый пример можно решить и с помощью булевой алгебры. Для этого составим булеву функцию.
Во-первых, обозначим простые условия через булевы переменные: X=B>A, Y=B<C. При этом они будут принимать значение 1, если условие верно, и 0, если нет.
Во-вторых, Теперь составим таблицу истинности. Для этого поступим следующим образом. Выпишем все входные наборы будущей функции:

X 0 0 1 1
Y 0 1 0 1

Затем, чтобы получить выходной набор функции, будем проверять простые условия, соответствующие переменным (в смысле, их истинность). Начнём с набора XY=(00). Т.к. X "отвечает" за истинность условия B>A, а Y - за B<C, то получим: B не больше A и B не больше C => наше условие не сходится => результат сложного условия - ложь (т.е. 0 для булевой алгебры). Таким же способом проверяем все наборы. И только в последнем XY=(11) получим: B>A и B>C => условие сходится => результат = 1. Таким образом получаем таблицу истинности:

X 0 0 1 1
Y 0 1 0 1

F(X,Y) 0 0 0 1

Теперь по таблице истинности можно найти совершенную дизъюнктивную форму. Она равна: F = X ^ Y. В принципе, для "укорачивания" результирующей формы функции желательно найти её минимальную д.н.ф. В нашем случае полученная с.д.н.ф. является одновременно и м.д.н.ф.
Следующим шагом будет преобразование м.д.н.ф. (или с.д.н.ф.) в форму условия. Для этого просто заменим введённые нами переменные начальными простыми условиями (при этом дизъюнкция заменяется логическим ИЛИ, конъюкция - логическим И, а отрицание - логичексим НЕ; все они почти всегда присутствуют во всех алгоритмических языках). В нашем случае: условие = F = X ^ Y = (B>A) И (B<C). К нему же мы и приходили после аналитических размышлений.
Такое решение может показаться громозжким. Но это потому, что "сложное" условие достаточно простое. И поэтому такой метод нахождения полезно применять при необходимости составления более сложных условий. Он "проще", чем аналитический анализ, т.к. является алгоритмом решения.
/Sonic, 13.06.01

	(С) Racckaz.narod.ru
	Desing by Nokkk