Логические основы работы ЭВМ

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

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

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

Широкое распространение имеют следующие логические операции: И (логическое умножение), ИЛИ (логическое сложение), НЕ (отрицание). В вычислительной технике они обозначаются соответственно AND (или ), OR (или ), NOT (или ). С помощью этих трех операций можно представить сколь угодно сложную логическую операцию (логическую функцию). Числа, участвующие в логической операции, называются операндами. Операции И, ИЛИ — двухоперандовые. Операция НЕ — однооперандовая.

Рассмотрим пять основных операций алгебры логики.

1. Операция отрицания. Отрицанием утверждения А называется утверждение, которое ложно, если А истинно, и истинно, если А ложно. Отрицание обозначается (читается «не »). Связь между значением истинности для утверждений и можно выразить с помощью следующей таблицы истинности для отрицания:

 

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

Пример 15. Рассмотрим высказывание

А = {Город Нью-Йорк — столица США}.

Отрицанием этого высказывания будет высказывание

={Город Нью-Йорк не является столицей США}.

Было бы ошибкой считать отрицанием высказывания А высказывание

= {Город Вашингтон — столица США}.

 

Пример 16. Записать результат выполнения логической операции .

Ответ:

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

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

 

Пример 17. Даны два высказывания

А= {Завтра первый урок литература} и

В = {Завтра первый урок математика}.

Дизъюнкция этих высказываний

= {Завтра первый урок литература или математика}

 

будет истинной, если на первом уроке будет литература (2-я строка таблицы истинности) или математика (3-я строка таблицы), и ложной, если на первом уроке будет любой другой предмет или если урока вообще не будет (4-я строка таблицы).

 

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

Пример 18. Логически сложить два двоичных числа 10100010₂ и 1111₂.

 

Решение:

 

Ответ: 10100010 1111=10101111

3. Операция конъюнкции. Конъюнкцией утверждений A и B называется утверждение, которое истинно, если истинны оба утверждения A и B, и ложно – в противном случае, т.е. когда хотя бы одно из утверждений ложно. Конъюнкция обозначается символом (читается «A и B») и определяется следующей таблицей истинности:

 

 

Пример 19. Пусть даны высказывания

А = {Петя не любит математику} и

В = {Петя любит физику}.

Конъюнкция = {Петя не любит математику и любит физику} истинна только тогда, когда Петя любит физику, аматематику не любит. В остальных трех случаях, т. е. когда Петя:

а) не любит математику и не любит физику,

б) любит математику и физику,

в) любит математику, но не любит физику высказывание ложно.

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

Пример 20. Логически перемножить два двоичных числа 11110011₂ и 111111₂.

Решение:

Ответ: 11110011 111111 = 110011

 

4. Операция эквиваленции. Эквивалентность двух утверждений A и B истинна тогда и только тогда, когда A и B оба истинны или ложны и обозначается А ~ В.

 

~	A	B	A ~ B

 

Пример 21. Рассмотрим два высказывания

 

А = {На Марсе будут обнаружены бактерии} и

В = {Сочи станет олимпийской столицей}.

Эквиваленцией этих двух высказываний является высказывание

А ~ В= {На Марсе будут обнаружены бактерии в том и только в том случае, если Сочи станет олимпийской столицей}.

Это высказывание истинно, если:

а) на Марсе будут обнаружены бактерии, и Сочи действительно станет олимпийской столицей;

б) на Марсе не будут обнаружены бактерии, а Сочи не станет олимпийской столицей,

и ложно, если:

в) на Марсе будут найдены бактерии, но олимпийской столицей Сочи не станет;

г) на Марсе не найдут бактерий, а Сочи будет олимпийской столицей.

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

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

 

 

Пример 22.

Даны два ложных высказывания

A = {Число 3 является делителем числа 17} и

B = {Число 6 – простое число}.

Высказывание ={Если число 3 – делитель 17, то 6 – простое число} истинно (согласно строке 4 таблицы истинности для импликации).

 

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

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

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

Пример 22. Составить таблицу истинностидля высказывания

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

 

A	B

 

Заполнив таблицу истинности, мы получили важный результат: высказывание ~ истинно всегда, т.е. при любом наборе значений истинны и лжи для составляющих его высказываний A и B. Такие высказывания называются тождественно- истинными и обозначаются латинской буквой I. Поэтому можно записать:

~ = I.

 

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

Формулы, имеющие одинаковые таблицы истинности, назовем эквивалентными. Эквивалентные формулы алгебры высказываний – аналог тождественных выражений обычной алгебры. Так как таблицы истинности конечны, то эквивалентность формул в алгебре высказываний можно доказать с помощью их таблиц истинности, сравнив их. Этот метод практически приемлем только в случае небольшого числа простых высказываний, образующих составные. Ведь если сложное высказывание состоит из n простых, то таблица истинности такого высказывания содержит строк, что при n = 10, например, превзойдет тысячу. В то же время в приложениях алгебры логики, в частности в теории автоматического управления при анализе релейно-контактных и электронно-ламповых схем, как раз приходится иметь дело с высказываниями, составленными из сотен и даже тысяч простых высказываний. Доказательство равносильности высказываний с помощью таблиц истинности в таких случаях практически невозможно.

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

Наиболее важными «тождествами» алгебры высказываний являются следующие:

 

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