1.
PROPOSITIONAL LOGIC
Proposition or statements, are also
known as simple sentences makes up the basic units for propositional logic.
When two or more simple sentences are related through connectives, it forms a
more complicated proposition called compound sentence.
A statement / propositions must always
be able to be validated as True (T) or False (F).
For example:
i) All fathers are men.
This statement is true because only man can be father.
ii) All men are father.
This statement is false because only those men who are
married and have kids are fathers. Single men are not father.
iii) I like Monday.
This sentence is neither true nor false as it does not include a fact.
The notion of ‘liking Monday’ is entirely depending on the particular
individual. Some may like it. Some may not.
Sentence which are neither true nor false (not containing any facts) are not propositions.
TRUTH VALUE
The truth value of a true proposition /
statement is always T. While the truth value of a false proposition / statement
is always F.
PROPOSITIONAL
VARIABLE
Propositional variables are used to
stand for unspecified statements. Means that each variable assigned may or may
not have connection between them.
For example:
A = She likes dancing.
B = She likes camping.
C = She likes outdoor activities.
Each variable is assigned to a
statement.
Now, let’s see how we can relate these
variables.
Conjunction [AND]
The conjunction
of two statements A and B is only true when both statements are true. And the
conjunction of the two statements is false if one of them is false.
Scenario:
You’re grading curriculum achievement for Grace. She will only get A for her
curriculum if she participated in more than 1 activity. So, the only way for
her to score A in her curriculum is:
|
A
|
B
|
(A & B)
|
|
T
T F F |
T
F T F |
T (She likes both dancing and camping.)
F (She likes dancing but not camping.) F (She doesn’t like dancing but fond of camping.) F (She doesn’t like both dancing and camping.) |
*The
conjunction of the two statements requires that she likes both activities
(dancing and camping) for the compound statement to be true (she score A for
her curriculum activities). The compound statement is false if one or both of
the simple sentences is false. Conjunction using the operator
‘&’ is the equivalent of joining statements together with ‘and’ in English.
Disjunction [OR]
The disjunction
of two statements is true even if only one of the two statements is true. It
will only be false if and only if both statements are false.
Scenario:
You’re trying to impress a girl by finding conversation topics you two have in
common. You’re a great dancer and camper having lots of experience in both
activities. You’ll succeed in getting her attention if:
|
A
|
B
|
(A & B)
|
|
T
T F F |
T
F T F |
T (She
likes both dancing and camping.)
F (She likes dancing but not camping.) F (She doesn’t like dancing but fond of camping.) F (She doesn’t like both dancing and camping.) |
*The
disjunction of two statements are true (you succeeded in finding a topic in
common) if both / one of the two statements is true (that she is either
interested in dancing or camping). You will only fail (disjunction is a false
statement) if she is not interested in both dancing and camping (both simple
sentence that makes up the disjunction are false). This is equivalent of joining statements together with the word ‘or’ in
English.
Material Implication[If… Then…]
With A as
antecedent, and B as consequence, statement / incident A catalyzes the event /
statement B which then determines the overall truth value of the statement. The
compound statement formed will only be false if A is true but B is false. The
statement will be true if both are true or false, and either A is false or B is
true.
Take:
A = It’s
cloudy outside.
B = I
bring umbrella.
For (A→B), I bring umbrella because it’s cloudy outside.
Because of the truth of the
statement A (It’s cloudy outside), that catalyses the event B (me bringing umbrella).
|
A
|
B
|
(A → B)
|
|
T
T F F |
T
F T F |
T (It’s
raining so I brought umbrella.)
F (It’s raining but I didn’t bring umbrella?) T (It’s not raining but I brought umbrella?) T (It’s not raining so I didn’t bring umbrella.) |
This is equivalent of joining
statements together with the word ‘if… then / so…’ in English.
Material Equivalence[If and only if]
Statements formed by material
equivalence are counted as true if both A and B have the same truth value, and
will be regarded as false if one of the statements is false. Hence:
|
A
|
B
|
(A ↔ B)
|
|
T
T F F |
T
F T F |
T
F F T |
Since this statement requires both
statements to have the same truth value, this is akin to joining statements
together with the word ‘… if and only if… ’ in English.
2. PROPOSITION EQUIVALENCE
Definition of :
·
Tautology
A compound
proposition that is always true.
·
Contradiction
A compound
proposition that is always false
·
Contingency
A compound
proposition that is neither a tautology nor a contradiction.
LOGICAL EQUIVALENCES
Compound
proposition that have the same logical content. Means, compound propositions p
and q are called logically equivalent if p ↔ q is a tautology.
Example of Tautology and Contradiction
|
p
|
q
|
p ∨ -p
|
p ∧ -p
|
|
T
|
T
|
T
|
F
|
|
F
|
F
|
T
|
F
|
*p ∨-q is always true
*p ∧-q is always false
Logical equivalences tables
|
Name
|
Equivalence
|
|
Identity Laws
|
p ∧ T ≡ p
p ∨ F ≡ p
|
|
Domination Laws
|
p ∨ T ≡ T
p ∧ F ≡ F
|
|
Idempotent Laws
|
p ∨ p ≡ p
p ∧ p ≡ p
|
|
Negation Laws
|
p ∨¬p ≡ T
p ∧¬p ≡ F
|
|
Double Negation Law
|
¬(¬p) ≡ p
|
|
Commutative Law
|
p ∨ q ≡ q ∨ p
p ∧ q ≡ q ∧ p
|
|
Absorption Law
|
p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p
|
|
De Morgan’s Laws
|
¬(p ∧ q) ≡¬p ∨¬q
¬(p ∨ q) ≡¬p ∧¬q
|
|
Associative Laws
|
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
|
|
Distributive laws
|
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
|
*T = Compound
proposition is always true
*F = Compound
proposition is always false
Logical Equivalences involving Conditional Statements
|
p → q ≡ ¬p ∨ q
|
|
p → q ≡ ¬q →¬p
|
|
p ∨ q ≡¬p → q
|
|
p ∧ q ≡¬(p →¬q)
|
|
¬(p → q) ≡ p ∧¬q
|
|
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
|
|
(p → r) ∨ (q → r) ≡ (p ∧ q) → r
|
|
(p → q) ∨ (p → r) ≡ p → (q ∨ r)
|
|
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
|
Logical Equivalences involving Bi-conditional Statements
|
p ↔ q ≡ ¬p ↔¬q
|
|
¬(p ↔ q) ≡ p
↔¬q
|
|
p ↔ q ≡
(p ∧ q) ∨ (¬p ∧¬q)
|
|
p ↔ q ≡ (p →
q) ∧ (q → p)
|
Logical Equivalent that are logical equivalents.
|
|
Double Negation
Law
¬ ( ¬ p ) ≡ p
|
p
|
-p
|
-(-p)
|
|
T
|
F
|
T
|
|
F
|
T
|
F
|
Commutative Law
p ∨ q ≡ q ∨ p
|
p
|
q
|
p ∨ q
|
q ∨ p
|
|
T
|
T
|
T
|
T
|
|
T
|
F
|
T
|
T
|
|
F
|
T
|
T
|
T
|
|
F
|
F
|
F
|
F
|
Associative Law
|
p
|
q
|
r
|
(p ∨ q)
|
(p ∨ q) ∨ r
|
(q ∨ r)
|
p ∨ (q ∨ r)
|
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
|
T
|
T
|
F
|
T
|
T
|
T
|
T
|
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
|
T
|
T
|
F
|
T
|
T
|
F
|
T
|
|
F
|
F
|
T
|
T
|
T
|
T
|
T
|
|
F
|
F
|
F
|
T
|
T
|
T
|
T
|
|
F
|
F
|
T
|
F
|
T
|
T
|
T
|
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
Logical Equivalent involving Conditional Statement that are logical
equivalents.
¬(p → q) ≡ p ∧¬q
|
p
|
q
|
¬(p → q)
|
¬q
|
p ∧¬q
|
|
T
|
T
|
F
|
F
|
F
|
|
T
|
F
|
T
|
T
|
T
|
|
F
|
T
|
F
|
F
|
F
|
|
F
|
F
|
F
|
T
|
F
|
|
(p→q) ∨ (p → r) ≡ p → (q ∨ r)
|
|
p
|
q
|
r
|
(p → q)
|
(p → r)
|
(p → q) ∨ (p → r)
|
(q ∨ r)
|
p → (q ∨ r)
|
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
|
T
|
T
|
F
|
T
|
F
|
T
|
T
|
T
|
|
T
|
F
|
T
|
F
|
T
|
T
|
T
|
T
|
|
T
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
|
F
|
T
|
T
|
T
|
T
|
T
|
T
|
T
|
|
F
|
T
|
F
|
T
|
T
|
T
|
T
|
T
|
|
F
|
F
|
T
|
T
|
T
|
T
|
T
|
T
|
|
F
|
F
|
F
|
T
|
T
|
T
|
F
|
T
|
Logical Equivalent involving Bi-conditional
p ↔ q ≡ (p → q) ∧ (q → p)
|
P
|
q
|
p ↔ q
|
p → q
|
q → p
|
(p → q) ∧ (q → p)
|
|
T
|
T
|
T
|
T
|
T
|
T
|
|
T
|
F
|
F
|
F
|
T
|
F
|
|
F
|
T
|
F
|
T
|
F
|
F
|
|
F
|
F
|
T
|
T
|
T
|
T
|
3. PREDICATES AND
QUANTIFIERS
PREDICATES
In some situations, a statement can be composed of two
parts, the variable and the predicates.
Take for an example.
Statement: The cost of an apple is
RM x.
(In this case, the cost of the
apple is a predicate, while x is the variable which represents the price.)
The above statement can also be
expressed as propositional function P at the value of x, which is P(x),
Where P[the cost of an apple] is affected by x[the price].
Note: A predicate is not a
proposition until it is bound by the variable. In this case, the predicate is
not a proposition until variable is declared on it. P itself is not a
proposition until it is bound by x, forming P(x).
Take P(x): x+5>10, it has no
value until x is substituted with a finite number or value.
When x is assigned a value, a
proposition is formed.
P (4) is false. [4+5<10]
P (5) is false. [5+5=10]
P (6) is true. [6+5>10]
P (7) is true. [7+5>10]
P (v) ∨ ¬P (0) is not a proposition as
the value of ‘v’ is not assigned.
However, P (3) ∨ ¬P (0) is a proposition which
is true.
QUANTIFIER
Universal Quantifier
∀ is used to
represent ‘for all’.
∀ x P (x) is
expressed as “For all (values of) x, P(x) is…” or x1 ∧ x2 ∧ x3 ∧ …… ∧ xn
The variable x is bound by the
universal quantifier that results in forming of a proposition.
Existential Quantifier
∃ is used to
represent “for some state / value of “
P (x) is true for some value of x
in the universal set.
∃ x P(x) is also
expressed as “There’s an x such that P(x),”, “For at least one value of x,
P(x)…”
UNIQUENESS QUANTIFIER
∃! Is used to
represent “for one and only one x”
P (x) is only true for one value of
x.
∃! x P (x) is also
expressed as “The is one and only one x such that P (x)”, “The is a unique x
such that P (x)…”.
