Преобразование логических выражений
ОДп..04.
Информатика и ИКТ
Автомеханик
УРОК № 8
Группа: АМ-2-19
Дата: 19.10.2020 г.
Преподаватель: Л.Н.Иванова
ТЕМА УРОКА:
ОСНОВЫ АЛГЕБРЫ ЛОГИКИ. ЛОГИЧЕСКИЕ ОПЕРАЦИИ. ЛОГИЧЕСКИЕ ФОРМУЛЫ. ЛОГИЧЕСКИЕ СХЕМЫ
Цель урока: познакомить с понятием основы алгебры логики, рассмотреть логические операции. Логические формулы. Логические схемы.
Алгебра логики
Алгебра логики - это математический аппарат, который позволяет производить алгебраические действия над логическими высказываниями. Алгебру логики также называют булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего основные ее методы в XIX веке.
Логическое высказывание - это утверждение, которое может быть либо истинным, либо ложным. Примеры высказываний: "Этот автомобиль черного цвета", "3 меньше 5". Противоречивое утверждение не может быть логическим высказыванием, например "Данное утверждение ложно". Логические высказывания обычно обозначаются латинскими буквами. В алгебре логики определены три основных логических операций с высказываниями и законы для выполнения этих операций. Действия с логическими высказываниями записываются в виде логических выражений.
Итак, для любого логического высказывания возможны два значения:
ИСТИНА - в некоторых языках программирования обозначается как True, в формулах и таблицах используется 1
|
|
|
ЛОЖЬ - в некоторых языках программирования обозначается как False, в формулах и таблицах используется 0
Любую логическую функцию можно представить в виде выражения или в виде таблицы истинности. В таблице истинности в столбцах указаны значения аргументов (переменных, операндов) и значение функции. Количество строк в таблице определяется количеством переменных и равно 2N, где N - количество переменных.
Основные логические операции:
1. Логическое отрицание (Инверсия). Обозначается AA, not A, НЕ А, в записи на черновике удобно использовать ¯¯¯¯AA¯
Выражение ¯¯¯¯AA¯ истинно тогда, когда AA ложно и ложно, когда AA истинно.
Таблица истинности операции логического отрицания:
| AA | ¯¯¯¯AA¯ |
| 0 | 1 |
| 1 | 0 |
2. Логическое умножение (Конъюнкция).
Обозначается AA ∧ BB , AA and BB, AA И BB, AA & BB, в записи на черновике удобно использовать A⋅BA⋅B
Выражение A⋅BA⋅B истинно тогда и только тогда, когда оба высказывания AA и BB истинны.
Таблица истинности операции логического умножения:
| AA | BB | A⋅BA⋅B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
3. Логическое сложение (Дизъюнкция).
Обозначается AA ∨ BB , AA or BB, AA ИЛИ BB, AA | BB, в записи на черновике удобно использовать A+BA+B
|
|
|
Выражение A+BA+B ложно тогда и только тогда, когда оба высказывания AA и BB ложны.
Таблица истинности операции логического сложения:
| AA | BB | A+BA+B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Остальные операции алгебры логики можно выразить основными операциями. Перечислим их:
4. Исключающее ИЛИ. Обозначается AA XOR BB , AA ⊕ BB
Выражение AA ⊕ BB истинно тогда и только тогда, когда высказывания AA и BB не равны.
Таблица истинности операции исключающего ИЛИ:
| AA | BB | AA ⊕ BB |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Исключающее ИЛИ можно выразить: ¯¯¯¯A⋅B+A⋅¯¯¯¯BA¯⋅B+A⋅B¯
5. Логическое следование (Импликация).
Обозначается AA → BB , AA ⇒ BB
Выражение AA → BB ложно тогда и только тогда, когда высказывание AA истинно, а BB ложно.
Таблица истинности операции логического следования:
| AA | BB | AA → BB |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Логическое следование можно выразить: ¯¯¯¯A+BA¯+B
6. Эквивалентность (Равносильность).
Обозначается AA → BB , AA ~ BB, AA ⇔ BB
Выражение AA ≡ BB истинно тогда и только тогда, когда высказывания AA и BB совпадают.
Таблица истинности операции эквивалентность:
|
|
|
| AA | BB | AA ≡ BB |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Эквивалентность можно выразить: (¯¯¯¯A+B)⋅(A+¯¯¯¯B)(A¯+B)⋅(A+B¯)
В логических выражениях порядок операций задается круглымим скобками. Если скобок нет, то порядок определяется приоритетом выполнения логических операций:
1. логическое отрицание
2. логическое умножение
3. логическое сложение
4. исключающее ИЛИ
5. логическое следование
6. эквивалентность
Законы алгебры логики
| Исключение констант | 1+A=11+A=1 0⋅A=00⋅A=0 0+A=A0+A=A 1⋅A=A1⋅A=A |
| Идемпотентность | A+A=AA+A=A A⋅A=AA⋅A=A |
| Закон исключения третьего | A+¯¯¯¯A=1A+A¯=1 |
| Закон непротиворечивости | A⋅¯¯¯¯A=0A⋅A¯=0 |
| Закон отрицания | ¯¯¯¯¯¯¯¯A=AA¯¯=A |
| Закон коммутативности | A+B=B+AA+B=B+A A⋅B=B⋅AA⋅B=B⋅A |
| Закон ассоциативности | A+B+C=A+(B+C)A+B+C=A+(B+C) A⋅B⋅C=A⋅(B⋅C)A⋅B⋅C=A⋅(B⋅C) |
| Закон дистрибутивности | A⋅(B+C)=A⋅B+A⋅CA⋅(B+C)=A⋅B+A⋅C A+(B⋅C)=(A+B)⋅(A+C)A+(B⋅C)=(A+B)⋅(A+C) |
| Правило де Моргана | ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯(A+B)=¯¯¯¯A⋅¯¯¯¯B(A+B)¯=A¯⋅B¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯(A⋅B)=¯¯¯¯A+¯¯¯¯B(A⋅B)¯=A¯+B¯ |
| Закон поглощения | A+A⋅B=AA+A⋅B=A A⋅(A+B)=AA⋅(A+B)=A |
| Закон склеивания | A⋅B+¯¯¯¯A⋅B=BA⋅B+A¯⋅B=B (A+B)⋅(¯¯¯¯A+B)=B(A+B)⋅(A¯+B)=B |
Законы алгебры можно доказать составив таблицу истинности.
|
|
|
Преобразование логических выражений
Упрощение логического выражение - это преобразование с использованием законов алгебры логики, которое приводит к выражению с меньшим количеством операций логического сложения и умножения и без отрицания не элементарных формул.
Рассмотрим несколько примеров:
| 1. | ¯¯¯¯¯¯¯¯¯¯¯¯¯(x⋅¯¯¯x)⋅(y+¯¯¯y)=(x⋅x¯)¯⋅(y+y¯)= | первый множитель - по закону непротиворечивости, | ||
| =¯¯¯0⋅1=1⋅1=1=0¯⋅1=1⋅1=1 | а второй множитель по закону исключения третьего | |||
|
| ||||
| 2. | ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯(x+y)⋅(x⋅¯¯¯y)=(x+y)¯⋅(x⋅y¯)= | правило де Моргана | ||
| =¯¯¯x⋅¯¯¯y⋅(x⋅¯¯¯y)==x¯⋅y¯⋅(x⋅y¯)= | ассоциативный закон | |||
| =¯¯¯x⋅x⋅¯¯¯y⋅¯¯¯y==x¯⋅x⋅y¯⋅y¯= | закон непротиворечивости | |||
| =0⋅¯¯¯y⋅¯¯¯y=0=0⋅y¯⋅y¯=0 | ||||
|
| ||||
| 3. | Докажем закон склеивания преобразованием выражения | |||
| (x+y)⋅(¯¯¯x+y)=(x+y)⋅(x¯+y)= | закон дистрибутивности | |||
| =x⋅¯¯¯x+y⋅¯¯¯x+x⋅y+y⋅y==x⋅x¯+y⋅x¯+x⋅y+y⋅y= | закон дистрибутивности для второго и третьего слагаемых | |||
| =0+y⋅(¯¯¯x+x)+y==0+y⋅(x¯+x)+y= | исключение констант | |||
| =y⋅1+y=y=y⋅1+y=y | ||||
|
| ||||
| 4. | ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯(x⋅y+¯¯¯z)=(x⋅y+z¯)¯= | правило де Моргана | ||
| =¯¯¯¯¯¯¯¯¯¯¯¯¯¯(x⋅y)⋅¯¯¯¯¯¯z==(x⋅y)¯⋅z¯¯= | правило де Моргана и двойное отрицание | |||
| =(¯¯¯x+¯¯¯y)⋅z=(x¯+y¯)⋅z | ||||
|
 Мы поможем в написании ваших работ! | ||||