ISC Computer Science - Propositional Logic
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.
Equivalence Laws
Properties of 0
0 + p = p
0 . p = 0
0 + p = p
0 . p = 0
Properties of 1
1 + p = 1
1 . p = p
1 + p = 1
1 . p = p
Absorption Law
p + pq = p
p + (p + q) = p
p + pq = p
p + (p + q) = p
Involution
~(~p) = p
~(~p) = p
Idempotence Law
p + p = p
p . p = p
p + p = p
p . p = p
Complementarity Law
p + ~p = 1
p . ~p = 0
p + ~p = 1
p . ~p = 0
Commutative Law
p + q = q + p
p . q = q . p
p + q = q + p
p . q = q . p
Associative Law
(p + q) + r = p + (q + r)
(p . q) . r = p . (q . r)
(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
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
~(p + q) = ~p . ~q
~(p . q) = ~p + ~q
Conditional Elimination
p ⇒ q = ~p + q
p ⇒ q = ~p + q
Bi-conditional Elimination
p ⇔ q = (p ⇒ q) . (q ⇒ p)
p ⇔ q = (p ⇒ q) . (q ⇒ p)
Transposition
p ⇒ q = ~q ⇒ ~p
p ⇒ q = ~q ⇒ ~p
SAME FEELING U CAN ALSO VISIT ROHINI TUTORIALS
ReplyDeleteCONTACT NUMBER : 8333826874
VERY LOW FEE WITH PERFECT GUIDANCE FOR ISC
10 YEARS OF TEACHING EXPERIENCE FOR ISC