Translating English Sentences
System Specifications
Boolean Searches
Logic Circuits
Learning Objective
To be able to translate English sentences into logical expressions
To understand the Boolean search and the notion of logic circuits
2
Translating English Sentences
Many reasons to translate English sentences into expressions involving
propositional variables and logical connectives
Removes the ambiguity
3
Translating English Sentences (Examples)
EXAMPLE 1 How can this English sentence be translated into a logical
expression? “ You can access the internet from campus only
if you are a computer science major or you are not a freshman.”
Solution
Let 𝒂 represent “You can access the Internet from campus”.
Let 𝒄 represent “You are a computer science major”.
Let 𝒇 represent “You are a freshman”.
𝑎 → (𝑐 ∨ ¬𝑓) .
P only if q p q
4
Translating English Sentences (Examples)
Example 2 How can this English sentence be translated into a logical
expression?
“ You cannot ride the roller coaster if you are under 4 feet tall
unless you are older than 16 years old .”
Solution Let q, r and s represent “ You can ride the roller coaster ,” “ you
are under 4 feet tall”, and “ you are older than 16 years old ,”
respectively .
The sentence can be translated to
(𝑟 ¬𝑠) → ¬𝑞.
5
System Specifications
EXAMPLE Express the specification “ The automated reply cannot be sent
when the file system is full ” using the logical connectives.
Solution Let p denote “ The automated reply can be sent” and
q denote “ The file system is full.”
Consequently, the given specification can be represented by the
conditional statement
𝑞 → ¬𝑝.
6
Boolean Searches (Web Page Searching)
To find Web pages about universities in New Mexico
NEW AND MEXICO AND UNIVERSITIES
“NEW MEXICO” AND UNIVERSITIES (more effective)
To find pages that deal with universities in New Mexico or Arizona
(NEW AND MEXICO OR ARIZONA) AND UNIVERSITIES
(“NEW MEXICO” OR ARIZONA) AND UNIVERSITIES
To find Web pages that deal with universities in Mexico (and not New Mexico)
(MEXICO AND UNIVERSITIES) NOT NEW
7
Logic Circuits
Input signals 𝑝1 , 𝑝2 , …, 𝑝𝑛 , each a bit 0 or 1
Output signals 𝑠1 , 𝑠2 ,…, 𝑠𝑛 , each a bit
Inverter(NOT gate) Input p, output ¬𝑝
Three Basic
OR gate Inputs p and q, output 𝑝 ∨ q Circuits
AND gate Inputs p and q, output p ∧ q
8
Basic Logic Gates
Complicated digital circuits can be constructed from three basic circuits.
p ¬p
The inverter, or NOT gate
p 𝑝∨ q
The OR gate q
p p∧q
The AND gate q
9
Propositional Equivalences
¬(𝑝 ∧ 𝑞) ≡ ¬𝑝 ∨ ¬𝑞
De Morgan’s Laws
¬(𝑝 ∨ 𝑞) ≡ ¬𝑝 ∧ ¬𝑞
𝑝 → 𝑞 ≡ ¬𝑝 ∨ 𝑞 Conditional –Disjunction Equivalence
Logical equivalences
𝑝 ∨ 𝑞 ≡ ¬𝑝 → 𝑞
10
Propositional Equivalences
A compound proposition that is always true, no matter
Tautology/ what the truth values of the propositional variables that occur in it,
Contradiction
is called a tautology. A compound proposition that is always false
is called a contradiction.
Show that (𝑝 ∧ 𝑞) → (𝑝 ∨ 𝑞) is tautology.
Conditional –Disjunction
(𝑝 ∧ 𝑞) → (𝑝 ∨ 𝑞) ≡ ¬(𝑝 ∧ 𝑞) ∨ 𝑝 ∨ 𝑞 Equivalence
Example
≡ (¬𝑝 ∨ ¬𝑞) ∨ 𝑝 ∨ 𝑞
≡ (¬𝑝 ∨ 𝑝) ∨ ¬𝑞 ∨ 𝑞
≡𝐓∨𝐓
≡𝐓.
11
Propositional Equivalences
Contingency A compound proposition that is neither a tautology
nor a contradiction is called a contingency.
The compound propositions 𝑝 and 𝑞 are called logically
Logically
equivalent equivalent if 𝑝 ↔ 𝑞 is a tautology. The notation 𝑝 ≡ 𝑞 denotes
that 𝑝 and 𝑞 logically equivalent.
¬ 𝑝 → 𝑞 ≡ ¬ ¬𝑝 ∨ 𝑞
Example
≡ ¬(¬𝑝) ∧ ¬𝑞
≡ 𝑝 ∧ ¬𝑞 .
12
Summary
Translating English sentences into logical expressions
Boolean searches
Propositional equivalences
Basic logic gates
13
𝑝
q
𝑟
Is the output of the following combinatorial circuit is
𝑝 ∧ ¬𝑞 ∨ ¬𝑟 ?
Answer: TRUE
14
Predicates and Nested Quantifiers
15
