Какая операция равносильна выражению a b

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

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

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

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

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

Алфавит языка логики высказываний, разделен на следующие категории:

• пропозициональные буквы (пропозициональные переменные) — р, q, г, s, t, р,, q,, г,, s_p t, и т. п.;
• логические знаки (логические союзы);
• технические знаки.

Логические и технические знаки приведены в таблице 3.1.

Элементы алфавита языка логики высказываний

Логические знаки (логические союзы)

Знак конъюнкции (И)

Знак дизъюнкции (включающее ИЛИ)

Знак строгой дизъюнкции (исключающее ИЛИ)

Окончание табл. 3.1

Технические знаки

Простые высказывания в алгебре логики обозначают заглавными латинскими буквами:

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

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

Логическая операция конъюнкции (логическое умножение)

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

Операция в естественном языке выражается связкой «и». Обозначается знаком л точкой «•» (в алгебре высказываний — знаком &), в языках программирования имеет обозначение And либо &&, например: А & В; A and В; А && В.

В алгебре множеств конъюнкции соответствует операция пересечения множеств, т. е. множеству, получившемуся в результате умножения множеств А и В, соответствует множество, состоящее из элементов, принадлежащих одновременно двум множествам. Высказывание А • В истинно тогда и только тогда, когда оба высказывания А и В истинны. Например, высказывание «10 делится на 2 и 5 больше 3» истинно, а высказывания «10 делится на 2 и 5 не больше 3», «10 не делится на 2 и 5 больше 3», «10 не делится на 2 и 5 не больше 3» ложны.

Логическая операция дизъюнкции (логическое сложение)

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

В обычной речи операция дизъюнкции, выражается связкой «или» и обозначается знаком «V» (или плюсом), в языках программирования имеет обозначение or, || либо |. Например: А | В; А || В; A or В.

В алгебре множеств дизъюнкции соответствует операция объединения множеств, т. е. множеству, получившемуся в результате сложения множеств А и В, соответствует множество, состоящее из элементов, принадлежащих либо множеству А, либо множеству В. Высказывание A v В ложно тогда и только тогда, когда оба высказывания А и В ложны. Например, высказывание «10 не делится на 2 или 5 не больше 3» ложно, а высказывания «10 делится на 2 или 5 больше 3», «10 делится на 2 или 5 не больше 3», «10 не делится на 2 или 5 больше 3» истинны.

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

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

Обозначается чертой над высказыванием А либо знаком например: -А. В обычной речи операция выражается словом «не», соответствует словам «неверно, что. », в языках программирования имеет обозначения Not, ~ !, например: ~А; !А; not А.

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

Высказывание А истинно, когда А ложно, и ложно, когда А истинно (например, «Луна — спутник Земли» (А); «Луна — не спутник Земли» (А).

Логическая операция импликации (логическое следование)

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

3.3. Основные операции алгебры логики (высказываний) условие (первое высказывание) истинно, а следствие (второе высказывание) ложно (обозначение —>).

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

Высказывание А—>В ложно тогда и только тогда, когда А истинно, а В ложно.

Импликация связывает два элементарных высказывания (например, высказывания: «данный четырехугольник — квадрат» (А) и «около данного четырехугольника можно описать окружность» (В).

Рассмотрим составное высказывание А >В, понимаемое как «если данный четырехугольник квадрат, то около него можно описать окружность». Есть три варианта, когда высказывание А^В истинно:

1) А истинно и В истинно, т. е. данный четырехугольник квадрат и около него можно описать окружность;
2) А ложно и В истинно, т. е. данный четырехугольник не является квадратом, но около него можно описать окружность (это справедливо не для всякого четырехугольника);
3) А ложно и В ложно, т. е. данный четырехугольник не является квадратом, и около него нельзя описать окружность.

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

В обычной речи связка «если. то» описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому импликации, образованные высказываниями, совершенно не связанными по содержанию, могут показаться бессмысленными. Например: «если множество деревьев — лес, то в Африке водятся жирафы», «если арбуз — ягода, то в кране есть вода».

Импликацию можно выразить через дизъюнкцию и отрицание:

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

Эквиваленция (равносильно), или двойная импликация, — логическая операция, ставящая в соответствие каждым двум про-139

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

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

Обозначается знаком В истинно тогда и только тогда, когда значения А и В совпадают. Например, высказывания: «24 делится на 6 тогда и только тогда, когда 24 делится на 3», «23 делится на 6 тогда и только тогда, когда 23 делится на 3» истинны, а высказывания «24 делится на 6 тогда и только тогда, когда 24 делится на 5», «21 делится на 6 тогда и только тогда, когда 21 делится на 3» ложны.

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

А В = (A v В) • (В v А).

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

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

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

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

F (А, В, С) = А л (-В v С);

F(xl, х2, хЗ) = —>xl v х2 л -хЗ.

Логическую функцию можно задать двумя способами: логической формулой или таблицей истинности.

ЛОГИЧЕСКИЕ ФОРМУЛЫ. ТАБЛИЦЫ ИСТИННОСТИ

Логические законы

Алгебра логики построена на законах и тождествах.

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

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

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

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

В алгебре логики доказано, что любую логическую функцию можно выразить только через комбинацию логических операций И, ИЛИ и НЕ. Для приведения логических выражений к эквивалентным, но более простым в записи используют ряд логических законов.

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

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

Закон исключенного третьего утверждает, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно; третьего не дано: «Сегодня я либо 141

получу 10, либо не получу». Истинно либо суждение, либо его отрицание

Закон двойного отрицания заключается в том, что отрицать отрицание какого-нибудь высказывания то же, что утверждать это высказывание: «Неверно, что 2 • 2<>4»

Законы идемпотентности утверждают, что в алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых «сомножителей» равносильна одному из них; дизъюнкция одинаковых «слагаемых» равносильна одному из них:

Законы коммутативности и ассоциативности заключаются в том, что конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел:

• законы ассоциативности:
(х v у) v z = х v (у v z);
(х Л у) Л z = X Л (у Л z).

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

х v (у л z) = (х v у) л (х v z);

х л (у v z) = (х л у) V (х л z).

Законы де Моргана показывают как отрицаются высказывания:

Данные законы можно выразить в следующих кратких формулировках:

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

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

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

Описания некоторых логических законов приведены в таблице 3.2.

Основные логические законы

А + В = В + А; А • В = В • А либо

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

А + (В + С) = (А + В) + С;

А • (В • С) = (А • В) • С либо

х v (у v z) = (х v у) v z;

X • (у • Z) = (х • у) • Z

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

А • (В + С) = А • В + А • С;

А + (В • С) = (А + В) • (А + С) либо

х • (у v z) = х • у v х • z;

х v (у • z) — (х v у) • (х v z)

Относительно сложения указывает на то, что общий множитель можно выносить за скобки. Этот закон так же, как пере-

Продолжение табл. 3.2

местительный и сочетательный, подобен аналогичному закону обычной алгебры

А + А — А; А • А = А либо х v х = х; х • х — X

Закон для логического сложения (равносильности). Для логического умножения закон означает отсутствие показателей степени

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

А + В = А В; А В = А + В либо

х v у = у • х; ху = уvx

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

Если существует операция логического умножения двух и более элементов, операция «и» — (АлВ), то для того, чтобы найти обратное от всего суждения ~(АлВ), необходимо найти обратное от каждого элемента и объединить их операцией логического сложения (~А+~В). Закон работает аналогично в обратном направлении: ~(А+В) = (~Ал~В)

Законы инверсии (отрицания). Операция переменной с ее инверсией

А + А = 1; АА = 0 либо xvx = 1; хх = 0

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

Окончание табл. 3.2

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

В основе закона лежит принцип классической логики, согласно которому, если неверно, что неверно А, то А верно

(А + В) • (А + В ) = А либо
(X • У) v (X • у) = у;
(X V у) • (X V у) = у

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

А+А • В = А + В либо

Показывают порядок упрощения логических выражений при повторе операнда

Правила операций с константами имеют следующий вид:

х • 1 = х; х • 0 = 0.

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

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

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

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

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

Нарушения законов логики приводят к логическим ошибкам и вытекающим из них противоречиям.

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

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

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

Буквенные выражения -А, (А —> В) и др. — это схемы формул. Например, выражение (А л В) есть схема формул (р л q), (р л (г v s)).

Определения формулы логики высказываний:

• пропозициональная переменная есть формула;
• если А — произвольная формула, то ->А — тоже формула;
• если А и В — произвольные формулы, то (А В), (А л В), (А В), (A v В) и (A v В) — тоже формулы.

Других формул в языке логики высказываний нет.

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

Язык логики высказываний можно рассматривать как множество пропозициональных формул.

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

В качестве примера рассмотрим высказывание: «Если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог». Это высказывание формализуется в виде формулы (A v В) —> С. При определенных сочетаниях значений переменных А, В и С она принимает значение «истина», при некоторых других сочетаниях — значение «ложь». Такие формулы называют выполнимыми.

Некоторые формулы принимают значение «истина» при любых значениях истинности входящих в них переменных.

Таковой будет, например, формула A v А, соответствующая высказыванию: «Этот треугольник прямоугольный или косоугольный». Данная формула истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный. Такие формулы называют тождественно истинными формулами, или тавтологиями. Высказывания, которые формализуются тавтологиями, называют логически истинными высказываниями.

В качестве другого примера рассмотрим формулу А • А, которой соответствует, например, высказывание: «Катя самая высокая девушка в группе, и в группе есть девушки выше Кати». Очевидно, что эта формула ложна, так как либо А, либо А обязательно ложно. Такие формулы называют тождественно ложными формулами, или противоречиями. Высказывания, которые формализуются противоречиями, называют логически ложными высказываниями.

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

Равносильность двух формул алгебры логики обозначают символом «=». Так, выражения А -> В и (-’A) v В равносильны, зАлВиАуВ — нет (значения выражений разные, например, при А = 1, В = 0). Замену формулы другой, ей равносильной, называют равносильным преобразованием данной формулы.

Пример. Запишем в форме логического выражения составное высказывание:

(2-2 = 5 или 2-2 = 4)и(2’2#5 или 2-2^4).

Проанализируем составное высказывание. Оно содержит два простых высказывания:

А = 2 • 2 = 5 — ложно (0);

В = 2 • 2 = 4 — истинно (1).

Перепишем составное высказывание. Получим:

(А или В) и (А или В).

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

Выполняем логические операции в строго определенном порядке.

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

F = (A v В) л (A v В) = (0 v 1) л (1 v 0) = 1 л 1 = 1.

Упрошение логических формул

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

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

Приемы и способы, применяемые при упрощении логических формул:

1) законы алгебры логики применяют в следующем порядке: правило де Моргана, сочетательный закон, правило операций переменной с ее инверсией и правило операций с константами:

xvy-(x-y) = x- y-(x-y) = x- x- y- y = O- y- y = O- y = O;

2) применяют правило де Моргана, выносят за скобки общий множитель, используют правило операций переменной с ее инверсией):

Х-у V X V у V X = Х-у VX-y VX = Х-(у vy) V X = X VX = 1;

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

(х v у) • (х v у) • (х v у) = (х v у) • (х v у)(х v у) • (х v у) = у • х;

= x- yvx-y-zvx-y-zvx-y-z = (x-yvx-y-z)v(x-y-zvx-y-z) =

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

6) выносят за скобки общие множители; применяют правило операций с константами:

х-уvх у• zvх• z •р = х- (у (1 vz)vz •р) = х (уv z •р);

7) к отрицаниям неэлементарных формул применяют правило де Моргана; используют законы двойного отрицания и склеивания:

xvy-zvxvyvz = xvyvzvx-y-z = xvyvzvx-y-z =

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

= х • ((у v у ? z) v (у • z v у • z)) = х • (у v у ? z v 1) = х • 1 = х;

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

(x-yvz)-(xvy)vz = x- y- xvx-y-yvz-xvz-yvz = OvOv

VZ ? XV Z • у V Z = Z — XV (zv z) • (у V z) = Z • XV 1 • (у V z) = Z • XV у V vz = (z • x v z) v у = (z v z) • (x v z) v у = 1 ? (x v z) v у = x v z v у;

10) используют правило де Моргана, закон двойного отрицания и закон поглощения:

= x-y-(x-zvx-yvzvz-t) = x-yvx-y-zvx-y-z-t = x-y.

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

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

Из этого следует два вывода:

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

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

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

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

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

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

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

Построить таблицу истинности, описывающую работу логических элементов, не сложно при небольшом количестве входных переменных. Если же число переменных больше трех, то таблица получается слишком большой. Так, при наличии четырех переменных, количество наборов в таблице будет равно 16, а уже при шести переменных — 64. Необходимо также учитывать скобки, приоритет и количество операций.

Общее количество всех возможных комбинаций в таблице можно определить по формуле

N = 2″;

где N — общее число возможных комбинаций; п — количество входных переменных.

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

1) подсчитать количество переменных п в логическом выражении;

2) определить число строк в таблице;
3) подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице (равно количеству переменных + количество операций);
4) ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов;
5) заполнить столбцы входных переменных наборами значений;
6) провести заполнение таблицы истинности по столбцам, выполняя логические операции.

Наборы входных переменных, во избежание ошибок, рекомендовано перечислять следующим образом:

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

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

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

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

(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) и т. д.

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

Пример. Составить таблицу истинности при условии: В v (В л A) =f(ab 152

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

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

Эквиваленция

Примеры:

1. Таблица истинности для формулы x-yvxvyvx, которая содержит две переменные X и у.

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

Промежуточные логические формулы

Из таблицы видно, что при всех наборах значений переменных х и у формула x yvxvyvx принимает значение 1, т. е. является тождественно истинной.

2. Таблица истинности для формулы xvy-(x-y).

Промежуточные логические формулы

Из таблицы видно, что при всех наборах значений переменных х и у формула xvy-(x-y) принимает значение 0, т. е. является тождественно ложной.

3. Таблица истинности для формулы xvyvx-z.

Промежуточные логические формулы

Из таблицы видно, что формула xvyvx-z в некоторых случаях принимает значение 1, а в некоторых — 0, т. е. является выполнимой.

Пример построения таблиц истинности для сложных выражений.

Составить таблицу истинности логического выражения

Решение. Определяем количество строк: на входе три простых высказывания: А, В, С поэтому п = 3 и количество строк 2 3 + + 1 = 9.

Определяем количество столбцов. Простые выражения (переменные): А, В, С; промежуточные результаты (логические операции): -^А — инверсия (обозначим через Е); В v С — операция 154

3.3. Основные операции алгебры логики (высказываний) дизъюнкции (обозначим через F); а также искомое окончательное значение арифметического выражения: D = -А л (В v С), т. е. D = -•? л F — это операция конъюнкции.

Заполняем столбцы с учетом таблиц истинности логических операций.

Пример построения логической функции по ее таблице истинности (решение обратной задачи).

Пусть дана таблица истинности для некоторой логической функции Z(X, Y).

Составить логическую функцию для заданной таблицы истинности.

Правила построения логической функции по ее таблице истинности:

• выделить в таблице истинности те строки, в которых значение функции равно 1;
• выписать искомую формулу в виде дизъюнкции нескольких логических элементов (число этих элементов равно числу выделенных строк);
• каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции;

• если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент взять с отрицанием.

Решение. В первой и третьей строках таблицы истинности значение функции равно 1. Так как строки две, получаем дизъюнкцию двух элементов: (Y) v (Y). Каждый логический элемент в этой дизъюнкции запишем в виде конъюнкции аргументов функции X и Y: (X л Y) v (X л Y). Возьмем аргумент с отрицанием, если его значение в соответствующей строке таблицы равно 0, и получаем искомую функцию: Z (X, Y) =(->Х л -Y) v V (X л -Y).

Логические элементы компьютера

Логические элементы — устройства, предназначенные для обработки информации в цифровой форме (последовательность сигналов ВЫСОКОГО — 1 и низкого — 0 уровней в двоичной логике, последовательность 0, 1 и 2 в троичной логике, последовательности 0, 1,2, 3, 4, 5, 6, 7, 8 и 9 в десятичной логике).

С развитием электротехники от механических логических элементов перешли к электромеханическим логическим элементам (на электромагнитных реле), а затем к электронным логическим элементам на электронных лампах, позже на транзисторах.

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

Логические элементы выполняют логическую функцию (операцию) над входными сигналами (операндами, данными).

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

Всего возможно 2 |? ” =2 4 =16 двоичных двухвходовых логических элементов и 2′ » = 2* =256 двоичных трехвходовых логических элементов (булева функция).

Кроме 16 двоичных двухвходовых логических элементов и 256 трехвходовых двоичных логических элементов возможны 19 683 двухвходовых троичных логических элементов и 7 625 597 484 987 трехвходовых троичных логических элементов (троичные функции).

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

Логическими элементами компьютеров являются такие электронные схемы, как И, ИЛИ, НЕ, И-НЕ, ИЛИ-HE и другие (называемые также вентилями), а также триггер.

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

Работу логических элементов описывают с помощью таблиц истинности.

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

Схема И реализует конъюнкцию двух или более логических значений.

Условное обозначение схемы И с двумя входами и соответствующая таблица истинности представлены на рисунке 3.1.

Рис. 3.1. Представление логической схемы И

Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Если хотя бы на одном входе будет О, на выходе также будет 0.

Связь между выходом z этой схемы и входами х и у описывается соотношением: z — хлу (читается как «х и у»).

Операцию конъюнкции на функциональных схемах обозначают знаком &.

Схема ИЛИ реализует дизъюнкцию двух или более логических значений.

Если хотя бы на одном входе схемы ИЛИ будет 1, то на ее выходе также будет 1.

Условное обозначение схемы ИЛИ и соответствующая таблица истинности представлены на рисунке 3.2. Знак «1» на схеме (устаревшее обозначение дизъюнкции) означает, что значение дизъюнкции равно 1, если сумма значений операндов больше или равна 1. Связь между выходом z этой схемы и входами х и у описывают соотношением: z = х v у (читается как «х или у»).

Рис. 3.2. Представление логической схемы ИЛИ

Схема НЕ (инвертор) реализует операцию отрицания. Связь между входом х этой схемы и выходом z можно записать соотношением z = х ( х читается как «не х» или «инверсия х»).

Если на входе схемы 0, то на выходе 1, если на входе 1, то на выходе 0. Условное обозначение инвертора и соответствующая таблица истинности представлены на рисунке 3.3.

Представление логической схемы НЕ

Рис. 3.3. Представление логической схемы НЕ

Схема И-НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И.

Связь между выходом z и входами х и у схемы записывают следующим образом: z = x-y (х-у читается как «инверсия х и у»).

Условное обозначение и соответствующая таблица истинности схемы И-НЕ представлены на рисунке 3.4.

Рис. 3.4. Представление логической схемы И-НЕ

Схема ИЛИ-HE состоит из элемента ИЛИ и инвертора и осуществляет отрицание результата схемы ИЛИ.

Связь между выходом z и входами х и у схемы записывают следующим образом: z = xvy (xvy читается как «инверсия х или у». Условное обозначение и соответствующая таблица истинности схемы ИЛИ-HE представлены на рисунке 3.5.

Рис. 3.5. Представление логической схемы ИЛИ-НЕ

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

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

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

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

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

Для представления двух логических состояний (1 и 0) в вен

тилях соответствующие им входные и выходные сигналы имеют один из двух установленных уровней напряжения, например +5 В и 0 В. Высокий уровень обычно соответствует значению «истина» (1), а низкий — значению «ложь» (0).

Сумматор — это электронная логическая схема, выполняющая

суммирование двоичных чисел.

Сумматоры широко используют в АЛУ процессора. Сумматор служит, прежде всего, центральным узлом АЛУ, однако находит применение также и в других устройствах компьютера.

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

Рис. 3.6. Представление многоразрядного двоичного сумматора

Сложение чисел А и В в одном z-м разряде осуществляется с помощью:

• цифры а_; первого слагаемого;
• цифры Ь. второго слагаемого;
• переноса р._ч из младшего разряда.

В результате сложения получают две цифры:

• цифра с для суммы;
• перенос р.из данного разряда в старший.

Таким образом, одноразрядный двоичный сумматор есть устройство с тремя входами и двумя выходами.

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

Например, схема вычисления суммы С = (с₃ с₂ с, с₀) двух двоичных трехразрядных чисел А = (а, а, а₀) и В = (Ь₂ Ц Ь₍₎) может иметь вид, приведенный на рисунке 3.7.

Рис. 3.7. Схема вычисления суммы двух двоичных трехразрядных чисел

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

Триггеры в основном используют в регистрах процессора.

Термин «триггер» происходит от английского слова trigger (защелка, спусковой крючок). Для обозначения этой схемы в английском языке употребляют термин flip-flop (хлопанье), что ука-161 зывает на способность данной электронной схемы почти мгновенно переходить (перебрасываться) из одного электрического состояния в другое и наоборот.

Самый распространенный тип триггера — так называемый RS-триггер (от англ, set — установка и reset — сброс). Условное обозначение триггера приведено на рисунке 3.8.

Схема триггера

Рис. 3.8. Схема триггера

Триггер имеет два симметричных входа S и R и два симметричных выхода Q и Q, причем выходной сигнал Q является логическим отрицанием сигнала Q.

На каждый из двух входов S и R могут подаваться входные сигналы в виде кратковременных импульсов (_ПП_ ).

Наличие импульса на входе будем считать 1, а его отсутствие — 0.

На рисунке 3.9 показаны реализация триггера с помощью вентилей ИЛИ-HE и соответствующая таблица истинности.

Рис. 3.9. Представление триггера

Проанализируем возможные комбинации значений входов R и S триггера, используя его схему и таблицу истинности схемы ИЛИ-HE (см. рис. 3.9). 162

3.3. Основные операции алгебры логики (высказываний) OO0QO0QO0QO0QOQOCOOCpO0<>O0QC0QCQQC9OQpOQQOQQOQQC9QC0OQ<>OQ<>OQQC4QC9QC9OQ9CQ<>CQQOQQC9QC0O40OOOOCCCCOCOOCOCCOOO«C«OC«CC««)COOC>X>C4CCCOCCO4OOOOCOCOOOOOCCOOOO4OOOOOOO

Если на входы триггера подать S = 1, R = 0, то независимо от состояния на выходе Q верхнего вентиля появится 0. После этого на входах нижнего вентиля окажется R = 0, Q = 0 и выход Q станет равным 1.

При подаче 0 на вход S и 1 на вход R на выходе Q появится 0, а на Q — 1.

Если на входы R и S подана логическая единица, то состояние Q и Q не меняется.

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

Поскольку один триггер может запомнить только один разряд двоичного кода, то для запоминания байта нужно 8 триггеров, а для килобайта — соответственно 8 • 2 10 = 8192 триггера.

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

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

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

Переключателю X соответствует логическая переменная х, которая принимает значение 1 в том и только в том случае, когда переключатель X замкнут и схема проводит ток; если же переключатель разомкнут, то х равен нулю.

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

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

Найдем функции проводимости F некоторых переключательных схем:

а) О——О
(схема не содержит переключателей и проводит ток всегда, следовательно F = 1);

(схема содержит один постоянно разомкнутый контакт, следовательно F = 0);
в) О——х——о
(схема проводит ток, когда переключатель х замкнут, и не проводит, когда х разомкнут, следовательно F(x) = х);
г) О——х»——О
(схема проводит ток, когда переключатель х разомкнут, и не проводит, когда х замкнут, следовательно, F(x) = х);
д) О——X——у——о
(схема проводит ток, когда оба переключателя замкнуты, следовательно F(x) = х • у);
——У——
(схема проводит ток, когда хотя бы один из переключателей замкнут, следовательно F(x) = х v у);

(схема состоит из двух параллельных ветвей и описывается функцией F(x, у, z) = (х • у) v z v (х • у) • z).

Две схемы называют равносильными, если через одну из них проходит ток тогда и только тогда, когда он проходит через другую (при одном и том же входном сигнале). Из двух равносильных 164

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

При рассмотрении переключательных схем возникают две основные задачи: синтез и анализ схемы.

Синтез схемы по заданным условиям ее работы сводится к следующим трем этапам:

1) составление функции проводимости по таблице истинности, отражающей эти условия;
2) упрощение этой функции;
3) построение соответствующей схемы.

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

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАЛАНИЯ

1. Определите понятие алгебры логики.
2. Перечислите и охарактеризуйте этапы развития логики.
3. Что представляет собой формальная логика?
4. Что представляет собой математическая логика?
5. Что такое понятие?
6. Что такое умозаключение?
7. Что такое суждение (высказывание)?
8. Укажите основные операции алгебры логики.
9. Из чего состоит алфавит языка логики высказываний?
10. Опишите подробно операции: отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность.
11. Перечислите и поясните логические законы.
12. Для чего нужны логические формулы?
13. Что такое пропозициональная формула?
14. Как происходит упрощение логических формул?
15. Что такое таблица истинности?
16. Поясните правила построения таблиц истинности.
17. Раскройте правила построения логической функции по ее таблице истинности.
18. Что такое логические элементы компьютера?
19. Для чего необходимы логические схемы?

20. Что представляет собой двоичный сумматор?
21. Что такое триггер?
22. Что такое переключательная схема?

ПРАКТИЧЕСКИЕ ЗАДАНИЯ

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

а) Солнце есть спутник Земли;
б) 2 + 3 = 4;
в) сегодня отличная погода;
г) в романе Л.Н. Толстого «Война и мир» 3 432 536 слов;
д) Санкт-Петербург расположен на Неве;
е) музыка Баха слишком сложна;
ж) первая космическая скорость равна 7,8 км/с;
з) железо — металл;
и) если один угол в треугольнике прямой, то треугольник будет тупоугольным;
к) если сумма квадратов двух сторон треугольника равна квадрату третьей, то он прямоугольный.

а) арифметика;
б) физика;
в) биология;
г) информатика;
д) геометрия;
е) повседневная жизнь.

Истинные высказывания’, а) 2 + 2 = 4; б) сила притяжения тел обратно пропорциональна квадрату расстояния между ними;

в) зайцы питаются растениями; г) бит — фундаментальная единица информации, используемая в теории информации; д) два треугольника равны, если две стороны и угол между ними одного треугольника равны двум сторонам и углу между ними другого треугольника; е) понедельник — первый день недели. 166

Ложные высказывания’, а) 4 + 3 = 5; б) тело падает на Землю с ускорением, пропорциональным его массе; в) животные — это неживая природа; г) информатика — наука о термической обработке металлов; д) квадрат — это фигура, у которой пять сторон; е) лев — домашнее животное.

Логические выражения

Алгебра логики (англ. algebra of logic) — один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях.

Основоположником алгебры логики является английский математик и логик Дж. Буль (1815–1864), положивший в основу своего логического учения аналогию между алгеброй и логикой. Любое высказывание он записывал с помощью символов разработанного им языка и получал «уравнения», истинность или ложность которых можно было доказать, исходя из определенных логических законов, таких как законы коммутативности, дистрибутивности, ассоциативности и др.

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

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

Например, «3 умножить на 3 равно 9», «Архангельск севернее Вологды» — истинные высказывания, а «Пять меньше трех», «Марс — звезда» — ложные.

Очевидно, что не всякое предложение может быть логическим высказыванием, т. к. не всегда есть смысл говорить о его ложности или истинности. Например, высказывание «Информатика — интересный предмет» неопределенно и требует дополнительных сведений, а высказывание «Для ученика 10-А класса Иванова А. А. информатика — интересный предмет» в зависимости от интересов Иванова А. А. может принимать значение «истина» или «ложь».

Кроме двузначной алгебры высказываний, в которой принимаются только два значения — «истинно» и «ложно», существует многозначная алгебра высказываний. В такой алгебре, кроме значений «истинно» и «ложно», употребляются такие истинностные значения, как «вероятно», «возможно», «невозможно» и т. д.

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

Обозначим как А высказывание «Алгебра логики успешно применяется в теории электрических схем», а через В — «Алгебра логики применяется при синтезе релейно-контактных схем».

Тогда составное высказывание «Алгебра логики успешно применяется в теории электрических цепей и при синтезе релейно-контактных схем» можно кратко записать как А и В; здесь «и» — логическая связка. Очевидно, что поскольку элементарные высказывания А и В истинны, то истинно и составное высказывание А и В.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение.

Логических значений всего два: истина (TRUE) и ложь (FALSE). Это соответствует цифровому представлению — 1 и 0. Результаты каждой логической операции можно записать в виде таблицы. Такие таблицы называют таблицами истинности.

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

1. Логическое отрицание, инверсия (лат. inversion — переворачивание) — логическая операция, в результате которой из данного высказывания (например, А) получается новое высказывание (не А), которое называется отрицанием исходного высказывания, обозначается символически чертой сверху ($A↖$) или такими условными обозначениями, как ¬, ‘not’, и читается: «не А», «А ложно», «неверно, что А», «отрицание А». Например, «Марс — планета Солнечной системы» (высказывание А); «Марс — не планета Солнечной системы» ($A↖$); высказывание «10 — простое число» (высказывание В) ложно; высказывание «10 — не простое число» (высказывание B ) истинно.

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

A	¬A
истина	ложь
ложь	истина

A	¬A
1	0
0	1

Высказывание $A↖$ ложно, когда А истинно, и истинно, когда А ложно.

Геометрически отрицание можно представить следующим образом: если А — это некоторое множество точек, то $A↖$ — это дополнение множества А, т. е. все точки, которые не принадлежат множеству А.

2. Конъюнкция (лат. conjunctio — соединение) — логическое умножение, операция, требующая как минимум двух логических величин (операндов) и соединяющая два или более высказываний при помощи связки «и» (например, «А и В»), которая символически обозначается с помощью знака ∧ (А ∧ В) и читается: «А и В». Для обозначения конъюнкции применяются также следующие знаки: А ∙ В; А & В, А and В, а иногда между высказываниями не ставится никакого знака: АВ. Пример логического умножения: «Этот треугольник равнобедренный и прямоугольный». Данное высказывание может быть истинным только в том случае, если выполняются оба условия, в противном случае высказывание ложно.

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

A	B	A ∧ B
истина	ложь	ложь
ложь	истина	ложь
ложь	ложь	ложь
истина	истина	истина

A	B	A ∧ B
1	0	0
0	1	0
0	0	0
1	1	1

Высказывание А ∧ В истинно только тогда, когда оба высказывания — А и В истинны.

Геометрически конъюнкцию можно представить следующим образом: если А, В — это некоторые множества точек, то А ∧ В есть пересечение множеств А и В.

3. Дизъюнкция (лат. disjunction — разделение) — логическое сложение, операция, соединяющая два или более высказываний при помощи связки «или» (например, «А или В»), которая символически обозначается с помощью знака ∨ (А ∨ В) и читается: «А или В». Для обозначения дизъюнкции применяются также следующие знаки: А + В; А or В; А | B. Пример логического сложения: «Число x делится на 3 или на 5». Это высказывание будет истинным, если выполняются оба условия или хотя бы одно из условий.

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

A	B	A ∨ B
истина	ложь	истина
ложь	истина	истина
ложь	ложь	ложь
истина	истина	истина

A	B	A ∨ B
1	0	1
0	1	1
0	0	0
1	1	1

Высказывание А ∨ В ложно только тогда, когда оба высказывания — А и В ложны.

Геометрически логическое сложение можно представить следующим образом: если А, В — это некоторые множества точек, то А ∨ В — это объединение множеств А и В, т. е. фигура, объединяющая и квадрат, и круг.

4. Дизъюнкция строго-разделительная, сложение по модулю два — логическая операция, соединяющая два высказывания при помощи связки «или», употребленной в исключающем смысле, которая символически обозначается с помощью знаков ∨ ∨ или ⊕ (А ∨ ∨ В, А ⊕ В) и читается: «либо А, либо В». Пример сложения по модулю два — высказывание «Этот треугольник тупоугольный или остроугольный». Высказывание истинно, если выполняется какое-то одно из условий.

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

А	В	А ⊕ B
истина	ложь	истина
ложь	истина	истина
ложь	ложь	ложь
истина	истина	ложь

А	В	А ⊕ B
1	0	1
0	1	1
0	0	0
1	1	0

Высказывание А ⊕ В истинно только тогда, когда высказывания А и В имеют различные значения.

5. Импликация (лат. implisito — тесно связываю) — логическая операция, соединяющая два высказывания при помощи связки «если. то» в сложное высказывание, которое символически обозначается с помощью знака → (А → В) и читается: «если А, то В», «А влечет В», «из А следует В», «А имплицирует В». Для обозначения импликации применяется также знак ⊃ (A ⊃ B). Пример импликации: «Если полученный четырехугольник квадрат, то около него можно описать окружность». Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием. Результат операции ложен только тогда, когда предпосылка есть истина, а следствие — ложь. Например, «Если 3 * 3 = 9 (А), то Солнце — планета (В)», результат импликации А → В — ложь.

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

А	В	А → В
истина	ложь	ложь
ложь	истина	истина
ложь	ложь	истина
истина	истина	истина

А	В	А → В
1	0	0
0	1	1
0	0	1
1	1	1

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

6. Эквивалентность, двойная импликация, равнозначность (лат. aequalis — равный и valentis — имеющий силу) — логическая операция, позволяющая из двух высказываний А и В получить новое высказывание А ≡ В, которое читается: «А эквивалентно B». Для обозначения эквивалентности применяются также следующие знаки: ⇔, ∼. Эта операция может быть выражена связками «тогда и только тогда», «необходимо и достаточно», «равносильно». Примером эквивалентности является высказывание: «Треугольник будет прямоугольным тогда и только тогда, когда один из углов равен 90 градусам».

Таблица истинности операции эквивалентности имеет вид

А	В	А ∼ В
истина	ложь	ложь
ложь	истина	ложь
ложь	ложь	истина
истина	истина	истина

А	В	А ∼ В
1	0	0
0	1	0
0	0	1
1	1	1

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

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

Сложение по модулю два	А ⊕ В	$(A↖ ∧B) ∧ (A ∧ B↖)$
Импликация	А → В	$A↖ ∨ B$
Эквивалентность	А ∼ В	$(A↖ ∧ B↖) ∨ (A ∧ B)$

Приоритет выполнения логических операций следующий: отрицание («не») имеет самый высокий приоритет, затем выполняется конъюнкция («и»), после конъюнкции — дизъюнкция («или»).

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

Рассмотрим, например, построение составного высказывания из высказываний А и В, которое было бы ложно тогда и только тогда, когда оба высказывания истинны. В таблице истинности для операции сложения по модулю два находим: 1 ⊕ 1 = 0. А высказывание может быть, например, таким: «Этот мяч полностью красный или полностью синий». Следовательно, если утверждение А «Этот мяч полностью красный» — истина, и утверждение В «Этот мяч полностью синий» — истина, то составное утверждение — ложь, т. к. одновременно и красным, и синим мяч быть не может.

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

Пример 1. Определить для указанных значений X значение логического высказывания ((X > 3) ∨ (X < 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

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

A	B	A → B
1	0	0
0	1	1
0	0	1
1	1	1

Пример 2. Указать множество целых значений X, для которых истинно выражение ¬((X > 2) → (X > 5)) .

Решение. Операция отрицания применена ко всему выражению ((X > 2) → (X > 5)) , следовательно, когда выражение ¬((X > 2) → (X > 5)) истинно, выражение ((X > 2) →(X > 5)) ложно. Поэтому необходимо определить, для каких значений X выражение ((X > 2) → (X > 5)) ложно. Операция импликации принимает значение «ложь» только в одном случае: когда из истины следует ложь. А это выполняется только для X = 3; X = 4; X = 5.

Пример 3. Для каких из приведенных слов ложно высказывание ¬(первая буква гласная ∧ третья буква гласная) ⇔ строка из 4 символов? 1) асса; 2) куку; 3) кукуруза; 4) ошибка; 5) силач.

Решение. Рассмотрим последовательно все предложенные слова:

1) для слова асса получим: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

2) для слова куку получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

3) для слова кукуруза получим: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 — высказывание ложно;

4) для слова ошибка получим: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 — высказывание истинно;

5) для слова силач получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 — высказывание ложно.

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

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

выражения, которые используют операции сравнения («больше», «меньше», «равно», «не равно» и т. п.) и принимают логические значения (например, выражение а > b , где а = 5 и b = 7, равно значению «ложь»);
непосредственные логические выражения, связанные с логическими величинами и логическими операциями (например, A ∨ В ∧ С, где А = истина, B = ложь и C = истина).

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

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

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

Пример. Найти значение выражения:

$1 ≤ a ∨ A ∨ sin(π/a — π/b) < 1 ∧ ¬B ∧ ¬(b^a + a^b >a + b ∨ A ∧ B)$ для а = 2, b = 3, A = истина, В = ложь.

Решение. Порядок подсчета значений:

1) b a + a b > a + b, после подстановки получим: 3 2 + 2 3 > 2 + 3, т. е. 17 > 2 + 3 = истина;

2) A ∧ B = истина ∧ ложь = ложь.

Следовательно, выражение в скобках равно (b a + a b > a + b ∨ A ∧ B) = истина ∨ ложь = истина;

3) 1≤ a = 1 ≤ 2 = истина;

После этих вычислений окончательно получим: истина ∨ А ∧ истина ∧ ¬В ∧ ¬истина.

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

5) ¬В = ¬ложь = истина; ¬истина = ложь;

6) A ∧ истина ∧ истина ∧ ложь = истина ∧ истина ∧ истина ∧ ложь = ложь;

7) истина ∨ ложь = истина.

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

Примечание. Учитывая, что исходное выражение есть, в конечном итоге, сумма двух слагаемых, и значение одного из них 1 ≤ a = 1 ≤ 2 = истина, без дальнейших вычислений можно сказать, что результат для всего выражения тоже «истина».

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

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

Закон	Для ∨	Для ∧
Переместительный	A ∨ B = B ∨ A	A ∧ B = B ∧ A
Сочетательный	A ∨ (B ∨ C) = (B ∨ A) ∨ C	A ∧ (B ∧ C) = (A ∧ B) ∧ C
Распределительный	A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)	A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C)
Правила де Моргана	$↖$ = $A↖ ∧ B↖$	$↖$ = $A↖ ∨ B↖$
Идемпотенции	A ∨ A = A	A ∧ A = A
Поглощения	A ∨ A ∧ B = A	A ∧ (A ∨ B) = A
Склеивания	(A ∧ B) ∨ (A↖ ∧ B) = B	(A ∨ B) ∧ (A↖ ∨ B) = B
Операция переменной с ее инверсией	$A ∨ A↖$ = 1	$A ∧ A↖$ = 0
Операция с константами	A ∨ 0 = A A ∨ 1 = 1	A ∧ 1 = A A ∧ 0 = 0
Двойного отрицания	$A↖$ = A

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

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

Рассмотрим на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

Для преобразования здесь можно применить закон идемпотенции, распределительный закон; операцию переменной с инверсией и операцию с константой.

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .

Здесь для упрощения применяется закон поглощения.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

При преобразовании применяются правило де Моргана, операция переменной с ее инверсией, операция с константой

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

Пример 1. Найти логическое выражение, равносильное выражению A ∧ ¬(¬B ∨ C) .

Решение. Применяем правило де Моргана для В и С: ¬(¬B ∨ C) = B ∧ ¬C .

Получаем выражение, равносильное исходному: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Ответ: A ∧ B ∧ ¬C.

Пример 2. Указать значение логических переменных А, В, С, для которых значение логического выражения (A ∨ B) → (B ∨ ¬C ∨ B) ложно.

Решение. Операция импликации ложна только в случае, когд а из истинной посылки следует ложь. Следовательно, для заданного выражения посылка A ∨ B должна принимать значение «истина», а следствие, т. е. выражение B ∨ ¬C ∨ B , — «ложь».

1) A ∨ B — результат дизъюнкции — «истина», если хотя бы один из операндов — «истина»;

2) B ∨ ¬C ∨ B — выражение ложно, если все слагаемые имеют значение «ложь», т. е. В — «ложь»; ¬C — «ложь», а следовательно, переменная С имеет значение «истина»;

3) если рассмотреть посылку и учесть, что В — «ложь», то получим, что значение А — «истина».

Ответ: А — истина, В — ложь, С — истина.

Пример 3. Каково наибольшее целое число X, при котором истинно высказывание (35

ООО «Экзамер», 2015—2023
Написать нам
Юридические документы

Логические операции

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

тест для 10 класса по теме Логические операции учебник Информатика. 10 класс. Углубленный уровень. В 2 ч. Поляков К.Ю., Еремин Е.А. М.: 2013 — Ч.1 — 344с., Ч.2 — 304с.

Система оценки: 5 балльная

Список вопросов теста

Вопрос 1

Какой ученый разработал основы алгебры логики?

Варианты ответов

Л. Пастер
Дж. Буль
Б. Паскаль
К. Шеннон
И. Ньютон

Вопрос 2

Какая операция называется «конъюнкцией»?

Варианты ответов

НЕ
И
или
исключающее ИЛИ
импликация

Вопрос 3

Какая операция называется «дизъюнкцией»?

Варианты ответов

не
и
или
исключающее ИЛИ
импликация

Вопрос 4

Как называется операция, соответствующая связке «тогда и только тогда»?

Варианты ответов

отрицание
конъюнкция
эквивалентность
дизъюнкция
импликация

Вопрос 5

Как называется операция, соответствующая связке «если . то»?

Варианты ответов

отрицание
конъюнкция
эквивалентность
импликация
дизъюнкция

Вопрос 6

Какие из этих логических выражений равны нулю независимо от значения переменной A? Здесь xor обозначает «исключающее ИЛИ»

Варианты ответов

A + A
A * 0
A xor A
A xor 0
A + 1

Вопрос 7

Какие из этих логических выражений истинны независимо от значения переменной A? Здесь xor обозначает «исключающее ИЛИ»

Варианты ответов

A + 1
A * 1
A xor 1
A xor A
1 xor (0 * A)

Вопрос 8

Найдите значение логического выражения

Вопрос 9

Какая операция равносильна выражению

Варианты ответов

исключающее ИЛИ
импликация
эквиваленция
конъюнкция
логическое сложение

Основы программирования на языке Python. Логическая операция

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

4. Инверсия (логическое отрицание)

Инверсия логической переменной истина,
если переменная ложна, и, наоборот,
инверсия ложна, если переменная истинна.
Обозначение: A

5. Конъюнкция (логическое умножение)

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

6. Дизъюнкция (логическое сложение)

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

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

Импликация двух логических переменных
ложна тогда и только тогда, когда из истинного
основания следует ложное следствие.
Обозначение: A B
А — условие
В — следствие

8. Эквивалентность (логическое равенство)

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

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

При вычислении значения логического выражения
(формулы) логические операции вычисляются в
определенном порядке, согласно их приоритету:
1.инверсия,
2.конъюнкция,
3.дизъюнкция,
4.импликация и эквивалентность.
Операции одного приоритета выполняются слева
направо.
Для
изменения
порядка
действий
используются скобки.

10. Пример

Дана формула
A B C D A
Определите порядок вычисления.
Порядок вычисления:
Инверсия – A
Конъюнкция – C D
Дизъюнкция – A B
Импликация – A B C D
Эквивалентность –
A B C D A

11.

Таблица истинности — таблица, показывающая,
какие
значения принимает составное высказывание при всех
сочетаниях (наборах) значений входящих в него простых
высказываний.
Логическое выражение — составные высказывания в виде
формулы.
Равносильные логические выражения – логические
выражения, у которых последние столбцы таблиц
истинности совпадают. Для обозначения равносильности
используется знак «=».
11

12.

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

13.

Заполнение таблицы:
1.
разделить колонку значений первой переменной
пополам и заполнить верхнюю часть «0», а нижнюю «1»;
2.
разделить колонку значений второй переменной на
четыре части и заполнить каждую четверть чередующимися
группами «0» и «1», начиная с группы «0»;
3.
продолжать деление колонок значений последующих
переменных на 8, 16 и т.д. частей и заполнение их группами
«0» или «1» до тех пор, пока группы «0» и «1» не будут
состоять из одного символа.
13

14.

Пример 1. Для формулы A/\ (B \/ ¬B /\¬C) постройте таблицу
истинности.
Количество логических переменных 3,
следовательно, количество строк — 23 = 8.
Количество логических операций в формуле 5, количество
логических переменных 3, следовательно количество
столбцов — 3 + 5 = 8.
14

15.

Пример 2. Определите истинность логического
выражения F(А, В) = (А\/ В)/\(¬А\/¬В)
Пример 3. Постройте таблицу истинности для логического
выражения F = (A\/ B) /\ ¬С
Пример 4. Определите истинность формулы:
F = ((С \/В) => В) /\ (А /\ В) => В.
15

16.

Пример 5. Символом F обозначено одно из указанных
ниже логических выражений от трех аргументов: X, Y, Z.
Дан фрагмент таблицы истинности выражения F:
X Y Z F
0
0
0
1
0
0
1
0
0
1
0
1
Какое выражение соответствует F?
1) ¬X/\¬Y/\Z
2) ¬X\/¬Y\/Z
3) X\/Y\/¬Z
4) X\/Y\/Z
16

Какая операция равносильна выражению a b

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

Логические выражения

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

Логические операции

Список вопросов теста

Вопрос 1

Варианты ответов

Вопрос 2

Варианты ответов

Вопрос 3

Варианты ответов

Вопрос 4

Варианты ответов

Вопрос 5

Варианты ответов

Вопрос 6

Варианты ответов

Вопрос 7

Варианты ответов

Вопрос 8

Вопрос 9

Варианты ответов

Основы программирования на языке Python. Логическая операция

4. Инверсия (логическое отрицание)

5. Конъюнкция (логическое умножение)

6. Дизъюнкция (логическое сложение)

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

8. Эквивалентность (логическое равенство)

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

10. Пример

11.

12.

13.

14.

15.

16.

Добавить комментарий Отменить ответ