Файл: Курс лекций по дисциплине Цифровая схемотехника для специальности.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 27.03.2024
Просмотров: 104
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Таким образом, равносильными являются формулы 1 и 2, 3 и 4. Равносильные формулы можно рассматривать как "имена"' одного и того же объекта, то есть они взаимозаменяемы. В математике это достаточно привычная ситуация, когда некоторое математическое выражение заменяется любым ему тождественным. В простейших случаях некоторое число можно заменить другим тождественным представлением. Например, дробь 1/2 можно заменить на 3/6, а единицу заменить на сумму квадратов синуса и косинуса некоторого угла. Таким образом, замена одной формулы на равносильную ей, ничего не меняет.
Кроме понятия равносильности формул, для определения отношения между различными формулами пользуются также такими понятиями как совместимость, несовместимости противоположность, логическое следование.
Две формулы называются совместимыми, если хотя бы при одной оценке miпеременных (наборе переменных), они одновременно являются истинными. В противном случае они несовместимые.
Две формулы называются противоположными (инверсными), если при любой оценке переменных miони принимают противоположные значения и в этом случае каждая из формул является отрицанием (инверсией) другой.
Формула В называется логическим следствием формулы А, если при любых оценках переменных, входящих в формулы, импликация А
В принимает только одно значение - истина.Всю совокупность формул логики высказываний можно разделить на три класса:
-
Нейтральные или выполнимые формулы. Формулы принимают как значение 1 (истинна), так и 0 (ложно). -
Тождественно-истинные формулы (тавтологии). Формулы принимают только значение 1 (истинно) независимо от логических значений входящих в них переменных. -
Тождественно-ложные формулы (противоречия или контрадикции). Формулы принимают только значение 0 (ложно) независимо от логических значений входящих в них переменных.
Замечание. Такая же классификация справедлива и для логических функций. Все введенные определения для логических формул справедливы для логических функций и наоборот.
Тождественно-истинные и тождественно-ложные формулы называют также невыполнимыми. Тождественно-истинные и тождественно-ложные формулы играют большую роль в математической логике. Эго связано с тем, что при любых наборах значений логических переменных они сохраняют постоянное значение истинности и, к тому же, являются взаимоинверсными. С помощью
тождественно-истинных формул, как правило, записываются основные законы математической логики.
Тема 1.5 Законы алгебры логики
-
Законы алгебры логики
Как в любой математической дисциплине, в математической логике вводится начальная система аксиом, которой подчиняются все вводимые в ней операции. Такие системы аксиом могут быть различны. Одной из самых простых и естественных систем аксиом в математической логике может быть принята система аксиом, определенная действиями основных логических операций.
Все преобразования логических функций производятся формально но правилам вывода: правилу подстановки и правилу заключения.
Правило подстановки: Пусть F - истинная формула (тавтология), содержащая переменную А. Тогда, заменив всюду в формуле F букву А другой формулой Ф, получим новую, также истинную, формулу.
Из этого правила следует, что если в истинной формуле F можно выделить какую-либо подформулу, которая может быть заменена другим тождественным выражением, то, сделав такую замену, получим новую истинную формулу.
Правило заключения: Если F и F
Ф истинные формулы, то и Ф - истинная формула.Для того чтобы две логические формулы F1и F2были эквивалентными необходимо и достаточно, чтобы их эквиваленция F1
F2была истинной. Это как раз следует из правила заключения, если вспомнить, что эквиваленция есть двойная импликация, то есть F1
F2 =(F1 F2 )( F2 F1)Из таблицы истинности. Ранее рассмотренного примера следует
, что формулы
эквивалентны. Тогда их эквиваленция 
очевидно тождественно-истинна.  | |||||
| А | В |  |  |  |  |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
. Смысл этой эквиваленции состоит в том что, доказав утверждение: «Из А следуем В» можно доказать утверждение: «Из отрицания В следует отрицание А». Приведенная эквивалентность, как и в классической логике называется законом контрапозиции. Импликация
является контрапозицией импликации 
. Эти две формулы в рассуждениях заменяют друг друга. На использовании этой эквивалентности основывается математический метод доказательства от противного.Из совпадения таблиц истинности формул
, следует, что эквиваленция
есть тавтология.  | |||
| В | | |  |
| 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 |
Таким образом, сказать "Из А следует В" - все равно, что сказать "Не А или В". Эквивалентность
называется законом инфолюции для импликации.Очевидно, множество равносильных формул бесконечно. Приведем наиболее важные равносильные формулы, которые используются при преобразованиях формул и которые отражают основные закономерности классической логики. Они называются основными законами алгебры логики.Эти законы, как увидим, аналогичны законам, характеризующим операции над множествами. (Здесь символ = используется для обозначения равносильных формул, то есть формул, которые при одинаковых логических значениях, входящих в них логических переменных, принимают одинаковые логические значения). Если взять любую из этих формул, то эквиваленция левой и правой частей формулы будет тавтологией.
Так как возможно представление этих законов через различные базисы, то в дальнейшем будем представлять логические формулы через операции дизъюнкции, конъюнкции и отрицания, то есть систему логических операции{
}Наиболее важными и специфическими из логических законов являются законы идемпотентности,которые исключают все коэффициенты и показатели степеней в логических формулах, содержащих одинаковые выражения.
