Логика первого порядка, 2025 г.

Уважаемый студент!

Вам предлагается пройти опрос по теме "Логика первого порядка". Результаты опроса будут показаны после завершения. Время выполнения заданий - 80 минут, всего 16 вопросов.

Максимум за опрос можно получить 50 баллов. Границы баллов для каждой оценки будут установлены после прохождения опроса всеми студентами.

Успехов!

Имя Фамилия

Группа

Выберите верные утверждения про определённое на наших занятиях исчисление предикатов (ИП):

ИП противоречиво.

В ИП есть зависимые аксиомы.

ИП независимо.

ИП разрешимо.

Теоремами ИП являются тождественно истинные формулы.

В ИП есть недоказуемые формулы.

ИП непротиворечиво.

ИП сигнатуры, содержащей символ n-местного предиката (n>2), неразрешимо.

Теоремами ИП являются только тождественно истинные формулы.

Существует алгоритм проверки формул ИП на доказуемость за конечное количество шагов.

Пусть \( \Sigma=\{+^{(2)}, \cdot^{(2)}, \leqslant^{(2)}\} \). Выберите верные утверждения:

\( 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\cdot y=z+x \), \( \forall z\ (z+x=x+y\cdot z) \) \( \vDash \) \( \exists y\ (x+y\cdot z=x\cdot y) \)

\( x+y=z\ \vDash\ \exists z\ (z=x+y) \)

\( 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)) \)

Пусть \( \Sigma=\{+^{(2)}, \cdot^{(2)}, -^{(2)}, 0^{(0)}, \leqslant^{(2)}\} \). Выберите все атомарные формулы сигнатуры \( \Sigma \):

\( \urcorner (x+0\leqslant z\cdot y) \)

\( x\cdot 0=y+z_1 \)

\( x+y^2\leqslant z \)

\( x+y\leqslant z-u \)

\( \exists x\ (x\leqslant y+z) \)

Пусть \( \Gamma=\{\Phi_1, \ldots, \Phi_7\} \) - множество формул сигнатуры \( \Sigma=\{s^{(1)}, +^{(2)}, \cdot{(2)}, 0^{(0)}\} \). Выберите модели множества \( \Gamma \).

\( \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) \)

\( \langle \mathbb{Z}; \Sigma \rangle \)

\( \langle \omega\cup\{a,b\}; \Sigma \rangle \), где \( a,b\notin\omega \)

\( \langle \omega; \Sigma \rangle \)

\( \langle \omega\cup\{a\}; \Sigma \rangle \), где \( a\notin\omega \)

Среди перечисленных символов операций и предикатов выберите символы предикатов:

\( \sqrt[3]{} \)

\( \geqslant \)

\( \wedge \)

\( 1 \)

\( \urcorner \)

\( \cup \)

\( \subseteq \)

Известно, что \( \vdash\ \forall x\exists z\forall y\ \Phi(x, y, z, u) \), где \( \Phi \) - формула сигнатуры \( \Sigma \). Выберите верные утверждения:

\( \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) \)

\( \vdash\ \forall w\exists x\ \urcorner\Phi(u, x, w, v) \)

\( \vdash\ \exists z\forall x\ \Phi(w, x, z, u) \)

Пусть \( \Gamma=\{\Phi(x),\ \Psi(y),\ \Theta(z)\} \). Выберите верные соотношения:

\( \Gamma\ \vdash\ \Phi(u)\wedge\Psi(u)\wedge\Theta(z) \)

\( \Gamma\ \vdash\ \Phi(z)\wedge\Psi(y)\wedge\Theta(x) \)

\( \Gamma\ \vdash\ \exists z\ (\Phi(x)\to\Psi(y)\vee\Theta(z)) \)

\( \Gamma\ \vdash\ \exists x\ (\Phi(x)\vee\Psi(y)\vee\Theta(z)) \)

\( \Gamma\ \vdash\ \exists u\ (\Phi(u)\wedge\Psi(u)\wedge\Theta(u)) \)

\( \Gamma\ \vdash\ \exists x\ (\Phi(x)\vee\Psi(x)\vee\Theta(x)) \)

Пусть \( \{\Phi(x),\ \Psi(x, y),\ \exists y\ \Theta(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)\} \) - непротиворечивое множество формул

\( \{\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))\} \) - непротиворечивое множество формул

Пусть \( \Sigma=\{+^{(2)}, \cdot^{(2)}, -^{(2)}, 0^{(0)}, \leqslant^{(2)}\} \). Выберите все термы сигнатуры \( \Sigma \):

\( x-y\leqslant z \)

\( x-y\cdot(z+1) \)

\( (x+y)\cdot z \)

\( x+y \)

\( 0-(x+y)^2 \)

\( x+y\cdot x \)

10.

Пусть \( \Sigma=\{+^{(2)}, \cdot^{(2)}, -^{(2)}, 0^{(0)}, \leqslant^{(2)}\} \). Выберите числовые множества, которые могут служить носителем алгебраической системы сигнатуры \( \Sigma \) со стандартными интерпретациями символов \( \Sigma \):

\( \omega \)

\( \mathbb{I}\cup\{0\} \)

\( 2\mathbb{Z} \)

\( \mathbb{I} \)

\( \mathbb{N} \)

\( \mathbb{Q} \)

\( \mathbb{Z} \)

11.

Выберите формулы, которые являются теоремами исчисления предикатов:

\( \Phi(x,y,x)\to\exists z\ \Phi(z,y,z) \)

\( \urcorner\urcorner(\Psi\to\Theta\vee\Phi)\to(\Psi\to\Phi\vee\Theta) \)

\( \Phi(x,y,z)\to\exists z\ \Phi(z,y,z) \)

\( \forall z\ \Phi(x, z)\vee\Psi(y,z)\to\Phi(x,u)\vee\Psi(y,u) \)

\( y+x=x+y \)

\( (\Phi\to\Theta)\to((\Phi\to\Psi)\to(\Phi\to\Psi\wedge\Theta)) \)

\( \Phi(x,y,x)\to\exists z\ \Phi(z,y,x) \)

\( (\Phi\to\Psi)\to((\Psi\to\Theta)\to((\Phi\to\Psi)\to\Theta)) \)

12.

Выберите формулы сигнатуры \( \Sigma=\{\leqslant^{(2)}, +^{(2)}\} \), равносильные формуле \( \forall x\ (\exists y\ (x\leqslant y)\to\urcorner(z\leqslant 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\ \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\exists y\ ((x\leqslant y)\to\urcorner(z\leqslant x))\wedge\urcorner(y=z) \)

13.

Пусть \( \Sigma=\{+^{(2)}, \cdot^{(2)}, -^{(2)}, 0^{(0)}, \leqslant^{(2)}\} \), \( \mathfrak{A}=\langle \mathbb{Z}; \Sigma \rangle \), \( t(x,y,z)\leftrightharpoons (((x+y)\cdot x)-(y+(z-x)\cdot 0))\cdot z \). Найдите \( t^{\mathfrak{A}}(-4, 3, 5) \):

14.

Среди перечисленных символов операций и предикатов выберите символы операций:

\( + \)

\( 1 \)

\( - \)

\( > \)

\( \sqrt{} \)

\( \vdots \)

\( \leqslant \)

15.

Пусть \( \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(3,5) \)

\( \mathfrak{A}\vDash\Phi(4,2) \)

\( \mathfrak{A}\vDash\urcorner\Phi(7,4) \)

\( \mathfrak{A}\vDash\Phi(-2,0) \)

\( \mathfrak{A}\vDash\Phi(2,-1)\to\Phi(4,2) \)

\( \mathfrak{A}\vDash\Phi(-1,-1) \)

\( \mathfrak{A}\vDash\Phi(1, 2, 4) \)

\( \mathfrak{A}\vDash\Phi(3,8)\to\Phi(1,0) \)

16.

Пусть \( \Sigma=\{+^{(2)}, \cdot^{(2)}, -^{(2)}, 0^{(0)}, \leqslant^{(2)}\} \). Выберите все формулы сигнатуры \( \Sigma \):

\( x\leqslant ((z+y=x)\to\exists y\ (y\leqslant z)) \)

\( \exists z\ (x\leqslant z\cdot z_1) \)

\( x+y\leqslant x\cdot z \)

\( (x+y) \wedge (x\leqslant z-u) \)

\( \urcorner (x+y=z+1) \)

\( \forall x\ (x+y\cdot (z+0)) \)

Пожалуйста, поделитесь впечатлениями об изученном курсе матлогики:

Логика первого порядка, 2025 г.

Опубликовано от Евгений Ефремов на 15.06.202315.06.2023

0 комментариев

Добавить комментарий Отменить ответ

Третий Приморский математический турнир, 2024-2025 уч. год

Второй Приморский математический турнир!

Школа юного математика в 2023-2024 уч. году!

Логика первого порядка, 2025 г.

Опубликовано от Евгений Ефремов на 15.06.202315.06.2023

0 комментариев

Добавить комментарий Отменить ответ

Похожие записи

Третий Приморский математический турнир, 2024-2025 уч. год

Второй Приморский математический турнир!

Школа юного математика в 2023-2024 уч. году!