Понятие функции алгебры логики (ФАЛ). Задание ФАЛ таблицей и формулами. Разложение ФАЛ по переменным. Совершенная дизъюнктивная нормальная форма (СДНФ) функции

Понятие функции алгебры логики (ФАЛ). Задание ФАЛ таблицей и формулами. Разложение ФАЛ по переменным. Совершенная дизъюнктивная нормальная форма (СДНФ) функции.

Функцией алгебры логики называется функция, у которой значения всех аргументов, так же как и значение самой функции, принадлежат множеству Е₂ ={0,1}, т.е. множеству из двух символов -0 и 1.

Другими словами, n -местная функция алгебры логики- это функция, реализующая отображение f: E₂ⁿ à Е₂.

Отождествляя в дальнейшем булеву функцию с отображением, которое она реализует, множество всех булевых функций произвольного числа переменных будем обозначать Р₂, множество всех булевых функций n переменных будем обозначать Р₂(n).

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

Табл.2.3
x1	x2	…	xn-1	xn	f(x1,x2,..,xn-1,xn)
					f( 0,0,..,0,0 )
					f( 0,0,..,0,1 )
					f( 0,0,..,1,0 )
					f( 0,0,..,1,1 )
…	…	…	…	…	…
					f( 1,0,..,0,0 )
					f( 1,0,..,0,1 )
…	…	…	…	…	…
					f( 1,1,..,1,1 )

Теорема. Число функций алгебры логики от n переменных x₁,x₂,..,x_n-1,x_n равно .

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

1-й способ.

Каждая функция алгебры логики может быть задана табл. вида 2.3. Число строк в таблице равно 2ⁿ=|E₂ⁿ|=|E₂|ⁿ.

Двоичные наборы в левой части таблицы располагаются в стандартном порядке, который соответствует представлению в двоичной системе счисления десятичных чисел 0,1,2,..,2 ⁿ -1. Две разные функции от n -переменных x₁,x₂,..,x_n-1,x_n могут различаться лишь столбцами значений. Таким образом, функций от n- переменных столько, сколько различных столбцов их значений, т.е. двоичных наборов длины l=2ⁿ. Число таких наборов равно .

2-й способ.

Каждая функция алгебры логики от переменных x₁,x₂,..,x_n-1,x_n однозначно определяется своей «областью истинности», т.е. подмножеством области определения, на котором эта функция принимает значение 1. Поэтому функций столько, сколько всех подмножеств в множестве E₂ⁿ. В множестве E₂ⁿ содержится l =2 ⁿ =| E₂ⁿ | элементов(теорема о числе всех подмножеств конечного множества), отсюда следует, что число всех подмножеств равно 2 ^l = . Что и требовалось доказать.

Суперпозицией функций называется подстановка в функцию вместо её переменных других функций. Подстановка может осуществляться вместо всех переменных или вместо некоторых.

Пусть W – некоторое множество функций из P₂ , W Í P₂.

Следующее определение формулы над W является индуктивным определением, т.к. задает процесс получения объектов (формул) из некоторого множества простейших таких объектов (выражений,обозначающих функции из W).