Computing
Truth Values
SYMBOLIC LOGIC
Definition
An assertion is a statement. A proposition is a
statement which is either true or false. If a
proposition is true we assign the truth value
“TRUE” to it. If a proposition is false, we assign the
truth value “FALSE” to it. We will denote by “T” or
“1”, for the truth value TRUE and by “F" or “0” for
the truth value FALSE.
SYMBOLIC LOGIC
Examples
The following are examples of propositions:
1. 2 > 4
2. The billionth prime, when written in base 10,
ends in a 3.
3. All men are mortals.
4. 9 is a prime number.
SYMBOLIC LOGIC
Non-Examples
The following are non-examples of propositions:
1. x < y
2. Factor 𝑥 2 + 2𝑥 + 1.
3. 𝑥 = 10
4. How old are you?
SYMBOLIC LOGIC
*Decide whether the following are propositions or
not:
1. 23 = z
2. 10 – 7 = 3
3. 5 < 27
4. All women are mammals.
5. Where do you live?
SYMBOLIC LOGIC
Definition
A propositional variable, denoted by 𝑃, 𝑄, 𝑅 …
denotes an arbitrary proposition with an
unspecified truth value.
A propositional variable is a variable that
represents a proposition.
SYMBOLIC LOGIC
Do Worksheet 1
SYMBOLIC LOGIC
Definition
Given two propositional variables 𝑃 and 𝑄. These two
propositional variables maybe combined to form a
new one. These are combined using
the logical operators or logical connectives : “and”,
“or”or “not”.
SYMBOLIC LOGIC
These new proposition are:
1. (Conjunction of P and Q) P and Q, denoted by𝑃 ;𝑄 ٿ
2. (Disjunction of P and Q) P or Q, denoted by𝑃 ;𝑄 ڀ
3. (Negation of P) not P, denoted by ¬ 𝑃.
Truth Tables
𝑃 𝑄 𝑃𝑄ٿ 𝑃𝑄ڀ
1 1 1 1
𝑃 ¬𝑃
1 0 0 1
1 0 0 1 0 1
0 1 0 0 0 0
Note: Other books represent the negation of P as ~P.
SYMBOLIC LOGIC
Inclusive and exclusive disjunction:
1. Inclusive disjunction denoted by 𝑃 𝑄 ڀis True when either
or both of the disjuncts are True.
2. Exclusive disjuction denoted byP⋁Q is True when only one
of the disjuncts is true and the other is false.
Truth Table:
𝑃 𝑄 𝑃 𝑄ڀP⋁Q
1 1 1 0
1 0 1 1
0 1 1 1
0 0 0 0
SYMBOLIC LOGIC
Do Worksheet 2 & 3
SYMBOLIC LOGIC
Definition
The proposition “P implies Q”, denoted by 𝑃⟹Q is called an
implication.
The operand P is called the hypothesis, premise or antecedent
while the operand Q is called the conclusion or the
consequence
When the if-then sentence is true,
we say that the hypothesis is a
sufficient condition for the
conclusion.
The conclusion is then called a
necessary condition of that
hypothesis.
SYMBOLIC LOGIC
Definition
Given the implication 𝑃⟹Q , its converse is 𝑄⟹P, its inverse
is¬𝑃⟹¬Q, and its contrapositive is ¬𝑄⟹¬P .
The operand P is called the hypothesis, premise or antecedent
and the operand Q is called the conclusion or the consequence
𝑃 𝑄 𝑃⟹Q ¬𝑃⟹¬Q 𝑄⟹P ¬𝑄⟹¬P
0 0 1 0 1 1
0 1 1 0 0 1
1 0 0 1 1 0
1 1 1 0 1 1
SYMBOLIC LOGIC
Definition
A biconditional proposition is expressed linguistically by
preceding either component by ‘if and only if’.
The truth table for a biconditional propositional form,
symbolised by P ⟷ Q is shown below.
𝑃 𝑄 P⟷Q
0 0 1
0 1 0
1 0 0
1 1 1
SYMBOLIC LOGIC
Do Worksheet 4
SYMBOLIC LOGIC
Definition
A propositional form is an assertion which contains at least
one propositional variable and maybe generated by the
following rules:
1. A propositional variable standing alone is a propositional
form;
2. If P is a propositional form, then Qis also a propositional
form;
3. If P and Q are propositional forms, then 𝑃 𝑄 ڀ, 𝑃 𝑄 ٿ, 𝑃 ⟺ 𝑄
are propositional forms;
4. A string of symbols containing propositional variables,
connectives and parentheses is a propositional form if and
only if it can be obtained by infinitely many applications of
rules (1.); (2.) or (3.) above.
SYMBOLIC LOGIC
Definition
Let X be a set of propositions.
A truth assignment (to X) is a function : X → {true, false} that
assigns to each propositional variable a truth value. (A truth
assignment corresponds to one row of the truth table.
If a truth value of a compound proposition under truth
assignment is true, we say that satisfies P, otherwise we say
that falsifies P.
A tautology is a propositional form where every truth assignment
satisfies P, i.e. All entries of its truth table are true.
A contradiction or absurdity is a propositional form where every
truth assignment is false;
A contingency is a propositional form that is neither tautology nor
contradiction.
Examples:
P V P is a tautology.
P P is a contradiction.
For each of the following compound propositions determine if it is
a tautology, contradiction or contingency:
1. (p v q) p q
2. P v q v r v (p q r)
3. (p → q) (p v q)
Do Worksheet 5
SYMBOLIC LOGIC
Definition
A logically equivalentpropositional form have identical values
for each assignment of the truth values to their component
propositional variables.
We can denote the logical equivalent variables P and Q as:
𝑃 ⟺𝑄
or
𝑃 ≡𝑄
(𝑥 + 2)2 and 𝑥 2 + 4𝑥 + 4 are regarded as equivalent algebraic
expressions.
SYMBOLIC LOGIC
Example
Show that P ⟹ Q and ¬P ⋁ Q are logically equivalent
propositional forms.
𝑃 𝑄 P⟹Q ¬P ¬P ⋁ Q
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 1 0 1
P ⟹ Q and ¬P ⋁ Q are logically equivalent propositional forms.
SYMBOLIC LOGIC
Example
Given the propositional forms Q ⋁ ¬P, ¬Q ⟹ ¬P and ¬P ⋀ ¬Q,
between which pairs of these forms does the relation logical
equivalence exist?
𝑃 𝑄 ¬P ¬Q Q ⋁ ¬P ¬Q ⟹ ¬P ¬P ⋀ ¬Q,
0 0 1 1 1 1 0
0 1 1 0 1 1 0
1 0 0 1 0 0 0
1 1 0 0 1 1 1
¬Q ⟹ ¬P and ¬P ⋀ ¬Q are logically equivalent
SYMBOLIC LOGIC
The following are logical identities or rules of replacement.
SYMBOLIC LOGIC
SYMBOLIC LOGIC
SYMBOLIC LOGIC
SYMBOLIC LOGIC
Example
Show that ¬(Q ⋀ P) ⟺ P ⟹¬Q.
Solution
¬(Q ⋀ P) ⟺ ¬Q ⋁¬P (De Morgan’s)
⟺ ¬P ⋁¬Q (Commutativity)
⟺ P ⟹¬Q (MI)
SYMBOLIC LOGIC
Example
Show that P ⋀ [(P ⋀ Q) ⋁ R] ⟺ P ⋀ (Q ⋁ R).
Solution
P ⋀ [(P ⋀ Q) ⋁ R] ⟺ [P ⋀ (P ⋀ Q)] ⋁ (P ⋀ R) (Dist)
⟺ [(P ⋀ P) ⋀ Q] ⋁ (P ⋀ R) (Assoc)
⟺ (P ⋀ Q) ⋁ (P ⋀ R) (Indempotence)
⟺ P ⋀ (Q ⋁ R) (Dist)
SYMBOLIC LOGIC
Do Worksheet 6
SYMBOLIC LOGIC
Definition
An argument is a collection of propositions wherein it is
claimed that one of the propositions, called the conclusion,
follows from the other propositions, called the premise of the
argument. the conclusion is usually preceded by such words as
therefore, hence, then, consequently.
Classification of Arguments:
1. Inductive argument is an argument where it is claimed
that within a certain probability of error, the conclusion
follows from a premise; and
2. Deductive argument is an argument where is it claimed
that the conclusion absolutely follows from the premise.
SYMBOLIC LOGIC
A deductive argument is said to be valid if whenever
the premises are all true, then the conclusion is also
true. In other words if 𝑃1 , 𝑃2 , … 𝑃𝑛 are premises and Q
is the conclusion of the argument
𝑃1 𝑎𝑛𝑑 𝑃2 , 𝑎𝑛𝑑 … 𝑃𝑛 therefore Q is valid if and only if
the corresponding prepositional form
(𝑃1 𝑃 ٿ2 𝑄 ⟹ ) 𝑛𝑃 ٿ … ٿ,
is a tautology. Otherwise, the argument is invalid.
SYMBOLIC LOGIC
To show that an argument is valid, we have to show an
instance where the conclusion is free and the premises
are all true.
Show that the following argument is invalid using
Truth Table.
SYMBOLIC LOGIC
To show the validity of arguments, we may use
the truth table. However, this method is
impractical specially if the argument contains
several propositional variables. A more
convenient method is by deducing the
conclusion from the premises by a sequence of
shorter, more elementary arguments known to
be valid.
SYMBOLIC LOGIC
Rules of Inference
These are known valid argument forms.
SYMBOLIC LOGIC
SYMBOLIC LOGIC
SYMBOLIC LOGIC
SYMBOLIC LOGIC
Construct a formal proof of the following rules of
inference:
1. Absorption
2. Modus Ponens
3. Modus Tollens
4. Disjunctive Syllogism
5. Constructive Dilemma
1. Absorption
p q
---------------
p (p q)
Proof:
p q Given premise
p q M.I.
1 (p q) Identity
(p p) (p q) Identity
p (p q) Dist.
p (p q) M.I.
2. Modus Ponens
p q
p
---------------
q
Proof:
1. p q Given premise
2. p Given premise
3. p q Addition
4. p q M.I. (1)
5. (p q) (p q) Conjunction (3,4)
6. (q p) (q p) Comm.
7. q (p p) Dist.
8. q 0 Ident.
9. q Ident.
3. Modus Tollens
p q
q
---------------
p
Proof:
1. p q Given premise
2. q Given premise
3. q p Addition
4. p q M.I. (1)
5. p q Comm. (3)
6. ( p q) (p q) Conjunction (4, 5)
7. p (q q) Dist.
8. p 0 Ident.
9. p Ident.
4. Disjunctive Syllogism
p q
p
---------------
q
Proof:
1. p q Given premise
2. p Given premise
3. p q M.I. (1)
4. q M.P. (3, 2)
5. Constructive Dilemma
(p q) (r s)
pr
---------------
qs
Proof:
1. (p q) (r s) Given premise
2. p r Given premise
3. p q Simplification (1)
4. r s Comm. & Simplification (1)
5. p r M.I. (2)
6. q p Contra+ (3)
7. q r H.S. (6, 5)
8. q s H.S. (6, 4)
9. q s M.I.
Construct a formal proof of validity of the following
arguments:
a) Jack is in Paris only if Mary is in New York. Jack is
in Paris and Fred is in Rome. Therefore, Mary is in
New York.
b) If Mark is correct then unemployment will rise
and if Ann is correct then there will be a hard
winter. Ann is correct. Therefore unemployment
will rise or there will be a hard winter or both.
SYMBOLIC LOGIC
Solution for (a):
J: Jack is in Paris.
M: Mary is in New York.
F: Fred Is in Rome.
The premises of the argument are J ⟹ M and J ⋀ F. The
conclusion is M.
1. J ⟹ M (premise)
2. J ⋀ F (premise)
3. J (2. Simp)
4. M (1, 3. MP)
SYMBOLIC LOGIC
Solution for (b):
M: Mark is correct.
U: Unemployment will rise.
A: Ann is correct.
H: There will be a hard winter.
The premises of the argument are: (M ⟹ U) ⋀ (A ⟹ H) and A. The
conclusion is: U ⋁ H.
1. (M ⟹ U) ⋀ (A ⟹ H) (premise)
2. A (premise)
3. (A ⟹ H) ⋀ (M ⟹ U) (1. Comm)
4. A ⟹ H (3. Simp)
5. H (4, 2. MP)
6. H ⋁ U (5. Add)
7. U ⋁ H (6. Comm)
SYMBOLIC LOGIC
Alternative Solution for (b):
M: Mark is correct.
U: Unemployment will rise.
A: Ann is correct.
H: There will be a hard winter.
The premises of the argument are: (M ⟹ U) ⋀ (A ⟹ H) and A. The
conclusion is: U ⋁ H.
1. (M ⟹ U) ⋀ (A ⟹ H) (premise)
2. A (premise)
3. A ⋁ M (2. Add)
4. M ⋁ A (3. Comm)
5. U ⋁ H (1, 4. CD)
SYMBOLIC LOGIC
Do Worksheet 7
SYMBOLIC LOGIC
Definition
A conditional proofis method of formal proof which is
particularly useful for establishing the validity of a valid
arguments which have a conclusion which can be expressed as
a conditional proposition.
Consider an argument form with premises 𝑝1 , 𝑝2 , … , 𝑝𝑛 and
conclusion q ⟹ r. Note that this argument form is valid if and
only if (𝑝1 ⋀ 𝑝2 ⋀ … ⋀ 𝑝𝑛 ) ⟹ (q ⟹ r). Now the exportation
replacement rule states that p ⟹ (q ⟹ r) ≡ (p ⋀ q) ⟹ rso that
the validity of the condition
(𝑝1 ⋀ 𝑝2 ⋀ … ⋀ 𝑝𝑛 ) ⟹ (q ⟹ r) is a tautology can be replaced by
(𝑝1 ⋀ 𝑝2 ⋀ …⋀ 𝑝𝑛 ⋀ 𝑞) ⟹ r is a tautology.
SYMBOLIC LOGIC
Example
Prove the validity of the following arguments using the method
of conditional proof.
1. If we have a party then we’ll invite Lana and Bob. If we invite
Lana or Bob then we must invite Jake. Therefore if we have a
party then we must invite Jake.
Solution
We symbolise the following simple propositions:
P: We have a party B: We’ll invite Bob.
L: We’ll invite Lana. J: We must invite Jake.
SYMBOLIC LOGIC
(Continued)
The premises of the argument are:
P ⟹ (L ⋀ B) and (L ⋁ B) ⟹ J
The conclusion is the conditional P ⟹ J.
Proof:
1. P ⟹ (L ⋀ B) (premise)
2. (L ⋁ B) ⟹ J (premise)
3. P (CP)
4. L ⋀ B (1, 3. MP)
5. L (4. Simp)
6. L ⋁ B (5. Add)
7. J (2, 6. MP)
8. P ⟹ J (3 – 7. CP)
SYMBOLIC LOGIC
Example
2. If we invite Lana then Jake will sulk, and if we invite Bob then
Alice will leave. So if we invite Lana and Bob then Jake will sulk
and Alice will leave.
Solution
We symbolize the following simple propositions:
L: We invite Lana. B: We invite Bob.
J: Jake will sulk. A: Alice will leave.
The premise of the argument is: (L ⟹ J) ⋀ (B ⟹ A)
and the conclusion is (L ⋀ B) ⟹ (J ⋀ A).
SYMBOLIC LOGIC
Solution
Proof:
1. (L ⟹ J) ⋀ (B ⟹ A) (premise)
2. L ⋀ B (CP)
3. L ⟹ J (1. Simp)
4. (B ⟹ A) ⋀ (L ⟹ J) (1. Com)
5. B ⟹ A (4. Simp)
6. L (2. Simp)
7. J (3, 6. MP)
8. B ⋀ L (2. Com)
9. B (8. Simp)
10. A (5, 9. MP)
11. J ⋀ A (7, 10. Conj)
12. (L ⋀ B) ⟹ (J ⋀ A) (2 – 11. CP)
SYMBOLIC LOGIC
Do Worksheet 8
SYMBOLIC LOGIC