IF the horn circuit wiring of a '56 F100 is the same as the '55/'57 cars, the same Battery + wire from the voltage regulator that powers the relay also powers the horns.
The switch contacts in the relay for the horns could be bad, but you replaced it already. Maybe the wire to the horn(s), the horns themselves, or their ground?. Were those parts recently painted?
Run a temporary jumper wire from the Positive terminal of the battery (or starter solenoid) directly to the power terminal on the horn(s) to see if they work.
.