Булевы функции (функции логики).

Основные теоремы алгебры логики.

Теоремы для одной переменной охватывают все операции над переменной x и константами "0" и "1":

1. 2. 3. 4.

5. 6. 7. 8.

9.

Теоремы для двух или более переменных – x и y:

10. Переместительный закон:

11. Сочетательный закон:

12. Распределительный закон:

Доказательство:

Здесь к скобке применена теорема 2.

13. Закон поглощения:

Доказательство:

14.

Доказательство:

15. Закон склеивания:

Доказательство:

16. Закон отрицания (теорема де-Морана)

Результат выполнения логических операций над двоичными переменными называется булевой функцией F. Она может принимать только два значения – "0" или "1". Задать булеву функцию – значит указать ее значение при всех возможных комбинациях переменных (аргументов). Если число переменных равно "n", то число возможных комбинаций равно . Когда значение функции известно для всех комбинаций, она называется полностью определенной. В противном случае – частично определенной.

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

Словесное описание функции должно однозначно определять все случаи, в которых выходные сигналы принимают значение "1" или "0". Например: Спроектировать устройство с тремя входами x₁, x₂, x₃, на выходе которого сигнал F = 1 в случае, если на любые два или на все три входа подан сигнал "1".

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