2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 математическая логика (без лекций как без рук)
Сообщение03.06.2010, 06:11 


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

 Профиль  
                  
 
 Re: математическая логика (без лекций как без рук)
Сообщение03.06.2010, 07:20 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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 , только убедитесь, что у Вас формулы вводились именно так, там иногда скобочки чуть-чуть по-другому ставят.

 Профиль  
                  
 
 Re: математическая логика (без лекций как без рук)
Сообщение03.06.2010, 10:03 
Заблокирован по собственному желанию
Аватара пользователя


18/05/09
3612
ADRenaLIN в сообщении #327057 писал(а):
Потеряла тетрадь с лекциями, а в инете столько мути, что вся запуталась...
1. ... 2. ... 3. ... 4. ... 5. ... 6. ...
7. ... 8. ... 9. ...

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

 Профиль  
                  
 
 Re: математическая логика (без лекций как без рук)
Сообщение03.06.2010, 12:39 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
ADRenaLIN в сообщении #327057 писал(а):
как это все делается?

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

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

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

 Профиль  
                  
 
 Re: математическая логика (без лекций как без рук)
Сообщение03.06.2010, 12:55 


22/05/09

685
Дискретная математика в вопросах и задачах - 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. Там есть лекции и по другим математическим дисциплинам.

 Профиль  
                  
 
 Re: математическая логика (без лекций как без рук)
Сообщение03.06.2010, 13:15 


26/04/10
116
Mitrius_Math в сообщении #327155 писал(а):
Может быть, тут что-то найдёте.
P.S. Там есть лекции и по другим математическим дисциплинам.

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

 Профиль  
                  
 
 Re: математическая логика (без лекций как без рук)
Сообщение03.06.2010, 13:17 


22/05/09

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

 Профиль  
                  
 
 Re: математическая логика (без лекций как без рук)
Сообщение03.06.2010, 19:23 
Аватара пользователя


15/08/09
1458
МГУ
Вопрос в том, что даже если вы и потеряли лекции, то , что же вы делали на семинарах?! :?:
Вот скажем доказать , что функция ПРФ, надо просто написать её ПРО, что не так сложно.

 Профиль  
                  
 
 Re: математическая логика (без лекций как без рук)
Сообщение03.06.2010, 19:34 


26/04/10
116
maxmatem в сообщении #327307 писал(а):
Вопрос в том, что даже если вы и потеряли лекции, то , что же вы делали на семинарах?! :?:
Вот скажем доказать , что функция ПРФ, надо просто написать её ПРО, что не так сложно.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group