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

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

Различные формы представления высказываний

Различные формы представления высказываний - раздел Математика, Теория множеств   Литерой - Называется Элемент Высказывани...

 

Литерой - называется элемент высказывания x или её отрицание.

Элементарной дизъюнкцией называется выражение следующего вида:

, (2.2)

где - литера.

Элементарной конъюнкцией называется выражение следующего вида:

, (2.3)

Дизъюнктивной нормальной формой (ДНФ) формулы называется выражение вида:

, (2.4)

где - элементарная конъюнкция.

 

Конъюнктивной нормальной формой (КНФ) формулы называется выражение вида:

, (2.5)

где - элементарная дизъюнкция.

Любую формулу можно представить в виде ДНФ или КНФ.

 

ПРИМЕР

Пусть дана формула

Требуется получить ДНФ и КНФ данной формулы.

Применяя формулы равносильности, получаем КНФ :

Применяя формулы равносильности, получаем ДНФ :

Совершеннойдизъюнктивной нормальной формой(СДНФ) формулы называется такая ДНФ, для которой выполняются следующие условия:

1. Все элементарные конъюнкции, входящие в ДНФ , различны.

2. Все элементарные конъюнкции, входящие в ДНФ , содержат литеры, соответствующие всем переменным.

3. Каждая элементарная конъюнкция, входящая в ДНФ , не содержит двух одинаковых литер.

4. Каждая элементарная конъюнкция, входящая в ДНФ , не содержит переменную и ее отрицание.

СДНФ можно получить двумя способами:

1. по таблице истинности;

2. с помощью равносильных преобразований.

Первый способ получения СДНФ рассмотрен выше. Рассмотрим второй способ, который состоит в следующем:

С помощью равносильных преобразований формулы получают ДНФ . При этом в полученной ДНФ возможны следующие ситуации:

1. Элементарная конъюнкция ДНФ не содержит переменную , тогда используются следующие равносильные преобразования:

2. Если в ДНФ входят две одинаковые элементарные конъюнкции, то используя следующее равносильное преобразование:

,

одну элементарную конъюнкцию можно отбросить.

3. Если элементарная конъюнкция ДНФ содержит одновременно переменную и ее отрицание, то используя следующие равносильные преобразования:

,

эту элементарную конъюнкцию можно отбросить

4. Если элементарная конъюнкция ДНФ содержит дважды переменную , то используя следующее равносильное преобразование:

,

одну переменную можно отбросить

СДНФ формулы существует в единственном виде.

 

ПРИМЕР

Получить СДНФ формулы

С помощью равносильных преобразований получаем СДНФ :

С помощью таблицы истинности получаем СДНФ :

 

СДНФ

Очевидно, что в результат двух способов совпадает.

 

Совершеннойконъюнктивной нормальной формой(СКНФ) формулы называется такая КНФ, для которой выполняются следующие условия:

1. Все элементарные дизъюнкции, входящие в КНФ , различны.

2. Все элементарные дизъюнкции, входящие в КНФ , содержат литеры, соответствующие всем переменным.

3. Каждая элементарная дизъюнкция, входящая в КНФ , не содержит двух одинаковых литер.

4. Каждая элементарная дизъюнкция, входящая в КНФ , не содержит переменную и ее отрицание.

СКНФ можно получить двумя способами:

1. по таблице истинности;

2. с помощью равносильных преобразований.

По первому способу по таблице истинности получаем СДНФ , а СКНФ можно получить, следуя следующему правилу

С помощью равносильных преобразований формулы получают КНФ . При этом в полученной КНФ возможны следующие ситуации:

1. Элементарная дизъюнкция КНФ не содержит переменную , тогда используются следующие равносильные преобразования:

2. Если в КНФ входят две одинаковые элементарные дизъюнкции, то используя следующее равносильное преобразование:

,

одну элементарную дизъюнкцию можно отбросить.

3. Если элементарная дизъюнкция КНФ содержит одновременно переменную и ее отрицание, то используя следующие равносильные преобразования:

,

эту элементарную дизъюнкцию можно отбросить.

4. Если элементарная дизъюнкция КНФ содержит дважды переменную , то используя следующее равносильное преобразование:

,

одну переменную можно отбросить.

СКНФ формулы существует в единственном виде.

 

ПРИМЕР

Получить СКНФ формулы

С помощью равносильных преобразований получаем СКНФ :

С помощью таблицы истинности получаем СДНФ :

 


СДНФ

Очевидно, что в результат двух способов совпадает.

 

СДНФ формулы можно получить из СКНФ , используя следующее правило:

 

 

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

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

Теория множеств

Объединением множеств А и В называется множество состоящее из всех тех и только тех элементов которые принадлежат хотя бы одному из множеств А... Пересечениеммножеств А и В называется множество состоящее из тех и только тех элементов которые принадлежат...

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

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

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

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

Теория множеств.
Множеством Sназывается объединение в одно целое объектов, хорошо различимых нашей мыслью или интуицией. Эти объекты называется элементами

Свойства подмножеств.
  1. Рефлексивность. Множество А является подмножеством множества А:

Алгебра теории множеств.
Для любых множеств А, В и С выполнимы следующие тождества: 1. Коммутативный закон

Решение уравнений алгебры множеств.
  Пусть дано уравнение вида: (23) где X - неизвестное множес

Кортеж.
Кортеж -это упорядоченный набор элементов. Кортеж характеризуется элементами и их порядком расположения. Элементы кортежа называются компонентами.Компон

График и свойства графика
Графиком называется множество пар. Графики могут задаваться : 1. перечислением:

Прямое (декартовое) произведение множество.
Прямым (декартовым) произведением множества и множества

Соответствия.
  Соответствием называется тройка вида . При этом

Отношения.
  Отношением называется пара вида такая, что ФÍM

Транзитивность.
Отношение называется транзитивным, если для всех x выполняется условие: xjy и yjz Þ xjz или Ф

Диаграммы Хассе.
Рассмотрим отношение частичного порядка: “быть подмножеством“ на множестве-степени М={1,2}. j=<F,M>, где Ф={<{Æ},{Æ}>;<{Æ},{1}>;<{Æ},{

Алгебраическое представление решеток.
Введем обозначения: sup(a,b)=ab, inf(a,b)=a

Формулы равносильности.
1) Коммутативность АVВ º ВVА А&В º В&А   2) Ассоциативность АV(ВVС) º (АVВ)VС А&(В&С) º (А&В) &С  

Выполнимость формулы алгебры логики
Все формулы алгебры логики делятся на три класс: 1. тождественно истинные или тавтологии: 2. тождественно ложные

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

Метод Квайна.
  Алгоритм метода Квайна включает в себя следующие этапы: 1. Любая формула

Метод минимизирующих карт.
Алгоритм метода минимизирующих карт включает в себя следующие этапы: 1. Любая формула приводится к СДНФ. 2. Составляется таблица всевозможных сочетаний переменных. 3. Из

Метод минимизации с помощью карт Вейча.
  Алгоритм метода карт Вейча включает в себя следующие этапы: 1. Любая формула приводится к СДНФ. 2. Составляется карта Вейча. Карта Вейча – это таблица всех возможн

Булевые функции и их свойства.
  Булевой функцией называется функция n переменных, которая принимает значение 1 или 0, а так же ее аргументы тоже принимают значение 1 или 0. Булевая фу

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

Логика предикат.
  Предикат - это сложное высказывание, в котором аргументы принимают значение и

Равносильные формулы логики предикатов.
  Две формулы логики предикатов и

Матрицей инцидентности
Матрица инцидентности - это матрица вершин и инцидентных им дуг. Дуга инцидентна вершине, если эта дуга исходит или заходит в данную вер

Матрицей смежности
Смежные дуги – это дуги инцидентные одной вершине. Смежные вершины – вершины, инцидентные одной дуге. Матрица смежности -

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

Множество внутренней устойчивости графа
  Множество внутренней устойчивости графа – это множество несмежных вершин. Пусть дан граф

Алгоритм Магу для определения множества внутренней устойчивости графа
Пусть дан граф . Для данного графа существует множество внутренней устойчивости

Множество внешней устойчивости графа
  Множество внешней устойчивости – множество вершин, для которых выполняется одно из следующих правил: 1). Любая вершина входит в это множество

Алгоритм Магу для определения множества внешней устойчивости.
Пусть дан граф . Для данного графа существует множество внешней устойчивости

Множество путей в графе
  По матрице смежности можно определить, сколько различных путей существует между i-той и j- той вершинами длиной в к

Алгоритм фронта волны. Поиск минимального пути в графе.
  Одной из самых распространенных задач в теории графов является задача поиска минимального пути в графе. Рассмотрим некоторые свойства минимальных путей 1. Любой ми

Ярусно-параллельная форма графов
Граф, не имеющий контуров, может быть представлен в ярусно-параллельной форме. Ярусно-параллельная форма – это такой вид графа, у которого в верхний нулевой ярус поме

Алгоритм приведения графа к ярусно-параллельной форме.
1. Составляется матрица смежности графа. 2. Матрица смежности просматривается в поисках нулевых столбцов. Вершины, которым соответствуют нулевые столбцы, помещаются в нулевой ярус.

Деревья и леса
Отделенными называются вершины, для которых не существует соединяющего эти вершины пути. Неотделенными называются вершины, между которыми существу

Алгоритм получения дерева из графа
  1. Выбирается любая вершина. Счетчик i принимаем равным 1 (i=1). 2. Если i = k, то дерево построено. 3. Если i ¹ k, то выбирается

ТЕОРИЯ АЛГОРИТМОВ
Алгоритм – это точное, понятное предписание о том, какие действия и в каком порядке должны быть выполнены, чтобы решить любую задачу из класса однотипных задач.

Функция-проекция
(4.3) Правила преобразования функций   1. Правило

Машина Тьюринга
Если для решения некоторой массовой проблемы известен алгоритм, то для его реализации необходимо лишь четкое выполнение предписаний этого алгоритма. Автоматизм, необходимый при реализации алгоритма

Программа машины Тьюринга (Р) - совокупность всех команд, Программа представляется в виде таблицы и называется Тьюринговой функциональной схемой.
a0 a1 a2 q1 а0

Нормальные алгоритмы Маркова
Нормальный алгоритм Маркова представляет собой систему подстановок , (4.10)

Законы функционирования автоматов.
В зависимости от законов функционирования различают 3 вида автоматов: 1. Автоматы первого рода, или автоматы Мили:

Минимизация автоматов
Входным словом называется совокупность сигналов, поступающих на вход. Выходным словом называются совокупность сигналов на выходе.

Алгоритм минимизации автомата Мили
1. По таблице выхода находятся состояния с одинаковыми выходными сигналами. Данные состояния объединяются в класс одноэквивалентных состояний. Проводится перекодировка. 2. По таблице перех

Переход от автомата Мили к автомату Мура
Автоматы Мили и автоматы Мура отличаются функцией выхода. Автомат Мили: (

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

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