Vse_chto_est_po_IVT / АРХ-13-4 / Lab_Informatic / lab5_logica
.docЛабораторная работа №5
Тема: Алгебра логики. Логические операции, формулы и их преобразования.
Цель работы: Практическое изучение логических операций, функций и их преобразований.
Краткие сведения из теории
Алгебра логики - это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.
Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 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.
Схема, реализующая логическое отрицание, называется логическим элементом НЕ.
Графическое обозначение элемента:
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
Условное графическое обозначение схемы ИЛИ
3. Логическое умножение (конъюнкция). Это функция нескольких переменных. Функция обозначается следующим образом:
f(x1x2) = x1 /\ x2 /\ х3 …
Функция определяется следующей таблицей истинности для двух переменных.
x1 x2 f(x1x2)
0 0 0
0 1 0
1 0 0
1 1 1
Условное графическое обозначение схемы И
4. Функция Шеффера – реализует умножение с отрицанием. Определяется для двух переменных следующей таблицей истинности. Это функция нескольких переменных:
x1 x2 f(x1x2)
0 0 1
0 1 1
1 0 1
1 1 0
Функция имеет вид:
f(x1x2) = x1x2 = ¬(x1 /\ x2)
Условное графическое обозначение схемы И-НЕ
5. Функция Пирса реализует логическое сложение с отрицанием. Определяется следующей таблицей истинности для двух переменных
x1 x2 f(x1x2)
0 0 1
0 1 0
1 0 0
1 1 0
Функция имеет вид:
f(x1x2) = x1 x2 = ¬(x1 v x2)
Условное графическое обозначение схемы ИЛИ-НЕ
Функции дизъюнкции и конъюнкции могут быть не только функциями двух переменных. В общем случае произвольного числа аргументов.
6. Сложение по mod 2. Выполняет логическую операцию XOR. Это функция нескольких переменных и определяется следующей таблицей истинности для двух переменных:
-
x1
x2
Y
0
0
1
1
0
1
0
1
0
1
1
0
Функция имеет вид Y =x1 x2
Условное графическое обозначение элемента исключающее ИЛИ.
Всякая логическая функция “n” переменных может быть задана таблицей, в левой части которой перечислены все 2n наборов значений переменных, а в правой части – значения функции на этих наборах. Например, для 3-х переменных имеем:
-
x1
x2
x3
Y
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
0
1
1
0
0
Наборы (строки) х на которых функция 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. Импликация
X → Y = (¬X) V Y
5. Закон поглощения.
X1 (X1 X2) = X1 X1 (X1 X2) = X1
6. Закон склеивания.
X1X2 X1X2 = X1 (X1 X2)(X1 X2) = X1
7. Правило де Моргана.
¬(X1 X2 X3) = ¬X1 /\ ¬ X2 /\ ¬ X3; ¬ (X1/\ X2 /\ X3 )= ¬X1 ¬X2 ¬X3
Выполнение логических операций производится в соответствии с приоритетами, представленными в таблице.
-
приоритет
операция
1
2
3
4
инверсия
конъюнкция
дизъюнкция
сложение по mod 2
Операции одного приоритета выполняются слева направо. Для изменения порядка выполнения операций могут использоваться скобки.
Содержание работы
Задание 1.
1. Выбрать вариант из таблицы 1 и составить логическую функцию. Для первого варианта берутся значения Y1, для второго варианта берутся значения Y2 и т.д.
2. Преобразовать логическую функцию к более простому виду.
3. Составить электрическую принципиальную схему устройства на логических элементах.
Таблица 1. Варианты заданий
X1 |
X2 |
X3 |
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
Y6 |
Y7 |
Y8 |
Y9 |
Y10 |
Y11 |
Y12 |
0 0 0 0 1 1 1 1
|
0 0 1 1 0 0 1 1
|
0 1 0 1 0 1 0 1
|
1 0 0 1 0 1 1 1 |
1 1 0 0 1 0 0 1 |
1 0 1 1 1 0 1 0 |
1 1 0 0 0 1 1 0 |
1 0 0 1 1 1 0 0 |
1 1 0 1 0 0 1 0
|
0 1 1 1 0 0 1 0 |
0 0 0 1 1 1 0 1 |
1 1 1 0 0 1 0 1 |
0 0 1 0 1 1 1 0 |
1 0 1 1 0 0 1 0 |
0 1 0 0 1 1 1 1 |
Задание 2.
Выбрать вариант. По заданной принципиальной схеме логического устройства составить логическое выражение и заполнить для него таблицу истинности.
Задание 3 (Творческое).
Построить электрическую схему мажоритарного устройства на четыре входа. (Сигнал на выходе равен “1” по большинству сигналов “1” на входах).
Содержание отчета
-
Постановка задачи.
-
Краткие сведения из теории.
-
Результаты выполненных заданий.
-
Ответы на контрольные вопросы.
Контрольные вопросы
-
Дайте определение Булевой функции.
-
Назовите основные функции алгебры логики.
-
Составить таблицу истинности для функции Пирса.
-
Какие значения может принимать Булева функция?
-
Составить таблицу истинности для функции Шеффера.
-
Какой вид имеет функция Пирса?
-
Составьте таблицу истинности для логической операции XOR.
-
Найти значение функции Y=¬(x1x2)x1x2 при х1=0,х2=1.
-
Перечислите основные законы алгебры логики.
-
Какая логическая операция имеет высший приоритет?
-
Напишите переместительный закон для двух аргументов.
-
Напишите сочетательный закон для двух аргументов.