Lecture 2 - Radford
Lecture 2 Logic (Cont.)
Goals and Objectives:
• Understand how to convert sentences using logic symbols and operators and vice versa
• Understand what is an consistent system specification
• Understand how to solve logic puzzles
Read section 1.1, p.10-15
Translate English sentences into Symbolic Logic: looking for keyword
such as NOT, AND, OR, BUT NOT BOTH, IF, ONLY IF, SUFFICIENT, NECESSARY
UNLESS(=AND NOT), BUT(=AND), NEVERTHELESS(=AND)
Example: Using symbolic logic to translate the following sentence:
You cannot ride the roller coaster if you are under 4 feet tall
unless you are older than 16 years old
Answer:
We create simple propositions (positive tense so we can remember easily)using symbols first such as
p: you can ride the roller coaster
q: you are under 4 feet tall
r: you are older than 16 years old
Symbolic logic: (q ^[pic]r)-> [pic]p
Example:
If A tells B: “At least one of us is a genius”.
If A tells the truth, then either A or B is a genius or both. What does it mean if A tells a lie?
Answer: Neither A nor B is a genius.
Order of Operators (from let to right):(), not, and, or, conditional, bi-condition.
Example: In the following:
q ^[pic]r-> [pic]p
we will first calculate [pic]r, then [pic]p
Then we find q ^[pic]r. Finally we calculate (q ^[pic]r)-> [pic]p
System specification consistent: all specifications must be true for at least one assignment of truth values for variables.
Example: decide whether the following system specification is 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.
The diagnostic message is not retransmitted.
Answer:
Let s: The diagnostic message is stored in the buffer
r: The diagnostic message is retransmitted
Then we have
s v r
[pic]s
s->r
[pic]r
In order to be consistent, we need s to be false (from 2nd statement) and r to be false (from 4th statement). This will make s v r to be false.
Therefore this is an inconsistent specification.
Logic Puzzle: puzzle that can be solved using logical relations.
Example 1:
The question relates to inhabitants of the island of knights and knaves created by Smullyan (1978), where knights always tell the truth and knaves always lie. You encounter two people A and B. Determine, if possible, what A and B are if they address you in the ways described. If you cannot determine what these two people are, can you draw any conclusions?
A knight is always telling the truth. A knave is always telling a lie.
If A says “B is a knight”. B says “Two of us are opposite kind”. Who are they?
Answer:
METHOD 1: modified truth table.
| |B is knight |B is knave |
|A is knight |impossible |impossible |
|A is knave |impossible |possible |
Therefore, both A and B are knave.
METHOD 2: sequential analysis.
If A is a knight, then B is a knight according to A. Then they are ont opposite kind. Impossible.
Therefore, A is a knave. Hence, B is a knave according to A. This will not contradict to B’s arbument.
Therefore, both A and B are knave.
Example 2: §1.1 Exercise 60: solve a crime.
Four friends have been identified as suspects for an unauthorized access into a computer system. They have been made statements to the investigating authorities.
Alice: Carlos did it. Carlos: Diana did it.
Diana: Carlos is lying. John: I didn’t do it.
Oracle: Only exactly one of them is telling the truth and exactly one did it. Problem: Who did it?
Answer:
METHOD 1: modified truth table. Find the row
|Tell truth |Alice |Carlos |Diana |John |
|Alice | |T |impossible |T |
|Carlos | |F |T |T |
|Diana | |F |F |T |
|John | |F |impossible |F |
John did it.
METHOD 2: sequential analysis.
(1) If Alice is telling the truth, then so is John. Impossible.
Thus, Alice is lying, this implies that Carlos
did not do it.
(2) Similarly, if Carlos is telling the truth, then
so is John. Impossible.
Thus, Carlos is lying, this implies
that Diana did not do it.
(3) By (2), Diana must be telling the truth.
(4) By (3), John is lying. Thus, John did it.
Logic and Bit Operations:
True: bit 1
False: bit 0
bit string of length n: a sequence of n bits
bit string operations: bitwise OR, bitwise AND, bitwise XOR
Example p.15, #18 Find XOR of bit strings 0110110110 and 1100011101
Answer:
1010101011
Assignment #2
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
Related searches
- marketing management pdf lecture notes
- strategic management lecture notes pdf
- strategic management lecture notes
- philosophy 101 lecture notes
- philosophy lecture notes
- philosophy of education lecture notes
- financial management lecture notes
- financial management lecture notes pdf
- business management lecture notes
- introduction to philosophy lecture notes
- business management lecture notes pdf
- introduction to management lecture notes