Отправляет 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:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

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

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

Гордиенко Андрей Владимирович
Статус: Академик
Рейтинг: 6931
∙ повысить рейтинг » 		Гаряка Асмик
Статус: Профессионал
Рейтинг: 4555
∙ повысить рейтинг » 		Абаянцев Юрий Леонидович aka Ayl
Статус: Профессионал
Рейтинг: 1980
∙ повысить рейтинг »

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

Номер выпуска:211
Дата выхода:31.08.2010, 19:30
Администратор рассылки:Гаряка Асмик, Профессионал
Подписчиков / экспертов:64 / 49
Вопросов / ответов:1 / 1

Вопрос № 179733: Здравствуйте уважаемые Эксперты решите Пожалуйста задачи(по математической логике): Задачи в файле MS Word(.doc) (Задача) За правильное решение обещаю +150руб может чуть больше.

Вопрос № 179733:

Здравствуйте уважаемые Эксперты решите Пожалуйста задачи(по математической логике):
Задачи в файле MS Word(.doc) (Задача)

За правильное решение обещаю +150руб может чуть больше.

(Можно скан бумажки)

Отправлен: 16.08.2010, 19:05
Вопрос задал: kapezc, Посетитель
Всего ответов: 1
Страница вопроса »

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

Проверить выводимость в исчислении высказываний методом Куайна, методом редукции и методом резолюций.
├A\∕B→(¬A→B)
1) проверка выводимости методом Куайна
Пусть в выводимой формуле A\∕B→(¬A→B) A=0.Тогда 0\∕B→(¬0→B) =B→(1→B)=B→B=1 при любой интерпретации B.
Пусть A=1.Тогда (1\/В)→(0→B)=1→1=1 при любой интерпретации B .
Формула A\∕B→(¬A→B) является тавтологией, а значит, выводима.

2) проверка выводимости методом редукции
Пусть в некоторой интерпретации формула A\∕B→(¬A→B) имеет значение 0. Тогда в соответствии с таблицей истинности для импликации A\∕B=1, (¬A→B)=0.
Если (¬A→B), то аналогично A=0, B=0. Но тогда A\∕B=0. Следовательно, формула не может быть ложной ни при какой интерпретации, то есть является тавтологией. Значит, формула выводима.

3) проверка выводимости методом резолюций

Преобразуем в конънкцию предложений отрицание выводимой функции.

¬(A\∕B→(¬A→B))=¬(¬(A\∕B)\∕(A\∕B))=(A\∕B)&¬(A\∕B)
Множество предложений: {(A\∕B),¬(A\∕B)}

Резольвируем предложения.
1. (A\∕B)
2. ¬(A\∕B).
3. |_| по правилу резолюции из 1,2
Получена пустая формула, следовательно, формула A\∕B→(¬A→B) выводима.

2 Пусть Омега - множество людей. На множестве Омега заданы следующие предикаты:
1. E(x, y) = И <=> x и y – один и тот же человек;
2. P(x, y) = И <=> x родитель y;
3. C(x, y) = И <=> x и y – супруги;
4. M(x) = И <=> x – мужчина;
5. W(x) = И <=> x – женщина.
С использованием этих предикатов записать формулы, выражающие следующие утверждения:
X(x,y) – кузены

Люди являются кузенами, если они оба мужчины и имеют общего дедушку или бабушку. Сна чала сформулируем предикат G
G(x,y) = И <=> x пра-родитель y ∃z P(x, z)& P(z,y)
X(x,y) ∃z G(z,x) & G(z,y) &M(x) &M(y)

Привести формулу к предваренной форме

(∀x∃yQ(x,y))→((∃yQ(x,y))\∕R(x,y))
1) Избавление от импликаций, пользуясь эквивалентностью A→B= ¬A\∕B.
¬(∀x∃yQ(x,y))∨ ((∃yQ(x,y))\∕R(x,y))
2) Проносим отрицания под кванторы. Воспользуемся эквивалентностями ¬(∀x A(x))=∃x¬A(x)
Получаем (∃x∃y¬Q(x,y))∨((∃yQ(x,y)) \∕R(x,y))=(∃x∃y¬Q(x,y))∨∃yQ(x,y) \∕R(x,y)=
=∃y(∃x¬Q(x,y)∨Q(x,y)) \∕R(x,y)
3) Заменяем связанные переменные и выносим кванторы вперёд.
∃y(∃u¬Q(u,y)∨Q(x,y)) \∕R(x,y)
∃y∃u(¬Q(u,y)∨Q(x,y)) \∕R(x,y)
∃v∃u(¬Q(u,v)∨Q(x,v)) \∕R(x,y)
∃v∃u(¬Q(u,v)∨Q(x,v ) \∕R(x,y))

Показать примитивную рекурсивность функции f(x,y)

f(x,y)={3,2 ≤y≤6,x+1, иначе

s(x) = x+1 является простейшей
Осуществляя операцию суперпозиции функций f(x) = 0 и g(x) = x+1, получим функцию:
h(x) = g(g(g(f(x))))) = 0 + 1+1+1 = 3.
Функция Sg(x)={0,x=0, 1, иначе
примитивно-рекурсивна
Функция сложения примитивно-рекурсивна, значит, сумма конечного числа примитивно-рекурсивных функций примитивно-рекурсивна
То же самое можно сказать о произведении
Sg(x-2)+Sg(x-3)+Sg(x-4)+Sg(x-5)+Sg(x-6)=Sg26 ={1,2 ≤x≤6,0, иначе
Значит, Sg26 примитивно-рекурсивна
f(x,y) можно определить как
f(x,y)=3*Sg26+(1-Sg26)*(x+1)
f(x,y) примитивно-рекурсивна







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

Ответ отправил: Гаряка Асмик, Профессионал
Ответ отправлен: 30.08.2010, 15:08
Номер ответа: 262927

Оценка ответа: 5
Комментарий к оценке:
Спасибо за решение!

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

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

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

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

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

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

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

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