Уважаемые студенты! Вам предлагается пройти тест по теме "Логика первого порядка". Результаты теста будут показаны после завершения. Время выполнения заданий - 90 минут, всего 16 вопросов. Максимум за тест можно получить 50 первичных баллов. Перевод во вторичные баллы будет осуществлён после прохождения теста всеми студентами. Успехов! Фамилия Имя Группа Адрес электронной почты 1. Термы и формулы Пусть \( \Sigma=\{+^{(2)}, \cdot^{(2)}, -^{(2)}, 0^{(0)}, \leqslant^{(2)}\} \). Выберите все термы сигнатуры \( \Sigma \): \( x+y\cdot x \) \( x-y\cdot(z+1) \) \( x+y \) \( x-y\leqslant z \) \( (x+y)\cdot z \) \( 0-(x+y)^2 \) 2. Алгебраические системы Пусть \( \Sigma=\{+^{(2)}, \cdot^{(2)}, -^{(2)}, 0^{(0)}, \leqslant^{(2)}\} \). Выберите числовые множества, которые могут служить носителем алгебраической системы сигнатуры \( \Sigma \) со стандартными интерпретациями символов \( \Sigma \): \( \mathbb{N} \) \( \mathbb{Z} \) \( \mathbb{I} \) \( \omega \) \( 2\mathbb{Z} \) \( \mathbb{I}\cup\{0\} \) \( \mathbb{Q} \) 3. Алгебраические системы Среди перечисленных символов операций и предикатов выберите символы предикатов: \( \sqrt[3]{} \) \( \urcorner \) \( \wedge \) \( \geqslant \) \( \subseteq \) \( 1 \) \( \cup \) 4. Алгебраические системы Среди перечисленных символов операций и предикатов выберите символы операций: \( \sqrt{} \) \( \leqslant \) \( \vdots \) \( 1 \) \( - \) \( > \) \( + \) 5. Логическое следствие Пусть \( \Sigma=\{+^{(2)}, \cdot^{(2)}, \leqslant^{(2)}\} \). Выберите верные утверждения: \( x+y=z\ \vDash\ \exists z\ (z=x+y) \) \( x\cdot y+z=x\cdot y \), \( z+y=x\cdot z \), \( (x\cdot y+z)\cdot y\leqslant z+y \) \( \vDash \) \( (x\cdot y)\cdot y\leqslant x\cdot z \) \( x+y=z\cdot x \), \( y\cdot (x+z)=x\cdot x \) \( \vDash \) \( (x+y)\cdot (x\cdot x)=(z\cdot x)\cdot (y\cdot (x+z)) \) \( x\cdot y=z+x \), \( \forall z\ (z+x=x+y\cdot z) \) \( \vDash \) \( \exists y\ (x+y\cdot z=x\cdot y) \) 6. Равносильные формулы Выберите формулы сигнатуры \( \Sigma=\{\leqslant^{(2)}, +^{(2)}\} \), равносильные формуле \( \forall x\ (\exists y\ (x\leqslant y)\to\urcorner(z\leqslant x))\wedge\urcorner(y=z) \): \( \forall x\ \urcorner(\urcorner(y=z)\to\exists y\ (x\leqslant y)\wedge(z\leqslant y)) \) \( \forall x\ (\forall y\ \urcorner(x\leqslant y)\vee(z>x))\wedge\urcorner(y=z) \) \( \forall x\ \urcorner (\exists y\ (x\leqslant y)\wedge(z\leqslant x)\wedge(y=z)) \) \( \forall x\ ((\urcorner \exists y\ (x\leqslant y)\vee\urcorner(z\leqslant x))\wedge\urcorner(y=z)) \) \( \forall x\exists y\ ((x\leqslant y)\to\urcorner(z\leqslant x))\wedge\urcorner(y=z) \) 7. Исчисление предикатов Выберите верные утверждения про определённое на наших занятиях исчисление предикатов (ИП): Теоремами ИП являются только тождественно истинные формулы. ИП разрешимо. Существует алгоритм проверки формул ИП на доказуемость за конечное количество шагов. В ИП есть зависимые аксиомы. ИП противоречиво. ИП непротиворечиво. В ИП есть недоказуемые формулы. ИП независимо. ИП неразрешимо. Теоремами ИП являются тождественно истинные формулы. 8. Термы и формулы Пусть \( \Sigma=\{+^{(2)}, \cdot^{(2)}, -^{(2)}, 0^{(0)}, \leqslant^{(2)}\} \). Выберите все формулы сигнатуры \( \Sigma \): \( x\leqslant ((z+y=x)\to\exists y\ (y\leqslant z)) \) \( (x+y) \wedge (x\leqslant z-u) \) \( x+y\leqslant x\cdot z \) \( \forall x\ (x+y\cdot (z+0)) \) \( \exists z\ (x\leqslant z\cdot z_1) \) \( \urcorner (x+y=z+1) \) 9. Исчисление предикатов Пусть \( \Gamma=\{\Phi(x),\ \Psi(y),\ \Theta(z)\} \). Выберите верные соотношения: \( \Gamma\ \vdash\ \exists z\ (\Phi(x)\to\Psi(y)\vee\Theta(z)) \) \( \Gamma\ \vdash\ \exists u\ (\Phi(u)\wedge\Psi(u)\wedge\Theta(u)) \) \( \Gamma\ \vdash\ \Phi(u)\wedge\Psi(u)\wedge\Theta(z) \) \( \Gamma\ \vdash\ \Phi(z)\wedge\Psi(y)\wedge\Theta(x) \) \( \Gamma\ \vdash\ \exists x\ (\Phi(x)\vee\Psi(x)\vee\Theta(x)) \) \( \Gamma\ \vdash\ \exists x\ (\Phi(x)\vee\Psi(y)\vee\Theta(z)) \) 10. Термы и формулы Пусть \( \Sigma=\{+^{(2)}, \cdot^{(2)}, -^{(2)}, 0^{(0)}, \leqslant^{(2)}\} \), \( t(x,y,z)\leftrightharpoons (((x+y)\cdot x)-(y+(z-x)\cdot 0))\cdot z \), \( \mathfrak{A}=\langle \mathbb{Z}; \Sigma \rangle \). Найдите \( t^{\mathfrak{A}}(-4, 3, 5) \): 11. Термы и формулы Пусть \( \Sigma=\{+^{(2)}, \cdot^{(2)}, -^{(2)}, 0^{(0)}, \leqslant^{(2)}\} \). Выберите все атомарные формулы сигнатуры \( \Sigma \): \( x\cdot0=y+z_1 \) \( x+y\leqslant z-u \) \( \exists x\ (x\leqslant y+z) \) \( x+y^2\leqslant z \) \( \urcorner (x+0\leqslant z\cdot y) \) 12. Термы и формулы Пусть \( \Sigma=\{+^{(2)}, \cdot^{(2)}, -^{(2)}, 0^{(0)}, \leqslant^{(2)}\} \), \( \Phi(x,y)\leftrightharpoons \exists z\ ((x+z=y)\wedge\urcorner (z\leqslant0)) \), \( \mathfrak{A}=\langle \mathbb{Z}; \Sigma \rangle \). Выберите верные утверждения: \( \mathfrak{A}\vDash\Phi(1, 2, 4) \) \( \mathfrak{A}\vDash\Phi(3,5) \) \( \mathfrak{A}\vDash\urcorner\Phi(7,4) \) \( \mathfrak{A}\vDash\Phi(-2,0) \) \( \mathfrak{A}\vDash\Phi(-1,-1) \) \( \mathfrak{A}\vDash\Phi(4,2) \) \( \mathfrak{A}\vDash\Phi(2,-1)\to\Phi(4,2) \) \( \mathfrak{A}\vDash\Phi(3,8)\to\Phi(1,0) \) 13. Алгебраические системы Пусть \( \Gamma=\{\Phi_1, \ldots, \Phi_7\} \) - множество формул сигнатуры \( \Sigma=\{s^{(1)}, +^{(2)}, \cdot^{(2)}, 0^{(0)}\} \), где\( \Phi_1\leftrightharpoons \forall x\forall y\ ((s(x)=s(y))\to (x=y)) \),\( \Phi_2\leftrightharpoons \forall x\ \urcorner(s(x)=0) \),\( \Phi_3\leftrightharpoons \forall x\ (\urcorner(x=0)\to\exists y\ (x=s(y))) \),\( \Phi_4\leftrightharpoons \forall x\ (x+0=x) \),\( \Phi_5\leftrightharpoons \forall x\forall y\ (x+s(y)=s(x+y)) \),\( \Phi_6\leftrightharpoons \forall x\ (x\cdot0=0) \),\( \Phi_7\leftrightharpoons \forall x\forall y\ (x\cdot s(y)=x\cdot y+x) \).Выберите модели множества \( \Gamma \): \( \langle \omega; \Sigma \rangle \) \( \langle \mathbb{Z}; \Sigma \rangle \) \( \langle \omega\cup\{a\}; \Sigma \rangle \), где \( a\notin\omega \) \( \langle \omega\cup\{a,b\}; \Sigma \rangle \), где \( a,b\notin\omega \) 14. Исчисление предикатов Выберите формулы, которые являются теоремами исчисления предикатов: \( \Phi(x,y,x)\to\exists z\ \Phi(z,y,x) \) \( \forall z\ \Phi(x, z)\vee\Psi(y,z)\to\Phi(x,u)\vee\Psi(y,u) \) \( \urcorner\urcorner(\Psi\to\Theta\vee\Phi)\to(\Psi\to\Phi\vee\Theta) \) \( (\Phi\to\Psi)\to((\Psi\to\Theta)\to((\Phi\to\Psi)\to\Theta)) \) \( (\Phi\to\Theta)\to((\Phi\to\Psi)\to(\Phi\to\Psi\wedge\Theta)) \) \( \Phi(x,y,z)\to\exists z\ \Phi(z,y,z) \) \( \Phi(x,y,x)\to\exists z\ \Phi(z,y,z) \) \( y+x=x+y \) 15. Исчисление предикатов Пусть \( \{\Phi(x),\ \Psi(x, y),\ \exists y\ \Theta(y)\} \) - непротиворечивое множество формул. Выберите верные утверждения: \( \{\Phi(x),\ \Psi(x, y),\ \exists y\ \Theta(y),\ \forall z\ \urcorner\Phi(z)\vee\exists y\ \Theta(y)\} \) - непротиворечивое множество формул \( \{\Phi(x),\ \Psi(x, y),\ \exists y\ \Theta(y),\ \exists z\ (\Phi(z)\wedge\Psi(x,y))\} \) - непротиворечивое множество формул \( \{\Phi(x),\ \Psi(x, y),\ \exists y\ \Theta(y),\ \forall u\ \urcorner\Psi(u,y)\wedge\urcorner\Phi(x)\} \) - непротиворечивое множество формул \( \{\Phi(x),\ \Psi(x, y),\ \Theta(z)\} \) - непротиворечивое множество формул 16. Исчисление предикатов Известно, что \( \vdash\ \forall x\exists z\forall y\ \Phi(x, y, z, u) \), где \( \Phi \) - формула сигнатуры \( \Sigma \). Выберите верные утверждения: \( \vdash\ \forall w\exists x\ \urcorner\Phi(u, x, w, v) \) \( \vdash\ \exists z\forall x\ \Phi(w, x, z, u) \) \( \vdash\ \forall u\exists x\forall y\ \Phi(u, y, x, z) \) \( \vdash\ \forall u\forall x\exists z\forall y\ \Phi(x, y, z, u) \) \( \vdash\ \exists u\forall x\exists z\forall y\ \Phi(x, y, z, u) \) Пожалуйста, поделитесь впечатлениями об изученном курсе матлогики: