Раздел 2. Основные понятия и определения

Логические основы информатики

Основные понятия и определения

В ЭВМ обрабатывается числовая информация, представленная в двоичной системе счисления (0 и 1). Любую схему ЭВМ можно рассматривать как устройство, имеющее n входных сигналов и m выходных. Поступления на входы некоторой последовательности 0 и 1 вызывает появление на выходах вполне определенной последовательности 0 и 1.

В ЭВМ различают два больших класса схем: класс комбинационных (логических) схем и класс конечных автоматов. В комбинационных схемах значение выходных сигналов в момент времени t однозначно определяется входными сигналами в тот же момент времени. В конечных автоматах выходные сигналы определяются не только входными сигналами, но и состоянием схемы (конечные автоматы содержат элементы памяти).

Построение схем ЭВМ решается с помощью аппарата математической логики. При этом используется только самая простая ее часть – алгебра логики. Основным понятием в той части алгебры логики, на которой основывается ее применение к построению схем ЭВМ, является понятие переключательной функции.

Переключательной или булевой функцией называется функция f(x_1, ,x₂, … x_n), способная принимать как и ее аргументы x₁, …, x_n только два значения 0 или 1. Любая переключательная функция (ПФ) может быть задана таблицей ее значений в зависимости от значений ее аргументов. Такая таблица называется таблицей истинности.

Таблица 2.1

Пример 2.1. Зададим ПФ трех аргументов f(x₁, x₂, x₃). Так как каждый из аргументов принимает лишь 2 значения, поэтому мы имеем 8 различных комбинаций 3 переменных. Эти комбинации называют набором. Наборы обычно пишут в так называемом естественном порядке, когда наборы принимают значения (000), (001), … Для получения следующего набора прибавляют 1 к правому разряду – применяется как бы сложение чисел. Наборам присваивается номер, равный двоичному числу, соответствующему данному набору. Сопоставляя каждому набору одно из двух значений ПФ, мы и получим таблицу истинности (например, представленную в табл. 2.1).

x1 x2 x3 f(x1,x2,x3)

Любая ПФ n аргументов определена на 2ⁿ наборах. Число различных ПФ n аргументов равно при n = 1 число различных ПФ равно 4, при n = 2 – 16, при n = 3 – 256, при n =4 – 65536, при n=5 – примерно 4,3´10⁹. Ясно, что прямое изучение ПФ с помощью таблиц истинности возможно для небольшого числа аргументов.

Возьмем какую либо комбинационную схему (КС) (рис.2.1).

Рис.2.1. Комбинационная схема

Если значения ПФ отождествить с выходным сигналом КС, а аргументов - с входными сигналами, то ПФ будет описывать процесс преобразования входных сигналов в выходные, т.е.

y₁ = f₁(x₁,x₂,…,x_n);

y₂ = f₂ (x₁,x₂,…,x_n);

.

.

.

y_m = f_m (x₁,x₂,…,x_n).

Любые сложные схемы ЭВМ строятся из простых схем, которые называют логическими элементами^Ì.

Логическим элементом называется электронная схема, реализующая элементарную ПФ, имеющая количество входов, равное числу аргументов ПФ и только один выход.

При составлении сложных схем используют два приема: последовательное соединение элементов и перестановку входов элементов. Последовательное соединение логических элементов показано на рис.2.2.

Рис.2.2. Последовательное соединение элементов

Последовательное соединение двух логических элементов позволяет получить функцию f₃ трех аргументов. Подстановка в функцию вместо ее аргументов других функций называется суперпозицией.

Перестановка входов элементов показана на рис.2.3.

В общем случае функция f₄(x₁,x₂,x₃) отличается от функции f₃(x₁,x₂,x₃). Замена одних аргументов функции другими или изменение порядка записи аргументов называется подстановкой аргументов.

Рис.2.3. Перестановка входов элементов

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