Равносильные преобразования дискретная математика

Равносильные формулы алгебры логики

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

Обозначение. A ≡ B .

.

Определение. Формула A называется тождественно истинной (тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных (напр., ).

Определение. Формула A называется тождественно ложной (противоречием), если она принимает значение 0 при всех значениях входящих в нее переменных (напр., ).

Утверждение. Отношение равносильности рефлексивно, симметрично, транзитивно.

Связь между понятиями равносильности и эквивалентности: если формулы A и B равносильны, то формула A ↔ B тавтология, и обратно, если формула A ↔ B тавтология, то формулы A и B равносильны.

Равносильности алгебры логики можно разбить на 3 группы:

1. Основные равносильности.

· – законы идемпотентности;

· ;

· ;

· ;

· ;

· – закон противоречия;

· – закон исключенного третьего;

· – закон снятия двойного отрицания;

· – законы поглощения.

1. Равносильности, выражающие одни логические операции через другие:

· ;

· ;

· ;

· ;

· ;

· .

Замечание. Из равносильностей группы 2 следует, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: конъюнкцию и отрицание, или дизъюнкцию и отрицание. Дальнейшее исключение операций невозможно. Например, если использовать только конъюнкцию, то уже такая простая формула, как не может быть выражена с помощью операции конъюнкции.

Существуют операции, с помощью которых может быть выражена любая из 5 логических операций:

1) Связка Шеффера – дизъюнкция отрицаний.

Обозначение. x | y ≡ (« x не совместно с y »).

Логические значения связки Шеффера описываются следующей таблицей истинности:

Имеют место следующие равносильности: а) ; б) .

2) Связка Лукасевича – конъюнкция отрицаний.

Обозначение . x ↓ y ≡ («ни x , ни y »).

Читайте также:  Слои в фотошопе для чайников

Логические значения связки Лукасевича описываются следующей таблицей истинности:

2. Равносильности, выражающие основные законы алгебры логики:

· – коммутативность конъюнкции;

· – коммутативность дизъюнкции;

· – ассоциативность конъюнкции;

· – ассоциативность дизъюнкции;

· – дистрибутивность конъюнкции относительно дизъюнкции;

· – дистрибутивность дизъюнкции относительно конъюнкции.

Замечание. Равносильности группы 3 показывают, что над формулами алгебры логики можно проводить те же преобразования, что и в алгебре чисел.

Равносильные преобразования формул

Используя равносильности групп 1–3 можно часть формулы или формулу заменить равносильной ей формулой. Такие преобразования формул называются равносильными.

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

Эквивалентные преобразования — преобразования, использующие эквивалентные соотношения и правило замены.

Два правила замены:

1. Правило подстановки формулы f вместо переменной х. При подстановке формулы f вместо переменной х все вхождения переменной х в исходное соотношение должны быть одновременно заменены формулой f.

2. Правило замены подформул. Если какая-либо формула f, описывающая функцию φ, содержит f1 в качестве подформулы, то замена f1 на эквивалентную f2 (f1= f2) не изменит функции φ.

Основные эквивалентные соотношения (законы) в булевой алгебре.

Ассоциативность конъюнкции и дизъюнкции:
(1)
Коммутативность конъюнкции и дизъюнкции:
(2)
Дистрибутивность конъюнкции относительно дизъюнкции:
(3)
Дистрибутивность дизъюнкции относительно конъюнкции:
(4)
Идемпотентность:
(5)
Закон двойного отрицания:
(6)
Свойства констант 0 и 1:
(7)
Правила де Моргана:
(8)
Закон противоречия:
(9)
Закон исключенного третьего:
(10)

Основные эквивалентные соотношения (1) – (10) отличаются тем, что они не выводимы друг из друга и этих соотношений достаточно для выполнения любых эквивалентных преобразований.

Читайте также:  Дота 2 на телефон андроид

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

Поглощение:
(11)
Склеивание:
(12)
Обобщенное склеивание:
(13)
(14)

Приведение к дизъюнктивной нормальной форме.

Элементарная конъюнкция — конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Дизъюнктивная нормальная форма (ДНФ) — формула, имеющая вид дизъюнкции элементарных конъюнкций.

Приведении формулы к ДНФ осуществляется в 4 этапа:

1. все отрицания «спустить» до переменных с помощью (6) и (8);

2. раскрыть скобки с помощью (1), (3), (4);

3. удалить лишние конъюнкции и повторения переменных в конъюнкциях с помощью (5), (9), (10);

4. удалить константы с помощью (7).

Процедура приведения ДНФ к СДНФ состоит в расщеплении (использовании (12) в обратную сторону) конъюнкций, которые содержат не все переменные.

Приведение к конъюнктивной нормальной форме.

Элементарная дизъюнкция — дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Конъюнктивная нормальная форма (КНФ) — конъюнкция элементарных дизъюнкций.

Пусть ДНФ F имеет вид F=k1Úk2Ú…Úkm, где k1,k2,…,km элементарные конъюнкции. Приведение ДНФ к КНФ состоит из двух шагов:

1. Применить к F правило двойного отрицания и привести к ДНФ 1Ú k¢2Ú…k¢p где 1Ú k¢2Ú…k¢p элементарные конъюнкции. Тогда

2. С помощью правил де Моргана освободиться от второго отрицания и преобразовать отрицания элементарных конъюнкций в элементарные дизъюнкции D1,D2,…Dp Тогда

Совершенная КНФ (СКНФ) — КНФ, каждая элементарная дизъюнкция которой содержит все переменные.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Да какие ж вы математики, если запаролиться нормально не можете. 8546 — | 7400 — или читать все.

Читайте также:  Как победить в игре гренни

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Что умеет калькулятор математической логики?

  • Расставлять скобки в выражении, учитывая приоритет операций
  • Упрощать логические выражения
  • Строит таблицу истинности для введённых формул
  • Найти нормальные формы логического выражения:
  • Конъюнктивную нормальную форму (КНФ), в том числе совершенную
  • Дизъюнктивную нормальную форму (ДНФ), в том числе совершенную

Поддерживаемые символы в логических выражениях

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

¬a — отрицание a⇒b — импликация a∧b — конъюкция a∨b — дизъюнкция a⇔b — эквиваленция a⊕b — сложение по модулю 2 (Исключающее или) a|b — Не-и (штрих Шеффера) a↓b — Не-или (стрелка Пирса)

Это символы не жёстко привязаны к соотв. операциям, можно использовать другие.

Примеры логических выражений

С применением отрицания

Со знаком "эквивалентно"

Со знаком "следствие"

С применением конъюкции и дизъюнкции

С применением Не-и и Не-или

В калькуляторе вы сможете упростить выражения, содержащие следующие операции: NOT, XOR, AND, OR, NAND, NOR, NOT

© Контрольная работа РУ — калькуляторы онлайн