Задачи.

1.Проверить выполнимость, истинность и ложность фор-мулы В( х, у, f ²₁, f ¹₂,P ² )=P(f ²₁ ( х, у), f ¹₂( у)) в соответ-ствующих интерпретациях:

а) М = R; f ²₁(х,у) =( х²- 2xy); f ¹₂( y) = -y ²;P(x,y) = ’ x > y ‘;

б) М = R; f ²₁(х,у) =( х²- 2xy); f ¹₂( y) = -y ²;P(x,y) =’ x < y ‘;

2.Доказать, что

а) формула тождественно истинна тогда и только тогда, ког-да её отрицание тождественно ложно,

б) формула выполнима тогда и только тогда, когда её отри-цание не является тождественно ложным.

3. Доказать выполнимость формул:

а)$х Р(х); б)"х Р(х); в)$х"y (Р(х,y)&Р(y,х)); г)$х"y Р(х,y); д) $х$y(Р(х)& Р(y)).

4. Доказать или опровергнуть тождественную истинность формул:

а) $ хР(х)®" хР(х); б)Ø($ хР(х)®" xР(х)); в)$ х" y Р(х,y) ® " y$ х Р(х,y); г) " х$ y Р(х,y) ® $ y" х Р(х,y); д) "х Р(х) ® $ xР(х); е) ($ xAÚ$ xB)®$ x(AÚ B); ж)$x(A(x)&B® C(x)) ® " х(A(x)® Ø C(x))®ØB, где х не свободна в В; з)" x(A(x) ® Ø B(x)) ® Ø ($ х A(x) & " xB(x)).

5. Рассматриваются формулы, содержащие двухместный предикат Р², зависящий от переменных (х,у), а также кон-станты (а,b) ( X=(х,у); A=(а,b); F=Æ; P={P²}). Для формул вводится предметная область М={0,1}, множества перемен-ных X = (u,v); и констант A=(0,1); F=Æ; P = { u&v}). Оп-ределить в данной интерпретации истинностные значения следующих формул: а) $ х" у Р(x,у); б) $ х$ у Р(x,у); в)" х Р(x,b); г)$ х Р(x,а); д) $ х Р(x,b); е) Р(а,b); е) Р(b,b).

6. Привести пример формулы, общезначимой на множестве натуральных чисел N.

7. Привести пример формулы, опровержимой на множестве

натуральных чисел N.