ISC CLASS 11 COMPUTER SCIENCE NOTES
Propositional Logic and Logical Connectives
•propositional logic is a statement which is true or false
eg : Statement-A - I have a mercedes - can be true or false
eg : Statement-B - I scored full marks in exams - can be true or false
Where Statement-A and Statement-B are prepositional variables
•
There are logical relationships between them, using connectives like "and," "or," "not," and "if...then"
eg : The sun rises in the East and sets in the West - true
•
Two main types of propositions:
1-Atomic Propositions: A simple statement without logical connectives that cannot be broken down further.
eg : "I have a Mercedes."
2-Compound Propositions: A statement formed by combining atomic propositions using logical connectives like AND, OR, or NOT.
eg:"I have a Mercedes and I scored full marks in exams."
•
Non-Propositions:
Questions, commands, and opinions are not propositions because they don’t have a definite truth value or may vary depending on context:
eg : “What time is it?” (Question)
•
Logical connectives combine simple propositions into compound ones using a small set of connectives
| Connective Symbols | Words | Terms | Example |
|---|---|---|---|
| ∧ | AND | Conjunction | A ∧ B |
| ∨ | OR | Disjunction | A ∨ B |
| → | Implies | Implication | A → B |
| ↔ | If and only If | Biconditional | A ↔ B |
| ¬ | Not | Negation | ¬A |
- Negation (~): Reverses the truth value.
- Conjunction (∧): True only if both parts are true.
- Disjunction (∨): True if at least one part is true (includes the Exclusive OR / XOR, which is true only if one is true, but not both).
- Implication / Conditional (⇒): An "if-then" relationship.
- Equivalence / Biconditional (⇔): An "if and only if" relationship.
- Exclusive Or p⊕q
Negation or NOT(~)
- Negation is a unary operation (operating on a single input variable) used in Boolean algebra and logic.
- It is also known as the complement or the logical inversion
- It reverses or inverts the truth value of a statement. If an input is True (1), its negation becomes False (0); if it is False (0), its negation becomes True (1).
- Notations:In ISC Computer Science, negation is commonly represented as: ∼A or ¬A (Logical notation), A′ (Prime notation, heavily used in Boolean algebra simplification), A̅ (Bar notation)
Truth table
| Input (A) | Negation (∼A) |
|---|---|
| 0 | 1 |
| 1 | 0 |
Conjunction (AND)(∧):
- Conjunction is a binary logical operation that performs logical multiplication
- It combines two or more input propositions or Boolean variables.
- The output is True (1) only if all inputs are True (1).If even a single input is False (0), the entire conjunction evaluates to False (0).
- A ∧ B (Propositional/Logical notation)
- A · B or simply AB (Boolean algebra notation using a dot)
Truth table
| Input (A) | Input (B) | Conjunction (A ∧ B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Disjunction (OR)(∨):
- Disjunction is a binary logical operation that performs logical addition
- It combines two or more input propositions or Boolean variables.
- The output is True (1) if at least one input part is True (1). It is False (0) only when all individual inputs are False (0).
- A ∨ B (Propositional/Logical notation)
- A + B(Boolean algebra notation using a plus)
Truth table
| Input (A) | Input (B) | Disjunction (A ∨ B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Implication / Conditional (⇒)
- An implication (or conditional statement) is a compound logical statement formed by connecting two propositions where the truth of the second statement depends as a logical consequence of the first
- It expresses an "if-then" relationship
- A → B or A ⇒ B - read as "A implies B" or "If A, then B"
- An implication is false only when a true antecedent leads to a false consequent (T ⇒ F = F)
- eg : "If you study hard, you will pass the exam."
Truth table
| Input (A) | Input (B) | Implication (A → B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Equivalence / Biconditional / Double Implication(⇔)
- A biconditional statement (logical equivalence) is a compound proposition formed by combining two statements where each statement implies the other
- It expresses an "if and only if" (often abbreviated as iff) relationship.
- We can denote the same as A ⇔ B
- "A is equivalent to B" or "A if and only if B"
- eg : "You will pass the exam if and only if you score above 40 percent."
Truth table
| Input (A) | Input (B) | Equivalence (A ↔ B) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Converse
- The converse is a derived conditional statement obtained by swapping the hypothesis (antecedent) and the conclusion (consequent) of an original implication
- If you start with a base conditional statement "If p, then q" (p ⇒ q), its converse reverses the roles, resulting in "If q, then p" (q ⇒ p)
- eg : p="If I run" q="I may win" then converse will be I may win if i run
- P→Q is Q→P
- A converse statement is formed by exchanging the hypothesis and conclusion of a conditional statement while retaining the same meaning
Truth table
| Input (p) | Input (q) | Converse (q → p) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Inverse
- The inverse is a derived conditional statement formed by negating both the hypothesis (antecedent) and the conclusion (consequent) of an original implication.
- If you start with a base conditional statement "If p, then q" (p → q), its inverse states "If not p, then not q" (~p → ~q)
- eg : p="If I run" q="I may win" then inverse will be "If i dont run i may not win"
Truth table
| Input (p) | Input (q) | Inverse (~p → ~q) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Contrapositive
- The contrapositive is a derived conditional statement formed by both interchanging the hypothesis and conclusion and negating both of them
- If you start with an original conditional statement "If p, then q" (p → q), its contrapositive states "If not q, then not p" (~q → ~p)
- eg : p="If I run" q="I may win" then contrapositive will be "i may not win if i dont run"
Truth table
| Input (p) | Input (q) | Contrapositive (~q → ~p) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Explain Boolean Expression and Variables
- Boolean expression is an expression that produces a Boolean value when evaluated, i.e., it produces either a true value or a false value
Boolean Variable: A symbol (like X, Y, Z) that can store only two discrete values: 0 (False) or 1 (True) - P + Q = R is a Boolean expression in which P, Q, and R are Boolean variables that can only store two values: 0 and 1.
- we can say that statements using Boolean variables and operating on Boolean operations are Boolean Expressions
eg : A + B = True and A . B = True - Literal: A variable or its complement (e.g., X or X')
eg : boolean defaultStatus = true; //literal
boolean isAccountActive = defaultStatus //boolean variable - Operations: AND (. / Logical Multiplication): Returns 1 only if all inputs are 1. OR (+ / Logical Addition): Returns 1 if any input is 1. NOT (' / Complement): Inverts the input (0 -> 1, 1 -> 0)
Essential laws of boolean algebra
- Property of 0:
X . 0 = 0
X + 0 = X -
Property- of 1:
X + 1 = 1
X . 1 = X (Identity) -
Annulment / Identity:
X + 0 = X (Identity)
X . 1 = X - Identity Law
A variable combined with 0 or 1 via an operation retains its identity:
X + 0 = X
X . 1 = X - Idempotent Law
A variable operated with itself produces the same variable:
X + X = X
X . X = X - Complementarity (Complement) Law
A variable combined with its inverse:
X + X' = 1
X . X' = 0 - Involution (Double Negation) Law
A variable inverted twice returns to its original state:
(X')' = X
- Commutative Law
The order of variables does not affect the result:
X + Y = Y + X (OR form)
X . Y = Y . X (AND form) - Associative Law
The grouping of variables does not matter when operators are identical:
X + (Y + Z) = (X + Y) + Z
X . (Y . Z) = (X . Y) . Z - Distributive Law
Allows opening up or factoring expressions:
X . (Y + Z) = X . Y + X . Z
X + (Y . Z) = (X + Y) . (X + Z) - Absorption Law
Reduces complex expressions by absorbing redundant terms:
X + (X . Y) = X
X . (X + Y) = X - De Morgan's Laws (Crucial for ISC Exams)
De Morgan's theorems allow you to break complement bars over complex expressions by changing the operator (. becomes +, and + becomes .):
1. First Law (X . Y)' = X' + Y'
The complement of a product is equal to the sum of the individual complements
2. Second Law (X + Y)' = X' . Y'
The complement of a sum is equal to the product of the individual complements
Introduction to Logic Gates
- Logic gates are electronic circuits that operate on one or more binary input signals (0 and 1) to produce a single binary output signal.
- Role: They are the fundamental building blocks of all digital electronic circuits, microprocessors, and computer memory.
- Representation: Their behavior is mathematically described using Boolean algebra and visually represented using Truth Tables and Logic Symbols.
- Basic Logic Gates
Basic gates perform the primary logical operations: AND, OR, and NOT.
-
NOT Gate (Inverter)
Function: Inverts the input state. If the input is 0, the output is 1; if the input is 1, the output is 0.
It always has only one input and one output.
Boolean Expression: Y = X'
TRUTH TABLEInput (X) Output (Y) 0 1 1 0 -
AND Gate
Function: Performs logical multiplication. The output is 1 only if all inputs are 1. If any input is 0, the output is 0.
Boolean Expression: Y = A . B
Input A Input B Output (Y) 0 0 0 0 1 0 1 0 0 1 1 1 -
OR Gate
Function: Performs logical addition. The output is 1 if at least one input is 1. The output is 0 only when all inputs are 0.
Boolean Expression: Y = A + B
Input A Input B Output (Y) 0 0 0 0 1 1 1 0 1 1 1 1 -
XOR Gate or Exclusive OR Gate
- Its a special type of logic gate used in digital electronics to perform the exclusive OR operation
- This gate takes two inputs and produces an output depending on the combination of the two inputs applied.
- This logic gate produces a high or logic 1 output when both of the inputs are dissimilar, otherwise, it produces a logic 0 output
-
NAND Gate (Not-AND)
Function: An AND gate followed immediately by a NOT gate. The output is 0 only if all inputs are 1; otherwise, it is 1.
Boolean Expression: Y = (A . B)'
Input A Input B Output (Y) 0 0 1 0 1 1 1 0 1 1 1 0 -
NOR Gate (Not-OR)
Function: An OR gate followed immediately by a NOT gate. The output is 1 only if all inputs are 0; otherwise, it is 0.
Boolean Expression: Y = (A + B)'
Input A Input B Output (Y) 0 0 1 0 1 0 1 0 0 1 1 0 -
NAND GATE AS UNIVERSAL BUILDING BLOCK
-
NOR GATE AS UNIVERSAL BUILDING BLOCK
BUILDING NOT GATE FROM NOR GATE
- The output Equation of the the NOT gate is A̅ and the Output of the NOR gate is A + A i.e A̅
- We provide a common input on both input terminals
BUILDING OR GATE FROM NOR GATE
Half Adder
- A half adder is a basic combinational circuit that adds two single-bit binary inputs (A and B) to produce a SUM using an XOR gate and a CARRY using an AND gate
- Performs binary addition of two single-bit inputs, generating a SUM (A ⊕ B) and CARRY (A · B)
- Simple Design: A half adder has a simple circuit design that uses only two logic gates (XOR and AND), making it easy to implement and understand.
- Fast Operation: Since it contains only a few logic gates, it produces the Sum and Carry outputs with very little delay.
- Low Hardware Requirement: It requires fewer hardware components, reducing circuit complexity and implementation cost.
- No Carry Input: A half adder cannot accept a carry input from a previous stage, limiting its use in larger arithmetic operations.
- Limited Functionality: It can add only two single-bit binary numbers and cannot perform multi-bit addition by itself.
- Requires fers: For multi-bit binary addition, half adders must be combined with full adders to handle carry propagation.
- Binary Addition: It is used to add two single-bit binary numbers and generate the corresponding Sum and Carry outputs.
- Building Block for Full Adders: Half adders are commonly used as the basic building blocks in the design of full adders
- Digital Arithmetic Circuits: They are used in arithmetic units, calculators, processors, and other digital systems where simple binary addition is required.
Advantages Of Half Adder
Disadvantages Of Half Adder
Applications Of Half Adder
-
Full Adder
- a combinational circuit which is designed to add three binary digits and produces two outputs (sum and carry) is known as a full adder.
- a full adder circuit adds three binary digits, where two are the inputs and one is the carry forwarded from the previous addition
- the circuit of the full adder consists of one EX-OR gate, three AND gates and one OR gate
- Full adder takes three inputs namely A, B, and Cin Where, A and B are the two binary digits, and Cin is the carry bit from the previous stage of binary addition. The sum output of the full adder is obtained by XOR gate, the bits A, B, and Cin. While the carry output bit (Cout) is obtained using AND and OR operations.
Truth Table
ISC Curriculum Breakdown
1. Review of Java: Basics of object-oriented programming, primitives, wrapper classes, operators, and control structures.
2. User-Defined Methods: Parameters, return types, method overloading, and recursion.
3. Arrays: Single dimensional and double dimensional arrays, sorting, and searching techniques.
4. String Handling: Built-in string manipulation functions and character processing algorithms.
Sample Java Source Codes
Explore standard implementation algorithms, pattern printing codes, and array sorting programs tailored for ISC examinations.
Source code repositories and downloadable PDF notes will populate here dynamically.