2. (a) Prove that the following sequents cannot be valid: (i) ( PQ) V ~RE (~Q...

Question

Question

2. (a) Prove that the following sequents cannot be valid: (i) ( PQ) V ~RE (~Q ^ R) P (ii) PQ, R=~SE (PVR) = (Q V S)

math Advanced-Math

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

(i) P => Q is equivalent to ~P V Q

Therefore the expression ( P => Q ) V ~ R becomes ~P V Q V ~ R

Now ( ~ Q /\ R ) => P is equivalent to ~ ( ~Q /\ R ) V P

which is equivalent to Q V ~ R V P ( Demorgans law ) i.e P V Q V ~R ( Rearranging )

Therefore our sequent becomes

~P V Q V ~ R ⊢ P V Q V ~R

Truth table for ~P V Q V ~R

(TP v (QVER)) O E F F F LEE ELE LEE EEEE ELLE

Truth Table for P V Q V ~R

P F Q R R (P v (Q v R)) F F T FI F F F TF T F TT T T F F T T T FT TF T T T T T T

From the truth table values it is clear that P V Q V ~R is not provable from ~P V Q V ~ R. The sequent is not valid

(ii) Given P => Q

Therefore ~P V Q

Now R=> ~S is equivalent to ~R V ~S

combining these two conditions, we have

(~P V Q ) /\ ( ~R V ~ S)

Truth table for (~P V Q ) /\ ( ~R V ~ S) is as follows

P Q R S ((PvQ) A (RV -S)) T F F חד F F חד F T T F F T F T F F T T F F T. חד F T F T F T T F T T F T F T T T F T F F F T F חד

Now ( P V R ) => ( Q V S ) is equivalent to ~ ( P V R ) V (Q V S )

i.e ~P /\ ~ R V Q V S

Truth table for ~ P /\ ~ R V Q V S is as follows

Р Q R S ((PAR) v (Q v S)) F F F T F F F F T T F F F F T T F F T T F T F F T F T F T T F T T F T F T T T T T F F F F T F F T T

From the truth table values it is clear that ~ P /\ ~ R V Q V S is not provable from (~P V Q ) /\ ( ~R V ~ S).

Hence sequent is not valid.

Add a comment

Answer 2

Similar Homework Help Questions

5.104. Let p and q be irreducible elements of a PID R. Prove that R/(pq) =...

5.104. Let p and q be irreducible elements of a PID R. Prove that R/(pq) = R/(p) x R/(q) if and only if p and q are not associates.
2. Suppose P and Q are positive odd integers such that (PQ)-1. Prove that Qm] Pn]...

2. Suppose P and Q are positive odd integers such that (PQ)-1. Prove that Qm] Pn] P-1 0-1 0<m<P/2 0<n
1. Use full-truth table method to check if the following argument is valid -p•(qv-I), (p=q). (qvr)>p...

1. Use full-truth table method to check if the following argument is valid -p•(qv-I), (p=q). (qvr)>p 1: p=(-q=r) 2. Use short-cut truth table method to check if the following argument is valid p=(r v (p.-9). [=(qv(re-p)) 1:9= (pv (q.-1))

Prove that the language L = {a^pb^qc^r|p,q,r >=1 and pq = r} is not context free using pumping lemma. I honestly just...

Prove that the language L = {a^pb^qc^r|p,q,r >=1 and pq = r} is not context free using pumping lemma. I honestly just need help coming up with a string that works, thanks.
2. Are the following valid distance functions between pixel p [pz, ^^] and pixel q [q,...

2. Are the following valid distance functions between pixel p [pz, ^^] and pixel q [q, qyl. Prove your answers D(p, q) — р. + qr + Py + qy D(p, q) pr r + Py.qy D(p, q) 3D Р-Ру + qr-4y 2. Are the following valid distance functions between pixel p [pz, ^^] and pixel q [q, qyl. Prove your answers D(p, q) — р. + qr + Py + qy D(p, q) pr r + Py.qy D(p, q)...
3. Prove valid by a deductive proof: 1. S (TR) 2. R R 3. (V S)-(W...

3. Prove valid by a deductive proof: 1. S (TR) 2. R R 3. (V S)-(W T)/ .. V D~W 4. Prove valid by a deductive proof: 1. (B. L)VT 2. (BVC) (~LO M) 3.~M /.. T 5. Prove valid by a deductive proof: 1. E.(FVG) 2. (E.G)(HVI) 3. (~HV I)(E . F) /.. H= I

Use the formal rules of deduction of the Propositional Calculus to carefully prove the following ...

Use the formal rules of deduction of the Propositional Calculus to carefully prove the following sequents. Feel free to use earlier sequents in proofs of later ones by applying Sequent Introduction. (iv) Q ⇒ R ⊢ (P ∨ Q) ⇒ (P ∨ R)
Show that the following is a valid argument. 1. y V t 2. (w V u)...

Show that the following is a valid argument. 1. y V t 2. (w V u) ^(w V x) 3. (q V r) rightarrow w 4. s V p 5. (y ^r) rightarrow x 6. (p ^q) rightarrow (t V r)
Prove the validity of the following sequents in predicate logic, where F, G, P, and Q...

Prove the validity of the following sequents in predicate logic, where F, G, P, and Q have arity 1, and S has arity 0 (a ‘propositional atom’):

3. Prove the following argument by the indireet method: P-Q Q' v R SR WA S

3. Prove the following argument by the indireet method: P-Q Q' v R SR WA S

2. (a) Prove that the following sequents cannot be valid: (i) ( PQ) V ~RE (~Q...

Homework Answers

Add Answer to:
2. (a) Prove that the following sequents cannot be valid: (i) ( PQ) V ~RE (~Q...

Post as a guest

Earn Coins

5.104. Let p and q be irreducible elements of a PID R. Prove that R/(pq) =...

2. Suppose P and Q are positive odd integers such that (PQ)-1. Prove that Qm] Pn]...

1. Use full-truth table method to check if the following argument is valid -p•(qv-I), (p=q). (qvr)>p...

Prove that the language L = {a^pb^qc^r|p,q,r >=1 and pq = r} is not context free using pumping lemma. I honestly just...

2. Are the following valid distance functions between pixel p [pz, ^^] and pixel q [q,...

3. Prove valid by a deductive proof: 1. S (TR) 2. R R 3. (V S)-(W...

Use the formal rules of deduction of the Propositional Calculus to carefully prove the following ...

Show that the following is a valid argument. 1. y V t 2. (w V u)...

Prove the validity of the following sequents in predicate logic, where F, G, P, and Q...

3. Prove the following argument by the indireet method: P-Q Q' v R SR WA S

2. (a) Prove that the following sequents cannot be valid: (i) ( PQ) V ~RE (~Q...

Homework Answers

Add Answer to: 2. (a) Prove that the following sequents cannot be valid: (i) ( PQ) V ~RE (~Q...

Post as a guest

Earn Coins

Add Answer to:
2. (a) Prove that the following sequents cannot be valid: (i) ( PQ) V ~RE (~Q...