Дискретная математика

[fortis]

Помогите пожалуйста разобраться
Есть контрольная работа из 9 заданий
Все задания возрастают по сложности 1
Самое интересное что 7 последних я решил - а 1 и 2 нет
Просто в методичке рассмотрено решение сложных примеров а основы не разобраны, а там безе этого никак
Вот само задание(правда я не знаю как ставить логические знаки так что пишу словами или, и)

С помощью ДНФ и КНФ установить выполнимость формулы

A->B<->AилиBиС

Так вот собственно в чем вопрос:
1.В какой последовательности выполнять действия(скобок нет)
2.От чего зависит что использовать ДНФ или КНФ
3.И как определить выполняется формула или нет?

Буду благодарен если вы мне обЪясните как надо решать(или дадите ссылочку на инфу), а не просто напишете ответ.
Спасибо огромное заранее

[Brukvalub]

fortis писал(а):

1.В какой последовательности выполнять действия(скобок нет)

Попробуйте установить это методом проб и ошибок.

fortis писал(а):

2.От чего зависит что использовать ДНФ или КНФ

Думаю, что только от удобства, главное - чтобы слева и справа - одну и ту же.

fortis писал(а):

3.И как определить выполняется формула или нет?

Если равенство верно, то его левая и правая часть превратятся в одинаковые ДНФ или в одинаковые КНФ.

[fortis]

Спасибо за ответ
Но из вашего ответа я не понял одного
Где здесь левая а где правая часть?
могу предположить что части разделяются <->
Я прав?

[Brukvalub]

Я тоже так подумал.

[Yuri Gendelman]

fortis писал(а):

Просто в методичке рассмотрено решение сложных примеров а основы не разобраны,

Обычно в методичках есть ссылка на базовый учебник.

fortis писал(а):

1.В какой последовательности выполнять действия(скобок нет)

В логике, как и в ариметике, есть старшинство операций, посмотрите в учебнике. Как правило это, в порядке убывания: $\wedge , \vee , \rightarrow , \leftrightarrow $. Уточните в учебнике.

fortis писал(а):

2.От чего зависит что использовать ДНФ или КНФ

Судя по Вашему заданию, нужно дать два решения, с ДНФ и КНФ.

fortis писал(а):

3.И как определить выполняется формула или нет?

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

[luitzen]

1. Слышал, что в Алголе «или» было старше, чем «и».

3. Формула называется выполнимой, если существует такой набор значений переменных, на котором она истинна.

2. Лучше, конечно, с помощью ДНФ. Если удалось построить ДНФ, то это, в сущности, и означает, что формула выполнима. Тут я чуть-чуть привираю, конечно…
А вот определить выполнимость формулы, заданной КНФ, — это уже, извините, NP. Но если очень хочется, можно доделать эту КНФ до СКНФ и посчитать число конъюнктов. Если их будет меньше, чем $2^n$, где $n$ — число литералов в каждом конъюнкте, то формула выполнима.

[gefest_md]

fortis писал(а):

С помощью ДНФ и КНФ установить выполнимость формулы

ДНФ и КНФ не помню. В учебнике надо посмотреть. Так что здесь мы равны.
По поводу скобок нашел интересную формулу: A\to B\vee A\ , которая остается истиной, как бы не ставить скобки. Есть ли еще такие формулы ? Не знаю. Но интуиция подсказывает, что такое возможно с короткими формулами и не более чем с двумя переменными.

[fortis]

Спасибо за ответы!
Но я все-равно не сделал!
Может,если кто в курсе - объяснит поконкретнее?

[luitzen]

gefest_md писал(а):

Есть ли еще такие формулы ? Не знаю. Но интуиция подсказывает, что такое возможно с короткими формулами и не более чем с двумя переменными.

Как насчёт формулы $A\rightarrow A \lor B \lor C$?

[fortis]

Простите luitzen, я вас не понял. Можете пояснить?

[luitzen]

Указанная мною «формула» тождественно истинна, как ни расставляй в ней скобки. В ней больше двух переменных. В процитированном же фрагменте gefest_md cомневался в возможности существования такой формулы.

[fortis]

Спасибо за ответы
Может еще кто-нибудь что-нибудь скажет?

[fortis]

Народ ну помогите пожалуйста. Очень надо. Ниужели на таком интересном форуме никто не знает ДМ?

[Gordmit]

А как Вы пытались ее решать? Выяснили ли вы, что означает "формула выполнима"?
Может стоит попробовать выписать для нее таблицу истинности.