Глава 2. Элементы теории переключательных функций.

Одной из важнейших интерпретаций булевых алгебр является БУЛЕВА АЛГЕБРА ПЕРЕКЛЮЧАТЕЛЬНЫХ ФУНКЦИЙ. Первоначально этот математический аппарат был применен для анализа и синтеза множества релейно-контактных схем с операциями последовательного (конъюнкция) и параллельного (дизъюнкция) соединения контактов и операцией дополнения (реле c нормально-замкнутым контактом). 1 - проводник, 0 – разрыв.

Переключательными (логическими) функциями называют функции, область значений которых есть подмножество двухэлементного множества {0,1}, а область определения – {0,1}n , где n – число переменных. Очень часто значение «0» обозначают как «Л» – «ложь», а значение «1» – как «И» – «истина». Каждая комбинация значений переменных называется набором (набором переменных). Множество наборов переменных образует область определения логической функции. Число всех возможных различающихся наборов значений n переменных переключательной функции f(x1, x2, x3, …, xn) равно 2n (равно числу всех возможных двоичных векторов длины n). Иногда множество наборов переменных интерпретируют как вершины n-мерного куба. Наборы и соответствующие им значения функции составляют таблицу истинности функции, в левой части которой выписаны все возможные наборы значений аргументов функции, а в правой части соответствующие этим наборам значения функций. Количество различных переключательных функций n аргументов (2 ) 2 n (равно числу возможных расстановок нулей и единиц в столбце с 2n строками).

2.1. Переключательные функции одного аргумента.

Существует четыре переключательные функции одного аргумента, которые приведены в табл. 1.

Таблица 1:

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

Функция f0(x) тождественно равна нулю. Она называется константой нуль и обозначается f0(x)=0.

Функция f1(x) повторяет значения аргумента и поэтому тождественно равна переменной x.

Функция f2(x) принимает значения, противоположные значениям аргумента: если x=0, то f2(x)=1; если x=1, то f2(x)=0. Эту функцию называют инверсией x или отрицанием x и вводят для нее специальное обозначение f2(x)= .

Функция f3(x) тождественно равна единице. Она называется константой единица и обозначается f3(x)=1.

2.2. Переключательные функции двух аргументов.

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

Переключательные функции двух аргументов

Рассмотренные шестнадцать функций двух аргументов (будем называть их элементарными) позволяют строить новые переключательные функции следующим образом:

· путем перенумерации аргументов;

· путем подстановки в функцию новых функций вместо аргументов.

Пусть формула F зависит от списка переменных <X1, X2, ..., Xk>.

Формула F называется тавтологией (тождественно-истинной формулой –ТИФ), если при любых значениях переменных списка <X1, X2, ..., Xk> соответствующая ей функция принимает значение 1.

Формула F называется выполнимой (условно-истинной формулой – УИФ), если при некоторых значениях переменных списка <X1, X2, ..., Xk> соответствующая ей функция принимает значение 1.

Формула F называется тождественно-ложной формулой – ТЛФ, если при любых значениях переменных списка <X1, X2, ..., Xk> соответствующая ей функция принимает значение 0.

Формула F называется опровержимой (условно-ложной формулой) , если при некоторых значениях переменных списка <X1, X2, ..., Xk> соответствующая ей функция принимает значение 0.

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

Правило подстановки формулы F вместо переменной x: все вхождения переменной x в исходное соотношение должны быть одновременно заменены формулой F.

Правило замены подформул: если какая-либо формула F, описывающая функцию f, содержит F1 в качестве подформулы, то замена F1 на эквивалентную F2 не изменит функцию f.

Эти два правила также называют эквивалентными преобразованиями так как в результате их применения получаются формулы, эквивалентные исходным.

Логическую функцию можно задать двумя способами:

1. С помощью таблиц истинности (табличный способ). Обычно наборы значений функций располагаются в таблице истинности по возрастанию соответствующих им n-значных двоичных чисел. Такое упорядочивание наборов позволяет записывать логическую функцию в виде набора значений функций (транспонированный правый столбец таблицы истинности).

2. В виде формулы, которая описывает логическую функцию как суперпозицию других функций. Для каждой логической функции существует бесконечное множество формул, но таблица истинности у всех этих формул одна и та же. Формулы, задающие одну и ту же логическую функцию (т.е. они на одних и тех же наборах имеют одни и те же значения), называются равносильными (эквивалентными).