4.2 Функции алгебры логики

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

            Определение 1. Функцией алгебры логики f(x₁,x₂,…,x_n) от n переменных x₁,x₂,…,x_n (или функцией Буля) называется функция n переменных, принимающая значения 0, 1, аргументы которой также принимают значения 0 и 1.

            Функция f(x₁,x₂,…,x_n) задается своей истинностной таблицей (табл. 1.3)

Таблица 1.3

            Из этой таблицы видно, что число различных двоичных наборов длины n x₁,x₂,…,x_n конечно и равно 2ⁿ.

            Ясно, что тавтологии и тождественно ложные функции алгебры логики представляют собой постоянные функции, а две равносильные формулы выражают одну и ту же функцию. Каждая функция определяется таблицей истинности, состоящей из  строк, т.е. принимает  значений. Общее число наборов из 0 и 1 длины  равно . Это число равно числу различных функций алгебры логики n переменных.

            Функция алгебры логики f(x₁,…,x_i-1,x_i,x_i+1,…,x_n) зависит существенным образом от аргумента x_i, если существуют такие значения  a₁,…,a_i-1,a_i,a_i+1,… a_n переменных x₁,…,x_i-1,x_i,x_i+1,…,x_n, что f(a₁,…,a_i-1,0,a_i+1,… a_n) ¹ f(a₁,…,a_i-1,1,a_i+1,… a_n). В этом случае переменная x_i называется существенной, в противном случае – несущественной, или фиктивной. Очевидно, что постоянные функции не имеют существенных переменных.

            Пример 1. f(x) – функция одной переменной. Ее возможные значения приведены в таблице (табл. 1.4).

Таблица 1.4

            f₁(x) =1 (постоянная, не зависит от x, x – фиктивная переменная),

            f₄(x) =0 (постоянная, не зависит от x, x – фиктивная переменная),

            f₂(x) =x, f₃(x) =, в f₂ и f₃ x – существенная переменная.

            Пример 2. Если n=2, то =16. Именно столько существует различных функций двух переменных. Перечислим их в таблице истинности (табл. 1.5).

Таблица 1.5

Выразим теперь все эти функции через значения аргументов x и y: f₁≡1,  f₂≡x Ú y,  f₃≡x,  f₄≡x Ù y,  f₅≡,  f₆≡,  f₇≡,  f₈≡,  f₉≡,  f₁₀≡,  f₁₁≡,  f₁₂≡y,  f₁₃≡,  f₁₄≡,  f₁₅≡,  f₁₆≡0.

            Каждой формуле алгебры логики соответствует своя функция. Если формулы А и В равносильны, то соответствующие им функции равны: f_A(x₁,x₂,…,x_n)=f_B(x₁,x₂,…,x_n). Это значит, что при всех значениях переменных x₁,x₂,…,x_n  значения f_A  и  f_B совпадают.

Create by Barshay Natalia © 2005-2007