Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

1) Для доказательства законов можно использовать: а) Метод совершенной индукции. б) Использование одних законов для доказательства других законов.
Метод совершенной индукции состоит в доказательстве эквивалентности левой и правой части на всем множестве наборов аргументов. Для этого составляется таблица истинности.
2) Большинство законов задается парой соотношений, при этом одно соотношение можно получить из другого заменив операции конъюнкции на дизъюнкцию или дизъюнкцию на конъюнкцию (метод не применим в законах, в которых участвуют константы). С константами же константы заменяются на противоположные значения. (Дуальность законов Булевой алгебры)
3) Некоторые законы можно распространять на произвольное число элементов.
4) В любом законе можно заменить любую букву на произвольное логическое выражение.
5) Законы применяются для упрощения Булевых функций.

Разнообразие Булевых функций.

1. Булева функция от одной переменной.
|Обозначение |Значения аргумента и функции |Наименование |
|аргумента и | |функции |
|функции | | |
|x |0 |1 | |
|[pic] |0 |0 |Логический ноль |
|[pic] |0 |1 |Повторение x |
|[pic] |1 |0 |Инверсия x |
|[pic] |1 |1 |Логическая единица|

2. Возможные функции от двух переменных.

|Обозначение |Значение аргументов и|Обозначение |Наименование |Вырожденность|Представление|
|аргументов и |функций |функций | | |функции в |
|функций | | | | |булевом |
| | | | | |базисе |
|[pic] |0 |0 |0 |0 |“0” |Логический ноль |+ |- |
|[pic] |0 |0 |0 |1 |x1&x2 |Конъюнкция |- |x1 x2 |
|[pic] |0 |0 |1 |0 |x1(x2 |Запрет x1 по x2 |- |x1 [pic]2 |
|[pic] |0 |0 |1 |1 |x1 |Повторение x1 |+ |- |
|[pic] |0 |1 |0 |0 |x2(x1 |Запрет x2 по x1 |- |x2[pic]1 |
|[pic] |0 |1 |0 |1 |x2 |Повторение x2 |+ |- |
|[pic] |0 |1 |1 |0 |x1(x2 |Сумма по модулю 2 неравнозначная |- |[pic]1 x2 ( |
| | | | | | |(исключительное или) XOR | |x1[pic]2 |
|[pic] |0 |1 |1 |1 |x1(x2 |Дизъюнкция |- |x1 ( x2 |
|[pic] |1 |0 |0 |0 |x1(x2 |Функция Вебба |- |x1(x2 |
|[pic] |1 |0 |0 |1 |x1(x2 |Равнозначность |- |[pic]1[pic]2 |
| | | | | | | | |( x1 x2 |
|[pic] |1 |0 |1 |0 |[pic]2 |Отрицание x2 |+ |- |
|[pic] |1 |0 |1 |1 |x2(x1 |Импликация от x2 к x1 |- |[pic]2 ( x1 |
|[pic] |1 |1 |0 |0 |[pic]1 |Отрицание x1 |+ |- |
|[pic] |1 |1 |0 |1 |x1(x2 |Импликация x1 к x2 |- |[pic]1 ( x2 |
|[pic] |1 |1 |1 |0 |x1 | x2 |Штрих Шеффера |- |[pic] |
|[pic] |1 |1 |1 |1 |“1” |Логическая единица |+ |- |
Определение: Булева функция от n аргументов fn(x) называется вырожденной по аргументу xi, если ее значение не зависит от этого аргумента, то есть для всех наборов аргументов имеет место равенство:

f(x1, x2, ... , xi-1, 0, xi+1, ... , xn) = f(x1, x2, xi-1, 1, xi+1,
... , xn).

Функция запрета x1(x2 принимает значение, равное нулю при равенстве запрещающей переменной (x2) единице и повторяет значение аргумента x1 при равенстве запрещающей переменной нулю.

Понятие импликации в Булевой алгебре отождествляется с выражением следования (если ... то ... ).
Пример: Имеют место два простых высказывания.

А. На небе тучи.

В. Идет дождь. В(А

|А |В |В(А |
|f |f |t |
|f |t |f |
|t |f |t |
|t |t |t |

Из истины не может следовать ложь!

Некоторые функции от трех переменных.

|Значение аргументов|Значение функций |
| |Сумма по модулю |Исключающее |Функция |
| |2 |ИЛИ |мажоритарности |
|x1 |x2 |x3 |x1(x2(x3 |XOR (x1,x2,x3)|x1#x2#x3 |
|0 |0 |0 |0 |0 |0 |
|0 |0 |1 |1 |1 |0 |
|0 |1 |0 |1 |1 |0 |
|0 |1 |1 |0 |0 |1 |
|1 |0 |0 |1 |1 |0 |
|1 |0 |1 |0 |0 |1 |
|1 |1 |0 |0 |0 |1 |
|1 |1 |1 |1 |0 |1 |

Функция - сумма по модулю 2 и исключающее ИЛИ являются эквивалентными только для двух аргументов.

n
Общее разнообразие функций от n аргументов равно 22

В самом компактном виде любую Булеву функцию можно представить символически: [pic], где n-количество аргументов, а N-десятичный эквивалент двоичного набора значений функции на упорядоченном множестве аргументов.
Пример: f3(x)=x1(x2(x3=[pic]

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

Нормальные формы Булевых функций

Нормальные формы - это особый класс аналитических выражений, используемых при решении задачи минимизации Булевых функций и для перехода от табличной формы задания к аналитической. Нормальные формы строятся на основании операций конъюнкции, дизъюнкции и отрицания, причем отрицание только единственной переменной.

Определение: Элементарной конъюнкцией (дизъюнкцией) называется конъюнкция (дизъюнкция) конечного числа попарно различимых переменных или их отрицаний.

Элементарную конъюнкцию (дизъюнкцию) принято называть конъюнктивным
(дизъюнктивным) термом.

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

Примеры конъюнктивных термов:

_ _ x1, x2, x1x3, x2x4x5 (терм)
___ _ x1x2, x1x2x3 (не терм)

Рекомендуем скачать другие рефераты по теме: реферат на тему менеджмент, класс.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата