рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Теорема о логическом следствии

Теорема о логическом следствии - раздел Математика, Порядок записи элементов множества не является существенным в отличие от записи элементов векторов, где порядок важен Формула Алгебры Логики F Является Логическим Следствием Формулы Алгебр...

Формула алгебры логики f является логическим следствием формулы алгебры логики g,тогда и только тогда, если g f.

Доказательство.

Пусть n - количество различных переменныхf, входящих в формулы g и f,и а n - мерный двоичный набор из 0 и 1.

Пусть gf ,покажем что .

Так какfявляется следствием из g,то на любом наборе а, если g(а)=1, то f(а)=1. Если же g(а)=0, то 0 f принимает значение 1 при любом значенииf (а).

Пусть g f,покажем, что gf.

f-следствие из g,если при любом наборе а,из g(а)=1 следует f(а)=1.

Пусть а,такой набор, что g(а)=1, тогда из того, что g f-тождественно истинная формула, её значение на наборе а должно равняться 1, а это для операции импликации может быть лишь тогда, когда f (а)=1.

Теорема доказана.

Аналогичным образом доказывается и более общая теорема.

Обобщённая теорема о логическом следствии

f1,f2,…,fmf тогда и только тогда, если f1 f2 ... fmf

Множество формул алгебры логики { f1,f2,…,fm } называется непротиворечивым,если существует по крайней мере один такой набор значений переменных, входящих в эти формулы, что все формулы из множества на этом наборе равны 1.

Множество формул алгебры логики { f1,f2,…,fm } называется противоречивым,если при всяком наборе значений переменных, входящих в эти формулы, по крайней мере одна из формул принимает значение 0.

Отсюда, { } -непротиворечиво, если f1 f2 ... fm=1по крайней мере на одном наборе и противоречиво, если f1 f2 ... fm=0для любого набора значений переменных.

 

– Конец работы –

Эта тема принадлежит разделу:

Порядок записи элементов множества не является существенным в отличие от записи элементов векторов, где порядок важен

Множество это совокупность определ нных различаемых объектов прич м таких что для каждого можно установить принадлежит этот объект данному... Множества обычно обозначаются заглавными латинскими буквами а элементы... Например...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Теорема о логическом следствии

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Характеристическая функция
Характеристическая функцияили индикатор показывает принадлежность элементов множеству (обозначается или ).   Характеристическая функция пуст

Графическое доказательство
Для построения графического доказательства необходимо изобразить на диаграмме Эйлера-Венна все множества, входящие в тождество таким образом, что бы присутствовали их все возможные пересечения,

Отношения.
n-местным отношением R на множествах называется подмножество прямого произведения . Если множества совпадают, то говорят что задаёт n-арные отношения. При n = 2 о

Пустое отношение.
Операции на отношениях: Пересечение Объединение Произведение Дополнение: Обратное отношение к R:

Алгебра логики
  Алгебраическая система (алгебра) – пара <G, M>, где G - это множество элементов (носитель), а M – множество операций, заданн

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

Таблицы истинности.
Логическое значение формулы определяется заданными логическими значениями входящих в неё элементарных высказываний. Пример. x1=1, x2=1, x3=0. Определить значение формулы

Равносильные формулы
Две формулы алгебры логики называются равносильными, если они принимают одинаковые логические значения при любом наборе значений элементарных высказываний, входящих в

Основные тождества (равносильные формулы) алгебры логики.
  xÙy=yÙx; xÚy=yÚx – коммутативность xÙ(yÙz)= (xÙy)Ùz; xÚ(yÚz)= (xÚy) Úz; - ассоциат

Двойственные функции
Функция 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 переменных по k переменным (k=n), можно воспользоваться таблицами истинности. Для построения

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

Разложение функций алгебры логики по к переменным.
  Теорема. Всякую логическую функцию f(x)=f(x1,x2,x3,…,xn) можно представить в виде  

Тавтологии и противоречия. Проблема разрешимости в алгебре логики. Логические следствия.
  Формула алгебры логики называется тождественно истиной, общезначимой или тавтологией,если она принимает значение 1 п

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

Теорема о тождественной ложности формулы алгебры логики
Для того, чтобы формула алгебры логики была тождественно ложной, необходимо и достаточно, чтобы каждая элементарная конъюнкция её ДНФ содержала по крайней мере одно элементарное переменное высказыв

Основные схемы доказательств
Схема 1. «Если x то y» Доказательство теорем типа “если x, то y”. Схема доказательства основана на следующем логическом следствии: .

Минимизация функций алгебры логики. Каноническая постановка задачи минимизации. Этапы минимизации. Методы минимизации.
Минимизация функций алгебры логики (ФАЛ) – это процедура нахождения наиболее простого представления ФАЛ в виде суперпозиции функций, составляющих фун

Методы минимизации
К настоящему времени широкое применение получили: 1. Расчетный метод (метод непосредственных преобразований). 2. Расчетно-табличный метод (метод Квайна-МакКласки). 3. Мет

Этапы минимизации
В общем случае минимизация ФАЛ, заданной в СДНФ, требует выполнения процедур следующих трех этапов: 1 этап - переход от СДНФ к сокращенной ДНФ (СокрДНФ). СокрДНФ - это форма ФАЛ, членами к

Формальные системы. Алфавит, формулы, аксиомы, правила вывода. Разрешимость формальной системы. Интерпретация формальной системы.
        Разрешимость формальной с-мы: Теория называется разрешимой, если в ней понятие теоремы эффективно

Исчисление предикатов
Наибольшее распространение в системах искусственного интеллекта получила формальная система, носящая название исчисления предикатов первого порядка (ИППП). Алфавит ИППП состо

Значение формулы логики предикатов.
О логическом значении формулы логики предикатов можно говорить лишь тогда, когда задано множество M, на котором определены входящие в эту формулу предикаты. Логическое значение формулы логики преди

Описание машины Тьюринга
Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj&

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги