Правило формирования

В математической логике правила формирования — это правила для описания того, какие строки символов , образованные из алфавита формального языка, являются синтаксически допустимыми в пределах языка. ^[1] Эти правила касаются только расположения и манипулирования строками языка. Они не описывают ничего другого о языке, например, его семантику (т. е. что означают строки). (См. также формальную грамматику ).

Формальный язык

Формальный язык — это организованный набор символов , существенной чертой которого является то, что он может быть точно определен в терминах только форм и местоположений этих символов. Такой язык может быть определен, следовательно, без какой-либо ссылки на какие-либо значения любого из его выражений; он может существовать до того, как ему будет назначена какая-либо интерпретация — то есть до того, как он обретет какое-либо значение. Формальная грамматика определяет, какие символы и наборы символов являются формулами в формальном языке.

Формальные системы

Формальная система (также называемая логическим исчислением или логической системой ) состоит из формального языка вместе с дедуктивным аппаратом (также называемым дедуктивной системой ). Дедуктивный аппарат может состоять из набора правил преобразования (также называемых правилами вывода ) или набора аксиом , или иметь и то, и другое. Формальная система используется для вывода одного выражения из одного или нескольких других выражений. Исчисления высказываний и предикатов являются примерами формальных систем.

Пропозициональная и предикатная логика

Правила формирования исчисления высказываний могут, например, иметь такую ​​форму:

• если мы принимаем Φ за пропозициональную формулу, мы также можем принять Φ за формулу; ${\displaystyle \neg }$
• если мы возьмем Φ и Ψ как пропозициональные формулы, мы также можем взять (Φ Ψ), (Φ Ψ), (Φ Ψ) и (Φ Ψ) также как формулы. ${\displaystyle \wedge }$ ${\displaystyle \to }$ ${\displaystyle \lor }$ ${\displaystyle \leftrightarrow }$

Исчисление предикатов обычно включает в себя все те же правила, что и исчисление высказываний, с добавлением квантификаторов, так что если мы возьмем Φ в качестве формулы пропозициональной логики, а α в качестве переменной , то мы можем взять ( α)Φ и ( α)Φ каждую в качестве формул нашего исчисления предикатов. ${\displaystyle \forall }$ ${\displaystyle \exists }$

Смотрите также

• Конечный автомат

Ссылки

1. Hinman, Peter (2005). Fundamentals of Mathematical Logic. AK Peters/CRC Press . Получено 17.11.2022 . Определение синтаксиса любого языка L следует общему шаблону. Сначала дается набор символов, и мы определяем L-выражение как любую конечную последовательность этих символов. Затем мы указываем один или несколько наборов L-выражений, которые мы считаем осмысленными. Осмысленные выражения обычно описываются как те, которые построены с помощью определенных правил или алгоритмов, и их набор характеризуется как наименьший набор выражений, который замкнут относительно этих правил формирования.