Logic Lecture 4 Flashcards
What are the basic axioms of Boolean algebra?
Commutativity, Idempotence, Associativity, Complement, Distributivity, De Morgan’s laws, Domination, and Involution.
What is the commutativity property in Boolean algebra?
φ ∨ ψ ≡ ψ ∨ φ and φ ∧ ψ ≡ ψ ∧ φ.
What is the idempotence property in Boolean algebra?
φ ∨ φ ≡ φ and φ ∧ φ ≡ φ.
What is the associativity property in Boolean algebra?
φ ∨ (ψ ∨ χ) ≡ (φ ∨ ψ) ∨ χ and φ ∧ (ψ ∧ χ) ≡ (φ ∧ ψ) ∧ χ.
What is the complement property in Boolean algebra?
φ ∨ ¬φ ≡ > and φ ∧ ¬φ ≡ ⊥.
What is the distributivity property in Boolean algebra?
φ ∨ (ψ ∧ χ) ≡ (φ ∨ ψ) ∧ (φ ∨ χ) and φ ∧ (ψ ∨ χ) ≡ (φ ∧ ψ) ∨ (φ ∧ χ).
What are De Morgan’s laws?
¬(φ ∨ ψ) ≡ ¬φ ∧ ¬ψ and ¬(φ ∧ ψ) ≡ ¬φ ∨ ¬ψ.
What is the domination property in Boolean algebra?
φ ∨ ⊥ ≡ φ, φ ∨ > ≡ >, φ ∧ > ≡ φ, φ ∧ ⊥ ≡ ⊥.
What is the involution property in Boolean algebra?
¬¬φ ≡ φ.
What does it mean for Boolean algebra to be sound?
Its axioms only equate semantically equivalent formulas.
What does it mean for Boolean algebra to be complete?
All valid equations between formulas can be derived using the axioms.
What does it mean for Boolean algebra to be irredundant?
No axiom can be derived from the others.
What is an equivalence relation?
A binary relation that is reflexive, symmetric, and transitive.
What is the correspondence between Boolean algebra and set theory?
Logical operations correspond to set operations: ∨ → ∪ (union), ∧ → ∩ (intersection), ¬ → ′ (complement).
What are the basic set theory operations corresponding to Boolean algebra?
Union (∪), intersection (∩), and complement (′).
What is an example of a set equation corresponding to a Boolean equivalence?
(A′ ∪ B) ∩ (A ∪ B′) = (A ∩ B) ∪ (A′ ∩ B′) corresponds to (¬φ ∨ ψ) ∧ (φ ∨ ¬ψ) ≡ (φ ∧ ψ) ∨ (¬φ ∧ ¬ψ).
What are equivalence classes of formulas?
Sets of formulas that are semantically equivalent.
What are the four equivalence classes for one variable p?
> , ⊥, p, and ¬p.
How many equivalence classes exist for two variables?
16 equivalence classes.
What is the general formula for the number of equivalence classes for n variables?
2^(2^n).
What is a Boolean function?
A function mapping tuples of truth values (0 or 1) to truth values.
What are common representations of Boolean functions?
Truth tables, logical formulas, logic circuits, and binary decision diagrams.
What are the three basic logic gates?
AND, OR, and NOT.
What does an AND gate represent?
Logical conjunction (∧).
What does an OR gate represent?
Logical disjunction (∨).
What does a NOT gate represent?
Logical negation (¬).
What is a half adder?
A logic circuit that adds two bits and outputs a sum and carry bit.
What is a full adder?
A logic circuit that adds three bits (two input bits and a carry bit) and outputs a sum and a carry.
What is the sum bit formula in a half adder?
s0 = x0 ⊕ y0.
What is the carry bit formula in a half adder?
c1 = x0 ∧ y0.
