Лекция 1-2. Функции алгебры логики презентация

— основное множество (исходный алфавит значений переменных), тогда

= {(α1, …, αn) | ∀ i ,αi∈ E2}.

Тогда всюду определённой булевой функцией назовём отображение f (x1, …, xn): → E2.

простых функций.
Например, для n = 1:

порядке (по возрастанию двоичных чисел).

из r букв можно построить ровно rm различных слов длины m.

Пусть утверждение леммы верно для m–1, то есть существует ровно rm – 1 различных слов длины
m–1. Для каждого такого слова длины m–1 существует ровно r возможностей добавить одну букву в конец. Так как всего слов длины m–1 существует rm – 1, то различных слов длины m получится r · rm – 1 = rm. ♦

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

(x1, …, xn), если существуют такие α1,…,αi–1,αi+1,…,αn∈E2, что f (α1, …,αi – 1, 0, αi + 1,…, αn) ≠ f (α1, …, αi – 1, 1, αi + 1, …, αn).

Такие наборы, отличающиеся лишь одной переменной xi, называются соседними по xi. В противном случае переменная xi называется фиктивной.

Если xi — фиктивная переменная функции f, то функция f однозначно определяется некоторой функцией g (x1, …, xi – 1, xi + 1, …, xn).
Таблицу любой функции можно расширить введением любого числа фиктивных переменных.

них можно получить из другой путём добавления и изъятия любого числа фиктивных переменных.

Определение 4.
Пусть имеется некоторое множество функций
A = {f1 (…), f2 (…), …, fn (…), …}.
Введем понятие формулы над A:
1) Любая функция из A называется формулой над A.
2) Если f (x1, …, xn) ∈ A и для любого i Hi — либо переменная, либо формула над A, то выражение вида f (H1, H2, …, Hn) является также формулой над A.
3) Только те объекты называются формулами над A, которые можно построить с помощью пунктов 1 и 2 данного определения.