Студопедия

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

КАТЕГОРИИ:

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






Dual functions






Definition: The dual of any formula S of Boolean algebra is the formula obtained by interchanging the operations ˅ and ˄, and interchanging elements 0 and 1 in the original statement S.

Ex: given equation:

(a ˄ 1)˄ (0˅ = 0 (True)

Its dual equation is: (a ˅ 0)˅ (1˄ = 1 (True)

Ex: given equation: a˅ ˄ b = a˅ ( ˄ b) = a˅ b; (True)

Its dual equation is: a˄ ( ˅ b) = a˄ b; (True)

H/a: write the dual of each Boolean equation:

1) a ˅ b) = b

2) (a˅ 1)(a˅ 0) = a

3) (a˅ b)(b˅ c) = ac˅ b

Note: the dual of every law of a Boolean algebra is also a law of this algebra.

Ex: ˅ = ; ˂ =˃ ˄ = ;

a˄ 1 = a ˂ =˃ a˅ 0 = a, etc.

Principle of duality: The dual of any theorem of a Boolean algebra is also a therem.

Note: a theorem is an equality of two formulas that can be obtained by applying some sequence of laws (axioms) of algebra.

Proof of the principle: Given any theorem and its proof (sequence of transformations by laws). Then the dual of the theorem can be proven in the same way by using the dual of each step in the original proof.

 

 

Ex:

original theorem ˂ =˃ dual theorem

˄ b = a˅ b Proof: a˅ ( ˄ b) = (a˅ )˄ (a˅ b) (step 1, Distributive law)   (a ˅ )=1 =˃ 1˄ (a˅ b) (step2, excluded middle)   1˄ (a˅ b) = (a˅ b) (step 3, law for a constant)   a˄ ( ˅ b)=a ˄ b Proof: a˄ ( ˅ b) = (a˄ )˅ (a˅ b) (step1, dual distributive law)   (a ˄ )=0 =˃ 0˅ (a˅ b) (step2, dual = contradiction law)   0˅ (a˅ b) = a ˅ b (step 3, dual law for a constant)

Some dual steps

 

 


Conclusion: Given a theorem of a Boolean algebra, one can write its dual theorem and be sure that it is correct. Meaning: In a new equality, the two formulas represent the same truth value.

 

H/a: Given a formula of 2-element Boolean algebra: ()˅ (.

a) Transform it into an equivalent formula by applying some sequence of laws.

b) Write the dual for the above obtained equation. Check if it is a correct equation by making the truth tables for both parts of the new equation.

If the new equation is incorrect check the correctness of the original equation.

 

Topic: Application of 2-valued Boolean algebra for design and analysis of logic circuits.

Logic circuits are structures that are built from elementary circuits called logic gates. Logic gates implement logic functions.

Example: Function OR and OR gate.

 


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

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