August 23rd, 2015, 08: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 (firstorder 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 PingPong 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 08:16 PM. 
August 24th, 2015, 07:47 AM  #2 
Global Moderator Joined: Dec 2006 Posts: 18,154 Thanks: 1421 
Is this problem from the textbook? Something quite similar is discussed in Chapter 6 of the textbook.

August 24th, 2015, 08: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:
Any ideas how I can do that with the strict firstorder logic rules?  
August 24th, 2015, 09:50 AM  #4 
Global Moderator Joined: Dec 2006 Posts: 18,154 Thanks: 1421 
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, 10: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 12:41 PM. 
August 24th, 2015, 07: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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
predicate logic  skaur  Applied Math  1  January 6th, 2014 06:51 PM 
Predicate Logic  mohitpd  Applied Math  0  October 26th, 2013 08:45 PM 
Predicate Logic  pavankumar.thati  Applied Math  0  April 16th, 2013 10:26 AM 
problem with natural deduction for predicate logic  drunkkat  Applied Math  14  July 31st, 2010 07:13 PM 
Sets and Predicate logic  Zhai  Applied Math  7  February 22nd, 2010 07:32 PM 