What is meant by syntactically distinct hypotheses? While reading about Concept Learning, in Chapter 2 of the book Machine Learning by Tom M. Mitchell, I came across this term (syntactically distinct hypotheses). I tried looking it up on Google but I could not find any reasonable explanation for this term.
It will be really helpful if anyone can explain because this term is used in Machine Learning literature quite a number of times.
 A: So I think we can consider this as a Permutation problem,
From Harsha's example above,


*

*X can take 4 values (T/F/?/Φ)

*Y can take 5 values (0/1/2/?/Φ)

*Z can take 4 values (Y/N/?/Φ)


So number of syntactically distinct hypotheses = 4*5*4 =80
However, we usually only take Φ in 1 hypothesis:  < Φ , Φ , Φ > 
and not in combination (ex < Φ ,T, 2, N >),


*

*X can take 3 values (T/F/?)

*Y can take 4 values (0/1/2/?)

*Z can take 3 values (Y/N/?)

*Specific hypothesis: 1


So number of syntactically distinct hypotheses = 3*4*3 + 1 = 37
A: Syntactically distinct hypotheses - Each Hypothesis is unique because of the rules of operation.
In the example provided by Prof. Mitchell, we have the following attributes
(Sky, AirTemp, Humidity, Wind, Water, Forecast) for describing the target function. In section 2.3 of the book, he assumes the following number of valid values for each of the attributes, respectively (3,2,2,2,2,2). 
If we simply multiply them all, we get 96 distinct instances which are all distinct complete instances since they make use of all attributes.
If we go by the hypothesis design choice that each attribute can have one of the following types of values: 


*

*?(we consider any value of the attribute) or  

*a single value specified or

*a 0(we do not consider the attribute at all)


Then we get the following valid values for each of the attribute (5,4,4,4,4,4). That is, we add two more possible values to the attribute "? and 0".
Combinations of this would result in 5120 distinct combinations. We get 5120 different hypotheses by applying the rule for each attribute and hence the name syntactically distinct hypothesis.

Semantically distinct hypotheses - Each Hypothesis is unique because of the logic applied to form the hypotheses.
Here, Prof. Mitchell categorizes hypotheses that use all of the attributes to describe the Target function as Positive members (complete set) and those hypotheses that omit either one or multiple attributes as Negative members (empty set). 
Then we have 972 distinct positive instances and 4148 distinct negative instances.
Since the motive of the concept learner is to learn when Aldo gets to Enjoy his favourite water sport, we consider all hypotheses were he does not get to enjoy the water sport as one set of empty instance.
Hence, logically we have 972 distinct positive instances and One negative instance and therefore, a total of 973 semantically distinct hypotheses.
A: Was looking it up myself, I think I understood what it means. Here it goes:
If you have say 3 features X, Y, Z where X can take true/false value, Y can take 0/1/2 values and Z can take yes/no values, then number of distinct instances will be 2*3*3 = 18. You add two possible values for each feature 1. (?) wild card & 2. (Φ) null so your "syntactically distinct hypotheses" would be 4*5*5 = 100.
A little more, if you have only wild card for each feature and one instance for the empty set (Φ) you get "semantically distinct hypotheses"
i.e. 3*4*4 + 1 =  49.
Hope this helps.
