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

1. Глава 3 Функции алгебры логики

Определение 1.
Пусть E2 = {0, 1} — основное множество
(исходный алфавит значений переменных),
тогда
Е
n
2
= {(α1, …, αn) | ∀ i ,αi∈ E2}.
Тогда всюду определённой булевойn функцией
назовём отображение f (x1, …, xn): Е2 → E2.

2.

Такую функцию можно задать таблично, а
можно как суперпозицию других, более
простых функций.
Например, для n = 1:

3.

Для n = 2:
При заполнении таблицы столбцы переменных
заполняются в лексикографическом порядке
(по возрастанию двоичных чисел).

4.

Лемма (о числе слов).
В алфавите A = {a1, …, ar} из r букв можно
построить ровно rm различных слов длины m.

5.

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

6.

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

7.

Определение 2.
Переменная xi называется существенной переменной
функции алгебры логики f (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).
Таблицу любой функции можно расширить введением любого
числа фиктивных переменных.

8.

Определение 3.
Две функции алгебры логики называются равными, если
одну из них можно получить из другой путём
добавления и изъятия любого числа фиктивных
переменных.
Определение 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
данного определения.