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

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

ВЫСКАЗЫВАНИЕ – это повествовательное предложение, о котором можно сказать, истинно оно или ложно.

Например:

Земля – планета Солнечной системы - истинно

2+8<5 - ложно

5*5=25 - истинно

А вот примеры, не являющиеся высказываниями:

Уходя, гасите свет;

Да здравствует мыло душистое и полотенце пушистое.

Высказывания, приведенные выше, являются простыми. Сложные высказывания получаются путем объединения простых высказываний связками – союзами И, ИЛИ, и частицей НЕ. Значение истинности сложных высказываний зависит от истинности входящих высказываний и от объединения их связок.

Например, даны четыре простых высказывания:

На улице идет дождь;

На улице светит солнце;

На улице пасмурная погода;

На улице идет снег.

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

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

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

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

Например:

У кошки четыре ноги. А=1

Москва столица Франции В=0

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

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

Х

У F(X,Y,Z)

Z

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

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

Q=2n

где n – количество входных переменных.

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

Логическая операция КОНЬЮНКЦИЯ иначе называется ЛОГИЧЕСКОЕ УМНОЖЕНИЕ.

соответствует союзу И,

в программировании AND

обозначается знаком ^

обозначение логического элемента соответствующего логической операции И, соответствует знак &?

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

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

A^B^C = 1, только если А=1, В=1, С=1..

Таблица истинности коньюнкции имеет следующий вид:

А В А^В

0 0 0

0 1 0

1 1 1

1 0 0

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

Например:

Пусть есть суждения А= «Сегодня хорошая погода»

В= «Коля пошел кататься на лыжах»

Тогда коньюнкция А^В есть суждение:

Х = «Сегодня хорошая погода и Коля пошел кататься на лыжах»

Если хотя бы одно из этих суждений ложно, то естественно построенное выше суждение Х ложно.

Логическая операция ДИЗЬЮНКЦИЯ – иначе называется ЛОГИЧЕСКОЕ СЛОЖЕНИЕ

соответствует союзу ИЛИ,

в логических элементах обозначается 1

в программировании соответствует OR

обозначается знаком \/

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

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

A\/B\/C = 0, только если А=0, В=0, С=0

Таблица истинности дизьюнкции имеет следующий вид:

А В А\/B

0 0 0

0 1 1

1 0 1

1 1 1

Из таблицы истинности следует, что операция, дизьюнкции (операция «ИЛИ») – логическое сложение – немного но отличается от обычного алгебраического сложения. А именно: отличается лишь последней строкой: 1+1=1. Результат этот также не совпадает со сложением двоичных чисел ( 1+1=10). Это следствие того, что 1 является не числом «один», а только символом смысл которого был пояснен выше. Если имеются две истинные величины, то результатом их сложения будет истинная величина, но не может быть ни дважды истинно, ни полуистинно! Именно поэтому 1+1=0.

Например: пусть даны два суждения:

А= «Снег пойдет ночью»

В= «Снег пойдет утром»

Тогда суждение Х=А+В= «Снег пойдет ночью или утром»

В этом примере связка «ИЛИ» играет объединяющую роль.

Приведем другой пример. Даны суждения:

А= «Он придет сегодня»

В= «Он придет завтра»

Суждение Х=А+В = «Он придет сегодня или завтра»

В этом случае связка «ИЛИ» играет только разъединительную роль (её можно заменить разделяющим либо).

Составное суждение со связкой «ИЛИ» считается истинным, если истинно хотя бы одно из составных суждений, и считается ложным, если ложны все его составляющие.

Логическая операция ИНВЕРСИЯ – ОТРИЦАНИЕ – операция «НЕ»

в программировании «NOT»

обозначается неА или употребляется символ «-« над А

Имея суждение А, можно образовать новое суждение, которое читается как «неА» или неверно, что А.

Таблица истинности выглядит следующим образом:

А А

0

0 1

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

1 = 0 и 0 = 1

Пусть суждение А= «Мы любим информатику»

А = «Мы не любим информатику»

Отрицание А имеет значение «истинно», если исходное суждение ложно. И

наоборот, А имеет значение «ложно», если исходное суждение А истинно.

Логическая операция ИПЛИКАЦИЯ (от латинского implication – тесно связывать) – Логическое следование

Обозначается так: А В,

А – условие. В – следствие.

Если А, то В:

Таблица истинности

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

Вывод: результат будет ложным тогда и только тогда, когда из истинного высказывания (А) следует ложное следствие (В)

Логическая операция ЭКВИВАЛЕНТНОСТЬ (от лат. Aequivalens – равноценное) – Логическое равенство.

Обозначается так: А В

Таблица истинности

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

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

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

Приоритет логических операций:

СКОБКИ,

ИНВЕРСИЯ,

КОНЬЮНКЦИЯ,

ДИЗЬЮНКЦИЯ.

ИМПЛИКАЦИЯ