Лекция основы булевой алгебры. Двоичное кодирование. Арифметические операции в двоичной системе счисления

• Название: Лекция основы булевой алгебры. Двоичное кодирование. Арифметические операции в двоичной системе счисления
• Дата: 26.09.2022
• Размер: 252 Kb.
• Имя файла: -2.doc
• Тип: Лекция; #697340

ЛЕКЦИЯ 2. Основы булевой алгебры. Двоичное кодирование. Арифметические операции в двоичной системе счисления.

План:

1. 
   Понятие логики, логической переменной, логической функции.
   
2. 
   Простые и сложные высказывания.
   
3. 
   Логические функции от одного и двух аргументов (переменных).
   
4. 
   Свойства элементарных функций алгебры логики.
   

Ключевые слова:

Логика, алгебра логики, логические или булевые переменные, логическая функция, простое и сложное высказывание, двоичный набор, элементарные логические функции, таблица истинности, свойство коммутативности, свойство ассоциативности, свойство дистрибутивности, сложение по модулю два.
Понятие логики, логической переменной, логической функции.

Наряду с решением арифметических задач ЭВМ могут решать и логические задачи. Как известно, логика – это наука о законах и формах мышления. Математическая логика занимается изучением возможности применения формальных методов для решения логических задач.

В цифровой технике применяется начальный раздел математической логики – исчисление высказываний или алгебра логики. Иногда алгебру логики называют также булевой алгеброй по имени английского математика Джорджа Буля, разработавшего ещё в 19 веке основные положения исчисления высказываний. В настоящее время она широко применяется при анализе и синтезе различных устройств ЭЦВМ, а также при машинном решении логических задач.

Начальным понятием алгебры логики является понятие высказывания. Под высказыванием понимается любое утверждение, которое оценивается только с точки зрения его истинности или ложности. Другие качественные характеристики высказываний (хорошие, плохие, литературные, политические и т. п.) не рассматриваются. Высказывания могут быть либо истинными, либо ложными. Считается, что истинно-ложных и ложно-истинных высказываний не существует.

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

Определение: Рассмотрим два высказывания :

Х – «Республика Узбекистан расположена в Азии»;

Y – «Оптика – это один из разделов математики».

Обозначим их латинскими буквами, присваивая им значение 1, в случае истинности и значение 0 в случае ложности. Первое высказывание истинно. В соответствии с этим Х = 1. Второе высказывание не соответствует действительности, т. е. является ложным, и поэтому Y = 0.

Простые и сложные высказывания

Высказывания могут быть простыми и сложными. Высказывание называется простым, если его значение истинности не зависит от значений истинности каких-либо других высказываний. Такое высказывание содержит одну простую законченную мысль. Приведённые в качестве примеров высказывания являются простыми. Сложным называется высказывание, значение истинности которого зависит от значений истинности других высказываний. Следовательно, любое сложное высказывание можно считать логической (булевой) функцией некоторых двоичных аргументов – простых высказываний, входящих в его состав. В свою очередь, сложные высказывания могут служить аргументами для более сложных логических функций, т.е. при построении логических функций справедлив принцип суперпозиции.

Определение: Таким образом, функцияf, зависящая от n переменных Х_1, Х_{2, ….} Х_nназывается булевой или переключательной, если функция f и любой из её аргументов Х_i, i 1, n принимает значения только из множества { 0, 1 }. Под двоичным набором а = < а_1, а_{2 …..,} а_n > а_i { 0, 1 } понимается совокупность значений аргументов Х_1, Х_{2, ….} Х_nбулевой функции f. Двоичный набор имеет длину n, если он предоставлен n цифрами из множества { 0, 1 }.

Рассмотрим значения функций от трёх переменных f(Х_1, Х_2, Х₃ ) и (Х_1, Х_2, Х₃ ), заданных в виде таблицы истинности.

	Х1	Х2	Х3	f(Х1, Х2, Х3 )	(Х1, Х2, Х3)
0	0	0	0	0	0
1	0	0	1	1	0
2	0	1	0	0	0
3	0	1	1	1	1
4	1	0	0	0	0
5	1	0	1	0	1
6	1	1	0	0	1
7	1	1	1	0	0

Функция f принимает значение 1 при наборах 001 и 011, а при всех остальных наборах равна 0.

Функция принимает значение 1 при 011, 101, 110, а при остальных 0.

Отметим следующие свойства логарифмической функции:

• 
  Логарифмическая функция от n аргументов может быть определена для 2² двоичных наборов, поскольку между двоичными наборами и двоичными числами существует взаимно однозначное соответствие.
  
• 
  Существует не более чем 2²ⁿ различных булевых функций n переменных. Действительно, если на каждом и 2ⁿ наборов функция может принимать два значения, то общее число функции определяется как 2²ⁿ.
  

Для функции от двух переменных возможны 4 двоичных набора. f(Х_1, Х_2, ) : 00, 01, 10, 11. А всего функций от 2 переменных может быть 16.

Иногда двоичные наборы в таблице истинности булевой функции удобно представлять номерами наборов.
Логические функции от одного и двух аргументов

Рассмотрим наиболее употребляемые логические функции от одной и двух переменных f(Х) и f(Х _, Y)

Обозначение функции	Значение аргумента		Запись функций	Название функции
	0	1
f0	0	0	0	Тождественная 0 (константа 0)
f1	0	1	Х	Тождественная функция
f2	1	0		Отрицание Х (инверсия)
f3	1	1	1	Тождественная 1 (константа 1)

f(Х _, Y)

Функция	Значение функции при аргументах Х , Y				Запись функции	Название функции
	00	01	10	11
f0	0	0	0	0	0	Тождественная 0 (константа 0)
f1	0	0	0	1	ХY	Конъюнкция
f2	0	0	1	0	Х	Запрет Х
f3	0	0	1	1	Х	Повторение Х
f4	0	1	0	0	Y	Запрет Х
f5	0	1	0	1	Y	Повторение Y
f6	0	1	1	0	Х Y	Неравнозначность
f7	0	1	1	1	Х Y	Дизъюнкция
f8	1	0	0	0	Х Y	Операция Пирса
f9	1	0	0	1	Х Y	Эквивалентность
f10	1	0	1	0		Отрицание двух аргументов
f11	1	0	1	1	Х Y	Импликация от 2 арг. к 1 арг.
f12	1	1	0	0		Отрицание одного аргументов
f13	1	1	0	1	Y Х	Импликация от 1 арг. ко 2 арг.
f14	1	1	1	0		Функция Шеффера
f15	1	1	1	1	1	Тождественная 1 (константа 1)

Из этих функций можно выделить следующие:

f₀ - константа 0;

f₁₅ - константа 1;

f₃ , f₅ , f₁₀ , f₁₂ – функции одного аргумента;

Остальные 10 функций имеют свои названия и математические выражения, их называют элементарными действиями.

1. 
   Отрицание – инверсия - операция НЕ – NOT
   

f₁₂ = = Х

«НЕ»

Х	f12 =
0	1
1	0

2. 
   Логическое умножение – конъюнкция – операция И – ANI.
   

(& - амперсанд) f₁ = X * Y = X & Y = X Y,

таблица истинности «И»

X	Y	f1
0	0	0
0	1	0
1	0	0
1	1	1

3. 
   Логическое сложение – дизъюнкция – операция ИЛИ – OR
   

(лат. название «Vel» ) f₇ = X Y = X + Y

Приведённые элементарные действия достаточны для анализа и синтеза схем ВС, поскольку остальные функции можно выразить через эти элементарные.

«ИЛИ»

X	Y	f7
0	0	0
0	1	1
1	0	1
1	1	1

4. 
   f₆ = Х Y = Х Y - неравнозначная или сложение по модулю 2 или сумма mod 2.
   

Х Y

X	Y	f6
0	0	0
0	1	1
1	0	1
1	1	0

5. 
   f₉ = Х Y = Х Y – эквивалентность f₉ = Х Y = ХY
   
6. 
   f₁₄ = Х / Y = - штрих Шеффера, функция И – НЕ, отрицание конъюнкции
   

И – НЕ

X	Y	f14
0	0	1
0	1	1
1	0	1
1	1	0

7. 
   f₈ = = Х Y отрицание дизъюнкция – стрелка Пирса – функция ИЛИ-НЕ
   

ИЛИ - НЕ

X	Y	f8
0	0	1
0	1	0
1	0	0
1	1	0

8. 
   f₈ = Y Х = Х + ; f₁₃ = Y Х = + Y
   

9. f₂ = Х * ; f₄ = * Y - отрицание и импликация – запрет.
Свойства элементарных функций алгебры логики

Из таблицы видно, что элементарные функции типа отрицания, дизъюнкции, Шеффера, Пирса, и т.д. находятся в определенной связи друг с другом. Рассмотрим эти связи и свойства исходных функций.

Конъюнкция, дизъюнкция отрицание (функции И, ИЛИ, НЕ).Используя основные положения алгебры логики, нетрудно убедиться в справедливо следующих восьми аксиом. Пусть Х – некоторая логическая переменная. Тогда

1. 
   что означает возможность исключения из логического выражения всех членов, имеющих двойное отрицание, заменив их исходной величиной;
   

2. ( X X ) = X; X X ……. X = X; X * X = X; X * X * ….. * X = X, правила подобных преобразований позволяют сокращать длину логических выражений;

3. Х 0 = Х;

4. Х 1 = 1;

5. Х * 0 = 0;

6. Х * 1 = Х;

7. Х * = 0;

8. Х = 1.

Дизъюнкция и конъюнкция обладают рядом свойств, аналогичных свойствам обычных арифметических операций сложения и умножения:

1) свойство ассоциативности (сочетательный закон):

( X Y ) Z = X ( Y Z ) = X Y Z;

( X * Y ) * Z = X * ( Y * Z ) = X * Y * Z;

2) свойство коммутативности (переместительный закон):

X Y = Y X; X * Y = Y * X;

3) свойство дистрибутивности (распределительный закон):

для конъюнкции относительно дизъюнкции

X * ( Y Z ) = X * Y X * Z;

для дизъюнкции относительно конъюнкции

X Y * Z = ( X Y ) * ( X Z );

Свойство дистрибутивности фактически определяет правила раскрытия скобок или взятия в скобки логических выражений.

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

Несложно установить правильность соотношений, известных как законы де Моргана:

= * ,

= ;

Из законов де Моргана вытекают следствия

( X Y ) = * ;

ХY = ;

с помощью которых появляется возможность выражать конъюнкцию через дизъюнкцию и отрицание или дизъюнкцию через конъюнкцию и отрицание.

Законы де Моргана и следствия из них справедливы для любого количества переменных.

Для логических функций устанавливаются соотношения, известные как законы поглощения

Х ХY = Х ;

Х ( X Y ) = Х

Функция сложения по модулю 2 (исключительное ИЛИ) – функция, выражаемая следующим образом

X Y = Y Х = ( )

Она обладает следующими свойствами:

коммутативности (переместительный закон):

X Y = Y X

ассоциативности (сочетательный закон)

X (Y Z) = (X Y) Z

дистрибутивности (распределительный закон)

X(Y Z) = (X*Y) ( Х*Z)

Для этой функции справедливы аксиомы

X X = 0; X 1 = ;

X = 1; X 0 = X;

На основании аксиом и свойств можно вывести правила перевода функций И, ИЛИ,НЕ через функцию сложения по модулю 2:

= X 1; X 0 = X;

( X Y ) = X Y Х*Y;

Х*Y = (X Y) ( X Y ).

При упрощении логических выражений можно воспользоваться также

следующей таблицей:

ХY			ХY	X Y		X Y		*	X Y	X=Y	Y Х	( ) (X Y)
00	1	1	0	0	1	1	1	1	0	1	0	0
01	1	0	0	1	1	0	1	0	1	0	1	1
10	0	1	0	1	1	0	1	0	1	0	1	1
11	0	0	1	1	0	0	0	0	0	1	0	0

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

1. 
   Что такое логическая переменная?
   
2. 
   Что представляет собой логическая функция?
   
3. 
   Как выглядит двоичный набор?
   
4. 
   В чем заключается суперпозиция логической функции?
   
5. 
   Как выглядит таблица истинности?
   
6. 
   В чем заключается свойство коммутативности функции?
   
7. 
   Какие функции относятся к элементарным логическим функциям?
   

Литература:

1. 
   X.K.Aripov, A.M.Abdullaev, N.B.Alimova, X.X.Bustanov, E.V.Ob’edkov, Sh.T.Toshmatov. Sxemotexnika. T.: TAFAKKUR BO’STONI, 2013 y.
   
2. 
   X.K. Aripov, A.M. Abdullayev, N.B. Alimova, X.X. Bustanov, Sh.T. Toshmatov. Raqamli mantiqiy qurilmalami loyihalashtirish. Darslik. -T.: «Aloqachi », 2017, 396 bet.
   
3. 
   Х.К.Арипов, А.М.Абдуллаев, Н.Б.Алимова, Х.Х.Бустанов, Е.В.Объедков, Ш.Т.Тошматов. Схемотехника. Т.: ALOQACHI, 2010г.
   
4. 
   Digital Logic Design, Jiwang Ware Z Scene. Fourth Edition, 2002y.
   
5. 
   Robert L. Boyleastad. Introductory Circuit analysis. 2014-Pearson Education Limited, 1091 p.
   
6. 
   Stephon Brown, Zvonko Vranesic. Fundamentals of Digital Logic with Verilog Design. 2014-The Me Grow-Hin Companies. 847p.
   
7. 
   Behzad Razavi. Fundamentals of Microelectronics.2nd edition. 2014y. John Wiley&Sons. 932 p.
   
8. 
   Амосов B.B. Схемотехника и средства проектирования цифровых устройств. Учебное пособие. БХВ-Петербург. 2016г. 562с.
   
9. 
   В.М. Пролейко. Базовые лекции по электронике (в 2-х томах). ТЕХНОСФЕРА. Москва. 2009 г.
   
10. 
    С.Н.Лехин. Схемотехника ЭВМ. Санкт-Петербург, 2010г.