помогите доказать тавтологию предикатов!!!

[Val Crazy]

волосы дыбом, совсем запуталась:
является ли тавтологией данная ф-ла логики предикатов:
$\forall x (P(x)\vee B) \leftrightarrow B\vee (\forall x P(x))$
получить предваренную форму данной ф-лы логики предикатов:
$\exists x (P(x) \leftrightarrow \forall y Q(y)$

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

[AKM]

Val Crazy ,

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

Про кванторы \forall x, \exists x почитайте здесь (п.$5.\infty$). Где-то недалеко и нужные Вам стрелочки.
Если нужны явные пробелы --- пробуйте \: \; \quad

[Val Crazy]

тема все еще актуальна. ПОМОГИТЕ ПОЖАЛУЙСТА!!!!!!! последнее задание в контрольной никак не осилю

[TOTAL]

Val Crazy в сообщении #221755 писал(а):

является ли тавтологией данная ф-ла логики предикатов:
$\forall x (P(x)\vee B) \leftrightarrow B\vee (\forall x P(x))$

Что здесь такое тавтология? Вообще, поясните, что надо доказать.

[Чудо-в-перьях]

тавтология в смысле теорема. да, является! а вкаком исчислении надо ее доказать?

-- Ср июн 24, 2009 14:26:55 --

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

[sasha_vertreter]

Как нас учили, тавтология это высказывание, которое всегда истинное, вне зависимости от значений компонент.
По-моему тоже, самое простое - это построить таблицу, помня, что эквивалентность $A \leftrightarrow B$ истина, только когда, либо одновременно A - истинно и B- истинно, либо одновременно A - ложно, B - ложно.

В таблице должно стоять везде "истина" как результат всего выражения - тогда это тавтология.

[Чудо-в-перьях]

Для локики предикатов таблицы с истинно/ложно не строятся. Для них есть специальные аналитические табилцы, с правилами сведения сложных формул к атомарным, Каждом столбике такой таблицы в итоге должно получиться противоречие--тогда формула общезначима (явл. тавтологией). Хуже, если автору надо не построить таблицу, адоказать эту формулу в аксиоматическом исчислении предикатов. Тодг анад этим док-вом придется посидеть, я с ходу не придумаю))

[sasha_vertreter]

Цитата:

Для локики предикатов таблицы с истинно/ложно не строятся.

да, простите, ошибся!

вот здесь на 108 странице "формулы, истинные при любой интерпретации, называются общезначимыми".

"... что же касается логики предикатов, то для ее формул, вообще говоря, не существует общего способа (алгоритма) установить общезначимости. Общезначимость некоторых формул можно установить с помощью рассуждений"

там же на 107 странице приведен пример интерпретации открытой формулы... а еще правила сведения формулы к приведенной форме - может это поможет?

[Val Crazy]

Чудо-в-перьях в сообщении #224497 писал(а):

... Хуже, если автору надо не построить таблицу, адоказать эту формулу в аксиоматическом исчислении предикатов. Тодг анад этим док-вом придется посидеть, я с ходу не придумаю))

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

Цитата:

там же на 107 странице приведен пример интерпретации открытой формулы... а еще правила сведения формулы к приведенной форме - может это поможет?

спасибо, но не очень помогло... увы.

[Чудо-в-перьях]

sasha_vertreter в сообщении #224509 писал(а):

"... что же касается логики предикатов, то для ее формул, вообще говоря, не существует общего способа (алгоритма) установить общезначимости. Общезначимость некоторых формул можно установить с помощью рассуждений"

Аналитические таблички и есть своего рода алгоритмизированное рассуждение, позволяющее установить общезначимость для большинства формул логики предикатов. Пр них хорошо рассказано в книге Бочарова В.А., Марикниа В.И. "Основы логики".

Val Crazy, да, пример хитрый. Какие аксиомы в Вашем исчислении?

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

Val Crazy в сообщении #221755 писал(а):

получить предваренную форму данной ф-лы логики предикатов:
$\exists x (P(x) \leftrightarrow \forall y Q(y)$

У Вас здесь нечётное количество скобок.

Val Crazy в сообщении #221755 писал(а):

является ли тавтологией данная ф-ла логики предикатов: $\forall x (P(x)\vee B) \leftrightarrow B\vee (\forall x P(x))$

А здесь всё более чем просто. Надо проверить, истинно ли это высказывание при всех значениях. Но это эквиваленция (надеюсь Вы помните, когда она истинна), а справа у Вас дизъюнкция. Здесь легче сказать, когда она ложная. Именно тогда, когда оба члена её ложны. А это когда случиться? Если В ложно и существует такое х, что P(x) ложно. Ну а слева? Опять же, если существует такое х, что $(P(x)\vee B)$ ложно. А это когда? А дальше самостоятельно.

[Val Crazy]

Виктор Викторов в сообщении #224765 писал(а):

А здесь всё более чем просто. Надо проверить, истинно ли это высказывание при всех значениях. Но это эквиваленция (надеюсь Вы помните, когда она истинна), а справа у Вас конъюнкция. Здесь легче сказать, когда она ложная. Именно тогда, когда оба члена её ложны. А это когда случиться? Если В ложно и существует такое х, что P(x) ложно. Ну а слева? Опять же, если существует такое х, что $(P(x)\vee B)$ ложно. А это когда? А дальше самостоятельно.

спасибо за добрый совет, я уже почти к этому пришла. только я думала что это:

Цитата:

конъюнкция. Здесь легче сказать, когда она ложная. Именно тогда, когда оба члена её ложны

относится к дизъюнкции и знак соответствующий последней
а вот что у меня получается:
эквивалентность ложна, если ее члены принимают разные значения. рассмотрим все возможные случаи:
1. $ B $ - тавтология $ A B $, тогда результат очевиден.
2. $ P ( x ) $ - тождественно истинный предикат на произвольном множестве $ M $, тогда, исходя из определения дизъюнкции предикатов и правила связывания квантором общности, видим, что оба компонента эквиваленции истины.
3. $ P ( x ) $ - опровержим на $ M $, тогда, видим, используя те же определения, что оба компонента эквиваленции ложны.
итак эквиваленция оказалась истина во всех возможных случаях, следовательно данная формула является тавтологией.

ну конечно же:
$\exists x P(x) \leftrightarrow \forall y Q(y)$
а с этим проблемы, наведите, пожалуйста, на мудрую мысль:

$\exists x P(x) \leftrightarrow \forall y Q(y) \equiv ( \overline{\exists x P(x)} \vee \forall y Q(y) ) ( \overline{\forall y Q(y)} \vee \exists x P(x) ) \equiv \equiv ( \forall x \overline{P(x)} \vee \forall y Q(y) ) ( \exists y \overline{Q(y)} \vee \exists x P(x) )$

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

поправьте пожалуйста где неправа...

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

Val Crazy в сообщении #224827 писал(а):

Виктор Викторов в сообщении #224765 писал(а):

а справа у Вас конъюнкция.

относится к дизъюнкции и знак соответствующий последней

Опепятка. Простите.

Val Crazy в сообщении #224827 писал(а):

а вот что у меня получается:
эквивалентность ложна, если ее члены принимают разные значения. рассмотрим все возможные случаи:
1. $ B $ - тавтология $ A B $, тогда результат очевиден.

Не понял. Есть высказывание и оно истинно или ложно.
Но, если оно всегда истинно, то это тавтология.
Ваше высказывание эквиваленция всегда истинно. Ведь левая часть ложна тогда и только тогда, когда ложна правая часть.

Val Crazy в сообщении #224827 писал(а):

ну конечно же:
$\exists x P(x) \leftrightarrow \forall y Q(y)$
а с этим проблемы, наведите, пожалуйста, на мудрую мысль:

$\exists x P(x) \leftrightarrow \forall y Q(y) \equiv ( \overline{\exists x P(x)} \vee \forall y Q(y) ) ( \overline{\forall y Q(y)} \vee \exists x P(x) ) \equiv \equiv ( \forall x \overline{P(x)} \vee \forall y Q(y) ) ( \exists y \overline{Q(y)} \vee \exists x P(x) )$

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

поправьте пожалуйста где неправа...

А что Вам здесь дальше нужно? Вы избавились от эквиваленции. Ваше высказывание записано с помощью конъюнкции, дизъюнкции и отрицания. Куда Вы дальше собрались? Какова Ваша цель?

[Val Crazy]

Цитата:

Не понял. Есть высказывание и оно истинно или ложно.
Но, если оно всегда истинно, то это тавтология.
Ваше высказывание эквиваленция всегда истинно. Ведь левая часть ложна тогда и только тогда, когда ложна правая часть.

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

Цитата:

Ваше высказывание записано с помощью конъюнкции, дизъюнкции и отрицания.

это условия приведения к приведенной форме, а мне нужна предваренная (пренексная) - это когда все кванторы вынесены в левую часть. например для левой скобки последнего полученного выражения это выглядит так:

$\forall x \forall y ( \overline{P(x)} \vee Q(y) ) $

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

Val Crazy в сообщении #221755 писал(а):

является ли тавтологией данная ф-ла логики предикатов:
$\forall x (P(x)\vee B) \leftrightarrow B\vee (\forall x P(x))$

Val Crazy в сообщении #224872 писал(а):

Цитата:

Не понял. Есть высказывание и оно истинно или ложно.
Но, если оно всегда истинно, то это тавтология.
Ваше высказывание эквиваленция всегда истинно. Ведь левая часть ложна тогда и только тогда, когда ложна правая часть.

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

Тогда давайте разбираться от печки.
B – высказывание. Например: «Япония расположена в Европе». Высказывание может быть истинным или ложным (других вариантов не бывает). Высказывание про Японию ложное высказывание. Теперь предикат или высказывательная форма – это выражение истинное или ложное в зависимости от переменной. Например: x>3. Предикат превращается в ложное высказывание при x=1 (1>3 – ложное высказывание) и превращается истинное высказывание при x=6 (6>3 – истинное высказывание). Теперь квантор всеобщности. Если навесить квантор на предикат, то мы опять имеем высказывание. Например: $\forall x (x>3)$. При любом x x>3. Это ложное высказывание. Тавтология же – это всегда истинное высказывание. Ваш случай тавтология. Почему? Это эквиваленция и она истинна тогда и только тогда, когда левая и правая часть имеют одинаковые истинностные значения. Но правая часть дизъюнкция и она почти всегда истинна. Поэтому посмотрим, когда она ложна. Она ложна при ложном В и если найдется хотя бы одно значение x при котором P(x) ложно. Теперь проверьте, когда ложна левая часть.