Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Булева алгебра






Логические функции, приведенные в табл. 2.1, можно рассматривать, как элементарные операции над одной или двумя двоичными переменными. Функционально полная система таких операций образует на множестве двузначных переменных алгебру логики. Таких алгебр можно представить столько же, сколько наберется подходящих функционально полных систем. Но наиболее распространена булева алгебра, в которой в качестве основных операций приняты конъюнкция х1х2 (И), дизъюнкция х12 (ИЛИ) и отрицание `х (НЕ). Часто конъюнкцию и дизъюнкцию называют соответственно логическим произведением и суммой, а отрицание – инверсией. Используются также и другие варианты обозначений: для конъюнкции х1Ù х2, для дизъюнкции х1Ú х2 и для отрицания х/. Чтобы избежать в сложных формулах лишних скобок, которые появляются при суперпозиции функций, установлен жесткий порядок выполнения операций – конъюнкция предшествует дизъюнкции. Свойства булевых операций И, ИЛИ, НЕ определяются таблицами соответствующих функций (см. табл. 2.1) и могут быть представлены в виде

0 1 1 0
х
0 0 0 0 1 1 1 0 1 1 1 1
х12
х1х2
 
0 0 1 1 2 0 1 1
х1х2
х1х2

 

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

Из приведенных определений булевых операций вытекают основные свойства булевой алгебры (табл. 2.3), которые можно доказывать методом совершенной индукции, т.е. проверкой для всех возможных комбинаций значений переменных. Любые свойства булевой алгебры можно также доказать аналитически без обращения к таблицам соответствия на основе первых пяти свойств, которые при этом роль аксиом.

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

Свойства булевой алгебры используются для преобразования и упрощения логических формул, а также доказательства теоретических положений. Коммутативность и ассоциативность позволяют выполнять операции И или ИЛИ, группируя переменные в любом порядке. Первая формула дистрибутивности указывает на допустимость вынесения общего множителя за скобки, как в обычной алгебре. Но вторая форма в обычной алгебре аналога не имеет, что является одним из основных отличий ее от алгебры логики. Свойства отрицания подчеркивают взаимодополнительную природу логических переменных. Повторы переменой и константы позволяют избавляться от постоянных слагаемых и множителей или при необходимости вводить их. Двойное отрицание не изменяет переменную, что можно рассматривать как пустую операцию. На основе идемпотентности можно удалять повторяющиеся переменные, вследствие чего в булевой алгебре не имеют смысла показатели степени и числовые коэффициенты, что также существенно отличает ее от обычной алгебры. Законы де Моргана позволяют свести отрицание сложного выражения к отрицания отдельных переменных. Последние четыре свойства (склеивание, поглощение, замещение и выявление) полезны при различных преобразованиях и упрощениях булевых формул.

Приведенные в табл. 2.3 пары свойств характеризуются специфической симметрией, выражающей принцип дуальности алгебры логики. В каждой паре одна форма получается из другой взаимной заменой операций И и ИЛИ, а также констант 0 и 1. В связи с этим операции И и ИЛИ, как и константы 0 и 1, называются дуальными. Вообще замена в любой формуле алгебры логики каждой операции и константы на дуальные приводит к дуальной формуле. Формула или функция, равносильная своей дуальной, называется автодуальной (как, например, двойное отрицание).

С принципом дуальности непосредственно связано обобщение законов де Моргана на любое число переменных. Если функция j*1, х2, …, хn) дуальная функции j (х1, х2, …, хn), то

`j (х1, х2, …, хn) = j*(`х1, `х2, …, `хn), (2.1)

откуда следует, что отрицание некоторой функции можно определить заменой в дуальной функции каждой переменной ее отрицанием. Пусть, например, задана функция y = x +`vz. Дуальная ей у* = х (v+`z) и, следовательно, `у =`х (`v + z).

Из выражения (2.1) также следует, что дуальная функция выражается как отрицание исходной функции, в которой каждая переменная замещена ее отрицанием:

j*1, х2, …, хn) =`j (`х1, `х2, …, `хn). (2.2)

Таблица 2.3

Свойство Первая форма Вторая форма
1. Коммутативность х+у=у+х ху=ух
2. Ассоциативность х+(y+z)=(x+y)+z x(yz)=(xy)z
3. Дистрибутивность x(y+z)=xy+xz x+yz=(x+y)(x+z)
4. Дополнение x+x=1 xx=0
5. Повтор переменной x+0=x x1=x
6. Повтор константы x+1=1 x0=0
7. Двойное отрицание X=x x=x
8. Идемпотентность x+x=x xx=x
9. Законы де Моргана x+y=xy xy=x+y
10. Склеивание xy+xy=x (x+y)(x+y)=x
11. Поглошение x+xy=x x(x+y)=x
12. Замещение x+xy=x+y x(x+y)=xy
13. Выявление xy+xz=xy+xz+yz (x+y)(x+z)= =(x+y)(x+z)(y+z)

 


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

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал