代写 R algorithm math database Finite State Automaton COMP2022: Formal Languages and Logic

COMP2022: Formal Languages and Logic
2018, Semester 2, Week 9
Kalina Yacef, Joseph Godbehere
4th October, 2018

COMMONWEALTH OF AUSTRALIA Copyright Regulations 1969 WARNING
This material has been reproduced and communicated to you by or on behalf of the University of Sydney pursuant to part VB of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act. Any further copying or communication of this material by you may be subject of copyright protect under the Act.
Do not remove this notice.

Revision Turing Machines Language Cool stuff Computability Logic Review
Outline
▶ Revision
▶ Turing Machines
▶ Logic
3/59

Revision Turing Machines Language Cool stuff Computability Logic Review
FIRST and FOLLOW sets
In order to fill in the entries of the table-drived parser, we need to compute some FIRST and FOLLOW sets.
FIRST(α) is the set of all terminals which could start strings derived from α. We will need to calculate these for every production of G (i.e. the right hand side of each rule).
FOLLOW (V ) is the set of all terminals which which could follow the variable V at any stage of the derivation. Needed whenever V can derive ε.
4/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Why do we need them?
Let the current input symbol be b, and the top of the stack be X. There are two ways we might try to derive a string starting with b:
1. Derive a string starting with b from the variable X . Look for aruleX →αwhereb∈FIRST(α)
2. If X can be derived to ε, then we might be able to derive a string starting with b by using the symbol(s) following X on the stack.
i.e. If any of the production rules X → α had ε ∈ FIRST (α), then we also look at FOLLOW (X )
5/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Another way to calculate FIRST sets
Let A → X1…Xn be a production of A, where Xi could be a terminal or variable.
We recursively compute FIRST(X1…Xn) by looking at X1:
▶ If X1 is a terminal symbol, then FIRST (X1…Xn ) = {X1}
▶ If X1 is a variable, then FIRST(X1…Xn) contains FIRST(X1) \ {ε}
▶ If X1 is a variable ε ∈ FIRST (X1) then FIRST (X1…Xn ) also contains FIRST(X2…Xn)
Don’t forget that FIRST (ε) = {ε}, so if every Xi can generate ε, then rule 3 will (eventually) give us ε ∈ FIRST(X1…Xn)
6/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Another way to calculate FOLLOW sets
If ε ∈ FIRST (α) for some production rule A → α then we need to compute FOLLOW (A)
Consider each production rule where A appears in the right hand side.
Let V → Y1…Yn AZ1…Zm (Yi , Zi can be terminals or variables)
▶ If A is the start symbol, then $ ∈ FOLLOW (A)
▶ FIRST(Z1…Zm)\{ε}⊆FOLLOW(A)
▶ If ε ∈ FIRST (Z1…Zm ) then FOLLOW (V ) ⊆ FOLLOW (A)
7/59

Revision Turing Machines Language Cool stuff Computability Logic Review
examples
(see last week)
8/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Constructing the parse table
Rows: one for each variable of the grammar
Columns: one for each terminal of the grammar, and for the end of string marker $
Steps to fill the table T:
1. IfthereisaruleR→αwithb∈FIRST(α)thenputαin
T[R,b]
2. IfthereisaruleR→αwithε∈FIRST(α)and b ∈ FOLLOW(R), then put α in T[R,b]
9/59

Revision Turing Machines Language Cool stuff Computability Logic Review
example
(see last week)
10/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Left factoring: definition
If a string w appears on the left of several rules for a variable A: A→wX1 |…|wX1
Then we can factor out w and introduce a new variable A′: A → wA′
A′ →X1 |…|Xn Any other rules produced by A are unaffected.
11/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Eliminating left recursion
Let α, β be arbitrary strings of terminals and/or variables. Let A be a variable, and R a new variable
If A has left recursive rules:
A → Aα | β
It can be replaced with:
A → βR
R → αR | ε
12/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Outline
▶ Revision
▶ Turing Machines
▶ Logic
13/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Beyond CFL
An unrestricted grammar to generate L = {a2i | i ≥ 1}:
S → ACaB Ca → aaC
CB → DB CB → E
aD → Da AD → AC aE → Ea
AE → ε
14/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Beyond CFL
An unrestricted grammar to generate L = {a2i | i ≥ 1}: How can we derive aaaa?
S → ACaB Ca → aaC
CB → DB CB → E
aD → Da AD → AC aE → Ea
AE → ε
S ⇒ACaB ⇒AaaCB ⇒AaaDB
14/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Chomsky Hierarchy
Regular (DFA)
Context- free (PDA)
Context- sensitive (LBA)
Recursively- enumerable (TM)
Type 0 grammars (unrestricted grammars) are powerful enough to describe the set of recursively enumerable languages.
15/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Turing Machines
▶ Finite automata have a finite memory. They recognise regular languages (regular grammars)
▶ Push Down Automata: Add a LIFO stack (infinite memory, but access is limited to the top). PDAs recognise context-free languages (context-free grammars)
▶ By changing the stack for a tape (infinite memory, no limitation of access) we get Turing machines: our current computers. TM recognise recursively enumerable languages (unrestricted grammars)
▶ Alan Turing (1912-1954) mathematician and logician
▶ http://www.alanturing.net
▶ Turing machines introduced in his 1936 article
16/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Turing Machines: schematic view
Turing machines have infinite memory: a tape.
▶ Can read and write symbols on it, or do nothing
▶ Can move to the right or to the left along the tape
…
B
a1
a2
…
ai
…
an
B
B
…
Finite control
i.e. it is a finite state automaton attached to an infinite tape
17/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Formal Definition
A Turing machine is a 7-tuple M = (Q,Σ,Γ,δ,q0,B,F) ▶ Q is a finite set of states
▶ Σ is a finite set called the input alphabet. B ̸∈ Σ
▶ Γisafinitesetoftapesymbols. Σ⊂Γ
▶ δ : Q ×Γ → Q ×Γ×{L,R} is the transition function. ▶ L means ’move left’, R means ’move right’
▶ q0 ∈ Q is the start state
▶ B is a special symbol of Γ, the blank ▶ F ⊆Q isthesetofacceptstates
18/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Turing machine for {0n 1n | n > 0}
▶ Q = {q0,q1,q2,q3,q4} ▶ Σ={0,1}
▶ Γ = {0,1,X,Y,B}
▶ q0 ∈ Q is the start state ▶B
▶ ▶
F = {q4} δ:Q×Γ→Q×Γ×{L,R}isgivenby:
01XYB
q0 (q1,X,R)
q1 (q1,0,R) (q2,Y,L) q2 (q2,0,L)
q3
q4
(q3,Y,R)
(q1,Y,R) (q0,X,R) (q2,Y,L)
(q3,Y,R) (q4,B,R)
19/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Trying M on 0011
20/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Semi-formal description of M
Assuming:
▶ The tape initially contains only 0s, 1s and blanks ▶ We start at the first non-blank symbol on the tape
1. If we did not start on a 0, reject 2. Replace the 0 with an X
3. Move right until a 1 occurs
4. Replace the 1 with a Y
5. Move left until we find the X marker
6. Move right once. If we are on a 0, goto (2)
7. Move right across the tape, skipping X and Y.
▶ If a 1 or 0 is scanned, reject ▶ If a blank is scanned, accept
21/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Turing machine for a non-CFL: {an bn cn | n > 0}
▶ Q = {q0,qa,qb,qc,qy,qz,qf } ▶ Σ={a,b,c}
▶ Γ={a,b,c,X,Y,Z,B}
▶ q0 ∈ Q is the start state ▶B
▶ F = {qf }
▶ δ:Q×Γ→Q×Γ×{L,R}isgivenby:
a
b
c
X
Y
Z
B
q0
(qa,X,R)
(qy,Y,R)
qa
(qa,a,R)
(qb,Y,R)
(qa,Y,R)
qb
(qb,b,R)
(qc,Z,L)
(qb,Z,R)
qc
(qc,a,L)
(qc,b,L)
(q0,X,R)
(qc,Y,L)
(qc,Z,L)
qy
(qy,Y,R)
(qz,Z,R)
qz
(qz,Z,R)
(qf ,B,R)
qf
22/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Trying it on aabbcc
23/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Language accepted by a Turing Machine
▶ The language accepted by a Turing machine M is the set of strings such that M started on the left of the input and reached some state of F
▶ M may fail to stop!
▶ If M stops in some non-accepting state or never stops on
input w, then M does not accept w.
▶ Languages accepted by a Turing Machine are “recursively
enumerable”
▶ Unrestricted grammars (type 0)
24/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Turing machine to add 2 numbers
A number n is represented by n 0’s (unary) The two numbers are separated by a 1
▶ Q = {q0,q1,q2,q3}
▶ Σ={0,1}
▶ Γ={0,1,B}
▶ q0 ∈ Q is the start state ▶B
▶ F = {q3}
▶ δ:Q×Γ→Q×Γ×{L,R}isgivenby:
0
1
B
q0
(q0, 0, R)
(q1, 0, R)
(q3,B,R)
q1
(q1, 0, R)
(q2,B,L)
q2
(q3,B,R)
q3
25/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Semi-formal description
1. Move to the right until we reach a 1 (skipping 0s)
2. Rewrite the 1 with a 0
3. Move to the right until we reach a blank (skipping 0s) 4. Move to the left once, to rewrite the last 0 with a blank
For example, if our tape originally read …B000100B…, it now reads …B 00000BB …. i.e. 3 + 2 = 5
Turing machines can make calculations! Note the similarity with computers.
26/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Left-bounded tapes
Can a Turing Machine with an infinite tape in both directions recognise more languages than tape that is only unbounded in one direction?
Does a tape with positions 0, 1, 2, 3, … have more positions than one with positions … − 2, −1, −0, 1, 2, …? i.e. are there “more” integers than positive integers?
Counter-intuitively, the answer is no, because we can pair up every integer with a positive integer:
1
2
3
4
5
…
0
−1
1
−2
2
…
So, a tape unbounded to the left does not have more positions. This is what we mean when we say a set is enumerable.
27/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Left-bounded tapes
Can a Turing Machine with an infinite tape in both directions recognise more languages than tape that is only unbounded in one direction?
We could make a machine that jumped around to seek the correct positions according to the bijection of integers to positive integers, but there’s a much simpler way:
Add states to the TM such that whenever we want to move past the left edge of the tape, we simply shift everything on the tape one position to the right instead.
▶ We will need to place a marker at the far right of the input, so we know when to stop shifting.
28/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Multi-tape Turing Machines
Can a multi-tape Turing Machine recognise more languages than a single-tape TM?
29/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Multi-tape Turing Machines
Can a multi-tape Turing Machine recognise more languages than a single-tape TM?
NO
Proof: We can modify a single tape TM to simulate having multiple tapes:
▶ Add markers symbolising the start and end of each tape
▶ Add markers symbolising the current TM position on each
▶ Add states which simulate switching between the tapes
▶ Add states which extend these (finite) stretches of tape (by shifting everything beyond it by one space)
29/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Context-free languages
Can a TM recognise every context-free language?
30/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Context-free languages
Can a TM recognise every context-free language?
YES
Proof: A TM can simulate a PDA.
▶ Write the PDA input to the tape
▶ Mark a section of tape beyond the end of the input as the stack
▶ Repeatedly move between the tape and the end of the stack
▶ i.e. each state in the PDA will have two states in the TM ▶ One for the current input symbol, one for the top of stack
30/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Non-deterministic TM
Is a Non-deterministic TM more powerful than a deterministic one?
31/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Non-deterministic TM
Is a Non-deterministic TM more powerful than a deterministic one?
NO
Proof: We can simulate a NTM with a 3-tape DTM
▶ Tape 1 contains the original input
▶ Tape 2 simulates a particular computation of the TM
▶ Tape 3 encodes the path through the tree of possible paths through the NTM
31/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Universal Turing machine
▶ It is possible to encode a Turing machine or to write a “program” to describe a Turing machine.
▶ The Universal Turing Machine accepts an encoded Turing machine M together with a string w and simulates M on w.
▶ Exactly what general computers do: ▶ They accept a program P
▶ and the input to that program
▶ and produces the output of P on the given input
▶ Again, note the similarity between TM and computers
32/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Church-Turing Thesis
“Every effectively calculable function is a computable function.” Essentially this means that the set of algorithms is equivalent to
the set of Turing Machine algorithms.
So:
▶ TM are a very precise model for definition of algorithm.
▶ TM can do everything that a computer can do.
▶ However, even a Turing machine cannot solve all problems:
▶ some are beyond theoretical limits of computation
33/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Computability, Decidability, Intractability
Decidable ⊂ TM computable
▶ A function that can be computed by a Turing machine is said
to be computable (therefore the language is enumerable) ▶ It is decidable if and only if the Turing machine will always
halt on any input string (the Halting Problem)
▶ Intractability: The efficiency problem – can we solve the problem in a reasonable time (e.g. polynomial vs exponential)?
34/59

Revision Turing Machines Language Cool stuff Computability Logic Review
Example of undecidable problem: The Halting problem
▶ Halting problem: Is there an algorithm that can decide whether the execution of an arbitrary program halts on an arbitrary input?
▶ e.g.
▶ f(x){ return 2x +1;}, will f halt on any number?
▶ h(x){ while(true) {x+ = 1;} …}?
▶ g(x){for(i=x; i<10; i−=1); ...}? ▶ Answer: NO (Church 1936, Turing 1937) 35/59 Revision Turing Machines Language Cool stuff Computability Logic Review Proving the Halting Problem is undecidable Suppose the Halting problem is decidable. Then there exists some universal Turing machine H such that H(a,b) accepts if and only if the TM represented by a would halt on input b. The language L of H is: {a, b | a represents a TM, b is an input string, a halts on b} 36/59 Revision Turing Machines Language Cool stuff Computability Logic Review Proving the Halting Problem is undecidable H (a, b) accepts iff TM a halts on input b Let X(c) be a Turing machine which either: ▶ If H (c, c) accepts, then loop forever ▶ If H (c, c) rejects, then halt 37/59 Revision Turing Machines Language Cool stuff Computability Logic Review Proving the Halting Problem is undecidable Now consider what happens if we use “X , X ” as input to H . i.e. what does X do when given its own representation as input. 38/59 Revision Turing Machines Language Cool stuff Computability Logic Review Proving the Halting Problem is undecidable Now consider what happens if we use “X , X ” as input to H . i.e. what does X do when given its own representation as input. Case 1: If H(X,X) accepts, then X must halt on input X, because H is a solution to the Halting problem. However, X will loop forever because H (X , X ) accepts. 38/59 Revision Turing Machines Language Cool stuff Computability Logic Review Proving the Halting Problem is undecidable Now consider what happens if we use “X , X ” as input to H . i.e. what does X do when given its own representation as input. Case 1: If H(X,X) accepts, then X must halt on input X, because H is a solution to the Halting problem. However, X will loop forever because H (X , X ) accepts. Case 2: If H(X,X) rejects, then X cannot halt on input X, because H is a solution to the Halting problem. However, X will halt because H (X , X ) rejected. 38/59 Revision Turing Machines Language Cool stuff Computability Logic Review Proving the Halting Problem is undecidable Now consider what happens if we use “X , X ” as input to H . i.e. what does X do when given its own representation as input. Case 1: If H(X,X) accepts, then X must halt on input X, because H is a solution to the Halting problem. However, X will loop forever because H (X , X ) accepts. Case 2: If H(X,X) rejects, then X cannot halt on input X, because H is a solution to the Halting problem. However, X will halt because H (X , X ) rejected. Both cases lead to contradictions, so the assumption was incorrect. i.e. The Halting problem cannot be decidable. 38/59 Revision Turing Machines Language Cool stuff Computability Logic Review Example of undecidable problem: The Halting problem ▶ Halting problem: Is there an algorithm that can decide whether the execution of an arbitrary program halts on an arbitrary input? ▶ e.g. ▶ f(x){ return 2x +1;}, will f halt on any number? ▶ h(x){ while(true) {x+ = 1;} ...}? ▶ g(x){for(i=x; i<10; i−=1); ...}? ▶ Answer: NO (Church 1936, Turing 1937) ▶ How can you restrict the halting problem to be decidable? 39/59 Revision Turing Machines Language Cool stuff Computability Logic Review Computability, Decidability, Intractability We will talk more about these concepts at the end of the course. 40/59 Revision Turing Machines Language Cool stuff Computability Logic Review Outline ▶ Revision ▶ Turing Machines ▶ Logic 41/59 Revision Turing Machines Language Cool stuff Computability Logic Review Logic: Introductory Example What do you think of the following argument? 1. If a number is a multiple of 2×3×4, then it is a multiple of 2 and a multiple of 3 and a multiple of 4 2. Therefore, if a number is a multiple of 2 and a multiple of 3 and a multiple of 4, then it is a multiple of 2×3×4 42/59 Revision Turing Machines Language Cool stuff Computability Logic Review Logic: Introductory Example What do you think of the following argument? 1. If a number is a multiple of 2×3×4, then it is a multiple of 2 and a multiple of 3 and a multiple of 4 2. Therefore, if a number is a multiple of 2 and a multiple of 3 and a multiple of 4, then it is a multiple of 2×3×4 Expressing this formally: M → (P ∧ Q ∧ R) (P ∧ Q ∧ R) → M 42/59 Revision Turing Machines Language Cool stuff Computability Logic Review Logic ▶ Logic is a language used to make some disciplines scientific by providing a way to deduce knowledge from a relatively small number of explicitly stated facts or hypotheses ▶ In CS: specification of requirements, program verification, some databases ▶ Allows expression of knowledge concisely and precisely, enabling analysis of the argument structure ▶ Provides a way to reason about the consequences of that knowledge rigourously. i.e. How to make a judgement on the validity of the argument ▶ Focus on validity (correctness) of the argument form, rather than its contents 43/59 Revision Turing Machines Language Cool stuff Computability Logic Review Logic in real arguments Argument 1: If I play cricket or I go to work, then I will not be going shopping. Therefore, if I go shopping, then I would neither play cricket nor would I go to work ▶ P: I play cricket ▶ Q: I go to work ▶ R: I go shopping IfP orQ,thennotR Therefore, if R then not P and not Q (P∨Q)→¬R R → (¬P ∧¬Q) 44/59 Revision Turing Machines Language Cool stuff Computability Logic Review Logic in real arguments Argument 2: An object remaining stationary or moving at a constant velocity means that there is no net external force acting upon it. Therefore, if there is a net force acting upon the object, then it is neither stationary nor is it moving at a constant velocity. ▶ P: The object is stationary ▶ Q: The object is moving at a constant velocity ▶ R: There is a net external force acting upon the object IfP orQ,thennotR (P∨Q)→¬R Therefore, if R then not P and not Q R → (¬P ∧¬Q) 45/59 Revision Turing Machines Language Cool stuff Computability Logic Review Arugment, Premises, Deduction An argument is a claim. It is composed of statements ▶ IfP orQ,thennotR ▶ Therefore, if R then not P and not Q The premises of an arugment are the hypothesis for the argument ▶ IfP orQ,thennotR The last statement is the conclusion of the argument, which needs to be deduced from the premises ▶ Therefore, if R then not P and not Q 46/59 Revision Turing Machines Language Cool stuff Computability Logic Review Propositional Logic Formalise sentences ▶ Propositions and connectives ▶ From english to propositions Semantics ▶ Truth tables ▶ Tautologies Formal Reasoning 47/59 Revision Turing Machines Language Cool stuff Computability Logic Review Propositions A Proposition is the underlying meaning of a declarative sentence (a sentence which is either true or false): ▶ Mammals are warm-blooded ▶ The sun orbits the earth ▶ 2+2=4 ▶ All integers are even But these are not propositions: ▶ Can you show me the way to Redfern? ▶ Pay your bills on time ▶ Stop talking! 48/59 Revision Turing Machines Language Cool stuff Computability Logic Review Well-formed formula (wff) syntax A well-formed formaula (wff) is an expression with the correct syntax (i.e. it is a string from the language of wff) Truth symbols are wff (true or false) Atomic propositions are wff (P,Q,R,...) Complex propositions are built up using connectives: If P and Q are wff, then (P), ¬P, (P ∧ Q), (P ∨ Q), (P → Q), (P ↔ Q) are all also wff To make it easier to refer to complex wff, we can set labels for them by writing, for example Z = ((P → Q) ∨ Q) 49/59 Revision Turing Machines Language Cool stuff Computability Logic Review Semantics (truth tables) Truth tables define the possible values that a wff can take, depending on the values of the atomic propositions that it contains. The meaning of true is 1, and false if 0, otherwise the meaning of a wff is its truth table. P Q P∧Q 1 1 1 1 0 0 0 1 0 0 0 0 50/59 Revision Turing Machines Language Cool stuff Computability Logic Review Connectives Negation (not) ¬P is true iff P is false Conjunction (and) (P∧Q) is true iff both P and Q are true Disjunction (or) (P∨Q)istrueiffP orQ istrue Implication (P → Q) is false iff P is true and Q is false Equivalence (P ↔Q)istrueiffP hasthesametruth value as Q P Q ¬P (P ∧ Q) (P ∨ Q) (P → Q) (P ↔ Q) 1 1 1 0 0 1 0 0 51/59 Revision Turing Machines Language Cool stuff Computability Logic Review Connectives Negation (not) ¬P is true iff P is false Conjunction (and) (P∧Q) is true iff both P and Q are true Disjunction (or) (P∨Q)istrueiffP orQ istrue Implication (P → Q) is false iff P is true and Q is false Equivalence (P ↔Q)istrueiffP hasthesametruth value as Q P Q ¬P (P ∧ Q) (P ∨ Q) (P → Q) (P ↔ Q) 1 1 0 1 0 0 0 1 1 0 0 1 51/59 Revision Turing Machines Language Cool stuff Computability Logic Review Connectives Negation (not) ¬P is true iff P is false Conjunction (and) (P∧Q) is true iff both P and Q are true Disjunction (or) (P∨Q)istrueiffP orQ istrue Implication (P → Q) is false iff P is true and Q is false Equivalence (P ↔Q)istrueiffP hasthesametruth value as Q P Q ¬P (P ∧ Q) (P ∨ Q) (P → Q) (P ↔ Q) 1 1 0 1 1 0 0 0 0 1 1 0 0 0 1 0 51/59 Revision Turing Machines Language Cool stuff Computability Logic Review Connectives Negation (not) ¬P is true iff P is false Conjunction (and) (P∧Q) is true iff both P and Q are true Disjunction (or) (P∨Q)istrueiffP orQ istrue Implication (P → Q) is false iff P is true and Q is false Equivalence (P ↔Q)istrueiffP hasthesametruth value as Q P Q ¬P (P ∧ Q) (P ∨ Q) (P → Q) (P ↔ Q) 1 1 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 51/59 Revision Turing Machines Language Cool stuff Computability Logic Review Connectives Negation (not) ¬P is true iff P is false Conjunction (and) (P∧Q) is true iff both P and Q are true Disjunction (or) (P∨Q)istrueiffP orQ istrue Implication (P → Q) is false iff P is true and Q is false Equivalence (P ↔Q)istrueiffP hasthesametruth value as Q P Q ¬P (P ∧ Q) (P ∨ Q) (P → Q) (P ↔ Q) 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 0 1 51/59 Revision Turing Machines Language Cool stuff Computability Logic Review Connectives Negation (not) ¬P is true iff P is false Conjunction (and) (P∧Q) is true iff both P and Q are true Disjunction (or) (P∨Q)istrueiffP orQ istrue Implication (P → Q) is false iff P is true and Q is false Equivalence (P ↔Q)istrueiffP hasthesametruth value as Q P Q ¬P (P ∧ Q) (P ∨ Q) (P → Q) (P ↔ Q) 1 1 0 1 1 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 51/59 Revision Turing Machines Language Cool stuff Computability Logic Review Example Construct the truth table for X =(((P∧Q)∨¬Q)→((P∨Q)∧P)) P Q (P ∧ Q) ¬Q ((P ∧ Q) ∨ ¬Q (P ∨ Q) (P ∨ Q) ∧ P X 1 1 1 0 0 1 0 0 52/59 Revision Turing Machines Language Cool stuff Computability Logic Review Formalising English as logic On Friday morning Mary went for a walk, in the afternoon she went to work and on Saturday she stayed home while her house was being painted. Although John is not tall, John has a better chance of winning the next match of tennis, despite Mark’s experience. If Gromit is not in his kennel, then he is reading the paper. Increased spending overheats the economy Increased spending coupled with tax cuts overheats the economy 53/59 Revision Turing Machines Language Cool stuff Computability Logic Review Formalising English as logic On Friday morning Mary went for a walk, in the afternoon she went to work and on Saturday she stayed home while her house was being painted. (W ∧J ∧H ∧P) Although John is not tall, John has a better chance of winning the next match of tennis, despite Mark’s experience. If Gromit is not in his kennel, then he is reading the paper. Increased spending overheats the economy Increased spending coupled with tax cuts overheats the economy 53/59 Revision Turing Machines Language Cool stuff Computability Logic Review Formalising English as logic On Friday morning Mary went for a walk, in the afternoon she went to work and on Saturday she stayed home while her house was being painted. (W ∧J ∧H ∧P) Although John is not tall, John has a better chance of winning the next match of tennis, despite Mark’s experience. (¬T ∧W ∧E) If Gromit is not in his kennel, then he is reading the paper. Increased spending overheats the economy Increased spending coupled with tax cuts overheats the economy 53/59 Revision Turing Machines Language Cool stuff Computability Logic Review Formalising English as logic On Friday morning Mary went for a walk, in the afternoon she went to work and on Saturday she stayed home while her house was being painted. (W ∧J ∧H ∧P) Although John is not tall, John has a better chance of winning the next match of tennis, despite Mark’s experience. (¬T ∧W ∧E) If Gromit is not in his kennel, then he is reading the paper. (¬K → P) Increased spending overheats the economy Increased spending coupled with tax cuts overheats the economy 53/59 Revision Turing Machines Language Cool stuff Computability Logic Review Formalising English as logic On Friday morning Mary went for a walk, in the afternoon she went to work and on Saturday she stayed home while her house was being painted. (W ∧J ∧H ∧P) Although John is not tall, John has a better chance of winning the next match of tennis, despite Mark’s experience. (¬T ∧W ∧E) If Gromit is not in his kennel, then he is reading the paper. (¬K → P) Increased spending overheats the economy (S → E) Increased spending coupled with tax cuts overheats the economy 53/59 Revision Turing Machines Language Cool stuff Computability Logic Review Formalising English as logic On Friday morning Mary went for a walk, in the afternoon she went to work and on Saturday she stayed home while her house was being painted. (W ∧J ∧H ∧P) Although John is not tall, John has a better chance of winning the next match of tennis, despite Mark’s experience. (¬T ∧W ∧E) If Gromit is not in his kennel, then he is reading the paper. (¬K → P) Increased spending overheats the economy (S → E) Increased spending coupled with tax cuts overheats the economy ((S ∧ T ) → E ) 53/59 Revision Turing Machines Language Cool stuff Computability Logic Review Possible interpretations in English ¬P not P P does not hold it is not the case that P P is false (P ∧ Q) P and Q P but Q not only P but Q P while Q P despite Q P yet Q P although Q (P ∨ Q) P or Q P or Q or both P and/or Q 54/59 Revision Turing Machines Language Cool stuff Computability Logic Review Possible interpretations in English (P → Q) If P then Q Q if P P only if Q P is sufficient for Q Q is necessary for P P implies Q (P ↔ Q) P if and only if Q P iff Q P is necessary and sufficient for Q 55/59 Revision Turing Machines Language Cool stuff Computability Logic Review Be careful with disjunction! We need to be careful with the definition of disjunction: ▶ Inclusive “or”: (P ∨ Q) ▶ Exclusive “or”: (P ∨ Q) ∧ ¬(P ∧ Q) 56/59 Revision Turing Machines Language Cool stuff Computability Logic Review Be careful with disjunction! We need to be careful with the definition of disjunction: ▶ Inclusive “or”: (P ∨ Q) ▶ Exclusive “or”: (P ∨ Q) ∧ ¬(P ∧ Q) Examples: You can go to the airport by taxi or bus You can choose to save your money or your life The error is in the program or the sensor data The program or the sensor data are erroneous 56/59 Revision Turing Machines Language Cool stuff Computability Logic Review Be careful with disjunction! We need to be careful with the definition of disjunction: ▶ Inclusive “or”: (P ∨ Q) ▶ Exclusive “or”: (P ∨ Q) ∧ ¬(P ∧ Q) Examples: You can go to the airport by taxi or bus You can choose to save your money or your life The error is in the program or the sensor data The program or the sensor data are erroneous Inclusive 56/59 Revision Turing Machines Language Cool stuff Computability Logic Review Be careful with disjunction! We need to be careful with the definition of disjunction: ▶ Inclusive “or”: (P ∨ Q) ▶ Exclusive “or”: (P ∨ Q) ∧ ¬(P ∧ Q) Examples: You can go to the airport by taxi or bus You can choose to save your money or your life The error is in the program or the sensor data The program or the sensor data are erroneous Inclusive Exclusive 56/59 Revision Turing Machines Language Cool stuff Computability Logic Review Be careful with disjunction! We need to be careful with the definition of disjunction: ▶ Inclusive “or”: (P ∨ Q) ▶ Exclusive “or”: (P ∨ Q) ∧ ¬(P ∧ Q) Examples: You can go to the airport by taxi or bus You can choose to save your money or your life The error is in the program or the sensor data The program or the sensor data are erroneous Inclusive Exclusive Exclusive? 56/59 Revision Turing Machines Language Cool stuff Computability Logic Review Be careful with disjunction! We need to be careful with the definition of disjunction: ▶ Inclusive “or”: (P ∨ Q) ▶ Exclusive “or”: (P ∨ Q) ∧ ¬(P ∧ Q) Examples: You can go to the airport by taxi or bus You can choose to save your money or your life The error is in the program or the sensor data The program or the sensor data are erroneous Inclusive Exclusive Exclusive? Inclusive? 56/59 Revision Turing Machines Language Cool stuff Computability Logic Review Be careful with implication/equivalence! Sometimes in english the syntax and terms used do not reflect the logical meaning 57/59 Revision Turing Machines Language Cool stuff Computability Logic Review Be careful with implication/equivalence! Sometimes in english the syntax and terms used do not reflect the logical meaning “Eating fast-food is equivalent to aiding the destruction of the world’s rainforests” ▶ This looks like an equivalence, but the speaker actually means implication (it’s unlikely that they are trying to claim that destroying rainforests implies eating fast food.) 57/59 Revision Turing Machines Language Cool stuff Computability Logic Review Be careful with implication/equivalence! Sometimes in english the syntax and terms used do not reflect the logical meaning “Eating fast-food is equivalent to aiding the destruction of the world’s rainforests” ▶ This looks like an equivalence, but the speaker actually means implication (it’s unlikely that they are trying to claim that destroying rainforests implies eating fast food.) “I will give you a lift to the city, if you are going to the city” ▶ This is really an equivalence, not the implication that the sentence structure suggests. 57/59 Revision Turing Machines Language Cool stuff Computability Logic Review More examples Max is home and Claire is at the library Max is home or Claire is at the library Max is home if Claire is at the library Max is home only if Claire is at the library Max is home if and only if Claire is at the library Max is not home nor Claire is at the library Max is home although Claire is at the library Max is home unless Claire is at the library 58/59 Revision Turing Machines Language Cool stuff Computability Logic Review More examples Max is home and Claire is at the library Max is home or Claire is at the library Max is home if Claire is at the library Max is home only if Claire is at the library Max is home if and only if Claire is at the library Max is not home nor Claire is at the library Max is home although Claire is at the library Max is home unless Claire is at the library (H ∧ L) 58/59 Revision Turing Machines Language Cool stuff Computability Logic Review More examples Max is home and Claire is at the library Max is home or Claire is at the library Max is home if Claire is at the library Max is home only if Claire is at the library Max is home if and only if Claire is at the library Max is not home nor Claire is at the library Max is home although Claire is at the library Max is home unless Claire is at the library (H ∧ L) (H ∨ L) 58/59 Revision Turing Machines Language Cool stuff Computability Logic Review More examples Max is home and Claire is at the library Max is home or Claire is at the library Max is home if Claire is at the library Max is home only if Claire is at the library Max is home if and only if Claire is at the library Max is not home nor Claire is at the library Max is home although Claire is at the library Max is home unless Claire is at the library (H ∧ L) (H ∨ L) (L → H ) 58/59 Revision Turing Machines Language Cool stuff Computability Logic Review More examples Max is home and Claire is at the library Max is home or Claire is at the library Max is home if Claire is at the library Max is home only if Claire is at the library Max is home if and only if Claire is at the library Max is not home nor Claire is at the library Max is home although Claire is at the library Max is home unless Claire is at the library (H ∧ L) (H ∨ L) (L → H ) (H → L) 58/59 Revision Turing Machines Language Cool stuff Computability Logic Review More examples Max is home and Claire is at the library Max is home or Claire is at the library Max is home if Claire is at the library Max is home only if Claire is at the library Max is home if and only if Claire is at the library Max is not home nor Claire is at the library Max is home although Claire is at the library Max is home unless Claire is at the library (H ∧ L) (H ∨ L) (L → H ) (H → L) (H ↔ L) 58/59 Revision Turing Machines Language Cool stuff Computability Logic Review More examples Max is home and Claire is at the library Max is home or Claire is at the library Max is home if Claire is at the library Max is home only if Claire is at the library Max is home if and only if Claire is at the library Max is not home nor Claire is at the library Max is home although Claire is at the library Max is home unless Claire is at the library (H ∧ L) (H ∨ L) (L → H ) (H → L) (H ↔ L) (¬H ∧ ¬L) 58/59 Revision Turing Machines Language Cool stuff Computability Logic Review More examples Max is home and Claire is at the library Max is home or Claire is at the library Max is home if Claire is at the library Max is home only if Claire is at the library Max is home if and only if Claire is at the library Max is not home nor Claire is at the library Max is home although Claire is at the library Max is home unless Claire is at the library (H ∧ L) (H ∨ L) (L → H ) (H → L) (H ↔ L) (¬H ∧ ¬L) (H ∧ L) 58/59 Revision Turing Machines Language Cool stuff Computability Logic Review More examples Max is home and Claire is at the library Max is home or Claire is at the library Max is home if Claire is at the library Max is home only if Claire is at the library Max is home if and only if Claire is at the library Max is not home nor Claire is at the library Max is home although Claire is at the library Max is home unless Claire is at the library (H ∧ L) (H ∨ L) (L → H ) (H → L) (H ↔ L) (¬H ∧ ¬L) (H ∧ L) (L → ¬H ) 58/59 Revision Turing Machines Language Cool stuff Computability Logic Review More examples Max is home and Claire is at the library Max is home or Claire is at the library Max is home if Claire is at the library Max is home only if Claire is at the library Max is home if and only if Claire is at the library Max is not home nor Claire is at the library Max is home although Claire is at the library Max is home unless Claire is at the library (H ∧ L) (H ∨ L) (L → H ) (H → L) (H ↔ L) (¬H ∧ ¬L) (H ∧ L) (L → ¬H ) (H ∨ L) 58/59 Revision Turing Machines Language Cool stuff Computability Logic Review Announcements ▶ Assignment 2 ▶ Appendices (on extensions) are available ▶ Some test cases will be released to you this weekend ▶ Submission system will be available next week ▶ Week 10 quiz tests concepts from the Week 8 tutorial 59/59

Related Posts