No Image

Упрощение формул логики с помощью равносильных преобразований

СОДЕРЖАНИЕ
5 просмотров
10 марта 2020

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

· ;

· ;

· ;

· ;

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

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

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

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

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

· ;

· ;

· ;

· ;

· ;

· .

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

Читайте также:  Cable not connected на мониторе

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Важнейшие равносильности можно разбить на три группы:

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

7. – закон противоречия.

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

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

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

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

1. – коммутативность конъюнкции.

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

Читайте также:  Mikroc pro for avr

3. – ассоциативность конъюнкции.

4. – ассоциативность дизъюнкции.

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

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

Используя равносильности группы I , II и III , можно часть формул алгебры логики или всю формулу заменить равносильной ей формулой. Такие преобразования называются равносильными . Равносильные преобразования формул применяются для доказательства равносильностей , для приведения формул к заданному виду, для упрощения формул.

Пример 1. Доказать равносильность .

Решение . Для доказательства равносильности подвергнем ее левую часть равносильным преобразованиям: .

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

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

Пример 2 . Доказать тождественную истинность формулы:

Решение. Подвергнем формулу А равносильным преобразованиям

Для проверки усвоения теоретического материала можно перейти к выполнению Проверочной работы №2.

Комментировать
5 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
Adblock detector