There is an app called X in my iPhone which can tell you whether or not you have installed other apps before in this iPhone.
Then I installed an app A into my iPhone, and app X tells me A has not been installed before.
Then I uninstalled app A and then reinstalled it, and app X tells me A has been installed before.
How does X know that A has been installed or not?
And how can I completely remove app A and let app X tells me A has not been installed?
I have jailbreaked my iPhone, is there any app can do that?
I am not quite sure if I understand what you are asking for. But if you are asking, how X is doing what you described, here is my guess:
If your iPhone is jailbreaked, every app can have full access to the file system. There is nothing on your phone the app can't find.
Under these circumstances, it is pretty easy to check if an app has already been installed: Each app is installed in a path with a unique id. This id, however, changes with every reinstall (and maybe even if you update the app). What doesn't change is the bundle identifier in the app inside the app's info.plist. This means, if you see the same bundle identifier in two different folders over time, the app has been installed multiple times.
If app X is running in the background that is even easier: If the folder of app A is removed, the app has been uninstalled. As the phone is jailbreaked, app X can constantly check this.