Главная страница

Лекции по Информатике_1курс_посл.версия. Курс лекций по дисциплине информатика москва, 2012 Оглавление


Скачать 1.55 Mb.
НазваниеКурс лекций по дисциплине информатика москва, 2012 Оглавление
АнкорЛекции по Информатике_1курс_посл.версия.doc
Дата05.06.2017
Размер1.55 Mb.
Формат файлаdoc
Имя файлаЛекции по Информатике_1курс_посл.версия.doc
ТипКурс лекций
#8312
страница3 из 24
1   2   3   4   5   6   7   8   9   ...   24

1.4.Логические основы ЭВМ


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

Математическая логика – это наука о формах и способах мышления и их математическом представлении.

Мышление основывается на понятиях, высказываниях и умозаключениях.

Понятие объединяет совокупность объектов, обладающими некоторыми существенными признаками, которые отличают их от других объектов. Например, понятие «звезда» объединяет множество светящихся газовых шаров. Это понятие трудно спутать с таким понятием как, например, «автомобиль». Объекты, соответствующие одному понятию, образуют множество.

Понятие имеет две характеристики:

1) содержание;

2) объем.

Содержание понятия – это совокупность существенных признаков, выделяющих объекты, соответствующие данному понятию, среди других объектов. Например, содержание понятия «человек» можно раскрыть так: «Общественное существо, обладающее сознанием и разумом».

Объем понятия «человек» определяется численностью людей, живущих в мире.

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

Истинным называется высказывание, в котором связь понятий правильно отражает свойства и отношения реальных вещей, например: «Москва – столица России». Истинность высказывания кодируется единицей (1) и имеет значение «истина».

Ложным высказывание будет в том случае, когда оно не соответствует реальной действительности, например: «Париж – столица США». Ложность высказывания кодируется нулем (0) и имеет значение «ложь».

Обычно высказывания обозначаются логическими переменными – заглавными латинскими буквами с индесом или без, например, A = «Сегодня идет дождь». Логические переменные принимают только два значения 0 и 1.

Умозаключение позволяет из известных фактов (истинных высказываний) получать новые факты. Например, из факта «Все углы треугольника равны» следует истинность высказывания «Этот треугольник равносторонний».

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

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


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

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 истинно.

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


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)

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

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

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

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

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

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

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


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

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

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

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

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

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

3) базис NAND, включающий штрих Шеффера.Рассмотрим некоторые способы представления логических функций.

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

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

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


написать администратору сайта