No Image

Упростить высказывание используя равносильные преобразования

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

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

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

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

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

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

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

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

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

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

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

Законы алгебры логики:

1.Коммутативность

относительно конъюнкции относительно дизъюнкции

2.Ассоциативность

относительно конъюнкции относительно дизъюнкции

3.Дистрибутивность

конъюнкции относительно дизъюнкции относительно

4.Законы де Моргана

относительно конъюнкции относительно дизъюнкции

5.Закон поглощения

6.Законы идемпотентности

относительно конъюнкции относительно дизъюнкции

7.Законы противоречия

относительно конъюнкции относительно дизъюнкции

8.Законы действие с константами

Одни операции можно выразить через другие: импликация выражается через дизъюнкцию и отрицание, эквиваленция – через отрицание, дизъюнкцию и конъюнкцию:

, , , .

Таким образом, операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания. Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок считается, что сначала выполняется операция отрицания («не»), затем конъюнкция («и»), после конъюнкции – дизъюнкция («или») и в последнюю очередь – импликация.

Пример 1. Упростить формулу .

.
б) По закону идемпотентности

.

в) Из высказываний и вынесем за скобки и, используя законы констант, получим: , таким образом, мы доказали закон дистрибутивности.

Всякую формулу можно преобразовать так, что в ней не будет отрицаний сложных высказываний – все отрицания будут применяться только к простым высказываниям.

Пример 2.Преобразовать формулу так, чтобы не было отрицаний сложных высказываний.

Решение:
а) воспользуемся формулой де Моргана ;

б) для выражения применим еще раз формулу де Моргана, получим: .

Читайте также:  Автопоиск и установка драйверов

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

Пример 3.

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

Решение:
Воспользуемся законом двойного отрицания, а затем формулой де Моргана: .

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

Используя формулы де Моргана и закон двойного отрицания, получим:
В алгебре логики всякую логическую функцию можно выразить через другие логические функции, но при этом должно быть по меньшей мере две операции, при этом одной из них обязательно должно быть отрицание.

Все операции можно выразить через конъюнкцию и отрицание, дизъюнкцию и отрицание, импликацию и отрицание.

Через эквиваленцию и отрицание остальные операции выразить нельзя.

Упражнения

1. Упростить логические выражения:

2. Формулы данных высказываний преобразовать в эквивалентные, исключив логическое сложение:

а) ; б) ; в) .

3. Формулы данных высказываний преобразовать в эквивалентные, исключив логическое умножение:

а) ; б) ; в) .

4. Упростить:

а) ; б) .

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

a) ; б) ; в) .

6. Записать высказывания, используя только операции логического сложения и отрицания:

а) ; б) ; в) .

Дата добавления: 2016-04-11 ; просмотров: 2151 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Цель работы: научиться составлять таблицы истинности формул алгебры высказываний и упрощать формулы алгебры высказываний.

Ход выполнения работы:

1. Изучить теоретический материал.

2. Получить задание у преподавателя.

3. Выполнить задание.

4. Ответить на контрольные вопросы.

5. Защитить выполненное задание.

Краткие теоретические сведения

Пропозициональная переменная – переменна, вместо которой можно подставлять высказывания.

Формула алгебры высказываний определяется следующим образом:

1. Каждая отдельно взятая пропозициональная переменная – формула алгебры высказываний.

Читайте также:  Microsoft office 365 активатор kms

2. Если F и G – формулы алгебры высказываний, то выражения также являются формулами алгебры высказываний.

3. Никаких других формул алгебры высказываний нет.

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

Такую последовательность всех подформул данной формулы является порождающей последовательностью для данной формулы.

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

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

Также можно отметить, что число наборов значений n пропозициональных переменных равно 2 n .

Формулы могут относиться к одному из классов:

1) общезначимые (последний столбец таблицы истинности такой формулы содержит и 0, и 1)

2) тавтологии (последний столбец истинности такой формулы состоит только из 1)

3) противоречия (последний столбец истинности такой формулы состоит только из 0)

Формулы алгебры высказываний F и H равносильны, если они принимают одинаковые логические значения на любом наборе значений входящих в них высказываний.

Одну равносильную формулу можно получить из другой, используя следующие равносильные преобразования

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

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

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

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

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

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

5) дистрибутивность конъюнкции

6) дистрибутивность дизъюнкции

Читайте также:  Link rev made href mailto postmaster localhost

1. Составить таблицу истинности формулы и определить вид формулы (общезначимая, тождественно истинная (тавтология), тождественно ложная (противоречие)):

Составим таблицу истинности формулы. Формула F зависит от двух переменных P и Q, поэтому таблица истинности будет содержать 4 строки

P Q P®Q (P®Q)®P F =
1 1
1 1 1
1 1
1 1 1 1 1

Так как в последнем столбце таблицы истинности присутствуют и 0, и 1, то формула является общезначимой.

2.Доказать, что формула является тавтологией (упростив формулу):

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

Отсюда получаем, что формула является тавтологией.

3. Преобразовать формулу равносильным образом так, чтобы она содержала только операции дизъюнкции, конъюнкции и отрицания:

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

Получена формула, содержащая только операции отрицания, конъюнкции и дизъюнкции. Таким образом,

Задания:

1. Составить таблицу истинности формулы и определить вид формулы (общезначимая, тождественно истинная (тавтология), тождественно ложная (противоречие)):

1)

2)

3)

4)

5)

6)

7)

8)

9)

2.Доказать, что формула является тавтологией (упростив формулу):

1)

2)

3)

4)

5)

6)

7)

8)

9)

3. Преобразовать формулу равносильным образом так, чтобы она содержала только операции дизъюнкции, конъюнкции и отрицания:

1)

2)

3)

4)

5)

6)

7)

8)

9)

1. Что такое формула алгебры высказываний

2. Что такое порождающая последовательность формулы

3. Что представляет собой таблица истинности формулы

4. Какие классы формул Вам известны

5. Какие формулы называются равносильными.

6. Перечислить основные группы равносильных преобразований

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

Лучшие изречения: Только сон приблежает студента к концу лекции. А чужой храп его отдаляет. 8955 — | 7623 — или читать все.

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

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

очень нужно

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

Это интересно
Adblock detector