Основные законы алгебры логики.
Лекция 18. Алгебра логики.
Алгебра логики возникла в середине XIX века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные задачи алгебраическими методами.
Алгебра логики - раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.
Логическое высказывание - любое повествовательное предложение, в отношении которого однозначно можно сказать, истинно оно или ложно.
Пример 1: предложение «6 - четное число» является высказыванием, т.к. оно истинное.
Существуют предложения, в которых для выяснения истинности или ложности требуются дополнительные сведения. Такие предложения являются высказывательными формами.
Высказывательная форма - повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями.
Пример 2:предложение «площадь поверхности Индийского океана равна 75 млн.км2» - и истинно (значение приближенное, приемлемо на практике) и ложно (указанное значение неточное)
Из логических высказываний составляются логические формулы.
Например, 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. Правила де Моргана | ![]() ![]() ![]() | ![]() ![]() ![]() |
5. Идемпотенция | X٧X = X | X * X = X |
6. Поглощения | X٧X * Y = X | X * (X٧Y) = X |
7. Склеивания | ![]() | ![]() |
8. Операция переменной с ее инверсией | ![]() | ![]() |
9. Операция с константами | X٧0 = X X٧1 = 1 | X * 0 = 0 X * 1 = X |
10. Двойного отрицания | ![]() ![]() |
Основные типы элементов.
1. Элемент “не”характеризует работу оператора, называемый инвертором,
выполняющего операцию “логическое отрицание” - инверсия, преобразующий выходной сигнал, обратный входному.
__
X | Y |
Y = NOT (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.
Для хранения многозначных двоичных кодов необходимое количество триггеров (логических элементов), объединяются в более крупные логические элементы, т.е. образуются комбинации основных элементов, именуемые регистрами.
Комбинации основных элементов позволяют получать различные логические схемы и соответствующие им электронные схемы, применяемые в ЭВМ для обработки сигналов и проведения механических и логических операций.
Для логических элементов различных комбинаций на основе логических операций сложения, вычитания, умножения и отрицания составляют таблицы истинности, описывающие различные состояния входов и соответствующие им состояния выходов. Таблицы истинности позволяют проанализировать работу составных логических элементов. Количество строк Таблица истинности равно 2n, где n-число входов.
Примеры комбинаций элементов.
1.Элемент «ИЛИ-НЕ» /отрицание сложения/
X1 | X2 | Y |
___________
Y = X1 OR X2.
|
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 млн.км2» - и истинно (значение приближенное, приемлемо на практике) и ложно (указанное значение неточное)
Из логических высказываний составляются логические формулы.
Например, 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. Правила де Моргана | ![]() ![]() ![]() | ![]() ![]() ![]() |
5. Идемпотенция | X٧X = X | X * X = X |
6. Поглощения | X٧X * Y = X | X * (X٧Y) = X |
7. Склеивания | ![]() | ![]() |
8. Операция переменной с ее инверсией | ![]() | ![]() |
9. Операция с константами | X٧0 = X X٧1 = 1 | X * 0 = 0 X * 1 = X |
10. Двойного отрицания | ![]() ![]() |