Page 71 - ComputerScience_Class_11

3.2.2 Types of Formulas
Here are the three types of formulas:
• Satisfiable Formula: A formula is satisfiable if there exists at least one assignment of truth values to its variables
that makes the formula true. In other words, a satisfiable formula can be true under some conditions. For example,
the formula (A∧B) is satisfiable because if both A and B are true, the formula will evaluate to true.
• Unsatisfiable Formula: A formula is unsatisfiable if no possible assignment of truth values makes it true. In this case,
the formula will always evaluate to false, regardless of the truth values assigned. An example of an unsatisfiable
formula is (A∧∼A), as A and ∼A cannot both be true at the same time.
• Valid Formula: A formula is valid if it is true for every possible assignment of truth values. This means that no matter
what truth values are assigned to the variables, the formula will always evaluate to true. For example, (A∨∼A) is
valid because, regardless of whether A is true or false, the formula will always be true.

3.3 CONNECTIVES
Now, we know that connectives or logical operators join two or more simple propositions to form a compound
proposition. There are mainly five connectives which are as follows:
• Negation (NOT): It inverts a single statement. It is also called a unary connective. If a proposition is true, negation
makes it false and vice versa. Negation is represented by ˜(tilde) or ‘ (apostrophe) or ̅ (bar). The truth table for
negation is given below, considering ‘a’ as a propositional variable:
a ∼a
0 1
1 0

 If a = “It is raining heavily” then ∼a = “It is not raining heavily.”
 If b = “Planet X is the ninth planet” then ∼b = “Planet X is not the ninth planet.”
• Conjunction (AND): It is a binary connective as it joins two or more simple propositions. It results in true if all
propositional variables are true. If any variable is false, the resulting output is false. A conjunction is represented by
a dot (.) or (∧). The truth table for conjunction using two variables ‘a’ and ‘b’ is given below:
a b a ∧ b
0 0 0
0 1 0
1 0 0
1 1 1
 If a = “10 is an even number.”
b = “10 is divisible by 5.”
Then, a ∧ b = “10 is an even number and 10 is divisible by 5.”
 If x = “Light is a form of energy.”
y = “Light travels in a straight line.”
Then, x ∧ y = “Light is a form of energy and light travels in a straight line.”
• Disjunction (OR): It is also a binary connective that results in true if any one proposition is true. The output is false
only when both propositions are false. A disjunction is represented by a plus (+) or (∨).
The truth table for disjunction using two variables ‘a’ and ‘b’ is given below:
a b a ∨ b
0 0 0
0 1 1
1 0 1
1 1 1

Propositional Logic, Hardware Implementation, Arithmetic Operations 69