Лекции по Информатике_1курс_посл.версия. Курс лекций по дисциплине информатика москва, 2012 Оглавление
Скачать 1.55 Mb.
|
1.4.Логические основы ЭВМПринципы работы ЭВМ основываются на законах математической логики, поэтому ее элементы широко используются для поиска и обработки информации и при разработке схем электронных устройств. Математическая логика – это наука о формах и способах мышления и их математическом представлении. Мышление основывается на понятиях, высказываниях и умозаключениях. Понятие объединяет совокупность объектов, обладающими некоторыми существенными признаками, которые отличают их от других объектов. Например, понятие «звезда» объединяет множество светящихся газовых шаров. Это понятие трудно спутать с таким понятием как, например, «автомобиль». Объекты, соответствующие одному понятию, образуют множество. Понятие имеет две характеристики: 1) содержание; 2) объем. Содержание понятия – это совокупность существенных признаков, выделяющих объекты, соответствующие данному понятию, среди других объектов. Например, содержание понятия «человек» можно раскрыть так: «Общественное существо, обладающее сознанием и разумом». Объем понятия «человек» определяется численностью людей, живущих в мире. Высказывание (суждение, утверждение) – это повествовательное предложение, в котором утверждаются или отрицаются свойства реальных предметов и отношения между ними. Поэтому высказывание может быть истинным или ложным. Истинным называется высказывание, в котором связь понятий правильно отражает свойства и отношения реальных вещей, например: «Москва – столица России». Истинность высказывания кодируется единицей (1) и имеет значение «истина». Ложным высказывание будет в том случае, когда оно не соответствует реальной действительности, например: «Париж – столица США». Ложность высказывания кодируется нулем (0) и имеет значение «ложь». Обычно высказывания обозначаются логическими переменными – заглавными латинскими буквами с индесом или без, например, A = «Сегодня идет дождь». Логические переменные принимают только два значения 0 и 1. Умозаключение позволяет из известных фактов (истинных высказываний) получать новые факты. Например, из факта «Все углы треугольника равны» следует истинность высказывания «Этот треугольник равносторонний». Высказывания и логические операции над ними образуют алгебру высказываний (булеву алгебру), предложенную английским математиком Джорджем Булем. 1.4.1.Логические операцииОсновные логические операции над высказываниями, используемыми в ЭВМ, включают отрицание, конъюнкцию, дизъюнкции, стрелку Пирса и штрих Шеффера. Рассмотрим эти логические операции. 1. Отрицание (обозначается также X, X). Отрицание (NOT, читается «не X») – это высказывание, которое истинно, если X ложно, и ложно, если X истинно. 2. Конъюнкция XY (X&Y, XY). Конъюнкция XY (AND, логическое умножение, «X и Y») – это высказывание, которое истинно только в том случае, если X истинно и Y истинно. 3. Дизъюнкция X+Y (XY). Дизъюнкция 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 истинно. Определить значения логических операций при различных сочетаниях аргументов можно из таблицы истинности. Таблица истинности для основных логических операций, используемых в ЭВМ
Чтобы определить значение операции 0 + 1 в таблице истинности, необходимо на пересечении столбца X + Y (определяет операцию) и строки, где X = 0 и Y = 1 (так первый аргумент равен 0, а второй – 1), найти значение 1, которое и будет являться значением операции 0 + 1. В алгебре высказываний существуют две нормальные формы: конъюнктивная нормальная форма (КНФ) и дизъюнктивная нормальная форма (ДНФ). КНФ – это конъюнкция конечного числа дизъюнкций нескольких переменных или их отрицаний (произведение сумм). Например, формула X(Y + Z) находится в КНФ. ДНФ – это дизъюнкция конечного числа конъюнкций нескольких переменных или их отрицаний (сумма произведений). Например, формула X + YZ находится в ДНФ. Логические операции обладают свойствами, сформулированными в виде равносильных формул.
Порядок применения формул при преобразованиях - перечисленные формулы рекомендуется применять в следующем порядке: 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. Нумерация наборов начинается с нуля. Аналогичным образом логическая функция может быть задана по нулевым значениям. |