 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Краткие сведения из теории. Алгебра логики - это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических
|
|
Алгебра логики - это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.
Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 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. Это функция нескольких переменных и определяется следующей таблицей истинности для двух переменных:
| x1 | x2 | Y |
Функция имеет вид Y =x1 Å x2
Условное графическое обозначение элемента исключающее ИЛИ.
x1
=1
Y = x1 Å x2
x2
Всякая логическая функция “n” переменных может быть задана таблицей, в левой части которой перечислены все 2n наборов значений переменных, а в правой части – значения функции на этих наборах. Например, для 3-х переменных имеем:
| x1 | x2 | x3 | Y |
Наборы (строки) х на которых функция 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
Выполнение логических операций производится в соответствии с приоритетами. В таблице представлены приоритеты выполнения логических операций.
| приоритет | операция |
| инверсия конъюнкция дизъюнкция сложение по mod 2 |
Операции одного приоритета выполняются слева направо. Для изменения порядка выполнения операций могут использоваться скобки.
Содержание работы
1. Выбрать вариант в задании 1 из таблицы 1 и составить логическую функцию. Для первого варианта берутся значения Y1, для второго варианта берутся значения Y2 и т.д.
2. Преобразовать логическую функцию к более простому виду.
3. Проверить полученную логическую функцию подстановкой нулей и единиц для аргументов Х1, Х2, Х3.
4. Выбрать вариант в задании 2 и найти значение логического выражения.
5. Выбрать вариант в задании 3 и по заданной принципиальной схеме составить логическое выражение и заполнить для него таблицу истинности.
Дата публикования: 2015-02-18; Прочитано: 531 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
