Некоторые теоремы алгебры логики

 

Тесная связь между теорией вероятностей событий и математической логикой замечена уже давно. В настоящее время математическая логика и теория вероятностей объединяются на основе логико-вероятностного исчисления.

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

Основной трудностью в практическом применении логико-вероятностных методов исследования надежности и безопасности структурно-сложных систем является преобразование произвольных ФАЛ в формы перехода к полному замещению (ФППЗ). Чтобы сделать это преобразование направленным (стандартным) и математически строгим, необходимо было построить своеобразный “мостик” между алгеброй логики и теорией вероятностей. История становления ЛВМ и вклад отдельных ученых в их создание и развитие описаны в работе [119]. Опуская строгие доказательства специальных теорем, свойств и алгоритмов, которые составляют математическую основу ЛВМ, сформулируем здесь только их суть для последующего практического применения.

Теорема 1. Любую ФАЛ, зависящую от n аргументов (n³ 1), можно представить в следующем виде:

(2.38)

Выражение (2.38) известное под названием формулы разложения Шеннона, которая оказывается справедливой и для алгебры по модулю 2. Применив правило 36 к правой части выражения(2.38), получим:

(2.39)

Свойство 1. Булеву разность любой ФАЛ по аргументу x_i можно представить в следующем виде:

(2.40)

Для доказательства эквивалентности выражений (2.30) и (2.40) используем формулу разложения (2.39) и правила 28-38. В соответствии с (2.30) и (2.31) имеем:

.

Свойство 2. Булеву разность любой ФАЛ по аргументу x_i можно представить в базисе конъюнкция, дизъюнкция, отрицание в следующем виде:

. (2.41)

Данное свойство следует из выражения (2.40) и правила 38.

Теорема 2. Любую ФАЛ, зависящую от n аргументов (n³ 1), можно представить в следующем виде:

. (2.42)

Эта теорема называется теоремой разложения произвольной ФАЛ по любому числу аргументов . Будет справедливо выражение (2.42) называть также формулой разложения Д.А. Поспелова, доказавшего теорему 2 в 1964г.[83].

При разложении ФАЛ по всем n аргументам получим СДНФ исходной функции, которую можно записать в виде:

, (2.43)

где символ означает, что дизъюнкция берется только по таким наборам , на которых выполняется равенство

. (2.44)

Теорема 3. Для всех монотонных ФАЛ множество наборов, на которых нулевая функция по аргументу x_i принимает значение, равное единице, есть подмножество наборов, на которых единичная функция по тому же аргументу x_i равна единице, т.е.

. (2.45)

Доказательство этой теоремы приведено в работе [103].

Из теоремы 3 следует пять следствий, знание которых существенно облегчает логические преобразования для монотонных ФАЛ.

1)

; (2.46)

2) ; (2.47)

3) ; (2.48)

4) ; (2.49)

5) . (2.50)

Теорема 4. Частная производная от вероятности истинности монотонной ФАЛ по вероятности истинности аргумента x_i численно равна вероятности истинности булевой разности этой функции по аргументу x_i:

. (2.51)

Доказательство этой теоремы произведено в работе [103].

Теорема 5. Вероятность истинности произвольной ФАЛ, представленной в ОДНФ, равна сумме вероятностей истинности всех ортогональных членов этой ФАЛ:

, (2.52)

где ð _i не только элементарные ортогональные конъюнкции ОДНФ, но и любые ФАЛ, попарно ортогональные.

Доказательство этой теоремы приведено в работе [105].

Теорема 6. Дизъюнкция ортогональных бесповторных форм в базисе конъюнкция-отрицание является формой перехода к полному замещению (ФППЗ).

Справедливость этой теоремы следует из теоремы 5 и того, что каждое слагаемое в исходной дизъюнктивной форме является ФППЗ.

В настоящее время известно несколько форм перехода к полному замещению: СДНФ, ОДНФ, бесповторные ФАЛ в базисе конъюнкция-отрицание.

Если ФАЛ представлена в ФППЗ, то переход к вероятностной функции осуществляется по следующим правилам:

1) каждая буква в ФППЗ заменяется вероятностью ее равенства единице, причем (в надежности)

; (2.53)

2) отрицание функции заменятся разностью между единицей и

вероятностью равенства этой функции единице, например:

 

; (2.54)

3) Операции логического умножения и сложения заменяются

Операциями арифметического умножения и сложения.

ВФ для ФАЛ, представленной в произвольной бесповторной форме, можно найти по ее выражению в базисе конъюнкция-отрицание, которое получается путем многократного применения правил де Моргана (2.10).

Пусть, например

,

и требуется найти . Так как эта функция является бесповторной (хотя и не ДНФ)

; (2.55)

. (2.56)

В заключении, еще раз повторим, что здесь приведены именно основы логико-вероятностного исчисления, а конкретные логико-вероятностные методы будут изложены ниже.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: