Формальные системы. Алфавит, формулы, аксиомы, правила вывода. Разрешимость формальной системы. Интерпретация формальной системы.
Формальные системы. Алфавит, формулы, аксиомы, правила вывода. Разрешимость формальной системы. Интерпретация формальной системы. - раздел Математика, Порядок записи элементов множества не является существенным в отличие от записи элементов векторов, где порядок важен
Разре...
Разрешимость формальной с-мы:
Теория называется разрешимой, если в ней понятие теоремы эффективно, то есть существует эффективный процесс (алгоритм), позволяющий для любой формулы за конечное число шагов определить, является она теоремой или нет.
Интерпретация формальной системы:
Интерпретация представляет собой распространение исходных положений формальной системы на реальный мир . При интерпретации теоремы формальной системы становится обычными утверждениями о котором можно истины они или ложны .
Множество это совокупность определ нных различаемых объектов прич м таких что для каждого можно установить принадлежит этот объект данному... Множества обычно обозначаются заглавными латинскими буквами а элементы... Например...
Характеристическая функция
Характеристическая функцияили индикатор показывает принадлежность элементов множеству (обозначается или ).
Характеристическая функция пуст
Графическое доказательство
Для построения графического доказательства необходимо изобразить на диаграмме Эйлера-Венна все множества, входящие в тождество таким образом, что бы присутствовали их все возможные пересечения,
Отношения.
n-местным отношением R на множествах называется подмножество прямого произведения .
Если множества совпадают, то говорят что задаёт n-арные отношения.
При n = 2 о
Пустое отношение.
Операции на отношениях:
Пересечение
Объединение
Произведение
Дополнение:
Обратное отношение к R:
Алгебра логики
Алгебраическая система (алгебра) – пара <G, M>, где G - это множество элементов (носитель), а M – множество операций, заданн
Формулы алгебры логики.
Атомарные высказывания обозначаются маленькими буквами и называются пропозициональными (или булевыми) переменными. Формулы алгебры логики называются пропозициональные формулы.
Формулой явл
Таблицы истинности.
Логическое значение формулы определяется заданными логическими значениями входящих в неё элементарных высказываний.
Пример. x1=1, x2=1, x3=0. Определить значение формулы
Равносильные формулы
Две формулы алгебры логики называются равносильными, если они принимают одинаковые логические значения при любом наборе значений элементарных высказываний, входящих в
Двойственные функции
Функция g(x1,...,xn) = ¬f(¬x1,...,¬xn) называется двойственной функцией к функции f и обозначается f* .
Двойственные функции
Функция g(x1,...,xn) = ¬f(¬x1,...,¬xn) называется двойственной функцией к функции f и обозначается f* .
Полные системы функций (связок).
Система функций является полной, если любая n-арная булева функция может быть записана в виде пропозициональной формулы с использованием только функций входящих в эту систему.
Систе
Теорема о тождественной истинности формулы алгебры логики.
Для того, чтобы формула алгебры логики была тождественно истиной, необходимо и достаточно, чтобы каждая элементарная дизъюнкция её конъюнктивной нормальной формы содержала, по крайней мере, одно эл
Теорема о тождественной ложности формулы алгебры логики
Для того, чтобы формула алгебры логики была тождественно ложной, необходимо и достаточно, чтобы каждая элементарная конъюнкция её ДНФ содержала по крайней мере одно элементарное переменное высказыв
Совершенные нормальные формы.
Совершенная дизъюнктивная нормальная форма.
Элементарная конъюнкция называется правильной,если в неё каждая переменная входит не более одного раза,
Построения СДНФ и СКНФ.
Построение СДНФ:
1. Преобразование исходной формулы в ДНФ (см выше):
Шаг 1.
Преобразовать исходную формулу к равносильному ей виду
Преобразование ДНФ в СДНФ.
Шаг 3.
Если в ДНФ есть несколько одинаковых элементарных конъюнкций, то оставляем только одну - это преобразование приводит к равносильной формуле , т.к. xVx=x.
Преобразование КНФ в СКНФ.
Шаг 3.
Если в КНФ есть несколько одинаковых элементарных дизъюнкций , то оставляем только одну - это преобразование приводит к равносильной формуле ,т.к. x&x=x.
Построение совершенной конъюнктивной нормальной формы.
Пусть задана некоторая функция алгебры логики от n переменных. Рассмотрим отрицание этой функции и , так как полученная формула будет формулой алгебры логики, то разложим её по n переменным. Получе
Теорема о тождественной истинности формулы алгебры логики.
Для того, чтобы формула алгебры логики была тождественно истиной, необходимо и достаточно, чтобы каждая элементарная дизъюнкция её конъюнктивной нормальной формы содержала, по крайней мере, одно эл
Теорема о тождественной ложности формулы алгебры логики
Для того, чтобы формула алгебры логики была тождественно ложной, необходимо и достаточно, чтобы каждая элементарная конъюнкция её ДНФ содержала по крайней мере одно элементарное переменное высказыв
Теорема о логическом следствии
Формула алгебры логики f является логическим следствием формулы алгебры логики g,тогда и только тогда, если g f.
Доказательство.
Основные схемы доказательств
Схема 1. «Если x то y»
Доказательство теорем типа “если x, то y”.
Схема доказательства основана на следующем логическом следствии:
.
Методы минимизации
К настоящему времени широкое применение получили:
1. Расчетный метод (метод непосредственных преобразований).
2. Расчетно-табличный метод (метод Квайна-МакКласки).
3. Мет
Этапы минимизации
В общем случае минимизация ФАЛ, заданной в СДНФ, требует выполнения процедур следующих трех этапов:
1 этап - переход от СДНФ к сокращенной ДНФ (СокрДНФ). СокрДНФ - это форма ФАЛ, членами к
Исчисление предикатов
Наибольшее распространение в системах искусственного интеллекта получила формальная система, носящая название исчисления предикатов первого порядка (ИППП).
Алфавит ИППП состо
Значение формулы логики предикатов.
О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество M, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики преди
Описание машины Тьюринга
Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj&
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов