36. Теорема о полноте системы фал. Формулировка, пояснения на примерах. Понятие базиса.

Функцию f(X₁, X₂, …, X_n) называют функцией алгебры логики, если она, как и ее переменные, может принимать только два значения: логический 0 и логическую 1. Система функций является полной, если она включает в себя по крайней мере одну функцию, не сохраняющую 0, одну функцию, не сохраняющую 1, одну несамодвойственную, одну немонотонную и одну нелинейную функции (теорема Поста ‑ Яблонского). Свойством сохранения нуля функция f(X₁, X₂, …, X_n) обладает, если она на нулевом наборе аргументов равна нулю, т.е. f(0,0,…,0)=0.

Свойством сохранения единицы функция f(X₁, X₂, …, X_n) обладает, если она на единичном наборе аргументов равна единице, т. е. f(1, 1,…, 1) = 1.

Свойством самодвойственности обладает функция, у которой инвертирование всех аргументов приводит к инверсии значения функции, т.е. .

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

где .

Свойством линейности обладает функция, которая может быть представлена полиномом первой степени:

где a₀, a₁, …, a_n – коэффициенты, равные нулю или единице.

Базисом называют полную систему функций алгебры логики. Минимальный базис состоит из такого набора функций, исключение из которого любой функции превращает этот набор в неполную систему функций.

36. Триггеры: структура, принципы построения, классификация.

Триггер представляет собой устройство с двумя устойчивыми состояниями: 0 и 1. Он удобен для обработки двоичной информации. Двум устойчивым состояниям триггера отвечают различные значения выходного сигнала, каждый из которых соответствует логическим 0 и 1. Записанная в триггере двоичная информация (0 или 1) сохраняется до тех пор, пока состояние триггера не изменится. В случае необходимости входным сигналом триггер переводится из одного устойчивого состояния в другое, тем самым изменяется записанная в нем информация.

Наибольшее распространение получили статические (потенциальные) триггеры, в которых устойчивые состояния различаются уровнем постоянного потенциала. Основу статических триггеров составляет бистабильная ячейка на двух логических элементах ИЛИ-НЕ или И-НЕ, охваченных перекрестной положительной обратной связью. Выходные сигналы в триггере взаимно инверсны (противоположны в логическом смысле). Один выход называют прямым, а другой – инверсным. По способу управления триггеры бывают со статическим (срабатывают в момент, когда входной сигнал достигает порогового уровня) и динамическим (реагируют на перепад управляющего сигнала) управлением. По способу ввода информации триггеры подразделяют на асинхронные (ввод информации определяется изменением сигналов на логических входах) и синхронные (смены информационных сигналов еще не достаточно для их переключения – нужен дополнительный командный импульс). Основным и наиболее общим классификационным признаком является функциональный, который позволяет подразделять триггеры по их функциональному назначению и числу входов. Описание работы триггера задается в виде таблицы переходов (состояний), определяющей состояние триггера Qⁿ⁺¹ в момент времени t_n+1, если известно его состояние Qⁿ и значение входного сигнала Xⁿ в момент времени t_n. При одном входе возможны только два значения входного сигнала и две имеющие практическое значение таблицы состояний