WEEK 1

LESSON LEARNING OUTCOMES

At the end of this lesson, students will be able to:

Define the purpose of proposition logic.
Carry out the formulae in proposition logic.
Identify the compound proposition.
Construct truth tables.
Write a well-formed proposition logic in English.

Introduction

Click to watch the video

1.1.1 Define the purpose of Proposition Logic

Logic is the study of correct reasoning.

Logic is used in mathematics to prove theorems.

In computer science, logic is used

to prove that programs do what they are supposed to do
in computer programming
in programming languages

Applications of logic in computer science are:

Design of computer circuits
Construction of computer programs
Verification of the correctness of programs
Design of computing machines
System specifications
Programming languages
Artificial Intelligence
Computer programming

1.1.2 Proposition

Proposition is a declarative sentence that is either true or false but not both. A primary statement is a statement that can be represented by a variable, like P, Q, R, S or p, q, r, s. The truthfulness or falsity of a statement is called it's truth value. A true statement has truth value T or 1. A false statement has truth value F or 0.

Example of propositions:

Kuala Lumpur is the capital of Malaysia. (True)

1+1 = 2 (True)

Bintulu is the capital city of Sarawak. (False)

9 is a prime number. (False)

All of statements above has truth value either true or false.

Example of NOT propositions:

What time is it? (this is a question)

Ouch, my leg is in pain! (this is an expression)

Read this carefully. (this is a command)

All the following declarative sentences are not propositions. (the sentences are unknown)

Tun Mahathir. (just a name)

x + 1 = 2 (x is unknown)

All of statements above does not have any truth value.

Quick Exercise 1

Identify whether the following statements are propositions or not. If it is a proposition, state it's truth value.

The earth is round.
Please sit down.
2+3 = 6
2 < 4
What a beautiful flower!
x is an even number.
Where do you live?
7 is an odd number.

1.1.3 Formulae in Proposition Logic

1. Negation (not)

Symbol: ~ or ¬

Negation turns a true proposition to false and a false statement to true. For instance, the negation of statement P is not P.

Truth Table:

2. Conjunction (and, but)

Symbol: ˄

The proposition is TRUE only when both p and q are true.

Read as :

"p and q".

"p but q".

Truth Table:

3. Disjunction (or)

Symbol: ˅

The proposition is FALSE only when both p and q are false.

Read as "p or q".

Truth Table:

4. Implication / Conditional (if...then...)

Symbol: →

p is called hypothesis and q is called the conclusion.

The proposition is TRUE only when both p and q are true and p is false (does not matter what truth value q has).

Read as "if p then q".

p → q can also be read as:

if p then q
if p, q
p is sufficient for q
q if p
q when p
a necessary condition for p is q
q unless ~p
p implies q
p only if q
A sufficient condition for q is p
q whenever p
q is necessary for p
q follows from p

Truth Table:

5. Biconditional statement (if and only if, iff)

Symbol: ↔

The proposition is TRUE when both p and q has the same truth values.

Read as "p if and only if q".

Truth Table:

Converse, Contrapositive and Inverse

There are some related implications that can be formed from p → q which are converse, contrapositive and inverse.

Let p → q

converse: q → p
contrapositive: ~q → ~p
inverse: ~p → ~q

E.g: p: It is raining , q: The home team wins.

p → q : If it is raining, then the home team wins.

Converse. q → p : If the home team wins, then it is raining.

Contrapositive, ~q → ~p : If the home team lost, then it is sunny.

Inverse, ~p → ~q : If it is not raining, then the home team did not win.

Quick Exercise 2

Let P: I am rich; Q: I am happy. Write the following compound statements in symbolic forms.

I am rich and happy.
I am poor but happy.
I am not rich and not happy.
If I am happy then I am not poor.
It is not true that if I am poor, then I am not happy.
I am rich is necessary for me to be happy.

Quick Exercise 3

For each of the symbolic expression, write the corresponding (compound) statement base on the given primary statements:

P: Men are immortal.

Q: Men are safe from tragedy.

R: Men are created by God.

P → Q
P → (Q ˄ R)
Q → ~R
~P → (~Q ˅ ~R)
(Q ˄ R)↔ P

Quick Exercise 4

What are the converse, the contrapositive and the inverse of the implication. Answer in sentences (English).

"If it is not sunny, then it is cold."

1.1.4 Construct the Truth Table

Step 1: Identify the number of variables involved and arrange according to alphabetical order.

Step 2: The number of lines needed is 2n where n is the number of variables. (E.g., with three variables, 2³ = 8).

Step 3: In the first column, group the Ts and Fs (always start with T e.g. T,T, F,F)

Step 4: In the second column, arrange the Ts and Fs alternately. But in the case of 3 variables, alternate double e.g. T, T, F, F, T, T, F, F.

Step 5: If there is a third column, then arrange the Ts and Fs alternately e.g. T, F, T, F.

Sequence of logical connectives:

Tautology, Contradiction & Contingency

Tautology - a compound proposition that is always true.
Contradiction - a compound proposition that is always false.
Contingency - a proposition that is neither a tautology nor a contradiction.

Column no 3 = Tautology

Column no 4 = Contradiction

Quick Exercise 5

Construct the truth table of the compound proposition (p → q) ˄ ~q → ~p and determine whether it is tautology or not.

Determine whether (p ˄ ~q) → ~r is tautology or not.

1.1.5 Logical Equivalence

Logical equivalent : Compound propositions that have the same truth values.
The compound propositions p and q are called logically equivalent if p ↔ q is a tautology.
The notation p ≡ q denotes that p and q are logically equivalent.
Truth table is used to determine whether two compound propositions are equivalent.

Quick Exercise 6

Show that ~(p ˅ q) and ~p ˄ ~q are logically equivalent.

Quick Exercise 7

Construct the truth table of the following compound proposition:

~(p ˄ ~q)
(p ˅ q) ↔ (q ˅ p)
(p → q) ˅ (~p → r)
(p → r)↔(q ˄~p)
~p → (q→ r)

WEEK 1 ACTIVITY

Kindly complete Week 1 activity as follows:

Page updated

Report abuse