Translating English Sentences
Steps to convert an English sentence to a statement in propositional logic:
Identify atomic propositions and represent these propositions using
propositional variables.
Determine appropriate logical connectives
Example: “If I go to Harry’s or to the country, I will not go shopping.”
Solution:
Identify Propositions:
• p: I go to Harry’s
• q: I go to the country.
• r: I will go shopping.
Determine connectives:
• If p or q then not r.
Translating English Sentences
Example #2: Translate the following sentence into propositional
logic: “You can access the Internet from campus only if you are a
computer science major or you are not a freshman.”
Solution: Let a, c, and f represent respectively “You can access
the internet from campus,” “You are a computer science major,” and
“You are a freshman.” The solution is:
a→ (c ∨ ¬ f )
System Specifications
The system and software engineers take requirements in English
and express them in a precise specification language based on
logic.
Example: Express in propositional logic: “The automated reply
cannot be sent when the file system is full”
Solution: Let p denote “The automated reply can be sent” and q
denote “The file system is full.” The solution is:
q→ ¬ p
Consistent System Specifications
Definition: A list of propositions is consistent if it is possible to
assign truth values to the proposition variables so that each
proposition is true.
Exercise: Are these specifications consistent?
“The diagnostic message is stored in the buffer or it is retransmitted.”
“The diagnostic message is not stored in the buffer.”
“If the diagnostic message is stored in the buffer, then it is retransmitted.”
Solution: Let p denote “The diagnostic message is not stored in the buffer.”
Let q denote “The diagnostic message is retransmitted” The specification
can be written as: p ∨ q, p→ q, ¬p. When p is false and q is true, all three
statements are true. So the specification is consistent.
Logic Circuits (optional)
(Studied in depth in Chapter 12)
Electronic circuits; each input/output signal can be viewed as a 0 or 1.
0 represents False
1 represents True
Complicated circuits are constructed from three basic circuits called gates.
The inverter (NOT gate)takes an input bit and produces the negation of that bit.
The OR gate takes two input bits and produces the value equivalent to the disjunction of the two
bits.
The AND gate takes two input bits and produces the value equivalent to the conjunction of the
two bits.
More complicated digital circuits can be constructed by combining these basic circuits to
produce the desired output given the input signals by building a circuit for each piece of
the output expression and then combining them. For example:
Diagnosis of Faults in an Electrical
System (Optional)
AI Example (from Artificial Intelligence: Foundations of
Computational Agents by David Poole and Alan Mackworth,
2010)
Need to represent in propositional logic the features of a piece of
machinery or circuitry that are required for the operation to
produce observable features. This is called the Knowledge Base
(KB).
We also have observations representing the features that the
system is exhibiting now.
Electrical System Diagram (optional)
Outside Power
s1 cb1
Have lights (l1, l2), wires
w1 (w0, w1, w2, w3, w4),
w3 switches (s1, s2, s3), and
w2 circuit breakers (cb1)
s2 The next page gives the
s3
knowledge base describing
the circuit and the current
w0 w4 observations.
l1
l2
Representing the Electrical System
in Propositional Logic (optional)
We need to represent our common-sense understanding of how the
electrical system works in propositional logic.
For example: “If l1 is a light and if l1 is receiving current, then l1 is
lit.
lit_l1 → light_l1 live_l1 ok_l1
Also: “If w1 has current, and switch s2 is in the up position, and s2 is
not broken, then w0 has current.”
live_w0 → live_w1 up_s2 ok_s2
This task of representing a piece of our common-sense world in
logic is a common one in logic-based AI.
Knowledge Base (optional)
live_outside We have outside power.
light_l1 Both l1 and l2 are lights.
light_l2
live_l1 → live_w0
live_w0 → live_w1 up_s2 ok_s2 If s2 is ok and s2 is in a down
live_w0 → live_w2 down_s2 ok_s2 position and w2 has current,
live_w1 → live_w3 up_s1 ok_s1 then w0 has current.
live_w2 → live_w3 down_s1 ok_s1
live_l2 → live_w4
live_w4 → live_w3 up_s3 ok_s3
live_w3 → live_outside ok_cb1
lit_l1 → light_l1 live_l1 ok_l1
lit_l2 → light_l2 live_l2 ok_l2
Observations (optional)
Observations need to be added to the KB
Both Switches up
up_s1
up_s2
Both lights are dark
lit_l1
lit_l2
Diagnosis (optional)
We assume that the components are working ok, unless we are
forced to assume otherwise. These atoms are called assumables.
The assumables (ok_cb1, ok_s1, ok_s2, ok_s3, ok_l1, ok_l2)
represent the assumption that we assume that the switches,
lights, and circuit breakers are ok.
If the system is working correctly (all assumables are true), the
observations and the knowledge base are consistent (i.e.,
satisfiable).
The augmented knowledge base is clearly not consistent if the
assumables are all true. The switches are both up, but the lights
are not lit. Some of the assumables must then be false. This is
the basis for the method to diagnose possible faults in the
system.
A diagnosis is a minimal set of assumables which must be false to
explain the observations of the system.
