Как определяется порядок выполнения логических операций в логических формулах кратко

Обновлено: 26.04.2024

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

НЕ запомнить, НЕ распечатать, а именно ещё раз осмыслить и собственноручно переписать на бумагу – чтобы они были перед глазами:

– таблица НЕ;
– таблица И;
– таблица ИЛИ;
– импликационная таблица;
– таблица эквиваленции.

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

1) любые элементарные (простые) высказывания ;

2) если и – формулы, то формулами также являются выражения вида
.

Никаких других формул нет.

Логическую формулу можно рассматривать, как логическую функцию. Запишем в функциональном виде ту же конъюнкцию:

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

– в первую очередь выполняется отрицание ;
– во вторую очередь – конъюнкция ;
– затем – дизъюнкция ;
– потом импликация ;
– и, наконец, низший приоритет имеет эквиваленция .

Наверное, все понимают, но на всякий пожарный: и – это две разные формулы! (как в формальном, так и в содержательном плане)

(три горизонтальные чёрточки – это значок тождества)

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

Ещё раз повторим порядок решения задачи:

1) Так как в формулу входят две переменные, то всего будет 4 возможных набора нулей и единиц. Записываем их в оговорённом выше порядке.

И, наконец, сверяемся с таблицей истинности эквиваленции .

Основные равносильности алгебры высказываний

С двумя из них мы только что познакомились, но ими дело, понятно, не огранивается. Тождеств довольно много и я перечислю самые важные и самые известные из них:

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

Коммутативность – это перестановочность:

Ассоциативность логического умножения и сложения

Дистрибутивные свойства

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

Что делать, латынь.

И тут же несколько похожих тождеств:

…мда, что-то я даже подзавис… так и доктором философии завтра можно проснуться =)

Закон двойного отрицания

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

В правом тождестве скобки можно опустить.

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

Предположим, что строгий Преподаватель (имя которого вам тоже известно:)) ставит экзамен, если – Студент ответил на 1-й вопрос и – Студент ответил на 2-й вопрос. Тогда высказывание , гласящее о том, что Студент не сдал экзамен, будет равносильно утверждению – Студент не ответил на 1-й вопрос или на 2-й вопрос.

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

Теперь убедимся, например, в справедливости закона де Моргана .

Доказать следующие равносильности:

Краткое решение в конце урока. Не ленимся! Постарайтесь не просто составить таблицы истинности, но ещё и чётко сформулировать выводы. Как я недавно отмечал, пренебрежение простыми вещами может обойтись очень и очень дорого!

Продолжаем знакомиться с законами логики!

Да, совершенно верно – мы с ними уже вовсю работаем:

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

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

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

Фирменный пример противоречия от древних греков:
– никакое высказывание не может быть истинным и ложным одновременно.

Однако и любое противоречие – это тоже закон логики, в частности:

Нельзя объять столь обширную тему в одной-единственной статье, и поэтому я ограничусь ещё лишь несколькими законами:

Закон исключённого третьего

Самостоятельно составьте табличку истинности и убедитесь в том, что это тождественно истинная формула.

Закон контрапозиции

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

Если истинна обратная теорема , то в силу закона контрапозиции , справедлива и теорема, противоположная обратной:

Закон силлогизма

Ну и здесь опять хочется отметить формализм математической логики: если наш строгий Преподаватель думает, что некий Студент – есть дуб, то с формальной точки зрения данный Студент, безусловно, растение =) …хотя, если задуматься, то может быть и с неформальной тоже =)

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

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

1) выполняем импликации и . Вообще говоря, можно сразу выполнить и 3-ю импликацию, но с ней удобнее (и допустимо!) разобраться чуть позже;

2) к столбцам применяем правило И;

3) вот теперь выполняем ;

4) и на завершающем шаге применяем импликацию к столбцам и .

Не стесняйтесь контролировать процесс указательным и средним пальцем :))

Из последнего столбца, думаю, всё понятно без комментариев:
, что и требовалось доказать.

Выяснить, будет ли являться законом логики следующая формула:

Краткое решение в конце урока. Да, и чуть не забыл – давайте условимся перечислять исходные наборы нулей и единиц в точно таком же порядке, что и при доказательстве закона силлогизма. Строки конечно, можно и переставить, но это сильно затруднит сверку с моим решением.

Преобразование логических формул

Кроме того, есть ещё одна важная вещь: тождества справедливы не только для элементарных высказываний, но и для произвольных формул. Так, например:

, где – любые (сколь угодно сложные) формулы.

Преобразуем, например, сложную импликацию (1-е тождество):

Ну, а с коммутативностью вообще всё просто – даже обозначать ничего не нужно… что-то запал мне в душу закон силлогизма:))

Таким образом, закон можно переписать и в более затейливом виде:

В качестве тренировки упростим формулу .

Как правило, на первом шаге (шагах) избавляются от эквиваленции и импликации (если они есть) и сводят формулу к трём основным логическим операциям. Что тут скажешь…. Логично.

(1) Используем тождество . А нашем случае .

(2) К внешним скобкам применяем закон де Моргана , где .

(3) К внутренним скобкам применяем закон двойного отрицания . Внешние скобки можно убрать, т.к. за её пределами находятся равные по силе операции.

(4) В силу коммутативности дизъюнкции меняем местами и . Оставшиеся скобки тоже убираем по озвученной выше причине.

(5) В силу коммутативности дизъюнкции меняем местами и , а также и .

(6) Используем закон идемпотентности и закон исключенного третьего

(7) Дважды используем тождество

Вот оно как…, оказалось, что наша формула – тожественно истинна:

Желающие могут составить таблицу истинности и убедиться в справедливости данного факта.

Пара задач для закрепления материала:

Выразить эквиваленцию через отрицание, конъюнкцию, дизъюнкцию и раскрыть скобки

Аккуратно проводим преобразования в соответствии с равносильностями. После этого будет не лишним вернуться к параграфу об эквиваленции и найти там фразу, которая соответствует полученному результату ;-)

Упростить логическую формулу

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

Решения и ответы:

Задание 1 Решение: составим таблицу истинности для формулы :

(подробные инструкции по заполнению таблицы находятся после условия задачи)
Полученный результат совпадает с эквиваленцией высказываний и , таким образом:

Задание 2 Решение: доказательства проведём с помощью таблиц истинности:

а) Дважды записываем все варианты истины и лжи высказывания и применяем к столбцам операцию ИЛИ:

Результат совпадает с . Тождество доказано

б) составим таблицу истинности для левой части тождества
. Сначала к столбцам и применяем операцию ИЛИ, затем к столбцам и – операцию И:

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

Задание 3 Решение: составим таблицу истинности:

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

Задание 4 Решение:

(1) Используем тождество .
(2) Дважды применяем тождество .
(3) Используем дистрибутивный закон , в данном случае:
(квадратные скобки можно было не ставить – они не меняют порядок действий, но помогают лучше видеть ситуацию).
(4) В квадратных скобках используем коммутативность конъюнкции.
(5) Дважды используем тот же самый дистрибутивный закон.
(6) Во второй слева скобке используем коммутативность конъюнкции.
(7) Согласно закону противоречия: .
(8) К формуле дважды применяем тожество .
(9) А это уже для красоты :)) Скобки, кстати, можно было убрать намного раньше (я их не опускал с целью улучшить восприятие преобразований).

Задание 5 Решение:

Автор: Емелин Александр

(Переход на главную страницу)

cкидкa 15% на первый зaкaз, при оформлении введите прoмoкoд: 5530-hihi5

Учебник по Информатике 8 класс Семакин
of your page -->

Задание 1. Какие проблемы решает формальная логика?

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

Задание 2. Определите основные понятия алгебры логики: логическая величина, логическая операция, логическая формула?

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

Задание 3. Сформулируйте правила выполнения основных логических операций.

1) Операция отрицания (инверсия): меняет значения на противоположное: не истина = ложь; не ложь = истина.

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

3) Операция логического сложения: будет истина тогда, когда хотя бы один из операндов имеет значение ИСТИНА. Обозначение: или

Задание 4. Как определяется порядок выполнения логических операций в логических формулах?

Порядок выполнения логических операций:
1) операции в скобках
2) отрицание (не)
3) логическое умножение (и)
4) операция логического сложения (или)

Задание 5. Пусть a, b, c – логические величины, которые имеют следующие значения: a = ИСТИНА, b = ЛОЖЬ, C = ИСТИНА. Определите результаты вычисления следующих логических формул.

1) a и b = ИСТИНА и ЛОЖЬ = ЛОЖЬ
2) a или b = ИСТИНА или ЛОЖЬ = ИСТИНА
3) не a или b = не ИСТИНА или ЛОЖЬ = ЛОЖЬ
4) a и b или c = ИСТИНА и ЛОЖЬ или ИСТИНА = ИСТИНА
5) a или b и c = ИСТИНА или ЛОЖЬ и ИСТИНА = ИСТИНА
6) не a или b и c = не ИСТИНА или ЛОЖЬ и ИСТИНА = ЛОЖЬ
7) (a или b) и (c или b) = (ИСТИНА или ЛОЖЬ) и (ИСТИНА или ЛОЖЬ) = ИСТИНА
8) не (a или b) и (c или b) = не (ИСТИНА или ЛОЖЬ) и (ИСТИНА или ЛОЖЬ) = не ИСТИНА и ИСТИНА = ЛОЖЬ
9) не (a и b и c) = не (ИСТИНА и ЛОЖЬ и ИСТИНА) = ИСТИНА

Задание 6. Постройте таблицы истинности для логических формул под номерами 3-9 из предыдущего задания?

3) не a или b

4) a и b или c

5) a или b и c

6) не a или b и c

7) (a или b) и (c или b)

8) не (a или b) и (c или b)

9) не (a и b и c)

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

Значения логических функций определяются с помощью таблица истинности.

Таблицы истинности для основных двоичных логических функций

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

Обозначение:

2. Дизъюнкция (логическое сложение) – это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно, если оба простых логических выражения ложны.

Обозначение:

3. Импликация (логическое следствие) – это сложное логическое выражение, которое является ложным тогда и только тогда, когда условие истинно, а следствие ложно.

Обозначение:

4. Эквиваленция – это сложное логическое высказывание, которое является истинным только при одинаковых значениях истинности простых выражений, входящих в него.

Обозначение:

5. Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное – истинным.

Обозначение:

6. Штрих Шеффера – операция, отрицающая конъюнкцию, т.е. значение ложно тогда и только тогда, когда оба простых выражения истинны.

Обозначение:

7. Стрелка Пирса – операция, отрицающая конъюнкцию, т.е. значение истинно тогда и только тогда, когда оба простых выражения ложны.

Обозначение:

Порядок выполнения логических операций

При построении таблицы истинности необходимо учитывать порядок выполнения логических операций:

1. Инверсия
2. Конъюнкция
3. Дизъюнкция
4. Импликация
5. Эквиваленция
6. Штрих Шеффера
7. Стрелка Пирса

Для последних двух операций приоритет не определен.

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

Примеры решения задач

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

I –

II –

III –

Конъюнкция или логическое умножение (в теории множеств – это пересечение)

Конъюнкция является сложным логическим выражением, которое истинно в том и только том случае, когда оба простых выражения являются истинными. Такая ситуация возможно лишь в единственном случае, во всех остальных случаях конъюнкция ложна.

Обозначение: &, $\wedge$, $\cdot$.

Таблица истинности для конъюнкции

1. Если хотя бы одно из подвыражений конъюнкции ложно на некотором наборе значений переменных, то и вся конъюнкция будет ложной для этого набора значений.
2. Если все выражения конъюнкции истинны на некотором наборе значений переменных, то и вся конъюнкция тоже будет истинна.
3. Значение всей конъюнкции сложного выражения не зависит от порядка записи подвыражений, к которым она применяется (как в математике умножение).

Дизъюнкция или логическое сложение (в теории множеств это объединение)

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

Таблица истинности для дизъюнкции

1. Если хотя бы одно из подвыражений дизъюнкции истинно на некотором наборе значений переменных, то и вся дизъюнкция принимает истинное значение для данного набора подвыражений.
2. Если все выражения из некоторого списка дизъюнкции ложны на некотором наборе значений переменных, то и вся дизъюнкция этих выражений тоже ложна.
3. Значение всей дизъюнкции не зависит от порядка записи подвыражений (как в математике – сложение).

Готовые работы на аналогичную тему

Отрицание, логическое отрицание или инверсия (в теории множеств это отрицание)

Отрицание - означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО и в итоге получаем, что если исходное выражение истинно, то отрицание исходного – будет ложно и наоборот, если исходное выражение ложно, то его отрицание будет истинно.

Обозначения: не $A$, $\bar$, $¬A$.

Таблица истинности для инверсии

Импликация или логическое следование

Импликация - это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть, данная логическая операция связывает два простых логических выражения, из которых первое является условием ($A$), а второе ($A$) является следствием условия ($A$).

Обозначения: $\to$, $\Rightarrow$.

Таблица истинности для импликации

1. $A \to B = ¬A \vee B$.
2. Импликация $A \to B$ ложна, если $A=1$ и $B=0$.
3. Если $A=0$, то импликация $A \to B$ истинна при любом значении $B$, (из лжи может следовать истинна).

Эквивалентность или логическая равнозначность

Эквивалентность - это сложное логическое выражение, которое истинно на равных значениях переменных $A$ и $B$.

Обозначения: $\leftrightarrow$, $\Leftrightarrow$, $\equiv$.

Таблица истинности для эквивалентности

1. Эквивалентность истинна на равных наборах значений переменных $A$ и $B$.
2. КНФ $A \equiv B = (\bar \vee B) \cdot (A \cdot \bar)$
3. ДНФ $A \equiv B = \bar \cdot \bar \vee A \cdot B$

Строгая дизъюнкция или сложение по модулю 2 ( в теории множеств это объединение двух множеств без их пересечения)

Строгая дизъюнкция истинна, если значения аргументов не равны.

Для функции трёх и более переменных результат выполнения операции будет истинным только тогда, когда количество аргументов равных $1$, составляющих текущий набор — нечетное. Такая операция естественным образом возникает в кольце вычетов по модулю 2, откуда и происходит название операции.

Обозначения: $A \oplus B$ (в языках программирования), $A≠B$, $A \wedge B$ (в языках программирования).

Таблица истинности для операции сложения по модулю два

Свойства строгой дизъюнкции:

• $a \oplus 0 = a$(идемпотентность)
• $a \oplus 1 = \bar$(отрицание)
• $a \oplus a = 0$(получение 0)
• $a \oplus b = b \oplus a$(коммутативность)
• $(a \oplus b) \oplus c = a \oplus (b \oplus c)$(ассоциативность)
• $(a \oplus b) \oplus b = a$(поглощение)
• $\bar \oplus b = a \oplus \bar = (a \equiv b)$(сравнения по модулю)

Стрелка Пирса

Бинарная логическая операция, булева функция над двумя переменными. Названа в честь Чарльза Пирса и введена в алгебру логики в $1880—1881$ гг.

Обозначения: $\downarrow$ , ИЛИ-НЕ

Таблица истинности для стрелки Пирса

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

$X \downarrow X = ¬X$— отрицание

$(X \downarrow Y) \downarrow (X \downarrow Y) \equiv X \vee Y$ — дизъюнкция

$(X \downarrow X) \downarrow (Y \downarrow Y) \equiv X \wedge Y$ — конъюнкция

$((X \downarrow X) \downarrow Y) \downarrow ((X \downarrow X) \downarrow Y) = X \to Y$ — импликация

Штрих Шеффера

Булева функция двух переменных или бинарная логическая операция. Введена в рассмотрение Генри Шеффером в 1913 г.

Обозначения: $|$, эквивалентно операции И-НЕ.

Таблицей истинности для функции штрих Шеффера

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

$X \mid X = ¬X$ — отрицание

$(X \mid Y) \mid (X \mid Y) = (X \wedge Y)$ — конъюнкция

$(X \mid X) \mid (Y \mid Y) = X \vee Y$ — дизъюнкция

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

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

1. Инверсия(отрицание);
2. Конъюнкция (логическое умножение);
3. Дизъюнкция и строгая дизъюнкция (логическое сложение);
4. Импликация (следствие);
5. Эквивалентность (тождество).

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

Общие свойства

Для набора из $n$ логических переменных существует ровно $2^n$ различных значений. Таблица истинности для логического выражения от $n$ переменных содержит $n+1$ столбец и $2^n$ строк.

Читайте также:

  
• Нематериальные блага как объекты гражданских прав кратко
  
• Картотека педагогической и методической литературы начальная школа
  
• Что я могу сделать для охраны гидросферы в школе дома в природе ответ кратко
  
• Swot анализ технологии рефлексии начальная школа
  
• Что вы знаете об ускорении свободного падения на луне кратко