Студопедия

КАТЕГОРИИ:

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


Основные соотношения, правила и теоремы




 

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

X + = X
X + =
X + X =
X + =
X * =
X * = X
X * X = X
X * =

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

 

1. Свойства коммутативности операций :

1а. , 1б. .

2. Свойства ассоциативности операций :

2а. , 2б. .

3. Свойства дистрибутивности операций

:

3а. ,

3б. .

4. Свойства нуля и единицы:

4а. - определение единицы,

4б. - определение нуля,

4в. , 4 г. ,

4д. , 4е. ,

4ж. , 4з. .

5.Свойства идемпотентности операций :

5а. , 5б. .

6. Законы поглощения:

6а. , 6б. .

7. Законы Де Моргана:

7а. , 7б. .

 

Формулы Де Моргана применимы при любом числе аргументов. Они иллюстрируют глубокую взаимную симметрию операций И и ИЛИ: если операция И избирательно реагирует на совпадение прямых сигналов, то операция ИЛИ так же избирательно реагирует на совпадение их инверсий. Элемент ИЛИ прозрачен для любого сигнала, элемент И - для любой инверсии. Пользуясь формулами Де Моргана, можно легко переводить логические схемы из базиса НЕ, И, ИЛИ, в котором человеку привычнее всего мыслить и составлять исходные логические выражения, в инвертирующие базисы, которые эффективнее всего реализуются интегральной технологией. Можно сформулировать общую рекомендацию, полезную при переводе логической формулы из булева базиса в базис инверсных функций И-НЕ, ИЛИ-НЕ: если все выражение или какой-либо его фрагмент не оканчивается операцией инвертирования, то к нему нужно применить формулы Де Моргана. Тогда в схеме не будет лишних инверторов [4-8].

Совокупность конкретных значений логических переменных, от которых зависит булева функция, называется наборомлогическихпеременных. Если булева функция зависит, например, от трех переменных x2,x1 и x0, тогда x2 = 0, x1 = 1, x0 = 1 является набором. Наборы могут быть представлены различными способами. Тот же набор можно представить как 0,1,1 или просто 011. Рассматривая последнее представление как двоичное число, можно записать его в виде десятичного эквивалента 3 = 0.22+1.21+1.20. Отсюда видно, что логическим переменным, как и разрядам двоичного числа, можно условно присвоить “веса”: для x0 вес будет 20 = 1, для x1 - 21 = 2, для x2 - 22 = 4 и т.д. Именно поэтому логические переменные удобно обозначать индексированными буквами, начиная с индекса 0 для младшей переменной, 1 для следующей переменной и т.д. до индекса n-1, если функция зависит от n переменных. При таком обозначении индекс переменной совпадает с показателем степени основания двоичной системы счисления, т.е. характеризует вес переменной. Так для переменной x5 вес будет равен 25 = 32.

Если функция алгебры логики зависит от n переменных, то всего для них существует 2n наборов, так как добавление одной переменной увеличивает число наборов в два раза. Одна переменная имеет два набора: 0 и 1, две переменные - четыре: 0 = 00, 1= 01, 2 =10, 3 = 11 и т.д. Десятичный эквивалент набора логических переменных называется номеромнабора. Наборы можно рассматривать как двоичныевекторы Хi, где i- номер набора, однако надо помнить, что они не являются векторами в классическом смысле, так как над ними нельзя выполнять векторные операции. Число переменных, имеющих в наборе значение 1, называется весом набора (не нужно путать с двоичным весом переменных). Вес набора удобно изображать римскими цифрами, так для n = 3 имеем: набор 000 с весом 0; наборы 001, 010, 100 с весом I; наборы 011, 101, 110 с весом II и набор 111 с весом III [2,3].

Логическое произведение любого числа переменных из конечного набора n переменных называется элементарным, когда сомножителями в нем являются либо переменные, либо их отрицания. Количество сомножителей в элементарном произведении называется его рангом r. Так для x321x0 r = 4, а для x30 r = 2. Логическое произведение, являющееся функцией всех n переменных, называется конституентой единицы (составляющей единицы). Для n переменных существует 2n конституент единицы, причем на данном конкретном наборе лишь одна конституента единицы будет равна 1, все другие будут равны 0.

Два элементарных произведения одинакового ранга r называются соседними, если они являются функциями одних и тех же переменных и отличаются только знаком инверсии лишь у одной переменной. Например, x210 и x21x0 являются соседними, а x210 и 21x0 нет.

Логическая сумма любого числа переменных из конечного набора n переменных называется элементарной, когда слагаемыми в ней являются либо переменные, либо их отрицания. Например, сумма 3+x2+x1+0 является элементарной, а 3x2+x0; 3+ +x0 и x3++0 нет.

Количество слагаемых в элементарной сумме называется ее рангом r. Так для 3+x2+x1+0 r = 4, а для x3+0 r = 2. Логическая сумма, являющаяся функцией всех n переменных, называется конституентой нуля (составляющей нуля). Смысл этого термина будет пояснен позже. Для n переменных существует 2n конституент нуля, причем на данном конкретном наборе лишь одна конституента нуля будет равна 0, все остальные будут равны 1.

Две элементарные суммы одинакового ранга r называются соседними, если они являются функциями одних и тех же переменных и отличаются только знаком инверсии лишь у одной переменной [7,9].

 


Поделиться:

Дата добавления: 2015-08-05; просмотров: 118; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты