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.

Google Online Preview   Download