Составляющие формальной системы. Язык формальной теории. Синтаксис формального языка, отношение между формулой и подформулой, сложные и атомарные формулы (стр. 2 )

Логические связки. В логике логическими связками называют действия, вследствие которых порождаются новые понятия, возможно с использованием уже существующих. В качестве основных обычно называют конъюнкцию, дизъюнкцию, импликацию, отрицание.

6.  Квантификация переменных в логических формулах. Семантика кванторов. Свободные и связанные переменные, термы, открытые и замкнутые формулы.

Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. Чаще всего упоминают квантор всеобщности (обозначение: , читается: «для всех…», «для любого…» или «любой…») и квантор существования (обозначение: , читается: «существует…» или «найдется…»). В математической логике приписывание квантора к формуле называется связыванием квантора. В логике предикатов, большое значение имеют 2-е операции называемые:

1) Квантор "Существования"

2) Квантор "Общности"

Кванторы являются способом сокращенной записи конъюнктивных и дизъюнктивных формул. Необходимость связана с тем, что область определения предикатов может быть бесконечной.

Переменная в формуле является свободной, если не существует кванторной формы для этой переменной, которая является подформулой рассматриваемой формулы. Иначе переменная называется связанной соответствующим квантором.

Терм — выражение формального языка (системы), является формальным именем объекта или именем формы. Понятие терма определяется индуктивно. Термом называется символьное выражение: t(X1, X2, … , Xn), где t — имя терма, называемая функтор или «функциональная буква», а X1, X2, … , Xn — термы, структурированные или простейшие. В логике первого и второго порядков терм определяется рекурсивно следующим образом:

·  всякая индивидная константа есть терм;

·  всякая свободная переменная есть терм;

·  если fi — і-местная фунциональная константа и t1, t2, …, ti — термы, то fi(t1,t2,...,ti) также есть терм;

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

7.  Дистрибутивность и ассоциативность кванторов.

Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. Чаще всего упоминают квантор всеобщности (обозначение: , читается: «для всех…», «для любого…» или «любой…») и квантор существования (обозначение: , читается: «существует…» или «найдется…»). В математической логике приписывание квантора к формуле называется связыванием квантора. В логике предикатов, большое значение имеют 2-е операции называемые:

1) Квантор "Существования"

2) Квантор "Общности"

Кванторы являются способом сокращенной записи конъюнктивных и дизъюнктивных формул. Необходимость связана с тем, что область определения предикатов может быть бесконечной.

Ассоциативность.

Высказывание означает, что область истинности предиката P(x) совпадает с областью значений переменной x.

Высказывание означает, что область истинности предиката P(x) непуста.

8.  Нормальные формы логических формул: КНФ, ДНФ. Предварённая нормальная форма. Сколемовская стандартная форма.

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

Элементарная конъюнкция – формула, подформулами которой являются только конъюнктивные формулы, либо – атомарные формулы, либо отрицания атомарных формул.

Элементарная дизъюнкция – формула, подформулами которой являются только дизъюнктивные формулы, либо – атомарные формулы, либо отрицания атомарных формул.

ДНФ – формула, подформулами которой являются дизъюнктивные формулы, либо элементарные конъюнкции.

КНФ – формула, подформулами которой являются конъюнктивные формулы, либо – элементарные дизъюнкции.

Предварённой нормальной конъюнктивной (дизъюнктивной) формой называется формула, в которой нет некванторной подформулы, которая имеет кванторную подформулу, и в которой присутствует в качестве подформулы КНФ (ДНФ), которая не является подформулой формулы, не являющейся кванторной формулой или КНФ (ДНФ). Другими словами, предварённая нормальная форма – это формула, у которой все кванторы записаны слева, а оставшаяся подформула является КНФ(ДНФ), не включающей кванторов.

Говорят, что предваренная формула является - формулой, если ее кванторная приставка содержит n групп кванторов, причем первыми стоят кванторы существования. Если первыми стоят кванторы всеобщности, говорят о классе . (Аналогичные обозначения используются в теории алгоритмов для классификации арифметических множеств).

Пример: формула принадлежит классу , формула принадлежит классу , а формула вообще не находится в предваренной нормальной форме.

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

9.  Интерпретация логических формул. Таблицы интерпретаций. Зависимость мощности множества интерпретаций от мощности носителя модели формальной теории.

Модель логики предикатов задается множеством элементов (носителей) и множеством отношений на этом множестве элементов (сигнатурой). Любое множество предикатов задает хотя бы одну модель.

Каждая формула языка логики предикатов обозначает некоторой предикат. Интерпретацией формулы логики предикатов называется функция, которая каждой предметной переменной ставит в соответствие ее значение. Как можно будет увидеть из последующих примеров число интерпретаций формулы в модели равно mn, где n – есть число свободных предметных переменных в формуле, а m – мощность носителя модели. Число моделей, которые можно построить равно , где p – число предикатов (мощность сигнатуры модели), qi – число аргументов (арность) предиката i, m – мощность носителя модели.

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

Рассмотрим пример:

a	b	c
0	0	0	0	1	0
0	0	1	0	1	0
0	1	0	1	1	1
0	1	1	1	1	1
1	0	0	1	0	0
1	0	1	1	0	0
1	1	0	1	1	1
1	1	1	1	1	1

10.  Семантическая классификация логических формул. Общезначимость, нейтральность, противоречивость. Отношение равносильности формул.

Общезначимость

Формула называется общезначимой логической формулой тогда и только тогда, когда она обозначает функцию равнозначную константе 1 . Примером общезначимой формулы является формула ( p →p ).