Информатика и программирование - Основы информатики, страница 8

Высказывания и логические операции над ними образуют алгебру высказываний (булеву алгебру), предложенную английским математиком Джорджем Булем.

6.2.Логические операции

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

1. Отрицание (обозначается также X, X).

Отрицание (NOT, читается «не X») – это высказывание, которое истинно, если X ложно, и ложно, если X истинно.

2. Конъюнкция XY (X&Y, XY).

Конъюнкция XY (AND, логическое умножение, «X и Y») – это высказывание, которое истинно только в том случае, если X истинно и Y истинно.

3. Дизъюнкция X+Y (XY).

Дизъюнкция X+Y (OR, логическая сумма, «X или Y или оба») – это высказывание, которое ложно только в том случае, если X ложно и Y ложно.

4. Стрелка Пирса X  Y.

Стрелка Пирса X  Y (NOR (NOT OR), ИЛИ-НЕ) – это высказывание, которое истинно только в том случае, если X ложно и Y ложно.

5. Штрих Шеффера X | Y.

Штрих Шеффера X | Y (NAND (NOT AND), И-НЕ) – это высказывание, которое ложно только в том случае, если X истинно и Y истинно.

Определить значения логических операций при различных сочетаниях аргументов можно из таблицы истинности (табл.  6 .7)

Таблица 6.7. Таблица истинности для основных логических операций, используемых в ЭВМ

Чтобы определить значение операции 0 + 1 в таблице истинности, необходимо на пересечении столбца X + Y (определяет операцию) и строки, где X = 0 и Y = 1 (так первый аргумент равен 0, а второй – 1), найти значение 1, которое и будет являться значением операции 0 + 1.

В алгебре высказываний существуют две нормальные формы: конъюнктивная нормальная форма (КНФ) и дизъюнктивная нормальная форма (ДНФ).

КНФ – это конъюнкция конечного числа дизъюнкций нескольких переменных или их отрицаний (произведение сумм). Например, формула X(Y + Z) находится в КНФ.

ДНФ – это дизъюнкция конечного числа конъюнкций нескольких переменных или их отрицаний (сумма произведений). Например, формула X + YZ находится в ДНФ.

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

Правило 6.13. (порядок применения формул при преобразованиях) Перечисленные формулы рекомендуется применять в следующем порядке:

1) преобразование стрелки Пирса ( 6 .0) и штриха Шеффера ( 6 .0);

2) законы де Моргана ( 6 .0)-( 6 .0);

3) формулы дистрибутивности ( 6 .0)-( 6 .0);

4) элементарные поглощения ( 6 .0)-( 6 .0).

Обычно формула приводится к ДНФ, а затем отдельные слагаемые поглощаются.

6.3.Логические функции

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

Логическая функция (функция алгебры высказываний) f(X₁, X₂, …, X_n) от n переменных – n-арная операция на множестве [0; 1]. В этой функции логические переменные X₁, X₂, …, X_n представляют собой высказывания и принимают значения 0 или 1.

Существует различных логических функций от n переменных.

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

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

1) булевый базис, состоящий из конъюнкции, дизъюнкции и отрицания;

2) базис NOR, состоящий из стрелки Пирса;

3) базис NAND, включающий штрих Шеффера.

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

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

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

Числовой. Функция задается в виде десятичных (восьмеричных, шестнадцатеричных) эквивалентов номеров тех наборов аргументов, на которых функция принимает значение 1. Нумерация наборов начинается с нуля. Аналогичным образом логическая функция может быть задана по нулевым значениям.

Пример 6.26. Функция задана аналитически:

f(X, Y, Z) = + .

Записать функцию в табличном и числовом представлениях.

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

Опустим отрицание до переменных по законам де Моргана ( 6 .0)-( 6 .0):

f(X, Y, Z) = + = Z + X + Y + Z.

Сократим одинаковые слагаемые по формуле ( 6 .0) и перегруппируем их:

f(X, Y, Z) = Z + X + Y + Z = X + Y + Z.

По полученному выражению построим таблицу истинности, путем подстановки значений переменных в строке и записи значения функции в эту строку (табл.  6 .8)

Таблица 6.8. Таблица истинности
функции f(X, Y, Z) = X + Y + Z

Чтобы представить функцию в числовом представлении, выпишем номера наборов, на которых функция принимает значение 1: 1, 2, 4, 5, 6, 7 и номера наборов, на которых функция принимает значение 0: 0, 3.

Тогда функция f(X, Y, Z) = X + Y  +  Z имеет два числовых представления. В первом случае перечисляются все наборы, на которых функция равна 1: