Полные системы функций (связок). - раздел Математика, Порядок записи элементов множества не является существенным в отличие от записи элементов векторов, где порядок важен Система Функций Является Полной, Если Любая N-Арная Булева Функция Может Б...
Система функций является полной, если любая n-арная булева функция может быть записана в виде пропозициональной формулы с использованием только функций входящих в эту систему.
Система {¬,∨,∧,→,↔} является полной.
Система {¬,∨,∧} является полной. Именно она и составляет сигнатуру Булевой Алгебры.
Системы {¬,→}, {|} (штрих шеффера), так же полны.
Вторая система – только И-НЕ является важной для микроэлектроники.
Последняя система позволяет представить булевы функции в виде полиномов (полиномов Жигалкина)
Замкнутый класс – это такое множество функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: [P] = P (то есть, любая функция, которую можно записать с помощью только функций входящих в P так же входит в P).
критерий Поста: Система булевых функций является полной тогда и только тогда, когда он не содержится целиком ни в одном из пяти замкнутых классов:
· монотонные функции
}
· функции, сохраняющие нуль
· функции, сохраняющие единицу
· линейные функции
· самодвойственные функции
Если функции содержатся в одном из классов, то и все композиции также не выходят за пределы этого класса (легко проверить для каждого из классов в отдельности) и поэтому система не является полной.
Можно показать, что имея функции по крайней мере из 2 разных классов, можно выразить любую другую функцию.
Множество это совокупность определ нных различаемых объектов прич м таких что для каждого можно установить принадлежит этот объект данному... Множества обычно обозначаются заглавными латинскими буквами а элементы... Например...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Полные системы функций (связок).
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Характеристическая функция
Характеристическая функцияили индикатор показывает принадлежность элементов множеству (обозначается или ).
Характеристическая функция пуст
Графическое доказательство
Для построения графического доказательства необходимо изобразить на диаграмме Эйлера-Венна все множества, входящие в тождество таким образом, что бы присутствовали их все возможные пересечения,
Отношения.
n-местным отношением R на множествах называется подмножество прямого произведения .
Если множества совпадают, то говорят что задаёт n-арные отношения.
При n = 2 о
Пустое отношение.
Операции на отношениях:
Пересечение
Объединение
Произведение
Дополнение:
Обратное отношение к R:
Алгебра логики
Алгебраическая система (алгебра) – пара <G, M>, где G - это множество элементов (носитель), а M – множество операций, заданн
Формулы алгебры логики.
Атомарные высказывания обозначаются маленькими буквами и называются пропозициональными (или булевыми) переменными. Формулы алгебры логики называются пропозициональные формулы.
Формулой явл
Таблицы истинности.
Логическое значение формулы определяется заданными логическими значениями входящих в неё элементарных высказываний.
Пример. x1=1, x2=1, x3=0. Определить значение формулы
Равносильные формулы
Две формулы алгебры логики называются равносильными, если они принимают одинаковые логические значения при любом наборе значений элементарных высказываний, входящих в
Теорема о тождественной истинности формулы алгебры логики.
Для того, чтобы формула алгебры логики была тождественно истиной, необходимо и достаточно, чтобы каждая элементарная дизъюнкция её конъюнктивной нормальной формы содержала, по крайней мере, одно эл
Теорема о тождественной ложности формулы алгебры логики
Для того, чтобы формула алгебры логики была тождественно ложной, необходимо и достаточно, чтобы каждая элементарная конъюнкция её ДНФ содержала по крайней мере одно элементарное переменное высказыв
Совершенные нормальные формы.
Совершенная дизъюнктивная нормальная форма.
Элементарная конъюнкция называется правильной,если в неё каждая переменная входит не более одного раза,
Построения СДНФ и СКНФ.
Построение СДНФ:
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
Новости и инфо для студентов