Chapter 1

Part 3
Fundamental and Elements of Logic
 Why Are We Studying Logic?
Some of the reasons:
 Logic is the foundation for computer operation
 Logical conditions are common in programs
Example:
Selection: if (score <= max) { ... }
Iteration: while (i<limit && list[i]!=sentinel) ...
 All manner of structures in computing have properties that need
to be proven (and proofs that need to be understood).
Example: Trees, Graphs, Recursive Algorithms, . . .
 Programs can be proven correct.
 Computational linguistics must represent and reason about
human language, and language represents thought (and thus
also logic).

2
 PROPOSITION

A statement or a proposition, is a declarative sentence

that is either TRUE or FALSE, but not both.

Example:
 4 is less than 3.
 7 is an even integer.
 Washington, DC, is the capital of United
State.

3
 Example
i) Why do we study mathematics?
ii) Study logic.
iii) What is your name?
iv) Quiet, please.

The above sentences are not propositions. Why ?

(i) & (iii) : is question, not a statement.

(ii)& (iv) : is a command.

4
 Example
i) The temperature on the surface of the planet Venus is
800 F.
ii) The sun will come out tomorrow.

Propositions? Why?
 Is a statement since it is either true or false, but not
both.
 However, we do not know at this time to determine
whether it is true or false.

5
 CONJUNCTIONS

TRUTH TABLE: This tables

 Compound propositions aid in the evaluation of
formed in English with compound propositions.
the word “and”
p q pq
 Formed in logic with the T T T
caret symbol (“ ∧ ”) T F F
F T F
 True only when both
F F F
participating
propositions are true.
True (T), False (F)

6
 Example

p : 2 is an even integer
propositions
q : 3 is an odd number

p∧q symbols
: 2 is an even integer and 3 is an odd number statements

p : today is Monday
q : it is hot

p ∧ q: today is Monday and it is hot

7
 Example
Proposition
p : 2 divides 4
q : 2 divides 6

Symbol & Statement

p ∧ q: 2 divides 4 and 2 divides 6.

or,
p ∧ q: 2 divides both 4 and 6.

8
 Example

Proposition
p : 5 is an integer
q : 5 is not an odd integer

Symbol & Statement

p ∧ q: 5 is an integer and 5 is not an odd integer.

or,
p ∧ q: 5 is an integer but 5 is not an odd integer.

9
 DISJUNCTION
 Compound propositions
formed in English with The truth table for p ∨ q
the word “or”,
p q p ∨q
 Formed in logic with the T T T
caret symbol (“ ∨ ”) T F T

 True when one or both F T T

participating F F F
propositions are true.

10
 Example

p: 2 is an integer
q: 3 is greater than 5

p ∨ q : 2 is an integer or 3 is greater than 5

p : 1+1=3
q : A decade is 10 years

p ∨ q : 1+1=3 or a decade is 10 years

11
 Example

p : 3 is an even integer
q : 3 is an odd integer

p∨q
3 is an even integer or 3 is an odd integer
or
3 is an even integer or an odd integer

12
 NEGATION
Negating a proposition simply
flips its value. Symbols
representing negation include: The truth table of ¬ p
￢x , x , ∼x, x′ (NOT) p ¬p
T F
Let p be a proposition. F T
The negation of p, written ¬ p
is the statement obtained by
negating
statement p.

13
Example
p : 2 is positive

¬ p : 2 is not positive.

p : 4 is less than 3

¬ p : 4 is not less than 3.

14
 Exercise
p: It will rain tomorrow
q: it will snow tomorrow

Give the negation of the following statement and write

the symbol.

It will rain tomorrow or it will snow tomorrow.

15
 Exercise
In each of the following, form the conjunction and the
disjunction of p and q by writing the symbol and the
statements.

i) p: I will drive my car

q: I will be late

ii) p : NUM > 10

q : NUM ≤ 15

16
 Exercise
Suppose x is a particular real number. Let p, q and r
symbolize “0 < x”, “x < 3” and “x = 3”, respectively.
Write the following inequalities symbolically:

a) x ≤ 3

b) 0 < x <3

c) 0 < x ≤ 3

17
 Exercise

State either TRUE or FALSE if p and r are TRUE

and q is FALSE.

a) ~ p ∧ ( q ∨ r )

a) ( r ∧ ~q ) ∨ ( p ∨ r )

18
 CONDITIONAL PROPOSITIONS

Let p and q be propositions.

“if p, then q”
is a statement called a conditional proposition,
written as
p→q

19
 CONDITIONAL PROPOSITIONS
The truth table of p → q
=> Cause and effect relationship
FALSE if TRUE if
p = True both
and q true or
=false p=false
p q p q for any
value of
T T T q

T F F
F T T
F F T

20
 Example
p : today is Sunday
q : I will go for a walk
p → q : If today is Sunday, then I will go for a walk.

p : I get a bonus
q : I will buy a new car

p → q: If I get a bonus, then I will buy a new car

21
 Example

p : x/2 is an integer.
q : x is an even integer.

p → q : if x/2 is an integer, then x is an even integer.

22
 BICONDITIONAL

Let p and q be propositions.

“p if and only if q”
is a statement called a biconditional proposition,
written as

p↔q
23
BICONDITIONAL

The truth table of p ↔ q:

p q p↔q
T T T
T F F
F T F
F F T

24
 Example
p : my program will compile
q : it has no syntax error.
p ↔ q : My program will compile if and only if it has no
syntax error.

p : x is divisible by 3
q : x is divisible by 9

p ↔ q : x is divisible by 3 if and only if x is divisible by 9.

25
 LOGICAL EQUIVALENCE

 The compound propositions Q and R are made up of

the propositions p1, …, pn.

 Q and R are logically equivalent and write,

Q≡R
provided that given any truth values of p1, …, pn,
either Q and R are both true or Q and R are both
false.

26
 Example
Q=p→q R= ¬ q → ¬ p
Show that, Q ≡ R

The truth table shows that, Q ≡ R

p q p →q ¬q →¬p
T T T T
T F F F
F T T T
F F T T
27
 Example
Show that, ¬ (p → q) ≡ p ∧ ¬ q

The truth table shows that, ¬ (p → q) ≡ p ∧ ¬ q

p q ¬(p → q) p ∧¬q
T T F F
T F T T
F T F F
F F F F
28
 PRECEDENCE OF LOGICAL CONNECTIVES

Precedence of logical connectives

is as follows:
not ¬ Highest
and ∧
or ∨
If…then →
If and only if ↔ Lowest

29
 Example
Construct the truth table for, A = ¬(p ∨ q) → (q ∧ p)

Solution
p q (p∨q) ¬(p∨q) (q∧p) A

T T T F T T
T F T F F T
F T T F F T
F F F T F F

30
 Exercise

Construct the truth table for each of the following

statements:
i) ¬p∧q
ii) ¬(p ∨ q) → q
iii) ¬(¬ p ∧ q) ∨ q
iv) (p → q) →(¬ q → ¬ p)

31
 LOGIC & SET THEORY
Logic and set theory go very well togather. The previous
definitions can be made very succinct:

32
 Venn Diagrams
Venn Diagrams are used to depict the various unions,
subsets, complements, intersections etc. of sets.

33
34
35
 Theorem for Logic
Let p, q and r be propositions.

Idempotent laws:
p∧p≡p
p∨p≡p
Truth table

36
 Theorem for Logic
Double negation law: ¬¬p≡p

Commutative laws: p∧q≡q∧p

p∨q≡q∨p

(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Associative laws:
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

37
 Theorem for Logic
Distributive laws: p ∨ (q ∧ r) ≡ (p∨q) ∧ (p∨r)
p ∧ (q ∨ r) ≡ (p ∧ q)∨ (p∧r)

PROVE

38
 Theorem for Logic

p ∧ (p ∨ q) ≡ p
Absorption laws:
p ∨ (p ∧ q) ≡ p

PROVE

39
 Theorem for Logic
¬(p ∧ q) ≡ (¬ p) ∨ (¬ q)
De Morgan’s laws:
¬(p ∨ q) ≡ (¬ p) ∧ (¬ q)

The truth table for ¬(p∨ q) ≡ (¬ p) ∧ (¬ q)

40
 Exercise

Given,
R = p ∧ (¬ q∨ r)
Q = p ∨ (q ∧ ¬ r)

State whether or not R ≡ Q.

41
 Exercise
Propositional functions p, q and r are defined as follows:
p is "n = 7"
q is "a > 5"
r is "x = 0"
Write the following expressions in terms of p, q and r, and show
that each pair of expressions is logically equivalent. State
carefully which of the above laws are used at each stage.
(a) ((n = 7) ∨ (a > 5)) (x = 0)
((n = 7) (x = 0)) ∨ ((a > 5) (x = 0))

(b) ¬((n = 7) (a ≤ 5))

(n ≠ 7) ∨ (a > 5)

(c) (n = 7) ∨ (¬((a ≤ 5) (x = 0)))

((n = 7) ∨ (a > 5)) ∨ (x ≠ 0)

42
 Exercise
Propositions p, q, r and s are defined as follows:
p is "I shall finish my Coursework Assignment"
q is "I shall work for forty hours this week"
r is "I shall pass Maths"
s is "I like Maths"

Write each sentence in symbols:

(a) I shall not finish my Coursework Assignment.
(b) I don’t like Maths, but I shall finish my Coursework Assignment.
(c) If I finish my Coursework Assignment, I shall pass Maths.
(d) I shall pass Maths only if I work for forty hours this week and finish my
Coursework Assignment.

Write each expression as a sensible (if untrue!) English sentence:

(e) q ∨ p
(f) ¬p → ¬r

43
 Exercise
For each pair of expressions, construct truth
tables to see if the two compound propositions
are logically equivalent:

(a) p ∨ (q ∧¬p)
p∨q

(b) (¬p ∧ q) ∨ (p ∧ ¬q)

(¬p ∧ ¬q) ∨ (p ∧ q)

44
Thank You