Главная страница Случайная лекция Мы поможем в написании ваших работ! Порталы: БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика Мы поможем в написании ваших работ! |
Краткие сведения из теории. Алгебра логики - это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических
Алгебра логики - это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: "1" и "0". Основоположником математической логики является английский математик Джордж Буль (1815 – 1864). Он впервые высказал идеи логического истолкования теории множеств. Рассмотрим 2х элементное множество B, элементы которого 0 и 1. Однако они не являются числами в обычном смысле. Наиболее распространенная интерпретация двоичных переменных – это логические: “ДА – НЕТ” или “ИСТИННО – ЛОЖНО”. Например: в языках программирования вводится специальный тип переменной – логическая переменная, значения которой обозначаются TRUE и FALSE. Таким образом, элементы множества B={0,1} будем рассматривать как формальные символы, а не числа. Алгебра, образованная множеством B вместе со всеми возможными операциями на нем, называется алгеброй логики или Булевой алгеброй. Булевой функцией f(x1, x2, … , xn) называется функция, которая принимает два значения 0 или 1 в зависимости от переменных хi , каждая из которых может также принимать только два значения 0 или 1. В таблице наборы переменных расположены в определенном порядке, который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа. Этим упорядочиванием будем пользоваться и дальше. Рассмотрим основные функции алгебры логики. 1. Логическое отрицание (инверсия) обозначается чертой над аргументом. Это функция одной переменной:
f(x) = x; 0 =1; 1=0.
Схема, реализующая логическое отрицание, называется логическим элементом НЕ. Графическое обозначение элемента: 1 x x
2. Логическое сложение (дизъюнкция). Это функция нескольких переменных. Функция обозначается следующим образом:
f(x1,x2) = x1 V x2 V x3…
Для двух переменных таблица истинности имеет вид: x1 x2 f(x1,x2) 0 0 0 0 1 1 1 0 1 1 1 1 Условное графическое обозначение схемы ИЛИ x1 1 x1 V x2 x2
3. Логическое умножение (конъюнкция). Это функция нескольких переменных. Функция обозначается следующим образом: f(x1x2) = x1 /\ x2 /\ х3 …
Функция определяется следующей таблицей истинности для двух переменных. x1 x2 f(x1x2) 0 0 0 0 1 0 1 0 0 1 1 1 Условное графическое обозначение схемы И
x1 & x1 * x2 x2
4. Функция Шеффера – реализует умножение с отрицанием. Определяется для двух переменных следующей таблицей истинности. Это функция нескольких переменных:
x1 x2 f(x1x2) 0 0 1 0 1 1 1 0 1 1 1 0
Функция имеет вид: f(x1x2) = x1½x2 = x1 /\ x2
Условное графическое обозначение схемы И-НЕ x1 & x1 * x2 x2
5. Функция Пирса реализует логическое сложение с отрицанием. Определяется следующей таблицей истинности для двух переменных
x1 x2 f(x1x2) 0 0 1 0 1 0 1 0 0 1 1 0
Функция имеет вид: f(x1x2) = x1 ¯ x2 = x1 Ú x2
Условное графическое обозначение схемы ИЛИ-НЕ
X1 1 x1 Ú x2 X2
Функции дизъюнкции и конъюнкции могут быть не только функциями двух переменных. В общем случае произвольного числа аргументов.
6. Сложение по mod 2. Выполняет логическую операцию XOR. Это функция нескольких переменных и определяется следующей таблицей истинности для двух переменных:
Функция имеет вид Y =x1 Å x2 Условное графическое обозначение элемента исключающее ИЛИ. x1 =1 Y = x1 Å x2 x2
Всякая логическая функция “n” переменных может быть задана таблицей, в левой части которой перечислены все 2n наборов значений переменных, а в правой части – значения функции на этих наборах. Например, для 3-х переменных имеем:
Наборы (строки) х на которых функция Y=1 называют единичным набором. Наборы х на которых Y=0, называют нулевым набором Y. Составим логическую функцию из таблицы значений. Для этого возьмем конъюнкции аргументов в той строке, где функция равна единице. Причем, если аргумент равен нулю – он берется с инверсией. Если аргумент равен единице – он берется с без инверсии. Полученные конъюнкции соединяем дизъюнкцией. Для нашего примера имеем три конъюнкции (три строки таблицы, где функция равна единице). Логическая функция имеет вид: Y = (X1 /\ X2 /\ X3) \/ (X1 /\ X2 /\ X3) \/ (X1 /\ X2 /\ X3)
Инверсия обозначается чертой над аргументом. В первой конъюнкции аргументы Х1, Х2 взяты с инверсией, так как их значения во второй строке таблицы равны нулю. Во второй конъюнкции аргументы Х2, Х3 взяты с инверсией, так как их значения в пятой строке таблицы равны нулю. В третьей конъюнкции аргумент Х2 взят с инверсией, так как его значение в шестой строке таблицы равно нулю. Полученные конъюнкции объединены операциями дизъюнкции.
Основные законы алгебры логики
1. Переместительный закон. Коммутативность (лат. – менять, переменять). X1 Ú X2 = X2 Ú X1 X1 Ù X2 = X2 Ù X1
2. Сочетательный закон. Ассоциативность (лат. – соединять). X1 Ú (X2 Ú X3) = (X1 Ú X2) Ú X3 X1 Ù (X2 Ù X3) = (X1 Ù X2) Ù X3
3. Распределительный закон. Дистрибутивность. X1 Ù (X2 Ú X3) = (X1 Ù X2) Ú (X1 Ù X3) X1 Ú (X2 Ù X3) = (X1 Ú X3) Ù (X1 Ú X3)
4. Закон поглощения. X1 Ú (X1 ÙX2) = X1 X1 Ù(X1 Ú X2) = X1
5. Закон склеивания. X1X2 Ú X1X2 = X1 (X1 Ú X2)(X1 Ú X2) = X1
6. Правило де Моргана. X1 Ú X2 Ú X3 = X1 X2 X3; X1X2X3 = X1 Ú X2 Ú X3
Выполнение логических операций производится в соответствии с приоритетами. В таблице представлены приоритеты выполнения логических операций.
Операции одного приоритета выполняются слева направо. Для изменения порядка выполнения операций могут использоваться скобки. Содержание работы
1. Выбрать вариант в задании 1 из таблицы 1 и составить логическую функцию. Для первого варианта берутся значения Y1, для второго варианта берутся значения Y2 и т.д. 2. Преобразовать логическую функцию к более простому виду. 3. Проверить полученную логическую функцию подстановкой нулей и единиц для аргументов Х1, Х2, Х3. 4. Выбрать вариант в задании 2 и найти значение логического выражения. 5. Выбрать вариант в задании 3 и по заданной принципиальной схеме составить логическое выражение и заполнить для него таблицу истинности.
Дата добавления: 2015-07-26; просмотров: 189; Нарушение авторских прав Мы поможем в написании ваших работ! |