Uninstall homebrew:

ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/uninstall)"

Then reinstall

ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"