39. Булевы функции, способы их задания. Представления булевых функций формулами.

Функцией алгебры логики (ФАЛ) от n переменных x₁,…,x_n называется любая функция f:{0,1}ⁿ→{0,1}, т.е. функция, которая произвольному набору {δ₁,…,δ_n} нулей и единиц ставит в соответствие значение f(δ₁,…,δ_n) из {0,1}.

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

Булевой функцией описывается преобразование некоторым устройством входных сигналов в выходные.

Булева функция f(x₁,…,x_n) полностью задается своей таблицей истинности. В каждой строке таблицы задается сначала набор значений переменных (δ₁,…,δ_n), а затем значение функции на этом наборе.

Если булева функция f и формула φ имеют одну и ту же таблицу истинности, то говорят, что формула φ представляет функцию f.

Булева функция также однозначно задается перечислением всех наборов, на которых она принимает значение 0, либо наборов, на которых она принимает значение 1.

Вектором значений булевой функции f(x₁,…,x_n) называется упорядоченный набор всех значений функции f, при котором значений упорядочены по лексикографическому порядку множества аргументов {0,1}ⁿ.

Отметим, что поскольку всего имеется 2ⁿ наборов нулей единиц, то существует ровно булевых функций от n переменных.

Наборы 0 и 1 можно представить в виде вершин n-мерных кубов или в виде вершин 2-дерева.

Функция f называется суперпозицией функций g(y₁,..,y_n) и h₁(x₁,…,x_n),…,h_m(x₁,…,x_n), если f(x₁,…,x_n)=g(h₁(x₁,…,x_n),…,h_m(x₁,…,x_n)).

Булева функция, принимающая значения 1 (соответственно 0) на всех наборах нулей и единиц, называется константой 1 (константой 0).

Опишем булеву алгебру β_n функцией алгебры логики от n переменных. В качестве носителя рассмотрим множество . Отношение ≤ на множестве B_n определим по следующему правилу: для любого набора значений X=(δ₁,…,δ_n). Пересечением называется такая функция h , что h(X)=min{f(X),g(X)} на любом наборе X=(δ₁,…,δ_n). Объединением называется такая функция h, чтоh=max{f(X),g(X)} на любом наборе X. Дополнение функции f определяется следующим образом: . В качестве 0 рассмотрим функцию, являющуюся константой 0, а в качестве 1 возьмем константу 1. Система образует булеву алгебру функций от n переменных (алгебру булевых функций).

40. Эквивалентность формул.

Формулы φ(x₁,…,x_n) и ψ(x₁,…,x_n) называются эквивалентными (φ≈ψ), если совпадают их таблицы истинности, т.е. совпадают представляемые этими формулами функции.

Основные эквивалентности:

1. ассоциативность

2. Коммутативность:

3. Идемпотентность:

4. Дистрибутивность: ,

5. Поглощение:

6. Законы де Моргана:

7. Двойное отрицание:

8. 

9. 

10. 

11. 

Формула φ(x₁,…,x_n) называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула принимает значения 1 (соответственно 0).

Формула φ(x₁,…,x_n) называется тождественно истинной, или тавтологией (тождественно ложной, или противоречием), если эта формула принимает значение 1 (соответственно 0) при всех наборах значений переменных, т.е. функция f_φ является константой 1 (константой 0).

Утверждения:

1. Формула φ тождественно ложна тогда и только тогда, когда ךφ тождественно истинна.

2. Формула φ опровержима тогда и только тогда, когда она не является тождественно истинной

3. Формула φ выполнима тогда и только тогда, когда она не является тождественно ложной.

Тождественно истинные (тождественно ложные) формулы образуют класс эквивалентности по отношению ≈.

Утверждение: Если формула φ₁ тождественно истинна, φ₀ – тождественно ложна, то справедливы следующие эквивалентности:

1) , 2) , 3) , 4) , 5) , 6) , 7) ,8) , 9) .