Понятие о формальных системах, языках и грамматиках

2355
0
08 июля 2009
(37.4.) Разберем что является элементами алфавита исчисления, представим систему аксиом для построения исчисления высказываний, дадим определение формального языка и формальной грамматики.

При рассмотрении формул алгебры логики не в качестве способа определения булевых функций, а в качестве составных высказываний, образованных из элементарных высказываний посредством логических связок37.4_html_5bfd23b2.gif, для этих формул составляется теория, которая носит название алгебры высказываний. В этом случае обозначается подмножество формул, именуемых аксиомами, и определяются правила вывода теорем. Разберем ряд терминов, которые имеют отношение к формальным системам.

О: Алфавит37.4_html_m2756962b.gifпредставляет собой конечное множество, в качестве элементов которого представлены символы (это могут быть буквы, цифры, знаки препинания и др.). Очередности37.4_html_m2756962b.gif, при этом запятые не используются.

Алфавит исчисления высказываний включает в себя переменные высказываний37.4_html_5bfd23b2.gifи скобок37.4_html_1fdd6433.gif.

Слова формулы есть37.4_html_1fdd6433.gif.

Чтобы построить исчисление высказываний следует также определить систему аксиом:

1)37.4_html_m17547154.gif

2)37.4_html_695ac039.gif

3)37.4_html_ce7cef0.gif

4)37.4_html_m271599ec.gif

5)37.4_html_m69615c51.gif

6)37.4_html_77ad69ab.gif

7)37.4_html_m7ba69b90.gif

8)37.4_html_2620962c.gif

Затем определяются правила вывода формул.

Аксиомы исчисления предикатов представляют собой аксиомы исчисления высказываний в совокупности с аксиомами:

9)37.4_html_29f35074.gif

10)37.4_html_m7847559e.gif

Предположим, что задан алфавит37.4_html_m2756962b.gifи, соответственно, определено множество37.4_html_m2756962b.gif.

О: В качестве формального языка37.4_html_m2756962b.gifпонимают произвольное подмножество37.4_html_m63d22926.gif

Для конструктивной характеристики формальных языков используют формальные системы, которые имеют специальный вид. Такие системы носят название формальных грамматик.

О: Формальная грамматика37.4_html_m2756962b.gif есть алфавит основных или терминальных символов,37.4_html_m2756962b.gif, который выводится из37.4_html_m7ce63bc6.gif. В случае, когда37.4_html_c1d6416.gif, грамматики37.4_html_m7362f793.gifназывают эквивалентными.

Таким образом, для исчисления высказываний37.4_html_556bb5e8.gifвключает правила вида37.4_html_556bb5e8.gifпредполагает наличие правил:37.4_html_m26997d0.gifЕго отличие от языка формул исчисления высказывний заключается в том, что он не имеет импликации.



(38.4.) Сформулируем понятие конечного автомата, обозначим входной алфавит, выходной алфавит, алфавит состояний, функцию переходов, функцию выходов, на рисунке изобразим граф переходов.
2687 0
(38.3.) Большинство графов, которые используются в приложениях (например, графы сортировок, классификаций) предполагают наличие диаграмм, именуемых деревьями. Связный неориентированный граф без циклов, в частности, предполагающий отсутствие петель и кратных ребер, именуют деревом. Несвязный неориентированный граф без цикла — лес, его связные компоненты являются деревьями.
7696 0
(38.2.) В рамках обозначенной темы рассмотрим случай определения связного неориентированного мультиграфа в качестве эйлерова и гамильтонова графа.
9686 0

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

    При использовании материалов данного сайта прямая и явная ссылка на сайт radiomaster.ru обязательна. 0.4419 s