Diskretnaya_matematika_1_semestr

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

Пусть Е2={0, 1}(самый простой вариант Еk). Булевой функцией f от n-переменных наз. отображение вида f: E2:nE2 или f=f(x1, x2, …xn). Всевозможные упорядоченые последовательности из 0 и 1 наз. набором.

Любую булевую ф-цию от n-переменных можно задать таблицей из 2^n строк и (n+1) столбца. Каждая строка является набором с 0 и 1 и имеет длину (n+1).

Область определения булевой функции конечна, поэтому её удобно записывать в виде таблицы. Такие таблицы называются таблицами истинности. Таблица имеет (n+1) столбец и 2^n строк.

Каждый набор x1, x2, …xn можно рассматривать как некоторое двоичное число. Будем предполагать, что наборы x1, …xn упорядочены в таблице по возрастанию (как двоичные числа). Каждый последующий набор получается из предыдущего прибавлением двоич. единицы (00…1). Последний столбец табл. истиности обозначается f=(f(0,0,…,0,0),…,f(1,1,…,1,)).

Так как длина каждого такого столбца 2^nа различных столбцов из 0 и 1 длины 2^n имеется 2^2^n тогда справедлива теорема.

Теорема. Числа булевых ф-ций от n-переменных=2^2^n

Ф-ции 2n и 22^n быстро растут с ростом n и поэтому распознование св-в бул. ф-ций полным перебором строк таблицы истиности и полным перебором бул. ф-ций от n переменных на практике возможно только для небольших n. Перебор строк – для n40. Перебор бул. ф-ций – для n6.

Переменную xi наз. существественной для булевой ф-ции f(x1, x2, …xn), если существуют 2 набора =(1,...,i,…,n) и набор =(1,2,…,i,…,n), которые отличаются только по i-той координате, такие, что f(i)f(i), все остальные координаты равны. В противном случае переменная хі назыв. Несущественной или фиктивной.

Два набора, отличающие по некоторой координате, назыв. соседними по этой координате.

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

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

Среди бул. ф-ций выделяются элементарные бул. ф-ции: 1)константы: 1, 0; 2)ф-ции от одной пересенной: -тождественная ф-ция: х; -отрицание:х; 4) ф-ции от двух переменных:











-логическое следование; |-ф-ция Шеффера;  Сложение по модулю 2

Содержание