Эквиваленция это в информатике

Эквиваленция это в информатике

Эквиваленция — это логическая операция, принятая в формализованных языках (см. Язык формализованный) для образования сложных высказываний (формул) из элементарных (простых) высказываний (см. Высказывание) и по смыслу равнозначная строгому условию «если…, то…», принятому в естественном языке (см. Язык). Эквиваленция читается: «A эквивалентно B», или «A равнозначно B», или «A то же самое, что B», или «A, если и только если B», или «A, тогда и только тогда, когда B»; записывается: А ≡ В, другое обозначение эквиваленции: AB (применяются также стрелки другой формы, но всегда указывающие на соотношение равнозначности); другие названия эквиваленции: эквивалентность, равнозначность.

Понятие эквиваленции сформировалось в процессе обособления языка логики и его последующей символизации (см. Логика символическая). В классической логике (см. Логика), формальной логике (см. Логика формальная), языках формальных теорий (см. Формализация) и языках программирования эквиваленция составляет одну из пяти наиболее распространённых логических связок, или логических операций (см. Логические операции), наряду с конъюнкцией (см. Конъюнкция), дизъюнкцией (см. Дизъюнкция), импликацией (см. Импликация) и отрицанием (см. Отрицание).

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

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

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

Содержание понятия — совокупность существенных признаков, отраженных в этом понятии.

Объем понятия — множество предметов, каждому из которых принадлежат признаки, составляющие содержание понятия. Выделяют понятия общие и единичные.

Выделяют следующие отношения понятий по объему:

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

Суждение — это форма мышления, в которой что-либо утверждается или отрицается о предметах, признаках или их отношениях.

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

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

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

Высказывание — это любое предложение какого-либо языка (утверждение), содержание которого можно определить как истинное или ложное.

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

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

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

Высказывание называется простым (элементарным), если никакая его часть сама не является высказыванием.

Высказывание, состоящее из простых высказываний, называются составным (сложным).

Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами:
А = <Аристотель — основоположник логики>,
В = <На яблонях растут бананы>.

Обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания: "Сумма углов треугольника равна 180 градусов" устанавливается геометрией, причем — в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского — ложным.

Истинному высказыванию ставится в соответствие 1, ложному — 0. Таким образом, А = 1, В = 0.

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

Основные операции алгебры высказываний.

Логическая операция КОНЪЮНКЦИЯ (лат. conjunctio — связываю):

  • в естественном языке соответствует союзу и;
  • обозначение: &;
  • в языках программирования обозначение: and;
  • иное название: логическое умножение.

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

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

Наиме­но­ва­ние: Эквиваленция (образовано от латинского слова: aequivalens — равнозначный, равноценный, равносильный).
Опреде­ле­ние: Эквиваленция — это логическая операция, принятая в формализованных языках для образования сложных высказываний из простых и по смыслу равнозначная строгому условию «если…, то…», принятому в естественном языке.
Раздел: Концепты Концепты философского дискурса Концепты научного дискурса
Дискурс: Философия
Субдис­курс: Семантика Логическая семантика
Логика Логика формальная Логика символическая Логика высказываний
Связан­ные концепты: Логические операции Высказывание Конъюнкция Дизъюнкция Импликация Отрицание
Текст статьи: Авторы: Ф. И. Голдберг. Подготовка элект­рон­ной публи­ка­ции и общая редакция: Центр гума­нитар­ных техно­логий. Ответст­вен­ный редактор: А. В. Агеев . Инфор­ма­ция на этой стра­нице пери­оди­чески обнов­ля­ется. Послед­няя редакция: 08.02.2020.
Читайте также:  Не удалось инициализировать стим
А В А&В
1
1
1 1 1

Логическая операция ДИЗЪЮНКЦИЯ (лат. disjunctio — различаю):

  • в естественном языке соответствует союзу или;
  • обозначение: ;
  • в языках программирования обозначение: or;
  • иное название: логическое сложение.

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

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

А В АВ
1 1
1 1
1 1 1

Логическая операция ИНВЕРСИЯ (лат. inversio — переворачиваю):

  • в естественном языке соответствует словам "Неверно, что. " и частице не;
  • обозначение: не А, ;
  • в языках программирования обозначение: not;
  • иное название: отрицание.

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

Таблица истинности отрицания:

А не А
1
1

Функция логического сложения ИЛИ (ЛогЗнач1;ЛогЗнач2;…) дает значение TRUE (Истина), только тогда, когда хотя бы один логический аргумент имеют значение TRUE (1).

Функция логического отрицания НЕ(ЛогЗнач) дает значение TRUE (Истина), когда логический аргумент имеют значение FALSE (0) и, наоборот, значение FALSE (Ложь), когда логический аргумент имеют значение TRUE (1).

Логическая операция ИМПЛИКАЦИЯ (лат. implicatio — тесно связываю):

  • в естественном языке соответствует обороту Если . то . ;
  • обозначение: ;
  • иное название: логическое следование.

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

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

А В АВ
1
1 1
1
1 1 1

Логическая операция ЭКВИВАЛЕНЦИЯ (лат. аequivalens — равноценное):

  • в естественном языке соответствует оборотам речи тогда и только тогда и в том и только в том случае;
  • обозначение:

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

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

А В А

В

1 1 1 1 1 1

Логические операции имеют следующий приоритет: действия в скобках, инверсия , &, , ,

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

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

Алгоритм построения таблицы истинности:

  1. подсчитать количество переменных n в логическом выражении;
  2. определить число строк в таблице m = 2 n ;
  3. подсчитать количество логических операций в формуле;
  4. установить последовательность выполнения логических операций с учетом скобок и приоритетов;
  5. определить количество столбцов в таблице: число переменных плюс число операций;
  6. выписать наборы входных переменных с учетом того, что они представляют собой натуральный ряд n-разрядных двоичных чисел от 0 до 2 n -1;
  7. провести заполнение таблицы истинности по столбикам, выполняя логические операции в соответствии с установленной в п.4 последовательностью.
Читайте также:  Программа преобразующая текст в звук

Наборы входных переменных, во избежание ошибок, рекомендуют перечислять следующим образом:
а) определить количество наборов входных переменных;
б) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки 0, а нижнюю
в) разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами 0 или 1, начиная с группы 0;
г) продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами 0 или 1 до тех пор, пока группы 0 и 1 не будут состоять из одного символа.

Пример. Для формулы A&(B C ) построить таблицу истинности алгебраически и с использованием электронных таблиц.

Количество логических переменных 3, следовательно, количество строк в таблице истинности должно быть 2 3 = 8.

Количество логических операций в формуле 5, следовательно, количество столбцов в таблице истинности должно быть 3 + 5 = 8.

А В C ВC А & (ВC)
1
1
1 1
1 1 1
1 1 1
1 1
1 1 1 1
1 1 1 1 1

Логической (булевой) функцией называют функцию F(Х1, Х2, . Хn), аргументы которой Х1, Х2, . Хn (независимые переменные) и сама функция (зависимая переменная) принимают значения 0 или 1.

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

Логические функции могут быть заданы табличным способом или аналитически — в виде соответствующих формул.

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

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

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

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

    Закон двойного отрицания:
    не (не А) = A.
    Двойное отрицание исключает отрицание.

Переместительный (коммутативный) закон:
— для логического сложения:
А B = B A;

— для логического умножения:
A & B = B & A.

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

Сочетательный (ассоциативный) закон:
— для логического сложения:
(A B) C = A (B C);

— для логического умножения:
(A & B) & C = A & (B & C).

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

Распределительный (дистрибутивный) закон:
— для логического сложения:
(A B) & C = (A & C) (B & C);

— для логического умножения:
(A & B) C = (A C) & (B C).

Определяет правило выноса общего высказывания за скобку.

Закон общей инверсии (законы де Моргана):
— для логического сложения:
;

— для логического умножения:
.

Закон идемпотентности ( от латинских слов idem — тот же самый и potens -сильный; дословно — равносильный):
— для логического сложения:
A A = A;

— для логического умножения:
A & A = A.

Закон означает отсутствие показателей степени.

Законы исключения констант:
— для логического сложения:
A 1 = 1, A 0 = A;

— для логического умножения:
A & 1 = A, A & 0 = 0.

Закон противоречия:
A & (не A)= 0.

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

Закон исключения третьего:
A (не A) = 1.

Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе — ложно, третьего не дано.

Закон поглощения:
— для логического сложения:
A (A & B) = A;

— для логического умножения:
A & (A B) = A.

Закон исключения (склеивания):
— для логического сложения:
(A & B) ( & B) = B;

— для логического умножения:
(A B) & ( B) = B.

Закон контрапозиции (правило перевертывания):
(AB) = (BA).

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

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

  1. Ефимова О., Морозов В., Угринович Н. Курс компьютерной технологии с основами информатики. Учебное пособие для старших классов. — М.: ООО "Издательство АСТ"; АВF, 2000 г.
  2. Задачник-практикум по информатике. В 2-х томах/Под ред. И.Семакина, Е.Хеннера. — М.: Лаборатория Базовых Знаний, 2001 г.
  3. Угринович Н. Информатика и информационные технологии. 10-11 класс- М.: Лаборатория Базовых Знаний, АО "Московские учебники", 2001 г.
Читайте также:  Как настроить телефон смартфон

Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота речи «…тогда и только тогда, когда …».

Логическая операция эквивалентности «А тогда и только тогда, когда В» обозначается А≡В, А

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

Таблица 16 – Таблица истинности логической функции эквивалентности

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

Рассмотрим, например, два высказывания: А = «Компьютер может производить вычисления» и В = «Компьютер включён».

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

«Компьютер может производить вычисления тогда и только тогда, когда компьютер включён».

«Компьютер не может производить вычисления тогда и только тогда, когда компьютер не включён».

Составное высказывание, полученное с помощью операции эквивалентности, ложно, когда одно высказывание истинно, а другое — ложно:

«Компьютер может производить вычисления тогда и только тогда, когда компьютер не включён».

«Компьютер не может производить вычисления тогда и только тогда, когда компьютер включён».

Логические законы и правила преобразования логических выражений

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

Для логических величин обычно используются три операции:

Конъюнкция – логическое умножение (И) – and, &, Ʌ.

Дизъюнкция – логическое сложение (ИЛИ) – or, |, v.

Логическое отрицание (НЕ) – not, ¬.

Всякое высказывание тождественно самому себе:

Высказывание не может быть одновременно истинным и ложным. Если высказывание А истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно:

А & Ā=0

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

Высказывание может быть либо истинным, либо ложным – третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение «истина»:

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

Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание:

=А.

Законы де Моргана (общей инверсии)

= Ā & ;

= Ā .

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

Закон коммутативности (переместительный)

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

Логическое умножение А & В = В & А.

Закон ассоциативности (сочетательный)

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

Логическое умножение Логическое сложение

Закон дистрибутивности (распределительный)

В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые:

Дистрибутивность умножения относительно сложения

Дистрибутивность сложения относительно умножения

ab+ ас = а(b+с) — в алгебре

(А & В) v (A & С) =А & (B v С)

(A v В) & (A v С) = A v (B & С)

Рассмотрим в качестве примера применения законов логики преобразование логического выражения. Пусть нам необходимо упростить логическое выражение (А & В) v (А & ).

Воспользуемся законом дистрибутивности и вынесем за скобки А:

(А & В) v (А & ) = А & (B v ).

По закону исключённого третьего В v =1, следовательно:

А&(В v )=А & 1=А.

Ссылка на основную публикацию
Шантаж фотографиями в контакте что делать
Социальные сети привлекли к себе внимание большого количества людей. Это не могло не стать очередной лазейкой для желающих получить выгоду....
Что такое shell core
Офис built-to-suit Shell & core – состояние офисного помещения «под отделку», в данном помещении присутствуют только бетонная стяжка, стеклопакеты, подведенные...
Что такое sptd в daemon tools
Подлинный файл является одним из компонентов программного обеспечения SPTD Device Driver, разработанного Duplex Secure. Sptd.sys - это драйвер в Windows....
Широта на карте это
Это приложение предназначено для определения по картам географических координат местности на Земле. Программа определяет долготу и широту в выбранной точке...
Adblock detector