Переключательные функции

Создателем алгебры логики (АЛ) является английский математик Джордж Буль (1815-1864). Первое применение алгебра логики нашла в начале XX века при анализе контактных цепей. Возможность описания переключательных схем с помощью логичных формул оказалась весьма ценной, так как:

1) с помощью формул легко проверить работу схемы;

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

Также аппарат АЛ применяется при анализе и синтезе логических схем ЭВМ; используется для формального описания цифровых автоматов; в теории кодировании и защиты информации и т. д.

Логической (булевой) переменной называется такая величина х, которая может принимать только значения 0 и 1.

Несколько логических переменных образуют набор переменных.

Функция , определённая на наборе двоичных переменных и принимающая в качестве возможных значений 0 и 1, называется логической (булевой) функцией, или функцией алгебры логики (ФАЛ), или переключательной функцией (ПФ). Область определения и значений ФАЛ: {0,1}.

Перечислим способы задания ФАЛ:

1) аналитический (при помощи формулы);

2) табличный (при помощи таблицы истинности);

3) числовой (перечислением десятичных номеров наборов, на которых функция принимает значение 0 или 1).

 

Фиктивные и существенные переменные.

Переменная x_i называется фиктивной (несущественной) переменной функции f(x₁,…,x_n), если

f(x₁,…,x_i-1,0,x_i+1,…,x_n) = f(x₁,…,x_i-1,1,x_i+1,…,x_n)

для любых значений x₁,…,x_i-1,x_i+1,…,x_n. Иначе переменная x_i называется существенной.

Если две функции алгебры логики f₁(x₁, x₂,..., x_n) и f₂(x₁, x₂,..., x_n) принимают на всех возможных наборах одинаковые значения, то они называются равными (эквивалентными).

Булеву функцию, определенную на всех своих наборах переменных, называют полностью определенной. Булеву функцию n переменных называют неполностью определенной или частичной, если она определена не на всех двоичных наборах длины n.

Элементарные ФАЛ

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

Х	Функции
f1	f2	f3	F4

Функция f1: – функция константы нуля.

Функция f2: – функция отрицания значений аргумента.

Функция f3: – функция повторений значений аргумента.

Функция f4: – функция константы единицы.

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

Аргумен- ты

Функции fi

х1

х2

Функция f1: – функция константы нуля.

Функция f2: – стрелка Пирса, функция Вебба, отрицание дизъюнкции (логического сложения) х₁ и х₂.

Функция f3: – отрицание импликации из х₂ в х₁.

Функция f4: – отрицание значений первого аргумента х₁.

Функция f5: – отрицание импликации из х₁ в х₂.

Функция f6: - отрицание значений второго аргумента х₂.

Функция f7: – сумма по модулю два, отрицание эквивалентности, неравнозначность.

Функция f8: – штрих Шеффера, отрицание конъюнкции (логического умножения) х₁ и х₂.

Функция f9: – конъюнкция х₁ и х₂, логическое умножение, операция «и».

Функция f10: – эквивалентность, равнозначность.

Функция f11: – функция повторений аргумента х₂.

Функция f12: – импликация из х₁ в х₂.

Функция f13: - функция повторений значений х₁.

Функция f14: – импликация из х₂ в х₁.

Функция 15: – дизъюнкция х₁ и х₂, логическое сложение, операция «или».

Функция f16: – функция константы единицы.

Свойства элементарных ФАЛ

1. Свойства конъюнкции, дизъюнкции и отрицания.

1.1. Снятие двойного отрицания: .

1.2. , .

1.3. .

1.4. .

1.5. .

1.6. .

1.7. .

1.8. .

Дизъюнкция и конъюнкция обладают рядом свойств, аналогичным арифметическим сложению и умножению.

1.9. Закон ассоциативности:

.

1.10. Закон коммутативности:

.

1.11. Закон дистрибутивности:

.

1.12. Законы де Моргана:

.

Из законов де Моргана вытекает:

.

Законы де Моргана распространяются на более чем одну переменную.

1.13. Законы поглощения:

.

1.14. Формулы склеивания:

.

2. Свойства функции неравнозначности.

2.1. .

2.2. Закон коммутативности: .

2.3. Закон ассоциативности:

.

2.4. Закон дистрибутивности: .

2.5.

2.6.

3. Свойства функции импликации.

3.1 .

3.1. , , , , , .

3.2. Закон коммутативности: .

3.3. Закон ассоциативности не выполняется.

3.4. , , .

4. Свойства штриха Шеффера.

4.1. .

4.2. , , , , , .

4.3. Закон коммутативности справедлив не более чем для двух переменных:

.

4.4. Дистрибутивность не выполняется.

4.5. Ассоциативность не выполняется.

4.6. , .

5. Свойства функции стрелки Пирса (функции Вебба).

5.1. .

5.2. , , , .

5.3. Законы ассоциативности и дистрибутивности не выполняются. Выполняются только законы коммутативности:

.

5.4. , .