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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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. Таблица истинности для основных логических операций, используемых в ЭВМ

X	Y		XY	X + Y	X  Y	X | Y
0	0	1	0	0	1	1
0	1	1	0	1	0	1
1	0	0	0	1	0	1
1	1	0	1	1	0	0

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

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

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

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

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

Снятие двойного отрицания (отрицание отрицания): =X. (6.0) Коммутативность: XY=YX. (6.0) X+Y=Y+X. (6.0) Ассоциативность: (XY)Z=X(YZ). (6.0) (X+Y)+Z=X+(Y+Z). (6.0) Дистрибутивность: X(Y+Z)=XY+XZ. (6.0) X+YZ=(X+Y)(X+Z). (6.0) Законы де Моргана: . (6.0) . (6.0) Идемпотентность: X+X=X. (6.0) XX=X. (6.0) Закон противоречия: X =0. (6.0)

Закон «исключения третьего»: X+ =1. (6.0) Свойства констант: X1=X. (6.0) X0=0. (6.0) X+1=1. (6.0) X+0=X. (6.0) Элементарные поглощения: X+XY=X. (6.0) X+ Y=X+Y. (6.0) X(X+Y)=X. (6.0) X( +Y)=XY. (6.0) Преобразование стрелки Пирса: XY= . (6.0) Преобразование штриха Шеффера: X | Y= . (6.0)

Правило 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

Номер набора	X	Y	Z	f(X, Y, Z) = X + Y + Z
0	0	0	0	0
1	0	0	1	1
2	0	1	0	1
3	0	1	1	0
4	1	0	0	1
5	1	0	1	1
6	1	1	0	1
7	1	1	1	1

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

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

Характеристики

Список файлов книги