Логічні основи обробки інформації на комп'ютерах

Лекція 7. Логічні основи побудови комп'ютерів [Л2, с.23-31; Л4, с.124-128, с.143-149; Л5, c.43-45].

7.1 Поняття булевої алгебри логіки. Логічне висловлювання та логічна функція.

7.2 Базові логічні операції: заперечення, кон'юнкція, диз'юнкція;

7.3 Додаткові логічні операції: штрих Шеффера, стрілка Пірса, імплікація, нерівнозначність.

Алгебра логики (Булевая алгебра) – математический аппарат формализующий записи и преобразования логических высказываний. Предложена английским математиком Джоном Булем в 19 веке.

Логическое высказывание – любое предположение относительно которого можно сказать истинно оно или ложно. Т.е. булева алгебра оперирует с логическими переменными, имеющими два значения, которые можно представить двоичной цифрой (битом):

Лог. 1 – да (правда, Thrue);

Лог. 0 – нет (ложь, False).

В силу этого булева алгебра лежит в основе работы цифровых двоичных компьютеров.

Логические переменные могут обозначаться:

x₁, x₂,….,x_i;

a, b, c, …., z;

A, B, C,…., Z.

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

Логическая функция – выражение, связывающее итоговое (выходное) логическое высказывание с исходными высказываниями, соединенными простыми логическими операциями.

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

y = f(x₁, x₂,….,x_i);

Y=f(A, B, C,…).

Лог. функция может быть представлена:

• выражением – формальной записью;
• таблицей истинности – значения наборов исходных переменных и значение функции, для каждого набора;
• картами типа матриц.

Базовые основные операции алгебры логики:

• отрицание;
• коньюнкция;
• дизъюнкция.

Отрицание является унарной операцией, т.е. выполняется над одной переменной (одним битом).

Коньюнкция и дизъюнкция относятся к бинарным операциям, т.е. выполняемым над двумя лог. переменными (двумя битами).

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

Теорема о числе логических функций.

Различных логических функций n-переменных может быть 2 в степени 2ⁿ.

Т.е.:

1-й переменной – 2;

2-х переменных - 16;

3-х переменных – 256;

4-х переменных – 65536 и т.д.

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

наименование и обозначение в булевой алгебре, в вычислительной технике и в программировании;

мнемоническое правило (словесное описание);

выражение (запись);

таблицу истинности;

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

Дата добавления: 2014-01-11