- •Логические основы работы эвм Методические указания к выполнению лабораторной работы для бакалаврантов 1-го курса всех направлений и форм обучения
- •Анатолий Николаевич Вишневский
- •Высказывание
- •Умозаключение
- •Алгебра логики
- •Логическое умножение (конъюнкция)
- •Логическое сложение (дизъюнкция)
- •Логическое отрицание (инверсия)
- •Логическое следование (импликация)
- •Логическое тождество (эквиваленция)
- •Операция «исключающее или»
- •Порядок выполнения логических операций в сложном логическом выражении
- •Логические выражения и таблицы истинности
- •Логические выражения
- •Равносильные логические выражения
- •Построение таблиц истинности для сложных выражений
- •Логические функции
- •Логическое следование (импликация)
- •Логическое равенство (эквивалентность)
- •Логические законы и правила преобразования логических выражений
- •Логические элементы
- •Простейший логический элемент не (инвертор)
- •Инверсия
- •Базовый набор операций
- •Логический элемент и (конъюнктор)
- •Логический элемент или (дизъюнктор)
- •Логический элемент «исключающее или»
- •Вопросы для самопроверки
- •Решение логических задач
- •Примеры решения задач
- •Задания
- •Библиографический список
- •Содержание
Логическое равенство (эквивалентность)
Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота речи «…тогда и только тогда, когда …».
Логическая операция эквивалентности «А тогда и только тогда, когда В» обозначается А≡В, А~В и выражается с помощью логической функции F10, которая задаётся соответствующей таблицей истинности (таблица 16).
Таблица 16 – Таблица истинности логической функции эквивалентности
-
A
B
F10 (А~В)
0
0
1
0
1
0
1
0
0
1
1
1
Составное высказывание, образованное с помощью логической операции эквивалентности, истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны.
Рассмотрим, например, два высказывания: А = «Компьютер может производить вычисления» и В = «Компьютер включён».
Составное высказывание, полученное с помощью операции эквивалентности, истинно, когда оба высказывания либо истинны, либо ложны:
«Компьютер может производить вычисления тогда и только тогда, когда компьютер включён».
«Компьютер не может производить вычисления тогда и только тогда, когда компьютер не включён».
Составное высказывание, полученное с помощью операции эквивалентности, ложно, когда одно высказывание истинно, а другое — ложно:
«Компьютер может производить вычисления тогда и только тогда, когда компьютер не включён».
«Компьютер не может производить вычисления тогда и только тогда, когда компьютер включён».
Логические законы и правила преобразования логических выражений
Законы логики отражают наиболее важные закономерности логического мышления. В алгебре высказываний законы логики записываются в виде формул, которые позволяют выполнять эквивалентные преобразования логических выражений.
Для логических величин обычно используются три операции:
Конъюнкция – логическое умножение (И) – and, &, Ʌ.
Дизъюнкция – логическое сложение (ИЛИ) – or, |, v.
Логическое отрицание (НЕ) – not, ¬.
Закон тождества
Всякое высказывание тождественно самому себе:
А = А
Закон непротиворечия
Высказывание не может быть одновременно истинным и ложным. Если высказывание А истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно:
А & Ā=0
Закон исключённого третьего
Высказывание может быть либо истинным, либо ложным – третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение «истина»:
А v Ā=1.
Закон двойного отрицания
Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание:
=А.
Законы де Моргана (общей инверсии)
= Ā & ;
= Ā .
Важное значение для выполнения преобразований логических выражений имеют законы алгебраических преобразований. Многие из них имеют аналоги в обычной алгебре.
Закон коммутативности (переместительный)
В обычной алгебре слагаемые и множители можно менять местами. В алгебре высказываний можно менять местами логические переменные при операциях логического умножения и логического сложения:
Логическое умножение А & В = В & А.
Логическое сложение A v В= A v В.
Закон ассоциативности (сочетательный)
Если в логическом выражении используются только операция логического умножения или только операция логического сложения, то можно пренебрегать скобками или произвольно их расставлять:
Логическое умножение Логическое сложение
(А & B) & С =A & (B & С). (A v В) v С = A v (B v С).
Закон дистрибутивности (распределительный)
В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые:
Дистрибутивность умножения относительно сложения |
Дистрибутивность сложения относительно умножения |
ab+ ас = а(b+с) — в алгебре (А & В) v (A & С) =А & (B v С) |
(A v В) & (A v С) = A v (B & С) |
Рассмотрим в качестве примера применения законов логики преобразование логического выражения. Пусть нам необходимо упростить логическое выражение (А & В) v (А & ).
Воспользуемся законом дистрибутивности и вынесем за скобки А:
(А & В) v (А & ) = А & (B v ).
По закону исключённого третьего В v =1, следовательно:
А&(В v )=А & 1=А.