My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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.
programmer123 is offline  
 
August 24th, 2015, 06:47 AM   #2
Global Moderator
 
Joined: Dec 2006

Posts: 17,910
Thanks: 1382

Is this problem from the textbook? Something quite similar is discussed in Chapter 6 of the textbook.
skipjack is offline  
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?
programmer123 is offline  
August 24th, 2015, 08:50 AM   #4
Global Moderator
 
Joined: Dec 2006

Posts: 17,910
Thanks: 1382

Is the sample exam online? If not, can you post the question in full exactly as it appears in the sample exam?
skipjack is offline  
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.
programmer123 is offline  
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
programmer123 is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

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 05:51 PM
Predicate Logic mohitpd Applied Math 0 October 26th, 2013 07:45 PM
Predicate Logic pavankumar.thati Applied Math 0 April 16th, 2013 09:26 AM
problem with natural deduction for predicate logic drunkkat Applied Math 14 July 31st, 2010 06:13 PM
Sets and Predicate logic Zhai Applied Math 7 February 22nd, 2010 06:32 PM





Copyright © 2017 My Math Forum. All rights reserved.