Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

A) элементтері болса 5 страница




Из особенностей логических переменных и аксиом вытекают некоторые закономерности, которые представляются как законы алгебры. Для булевой алгебры выявлены следующие соотношения, которые рассматриваются как законы.

1. Переместительный закон.

1.1. ; (2.1)

1.2. . (2.2)

2. Сочетательный закон.

2.1. ; (2.3)

2.2. . (2.4)

3. Распределительный закон.

3.1. ; (2.5)

3.2. . (2.6)

Обе формы первого и второго закона и первая форма третьего закона (2.1, 2.2, 2.3, 2.4, 2.5) очевидны и особого доказательства не требуют. Остановимся лишь на (2.6).

,

что и требовалось доказать. В процессе доказательства использовались закон (2.5) и 4-ая и 7-ая аксиомы.

4. Закон поглощения.

4.1 . (2.7)

Следствие: . (2.8)

4.2 . (2.9)

Следствие: . (2.10)

Доказательство (2.7):

.

Здесь содержится доказательство и для (2.9).

5. Закон склеивания.

5.1 ; (2.11)

5.2 . (2.12)

Доказательство (2.11):

.

Доказательство (2.12):

6. Закон обобщённого склеивания.

6.1 ; (2.13)

6.2 . (2.14)

Доказательство (2.13):

Доказательство (2.14).

Раскроем скобки сначала левой части равенства (2.14) а, затем, правой его части.

;

.

Результаты преобразований одинаковы, что подтверждает справедливость (2.14).

7. Закон без имени.

7.1 ; (2.15)

7.2 . (2.16)

 

Доказательство (2.15):

.

Доказательство (2.16).

Развернём с помощью действия обратного склеиванию (см. 2.11).

, тогда

.

8. Закон де Моргана.

8.1. ; (2.17)

8.2. . (2.18)

Доказательство (2.17) и (2.18) заключается в сравнивании табличных форм левых и правых частей этих равенств. Данный закон имеет обобщённую форму.

8.3. (2.19)

Равенство (2.19) означает следующее. Отрицание функции равно самой функции с отрицанием переменных. Порядок выполнения операций сохраняется, а сами операции меняются с «И» на «ИЛИ» и с «ИЛИ» на «И».

 

Пример 2.1.1.

.

Чтобы сохранить при преобразовании порядок выполнения операций в правой части равенства использовались скобки.

Функция называется двойственной по отношению к функции , если образуется из путем замены операций «И» на операцию «ИЛИ» и операций «ИЛИ» на операцию «И». Функцию будем называть оригиналом. Порядок выполнения операций в двойственной функции должен сохраняться таким, каким он был в оригинале.

Пример 2.2.1.

Для недопущения возможных ошибок при написании двойственной формы функций, рекомендуется в оригинале предварительно расставить скобки, дополнительно учитывающие ранги операций. Затем, в полученной двойственной форме, скобки, не изменяющие порядок выполнения операций, удаляются.

Пример 2.2.2.

.

Расставляем дополнительные скобки, не меняющие формулу.

.

Делаем преобразование в двойственную форму.

.

Убираем ненужные скобки и получаем окончательный вид двойственной функции

.

Двойственные функции обладают следующими свойствами.

1. Если имеются две тождественно равные функции , то их двойственные формы также равны .

2. Если , то . Свойство подтверждается следующим образом.

; .

3. Если , то . Действительно, так как (согласно пятой аксиоме), то (согласно девятой аксиоме).

4. Если , то . Например, если , то .

Эти свойства бывают очень полезны в тех случаях, когда преобразование логических выражений в двойственном виде делать удобнее, чем в оригинале.

Примером двойственных функций можно считать все вторые формы законов булевой алгебры, если принять первые формы за оригиналы.

 

Форма логических функций представленных в базисе {И, ИЛИ, НЕ} называется нормальной.

Пример 2.3.1.

.

Очень важным является более узкий класс функций со структурой, образованной элементарными составляющими двух типов: элементарных конъюнкций и элементарных дизъюнкций.

Элементарной конъюнкцией k- того ранга или, иначе, минтермом k- того ранга называется логическое произведение k логических переменных, каждая из которых может быть представлена в прямом или инверсном виде.

 

Пример 2.3.2.

Замечание: конъюнкции не являются элементарными

Элементарной дизъюнкцией называется логическая сумма любого числа логических переменных, каждая из которых может быть представлена в прямом или инверсном виде.

 

Пример 2.3.3.

Замечание: дизъюнкции не являются элементарными.

Дизъюнкция любого числа элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).




Поделиться с друзьями:


Дата добавления: 2014-11-09; Просмотров: 373; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.042 сек.