Формула тождественно истинна?

[bonika]

Здравствуйте, начала решать задачу и что-то у меня не выходит, не могли бы вы мне подсказать
Задача следующая:
Доказать, что формала вида $\forall x_1...\forall x_m A(x_1,...,x_m)$, где $A(x_1,...,x_m)$ - бескванторная формула без функциональных символов и констант, тождественно истинна тогда и только тогда, когда она истинна в любой модели из $m$ элементов

-- Пт апр 01, 2011 22:25:09 --

Ясно, что формула является тождественно истинной, если она истинна при любых значениях входящих в неё переменных, но как провести само доказательство что-то не пойму...
у меня просто еще одна задача, но там в одноэлементной модели...значит это как то должно влиять...

[cyb12]

Ну в одну сторону это очевидно.
В обратную. Предположим противное. Что означает, что эта формула не является тождественно истинной? Это означает, что существует некоторая модель и некоторые значения $x_1,\ldots,x_m$ из нее, что $A(x_1,\ldots,x_m)$ ложна при этих значениях. Какую модель из $m$ элементов тогда нужно взять, чтобы показать, что условие истинности во всех $m$-элементных моделях не выполняется и получить противоречие?

[bonika]

Вы имеете ввиду конечную или бесконечную? Просто формула в данном случае станет тождественно ложной (противоречием), если я не ошибаюсь конечно, а чтобы на множестве $m$ это выполнялось множество должно быть бесконечным, а так как наше множество конечное, то противоречие нашему допущению, так? или я не правильно размышляю...

[Виктор Викторов]

bonika в сообщении #430399 писал(а):

на множестве $m$

Где это множество $m{?}$ Речь шла о множестве, в котором $m$ элементов.

bonika в сообщении #430399 писал(а):

Вы имеете ввиду конечную или бесконечную?

Конечную или бесконечную что? О чем речь?

Думаю, что Вы не совсем правильно понимаете, что такое $A(x_1,...,x_m)$ и $\forall x_1...\forall x_m A(x_1,...,x_m) {.}$
$A(x_1,...,x_m)$ - формула или высказывательная форма. Она сама по себе не является истинной или ложной. Теперь возьмем набор из $m$ элементов и подставим этот набор в $A(x_1,...,x_m)$. Формула превратилась в высказывание. Может быть истинное или ложное (если формула фиксирована, то это зависит только от набора переменных).
$\forall x_1...\forall x_m A(x_1,...,x_m)$ - высказывание (не формула) и оно истинно или ложно. Оно не зависит от набора переменных. Вопрос истинно онo или ложно решается именно так, как это расписал cyb12. Рассмотрим $A(x_1,...,x_m)$. Если по каждому из наборов из $m$ элементов, $A(x_1,...,x_m)$ превращается в истинное высказывание, то $\forall x_1...\forall x_m A(x_1,...,x_m)$ истиннo, а если «существует некоторая модель и некоторые значения $x_1,\ldots,x_m$ из нее, что $A(x_1,\ldots,x_m)$ ложна при этих значениях», то $\forall x_1...\forall x_m A(x_1,...,x_m)$ ложнo.

[Виктор Викторов]

Вот пример. Пусть область есть множество натуральных чисел. $A(x_1, x_2)=: x_1\leqslant x_2{,}$ тогда $\forall x_1\forall x_2A(x_1, x_2)$ есть $\forall x_1\forall x_2( x_1\leqslant x_2){.}$
Если $x_1=3$ и $x_2=7{,}$ то формула $x_1\leqslant x_2$ превращается в истинное высказывание $3\leqslant 7{.}$ Но формула $x_1\leqslant x_2$ превращается в ложное высказывание $6\leqslant 2{,}$ если $x_1=6$ и $x_2=2$.
Теперь о высказывании $\forall x_1\forall x_2( x_1\leqslant x_2){.}$ Истинно оно или ложно? Оно ложно, т. к. формула $x_1\leqslant x_2$ превращается в ложное высказывание $6\leqslant 2{,}$ если $x_1=6$ и $x_2=2$. Если бы для формулы $x_1\leqslant x_2$ такой пары, как $x_1=6$ и $x_2=2$ не существовало бы, то $\forall x_1\forall x_2( x_1\leqslant x_2)$ было бы истинным.

[bonika]

Большое спасибо за помощь, без вас я бы не справилась...Еще раз спасибо!