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

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

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

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

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

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

1)

2)

3)

4)

5)

6)

7)

8)

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

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

9)

10)

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

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

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

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

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