Формула или нет?

[Sinoid]

Здравствуйте! Помогите, пожалуйста, разобраться, что является формулой, а что нет. Вот в задачнике $((\neg P\rightarrow Q)\rightarrow(R\wedge(Q\vee S)))$ признается формулой, а $((P\leftrightarrow Q)\wedge R)\rightarrow(P\vee R)$ - нет. Хорошо, допустим, это из-за отсутствия внешних скобок, хотя это очень и очень спорное предположение: в теоретическом материале того же автора сказано, что если формула больше нигде не используется, то внешние скобки можно опускать. Но тогда почему не признается формулой $((P\vee\neg Q)\rightarrow(\neg P\wedge\neg R\wedge(Q\leftrightarrow R)))$???

[Mihr]

Sinoid в сообщении #1109039 писал(а):

Но тогда почему не признается формулой $((P\vee\neg Q)\rightarrow(\neg P\wedge\neg R\wedge(Q\leftrightarrow R)))$???

Возможно, потому что в подформуле $(\neg P\wedge\neg R\wedge(Q\leftrightarrow R))$ три терма соединены двумя знаками конъюнкции без скобок, указывающих на приоритет одной из конъюнкций. Чисто формально это некорректно.

[Ellan Vannin]

Надо смотреть на контекст. Вы по какому учебнику занимаетесь?

Рискну предположить, что во втором выражении (пусть это будет не формула, а выражение) играет роль значок эквиваленции $\leftrightarrow$.

Sinoid в сообщении #1109039 писал(а):

$((P\vee\neg Q)\rightarrow(\neg P\wedge\neg R\wedge(Q\leftrightarrow R)))$

Здесь снова знак эквиваленции, возможно всё из-за него. Но пока неясно, откуда вы это взяли.

[Sinoid]

Ellan Vannin в сообщении #1109043 писал(а):

Надо смотреть на контекст. Вы по какому учебнику занимаетесь?

Задачник Игошина. А контекст. Какой контекст? Задание: "Определите, является ли последовательность символов формулой" вот и весь контекст.

Mihr в сообщении #1109042 писал(а):

Возможно, потому что в подформуле $(\neg P\wedge\neg R\wedge(Q\leftrightarrow R))$ три терма соединены двумя знаками конъюнкции без скобок, указывающих на приоритет одной из конъюнкций

С одной стороны, в пользу вашего предположения говорит то, что в том комплекте учебник-задачник не определен приоритет операций, он компенсирован использованием скобок, но с другой стороны, это выражение оставалось бы не формулой только до доказательства ассоциативности конъюнкции, после доказательства оной это выражение превратилось бы в формулу, так что маловероятно, чтобы автор вставил бы, так сказать, временно неформулу, а потом бы тоже самое выражение чудным образом превратилось бы в формулу. Нет, тут что-то другое.

[arseniiv]

Sinoid в сообщении #1109144 писал(а):

после доказательства оной это выражение превратилось бы в формулу

Смотря насколько быть дотошным. Формулы-с-учётом-ассоциативности можно считать отдельным, более широким множеством строк, вместе с функцией перевода их в «правильные» формулы.

(Вообще вместо формул следовало бы рассматривать синтаксические деревья. Их намного труднее построить неправильно, если наложить разумные условия на их структуру. (Хотя разночтения у авторов вызовут и они.) Но описание работы с деревьями, видимо, займёт в учебниках ещё больше места, чем работа с формулами как строками символов… Несмотря на то, что вопрос парсинга строк не очень-то связан с логикой, его придётся освещать в любом случае — потому что в какой ещё курс его запихнуть?)

[Mihr]

Sinoid, тут смысл задания, как я пониманию, не в том, чтобы вспоминать, доказана ли уже ассоциативность конъюнкции или ещё не доказана. Смысл задания в том, чтобы дотошно проверить корректность синтаксиса. Я думаю так. Если Вы считаете иначе - что ж, дело Ваше.

[Sinoid]

Mihr в сообщении #1109154 писал(а):

Если Вы считаете иначе - что ж, дело Ваше.

уже

arseniiv в сообщении #1109149 писал(а):

разночтения

[Sinoid]

Ну а все-таки, как вы думаете, почему и $((P\leftrightarrow Q)\wedge R)\rightarrow(P\vee R)$ - не формула? Ведь внешние скобки можно опускать.

[Mihr]

Перечитайте Игошина. Посмотрите, что он называет формулой. Это разумнее, чем повторно задавать вопросы, возможные ответы на которые Вам уже дали.

Что касается меня, я своё мнение высказал:

Mihr в сообщении #1109154 писал(а):

Смысл задания в том, чтобы дотошно проверить корректность синтаксиса.

Если следовать букве известного мне определения формулы в исчислении высказываний, то никакие скобки опускать нельзя. В том числе внешние.

[Sinoid]

Mihr в сообщении #1109328 писал(а):

Это разумнее, чем повторно задавать вопросы, возможные ответы на которые Вам уже дали.

А я и не задаю повторно. Я писал:

Sinoid в сообщении #1109039 писал(а):

Хорошо, допустим, это из-за отсутствия внешних скобок, хотя это очень и очень спорное предположение

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

Mihr в сообщении #1109328 писал(а):

Перечитайте Игошина. Посмотрите, что он называет формулой.

Пожалуйста:

[Mihr]

Sinoid, я Вам рекомендую найти у Игошина определение формулы, а не позднейшие комментарии к нему. И ответить на вопрос совершенно формально - на основе определения. Ничего иного посоветовать не могу. Вообще, подобные вопросы малосодержательны: от Вас не требуется глубоких размышлений, требуется лишь продемонстрировать, что Вы усвоили определение. Именно об этом я Вам говорил уже дважды и говорю сейчас в третий раз. Это моё мнение по поводу данной "задачи". Возможно, ошибочное, но моё И повторять его в четвёртый раз я уже не стану
Всего хорошего.

[kernel1983]

Игошин определяет формулу алгебры высказываний следующим образом.

1. Любая пропозициональная переменная есть формула алгебры высказываний.
2. Пусть $F_1$ и $F_2$ - формулы алгебры высказываний. Тогда $\neg F_1$, $F_1 \wedge F_2$, $F_1 \vee F_2$, $F_1 \to F_2$ и $F_1 \leftrightarrow F_2$ - формулы алгебры высказываний.
3. Никаких других формул алгебры высказываний, кроме получающийся согласно пп. 1 и 2, нет.

Игошин доказывает теорему "Формулы $F_1$ и $F_2$ равносильны тогда и только тогда, когда формула $F_1 \leftrightarrow F_2$ тождественно истинна". Далее фигурируют равносильности с логическими константами, например, $P \vee 1 \simeq 1$. Но ей соответствует тавтология $( P \vee 1 ) \leftrightarrow 1$, однако, следуя Игошину буквально, можно сказать, что это вообще не формула. Поэтому более правильным было бы включить в определение не только пропозициональные переменные, но и логические константы $0$ и $1$.

Игошин особо подчёркивает, что внешние скобки у формулы можно опустить, если она не входит в состав другой формулы. Но это уже позже. А до этого внешние скобки обязательны. Именно поэтому и не признаётся формулой второе выражение из заглавного сообщения данной темы. Последняя формула не признаётся формулой из-за недостатка скобок (после доказательства ассоциативности конъюнкции и дизъюнкции лишние скобки негласно разрешается опускать).

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

[arseniiv]

kernel1983 в сообщении #1109705 писал(а):

2. Пусть $F_1$ и $F_2$ - формулы алгебры высказываний. Тогда $\neg F_1$, $F_1 \wedge F_2$, $F_1 \vee F_2$, $F_1 \to F_2$ и $F_1 \leftrightarrow F_2$ - формулы алгебры высказываний.

Без скобок?

[kernel1983]

arseniiv в сообщении #1109774 писал(а):

Без скобок?

Со скобками, конечно. Спасибо за замечание.
Поздно уже было.

[Sinoid]

Думал, тема уже затухла, но коль так...

kernel1983 в сообщении #1109705 писал(а):

Игошин особо подчёркивает, что внешние скобки у формулы можно опустить, если она не входит в состав другой формулы. Но это уже позже. А до этого внешние скобки обязательны. Именно поэтому и не признаётся формулой второе выражение из заглавного сообщения данной темы

Когда потом-то? Это происходит в рамках одного, так сказать, параграфа, или не параграфа, пункта, на какие он там части делит книгу. Я эту часть, естественно, и прочитал целиком. И начал закреплять задачами. А вы, что, один параграф книг читаете в несколько подходов?

kernel1983 в сообщении #1109705 писал(а):

(после доказательства ассоциативности конъюнкции и дизъюнкции лишние скобки негласно разрешается опускать).

А зачем вообще создавать путаницу в голове (повторюсь): сегодня не формула, завтра формула, а потом, студенты разные бывают по знаниям, может, он программу наперед знает, а ему сказки начинают рассказывать. Ну поставь ты вместо какой-нибудь дизъюнкции ту же импликацию и все, ответ будет верен и сейчас и потом (в рамках построения Игошина) и вопросов меньше будет.