Propositional Logic and Hardware

Propositional Logic

Logic is a formal method of reasoning.

A proposition is an elementary atomic sentence that may either be true or false but may take no other value.

A simple proposition is one that does not contain any other proposition as a part.

A compound proposition is one with two or more simple propositions as parts.

An operator or connective joins simple propositions into compounds.

Following are the various types of connectives:

  1. Disjunctive (OR): It means at least one of the two arguments is true. OR is represented by + or ∨.
  2. Conjunctive (AND): It means that both the arguments are true. AND is represented by . or & or ∧.
  3. Conditional (Implication or If Then): It means that if one argument is true then other argument is true. Implication is represented by ⇒ or → or ⊃.
  4. Bi-conditional (Equivalence or If And Only If): It means that either both arguments are true or both are false. Equivalence is represented by ⇔ or ≡.
  5. Negation (NOT): Actually, it is an operator, and not a connective. It means that an argument is false. NOT is represented by ∼ or ‘ or ‾.

Propositions are also called as sentences or statements or formula or well-formed formula.

Truth value is defined as truth or falsity of a proposition.

A truth table is a complete list of all possible truth values of a proposition.

Truth Table for NOT

p ~p
0 1
1 0

Truth Table for OR

p q p + q
0 0 0
0 1 1
1 0 1
1 1 1

Truth Table for AND

p q p . q
0 0 0
0 1 0
1 0 0
1 1 1

Truth Table for Implication

p q p ⇒ q
0 0 1
0 1 1
1 0 0
1 1 1

Truth Table for Equivalence

p q p ⇔ q
0 0 1
0 1 0
1 0 0
1 1 1

Some Related Terms

Contingencies are the propositions that have some combination of 1s and 0s in their truth table column.

Tautologies are the propositions having nothing but 1s in their truth table column.

Contradictions are the propositions having nothing but 0s in their truth table column.

Two statements are consistent if and only if their conjunction is not a contradiction.

Converse of p ⇒ q is q ⇒ p.

Inverse of p ⇒ q is p’ ⇒ q’.

Contrapositive of p ⇒ q is q’ ⇒ p’.

The logical process of drawing conclusions from given propositions is called syllogism.

The propositions used to draw conclusion are called premises.

Modus Ponens is

p
p ⇒ q
------
q

Chain rule is

p ⇒ q
q ⇒ r
------
p ⇒ r

Equivalence Laws

Properties of 0
0 + p = p
0 . p = 0

Properties of 1
1 + p = 1
1 . p = p

Absorption Law
p + pq = p
p + (p + q) = p

Involution
~(~p) = p

Idempotence Law
p + p = p
p . p = p

Complementarity Law
p + ~p = 1
p . ~p = 0

Commutative Law
p + q = q + p
p . q = q . p

Associative Law
(p + q) + r = p + (q + r)
(p . q) . r = p . (q . r)

Distributive Law
p . (q + r) = (p . q) + (p . r)
p + (q . r) = (p + q) . (p + r)
p + ~pq = p + q

De Morgan’s Law
~(p + q) = ~p . ~q
~(p . q) = ~p + ~q

Conditional Elimination
p ⇒ q = ~p + q

Bi-conditional Elimination
p ⇔ q = (p ⇒ q) . (q ⇒ p)

Transposition
p ⇒ q = ~q ⇒ ~p

Logic Gates

A gate is an electronic circuit which operates on one or more signals to produce an output signal.

The three basic logic gates are:

  1. NOT gate (inverter)
  2. OR gate
  3. AND gate

An Inverter (NOT gate) is a gate with only one input signal and one output signal. The output state is always the opposite of the input state.

The OR gate has two or more input signals but only one output signal. If any one of the input signals is 1, the output signal is 1, otherwise the output is 0.

The AND gate two or more input signals but produce only one output signal. When all inputs are 1, then the output is one, otherwise the output is 0.

More Logic Gates

The NOR gate has two or more input signals but only one output signal. If all the inputs are 0s, then the output is 1, otherwise the output is 0.

The NAND gate has two or more input signals but only one output signal. If all the inputs are 1, then the output is 0, otherwise the output is 1.

The XOR (Exclusive OR) gate has two or more input signals but only one output signal. It produces output 1 for only those input combinations that have odd number of 1s.

The XNOR (Exclusive NOR) gate has two or more input signals but only one output signal. It produces output 1 when the input combination has even number of 1s.

NAND and NOR gates are known as universal gates because we can easily implement other switching functions (AND, OR, NOT) using these gates.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.