1. а) Приведите пример функции с обоснованием , которая сама по себе не образует полный класс , а вместе с f(x,y,z) = x \/ yz образует.

    б) Найдите все такие функции двух переменных или докажите , что их нет. в) Выразите функцию x NOR y (Стрелка Пирса) через x \/ yz и найденную в пункте а) функцию

2)Дано регулярное выражение (a + b)^(cd)^ ^ - "звездочка" , почему - то у меня она не печатается

а) Построить конечный автомат , распознающий это выражение б) Сколько десятибуквенных слов оно задает?

3.а)Введите соответствующие обозначения (например , P(x) означает , что x положительно) . Запишите при помощи исчисления предикатов следущие утверждения :

i) Если x > y , а y > z , то x > z
ii) Положительное число - это число больше нуля
iii) Если число больше некоторого положительного , то оно больше нуля

б) При помощи метода резолюций вывести iii из i и ii

4)Дана машина Тьюринга с начальным состоянием s , конечным f и набором правил s0 -> q0 ^R , s1->q1 ^R , q0 0->q0 0R, q0 1-> q0 1R , q0 ^-> f 1E , q1 1->q1 1R , q1 0->q1 0R , q1 ^-> f 0E; Крышечкой я обозначил символ "звездочка" , потому что почему-то некорректно отображается на форуме . R - сдвиг карретки вправо , L - влево , E - положение на месте. На каких строках она работает и что она с ними делает?

задан 8 Янв '17 14:43

изменен 8 Янв '17 15:33

Мое решение к 3 а)B(x,y) - x больше y , c = 0 , P(x) - x положительно i) ∀x∀y∀z(B(x,y)&B(y,z)->B(x,z)) , ii) ∀(P(x) <-> B(x,c)) ,iii) ∀x∀y(P(y)&B(x,y)->P(x))

(8 Янв '17 15:14) ExcountKek
10|600 символов нужно символов осталось
0

Тут у Вас многовато заданий для одного вопроса. Лучше было бы их разделить.

1) Аналогичная задача только что была разобрана здесь.

В данном примере функция $%f(x,y,z)=x\lor yz$% сохраняет 0 и 1, а также монотонна. При этом она не линейна и не самодвойственна. Для получения полной системы надо присоединить функцию, которая не принадлежит никакому из трёх классов $%T_0$%, $%T_1$%, $%M$%, но при этом она или линейна, или самодвойственна. Функций двух переменных с таким свойством имеется две: это отрицания переменных. Поэтому можно взять $%\bar{x}$%. Стрелка Пирса теперь выражается очень просто: полагаем $%z=y$%, выражая дизъюнкцию, и подставляем её в отрицание.

2) Язык, насколько я понимаю, такой: $%(a+b)^{\ast}(cd)^{\ast}$%. Он состоит из слов вида $%uv$%, где $%u$% -- произвольное слово от $%a,b$%, и $%v$% -- степень $%cd$%. Если $%v=(cd)^k$%, где $%0\le k\le5$%, то при фиксированном $%k$% имеем $%2^{10-k}$% слов длиной $%10-k$% от $%a,b$% на роль $%u$%. Таким образом, десятибуквенных слов в языке будет $%2^{10}+2^8+2^6+2^4+2^2+1=1365$%.

Автомат желательно предъявить детерминированный. Сделаем это так: из начального состояния $%q_0$% рисуем петли с метками $%a,b$%. Далее рисуем стрелку $%с$% в $%q_1$% и оттуда стрелку $%d$% в $%q_2$%. Из $%q_2$% идёт стрелка $%c$% в $%q_3$%, а из $%q_3$% стрелка $%d$% в $%q_2$%. Заключительными (терминальными) состояниями объявляем $%q_0$% и $%q_2$%.

3) Здесь всё зависит от того, какую сигнатуру мы выберем. Естественно было бы взять двуместный предикат $%B(x,y)$%, выражающий свойство $%x > y$%. Тогда условие транзитивности из пункта (i) записывается тривиально. Для пункта (ii) напрашивается идея ввести одноместный предикат $%P(x)$% для положительности, а также предметную константу $%0$%. Тогда вместе с предикатом из предыдущего пункта получится $%(\forall x)(P(x)\to B(x,0))$%. Саму мысль можно трактовать и по-другому: её можно понять как определение положительного числа, и тогда эквиваленция более уместна.

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

В пункте (iii) слово "некоторого" указывает на квантор существования. Если $%x$% произвольно, и оно больше некоторого положительного $%y$%, то оно больше нуля. Формула будет такая: $%(\forall x)((\exists y)(B(x,y)\&P(y))\to B(x,0))$%. Но можно истолковать и по-другому, так как однозначных правил перевода нет.

Метод резолюций в исчислении предикатов лучше разбирать по "методичкам". Я его никогда не использую, поэтому все технические детали лучше брать из рекомендованных лекторами источников.

4) Здесь мне пока непонятно, что означает символ E в составе команд машины.

ссылка

отвечен 8 Янв '17 16:19

@falcao , 4)E - положение на месте . Мое мнение , что данная машина Тьюринга работает только для алфавита A = {0 , 1} и строк , заканчивающихся на звездочку (иначе машина никогда не остановится) и вместо первого символа ставит звездочку , переходя в новое состояния якобы запоминая этот символ , далее копирует все символы (от второго до звездочки) , вместо звездочки ставит символ , отличный от первого (если была 1 ставит 0 и наоборот)

(8 Янв '17 16:22) ExcountKek

@falcao насчет второго , непринципиально ДКА мы построим или НКА . Я построил его так : (s - начальное , f - конечное состояние) из s провожу петли по a и b , также провожу ребро с весом eps(пустой символ) в конечное f , также из s провожу ребро с весом c в q1 , из q1 в f по d и из f в q1 по с . Хотелось бы узнать , правильно ли я сделал :)

(8 Янв '17 16:25) ExcountKek

@falcao насчет первого , в силу теоремы Поста достаточно хотя бы одной функции , которая не содержится в T0 , хотя бы одной не содержащийся в T1 и так далее для классов S , M , L. Исходная функция нелинейна и несамодвойственна , таким образом нам необязательно чтобы добавляемая функция была линейной или самодвойственной , так?

(8 Янв '17 16:35) ExcountKek

@ExcountKek: насчёт машины Тьюринга сейчас посмотрю. Я в "параллельном" вопросе ещё уточнял насчёт пустого символа. Вообще, в таких случаях полезно сообщать весь набор "условностей". Они очень часто могут отличаться.

С построением автомата проблем нет, но здесь также лучше пояснять, можно ли брать рёбра с пустыми метками. Я рассмотрел наиболее "жёсткий" вариант, когда нельзя, и когда автомат детерминированный.

В первом пункте нужно, чтобы добавляемая функция g не принадлежала никакому из трёх классов T0, T1, M, но принадлежала хотя бы одному из двух классов L, S -- чтобы {g} не была полна.

(8 Янв '17 17:00) falcao

@falcao как выразить стрелку Пирса через x \/ yz ?

(8 Янв '17 17:44) ExcountKek

@ExcountKek: у меня это написано в тексте. Стрелка Пирса теперь выражается очень просто: полагаем z=y, выражая дизъюнкцию, и подставляем её в отрицание.

(8 Янв '17 18:12) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×824
×81
×56
×52
×9

задан
8 Янв '17 14:43

показан
927 раз

обновлен
8 Янв '17 18:12

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru