Помощничек
Главная | Обратная связь

...

Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Элементарные логические функции



Обработка информации в ЭВМ во многом напоминает процесс мышления. Законы и формы мышления изучает наука, называемая логикой. Одним из ее разделов является математическая логика. В нем используются математические, в основном алгебра­ические, методы, впервые разработанные в трудах английского математика Джорджа Буля (1815 — 1864). Поэтому этот раздел логики называют также алгеброй логики, или булевой алгеброй. Предметом изучения алгебры логики являются суждения (высказывания), в связи с чем встречается и такое ее название как исчисление высказываний. В исчислении высказываний оперируют только такими суждениями, про которых известно, что они либо истинны, либо ложны (обязательно одно из двух). Каждое конкретное высказывание имеет вполне определенное значение истинности: для истинного высказывания это значение равно единице, для ножного — нулю.

Воспользуемся для обозначения высказываний прописными латинскими буквами и рассмотрим несколько из них: А — свинец — это металл; В — Земля больше Солнца; С — студенты — люди; О — дважды два -— четыре; Е — соль — сладкая. Запишем значения истинности для этих высказываний: А = 1; В = 0; С = 1; D = 1; Е = 0. Из подобных простых высказываний могут образовываться сложные. Например, «свинец — это металл, и Земля больше Солнца». Или «студенты — это люди, и дважды два — четыре». Значения истинности сложных высказываний зависят от истинности или ложности простых высказываний, т.е. являются их функциями. В нашем случае первое сложное высказывание обозначим F(A, В), а второе F(C, D). Запишем значения истинности этих функций: F(A, В) = 0; F(C, D) = 1. Функции, которые могут принимать только одно из двух значений (1 или 0), принято называть логическими (булевыми), или двоичными функциями. Аналогично и пе­ременные, входящие в логические функции и принимающие значения 1 или 0, называют логическими переменными.

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

В современных ЭВМ для записи и хранения информации используются электрические (чаще всего электронные и магнитные) элементы, имеющие два устойчивых состояния. Арифметические операции в этих ЭВМ выполняются над двоичными числами. Обработка информации проводится по правилам алгебры логики. Для обозначения состояний элементов, записи чисел, указания истинности и ложности суждений используются одни и те же условные знаки — 1 и 0. Благодаря этому соответствию между, на первый взгляд, разными явлениями и предметами оказывается возможным и практически удобным описывать работу ЭВМ с помощью алгебры логики.

Сложные высказывания строятся из простых с помощью логических связок-операций, которые выражаются словами «не», «и», «или». Этим словам соответствуют основные логические (булевы) функции: НЕ — инверсия, И — конъюнкция, ИЛИ — дизъюнкция. Простые высказывания являются аргументами. Составленные из этих простых высказываний сложные являются функциями этих аргументов.

Из приведенных выше простых высказываний (аргументов А, B, С, D и Е) можно составить различные сложные высказывания, т.е. сложные функции. Рассмотрим несколько таких сложных высказываний, построенных с использованием трех основных логических функций. Для записи этих основных логических функций и соответствующих им логических операций служат специальные математические знаки (подобно тому как для записи арифметических операций служат знаки «+», «-» и т.п.). При чтении записанных таким образом сложных функций используют привычные слова «не», «и», «или», выполняющие роль логических связок.

Простейшей логической связкой алгебры логики является операция отрицания, или инверсии, выражаемая в русском языке частицей «не». Если, например, имеем простое высказывание В «Земля больше Солнца», то новое сложное высказывание «Земля не больше Солнца» обозначается В и читается: «не В». Легко видеть, что если В — ложное высказывание (В = 0), то — истинное ( = 1), и наоборот, если В = 1, то = 0. Этот факт лежит в основе определения логической операции НЕ в виде формулы А + = 1. Из него следует, что А= , т. е. двойное отрицание логи­ческой функции восстанавливает ее прежнее значение.

В качестве второй логической связки рассмотрим операцию конъюнкции, выражаемую союзом «и». Обозначается конъюнкция знаком «^», который ставится между высказываниями. Если А и В — простые высказывания, то F(A, В) = А ^ В — сложное высказывание (читается: «А и В»). При этом суть операции конъюнкции определяется так. Сложное высказывание А ^ В истинно в том и только в том случае, если оба высказывания А и В истинны, т.е. А ^ В = 1 ^ 1 = 1; F(A, В) = 1. Но если одно из двух высказываний (или оба) ложное, то и сложное высказывание можно: А^В=1^0 = 0; А^В = 0^1=0;А^В=0^0 = 0. Это определение вполне соответствует смыслу союза «и», в чем можно убедиться, воспользовавшись высказываниями В, С, D и Д приве­денными выше. Сложное высказывание «студенты — люди, и дважды два — четыре» (С ^ D = 1 ^ I = I) истинно, а сложные высказывания «студенты — люди, и Земля больше Солнца» (С ^ B=1 ^ 0 = 0); «соль — сладкая, и дважды два — четыре» (E ^ D = 0 ^ 1 =0); «Земля больше Солнца, и соль — сладкая» (В ^ Е=0 ^ 0 = 0) являются ложными. Операцию конъюнкции, особенно в приложениях математической логики, часто называют операцией И, или логическим умножением, и обозначают, как в алгебре, знаком «•» или, вообще, его опускают.

Третья операция, которая употребляется в алгебре логики, выражается союзом «или», который в русском языке имеет два различных значения. В одном случае может быть исключающее «или», например в сложном высказывании «монета после паде­ния оказывается лежащей вверх «орлом» или «решкой». В другом высказывании «при стуке в дверь сестра или брат проснется» союз «или» не исключает возможности того, что проснутся оба. Логическая операция, соответствующая неисключающему ИЛИ, т.е. допускающему обе возможности, называется дизъюнкцией и обозначается знаком «v». Если А v В — два простых высказывания, то их дизъюнкция A v В (читается: «А или В») есть сложное высказывание, которое ложно тогда и только тогда, когда ложны оба высказывания, т.е. A v B=0 v 0 = 0, но A v B = 1 v 0 = 1, A v B = 0 v 1 = 1; A v В = 1 v 1 = 1. Часто операцию дизъюнкции называют логическим сложением и обозначают знаком «+».

Отрицание, конъюнкция и дизъюнкция относятся к элементарным логическим операциям. Функции одного и двух аргумен­тов называются элементарными, если логические выражения этих функций содержат не более одной логической элементарной операции. Элементарной функцией одного аргумента является отрицание (инверсия). При двух аргументах возможны четыре варианта их набора: 0 и 0; 0 и 1; 1 и 0; 1 и 1. Для каждого набора будет определенное значение функции, т.е. количество таких функций при всех возможных наборах двух аргументов будет выражаться четырехразрядным двоичным числом. Всего возможны 24 = 16 различных элементарных функций. Из них кроме конъюнкции и дизъюнкции следует упомянуть функцию Пирса (другие названия — стрелка Пирса, функция Вебба) и функцию Шеффера (другое название — штрих Шеффера). Функция Пирса реализует логическое сложение с отрицанием, т.е. логическое ИЛИ —НЕ, функция Шеффера — логическое умножение с отрицанием, т. е. логическое И —НЕ.

Четыре функции — дизъюнкция, конъюнкция, функция Пирса, функция Шеффера — относятся к функциям конституенты единицы или нуля. Они обращаются в 0 (или 1) при одном единственном варианте набора аргументов. При трех остальных вариантах эти функции обращаются соответственно в 1(или 0).

Дизъюнкция двух переменных обращается в 0 лишь в том случае, если оба входных аргумента равны 0. Функция Пирса при таком входном наборе обращается в 1.

Конъюнкция двух переменных обращается в 1 лишь в том случае, если оба входных аргумента равны 1. Функция Шеффера при таком входном наборе обращается в 0.

Таким образом, дизъюнкция и функция Шеффера относятся к функциям конституенты нуля, а конъюнкция и функция Пирса — к функциям конституенты единицы.

Функции дизъюнкции, конъюнкции, Шеффера и Пирса в общем случае могут быть функциями произвольного числа аргументов. Следовательно, можно определить их значения для любого входного набора, т.е. любого поданного на вход двоичного числа. Подобные функциональные зависимости и используются в вычислительной технике. Поскольку над двоичными числами выполняются операции по правилам арифметики, а над информацией, представленной в виде двоичных чисел, — операции по правилам алгебры логики, то в состав вычислительной машины входит специальное арифметико-логическое устройство (АЛУ).

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




©2015 studopedya.ru Все права принадлежат авторам размещенных материалов.