Приоритет операций в дискретной математике

Кроме знаков операций, в алгебре Буля применяются знак “=” (равно) и скобки. Знак “равно” указывает, конечно, не количественное равенство, а то, что разделяемые им символы идентичны, поэтому сигналы слева от этого знака всюду можно заменить символами справа от него и наоборот. Например, если y₁ = , y₂ = , y₃ = , а z = y₁ + y₂ + y₃ , то можно записать

z = y₁ + y₂ + y₃ = + + .

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

Скобки, как и в обычной алгебре, применяются для дополнительного указания порядка выполнения (приоритета) операций. Для уменьшения числа скобок используется приоритет операций.

Приоритет (порядок выполнения) логических операций следующий:

1. Вычисляются значения выражений внутри скобок;

2. Выполняются отрицания над отдельными переменными (НЕ);

3. Вычисляются конъюнкции (И, И-НЕ);

4. Вычисляются дизъюнкции (ИЛИ, ИЛИ-НЕ);

5. Вычисляются суммы по модулю 2 и функции равнозначности;

6. Вычисляется импликация.

Заметим, что иногда знак отрицания ставится над целым выражением, не заключённым в скобки; в этом случае отрицание выполняется в последнюю очередь.

Пример 2.2. Логическая формула

,

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

.

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

Лучшие изречения: Сдача сессии и защита диплома — страшная бессонница, которая потом кажется страшным сном. 8912 — | 7222 — или читать все.

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

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

Как и в привычной математике, одни операции бывают сильнее других, и мы выполняем их в первую очередь (например, умножение в алгебре)

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

Пример 6: Даны множества:

Определить, из каких элементов состоит множество

Определить его мощность.

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

1). Выполним операции в первой скобке (). Для этого в первую очередь необходимо найти дополнение множества А до универсального:

=

Далее выполним пересечение полученного множества с множеством D:

=

2). Выполним операции во второй скобке (). Рассуждая аналогичным образом, получим:

=

B =

3). Невыполненными остались две операции: объединение и пересечение. Согласно приоритету операций, в первую очередь выполняется пересечение. Поэтому далее нам необходимо выполнить пересечение уже найденного множества с множеством А:

()А =

4) Далее необходимо результат, полученный в пункте (1) объединить с результатом, полученным в пункте (3):

() ()А =

5) Полученное множество состоит из 4-х элементов, поэтому его мощность равна 4:

() ()А = 4

Раздел 2. Математическая логика.

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

Тема 1. Логика высказываний.

Повествовательное, утвердительное предложение, о котором можно сказать истинно оно или ложно, будем называть высказыванием.

Пример1: «Рубль – валюта Греции» — ложное высказывание;

«Трава зеленая» — истинное высказывание.

Высказывания обозначаются малыми латинскими буквами: p, q, r, t.

Значения высказываний:  p

Возможны два варианта значений высказываний (согласно введенному определению):

 p=И (истинное высказывание);  p= Л (ложное высказывание)

Высказывания, аналогичные приведенным в примере 1 называются простыми высказываниями. Для связи отдельных простых предложений в речи мы используем союзы и словосочетания типа: и; или; если, то; тогда и только тогда, когда

Выделяют 5 логических связок, позволяющих из простых высказываний формировать составные высказывания:

Логические связки (операции):

Название связки (операции)

Тогда и только тогда, когда

Отрицанием (инверсией) высказывания p называется новое высказывание, которое обозначается p или , истинное когда высказываниеp ложное и ложное в противном случае.

Конъюнкцией двух высказываний p и q называется новое высказывание, которое обозначается pq, которое принимает значение истина, когда оба высказывания p и q истинны.

Дизъюнкцией двух высказываний p и q называется новое высказывание, которое обозначается pq, которое принимает значение истина, когда хотя бы одно из высказываний p или q истинно.

Импликацией двух высказываний p и q называется новое высказывание, которое обозначается pq, которое принимает значение ложь только в том случае, если p – истинно, а q -ложно.

Эквиваленцией двух высказываний p и q называется новое высказывание, которое обозначается pq, которое принимает значение истина если p и q принимают одинаковые значения.

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

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

Таблица истинности для логических связок:

Нужно составить таблицу истинности выражения: Y*Z -> X и над всем выражением черта. Отрицание необходимо производить в начале, перед остальными действиями, или в самом конце? В случае отрицания отдельных переменных, то как я понимаю, сначала делается оно, а потом остальные действия? &&overline&&

задан 12 Мар ’18 21:01

Если отрицание над всем выражением, то оно осуществляется в самом конце. Вообще, здесь сразу можно сказать, что только на наборе 011 (когда импликация ложна) получится значение выражения 1, а на остальных семи наборах получится 0.

Здравствуйте

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