Explain what it means for a relation to be symmetric

Assignment Help Theory of Computation

Reference no: EM131060114

Q1)

a) Explain what it means for a relation to be symmetric.

b) Explain what it means for a proof system to be complete.

c) Explain what it means for a set of sentences, S, to semantically entail a sentence A.

Q2) Use natural deduction to prove the following arguments:

a) P∧Q, P→R ?Q∧R
b) P∨Q ?(P∨R)∨(Q∨S)
c) P→Q, Q→R, R→S ?P→S
d) ?P→(¬P→P)

Q3) Use tableaux to test whether the following arguments of QL are valid. If they are invalid, give a counterexample.

a) ∃xFx→∀xFx, ∃x¬Fx ?¬∃xFx
b) a=b, Fa↔Gb, ∃xFx ?∃xGx
c) ∀x∃y(Hxy∧Hyx) ?∃xHxx

Q4) Using the translation keys provided, translate the following collections of sentences of English into sentences of QL, then use tableaux to test whether the sentences are jointly consistent. If they are consistent, provide a model that shows this.

a) C(x,y): x causes y
(i) Everything has a cause
(ii) Nothing causes itself

b) Mx: x is a musician
Wx: x is a woman
m: Marshall Mathers
b: Beyonce
e: Eminem

(i) Eminem is Marshall Mathers
(ii) Beyonce is not Eminem
(iii) If Beyonce is not Marshall Mathers then every musician is a woman
(iv) Marshall Mathers is a musician
(v) Eminem is not a woman

Dx: x is a dog
Hx: x is a human
Lxy: x loves y
(i) All dogs are loved
(ii) All humans love something
(iii) Some humans do not love any dogs

Q5) Consider the following model, M:

D: {Luke, Leia, Han, ObiWan}
I(s) = Luke
I(l) = Leia
I(h) = Han
I(b) = ObiWan

I(o) = ObiWan
I(J): {Luke, ObiWan}
I(H): {<Luke, Leia>, <Leia, Luke>}
I(L): {<Luke, Leia>, <Han, Leia>}
I(S): {}

And the following translation scheme:
s: Luke Skywalker
l: Leia Organa
h: Han Solo
b: Ben Kenobi
o: ObiWan Kenobi
Jx: x is a Jedi
Hxy: x and y are siblings
Lxy: x loves y
Sx: x is a Sith

Translate the following sentences of English into QL and say whether they are true or false on M. Explain your answer.

a) Ben Kenobi is ObiWan Kenobi

b) If Luke and Leia are siblings, then Leia and Luke are siblings

c) Someone is both a Jedi and a Sith

d) Somebody loves someone who is their sibling

e) Han Solo loves only Leia

Reference no: EM131060114

Questions Cloud

How the team members performed collaboratively : How the team members performed collaboratively - Steps that were taken to ensure that team members focused on their tasks and listened to others and how suggestions were integrated from group members.

Calculate the tension in the rope joining : If Sue's mass is 56.0 kg and she falls 2.00 m in 10.0 s starting from rest, calculate the tension in the rope joining them. (Express your answer to three significant figures.) Calculate Paul's mass. (Express your answer to three significant figures..

Just fill out the template using my story : There lived a family with two little girls in a small grey house. The family lived happily with their children who lived to enjoy every bit of their life since they could get provided with all that needed.

Determine the layout and equipment for restaurant kitchen : Create a concept / theme for your restaurant. Identify the key aspects of your concept / theme, the ownership type, and the restaurant type. Provide a rationale for your decisions.

Explain what it means for a relation to be symmetric : Explain what it means for a relation to be symmetric. Explain what it means for a proof system to be complete.

Displacement current in the capacitor : A 4.0-cm-diameter parallel-plate capacitor has a 0.54 mm gap. What is the displacement current in the capacitor if the potential difference across the capacitor is increasing at 500,000V/s?

Magnetic field region spans : The wire is inclined at an angle of 75 degrees above the +x direction. What is the magnitude of the force on the wire, if the magnetic field region spans 15 cm in the x direction?

Demonstrate your knowledge of children : This assignment enables you to demonstrate your knowledge of children and how they learn in the area of language and literacy development, with a particular focus on reading and the links between oral language and reading development

Aluminum cup of a well-insulated calorimeter : You drop a 289-g silver figure of a polar bear into the 251-g aluminum cup of a well-insulated calorimeter containing 275 g of liquid water at 23.1°C. The bear's initial temperature is 95.7°C.

User Account

All Pages