8. Теоремы логики и их использование в ииc.

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

Cложные высказывания можно разделить на частичные, которые связаны между собой с помощью слов: и, или, не, если — то. Элементарными называются высказывания, которые нельзя разделить на части. Логика высказываний оперирует логическими связями между высказываниями. При этом семантика высказываний не имеет значения. Элементарные высказывания рассматриваются как переменные логического типа, над которыми разрешены логические операции: - отрицание (унарная операция); ^ - конъюнкция (логическое умножение); - дизъюнкция (логическое сложение); -> - импликация (если — то); <-> - эквивалентность.

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

Приведем объяснение понятия предиката, данное Д. А. Поспеловым: «Под предикатом будем понимать некоторую связь, которая задана на наборе из констант или переменных.

Пример предиката: «Р больше Q». Если семантика Р и Q не задана, то о предикате сказать особенно нечего, только что он является антирефлексивным, антисимметричным и транзитивным. Но при задании семантики (областей определения) о предикате можно будет сказать больше. Иногда для утверждения об истинности или ложности предиката можно обойтись без подстановки.

Основными синтаксическими единицами логики предикатов являются константы, переменные, функции, предикаты, кванторы и логические операторы.

Имя в угловых скобках представляет собой тип синтаксического объекта. Определение каждого типа начинается с появления его имени в левой части записи. В правой части каждой записи приводятся возможные способы организации синтаксически корректных объектов определяемого типа. Альтернативные варианты разделены знаком | (ИЛИ). Функции, как и предикаты, задают некоторую связь между переменными или константами. Но эта связь или отношение не характеризуются истинностным значением. С помощью функции можно представить сложный объект. Функции могут являться аргументами предикатов (т.е. термами), а предикаты - нет.

Кванторы в логике предикатов необходимы для определения области действия переменных. Чтобы показать справедливость формулы для любого X, используется квантор общности: Х— «для любого X». Кроме квантора общности в логике предикатов есть квантор существования: Х — «существует хотя бы один такой X, что ...».

Формула, в которой все переменные связаны-предложение. Каждому предложению можно поставить в соответствие значение — «истина» или «ложь».

Операции в логике предикатов имеют неодинаковые приоритеты. Самый высокий приоритет имеет квантор общности, самый низкий — эквивалентность.

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

Теоре́ма Гёделя о неполноте́ и втора́я теоре́ма Гёделя[~ 1] — две теоремы математической логики о принципиальных ограничениях формальной арифметики и, как следствие, всякой формальной системы, в которой можно определить основные арифметические понятия: натуральные числа, 0, 1, сложение и умножение.

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

Вторая теорема утверждает, что если формальная арифметика непротиворечива, то в ней невыводима некоторая формула, содержательно утверждающая непротиворечивость этой арифметики.

Теорема корректности. Если существует вывод замкнутой формулы F из множества формул G, тогда G влечёт F.

Теорема полноты. Для любой замкнутой формулы F и любого множества предложений G, если G влечёт F, то существует вывод F из некоторого подмножества G.

Теоремы для одной переменной: A \/ 0 = A           4. A \/ Ā = 1         7. A · A = A

2. A \/ 1 = 1           5. A · 0 = 0         8. A · Ā = 0

3. A \/ A = A           6. A · 1 = 1         9.

Теоремы для двух и более переменных:

10. а) A \/ B = B \/ A,         б) AB = BA

переместительный закон, означает, что все входы логического элемента равнозначны.

11. а) A \/ B \/ C = A \/ (B \/ C) = (A \/ B) \/ C,

б) ABC = A(BC) = (AB)C – сочетательный закон.

12. а) A (B \/ C) = AB \/ AC, б) A \/ BC = (A \/ B)(A \/ C) – распределительный закон.