1. Which of the following variables are free and which are bound?
   
   
• (( ∀ x) ( ∃ y) x+2y < z ∨( ∃ y) x+z=y)
  
  
• ( ∃ x) ( x+y = 3 ∧ ( ∀ y) x*(3-y) >0)


2. Write the quantifier calculus formulas corresponding to the following propositions:
• {a_n} is an increasing sequence,
• x is the smallest upper bound of a set A which is the subset of a set X ordered by relation ≤,
• there is no the greatest natural number,
• every number divided by 2 gives the reminder equal to 0 or 1,
• for every real number there is a number lower than it,
• there is no solution to the system of equations 3x-y = 0, x+y = 2.


3. Let's consider the structure <N, s, p>, where s(x,y,z) if and only if x+y = z and p(x,y,z) if and only if x*y = z.
• Write down a formula with one free variable x which is valid in this structure if and only if
  (a) when x=0 (b) when x=1 (c) when x=2,
• Write down a formula with two free variables x, y, which is valid in this structure if and only if x < y.


4. Draw a graphical illustration of the following propositional functions defined in the set of real numbers:
   
• x² + y² =1
• ( ∃ x) x² + y² =1
• ( ∀ x) x² + y² =1
• ( ∃ x) x*y =1


5. Which of the following formulas are tautologies of predicate calculus?
   
   
• (( ∀ x) α(x) ∨ ( ∀ x) β(x)) → ( ∀ x)( α(x) ∨ β(x))
  
  
• ( ∀ x)( α(x) ∨ β(x)) → (( ∀ x) α(x) ∨ ( ∀ x) β(x))

 

« previous section

next section »