ISC Computer Science — Class XI Study Notes

Chapters: System of Numeration | Encodings | Propositional Logic |

Logic & Hardware

CHAPTER 1: SYSTEM OF NUMERATION

1.1 Why Number Systems Matter
A number system is a way of representing numbers using a fixed set of digits — called its base or
radix. The base tells you how many unique digits exist in that system.

System Base Digits Used

Decimal 10 0–9
Binary 2 0, 1
Octal 8 0–7
Hexadecimal 16 0–9, A–F (A=10 ... F=15)

Computers use binary because digital circuits only have two stable states: ON/OFF, High/Low
voltage. Octal and hexadecimal exist purely as shorthand for binary — they make long strings of
1s and 0s easier for humans to read, because 3 binary bits = 1 octal digit, and 4 binary bits = 1 hex
digit exactly.
Notation: A number's base is written as a subscript. (25)₁₀ means 25 in decimal. (11001)₂
means that binary number.

1.2 Decimal → Binary / Octal / Hex (Whole Numbers)

Method: Repeated Division
1. Divide the number by the target base.
2. Write down the remainder.
3. Take the quotient and divide again by the base.
4. Repeat until the quotient becomes 0.
5. Read the remainders from bottom to top — that's your answer (first remainder = Least
Significant Bit/Digit, last = Most Significant).
Worked Example — Decimal to Binary: Convert (85)₁₀
2 | 85 → remainder 1 (LSB)
2 | 42 → remainder 0
2 | 21 → remainder 1
2 | 10 → remainder 0
2 | 5 → remainder 1
2 | 2 → remainder 0
2 | 1 → remainder 1 (MSB)
0

Reading remainders bottom→top: (85)₁₀ = (1010101)₂

Same number to Octal: divide repeatedly by 8.
8 | 85 → remainder 5
8 | 10 → remainder 2
8 | 1 → remainder 1
0

(85)₁₀ = (125)₈
Same number to Hex: divide repeatedly by 16.
16 | 85 → remainder 5
16 | 5 → remainder 5
0

(85)₁₀ = (55)₁₆
Tip: Whatever the base, the process is identical — only the divisor changes.

1.3 Decimal → Binary/Octal/Hex (Fractional / Real Numbers)

Real numbers have an integral part and a fractional part — convert them separately, then join
with a point.
Integral part: repeated division (as above). Fractional part: repeated multiplication by the base;
take the integer part of each result as the next digit (read top to bottom this time), and carry the
leftover fraction into the next multiplication. Stop when the fraction becomes 0, or after 4 iterations
if it never terminates (this is the standard rule used in the textbook).
Worked Example: Convert (41.75)₁₀ to binary.
Integral part (41):
2 | 41 → 1
2 | 20 → 0
2 | 10 → 0
2 | 5 → 1
2 | 2 → 0
2 | 1 → 1
0

→ 101001
Fractional part (0.75):
0.75 × 2 = 1.50 → integer part 1
0.50 × 2 = 1.00 → integer part 1

Fraction became 0, so we stop. → .11

Answer: (41.75)₁₀ = (101001.11)₂
Worked Example (non-terminating case): Convert (0.95)₁₀ to binary.
0.95 × 2 = 1.90 → 1
0.90 × 2 = 1.80 → 1
0.80 × 2 = 1.60 → 1
0.60 × 2 = 1.20 → 1
0.20 × 2 = 0.40 → 0
0.40 × 2 = 0.80 → 0
0.80 × 2 = 1.60 → 1 (this repeats forever, so we stop after enough digits)

(0.95)₁₀ ≈ (0.1111001)₂
The same logic applies for converting to octal (multiply by 8) or hex (multiply by 16) — only the
multiplier changes.

1.4 Binary / Octal / Hex → Decimal

Method: Multiply each digit by (base)^position, where position counts outward from the decimal
point: position 0, 1, 2, 3... to the left (integer part) and −1, −2, −3... to the right (fractional part).
Add all products.
Worked Example: Convert (110101)₂ to decimal.

Digit 1 1 0 1 0 1
Position 2⁵ 2⁴ 2³ 2² 2¹ 2⁰
(power of 2)
Value 32 16 8 4 2 1

Sum = 32+16+0+4+0+1 = (53)₁₀

Worked Example with fraction: Convert (A4B.C2)₁₆ to decimal.
Integral part: A(10)×16² + 4×16¹ + B(11)×16⁰ = 2560+64+11 = 2635 Fractional part: C(12)×16⁻¹ +
2×16⁻² = 0.75 + 0.0078 = 0.7578
(A4B.C2)₁₆ = (2635.7578)₁₀
Same method works for octal — just replace the base with 8.

1.5 Shortcut Conversions (Binary ↔ Octal ↔ Hex)

These shortcuts exist because: 2³ = 8 (so 3 binary bits map exactly to 1 octal digit) and 2⁴ = 16 (so 4
binary bits map exactly to 1 hex digit).

Octal ↔ Binary (group in 3s)

Octal Binary (3-bit)
0 000
1 001
Octal Binary (3-bit)
2 010
3 011
4 100
5 101
6 110
7 111

Octal → Binary: replace each octal digit with its 3-bit binary code. Example: (312)₈ → 3=011,
1=001, 2=010 → (011 001 010)₂
Binary → Octal: group binary digits into 3s from the decimal point outward (right to left for
integer part, left to right for fractional part), padding with zeros if needed, then convert each
group. Example: (10101011110)₂ → group as 010 101 011 110 → 2 5 3 6 → (2536)₈

Hex ↔ Binary (group in 4s)

Hex Binary (4-bit) Hex Binary (4-bit)
0 0000 8 1000
1 0001 9 1001
2 0010 A(10) 1010
3 0011 B(11) 1011
4 0100 C(12) 1100
5 0101 D(13) 1101
6 0110 E(14) 1110
7 0111 F(15) 1111

Same idea: Hex→Binary, expand each digit to 4 bits. Binary→Hex, group into 4s (pad with zeros
at the outer ends if needed).

Octal ↔ Hex (always go via Binary — there's no direct shortcut)

Steps: Octal digit → 3-bit binary → regroup the whole binary string into 4-bit chunks → Hex digit.
Worked Example: Convert octal (342.41)₈ to hex.
1. Octal → binary (3-bit groups): 3=011, 4=100, 2=010 | 4=100, 1=001 → 011100010.100001
2. Regroup into 4-bit chunks (pad zeros at outer ends): 0000 1110 0010 . 1000 0100
3. Convert each 4-bit group to hex: 0=0, E=14, 2=2 | 8=8, 4=4
(342.41)₈ = (0E2.84)₁₆
1.6 Binary Arithmetic
Addition Rules
A B Sum Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
1+1+1 1 1

Example: (110010)₂ + (11011)₂

1 1 ← carry
110010
+ 11011
--------
1001101

Answer: (1001101)₂

Subtraction Rules
A B Result Borrow?
0 0 0 No
1 0 1 No
1 1 0 No
0 1 1 Yes (borrow 1 from
next higher digit; that
borrow adds 2 to the
current digit, since
base=2)

Example: Subtract (11011)₂ from (100100)₂ Work column by column from the right, borrowing as
needed (borrowing adds 2, since binary base = 2). Answer: (1001)₂

Multiplication Rules
Same as decimal — 0×0=0, 0×1=0, 1×0=0, 1×1=1. Multiply digit by digit to get partial products,
shift left for each subsequent digit, then add all partial products using binary addition rules.
Example: (1010)₂ × (101)₂ = (110010)₂
1.7 Octal Arithmetic
Addition: Add corresponding digits. If the sum ≥ 8, subtract 8 and carry 1 to the next column
(instead of subtracting 10 as in decimal).
Example: (6547)₈ + (5436)₈
 7+6=13 → 13−8=5, carry 1
 4+3+1=8 → 8−8=0, carry 1
 5+4+1=10 → 10−8=2, carry 1
 6+5+1=12 → 12−8=4, carry 1 Result: (14205)₈
Subtraction: If borrowing is needed, borrow adds 8 (not 10) to the digit, since octal's base is 8.
Multiplication (no direct table method taught):
1. Convert both octal numbers to decimal.
2. Multiply in decimal.
3. Convert the product back to octal (repeated division by 8).
Example: (75)₈ × (64)₈
 (75)₈ = 7×8+5 = 61; (64)₈ = 6×8+4 = 52
 61×52 = 3172
 Convert 3172 to octal: 3172÷8=396 r4, 396÷8=49 r4, 49÷8=6 r1, 6÷8=0 r6 → 6144 (75)₈ ×
(64)₈ = (6144)₈

1.8 Hexadecimal Arithmetic

Same logic as octal but the threshold is 16.
Addition: If sum ≥ 16, subtract 16 and carry 1. Example: (1B2C)₁₆ + (AB45)₁₆ = (C671)₁₆
Subtraction: Borrowing adds 16 to the digit. Example: (D8E7)₁₆ − (A6B4)₁₆ = (3233)₁₆
Multiplication: Convert both to decimal → multiply → convert product back to hex (repeated
division by 16).

CHAPTER 2: ENCODINGS
2.1 What Is Encoding?
Encoding = converting characters (letters, digits, symbols) into a specific binary format so a
computer can store, process, or transmit them. Since computers only understand 0s and 1s, every
character we type needs a numeric binary code behind it.
Why encoding matters:
  Keeps data safe/unreadable to unauthorized users during transmission
 Reduces file size for storage
 Organizes unstructured data
 Ensures compatibility across different systems/devices
 Improves speed of data transmission
Common encoding schemes: BCD, ASCII, ISCII, Unicode, BinHex, MIME. Manchester
Encoding specifically depicts ON/OFF (High/Low) signal states.

2.2 BCD — Binary Coded Decimal

Concept: Each decimal digit (0–9) is individually converted into its own 4-bit binary code — you
do NOT convert the whole number as one unit like normal binary conversion.
Also called the 8-4-2-1 code because the 4 bit positions represent weights 2³, 2², 2¹, 2⁰ = 8,4,2,1.

Decimal BCD
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001

Multi-digit numbers: convert each digit separately and concatenate. Example: (12)₁₀ → 1=0001,
2=0010 → BCD = 00010010
Important distinction: BCD ≠ pure binary. E.g., (12)₁₀ in pure binary is 1100, but in BCD it's
00010010 (each digit encoded separately).

BCD for Characters (with Zone bits)

Since 4-bit BCD can only represent 0–9, 2 extra zone bits are added to represent letters and special
characters too — giving a 6-bit code, which can also be expressed as an octal equivalent.

Character group Zone

A–I 11
J–R 10
Character group Zone
S–Z 01
1–9, 0 00

Worked Example: Represent the word "TEXT" in BCD. T = 010011, E = 110101, X = 010111, T
= 010011 → 010011 110101 010111 010011

2.3 ASCII — American Standard Code for Information

Interchange
The most widely used character encoding. Assigns a unique numeric value to every letter, digit, and
symbol.

ASCII-7 (7-bit code)

 Represents 128 (2⁷) characters (values 0–127)
 Structure: first 3 bits = zone, last 4 bits = digit
 Micro-computers actually store it in 8 bits (1 byte), padding with a leading 0

Character range Zone bits

0–9 011
A–O 100
P–Z 101

Worked Example: Represent "COMPUTER" in ASCII-7. C=1000011, O=1001111, M=1001101,

P=1010000, U=1010101, T=1010100, E=1000101, R=1010010

ASCII-8 (extended version)

 Represents 256 (2⁸) characters
 Zone is now 4 bits (not 3), digit is still 4 bits
 Note: ASCII-7 and ASCII-8 zone values are not identical even for the same character

Key ASCII value ranges to memorize

Range Meaning
0–31 Control characters (non-printable: newline, tab,
etc.)
32 Space
48–57 Digits 0–9
65–90 Uppercase A–Z
Range Meaning
97–122 Lowercase a–z
127 DEL (delete control character)

Handy fact: lowercase letters = uppercase value + 32 (e.g., 'A'=65, 'a'=97).

Limitations of ASCII
 Only 128 characters (7-bit) — not enough for global use
 Cannot represent accented characters (é, ñ, ü, ç)
 Cannot represent non-Latin scripts (Hindi, Chinese, Arabic, Japanese)
 Designed for American English only — not multilingual

2.4 ISCII / IISCI — Indian Script Code for Information

Interchange
 Developed in India (1986–1988) by Dept. of Electronics; adopted by Bureau of Indian
Standards in 1991
 An 8-bit encoding for Indian scripts: Devanagari, Bengali, Tamil, Telugu, etc.
 Indian scripts have an inherent vowel 'a' attached to each consonant; Matra signs are used
to modify/attach different vowel sounds
 The Halant sign ( ् ) removes the inherent vowel, used to combine consonants into conjuncts
(e.g., प् + ल + स = प्लस)

2.5 Unicode
Why it was needed: No single encoding system (like ASCII) could represent all the world's
languages. A global standard was needed so the same software/website could work across all
languages and platforms without altering the original data.
 Established: 1991, by a consortium in California ("The Unicode Consortium")
 Indian scripts (Devanagari, Bengali, Kannada, Malayalam, Oriya, Tamil, Telugu, etc.) were
added in version 3.0
 Assigns a unique code point to every character across nearly all languages/symbols

Advantages of Unicode
 Supports multiple languages in a single encoding system
 Much larger character set than ASCII
 Universal, platform-independent standard
  Supports special symbols: math symbols, currency signs, emojis, technical characters

Key facts
 The first 128 Unicode characters are identical to ASCII (ensures backward compatibility)
 Uses variable-width encoding formats: UTF-8, UTF-16, UTF-32
 Written as U+XXXX (hex code point)

Unicode ranges (memorize a few key ones)

Script Range
Basic Latin U+0000 – U+007F
Devanagari U+0900 – U+097F
Bengali U+0980 – U+09FF
Tamil U+0B80 – U+0BFF
Arabic U+0600 – U+06FF
Hiragana U+3040 – U+309F

ASCII vs Unicode — Comparison Table

ASCII Unicode
Supports only 128 characters Supports thousands of characters, nearly all
languages
Limited to English letters, digits, basic symbols Supports multilingual text: Hindi, Chinese,
Arabic, emojis
Uses 7 bits (usually stored in 1 byte) Uses variable encoding: UTF-8/16/32, needs
more bits

2.6 ASCII and Unicode in Java

 ASCII String in Java: a string containing only characters with values 0–127
 Unicode String in Java: Java internally uses Unicode by default, so it can natively handle
multilingual text, emojis, and regional scripts
 A character can be represented in Java in two ways:
 Unicode escape: char ch1 = '\u0041'; (represents 'A')

 ASCII code: char ch2 = 65; (also represents 'A')

 Since ASCII is a subset of Unicode, Java stores ASCII-only strings efficiently while still
maintaining full Unicode compatibility.
CHAPTER 3.1: PROPOSITIONAL LOGIC
3.1.1 What Is a Proposition?
A proposition is a sentence that can be concluded as either True or False (not both, not neither).

Statement Is it a proposition?
"Apples are red." Yes — True/False
"Where are you going?" No — a question, can't be True/False
"Sita is singing." Yes
"What is your name?" No

Questions, commands, and exclamations are never propositions.

Propositional Constant vs Variable

 Propositional constant: the sentential form of a statement itself, resulting in True or False
(e.g., "Today is Sunday" — this is a constant).
 Propositional variable: the symbolic letter (conventionally a–z) used to represent that
constant in shorthand. E.g., let a = "Today is Sunday". Now wherever 'a' appears in the
logic, it stands for that sentence.

Types of Propositions
 Simple proposition: a single, standalone sentence. E.g., "Milk is a liquid."
 Compound proposition: two or more simple propositions joined by a connective
(and/or/if-then/etc.). E.g., "Bengaluru is a green city AND it is situated in Karnataka" → (a
∧ b)

3.1.2 Well-Formed Formula (WFF)

A WFF is the symbolic/abbreviated representation of a propositional statement. Once you assign
letters to statements (a, b, c...), any valid combination using logical connectives — like (a ∧b),
(a∨b), (a→b) — is a WFF.

Statement WFF
You work hard. a
You will win the race. b
You work hard and you will win the race. a∧b
If you work hard then you will win the race. a→b
You will listen to a song or play music. a∨b
3.1.3 Truth Values and Truth Tables
Truth values = the True/False (or 1/0) outcome of a proposition. Truth table = a systematic
tabular listing of all possible combinations of truth values for the propositions involved, along with
the resulting conclusion after applying a connective.
For n propositions, a truth table has 2ⁿ rows (covering every possible True/False combination).

3.1.4 The Five Connectives — In Detail

1. Conjunction (AND) — symbol: ∧ or .
Combines two+ propositions. Result is True only if ALL are True.

a b a∧b
0 0 0
0 1 0
1 0 0
1 1 1

Real examples: "Anita's age is 12 years and she is minor." / "John is a rock singer and he has long
hair." (Note: "but" can also express conjunction.)

2. Disjunction (OR) — symbol: ∨ or +

Combines two+ propositions. Result is True if ANY (or all) are True; False only if all are False.

a b a∨b
0 0 0
0 1 1
1 0 1
1 1 1

Real examples: "I will be in my room or I will be reading the newspaper."

3. Negation (NOT) — symbol: ~ or '

Applied to a single proposition — reverses its truth value.

a ~a
1 0
0 1

Double negation: negating twice returns the original value: (a) = a Example: (0) = ~(1) = 0 ✓
(matches original)

4. Implication / Conditional — symbol: → or ⇒

Form: "if...then". a → b reads "a implies b" — if a is true, then b must be true.

a b a→b
0 0 1
0 1 1
1 0 0
1 1 1

Key rule to remember: the implication is False only when the antecedent (a) is True and the
consequent (b) is False. All other combinations are True.
Algebraic identity: a → b = a' + b (this can be verified with a truth table — both give
identical results).

5. Equivalence / Bi-conditional — symbol: ⇔

Form: "if and only if". True only when both propositions have the same truth value.

a b a⇔b
0 0 1
0 1 0
1 0 0
1 1 1

Algebraic identity: a ⇔ b = a'b' + ab

Summary Table
Connective Symbol Name
not ~ or ' Negation
and ∧ or . Conjunction
or ∨ or + Disjunction
if...then → or ⇒ Conditional/Implication
if and only if ⇔ Equivalence/Bi-conditional

3.1.5 Antecedent and Consequent

In a conditional a ⇒ b:
  a (before the arrow, tied to "if") = antecedent
 b (after the arrow, tied to "then") = consequent
Example: "If it is cold today then you cannot go out." → a = "It is cold today" (antecedent), b =
"You cannot go out" (consequent).

3.1.6 Converse, Inverse, Contrapositive

Given the original conditional p ⇒ q:

Name Formula How to get it

Converse q⇒p Swap antecedent and
consequent
Inverse p' ⇒ q' Negate both antecedent and
consequent (keep order)
Contrapositive q' ⇒ p' Swap AND negate both

Example: If p: "You play." q: "You will not go to the party."

 Original (p⇒q): "If you play then you will not go to the party."
 Converse (q⇒p): "If you will not go to the party then you play."
 Contrapositive (q'⇒p'): "If you will go to the party then you don't play."
Important exam fact: A conditional and its contrapositive are always logically equivalent (same
truth table) — this is a common thing to be asked to verify.

3.1.7 Tautology, Contradiction, Contingency

Construct the truth table for the compound expression, then look at the final output column only:

Type Output column pattern

Tautology ALL 1s (always True), regardless of input
Contradiction ALL 0s (always False), regardless of input
Contingency Mixed 0s and 1s (depends on input)

Worked Example (Tautology): Verify (a⇒~b)∨b

a b ~b a⇒~b (a⇒~b)∨b
0 0 1 1 1
0 1 0 1 1
1 0 1 1 1
1 1 0 0 1
All outputs = 1 → Tautology
Worked Example (Contradiction): a ∧ 0 — anything ANDed with 0 is always 0 →
Contradiction
Worked Example (Contingency): a ∧ (a∨b) gives outputs 0,0,1,1 (mixed) → Contingency

3.1.8 Deriving a Propositional Expression from a Real Situation

This is a frequently tested application question. Steps:
1. Identify the inputs (conditions) and assign each a letter.
2. Identify the output (decision/result).
3. Build a complete truth table (2ⁿ rows for n inputs), filling in the output for every
combination based on the situation's rules.
4. Write the expression using either:
(a) Sum of Products (SOP) — Disjunction of Conjunction terms:
 For each row where output = 1 (HIGH): write a conjunction (AND) term.
 If the input variable = 1, write it as-is; if = 0, write its negation.
 OR (∨) all these conjunction terms together.
(b) Product of Sums (POS) — Conjunction of Disjunction terms:
 For each row where output = 0 (LOW): write a disjunction (OR) term.
 If the input variable = 0, write it as-is; if = 1, write its negation.
 AND (∧) all these disjunction terms together.

Worked Example (SOP method)

Situation: A club selects members if: (graduate AND active in social service) OR
(graduate/undergraduate but won an award). Inputs: G=graduate, S=active in social service, A=won
award. Output X=selected.

G S A X Conjunction
term (only for
X=1)
0 0 0 0 —
0 0 1 1 G∧S∧A
0 1 0 0 —
0 1 1 1 ~G∧S∧A
1 0 0 0 —
1 0 1 1 G∧~S∧A
G S A X Conjunction
term (only for
X=1)
1 1 0 1 G∧S∧~A
1 1 1 1 G∧S∧A

Expression: (G∧S∧A) ∨ (G∧S∧A) ∨ (G∧S∧A) ∨ (G∧S∧~A) ∨ (G∧S∧A)

Worked Example (POS method)

Situation: A committee's decision is implemented only if (President AND (Secretary OR
Treasurer)) OR (all three agree). Inputs: P, S, T. Output X.
Take rows where X = 0, write disjunction terms (negate variables that are 1):

P S T X Disjunction term
(only for X=0)
0 0 0 0 P∨S∨T
0 0 1 0 P∨S∨~T
0 1 0 0 P∨~S∨T
0 1 1 0 P∨S∨T
1 0 0 0 ~P∨S∨T

Expression: (P∨S∨T) ∧ (P∨S∨T) ∧ (P∨S∨T) ∧ (P∨S∨T) ∧ (~P∨S∨T)

CHAPTER 3.2: LOGIC AND HARDWARE (BOOLEAN

ALGEBRA)
3.2.1 Historical Background
 1854 — George Boole discovered the link between Mathematics and Logic, developing
"Symbolic Logic" → became known as Boolean Algebra. Deals only with True/False (1/0).
 1938 — Claude Shannon applied Boolean algebra practically to electronic telephone
switching circuits, using relays with two states (On/Off). This is why Boolean algebra is also
called Switching Algebra. This was the bridge between abstract math and real computer
electronics.
Boolean Variable: like an algebraic variable but can ONLY hold 0 or 1 (never any other number)
— hence also called a binary valued variable.
3.2.2 The Three Logical Operators
1. Logical NOT (Complement)
Converts 0→1 and 1→0. Symbol: ' or overline (bar).

A A'
0 1
1 0

2. Logical OR (Logical Addition) — symbol +

 0+0=0, 0+1=1, 1+0=1, 1+1=1 (NOT 10 — this is logical, not arithmetic, addition)
 Output = 0 only when ALL inputs are 0.

3. Logical AND (Logical Multiplication) — symbol .

 0.0=0, 0.1=0, 1.0=0, 1.1=1
 Output = 1 only when ALL inputs are 1.
Boolean Expression: built from Boolean variables + these operators. Examples: A'+B, A+B.C,
(A+B).(A+C)

3.2.3 Boolean Postulates and Laws (MEMORIZE — frequently

tested)
1. Properties of 0 and 1
 A+1 = 1
 A.0 = 0
 A+0 = A
 A.1 = A

2. Complementary Laws
 A+A' = 1
 A.A' = 0

3. Idempotent Law
 A+A = A
 A.A = A
4. Involution Law (double complement)
 (A')' = A

5. Commutative Law
 A+B = B+A
 A.B = B.A

6. Distributive Law
 A(B+C) = A.B + A.C (this one also applies in ordinary math)
 A+BC = (A+B).(A+C) (this one is UNIQUE to Boolean algebra — doesn't hold in ordinary
math)

7. Associative Law
 A+(B+C) = (A+B)+C
 A(B.C) = (A.B)C

8. Absorption Law
 A+A.B = A
 A(A+B) = A
How to prove any of these: construct a truth table for LHS and RHS separately; if every row
matches, the law is proved (this is the standard exam method — "prove using truth table").

3.2.4 De Morgan's Theorem

Two of the most important laws — state that the complement of a sum equals the product of
complements, and vice versa.
 (A+B)' = A'.B'
 (A.B)' = A'+B'
Proof (for the first law) via truth table:

A B A+B (A+B)' A' B' A'.B'

0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0

Columns (A+B)' and A'.B' match exactly → proved.

Why this matters practically: De Morgan's theorem is the tool used to convert any Boolean
expression into a form usable by NAND-only or NOR-only circuits (see Universal Gates section
below).

3.2.5 Principle of Duality

You can derive a dual of any Boolean expression by simultaneously:
 Replacing every + with . and every . with +

 Replacing every 1 with 0 and every 0 with 1

 Keeping variables unchanged

The dual of a true Boolean postulate is also always true.

Original Dual
A+0=A A.1=A
A+A'=1 A.A'=0
A+1=1 A.0=0
A(A+B)=A A+AB=A
A+BC=(A+B)(A+C) A.(B+C)=AB+AC

3.2.6 Logic Gates

A logic gate is a physical/circuit implementation of a logical operation — takes one or more input
signals, produces one output signal.

Fundamental (Basic) Gates — these are independent, not built from

other gates
NOT Gate (Inverter): 1 input → complement output. Only gate that takes a single input (an
exception to the "2+ inputs" idea).

A A'
0 1
1 0

OR Gate: output = 1 if ANY input is 1; output = 0 only if ALL inputs are 0.

A B A+B
0 0 0
0 1 1
1 0 1
A B A+B
1 1 1

AND Gate: output = 1 only if ALL inputs are 1.

A B A.B
0 0 0
0 1 0
1 0 0
1 1 1

Derived Gates — built by combining two or more fundamental gates

NOR Gate = OR followed by NOT → complement of OR. Also called "complemented/inverted
OR gate."

A B (A+B)'
0 0 1
0 1 0
1 0 0
1 1 0

NAND Gate = AND followed by NOT → complement of AND. Also called

"complemented/inverted AND gate."

A B (A.B)'
0 0 1
0 1 1
1 0 1
1 1 0

XOR (Exclusive-OR) Gate: A⊕B = A'B + AB'. Output is HIGH (1) when the number of 1s in the
input is ODD; LOW (0) when EVEN.

A B A⊕B
0 0 0
0 1 1
1 0 1
1 1 0
XNOR (Exclusive-NOR) Gate: complement of XOR. Output is HIGH when number of 1s is
EVEN; LOW when ODD. (Opposite behavior of XOR.)

A B (A⊕B)'
0 0 1
0 1 0
1 0 0
1 1 1

Memory tip: XOR = "odd ones → 1"; XNOR = "even ones → 1" (this pattern extends to 3+ inputs
too).

3.2.7 Universal Logic Gates

NAND and NOR are called universal gates because any other logic gate (NOT, OR, AND, XOR,
XNOR) can be built using ONLY NAND gates, or ONLY NOR gates. This matters practically in
circuit manufacturing — using a single gate type simplifies fabrication.

Method to realize any gate using NAND/NOR only:

1. Take the target gate's Boolean expression.
2. Apply double complement over the whole expression (this doesn't change its value, since
(X')' = X).
3. Use De Morgan's theorem on the inner complement to flip the operator sign (+ ↔ .) —
this converts the expression into NAND form (all dots) or NOR form (all pluses).
4. Draw the circuit using only NAND (or only NOR) gates matching this converted expression.

Key derivations (NAND-only)

NOT using NAND: A' → (A.A)' — feed the same input to both pins of a NAND gate.
OR using NAND: A+B = [(A+B)']' = (A'.B')' — so: invert A, invert B (each via a NAND used as
NOT), then NAND those two results together.
AND using NAND: A.B = [(A.B)']' — take a NAND gate's output and invert it (using another
NAND as NOT).
NOR using NAND: (A+B)' = [(A'.B')']' — take the OR-via-NAND circuit's output and pass
through one more NAND-as-NOT.
XOR using NAND: A'B+AB' → double complement → [(A'B).(AB')]' — this needs a 4-gate
NAND construction (two NANDs for A'B and AB' individually, combined via a NAND).

Key derivations (NOR-only)

NOT using NOR: A' → (A+A)'
AND using NOR: A.B = [(A.B)']' = (A'+B')' — invert A, invert B, then NOR them.
OR using NOR: A+B = [(A+B)']' — take a NOR gate's output and invert it.
(Exam tip: always start by writing the target expression, apply double-complement, then De
Morgan's on the inner term — this 3-step pattern works for every gate conversion.)

3.2.8 Drawing Logic Circuits from Boolean Expressions

General method (example expression: A'B + AC):
1. Identify each term (product/AND group) in the expression: here, A'B and AC.
2. For each term, invert any variable that appears complemented (use a NOT gate), then feed
the (possibly inverted) variables into an AND gate to produce that term's output.
3. Once all term outputs are ready, feed them all into a final OR gate to get the complete
expression's output.
Worked Example: A.(B̄ +C̄ ) + A.B.C̄
1. B̄ +C̄ : invert B and C individually, OR them together.
2. A.(B̄ +C̄ ): AND that OR-output with A.
3. A.B.C̄ : invert C, AND with A and B.
4. Final: OR the two term outputs from steps 2 and 3.

Building circuits using ONLY universal gates (NAND or NOR)

1. Take the given expression.
2. Apply double complement over the whole thing.
3. Use De Morgan's theorem to convert inner + signs into . (for NAND form) or inner . signs
into + (for NOR form).
4. Draw using only that gate type.
Worked Example (NAND only): A'BC + A'B'C + AC
 Double complement: [A'BC + A'B'C + AC]''
 Apply De Morgan's on the inner complement to convert + into . between
terms: ‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾ (A'BC).(A'B'C).(AC)
 Now build using 3 NAND gates (one per term, each computing the term as a NAND-form
product), feeding into a final NAND gate.

3.2.9 Adders
An adder is a logic circuit that performs binary addition.
Half Adder
Adds exactly 2 binary digits. Has 2 outputs: Sum and Carry.

A B Carry Sum
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

Formulas:
 Sum = A ⊕ B (XOR gate)
 Carry = A . B (AND gate)
Limitation: cannot handle a third input (e.g., a carry-in from a previous addition) — this is why we
need the Full Adder.

Full Adder
Adds 3 binary digits (A, B, and an incoming carry C) — needed for adding multi-bit numbers
where carries propagate between columns.
Built from 2 Half Adders + 1 OR gate:
1. H.A.1 adds A and B → produces intermediate Sum (S1) and intermediate Carry (C1).
2. H.A.2 adds S1 and C (the third input) → produces the final Sum, and its own carry.
3. The carries from H.A.1 and H.A.2 are combined with an OR gate to get the final Carry.
Formulas:
 Sum = A ⊕ B ⊕ C
 Carry = AB + (A⊕B).C

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
QUICK SELF-CHECK QUESTIONS (test yourself before
the exam)
1. Convert (58823)₁₀ to hexadecimal. Convert (D97)₁₆ to binary.
2. Represent the word "SCIENCE" in ASCII-7 hex codes.
3. What's the difference between BCD and pure binary conversion of the same decimal
number? Show with (18)₁₀.
4. Write the converse, inverse, and contrapositive of: "If 17 is a prime number, then it has only
two factors."
5. Is (p∧~q)∨(p∧q) a tautology, contradiction, or contingency? Prove with a truth table.
6. Prove A+BC = (A+B).(A+C) using a truth table.
7. Draw a logic circuit for AB̄ C + AB(A+BC) using only NAND gates.
8. Design a full adder truth table and derive its Sum and Carry expressions from first principles
(using two half adders).
(Work these out fully on paper — the process, not just the final answer, is what scores marks in
ISC.)