Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Январь 2010   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Дискретная математика


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный платный хостинг на базе Windows 2008

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Гордиенко Андрей Владимирович
Статус: Профессор
Рейтинг: 4271
∙ повысить рейтинг » 		Гаряка Асмик
Статус: Практикант
Рейтинг: 1542
∙ повысить рейтинг » 		_Ayl_
Статус: Студент
Рейтинг: 1525
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Дискретная математика

Номер выпуска:162
Дата выхода:25.01.2010, 22:30
Администратор рассылки:Alexey G. Gladenyuk, Управляющий
Подписчиков / экспертов:114 / 45
Вопросов / ответов:4 / 5

Вопрос № 176147: Здравствуйте эксперты, есть такая задачка: Построить машину Тьюринга для распознавания последовательности символов на ленте. Построить машину Поста для той же задачи. Последовательно 01373 С машиной Тьюринга знаком вроде, то что ...

Вопрос № 176149: Здравствуйте эксперты, есть такая задачка: Построить автомат – распознаватель последовательности. 0-1-0-2-3 Из теорие автоматов ознакомился, но как распозновать последовательности так и не понял, подскажите пожалуйста как или дайте нужный м...
Вопрос № 176167: Уважаемые эксперты! Помогите решить 2 задачи по мат.логике. 1) Докажите, что следующая формула является тавтологией алгебры высказываний: ((P→R)∧(Q→S)∧(_R∨_S))→(_P∨_Q). _ отрицание 2) ...
Вопрос № 176169: Здраствуйте. Требуется ваша помощь. Используя при необходимости теорему дедукции и производные правила вывода, докажите, что следующие формулы являются теоремами формализованного исчисления высказываний: (F→(G→H))→(G&#...
Вопрос № 176147:

Здравствуйте эксперты, есть такая задачка:
Построить машину Тьюринга для распознавания последовательности символов на ленте. Построить машину Поста для той же задачи.
Последовательно 01373
С машиной Тьюринга знаком вроде, то что она двигает головку и меняет внутренние состояние и переписывает ленту, но что значит – распознавать последовательность.
Объясните или дайте ссылку на материал
Заранее спасибо.

Отправлен: 20.01.2010, 01:01
Вопрос задал: Tribak, Студент
Всего ответов: 1
Страница вопроса »

Отвечает Anton A., 4-й класс :
Здравствуйте, Tribak.



Определение свойства распознавания машиной Тьюринга и программа для последовательности 01373:

http://picasaweb.google.ru/ParkerSubscribe/RFPro#5428641747087982290


Для машины поста надо уточнить постановку задачи, т.к. "Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. " Т.е. символы 3 и 7 в явном виде недопустимы.

http://ru.wikipedia.org/wiki/Машина_Поста



С уважением, Антон.

Ответ отправил: Anton A., 4-й класс
Ответ отправлен: 20.01.2010, 05:25

Оценка ответа: 5

Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258762 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!

    Вопрос № 176149:

    Здравствуйте эксперты, есть такая задачка:
    Построить автомат – распознаватель последовательности.
    0-1-0-2-3
    Из теорие автоматов ознакомился, но как распозновать последовательности так и не понял, подскажите пожалуйста как или дайте нужный материал.

    Отправлен: 20.01.2010, 01:31
    Вопрос задал: Tribak, Студент
    Всего ответов: 1
    Страница вопроса »

    Отвечает Anton A., 4-й класс :
    Здравствуйте, Tribak.


    Решение задачи: http://picasaweb.google.ru/ParkerSubscribe/RFPro#5428650894017526082
    Идём подряд по символам входной последовательности, меняя состояния автомата согласно картинке. Если попали в конечное состояние и больше входный символов нет - цепочка принимается, иначе - не принимается.


    С уважением, Антон.

    Ответ отправил: Anton A., 4-й класс
    Ответ отправлен: 20.01.2010, 06:01

    Оценка ответа: 5

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258763 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!

    Вопрос № 176167:

    Уважаемые эксперты! Помогите решить 2 задачи по мат.логике.

    1) Докажите, что следующая формула является тавтологией алгебры высказываний:
    ((P→R)∧(Q→S)∧(_R∨_S))→(_P∨_Q).

    _ отрицание

    2) Приведите следующую формулу равносильными преобразованиями сначала к совершенной дизъюнктивной нормальной форме, а затем к совершенной конъюнктивной нормальной форме:
    F(X,Y,Z)=(X↔(Y∨_Z)∧_X)→(X∨_Y↔Z).

    ещё отрицание над (X↔(Y∨_Z) и (X∨_Y

    Заранее спасибо

    Отправлен: 20.01.2010, 21:01
    Вопрос задал: Антонов Владимир Дмитриевич, Посетитель
    Всего ответов: 2
    Страница вопроса »

    Отвечает _Ayl_, Студент :
    Здравствуйте, Антонов Владимир Дмитриевич.

    Везде далее логическое "И" буду обозначать знаком умножения или опускать вообще, а логическое "ИЛИ" - знаком "+". Отрицание - знаком апострофа перед символом.

    1. Тавтология - это формула, которая при любых значениях своих переменных обращается в одно и тоже значение. Проще всего это доказывается с помощью таблиц истинности.
    В вашем примере имеем формулу: ((P->R)(Q->S)('R+'S))->('P+'Q)
    Вот ее таблица истинности:
    P Q R S P->R Q->S 'R+'S A*B*C 'P+'Q D->E
    A B C D E
    0 0 0 0 1 1 1 1 1 1
    0 0 0 1 1 1 1 1 1 1
    0 0 1 0 1 1 1 1 1 1
    0 0 1 1 1 1 0 0 1 1
    0 1 0 0 1 0 1 0 1 1
    0 1 0 1 1 1 1 1 1 1
    0 1 1 0 1 0 1 0 1 1
    0 1 1 1 1 1 0 0 1 1
    1 0 0 0 0 1 1 0 1 1
    1 0 0 1 0 1 1 0 1 1
    1 0 1 0 1 1 1 1 1 1
    1 0 1 1 1 1 0 0 1 1
    1 1 0 0 0 0 1 0 0 1
    1 1 0 1 0 1 1 0 0 1
    1 1 1 0 1 0 1 0 0 1
    1 1 1 1 1 1 0 0 0 1

    В последней колонке видим, что при любых значениях переменных результатом будет ИСТИНА, т.е. исходная формула является тавталогией.

    2. F(x, y, z) = ('(x <-> (y+'z))*'x) -> ('(x+'y) <-> z)

    Преобразовывать будем по частям.
    A = x <-> (y+'z) = x(y+'z)+'x*'(y+'z) = x(y + 'z) + 'x('y*z) = x(y + 'z) + 'x'yz
    B = 'A = '(x(y + 'z) + 'x'yz) = '(x(y+'z))*'('x'yz) = ('x+'yz)(x+y+z) = x'yz+'xy+'xz+'yz = 'yz(x+1)+'xy+'xz = 'xy + 'xz + 'yz
    C = B*'x = ('xy + 'xz + 'yz)*'x = 'xy + 'xz + 'x'yz
    D = '(x+'y) = 'xy
    E = D <-> z = 'xy <-> z = 'xyz + '('xy)'z = 'xyz + (x+'y)'z = 'xyz + x'z + 'y'z
    F = C -> E = 'C + CE
    G = 'C = '('xy + 'xz + 'x'yz) = &# 39;('xy)*'('xz)*'('x'yz) = (x+'y)(x+'z)(x+y+'z) = (x+'y'z)(x+y+'z) = x+xy+x'z+x'y'z+'y'z = x+'y'z
    H = CE = ('xy + 'xz + 'x'yz)('xyz + x'z + 'y'z) = 'xyz
    F = G + H = x + 'y'z + 'xyz = x(1+yz) + 'y'z + 'xyz = x + 'y'z + yz(x+'x) = x + 'y'z + yz

    Получим нормальные формы:
    СДНФ = x*(y+'y)*(z+'z) + 'y'z(x+'x) + 'xyz = xyz + xy'z + x'yz + x'y'z + x'y'z + 'x'y'z + 'xyz = 'x'y'z + 'xyz + x'y'z + x'yz + xy'z + xyz

    СКНФ = ''(x + 'y'z + yz) = '('x*'('y'z)*'(yz)) = '('x*(y+z)*('y+'z)) = '('x('yz+y'z)) = '('x'yz+'xy'z) = ('('x'yz))*('('xy'z)) = (x+y+'z)(x+'y+z)

    Все.

    Ответ отправил: _Ayl_, Студент
    Ответ отправлен: 21.01.2010, 18:22

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258799 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!
    Отвечает Гаряка Асмик, Практикант :
    Здравствуйте, Антонов Владимир Дмитриевич.

    Тавтология доказывается методом от противного.
    Отрицанием целевой формулы A→B является A∧_B
    Применим его здесь.
    _(_P∨_Q)=P∧Q
    _((P→R)∧(Q→S)∧(_R∨_S))→(_P∨_Q)=(P→R)∧(Q→S)∧(_R∨_S)∧P∧Q
    По правилу вывода (P→R)∧P можно заменить на R, (Q→S)∧Q можно заменить на S
    Получится R∧S∧(_R∨_S)
    R∧S∧_(R∧S)
    A∧_A - противоречие, значит его отрицание - тавтология
    -----
    Я ни от чего, ни от кого не завишу.

    Ответ отправил: Гаряка Асмик, Практикант
    Ответ отправлен: 22.01.2010, 17:56

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258833 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!

    Вопрос № 176169:

    Здраствуйте. Требуется ваша помощь.

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

    (F→(G→H))→(G→(F→H)).

    Спасибо

    Отправлен: 20.01.2010, 21:31
    Вопрос задал: Ксенофонтов Матвей Юрьевич, Посетитель
    Всего ответов: 1
    Страница вопроса »

    Отвечает Гаряка Асмик, Практикант :
    Здравствуйте, Ксенофонтов Матвей Юрьевич.

    Теорема 1.10 (теорема дедукции). Если Г, A |- B, то Г |- A→B и обратно.
    Здесь |- значок, означающий, что в теории Г существует вывод формулы, идущей за значком
    Используем следующие аксиомы исчисления высказываний
    1. A →(B→A)
    2. (A→ (B→ C))→ ((A→B)→ (A→ C))
    3. (¬B→¬A)→ ((¬B→A)→B)
    4. (A,A→ B)→B Modus ponens(правило вывода)

    По теореме дедукции, если (F→(G→H))→(G→(F→H)), то (F→(G→H))|-(G→(F→H)) и обратно.
    В предположении, что (F→(G→H)), выведем G→(F→H)
    По 2 аксиоме исчисления высказываний (F→(G→H))→(F→G)→(F→H)
    По правилу вывода (F→G)→(F→H)
    По 1 аксиоме G→(F→G)
    По транзитивности (следствие теоремы дедукции)
    G→(F→G), (F→G)→(F→ H) |- G→(F→H)

    -----
    Я ни от чего, ни от кого не завишу.

    Ответ отправил: Гаряка Асмик, Практикант
    Ответ отправлен: 22.01.2010, 17:25

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 258832 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!

    Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2010, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2010.6.14 от 23.01.2010
    В избранное