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

Обработка информации в ЭВМ во многом напоминает процесс мышления. Законы и формы мышления изучает наука, называемая логикой. Одним из ее разделов является математическая логика. В нем используются математические, в основном алгебра­ические, методы, впервые разработанные в трудах английского математика Джорджа Буля (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. Для каждого набора будет определенное значение функции, т.е. количество таких функций при всех возможных наборах двух аргументов будет выражаться четырехразрядным двоичным числом. Всего возможны 2⁴ = 16 различных элементарных функций. Из них кроме конъюнкции и дизъюнкции следует упомянуть функцию Пирса (другие названия — стрелка Пирса, функция Вебба) и функцию Шеффера (другое название — штрих Шеффера). Функция Пирса реализует логическое сложение с отрицанием, т.е. логическое ИЛИ —НЕ, функция Шеффера — логическое умножение с отрицанием, т. е. логическое И —НЕ.

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

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

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

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

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

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

Поиск по сайту: