My Math Forum Predicate Logic Problem
 User Name Remember Me? Password

 Applied Math Applied Math Forum

 August 23rd, 2015, 07:00 PM #1 Newbie   Joined: Aug 2015 From: Toronto Posts: 4 Thanks: 0 Predicate Logic Problem Hello, I am having particular trouble with the below problem. We are using Tourlakis' Logic Textbook and we must prove this statement using Hilbert style or Equational style proof (first-order logic), but any proof of any type would point me in the right direction. (∀x)(A→B) ≡ ((∃x)A) → B So far I have tried to use Ping-Pong Theorem to prove that 1. (∀x)(A→B) → (((∃x)A) → B) and 2. (((∃x)A) → B) → (∀x)(A→B) but I can't prove either 1. or 2. If anyone could provide insight, I would appreciate it. Last edited by programmer123; August 23rd, 2015 at 07:16 PM.
 August 24th, 2015, 06:47 AM #2 Global Moderator   Joined: Dec 2006 Posts: 19,059 Thanks: 1618 Is this problem from the textbook? Something quite similar is discussed in Chapter 6 of the textbook.
August 24th, 2015, 07:33 AM   #3
Newbie

Joined: Aug 2015
From: Toronto

Posts: 4
Thanks: 0

Hey skipjack,

Thanks for the reply. This problem is not from the textbook, it is from a sample exam, although you're right example 6.5.12 is a very similar problem.

Quote:
 Example 6.5.12: (∀x)(A ⇒ B), (∃x)A ⇒ (∃x)B (1) (∀x)(A ⇒ B) (hyp) (2) (∃x)A (hyp) (3) A[x := z] (aux hyp) (4) A[x := z] ⇒ B[x := z] (specialization) (5) B[x := z] (Modus Ponens) (6) (∃x)B (dual of specialization)
However, this leaves you with (∃x)B whereas in my original problem I need just B at the end. Also, the above is an implication whereas I need an equivalence (ie one side implies the other and vice-versa).

Any ideas how I can do that with the strict first-order logic rules?

 August 24th, 2015, 08:50 AM #4 Global Moderator   Joined: Dec 2006 Posts: 19,059 Thanks: 1618 Is the sample exam online? If not, can you post the question in full exactly as it appears in the sample exam?
 August 24th, 2015, 09:02 AM #5 Newbie   Joined: Aug 2015 From: Toronto Posts: 4 Thanks: 0 Here is a link to the exam. It is question 10. "Give an equational proof of ⊢ (∀x)(A → B) ≡ ((∃x)A) → B" This might also help. It is all of the rules of inference and absolute theorems we are allowed to use (note dnof means does not occur free). Last edited by skipjack; August 24th, 2015 at 11:41 AM.
 August 24th, 2015, 06:48 PM #6 Newbie   Joined: Aug 2015 From: Toronto Posts: 4 Thanks: 0 Hey skipjack and anyone else who was working on this problem. I actually just disproved this statement to be true and then found out it was indeed a typo by my teacher. Sorry if I caused anyone much pain over this problem. To disprove that (∀x)(A → B) ≡ ((∃x)A) → B is an absolute theorem, consider the following interpretation: Let D be {0, 1}, A be x=0, B be x=0, and xD be 1. ((∀x)(A → B) ≡ ((∃x)A) → B)D (∀x∈D)(x=0 → x=0) ≡ ((∃x∈D)x=0) → xD=0 (∀x∈D)(x=0 → x=0) ≡ ((∃x∈D)x=0) → 1=0

 Tags logic, predicate, predicate logic, problem

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post skaur Applied Math 1 January 6th, 2014 05:51 PM mohitpd Applied Math 0 October 26th, 2013 07:45 PM pavankumar.thati Applied Math 0 April 16th, 2013 09:26 AM drunkkat Applied Math 14 July 31st, 2010 06:13 PM Zhai Applied Math 7 February 22nd, 2010 06:32 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top