Основные законы алгебры логики.

Лекция 18. Алгебра логики.

Алгебра логики возникла в середине XIX века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные задачи алгебраическими методами.

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

Логическое высказывание - любое повествовательное предложение, в отношении которого однозначно можно сказать, истинно оно или ложно.

 

Пример 1: предложение «6 - четное число» является высказыванием, т.к. оно истинное.

Существуют предложения, в которых для выяснения истинности или ложности требуются дополнительные сведения. Такие предложения являются высказывательными формами.

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

Пример 2: предложение «площадь поверхности Индийского океана равна 75 млн.км²» - и истинно (значение приближенное, приемлемо на практике) и ложно (указанное значение неточное)

Из логических высказываний составляются логические формулы.

Например, X ® Y = X ٧Y

Основные законы алгебры логики.

 

В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений:

Закон	дляИЛИ (+)	дляИ (*)
1. Переместительный	X٧Y = Y٧X	X * Y = Y * X
2. Сочетательный	X٧(Y٧Z) = (X٧Y)٧Z	X * (Y * Z) = (X * Y) * Z
3. Распределительный	X * (Y٧Z) = X * Y٧X * Z	X٧Y *Z = (X٧Y) * (X٧ Z)
4. Правила де Моргана	X٧Y = X * Y	X*Y = X٧Y
5. Идемпотенция	X٧X = X	X * X = X
6. Поглощения	X٧X * Y = X	X * (X٧Y) = X
7. Склеивания	(X * Y)٧(X * Y) = Y	(X٧Y) * (X٧Y) = Y
8. Операция переменной с ее инверсией	X٧X = 1	X * X = 0
9. Операция с константами	X٧0 = X X٧1 = 1	X * 0 = 0 X * 1 = X
10. Двойного отрицания	X = X

Основные типы элементов.

1. Элемент “не” характеризует работу оператора, называемый инвертором,

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

__

X	Y

Y = NOT (X) = X

X

x y

 

2.Элемент “ или ” характеризует работу оператора, называемого дизъюнктором, выполняющего операцию “ логическое сложение ”- дизъюнкция. Для получения выходного сигнала достаточно наличие одного входного сигнала.

 

X1	X2	Y

Y = X1 OR X2.

x1 y

x2

 

Если хотя бы на одном входе 1,

то выходе тоже 1, иначе – 0.

 

3.Элемент “и” характеризует работу оператора, именуемый конъюнктуром, выполняющего операцию “ логическое умножение ”- конъюнкция. Для получения выходного сигнала необходимо наличие двух входных сигналов.

X1	X2	Y

Y = X1 AND X2 = X1&X2

x1 y

x2

 

Если хотя бы на одном входе 0,

то на выходе тоже 0, иначе – 1.

 

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

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

Для логических элементов различных комбинаций на основе логических операций сложения, вычитания, умножения и отрицания составляют таблицы истинности, описывающие различные состояния входов и соответствующие им состояния выходов. Таблицы истинности позволяют проанализировать работу составных логических элементов. Количество строк Таблица истинности равно 2ⁿ, где n-число входов.

Примеры комбинаций элементов.

1.Элемент «ИЛИ-НЕ» /отрицание сложения/

X1	X2	Y

___________

 

Y = X1 OR X2.

OR

x1

x2 y

 

 

Задание

Практическая работа № 3

Тема: Логические основы ПК. Алгебра логики. Простейшие логические элементы

И, ИЛИ, НЕ, логические операции конъюнкция, дизъюнкция и инверсия.

Таблица истинности.

Время: 2 ч.

Цель: первичное получение навыков построения логических схем.

Перечень оборудования: курс лекций, таблица схем простейших логических элементов.

Задания

 

1. Составить логические схемы следующих функций:

 

 

1. y = (x1 & x2) & x1

__ __

2. y = (x1 or x2) & x3

_________ _______

3. y = (x1 & x2) or x3

___ _ __ __

4. y = (x1 or x2) & x1

5. y = (x1 or x2) or (x3 & x4).

6. y = (x1 or x2) & x3

 

7. Y = (x1 or x2) or (x3 and x4).

____ _____

8. Y = (x1 or x2) & x3

9. Y = (x1 & x2) & (x1 or x2)

 

 

X2 Y У х2

x3

 

Практическая работа № 4

Тема: Законы алгебры логики.

Время: 2 ч.

Цель: первичное получение навыков построения логических схем.

Перечень оборудования: курс лекций, таблица схем простейших логических элементов.

Задания

1. Преобразовать оператор, используя основные законы алгебры логики, построить схемы и таблицу истинности:

1. Y = (x1 & x2) or (x3 & x4)

2. Y = (x1 & x2) or (x3 or x4)

3. Y = (x1 or x2) & x1

4. Y = x1 & (x2 or x3)

 

5. Y = x1 & x2

6. Y = (x1 or x2)or (x1 & x2)

__

7. Y = (x1 or x2 or x3)

Истинности.

d) е)

x1 х1

X2 х2

Y х3 у

x3

x4

F) g)

x1 х1

X2 х2

Y У

X3 х3

 

Лекция 18. Алгебра логики.

Алгебра логики возникла в середине XIX века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные задачи алгебраическими методами.

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

Логическое высказывание - любое повествовательное предложение, в отношении которого однозначно можно сказать, истинно оно или ложно.

 

Пример 1: предложение «6 - четное число» является высказыванием, т.к. оно истинное.

Существуют предложения, в которых для выяснения истинности или ложности требуются дополнительные сведения. Такие предложения являются высказывательными формами.

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

Пример 2: предложение «площадь поверхности Индийского океана равна 75 млн.км²» - и истинно (значение приближенное, приемлемо на практике) и ложно (указанное значение неточное)

Из логических высказываний составляются логические формулы.

Например, X ® Y = X ٧Y

Основные законы алгебры логики.

 

В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений:

Закон	дляИЛИ (+)	дляИ (*)
1. Переместительный	X٧Y = Y٧X	X * Y = Y * X
2. Сочетательный	X٧(Y٧Z) = (X٧Y)٧Z	X * (Y * Z) = (X * Y) * Z
3. Распределительный	X * (Y٧Z) = X * Y٧X * Z	X٧Y *Z = (X٧Y) * (X٧ Z)
4. Правила де Моргана	X٧Y = X * Y	X*Y = X٧Y
5. Идемпотенция	X٧X = X	X * X = X
6. Поглощения	X٧X * Y = X	X * (X٧Y) = X
7. Склеивания	(X * Y)٧(X * Y) = Y	(X٧Y) * (X٧Y) = Y
8. Операция переменной с ее инверсией	X٧X = 1	X * X = 0
9. Операция с константами	X٧0 = X X٧1 = 1	X * 0 = 0 X * 1 = X
10. Двойного отрицания	X = X