Propositional Logic & Hardware

A proposition is a declarative sentence that is either true or false, but not both. They are often represented by variables, such as p, q, r, etc.

A simple proposition does not contain any other proposition as a part. Example: It is raining.

A compound proposition contains two or more propositions as its parts. Example: It is raining and the ground is wet.

An operator (connective) joins simple propositions to form compound propositions. Following are the types of connectives:

Conjunctive (AND) evaluates to true when both the propositions are true, otherwise it evaluates to false. It is represented by the symbol . (dot) or ^.
Disjunctive (OR) evaluates to true when at least one of the propositions is true, otherwise it evaluates to false. It is represented by the symbol + or ∨.
Negation (NOT) converts a true proposition to false and vice versa. It is represented by the symbols ~, ‘
Conditional (It Then or Implication) means that is one proposition is true then the other proposition is also true. It is represented by the symbol →.
Bi-conditional (If and only if or Equivalence) means either both the propositions are true or both are false. It is represented by the symbol ↔.

Well Formed Formulas are expressions that are syntactically correct and adhere to the rules of the algebraic system.

A truth value is the truth or falsity of a proposition. A truth table is a complete list of possible truth values of a proposition.

p	p’
0	1
1	0

Truth Table of NOT connective

p	q	pq
0	0	0
0	1	0
1	0	0
1	1	1

Truth Table of AND connective

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

Truth Table of OR connective

p	q	p→q
0	0	1
0	1	1
1	0	0
1	1	1

Truth Table of Implication

p	q	p↔q
0	0	1
0	1	0
1	0	0
1	1	1

Truth Table of Equivalence

A contingency is a formula that is neither a tautology nor a contradiction.

A tautology is a formula that is always true, regardless of the truth values of the variables within it.

A contradiction is a formula that is always false, regardless of truth values of the variables within it.

Consistent Statements refer to a set of formulas or propositions that can all be true simultaneously. Two statements are consistent if and only if their conjunction is not a contradiction.

The converse of p→q is q→p.
The inverse of p→q is p’→q’.
The contrapositive of p→q is q’→p’.

Equivalence Laws

Properties of 0
0 + p = p
0 . p = 0
Properties of 1
1 + p = 1
1 . p = p
Absorption Laws
p + pq = p
p . (p + q) = p
Involution
(p’)’ = p
Idempotence Laws
p + p = p
p . p = p
Complementarity Laws
p + p’ = 1
p . p’ = 0
Commutative Laws
p + q = q + p
p . q = q . p
Associative Laws
(p + q) + r = p + (q + r)
(p . q) . r = p . (q . r)
Distributive Laws
p . (q + r) = pq + pr
p + qr = (p + q)(p + r)
p + p’q = p + q
De Morgan’s Laws
(p + q)’ = p’ . q’
(pq)’ = p’ + q’
Conditional Elimination
p→q = p’ + q
Bi-conditional Elimination
p↔q = (p→q)(q→p)
XOR Elimination
p⊕q = pq’ + p’q
Transposition
p→q = q’→p’

A syllogism is a form of logical reasoning where a conclusion is drawn from two given or assumed propositions (premises). The propositions used to draw conclusion are called premises.

Modus Ponens

Modus ponens is a fundamental rule of inference in logic that allows one to derive a conclusion from a conditional statement and its antecedent.
The rule states that: If p→q and p is true, then q must also be true.
Algebraic Method to infer q from premises p and p→q
[p.(p→q)]→q
= [p(p’ + q)]→q
= (pq)→q
= (pq)’ + q
= p’ + q’ + q
= p’ + 1
= 1

Chain Rule

The Chain Rule allows us to infer a direct relationship between two variables from the given two implications. It states that if p→q and q→r, then p→r.
[(p→q)(q→r)]→(p→r)
= [(p’ + q)(q’ + r)]→(p’ + r)
= [(p’ + q)(q’ + r)]’ + (p’ + r)
= (p’ + q)’ + (q’ + r)’ + (p’ + r)
= pq’ + qr’ + p’ + r
= p’ + pq’ + r + qr’
= p’ + q’ + r + q
= p’ + r + 1
= 1

Logic gates are the basic building blocks of digital circuits. They are electronic devices that perform logical operations on one or more binary inputs to produce a single binary output.

There are three basic logic gates:
1. AND gate: outputs true only if all inputs are true.
2. OR gate: outputs true if at least one input is true.
3. NOT gate (Inverter): outputs the opposite (inverted) value of the input.

Derived logic gates:
1. NAND gate: outputs 0 only if all inputs are 1, otherwise, it outputs 1.
2. NOR gate: outputs 1 only if all inputs are 0, otherwise outputs 0.
3. XOR gate (Exclusive OR): outputs 1 when odd number of inputs are 1, otherwise outputs 0. Example: A ⊕ B.
4. XNOR gate (Exclusive NOR): outputs 1 when even number of inputs are 1, otherwise outputs 0. Example: A ⊙ B.

A	B	A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

XOR Truth Table

A	B	A ⊙ B
0	0	1
0	1	1
1	0	1
1	1	0

XNOR Truth Table

NAND and NOR gates are known as Universal Gates because they can be used to create any other type of logic gate, such as AND, OR, and NOT gates, and consequently, any digital circuit.

Design rule for NAND-to-NAND logic:
1. Derive simplified SOP (Sum of Products) of the given expression.
2. Draw the circuit diagram using AND, OR, NOT gates.
3. Replace all gates with NAND gates.

Design rule for NOR-to-NOR logic:
1. Derive simplified POS (Product of Sums) of the given expression.
2. Draw the circuit diagram using AND, OR, NOT gates.
3. Replace all gates with NOR gates.

Applications of Logic Gates

Half Adder
It is a logic circuit that adds two bits.
Equation:
SUM = A ⊕ B
CARRY = XY

A	B	CARRY	SUM
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

Full Adder
It is a logic circuit that adds three bits.
Equation
SUM = A ⊕ B ⊕ C
CARRY = AB + BC + AC

A	B	C	CARRY	SUM
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

Encoder

An encoder is a combinational circuit that converts information from one format to another, typically from a 2ⁿ input line to an n-bit binary output. The primary purpose is to reduce the number of wires needed to transmit information.