Вычитание операция обратная сложению логика ошибка

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

Сложение двух
чисел в двоичной системе счисления
выполняется на основе таблицы двоичного
сложения:

0 + 0 = 0,

0 + 1 = 1,

1 + 0 = 1,

1 + 1 = 10.

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

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

1 1 0 1 1 0 1 — первое
слагаемое

+

1
0 0 1 1 1 1
— второе слагаемое

0 1 0 0 0 1 0 — поразрядная
сумма без учета переносов

+

1
1 1 1
— переносы

10 1 1 1
1 0 0 — окончательная сумма

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

1 0 1 1 0 1 0 0 1 —
первое слагаемое

+

1
1 0 0 1 1 1 1 1 —
второе слагаемое

0 1 1 1 1 0 1 1 0 —
поразрядная сумма

+

1
1 1 —
переносы

1 1 0 0 0 0 1 0 0 0 —
окончательная сумма

Использование
этого правила позволяет ускорить
формирование окончательной суммы.

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

0 — 0 = 0,

1 — 0 = 1,

1 — 1 = 0,

10—1 = 1.

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

1 1 1 0 0 0 1 1 —
уменьшаемое

__1 1
0 1 1 (11) 1 1 — уменьшаемое с учетом заема

1
0 0 1 0 1 1 0 — вычитаемое

0 1 0 0 1 1 0 1 —
разность

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

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

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

1
01001 — первое слагаемое в обратном коде

+

0
01101
— второе слагаемое в прямом коде

1
10110 — сумма в обратном коде

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

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

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

0
10110 — первое слагаемое в прямом коде

+

1
10011
— второе слагаемое в дополнительном
коде

0
01001 — сумма в прямом коде

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

1
01010 — первое слагаемое в дополнительном
коде

+

0
01101
— второе слагаемое в прямом коде

1
10111 — сумма в дополнительном коде

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

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

00
11011 — первое слагаемое в прямом
модифицированном коде

+

11
01011
— второе слагаемое в дополнительном
модифицированном коде

00
00110 — сумма в прямом модифицированном
коде

Переполнения
разрядной сетки не возникает. Перенос
из старшего знакового разряда
отбрасывается. При сложении чисел 00
10110 и 00
11011

00
10110

+

00
11011

01
10001

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

11
010011

+

11
100011

10
110110

В
этом случае комбинация 10
в знаковых разрядах указывает на
переполнение разрядной сетки.

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

0 + 0 = 0,

0 + 1 = 1,

1 + 0 = 1,

1 + 1 = 0 без формирования
переноса

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

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

0 x 0 = 0,

0 x 1 = 0,

1 х 0 = 0,

1 х 1 = 1.

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

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

10111 —
множимое

______1101
— множитель

10111 — первое
частичное произведение

00000 — второе
частичное произведение

10111
— третье частичное произведение

10111_____—
четвертое частичное произведение

100101011
— произведение

Тот же результат
можно получить при умножении, начиная
со старших разрядов множителя:

10111

^х
1101

10111

10111

00000

10111

100101011

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

Пример умножения
чисел этим методом:

10111 — четвертое
частичное произведение

101110 — сдвиг
на разряд влево

_10111
— третье частичное произведение

1000101 —прибавление
третьего частичного произведения

10001010 — сдвиг на
разряд влево

00000
— второе частичное произведение

10001010
— прибавление второго частичного
произведения

100010100 — сдвиг на
разряд влево

10111
— первое частичное произведение

100101011 — прибавление
первого частичного произведения

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

При умножении
дробных чисел меньше единицы умножение
удобнее начинать с младшего разряда
множителя. Так, при перемножении дробных
чисел 0,10111 и 0,1101 получим

0,10111: —
первое частичное произведение

0,01011: 1 — сдвиг
на разряд вправо

+

00000:

— второе частичное произведение

0,01011: —
прибавление второго частичного
произведения

0,00101: 11 — сдвиг
на разряд вправо

+

10111:
— третье частичное произведение

0,11100: 11 —
прибавление третьего частичного
произведения:

0,01110: 011 — сдвиг
на разряд вправо

+

10111:
— четвертое частичное произведение

1,00101: 011 —
прибавление четвертого частичного
произведения

0,10010: 1011— сдвиг
на разряд вправо

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

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

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

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

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

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

Рассмотрим примеры,
в которых делимое больше и меньше
делителя:

В цифровых
устройствах при выполнении операции
деления так же, как и при выполнении
операции алгебраического сложения,
используется дополнительный и
модифицированный коды. Например, при
делении числа 0,11011 на 0,11101 представляем
делитель в дополнительном коде 00011:

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

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

Например,
при делении числа N₁=
10011 на число N₂=0,11001
по способу без восстановления остатка
при переходе к модифицированным
дополнительным кодам получим N₁
= 00
10011, N₂=00
11001,

—N₂=11
100111:

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

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

Код ОГЭ: 1.3.3. Логические значения, операции, выражения

Алгебра логики, логические высказывания

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

Форма мышления — это способ выражения мыслей или форма, по которой они строятся.

Форма, обозначающая какой–либо объект или отличающий его признак, называется понятием. Примеры понятий: «компьютер», «планета», «длина», «профессия».

Форма, утверждающая или отрицающая что–либо о свойствах понятий и отношений между ними, называется утверждением (высказыванием, суждением). Примеры логических утверждений: «Декодирование — процесс восстановления информации из закодированного представления»; «В двоичной системе используются две цифры: 0 и 1»; «Париж — столица Франции». Утверждения могут быть истинными или ложными. Так, высказывание «Шанхай — столица Франции» является ложным утверждением.

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

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

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

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

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

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

В алгебре логики различают простые высказывания и сложные (составные), составленные из нескольких простых. Если в высказывании нельзя выделить некую часть, которая не совпадает по смыслу с исходным высказыванием и сама является высказыванием, то оно называется простым высказыванием. Простые высказывания обычно обозначаются латинскими буквами A, B, C и т. д.

Сложные высказывания представляют собой объединение простых высказываний с помощью логических связок. В качестве логических связок используются слова «не», «и», «или», «тогда и только тогда», «если … то». Истинность или ложность получаемых таким образом сложных высказываний определяется значением простых высказываний. Например, из простых высказываний «Офис фирмы находится в Мадриде» и «Офис фирмы находится в Берлине» можно составить сложные: «Офис фирмы находится в Мадриде или Берлине», «Офис фирмы находится в Мадриде и Берлине», «Если офис фирмы находится в Мадриде, то он находится в Берлине». Истинность первого из них означает, что офис фирмы находится в одном из названных городов или же имеются офисы в обоих городах. Ложность его означает, что ни в одном из этих городов офиса нет. Второе составное утверждение истинно тогда, когда в обоих городах имеется офис фирмы. Если же офис существует только в Берлине или только в Мадриде, — второе составное высказывание ложно.

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

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

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

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

Логическое отрицание (инверсия) — логическая операция, в результате которой из данного высказывания получается новое высказывание — отрицание исходного. Обозначается символически чертой сверху (Ā) или условными обозначениями ¬А, not А, не А (читается «отрицание А», «не А», «А ложно», «неверно, что А»).

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

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

Если обозначить через А высказывание «Арбуз является ягодой», то ¬А соответствует высказыванию «Арбуз не является ягодой» («Неверно, что арбуз — ягода»).

Отрицание является унарной операцией. Унарная (одноместная) операция — это операция, которая применяется к одному операнду.

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

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

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

Таблица истинности операции конъюнкции

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

Логическое сложение (дизъюнкция) — операция, соединяющая два или более высказываний при помощи связки « или». Эта связка символически обозначается с помощью знака v и читается «А или В». Для обозначения дизъюнкции также применяются знаки: А + В, А или В, А or В, А | B.

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

Таблица истинности операции дизъюнкции

Например, высказывания «Виктор старше Ольги» и «Виктор — однофамилец Ольги» истинны. Тогда истинными будут и составные логические высказывания «Виктор старше Ольги или Виктор — однофамилец Ольги», «Виктор младше Ольги или Виктор — однофамилец Ольги», «Виктор старше Ольги или Виктор — не однофамилец Ольги». Высказывание «Виктор младше Ольги или Виктор — не однофамилец Ольги» — ложно, поскольку ложны оба составляющие его простые высказывания.

Исключающее сложение (исключающая дизъюнкция, строгая дизъюнкция, сложение по модулю два, дизъюнкция строго–разделительная) — логическая операция, соединяющая два высказывания при помощи связки «или», употребленной в исключающем смысле (называется также исключающее «или»). Операция символически обозначается с помощью знака ⊕ и читается «либо А, либо В».

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

Таблица истинности операции строгой дизъюнкции

Например, результат исключающей дизъюнкции двух высказываний «Виктор не старше Ольги» и «Виктор младше Ольги» всегда будет истиной, кто бы из них не был старше.

Логическое следование (импликация) — логическая операция, соединяющая два высказывания при помощи связки «если… то» в сложное высказывание. Операция символически обозначается с помощью знака → и читается «Если А, то В», «А влечет В», «из А следует В», «А имплицирует В». Для обозначения импликации применяются также знаки ⊃ или ⇒. Первое логическое высказывание является условием (посылкой), а второе — следствием (заключением).

Для операции импликации справедливо утверждение, что из лжи может следовать все что угодно, а из истины — только истина. Таким образом, импликация А → В ложна только тогда, когда А истинно, а В ложно (из истинного высказывания следует ложное). Во всех остальных случаях импликация истинна.

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

Для высказываний «Луна — спутник Земли» и «Сумма углов треугольника не равна 180°» (первое истинно, второе ложно) составное высказывание «Если Луна — спутник Земли, то сумма углов треугольника не равна 180°» будет ложным. Однако истинными будут высказывания «Если Луна — спутник Земли, то сумма углов треугольника равна 180°», «Если Луна — не спутник Земли, то сумма углов треугольника не равна 180°» и «Если Луна — не спутник Земли, то сумма углов треугольника равна 180°». Этот пример наглядно демонстрирует, что в алгебре логики смысл высказываний не учитывается, а рассматриваются только их истинность или ложность.

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

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

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

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

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

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

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

Правила построения логических выражений:

• любая логическая переменная или константа (истина и ложь) являются логическим выражением;
• если А — , то ¬А — тоже логическое выражение;
• если А и В — логические выражения, то А ∧ В; А v В ; А ⊕ В; А → В; А ~ В — тоже логические выражения.

Например, A ⊕ истина v В v ложь — логическое выражение; А v ⊕ В v ложь не является логическим выражением.

Логическое выражение, принимающее значение истина при любых значениях входящих в него переменных, называется тождественно–истинным выражением (тавтологией). Например, А v В v ¬А; (А ∧ ¬А) → В.

Логическое выражение, принимающее значение ложь при любых значениях входящих в него переменных, называется тождественно–ложным выражением (противоречием). Например, А ∧ ¬А; В ~ ¬В.

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

ПРИОРИТЕТ ЛОГИЧЕСКИХ ОПЕРАЦИЙ

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

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

Пример 1
Определить порядок выполнения логических операций в выражении.
Вычислить его значение, если А = 1, В = 0, С = 1.
¬А ∧ С v (A ⊕ В) ∧ В

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

Тогда значение выражения ¬1 ∧ 1 v (1 ⊕ 0) ∧ 0 после вычисления отрицания и выражения в скобках: 0 ∧ 1 v 1 ∧ 0, после операций умножения: 0 v 0. Итог: 0.
Ответ: логическое выражение ложно.

Пример 2
Для каких из приведенных слов истинно следующее высказывание?
(Вторая буква гласная) ИЛИ (Первая буква гласная) И НЕ (Длина имени не больше 5 букв)

1) Олег   2) Марианна  3) Светлана   4) Ольга.

Решение.

1.  В соответствии с приоритетом выполнения операций сначала нужно вычислить результат операции отрицания: «Длина имени больше 5 букв». Такие имена — Марианна, Светлана.
2. Затем необходимо рассчитать результат конъюнкции (связка И) второго и третьего высказываний. Конъюнкция истинна только тогда, когда истинны оба высказывания. Следовательно, нужно выбрать имена, в которых и первая буква гласная, и длина имени больше 5 букв — таких имен среди вариантов нет.
3. Результат дизъюнкции (связка ИЛИ) истинен только тогда, когда истинно или одно, или второе, или одновременно оба простые высказывания. Первое простое высказывание истинно для имени Марианна, второе ложно для указанных имен. Таким образом, верный вариант ответа — 2.

Ответ: 2) Марианна.

СВЯЗЬ МЕЖДУ ЛОГИЧЕСКИМИ ОПЕРАЦИЯМИ

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

Связь между логическими операциями

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

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

РАВНОСИЛЬНЫЕ ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ

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

Чтобы убедиться, что два выражения равносильны, можно построить для них таблицы истинности. Если в таблицах совпадут все значения, значит, выражения равносильны.

Пример 3
Проверить равносильность выражений А ~ E и (Ā ∧ Ē) v (A ∧ E).

Решение. Для проверки следует создать таблицу истинности, содержащую столько строк, сколько возможно наборов значений переменных, входящих в выражение. Для двух переменных (А и E) количество наборов равно четырем. К двум столбцам для значений переменных (А и E) нужно присовокупить количество столбцов, равное количеству операций в выражении. Таким образом, необходимо создать таблицу, содержащую 4 строки и 7 столбцов.

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

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

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

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

Нормальная форма выражения содержит только операции отрицания, конъюнкции и дизъюнкции и не содержит отрицания выражений и двойных отрицаний.

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

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

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

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

Пример 4
Выбрать выражение, которое равносильно выражению (A ∧ B) v (Ā ∧ B).

1) A         2) A ∧ B          3) Ā ∧ B           4) B

Решение. В соответствии с законом склеивания (A ∧ B) v (Ā ∧ B) = B, следовательно, исходное выражение равносильно выражению В.
Ответ: 4) В.

ОПРЕДЕЛЕНИЕ ЗНАЧЕНИЙ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ

Выражения, которые принимают логические значения (истина или ложь) в результате выполнения операций сравнения (больше >, меньше <, больше или равно ≥, меньше или равно ≤, равно =, не равно ≠), также являются логическими выражениями. Кроме операций сравнения и логических операций такие выражения могут включать функции и алгебраические операции. Приоритет выполнения этих операций таков:

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

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

Пример 5
Для какого из приведенных ниже значений числа М истинно следующее выражение?
¬М ≥ 10 ∧ M > 3

1) 1          2) 2         3) 3        4) 4

Решение. В соответствии с приоритетами операций сначала следует выполнить операции сравнения, затем отрицания, а потом — конъюнкцию. Отрицанием высказывания М ≥ 10 является высказывание М < 10. Получим выражение М < 10 ∧ M > 3. Для того чтобы это выражение (конъюнкция) было истинным, должны выполняться (т. е. быть истинными) оба неравенства. Следовательно, значение М должно быть больше 3, но меньше 10. Среди предложенных значений этому условию удовлетворяет только одно — число 4.
Ответ: 4) 4.

Задачи, подобные предыдущему примеру, можно решать и с помощью таблиц истинности.

Пример 6.
Для какого из приведенных ниже значений числа М истинно следующее выражение?
¬М ≥ 10 ∧ M > 3

1) 1           2) 2         3) 3        4) 4

Решение. Составим таблицу истинности: все операции выражения укажем в столбцах таблицы, все предложенные значения М укажем в ее строках. Рассчитаем значения таблицы:

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

Пример 7.
В табличной форме представлены ежемесячные данные о продаже групп товаров за полгода. Сколько групп товаров демонстрировали рост продаж в весенние месяцы или вышли на уровень свыше 80 % в июне?

Решение. Переформулируем условие задачи: необходимо найти группы товаров, для которых (Март < Апрель) ∧ (Апрель < Май) v (Июнь > 80).

Введем обозначения:
А = (Март < Апрель)
В = (Апрель < Май)
С = (Июнь > 80)

Тогда выражение можно записать как А ∧ В v С.

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

Составим таблицу истинности для исходных данных.

Логическому выражению удовлетворяют 3 записи — 4–я, 6–я и 7–я.
Ответ: 3.

Конспект урока по информатике «Логические значения, операции, выражения».

Вернуться к Списку конспектов по информатике.