Виталий Сигорский - Математический аппарат инженера

Номера столбцов определяются расположенными над ними n -разрядными числами с основанием k, каждое из которых читается сверху вниз. Номера функций отождествляются с k n -разрядными числами, которые соответствуют строкам матрицы в той же системе счисления.

4. Двузначные однородные функции.Наиболее простым и в то же время важнейшим классом однородных функций являются двузначные (булевы) функции, частично рассмотренные в (1.5. 2) и последующих пунктах.

- 506 -

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

Число всевозможных булевых функций n переменных v = 2 n быстро возрастает с увеличением n (при n = 3 оно равно 256, а при n = 5 превышает 4 миллиарда). Но функции одной и двух переменных еще можно перечислить и подробно исследовать, так как их количество сравнительно невелико ( v = 4 при п = 1 и v = 16 при n = 2).

Булевы функции одной переменной.Общая таблица соответствия для булевых функций одной переменной имеет вид (справа указаны обозначения функций):

Две функции у 0= 0 и у 3= 1 представляют собой функции-константы (тождественный нуль и тождественная единица), таккакони не изменяют своих значений при изменении аргумента. Функция y 1 = х повторяет значения переменной х и потому просто совпадает с ней.

Единственной нетривиальной функцией является у 2= x̅ , называемая отрицанием или инверсией ( x̅ читается «не х» ). Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.

- !!!!!!!!!!!!!!!!!!!!! -

- Продолжение следует... -

...

2. Алгебра логики

3. Контактные схемы

4. Логические схемы

5. Минимизация булевых функций

1. Основные определения. В контактных и логических схемах значения выходных переменных определяются только комбинацией значений переменных на входах в данный момент времени. Поэтому их называют комбинационными схемами. В более общем случае выходные переменные могут зависеть от значении входных переменных не только в данный момент, но и от их предыдущих значений. Иначе говоря, значения выходных переменных определяются последовательностью значений входных переменных, в связи, с чем схемы с такими свойствами называют последовательностными. Если входные и выходные переменные принимают значения из конечных алфавитов, то оба типа схем объединяются под названием конечные автоматы.

Пусть X i- алфавит входной переменной х i, а Y i – алфавит выходной переменной y i . Конечный автомат с n входами и m выходами характеризуется входным алфавитом Х = Х 1 × Х 2 × ... Х n и выходным алфавитом Y = Y 1 × Y 2 × ... Y m , причем символами входного алфавита служат слова x = ( x 1 , x 2 , …, x n ) длины n, а символами выходного алфавита - слова y = ( y 1 , y 2 , …, y m ) длины m, где x i ∈ X i и y i ∈ Y i . Особого внимания заслуживают конечные автоматы с двузначным структурным алфавитом, зависимости между входными и выходными переменными которых выражаются булевыми санкциями. Их значение обусловлено тем, что любая информация может быть представлена в двоичных кодах (двоично-десятичные коды чисел, телетайпный код в технике

- 564 -

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

В реальных условиях сигналы представляются непрерывными функциями времени, поэтому для надежного различения сигналов требуется, чтобы новые значения на входах появлялись после окончания переходных процессов, связанных с предыдущими значениями. При рассмотрении логической структуры автоматов обычно отвлекаются от существа этих процессов и считают, что переменные изменяются не непрерывно, а мгновенно в некоторые моменты времени, называемые тактами. Интервалы между тактами могут быть различными, но без потери общности их можно считать равными Δt . Предполагается, что тактовые моменты t ν + 1=t ν+ Δt определяются синхронизирующими сигналами. Таким образом, вводится понятие дискретного автоматного времени t n ( n = 1, 2, ...), причем переменные зависят не от физического времени, а от номера такта ν , т. е. вместо непрерывных функций x( t ) рассматриваются дискретные значения х ( ν ).

2. Состояния.Кроме входных и выходных переменных, можно выделить некоторую совокупность промежуточных переменных, которые связаны с внутренней структурой автомата. В комбинационных схемах промежуточные переменные непосредственно не участвуют в соотношениях вход - выход. Напротив, выходные функции последовательностных схем в качестве своих аргументов, кроме входных переменных, обязательно содержат некоторую совокупность промежуточных переменных s 1, s 2, …, s k, характеризующих состояние схемы. Набор всех возможных состоянии, которые присущи данной схеме, называется множеством состояний. Если S 1, S 2, …, S k- конечные алфавиты переменных состояния s 1, s 2, …, s k, то множество состояний S = S 1× S 2× … × S kтакже является конечным множеством.

Строгое определение понятия состояния связывается с той ролью, которое оно играет при описании конечных автоматов. Во-первых, значения совокупности выходных переменных на ν -м такте у ( ν ) = ( y 1 ( ν ), y 2 ( ν ), …, y m ( ν )), однозначно определяется значениями входных переменных x( ν ) = ( x 1 ( ν ), x 2 ( ν ), …, x n ( ν )) и состоянием s( ν ) = ( s 1 ( ν ), s 2( ν ), …, s k ( ν )), на том же такте, т.е. у ( ν ) = λ (x( ν ), s( ν )). Во-вторых, состояние s( ν + 1) в следующем ( ν + 1)-м такте однозначно определяется входными переменными х ( ν ) и состоянием s( ν ) в предыдущем такте, т.е. s( ν + 1) = δ (x( ν ), s( ν )).

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