Основные законы алгебры логики и правила преобразования логических выражений
В алгебре логики имеются законы, которые записываются в виде соотношений. Логические законы позволяют производить равносильные (эквивалентные) преобразования логических выражений. Преобразования называются равносильными, если истинные значения исходной и полученной после преобразования логической функции совпадают при любых значениях входящих в них логических переменных.
Для простоты записи приведем основные законы алгебры логики для двух логических переменных А и В. Эти законы распространяются и на другие логические переменные.
1. Закон противоречия:
2. Закон исключенного третьего:
3. Закон двойного отрицания:
4. Законы де Моргана:
5. Законы повторения: A & A = A; A v A = A; В & В = В; В v В = В.
6. Законыпоглощения: A (A & B) = A; A & (A B) = A.
7. Законыисключенияконстант: A 1 = 1; A 0 = A; A & 1 = A; A & 0 = 0; B 1 = 1; B 0 = B; B & 1 = B; B & 0 = 0.
8. Законы склеивания:
9. Закон контрапозиции: (A B) = (B A).
Для логических переменных справедливы и общематематические законы. Для простоты записи приведем общематематические законы для трех логических переменных A, В и С:
1. Коммутативный закон: A & B = B & A; A B = B A.
2. Ассоциативныйзакон: A & (B & C) = (A & B) & C; A (B C) = (A B) C.
3. Дистрибутивный закон: A & (B C) = (A &B) (A & C).
Как уже отмечалось, с помощью законов алгебры логики можно производить равносильные преобразования логических выражений с целью их упрощения. В алгебре логики на основе принятого соглашения установлены следующие правила (приоритеты) для выполнения логических операций: первыми выполняются операции в скобках, затем в следующем порядке: инверсия (отрицание), конъюнкция ( & ), дизъюнкция (v), импликация ( ), эквиваленция ( )
|
|
|
Выполним преобразование, например, логической функции
применив соответствующие законы алгебры логики.
35.Равносильные формулы алгебры логики. Основные равносильности.
Равносильные формулы – это две формулы алгебры логики, А и В, если они принимают одинаковые логические значения на любом наборе значений. Равносильность формул будем обозначать знаком= тогда запись означает, что формулы А и В равн 
осильны.
Тождественно ложной называется формула, принимающая значение 0 при всех значениях входящих в нее переменных.Пример. Тождественно ложная формула: х ^ не х конъюнкции, а отрицание относят к элементарным высказываниям.
18. Равносильности, выражающие одни логические операции через другие. 
Из равносильностей этой группы следует, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: конъюнкцию и отрицание или дизъюнкцию и отрицание. Дальнейшее исключение логических операций невозможно. Так, если мы будем использовать только конъюнкцию, то уже такая формула, как отрицание х, не может быть выражена с помощью операции конъюнкции. Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией является, например, операция Штрих Шеффера. Эта операция обозначается символом | и определяется следующей таблицей истинности: 
19.Равносильности, выражающие основные законыалгебры логики. 
|
|
|
36.Понятие логической переменной, способы задания функций алгебры логики.
Логические переменные принимают два значения: истина и ложь. Логическая переменная — это электрический сигнал, принимающий два различных значения, известные как состояния ИСТИНА и ЛОЖЬ.
Логической функцией называется функция f (x 1, x 1,...,x n) , которая, так же как и ее аргументы, может принимать только два значения (0 и 1).
Различают несколько способов задания ФАЛ, основными из которых являются: табличный, аналитический, цифровой, таблично-графический, геометрический.
Табличный способ предусматривает задание ФАЛ таблицей истинности, в которой указывают, какие из двух возможных значений «0» или «1» принимает функция на каждом наборе аргументов. Наборы, на которых значение ФАЛ равно «1» называются рабочими. Наборы, на которых функция принимает нулевое значение, называются запрещёнными.
|
|
|
Аналитический способ задания предполагает запись функции в виде формализованного выражения, составленного с использованием математического аппарата алгебры логики.
Например 
Цифровой способ задания ФАЛ реализуется посредством записи функции в виде совокупности рабочих, запрещённых и условных наборов аргументов. Условными наборами аргументовназываются наборы, на которых значение функции не определено или нас не интересует.При цифровом способе задания функции f, будут записаны в виде: 
Таблично-графический или координатный способ предусматривает задание ФАЛ ввиде координатных карт состояний, называемых картами Карно. При наличии n переменных карты Карно состоят из 
полей и представляют собой прямоугольные таблицы, на пересечении строки и столбца которых записывают значение функции при соответствующем наборе аргументов. При составлении карты необходимо следить, чтобы наборы аргументов в соседних полях (клетках) таблицы отличались только значением одной переменной.
|
|
|
Каждое поле карты соответствует одной строчке таблицы истинности, при табличном способе задания функции.
2. Полностью и не полностью определенные функции алгебры логики.
Функция является полностью заданной, если указаны ее значения для всех наборов. Сопоставляя каждому набору значение функции можно задать функцию с помощью таблицы, называемой таблицей истинности или таблицей соответствия.
Функция является не полностью заданной, если не указаны ее значения для некоторых наборов.
3. Функции алгебры логики одной переменной.
Рассмотрение понятия функции в алгебре логики (АЛ) можно начать с функций одной переменной. Нетрудно видеть, что таких функций можно построить четыре набора. Продолжая этот ряд получим таблицу, показывающую, что количество логических функций вычисляется как два в степени количества возможных входных наборов.
37.Одноразрядные сумматоры
Одноразрядные сумматоры (ОС) имеют три входа и обеспечивают сложение разрядов слагаемы ai и bi с переносом из предыдущего разряда pi-1 (таблица 4.1).
Таблица 4.1 – Схема переноса
В таблице скобками объединены строки, отличающиеся инвертированием аргументов. Видно, что при этом инвертируются и значения функций суммы и переноса. Обозначив вектор аргументов X, можно записать
Функции, обладающие указанным свойством, называются самодвойственными.
Дата добавления: 2018-02-15; просмотров: 1800; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!