Алгебра логики - раздел Математика, Порядок записи элементов множества не является существенным в отличие от записи элементов векторов, где порядок важен
Алгебраическая Система (Алгебра...
Алгебраическая система (алгебра) – пара <G, M>, где G - это множество элементов (носитель), а M – множество операций, заданных на G (сигнатура).
(n-арная операция на G задаёт отображение на G)
Определение: Алгебраическая система, образованная множеством B = {0,1} вместе со всеми возможными операциями на нем, называетсяалгеброй логики.
Функцией алгебры логики (или логической функцией) от n переменных называется n-арная операция на В. Эта функция может принимать значения 0 или 1. (т.о. задаёт отображение B^n -> B)
Чаще всего под алгеброй логики понимают алгебру, сигнатура которой включает 3 операции: отрицание, конъюнкцию и дизъюнкцию.
Основные функции алгебры логики:
x1
u1
u2
u3
u4
Унарные:
Всего теоретически возможны 4 унарных операции, но лишь одна из них имеет собственное название и обозначение.
u3 - Отрицание: (читается: не-А)
Бинарные:
Всего существует 16 бинарных функций алгебры логики:
x1
x2
b1
b2
b3
b4
b5
b6
b7
b8
b9
b10
b11
b12
b13
b14
b15
b16
b2 -Конъюнкция: (читается А и В)
b8 - Дизъюнкция: (А или В)
b12 - Импликация: (из А следует В)
Результат импликации ложен только тогда, когда исходное (А) высказывание ложно, а результат (B) истинен.
Примеры: (x делится на 4) -> (x делится на 2), Если 2*2 = 5 то 2*2 = 4
b10 - Эквиваленция: , (А равносильно В)
Результат эквиваленции есть истина, если A и B одновременно истины либо ложны (Иными словами, если A=B)
b7 – сложение по модулю или неравнозначность, x1Åx2
Результат сложения по модулю истинен, если истинно лишь одно из A и B (То есть, если A B)
b9 – cтрелка Пирсаx1¯x2 («или-не»). Результат этой операции равносилен последовательному применению операций дизъюнкции и отрицания
b15 – штрих Шеффера обозначается x1|x2, «и-не». Результат этой операции равносилен последовательному применению операций конъюнкции и отрицания. Соответственно, результирующее высказывание будет ложным, только если входящие в него высказывания одновременно истинны. Штрих Шеффера - это операция замечательная тем, что её одной (необходимое количество раз применённой) достаточно, чтобы записать любое сложное высказывание. Является основной операцией в электронике.
Множество это совокупность определ нных различаемых объектов прич м таких что для каждого можно установить принадлежит этот объект данному... Множества обычно обозначаются заглавными латинскими буквами а элементы... Например...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Алгебра логики
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Характеристическая функция
Характеристическая функцияили индикатор показывает принадлежность элементов множеству (обозначается или ).
Характеристическая функция пуст
Графическое доказательство
Для построения графического доказательства необходимо изобразить на диаграмме Эйлера-Венна все множества, входящие в тождество таким образом, что бы присутствовали их все возможные пересечения,
Отношения.
n-местным отношением R на множествах называется подмножество прямого произведения .
Если множества совпадают, то говорят что задаёт n-арные отношения.
При n = 2 о
Пустое отношение.
Операции на отношениях:
Пересечение
Объединение
Произведение
Дополнение:
Обратное отношение к R:
Формулы алгебры логики.
Атомарные высказывания обозначаются маленькими буквами и называются пропозициональными (или булевыми) переменными. Формулы алгебры логики называются пропозициональные формулы.
Формулой явл
Таблицы истинности.
Логическое значение формулы определяется заданными логическими значениями входящих в неё элементарных высказываний.
Пример. 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
Новости и инфо для студентов