misle.ru страница 1
скачать файл
      1. Основные понятия алгебры логики


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

Основным предметом алгебры логики являются высказывания.

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

Пример_1:


  • «5 есть простое число». Это высказыванием является истинным.

  • «4+х=6». Это уравнение не является высказыванием. Однако, придавая переменной х определенное числовое значение, получим высказывание.

  • «роза – цветок». Это высказывание является истинным.

  • «все углы – прямые». Это высказывание является ложным.

  • «3+5=9». Это высказывание является ложным.

Истинностные значения новых высказываний определяются при этом только истинностными значениями входящих в них высказываний. Построение из данных высказываний (или из данного высказывания) нового высказывания называется логической операцией. Знаки логических операций называются логическими связками.

Пример_2:

  • Из высказываний «х>2», «х<3» при помощи связки и можно получить высказывание «x>2 и х<3»;

  • из высказываний «у>10», «х<3» при помощи связки или можно получить высказывание «у>10 или х<3»;

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

Одной из основных операций алгебры логики является операция отрицания (инверсия). Отрицание высказывания А (т.е. не А) обозначается и читается: «отрицание А», «не А» или «А с чертой».

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

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

Таблица 1

Обозначение логической операции

Другие обозначения

логической операции



Название логической операции и связки

Логические
связки

АВ

А&В

АВ


АВ

конъюнкция,
логическое умножение,

логическое «и»



А и В

АВ

А+В

дизъюнкция,
логическое сложение,

логическое «или»



А или В

АВ

АВ

АВ


импликация,
логическое следование

если А, то В;

АВ

АВ

сумма по модулю 2,
разделительная дизъюнкция,
разделительное «или»

либо А, либо В

А~В

АВ

АВ


АВ

эквиваленция,
тождественность

равнозначность



А тогда и только тогда, когда В;

АВ



штрих Шеффера,
антиконъюнкция

неверно, что А и В;

АВ



стрелка Пирса,
антидизъюнкция,

ни А, ни В;

Примечание: А и В являются высказываниями.

Инверсия

Пример_3: Дано высказывание А=<Киев-столица Франции>.

Тогда не Ане Киев-столица Франции». Высказывание не А означает – не верно, что А, т.е. не верно, что <Киев-столица Франции>.



прямоугольник 6Конъюнкция

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



Пример_4: Даны высказывания А=«Москва – столица России» и В=«Рим – столица Италии».

Сложное высказывание АВ=«Москва – столица России и Рим – столица Италии» истинно, так как истинны оба высказывания.

Дизъюнкция

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



Пример_5: Даны высказывания А=«2+3=5» и В=«3+3=5».

Сложное высказывание АВ=«2+3=5 или 3+3=5» истинно, так как истинно высказывание А.



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

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



Пример_6: Даны высказывания А=«2+2=7» и В=«1–8=5».

Сложное высказывание А~В=«2+2=7 тогда и только тогда, когда 1–8=5» истинно, так как оба высказывания ложны.



Импликация

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



Пример_7: Даны высказывания А=«2+2=4» и В=«1–8=5».

Сложное высказывание АВесли 2+2=4, то 1–8=5» ложно, так как высказывание А истинно, а В – ложно.



Антиконъюнкция

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



Пример_8: Даны высказывания А=«Москва – столица России» и В=«Рим – столица Италии».

Сложное высказывание АВневерно, что Москва–столица России и Рим–столица Италии» ложно, так как истинны оба высказывания.



Антидизъюнкция

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



Пример_9: Даны высказывания А=«Рим – столица России» и В=«Москва – столица Италии».

Сложное высказывание АВни Рим–столица России, ни Москва–столица Италии» истинно, так как ложны оба высказывания.

Связки и частица «не» рассматриваются в алгебре логики как операции над величинами, принимающими значения 0 (ложь/false) и 1(истина/true), и результатом применения этих операций также являются значения 0 или 1.

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

В таблице 2 представлена таблица истинности для операции отрицания (инверсия).

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

Таблица 2


А

не А

0

1

1

0

Пример_10: Дана переменная А=1 (истина). После применения операции инверсии для переменной А ее значение станет равным 0 (ложь).

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



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

Таблица 3



А

В









~





0

0

0

0

1

0

1

1

1

0

1

0

1

1

1

0

1

0

1

0

0

1

0

1

0

1

0

1

1

1

1

1

0

1

0

0

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

  1. Инверсия (отрицание)

  2. Конъюнкция

  3. Дизъюнкция, разделительная дизъюнкция

  4. Импликация

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

Пример_11: Даны высказывания А=«Москва–столица России» и В=«Рим–столица Италии». Следовательно А=1 (истина) и В=1.

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



  • в таблице 1.4. в столбцах с именами А и В найти строку для А=1 и В=1;

  • затем найти пересечение этой строки со столбцом с именем ;

  • получим АВ=1.

А

В









~





0

0

0

0

1

0

1

1

1

0

1

0

1

1

1

0

1

0

1

0

0

1

0

1

0

1

0

1

1

1

1

1

0

1

0

0

Пример_12: Даны высказывания А=«2+3=5» и В=«3+3=5». Тогда А=1 и В=0.

Высказывание АВ=1.




А

В









~





0

0

0

0

1

0

1

1

1

0

1

0

1

1

1

0

1

0

1

0

0

1

0

1

0

1

0

1

1

1

1

1

0

1

0

0

Пример_13: Даны высказывания А=«2+2=4» и В=«1–8=5». Тогда А=1 и В=0.

Высказывание А~В=0.



А

В









~





0

0

0

0

1

0

1

1

1

0

1

0

1

1

1

0

1

0

1

0

0

1

0

1

0

1

0

1

1

1

1

1

0

1

0

0


Реализация импликации через инверсию и дизъюнкцию

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






Реализация эквиваленции через инверсию, дизъюнкцию и конъюнкцию

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






Пример_14: Дана логическая формула . Построить таблицу истинности для данной формулы.

Решение:

  1. Расставляем приоритеты выполнения операций:

1) – операция отрицания высказывания В. Результат выполнения операции присваиваем переменной .

2) – операция логического умножения (конъюнкция) высказываний и . Результат выполнения операции присваиваем переменной .

3) – операция логического следования (импликация) высказываний и . Результат выполнения операций присваиваем переменной .

2. Строим таблицу, состоящую из пяти столбцов:



Исходные данные

1

2

3

A

B





























































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

3. Исходные данные таблицы заполняем возможными комбинациями значений высказываний А и В (первый вариант – когда оба высказывания истинны; второй и третий варианты – когда одно из высказываний истинно, а другое ложно; четвертый вариант – когда оба высказывания ложны).



Исходные данные

1

2

3

A

B

1

1










0

1










1

0










0

0










Примечание: истина обозначается – 1, а ложь – 0.

4. Заполняем значениями столбец с именем 1. Для этого по таблице истинности для логической операции инверсия (см. таблицу 2) определяем значение операции инверсия Х=0 (при начальном значении В=1).



Исходные данные

1

2

3

A

B

1

1

0







0

1

0







1

0

1







0

0

1







5. Заполняем значениями столбец с именем 2. Для этого по таблице истинности основных логических операций (см. таблицу 3) определяем значение операции конъюнкции Y=0 (при А=1 и Х=0) и т.д.

Исходные данные

1

2

3

A

B

1

1

0

0




0

1

0

0




1

0

1

1




0

0

1

0




6. Заполняем значениями столбец с именем 3. Для этого по таблице истинности основных логических операций определяем значение операции логическое следование F=1 (при Y =0 и А=1) и т.д.

Исходные данные

1

2

3

A

B

1

1

0

0

1

0

1

0

0

1

1

0

1

1

1

0

0

1

0

1


Пример_15: Дана логическая формула . Построить таблицу истинности для данной формулы.

Решение:

  1. Расставляем приоритеты выполнения операций:

1) – операция отрицания высказывания В. Результат выполнения операции присваиваем переменной .

2) – операция логического умножения (конъюнкция) высказываний и . Результат выполнения операции присваиваем переменной .

3) – операция логического следования (импликация) высказываний и . Результат выполнения операций присваиваем переменной .

2. Строим таблицу, состоящую из пяти столбцов:



Исходные данные

1

2

3

4

X

Y

Z









































































































































































В Исходные данные таблицы записываем имена высказываний X, Y и Z. В остальные четыре столбца записываем имена переменных, которым присваиваем результаты логических операций.

3. Исходные данные таблицы заполняем возможными комбинациями значений высказываний X, Y и Z (первый вариант – когда все высказывания истинны; второй вариант – когда два высказывания истинны, а третье ложно; третий вариант – когда одно из высказываний истинно, а другие ложны; четвертый вариант – когда все три высказывания ложны).



Исходные данные

1

2

3

4

X

Y

Z

1

1

1













1

1

0













1

0

1













0

1

1













1

0

0













0

1

0













0

0

1













0

0

0













Примечание: истина обозначается – 1, а ложь – 0.

4. Заполняем значениями столбец с именем 1. Для этого по таблице истинности для логической операции антиконъюнкция (см. таблицу 2) определяем значения.



Исходные данные

1

2

3

4

X

Y

Z

1

1

1













1

1

0













1

0

1













0

1

1













1

0

0













0

1

0













0

0

1













0

0

0













5. Заполняем значениями столбец с именем 2. Для этого по таблице истинности основных логических операций (см. таблицу 3) определяем значение операции конъюнкции Y=0 (при А=1 и Х=0) и т.д.

Исходные данные

1

2

3

4

X

Y

Z

1

1

1













1

1

0













1

0

1













0

1

1













1

0

0













0

1

0













0

0

1













0

0

0













6. Заполняем значениями столбец с именем 3. Для этого по таблице истинности основных логических операций определяем значение операции логическое следование F=1 (при Y =0 и А=1) и т.д.

Исходные данные

1

2

3

4

X

Y

Z

1

1

1













1

1

0













1

0

1













0

1

1













1

0

0













0

1

0













0

0

1













0

0

0














      1. Логические основы ЭВМ


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

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

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

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

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

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



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

Рис. 2.1.2. Схема «И»

На выходе схемы «И» значение «1» будет тогда и только тогда, когда на всех входах будут «1». Когда хотя бы на одном входе будет «0», на выходе также будет «0».

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



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

Рис. 2.1.3. Схема «ИЛИ»

На выходе схемы «ИЛИ» значение «0» будет тогда и только тогда, когда на всех входах будут «0». Когда хотя бы на одном входе будет «1», на выходе также будет «1».

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



Схема «НЕ» (инвертор) реализует операцию отрицания. Условное обозначение схемы НЕ представлено на рис. 2.1.4.

Рис. 2.1.4. Схема «НЕ»

Если на входе схемы – «0», то на выходе будет «1». Когда на входе – «1», на выходе будет «0».

Схема «И-НЕ» состоит из элемента «И» и инвертора и осуществляет отрицание результата схемы «И». Условное обозначение схемы «И-НЕ» представлено на рисунке 2.1.5.

Рис. 2.1.5. Схема «И-НЕ»

На выходе схемы «И-НЕ» значение «0» будет тогда и только тогда, когда на всех входах будут «1».
Схема «ИЛИ-НЕ» состоит из элемента «ИЛИ» и инвертора и осуществляет отрицание результата схемы «ИЛИ». Условное обозначение схемы «ИЛИ-НЕ» представлено на рис. 2.1.6.

Рис. 2.1.6. Схема «ИЛИ-НЕ»



На выходе схемы «ИЛИ-НЕ» значение «1» будет тогда и только тогда, когда на всех входах будут «0».

      1. Вопросы для самоконтроля


  1. Что изучает дисциплина информатика?

  2. Дайте определение понятию «информация».

  3. Формы представления информации.

  4. Перечислите свойства информации.

  5. Какова минимальная единица измерения информации?

  6. Какова основная единица измерения информации?

  7. Как задаются производные единицы измерения информации?

  8. Дайте определение понятию «количество информации».

  9. Как связаны между собой понятия «энтропия» и «информация»?

  10. Что измеряет синтаксическая мера информации?

  11. Что измеряет семантическая мера информации?

  12. Что измеряет прагматическая мера информации?

  13. Дайте определение понятию «система счисления».

  14. Чем отличается позиционная система счисления от непозиционной?

  15. Приведите примеры позиционной и непозиционной систем счисления.

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

  17. Как представляются данные в компьютере?

  18. Для чего используется кодовая таблица?

  19. Как кодируются символы в памяти компьютера?

  20. Что собой представляет таблица ASCII кодов?

  21. Как определить числовой код символа?

  22. Представление целых положительных и отрицательных чисел в прямом, обратном и дополнительном кодах.

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

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

  25. Что изучает алгебра логики?

  26. Что понимается под высказыванием?

  27. Перечислите основные логические операции?

  28. Для каждой логической операции назовите соответствующие логические связки.

  29. Для чего используется таблица истинности?

  30. Для высказываний А=«На улице светит солнце» и В=«Идет дождь» примените операцию конъюнкции. Какое новое высказывание получилось?

  31. Для высказываний А=«У меня в зачетке стоят одни пятерки» и В=«Я добросовестно выполняю задания» примените операцию эквиваленции. Какое новое высказывание получилось?

  32. Как изображается логическая схема «И-НЕ»?

  33. Как изображается логическая схема «ИЛИ»?

  34. Как изображается логическая схема «НЕ»?

  35. Через какие логические операции можно реализовать импликацию?

  36. Через какие логические операции можно реализовать эквиваленцию?
скачать файл


Смотрите также: