0.3 Discrete structures logic  (Page 14/23)

For example, in ∃x P(x, y), the variable x is bound while y is free. In ∀x [ ∃y P(x, y) ⋁Q(x, y) ], x and the y in P(x, y) are bound, while y in Q(x, y) is free, because the scope of ∃y is P(x, y). The scope of ∀x is [ ∃y P(x, y) ⋁Q(x, y) ].

How to read quantified formulas

When reading quantified formulas in English, read them from left to right. ∀x can be read as "for every object x in the universe the following holds" and ∃x can be read as "there exists an object x in the universe which satisfies the following" or "for some object x in the universe the following holds". Those do not necessarily give us good English expressions. But they are where we can start. Get the correct reading first then polish your English without changing the truth values.

For example, let the universe be the set of airplanes and let F(x, y) denote "x flies faster than y". Then

∀x∀y F(x, y) can be translated initially as "For every airplane x the following holds: x is faster than every (any) airplane y". In simpler English it means "Every airplane is faster than every airplane (including itself !)".

∀x∃ y F(x, y) can be read initially as "For every airplane x the following holds: for some airplane y, x is faster than y". In simpler English it means "Every airplane is faster than some airplane".

∃x∀y F(x, y) represents "There exist an airplane x which satisfies the following: (or such that) for every airplane y, x is faster than y". In simpler English it says "There is an airplane which is faster than every airplane" or "Some airplane is faster than every airplane".

∃x∃ y F(x, y) reads "For some airplane x there exists an airplane y such that x is faster than y", which means "Some airplane is faster than some airplane".

Order of application of quantifiers

When more than one variables are quantified in a wff such as ∃y ∀x P( x, y ), they are applied from the inside, that is, the one closest to the atomic formula is applied first. Thus ∃y ∀x P( x, y ) reads ∃y [ ∀x P( x, y ) ] , and we say "there exists an y such that for every x, P( x, y ) holds" or "for some y, P( x, y ) holds for every x".

The positions of the same type of quantifiers can be switched without affecting the truth value as long as there are no quantifiers of the other type between the ones to be interchanged.

For example ∃x ∃y ∃z P(x, y , z) is equivalent to ∃y ∃x ∃z P(x, y , z), ∃z ∃y ∃x P(x, y,z), etc. It is the same for the universal quantifier.

However, the positions of different types of quantifiers can not be switched.

For example ∀x ∃y P( x, y ) is not equivalent to ∃y ∀x P( x, y ). For let P( x, y ) represent x<y for the set of numbers as the universe, for example. Then ∀x ∃y P( x, y ) reads "for every number x, there is a number y that is greater than x", which is true, while ∃y ∀x P( x, y ) reads "there is a number that is greater than every (any) number", which is not true.

Well-formed formula for first order predicate logic

Not all strings can represent propositions of the predicate logic. Those which produce a proposition when their symbols are interpreted must follow the rules given below, and they are called wffs (well-formed formulas) of the first order predicate logic.