математическая логика (без лекций как без рук)

[ADRenaLIN]

Потеряла тетрадь с лекциями, а в инете столько мути, что вся запуталась...
1. требуется привести формулы к СДНФ и СКНФ. Очень помог бы хороший алгоритм.
2. требуется формулы привести к предваренной нормальной форме.
3. указать свободные и связанные вхождения переменных, свободные и связанные переменные в формулах
4. построить машину Тьюринга для вычисляющей функции $f=y-x$, $f=2x+2y$
5. доказать, что функция примитивно рекурсивна $f=2x+2y$
6. доказать, что функция частично рекурсивна $f=2x-y$
примерно так...
как это все делается? может примеры есть какие?

[Xaositect]

ADRenaLIN в сообщении #327057 писал(а):

Потеряла тетрадь с лекциями, а в инете столько мути, что вся запуталась...

А учебников Вам не рекомендовали?

ADRenaLIN в сообщении #327057 писал(а):

1. требуется привести формулы к СДНФ и СКНФ. Очень помог бы хороший алгоритм.

СДНФ = $\bigvee\limits_{(\sigma_1,\dots,\sigma_n)\colon f(\sigma_1,\dots,\sigma_n) = 1} x_1^{\sigma_1}x_2^{\sigma_2}\dots x_n^{\sigma_n}$
СКНФ, двойственно: $\mathop{\Big \&}\limits_{(\sigma_1,\dots,\sigma_n)\colon f(\sigma_1,\dots,\sigma_n) = 0} (x_1^{\bar{\sigma}_1}\vee x_2^{\bar{\sigma}_2}\vee\dots\vee x_n^{\bar{\sigma}_n})$
$x^1 = x$, $x^0 = \bar{x}$
Пример: $f(x,y,z) = \begin{cases}1, \text{если в наборе}\ (x,y,z)\ \text{2 или 3 единицы}\\ 0, \text{иначе}\end{cases}$

Единичные наборы ф-и: (0,1,1), (1, 0, 1), (1, 1, 0), (1, 1, 1). СДНФ $\bar{x}yz\vee x\bar{y}z\vee xy\bar{z}\vee xyz$
Нулевые наборы ф-и: (0,0,1), (0, 1, 0), (1, 0, 0), (0, 0, 0). СКНФ $(x\vee y\vee \bar{z}) (x\vee \bar{y}\vee z) (\bar{x}\vee y\vee z)(x\vee y\vee z)$

-- Чт июн 03, 2010 07:28:50 --

Про предваренную форму посмотрите пример тут: http://mathcyb.cmc.msu.ru/paper/zakh/LectLog6.pdf
Про свободные и связанные переменные тут: http://mathcyb.cmc.msu.ru/paper/zakh/LectLog2.pdf , только убедитесь, что у Вас формулы вводились именно так, там иногда скобочки чуть-чуть по-другому ставят.

[AKM]

ADRenaLIN в сообщении #327057 писал(а):

Потеряла тетрадь с лекциями, а в инете столько мути, что вся запуталась...
1. ... 2. ... 3. ... 4. ... 5. ... 6. ...

7. ... 8. ... 9. ...

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

[Профессор Снэйп]

ADRenaLIN в сообщении #327057 писал(а):

как это все делается?

Вы что, всерьёз предполагаете, что Вам восстановят здесь на форуме Ваши потерянные лекции? :)

Я, конечно, могу ответить на все Ваши вопросы, но на это потребуется пару дней труда, страниц 20-30 напечетанного текста... Оно мне надо? Думаю, что нет.

Единственное, что могу посоветовать: найдите себе хорошего репетитора из числа преподавателей матлогики. Или возьмите лекции у одногрупников и сделайте ксерокопию.

[Mitrius_Math]

Дискретная математика в вопросах и задачах - http://eek.diary.ru/p97394498.htm.
Лекции по теории алгоритмов - http://matem.uspu.ru/i/inst/math/subjects/A08DPPMAT_UPS2006D00.pdf.
Лекции по математической логике - http://matem.uspu.ru/i/inst/math/subjects/A05DPPMAT_UPS2002D00.pdf.
Лекции по вводному курсу математики - http://matem.uspu.ru/i/inst/math/subjects/A02DPPMAT_UPS2006D00.pdf.
Может быть, тут что-то найдёте.

P.S. Там есть лекции и по другим математическим дисциплинам.

[ADRenaLIN]

Mitrius_Math в сообщении #327155 писал(а):

Может быть, тут что-то найдёте.
P.S. Там есть лекции и по другим математическим дисциплинам.

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

[Mitrius_Math]

Вам, скорей всего, теорию алгоритмов надо смотреть.

[maxmatem]

Вопрос в том, что даже если вы и потеряли лекции, то , что же вы делали на семинарах?!
Вот скажем доказать , что функция ПРФ, надо просто написать её ПРО, что не так сложно.

[ADRenaLIN]

maxmatem в сообщении #327307 писал(а):

Вопрос в том, что даже если вы и потеряли лекции, то , что же вы делали на семинарах?!
Вот скажем доказать , что функция ПРФ, надо просто написать её ПРО, что не так сложно.

проехали... не надо ничего решать.
что я делала на семинарах? хм... я не помню, что я делала на семинарах 8 лет назад. что-то из логики я еще помню, но далеко не все. просто знакомая просила помочь, вот и пыталась.