Vse_chto_est_po_IVT / Lab_Informatic / lab5_logica

Лабораторная работа №5

Тема: Алгебра логики. Логические операции, формулы и их преобразования.

Цель работы: Практическое изучение логических операций, функций и их преобразований.

Краткие сведения из теории

Алгебра логики - это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: "1" и "0".

Основоположником математической логики является английский математик Джордж Буль (1815 – 1864). Он впервые высказал идеи логического истолкования теории множеств.

Рассмотрим 2^х элементное множество B, элементы которого 0 и 1. Однако они не являются числами в обычном смысле. Наиболее распространенная интерпретация двоичных переменных – это логические: “ДА – НЕТ” или “ИСТИННО – ЛОЖНО”. Например: в языках программирования вводится специальный тип переменной – логическая переменная, значения которой обозначаются TRUE и FALSE.

Таким образом, элементы множества B={0,1} будем рассматривать как формальные символы, а не числа.

Алгебра, образованная множеством B вместе со всеми возможными операциями на нем, называется алгеброй логики или Булевой алгеброй.

Булевой функцией f(x₁, x₂, … , x_n) называется функция, которая принимает два значения 0 или 1 в зависимости от переменных х_i , каждая из которых может также принимать только два значения 0 или 1.

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

Рассмотрим основные функции алгебры логики.

1. Логическое отрицание (инверсия) обозначается чертой над аргументом или символом «¬». Это функция одной переменной:

f(x) = ¬x; ¬0 =1; ¬1=0.

Схема, реализующая логическое отрицание, называется логическим элементом НЕ.

Графическое обозначение элемента:

2. Логическое сложение (дизъюнкция). Это функция нескольких переменных. Функция обозначается следующим образом:

f(x₁,x₂) = x₁ V x₂ V x₃…

Для двух переменных таблица истинности имеет вид:

x₁ x₂ f(x₁,x₂)

0 0 0

0 1 1

1 0 1

1 1 1

Условное графическое обозначение схемы ИЛИ

3. Логическое умножение (конъюнкция). Это функция нескольких переменных. Функция обозначается следующим образом:

f(x₁x₂) = x₁ /\ x₂ /\ х₃ …

Функция определяется следующей таблицей истинности для двух переменных.

x₁ x₂ f(x₁x₂)

0 0 0

0 1 0

1 0 0

1 1 1

Условное графическое обозначение схемы И

4. Функция Шеффера – реализует умножение с отрицанием. Определяется для двух переменных следующей таблицей истинности. Это функция нескольких переменных:

x₁ x₂ f(x₁x₂)

0 0 1

0 1 1

1 0 1

1 1 0

Функция имеет вид:

f(x₁x₂) = x₁x₂ = ¬(x₁ /\ x₂)

Условное графическое обозначение схемы И-НЕ

5. Функция Пирса реализует логическое сложение с отрицанием. Определяется следующей таблицей истинности для двух переменных

x₁ x₂ f(x₁x₂)

0 0 1

0 1 0

1 0 0

1 1 0

Функция имеет вид:

f(x₁x₂) = x₁  x₂ = ¬(x₁ v x₂)

Условное графическое обозначение схемы ИЛИ-НЕ

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

6. Сложение по mod 2. Выполняет логическую операцию XOR. Это функция нескольких переменных и определяется следующей таблицей истинности для двух переменных:

x1	x2	Y
0 0 1 1	0 1 0 1	0 1 1 0

Функция имеет вид Y =x₁  x₂

Условное графическое обозначение элемента исключающее ИЛИ.

Всякая логическая функция “n” переменных может быть задана таблицей, в левой части которой перечислены все 2ⁿ наборов значений переменных, а в правой части – значения функции на этих наборах. Например, для 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. Переместительный закон. Коммутативность (лат. – менять, переменять).

X₁  X₂ = X₂  X₁ X₁  X₂ = X₂  X₁

2. Сочетательный закон. Ассоциативность (лат. – соединять).

X₁  (X₂  X₃) = (X₁  X₂)  X₃

X₁  (X₂  X₃) = (X₁  X₂)  X₃

3. Распределительный закон. Дистрибутивность.

X₁  (X₂  X₃) = (X₁  X₂)  (X₁  X₃)

X₁  (X₂  X₃) = (X₁  X₃)  (X₁  X₃)

4. Импликация

X → Y = (¬X) V Y

5. Закон поглощения.

X₁  (X₁ X₂) = X₁ X₁ (X₁  X₂) = X₁

6. Закон склеивания.

X₁X₂  X₁X₂ = X₁ (X₁  X₂)(X₁  X₂) = X₁

7. Правило де Моргана.

¬(X₁  X₂  X₃) = ¬X₁ /\ ¬ X₂ /\ ¬ X₃; ¬ (X₁/\ X₂ /\ X₃ )= ¬X₁  ¬X₂  ¬X₃

Выполнение логических операций производится в соответствии с приоритетами, представленными в таблице.

приоритет	операция
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” на входах).

Содержание отчета

1. Постановка задачи.

2. Краткие сведения из теории.

3. Результаты выполненных заданий.

4. Ответы на контрольные вопросы.

Контрольные вопросы

1. Дайте определение Булевой функции.

2. Назовите основные функции алгебры логики.

3. Составить таблицу истинности для функции Пирса.

4. Какие значения может принимать Булева функция?

5. Составить таблицу истинности для функции Шеффера.

6. Какой вид имеет функция Пирса?

7. Составьте таблицу истинности для логической операции XOR.

8. Найти значение функции Y=¬(x1x2)x1x2 при х1=0,х2=1.

9. Перечислите основные законы алгебры логики.

10. Какая логическая операция имеет высший приоритет?

11. Напишите переместительный закон для двух аргументов.

12. Напишите сочетательный закон для двух аргументов.

12